7

我知道这不是问这个问题的正确地方，但也许一个聪明的人会遇到并有解决方案。

我正在尝试编写一个电脑游戏，我需要一个算法来解决这个问题：

游戏在 2 名玩家之间进行。每边有 1.000 美元。共有三个“盒子”，每个玩家写下他要放入这些盒子的金额。然后比较这些数量。谁把更多的钱放在一个盒子里，谁得 1 分（如果每人抽半分）。谁得分多，谁就赢得他的对手 1.000 美元。示例游戏：

玩家 A: [500, 500, 0] 玩家 B: [333, 333, 334]

玩家 A 获胜，因为他赢得了 Box A 和 Box B（但输掉了 Box C）。

问题：放置资金的最佳策略是什么？

我还有更多问题要问（与算法相关，与数学无关），但我需要先知道这个问题的答案。

更新（1）：经过更多研究，我了解到这些类型的问题/游戏被称为Colonel Blotto Games。我尽了最大的努力，发现关于这个主题的（高度技术性的）文档很少。简而言之，我遇到的问题（如上所述）被称为简单的 Blotto 游戏（只有三个具有对称资源的战场）。困难的是那些拥有 10 多个非对称资源的战场。我读过的所有文件都说简单的 Blotto 游戏很容易解决。问题是，他们都没有真正说出那个“简单”的解决方案是什么。

更新（2）：我写了一个小的 actionscript 文件来演示 Tom Sirgedas 提到的论文中的策略。您可以在megaswf对其进行测试。说明：单击三角形内的一个点。红色区域代表获胜案例。蓝色区域代表失败案例，白色细线代表平局。

4

3 回答 3

4

我在这篇论文中找到了一个最优策略：http ://www.rand.org/pubs/research_memoranda/2006/RM408.pdf

我们称之为 Blotto 的策略。

在此处输入图像描述

看上面的图表。你所做的任何动作都可以用三角形上的一个点来表示。论文中的策略是在六边形中随机选择一个点。选择更接近六边形边缘的点概率更高（六边形中心的概率为0，并线性放大到六边形轮廓处的最大概率。六边形轮廓上的每个点具有相等的概率。）

此解决方案适用于“连续”Blotto，但我假设您对离散情况感兴趣（将 N 个部队分成 3 组）。当 N 是 3 的倍数时，将 Blotto 的策略应用于离散情况非常有效。对于 N 的其他值，我能够对六边形边框进行小幅调整，效果很好，但并不完美。

如果有一种策略可以打败这个策略，那么一定有一些静态的动作可以战胜 Blotto 的策略。没有，除了当 N 不是 3 的倍数时，似乎在大三角形和六边形相交的线上的移动（例如移动 <0,.5,.5>）将战胜 Blotto 的策略略多于输。对于 N=100，差异似乎小于 1%，并且对于更大的 N 继续缩小。

实现 Blotto 策略的代码：

// generate a random number in the range [0,x) -- compensate for rand()%x being slightly un-uniform
int rnd( int x ) { int r; while ( 1 ) { r = rand(); if ( r < RAND_MAX/x*x ) return r % x; } }

// distance from center of triangle/hexagon to (x,y,z), multiplied by 3 (trilinear coordinates)
int hexagonalDist3( int x, int y, int z, int N ) { return max(max(abs(N-x*3),abs(N-y*3)),abs(N-z*3)); }

void generateRandomSimpleBlottoMove( int& x, int& y, int& z, int totalTroops )
{
   int N = totalTroops;
   while ( true )
   {
      x = rnd(N+1);
      y = rnd(N+1);
      z = N-x-y;

      // keep only moves in hexagon, with moves closer to the border having higher probability
      double relativeProbabilityOfKeepingThisMove = hexagonalDist3(x,y,z,N) > N ? 0 : hexagonalDist3(x,y,z,N);

      // minor adjustment for hexagon border when N is not a multiple of 3 -- not perfect, but "very close"
      if ( N % 3 != 0 && hexagonalDist3(x,y,z,N) == N ) 
         relativeProbabilityOfKeepingThisMove = N*(N%3)/3; 

      // possibly keep our move 
      if ( rnd(N) < relativeProbabilityOfKeepingThisMove )
         break;
   }
}
于 2011-03-03T01:14:52.030 回答
0

所以这实际上是一个博弈论问题（经济学）而不是一个离散的数学问题，重新标记你的问题可能会吸引你想要的那种关注。在博弈论中，“解决方案”的概念通常是纳什均衡。对于零和游戏，事实证明您要解决的算法是线性规划问题。有关如何设置它的示例，请参阅此 wikipedia页面。

于 2011-03-01T05:29:39.963 回答
-1

在我看来，证明这个博弈没有纯纳什均衡是相当容易的。纯策略是固定策略，例如 [333,333,334]。我的证明草图如下：

对于玩家 A 所玩的任何纯策略，玩家 B 可以找到另一个获得 B 2 分的纯策略。例如，如果 A 播放 [500,500,0]，则 B 播放 [501,0,499]，或者如果 A 播放 [333,333,334]，则 B 播放 [500,500,0]，依此类推。总有办法得到2分。当然，这意味着玩家 A 将获得 1 分。

类似地，对于玩家 B 的任何策略，玩家 A 都可以找到另一个让他得到 2 的纯策略。因此，不存在纯纳什。

另外，我认为可以证明（两者）的策略

1/3 [500,500,0]、1/3 [500,0,500]、1/3 [0,500,500]

（以 1/3 的概率玩 [500,500,0]，以 1/3 的概率玩 [500,0,500]，以 1/3 的概率玩 [0,500,500]）是该博弈的混合纳什均衡。在这种策略下，他们的预期收益（#points）是 3/2。证明对我来说似乎很费力。也许别人会有一个简单的证明。

混合纳什尽可能接近“最优”。这场比赛可能还有其他混合纳什均衡。

于 2011-03-01T20:16:51.213 回答