f(Program,Poet)=Programet

有时候博弈论问题真的让人疯狂啊……以为自己“旁观者清”，却不得不轮流站在双方的角度上想问题，还要每一次都最优——搞不好要精神分裂的……

周末的时候在ACM杭州赛区网络选拔赛上做到一题，差点晕掉。还好最后还是把它吃了。下面是问题的中文描述。

红黑双方进行一种棋类比赛，棋盘如图：

棋盘分为4行，每行10列，分为左右两半。这四行用不同英文字母标识（按图示方法标识）。

开始时，红黑双方需要在每行放一枚棋子，红方棋子只能放在左五列，黑方棋子只能放在右五列。此时，每一行上都有红黑双方各一枚棋子。

然后掷骰子决定先后手，轮流移动棋子，每次可以移动一枚，规则如下：

• A行的棋子只能向靠近对方棋子的方向移动，每次一格；一旦移到对方棋子所在的格子内，就取得胜利，比赛结束。
• B、C行的棋子可以向左右两个方向任意移动，但是不能移到对方棋子所在的格子内，也不能越过对方棋子。
• D行的棋子只能向背离对方棋子的方向移动，每次一格。
• 每次必须移动一枚棋子，否则直接判负。

现在是两位绝顶聪明的棋手对阵，告诉你双方的放棋子的位置和先后手关系，你要说出他们之中谁必胜。因为两位棋手都绝顶聪明，现在可以确定的是他们一定会在D5、D6放棋子。

问题似乎比较复杂，于是先考虑几个子问题。

如果只有A这一行？显然，如果开始时两棋子距离为偶数格，先手方就杯具了。大家期望的是自己移动棋子后两颗棋子距离为偶数格，使自己占优；为了方便，这里记这种情形为[A-Even]。如果某方破坏[A-Even]，对方必能重建[A-Even]，且两棋子越来越接近，因而破坏[A-Even]必定带来失败。

下面把B、C两行也加入考虑范围。在某一方走之前[A-Even]，占劣势，就会考虑用B、C行使局势逆转。比较容易想到的情况是，如果使自己的B行、C行棋子和对方的相邻同时[A-Even]，那么对方要么破坏[A-Even]，要么在B或C行后退。如果对方选择后退，则自己又可以跟进“压住”对方。这样下去，对方只能退到边界上边界上无法移动，然后己方必胜。这里把在B、C两行都压住对方的情形记为[BC-Close]。某方走完后同时达到[A-Even]和[BC-Close]，则这一方必胜。

更常见的一种情况是，开始时有[A-Even]，但B、C两行棋子都不紧邻，不可能一步达到[BC-Close]；如果强行使一行紧邻，则对方可立即使另一行紧邻，拿到[BC-Close]，己方就杯具了。因而此时不能让任何一行紧邻，而应该尽量靠近对方，逼对方先使一行紧邻。也许你能想到的是使B、C一行棋子间距为2，但是如果另一行棋子间距大于2，对方又可使该行棋子间距为2，结果你不愿紧邻一行，只能后退，此时对方又跟进保持距离，最终你退到边界上，杯具了。或许你现在发现了，应该达到一种状况[BC-Same]，即B、C两行棋子间距相等。对方一旦破坏[BC-Same]，则己方又能通过重建[BC-Same]，并且这次重建要么减小间距，要么把对方往边界逼，必定最后达到[BC-Close]。

现在的结论是，某方走完后若同时达到[A-Even]和[BC-Same]，则这一方必胜。（从这里开始把[BC-Close]视为[BC-Same]的一种特殊情形。）

这样开局时若同时有[A-Even]和[BC-Same]，则先手必败；若只有[A-Even]和[BC-Same]其中之一，则先手必定可以走出[A-Even]和[BC-Same]同时存在的情形，先手必胜。

开局时没有[A-Even]和[BC-Same]？先手必定不能走出[A-Even]和[BC-Same]其中之一。可以想见的是，先手还可以选择走出另一种B、C两行棋子间距不同的情形，比如把B/C行棋子间距从2/3走成2/1。此时没有形成[A-Even]和[BC-Same]其中之一，而对方必定也会选择相似的策略。那么如何才能占优？还是逼对方后退。显然，如果把B/C行棋子间距走成1/2或2/1，对方只能后退，结果可想而知。而B/C行棋子间距走成3/4或4/3，对方走后必可形成1/2或2/1，必胜；可推知2n-1/2n这样的数对都有类似的性质，将这些情况统称为[BC-Pair]。在没有[A-Even]的情况下走出[BC-Pair]，必胜。

现在，可以把情况完整归纳了：开局时若同时有[A-Even]和[BC-Same]，则先手必败；若没有[A-Even]但有[BC-Pair]，则先手必败；其余情况下先手必胜。

那么D行呢？其实D行没有任何影响。A、B、C三行直接决定了先手的胜败，必胜方必定不会主动移动D行的棋子，必败方若移动D行，则必胜方同样立即移动D行，胜负关系不变。

就写到这里吧。快晕掉了。

本文由 最后的叶子 创作，转载或引用前请联系我们。

相关文章：

1. Thank You
2. Thank You (2)
3. 推荐时间：数学家的情歌
4. Thank You (3)
5. Lose Yourself (In The Digits)——π Rap

2010年9月21日 星期二