资源布局（最优策略）
我知道这不是问这个问题的恰当地方，但也许是一个聪明人遇到并有解决方案。
我试图写一个电脑游戏，我需要一个算法来解决这个问题：
这场比赛是在2名球员之间进行的。 每边有1.000美元。 有三个“盒子”，每个玩家都记下他要放入这些盒子的金额。 然后比较这些数量。 在一个盒子里放更多钱的人得分1分（如果每个都得到半分）。 获得更多积分的球员赢得对手1000美元。 示例游戏：
玩家A：[500,500,0]玩家B：[333,333,334]
玩家A获胜是因为他赢得了方框A和方框B（但是丢失了方框C）。
问题：放置这些资金的最佳策略是什么？
我有更多的问题要问（算法相关，而不是数学相关），但我需要首先知道这个答案。
更新（1）：经过一些更多的研究后，我发现这些类型的问题/游戏被称为Colonel Blotto Games。 我尽了最大的努力，发现了很少（高度技术性）的文件。 削减它，我有问题（如上所述）被称为简单的Blotto游戏（只有三个对称资源的战场）。 困难的是拥有10+以上非对称资源的战场。 我读过的所有文件都表明，简单的Blotto游戏很容易解决。 问题是，他们中没有一个真正说出那种“简单”的解决方案。
更新（2）：我写了一个小动作文件来证明Tom Sirgedas提到的论文中的策略。 你可以在megaswf上测试它。 说明：点击三角形内的一个点。 红色区域代表胜利案例。 蓝色区域表示失败案例，微小的白色线条表示绘制。
我在本文中找到了一个最佳策略：http://www.rand.org/pubs/research_memoranda/2006/RM408.pdf
我们称之为Blotto的策略。
看看上面的图表。 你做的任何动作都可以用三角形上的一个点来表示。 报纸中的策略是在六边形中随机挑选一个点。 选择更接近六边形边缘的点的概率较高（六边形中心的概率为0，线性放大到六边形轮廓的最大概率，六边形轮廓上的每个点具有相等的概率）。
此解决方案适用于“连续”Blotto，但我认为您对离散案例感兴趣（将N部队分成3组）。 将Blotto的策略应用到离散案例中效果很好，当N是3的倍数时。对于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;
}
}
所以这实际上是一个博弈论问题（经济学）而不是一个离散的数学问题，重新标记你的问题可能会吸引你想要的那种注意力。 在博弈论中，“解”的思想通常是纳什均衡。 对于零和游戏，原来你想解决的算法是一个线性规划问题。 请参阅此维基百科页面以获取如何设置它的示例。
在我看来，证明这个游戏没有纯纳什均衡是相当容易的。 纯粹的策略是固定的，如[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]）是该游戏的混合纳什均衡。 在这种策略下，他们的预期收益（＃点）是3/2。 证据对我来说似乎很辛苦。 也许别人会有一个简单的证明。
我们可以得到一个混合纳什关闭“最佳”。 这场比赛可能还有其他混合纳什均衡。
链接地址: http://www.djcxy.com/p/5195.html