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

Question

我有一个关于我创建的游戏的一个非常简单的问题(这不是作业):以下方法应该包含什么来最大化收益:

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)方法应该进入什么才能最大化平均收益？为什么？

Answer 1

由于每个玩家使用您的goForBiggerResource方法中描述的相同策略,并且您尝试最大化总体回报,最好的策略是三个玩家坚持使用本地资源,一个玩家参加大型游戏.不幸的是,因为他们不能就战略达成一致,而且我认为没有一个球员不能被分类为大型猎人,所以事情变得棘手.

我们需要随机化玩家是否参加大型比赛.假设p是他为之而去的概率.然后根据有多少大型游戏猎人将案件分开,我们可以计算案件的数量,概率,收益,并在此基础上计算预期收益.

• 0 BGH:(4选0)个案,(1-p)^ 4个概率,4个支付,预期4个(p ^ 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(p ^ 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,对于所有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;
}