资源配置(最优策略)

Question

我知道这不是提出这个问题的正确位置,但也许是一个聪明人遇到并有解决方案.

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

游戏在2名玩家之间进行.每边都有1.000美元.有三个"盒子",每个玩家记下他要放入这些盒子里的钱.然后比较这些数量.谁在一个盒子里放了更多的钱,得分为1分(如果每个人得到半分).获得更多积分的人赢得了对手1.000美元.游戏示例:

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

玩家A获胜是因为他赢得了方框A和方框B(但输掉了方框C).

问题:放钱的最佳策略是什么？

我有更多问题要问(算法相关,而不是数学相关)但我需要首先知道这个问题的答案.

更新(1):经过一些研究后,我了解到这些类型的问题/游戏被称为Colonel Blotto Games.我尽了最大努力,发现了很少(高技术性)的文件.简而言之,我所遇到的问题(如上所述)被称为简单的Blotto游戏(只有三个具有对称资源的战场).困难的是具有10个以上具有非对称资源的战场.我读过的所有文件都说简单的Blotto游戏很容易解决.问题是,他们都没有真正说出那个"简单"的解决方案.

更新(2):我写了一个小动作文件来演示Tom Sirgedas提到的论文中的策略.你可以在megaswf测试它.说明:单击三角形内的一个点.红色区域代表胜诉案例.蓝色区域代表丢失的情况,微小的白色线代表抽奖.

Answer 1

我在本文中找到了最佳策略：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;
   }
}