解决一个简单的游戏最大化

我有一个关于游戏我创建了一个很简单的问题(这不是做作业):什么都要下面的方法包含最大化收益:

private static boolean goForBiggerResource() { return ... // I must fill this };

我再次强调,这不是功课:我想了解什么是在这里工作。

该“战略”很简单:只能有两种选择:真或假。

“游戏”本身非常简单:

P1 R1 R2 P2 R5 P3 R3 R4 P4

  • 有四名球员(P1,P2,P3和P4)和五个资源(R1,R2,R3,R4一切都是值得的1和R5,价值2)
  • 每个玩家有恰好两个选择:要么去接近它的开始位置的资源,给1和玩家是一定要得到(没有其他玩家可以获得该资源第一)OR玩家可以尝试去资源可值得一2 ...但是其他球员可能会去这一点。
  • 如果两个或更多的球员去为更大的资源(一个价值2),那么他们就会到达,同时更大的资源,只有一名选手,随机的,会得到它和其他玩家(S)去为该资源将得到0(他们不能回去资源价值1)。
  • 每个球员发挥了同样的策略(在方法goForBiggerResource定义的())
  • 玩家不能“讲”给对方一个战略达成一致
  • 游戏运行100万次

所以基本上我要填写方法goForBiggerResource(),它返回 true或false,在某种程度上最大限度的回报。

下面是允许测试解决方案的代码:

private static final int NB_PLAYERS = 4; private static final int NB_ITERATIONS = 1000000; public static void main(String[] args) { double totalProfit = 0.0d; for (int i = 0; i < NB_ITERATIONS; i++) { int nbGoingForExpensive = 0; for (int j = 0; j < NB_PLAYERS; j++) { if ( goForBiggerResource() ) { nbGoingForExpensive++; } else { totalProfit++; } } totalProfit += nbGoingForExpensive > 0 ? 2 : 0; } double payoff = totalProfit / (NB_ITERATIONS * NB_PLAYERS); System.out.println( "Payoff per player: " + payoff ); }

例如,如果我提出以下解决方案:

private static boolean goForBiggerResource() { return true; };

然后,所有四名球员会去更大的资源。 只是其中之一会得到它,随意。 超过一百万次迭代每个玩家的平均收益将是2/4这给0.5和程序应输出:

每个玩家得偿所愿:0.5

我的问题很简单:应该进入方法goForBiggerResource什么()(返回true或false),以最大化平均收益,为什么?

--------------解决方案-------------

由于每个玩家使用你的描述相同的策略goForBiggerResource方法,并尝试最大限度地提高整体收益,最好的策略是三个球员与当地的资源,并坚持一个球员去为大型游戏。 不幸的是,因为他们不能在战略达成一致,我认为没有球员不能区分一个大游戏猎人,事情变得棘手。

我们需要一个随机玩家是否也适用于大型游戏还是不行。 假设p的概率是他去为它。 然后根据许多大游戏猎人有是如何分离的情况下,我们可以计算出的病例数,概率,收益,并在此基础上,预期收益。

  • 0 BGH:(4选择0)的情况下,(1-p)的^ 4概率,4-回报,预期4(对^ 4-4p ^ 3 + 6P ^ 2-4p + 1)的
  • 1 BGH:(4选1)的情况下,(1-P)^ 3 * P的概率,5收益,预计20(-p ^ 4 + 3P ^ 3-3p ^ 2 + P)
  • 2 BGH:(4选2)的情况下,(1-P)^ 2 * P ^ 2概率,4-回报,预期24(对^ 4-2p ^ 3 + P ^ 2)
  • 3 BGH:(4选择3)的情况下,(1-p)的* P ^ 3概率,3回报,预期12(-p ^ 4 + P ^ 3)
  • 4 BGH:(4选4)的情况下,P ^ 4的概率,2回报,预计2(P ^ 4)

然后我们需要最大化预期回报的总和。 这是-2p ^ 4 + 8P ^ ^ 3-12p 2 + 4P + 4,如果我正确地计算。 由于第一项是-2 <0时,它是一个凹函数,和根其衍生物的希望之一,-8P ^ 3 +的24p ^ 2-24p + 4,将最大限度地预期收益。 将其插入一个在线多项式求解器,它返回三个根,其中两个复杂的,第三个是P〜0.2062994740159。 第二是衍生物^ -24p 2 + 48P-24 = 24(-p ^ 2 + 2P-1)= -24(P-1)^ 2,这是<0,所有的p!= 1,所以我们确实发现最大值。 在(总体)预期收益是在这个最大的评估,围绕4.3811015779523多项式,这是每一个玩家的回报1.095275394488075。

因此,获胜的方法是这样的

private static boolean goForBiggerResource ()
{
return Math.random() < 0.2062994740159;
}

当然,如果玩家可以使用不同的策略和/或互相对战,这是一个完全不同的问题。

编辑:另外,你可以欺骗;)

private static int cheat = 0;

private static boolean goForBiggerResource ()
{
cheat = (cheat + 1) % 4;
return cheat == 0;
}

我想你试过如下:

private static boolean goForBiggerResource() {
return false;
};

在这里没有球员试图去,是值得他们正在因此保证,因此每次都各得价值资源1资源:

每个玩家得偿所愿:1.0

我想也是,如果你问这个有趣的问题是因为你想有一个更好的答案。

诀窍在于,你需要什么是所谓的“混合战略”。

编辑:好 ,我来了一个混合策略......我不明白怎么帕特里克发现20%那么快(当时他评论说,你贴你的问题只分钟后),但,是的,我发现基本相同值太大:

private static final Random r = new Random( System.nanoTime() );

private static boolean goForBiggerResource() {
return r.nextInt(100) < 21;
}

其中给出,例如:

每个玩家得偿所愿:1.0951035

基本上,如果我没有记错,你想在“纳什均衡”,特别是这个阅读维基百科页面:

“纳什均衡是混合策略,玩家选择的概率分布在可能的行动来定义”

你的问题/如果我没有记错的话也简单的例子可以用来说明为什么串通的玩家可以做的更好平均回报:如果玩家能colude,他们会得到1.25的平均水平,击败了1.095我。

另外请注意,我的答案包含逼近错误(我只检查随机数从0到99),并取决于随机PRNG一点,但你应该得到的想法。

如果玩家不能合作并且没有记忆,只有一个实现可能的方式goForBiggerResource :随机选择的值。 现在的问题是什么,是用最好的速率。

现在, 简单的数学 (不是真的编程相关的):

  • 假设率x代表留在小的资源的可能性;
  • 因此,对于没有球员去为大单的机会是x^4 ;
  • 因此对于至少一个玩家要大个的机会是1-x^4 ;
  • 利润总额为x + ( 1 - x^4 ) / 2
  • 发现的最大的式为0%<= x <= 100%

其结果是约79.4%(对于返回false)

嗯,我觉得你的基本问题是,所描述的游戏实在是微不足道。 在所有情况下,最优策略是坚持使用本地资源,因为去为R5预期收益只有0.5(1/4 * 2)。 提高对R5奖励至4,并且它变得均匀; 有没有更好的策略。 奖励(R5)> 4,它总是希望采取R5。

分类:java的 时间:2015-03-14 人气:0
分享到:

相关文章

Copyright (C) 55228885.com, All Rights Reserved.

55228885 版权所有 京ICP备15002868号

processed in 2.936 (s). 10 q(s)