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

Question

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

3

我有一个关于我创建的游戏非常简单的问题（这不是作业）：为了最大化回报，以下方法应包含什么内容：

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点的资源，并确保玩家能够得到该资源（没有其他玩家可以先到达该资源）或者玩家可以尝试去争夺价值为2的资源...但是其他玩家也可能会去。
如果两名或更多玩家争夺更大的资源（价值为2），那么他们将同时到达更大的资源，只有一名玩家，随机地，会得到它，而其他去争夺该资源的玩家将得到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），并且为什么？

- Cedric Martin

玩家是否记得模拟的前几轮发生了什么，还是每个游戏都像第一次开始？ - brc

一个固定的选择可能不是最优的，尝试分析一种概率策略，比如有20%的几率选择中心点。 - Patrick

@brc：每个游戏都像第一次开始一样 :) - Cedric Martin

@Patrick：你的评论看起来像是已经给出的答案。你怎么知道固定选择不能是最优的？比如说20%的概率怎么办？ - Cedric Martin

2

选择中间时，您可以赢得1分，但当太多人选择中间时，您可能会输掉2分。因此，即使只有0.01％的几率选择中间，也比任何两个固定选择都要好，因为这种比例下冲突的可能性非常小。存在某些最佳比例，其中更高的得分机会恰好抵消了冲突的增加机会。 - Patrick

4个回答

3

我猜你已经尝试过以下操作:

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

当没有任何玩家试图获取价值为2的资源时，他们每次都保证可以获得价值为1的资源：

每个玩家的收益：1.0

我想，如果你提出这个问题，也许是因为你觉得有更好的答案。

诀窍在于你需要使用所谓的“混合策略”。

编辑：好的，这里我提供一种混合策略……我不知道Patrick是如何那么快地找到20%的（当他评论时，你发布问题后只过了几分钟），但是，是的，我也发现了基本相同的值：

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

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

例如，给出如下结果：每个玩家的收益：1.0951035

如果我没有误解的话，您想了解“纳什均衡”维基百科页面，特别是这一段：“纳什均衡是通过混合策略来定义的，那里的玩家选择可能动作的概率分布”

如果我没理解错您的问题/简单例子，也可以用它来说明为什么勾结的玩家可以获得更高的平均回报：如果玩家能够合作，他们可以获得平均1.25的回报，这比我得到的1.095要高。

另外请注意，我的答案包含近似误差（我只检查从0到99的随机数），并且有点依赖于随机PRNG，但您应该能够理解。

- TacticalCoder

我认为在这里没有任何策略是保证比“返回false”更好的。 - Charlie Martin

1

请参考Frigo的答案，了解如何精确计算所需概率，以便在问题的约束条件下混合策略最优。 - TacticalCoder

2

如果玩家无法合作且没有记忆，那么实施goForBiggerResource只有一种可能的方式：随机选择一个值。现在的问题是什么是最好的使用率。

现在进行简单的数学计算（与编程无关）：

假设比率x表示留在小资源的概率；因此，没有玩家选择大资源的机会为x^4；因此，至少有一个玩家选择大资源的机会为1-x^4；总利润为x + ( 1 - x^4 ) / 2；找到该公式在0% <= x <= 100%范围内的最大值。

结果约为79.4%（返回false）。

- user85421

在我写这篇文章时，还没有看到Frigo的答案 - 它是相同的答案，只是使用了x = 1-p。 - user85421

啊，非常感谢，这基本上就和另一个用户回答的一样：） - Cedric Martin

@CarlosHeuberger 只有在竞技游戏中允许使用不同的策略，而不仅仅是单一的策略时，这才有意义。 - Frigo

@Frigo不同意-我仍然认为使用相同的策略但带有记忆来最大化总利润会很有趣...也许太简单了。 - user85421

他们仍然需要不同的内存（=不同的策略），否则共享内存将出现勾结，从根本上违反规则。这是一条非常微妙的界限。 - Frigo

@Frigo - 不同的内存状态并不代表不同的策略。比如，如果一个玩家获得了更多的资源，他下一轮就会去争取更少的资源。 - user85421

-1

嗯，我认为你的基本问题是所描述的游戏很琐碎。在所有情况下，最优策略是坚持使用本地资源，因为去获取R5的预期收益仅为0.5(1/4*2)。将R5的奖励提高到4，它就变得平衡了；没有更好的策略。reward(R5)>4，这时取R5总是划算的。

- Charlie Martin

我认为你是不正确的。另一个答案和“Patrick”都评论说，像你建议的固定策略不能是最优的。 - Cedric Martin

这并不是微不足道的。每个人都坚持使用他的本地资源只能得到4的回报，三个玩家坚持使用本地资源，一个人选择大资源可以获得5的回报。 - Frigo

但是玩家们不能合作并且都使用相同的策略。“返回false”策略对于所有玩家来说预期回报率恰好为1，而另一种策略--正如你费尽心思计算得到与我相同的结果--预期回报率为0.5。声称预期回报率为0.5比回报率为1更“最优”是我不熟悉的“最优”用法。 - Charlie Martin

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Frigo · Accepted Answer

由于每个玩家都使用您的goForBiggerResource方法中描述的相同策略，并且您尝试最大化总体回报，因此最佳策略是三名玩家坚持使用本地资源，一名玩家去攻击大猎物。不幸的是，由于他们无法就策略达成一致，我假设没有玩家可以被区分为大猎人，事情变得棘手起来。

我们需要随机决定玩家是否攻击大猎物。假设p是他攻击的概率。然后根据有多少名大猎人将情况分开，我们可以计算出情况数、概率、回报，并基于此计算期望回报。

0个大猎人：(4选0)种情况，(1-p)^4概率，4回报，期望为4(p^4-4p^3+6p^2-4p+1)
1个大猎人：(4选1)种情况，(1-p)^3*p概率，5回报，期望为20(-p^4+3p^3-3p^2+p)
2个大猎人：(4选2)种情况，(1-p)^2*p^2概率，4回报，期望为24(p^4-2p^3+p^2)
3个大猎人：(4选3)种情况，(1-p)*p^3概率，3回报，期望为12(-p^4+p^3)
4个大猎人：(4选4)种情况，p^4概率，2回报，期望为2(p^4)

然后我们需要最大化期望回报的总和。如果我计算正确，那么该总和为-2p^4+8p^3-12p^2+4p+4。由于第一项为-2 < 0，它是一个下凸函数，希望其导数的一个根将最大化期望回报。将它代入在线多项式求解器中，它返回三个根，其中两个为复数，第三个为p ~ 0.2062994740159。二次导数为-24p^2+48p-24 = 24(-p^2+2p-1) = -24(p-1)^2，对于所有p != 1，它都是小于0的，因此我们确实找到了一个最大值。该（总体）期望回报是在此最大值处计算的多项式，约为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;
}