考虑这样一个双人对弈游戏：在一个8×8的方阵里分别填上1-64这64个正整数。然后A和B两个人轮流在格子中取数，A先取，B后取。取数的规则很简单：取过的数不能够再取，并且除了第一次以外，以后每次取的数必须与某个已经取过的格子相邻。所有数都取完后，所取数之和最大的人获胜。
    很显然，这个游戏对于A更有利一些。我们可以轻易构造一个初始状态，使得先取的人必胜。考虑A的这样一个策略：总是取能取的数中最大的一个。如果每次A都可以取走整个棋盘中最大的那个数，那A就赢定了（因为每次B接下来取的数都比A小）。这样的初始状态是很容易构造出来的，比如我们只需要从左往右从上至下依次填入这64个数就可以了，这可以保证如果从n到64的所有数都取走了，则n-1也可以被取走。
    现在的问题是，能否构造一个初始状态，使得后取的人有必胜策略？提示，解决这道题需要有超强的“整人”能力。你得想出足够多的坏点子才能找到弄死先行者的方法。你的心肠坏到足以解决这个问题吗？

  
    解决问题的关键在于，我们要给A埋下“陷阱”。考虑这样一种局部构造：奇数个大数彼此相连，这些大数周围一圈全是小数。上图就是这样一个陷阱，钻石代表大数，其余黄色的格子都是小数。只要A踩进了某个黄色格子，他就中计了：B和A开始轮流取大数，但大数只有奇数个，因此B获得的大数比A多一个。为了让事情变得更简单，我们只考虑最简单的一种陷阱：只有一个大数，周围的邻格都是小数。我们还有几个难点：万一A一开始就把陷阱内的钻石取走咋办，又如何避免自己不会掉进陷阱，还有我们必须保证B从这些陷阱里赚到的足以弥补在其它地方亏的。要想有足够多的陷阱对A起作用，我们得布上至少三个陷阱，这样A可以在最能赚的陷阱里开局，但无法避免落入另外两个陷阱。为了保证自己不会掉进陷阱，我们可以把棋盘的其余部分划分为多米诺骨牌（一个个1×2的小长方形），这样的话不管A取哪一个格子，B总可以取对应的另一个格子，不会踩到陷阱。于是我们想到了下面的这个构造：

    我们在四个陷阱里分别填上1-2-3-61，4-5-6-62，7-8-9-63，10-11-12-64这四组数，每个多米诺骨牌里填上两个相邻的数。这样的话，A的最好策略就是从第一个陷阱里开始取数。他能从第一个陷阱里赚到(61+2)-(1+3)=59分，但他在其它陷阱里将分别丢掉(62+4)-(5+6)=55分、(63+7)-(8+9)=53分、(64+10)-(11+12)=51分。而多米诺骨牌一共只有24个，他最多只能捡24分回来，这是远远不够的。因此，先取者必输无疑。

参考资料：http://www.brand.site.co.il/riddles/200802q.html

  
    有这样的一类组合游戏，对于任一个游戏局面，游戏双方的合法决策都完全一样，游戏对战双方的唯一区别就是看谁先走。这样的游戏叫做Impartial Games。像什么报数啊，取火柴啊，取石子啊，这些游戏都属于Impartial Games；而象棋、围棋等要分棋子颜色的游戏则不属于Impartial Games。共享状态的游戏几乎没有可玩性，因为游戏开始前我们就能知道谁赢谁输（如果双方均使用最佳策略）。棋局的任一状态只有两种，面对这个棋局的人要么必胜要么必败。考虑这样的一个递推关系：如果一个状态是必胜态，那至少有一种走法能走成一个必败态留给对方；如果一个状态是必败态，那它怎么走都只能走到必胜态。运用这样的关系，我们可以自底向上推出初始状态是必胜还是必败。
    近来有人提出一个名为Atropos的游戏，它就是一个即使计算机也很难办的Impartial Game，它能保证这个游戏仍然具有可玩性。游戏在一个Sperner三角形上进行，上图就是一个边长为7的Sperner三角形。游戏开始后，双方依次在白色的圆圈里涂上红色、绿色或者蓝色，已经涂过颜色的圆圈不能再涂色。另外，只要有可能，所涂的圆圈都必须紧挨着上次对方涂的那个圆圈。谁先涂出三种颜色都有的小三角形，谁就输掉这场游戏。

  
    注意这个游戏是不可能出现平局的。当所有白色圆圈全部涂上了颜色后，至少会出现一个红绿蓝小三角形。为了证明这一点，我们可以在所有的绿色和红色圆圈中间画一个箭头，红的在箭头右边，绿的在箭头左边。这些箭头一定组成了一条一条的路径，它们既不会交汇也不会分岔。但整个图的边界上进来的箭头有4个，出去的箭头只有3个，于是至少有一条路径在里面走死了，也即迎面碰上了蓝色的圆圈。这样，我们就找到了一个红绿蓝三色都有的小三角形。

    这个游戏虽然属于Impartial Games，但它仍然具有可玩性。从直觉上看，这个游戏中的先手后手几乎没有区别，谁也不占优势。这篇论文则严格证明了，判断Atropos游戏的最佳策略属于PSPACE-complete，这是所有使用多项式空间的问题中最难的一类，所有使用多项式空间的问题都可以（在多项式的时间内）约化到它。这说明，Atropos游戏没有什么很显然的“决窍”，即使利用计算机也很难确定最优决策。

在线游戏：http://cs-people.bu.edu/paithan/spernerGame/SpernerGame.html (Java Applet)
查看更多：http://cs-people.bu.edu/paithan/spernerGame/

    小学奥赛的经典题目：两个人轮流在黑板上写一个不大于10的正整数。规定不准把已经写过的数的约数再写出来。谁最后没写的了谁就输了。问是先写的人必胜还是后写的人必胜，必胜策略是什么。
    答案很巧妙。先写者有必胜策略。他可以先写下数字6，现在就只剩下4、5、7、8、9、10可以写了。把剩下的6个数分成三对，分别是(4,5)、(7,9)、(8,10)，每一对里的两个数都不成倍数关系，且它们各自的倍数（如果出现过）必然是同时出现。因此不管你写什么数，我就写它所在的数对里的另一个数，这样可以保证我总有写的。
    今天偶然看到一个加强版，不知大家见过没有：规则不变，可以写的数扩展到所有不大于n的正整数。对于哪些n先写者必胜？证明你的结论。

    你会有一种被骗的感觉-_-b
    其实，不管n是多少，先写者总有必胜策略。考虑一个新的规则“不准写数字1”。如果加上这个新规则后先写者有必胜策略，那么这个策略对于原游戏同样适用（因为1是所有数的约数，本来就不能写）；如果在新规则下后写者必胜，则原游戏中的先写者写下数字1，然后他就变成了新规则下的后写者。于是不管怎么样，先写者总是有必胜策略。
    To 3楼：忘了提一句，只要是双方共用状态（合法的决策完全相同）的对弈游戏，其中一方肯定有必胜策略。棋局的任一状态只有两种，面对这个棋局的人要么必胜要么必败。考虑这样的一个递推关系：如果一个状态是必胜态，那至少有一种走法能走成一个必败态留给对方；如果一个状态是必败态，那它怎么走都只能走到必胜态。运用这样的关系，我们可以自底向上推出初始状态是必胜还是必败。

    
    Update: 感谢网友FreePeter的精彩评论。这种分析方法有一种很形象的名字叫做Strategy-stealing，它的另一个经典例子是Chomp游戏。游戏在一块矩形的巧克力上进行，巧克力被分为MxN块。两人轮流选择其中一个格子，然后吃掉这一格及它右边、下边和右下角的所有格子。最左上角的那一块巧克力有毒，谁吃到谁就输了。上图是一个可能的对战过程。我们可以用类似的方法证明先手必胜。假设后手有必胜策略，那么先手把最右下角的那一块取走。注意到接下来对方不管走哪一步，最右下角的那一块本来也会被取走，因此整个棋局并无变化，只是现在的先手扮演了后手的角色，可以用后手的那个必胜策略来应对棋局，这样便巧妙地“偷”走了后手的必胜策略。
    上面所举的例子都是双方共用状态的游戏（ICG游戏），因此至少有一方存在必胜策略。对于其它一些非ICG游戏，我们也可以用类似的方法证明后手不可能有必胜策略（但在这里并不能说明先手一定必胜）。比如对于井字棋游戏，假设后手有必胜策略，那先手就随便走一步，以后就装成是后手来应对。如果在哪一步需要先手在已经下过子的地方落子，他就再随便走一步就是了。这种证明方法成立的前提就是，多走一步肯定不是坏事。事实上，对于所有这种“多走一步肯定不是坏事”的且决策对称的游戏，我们都可以证明后手是没有必胜策略的。

    在数学中，比较运算是有传递性的。如果A>B，且B>C，那么一定有A>C。但现实生活中却不一定是这样。三个人两两之间进行比赛，有可能A比B要强，B比C要强，但C反过来赢了A。事实上，这种现象即使在数学中也是存在的。在一些概率事件中，类似的“大小关系”很可能并不满足传递性。
    右边有四颗骰子，分别用A、B、C、D来表示。我让你先选择一颗你自己认为最好的骰子，然后我再从剩下的三个骰子中选一个。抛掷各自所选的骰子后，谁掷出的数字大，谁就赢了。那么，你应该选哪颗骰子好呢？
    其实，不管你选哪一个骰子，我获胜的概率总是要大一些，因为剩下的三个骰子中总有一个骰子比你的要好。事实上，在这四颗骰子中，A赢B的概率是2/3，B赢C的概率是2/3，C赢D的概率是2/3，D赢A的概率还是2/3，因此不管你选的是哪一个骰子，只要我选择它左边的那一个（如果你选的是最左边的，则我选择最右边的），我总保证有2/3的概率获胜。你认为这样的事情有可能吗？对你来说这样的事情合乎情理吗？

    如果你不信的话，我们可以一起来算一算：
    A和B比时，只要A扔出4的话A就赢了，这有2/3的概率；
    B和C比时，只要C扔出2的话B就赢了，这有2/3的概率；
    C和D比时，若C扔出6则C一定能赢，若C扔出2则胜负几率对等，因此C获胜的概率是(1/3) + (2/3)*(1/2) = 2/3；
    D和A比时，若A扔出0则D一定能赢，若A扔出4则胜负几率对等，因此D获胜的概率是(1/3) + (2/3)*(1/2) = 2/3。

Problem: game 取数游戏
题目来源：Matrix67根据经典问题改编

问题描述
    选数游戏是一个两人游戏。两人将轮流从1到9这九个数字中取数，取过的数不能再取。我们规定，谁取到的数里能找到三个数，使得这三个数的和为15，谁就获得了这次游戏的胜利。如果A取了1、6、7三个数，B取了2、3、5，若这时该A继续取数，则A取8可以获得胜利，因为当A获得了数字8后，出现了1+6+8=15。
    在游戏的每一着中，你可以得到此时游戏的状态。请你编程选择一种赢得游戏的最佳策略。

输入格式
    第一行输入若干个用空格隔开的数，表示你已经取了的数。这些数递增排列。
    第二行输入若干个用空格隔开的数，表示对手已经取了的数。这些数递增排列。
    当某一行没有数字（某个游戏者还没有选数）时，该行仍然会留出位置。

输出格式
    输出你认为此时你的最佳选择。

样例输入
1 6 7
2 3 5

样例代码
    下面的代码演示了游戏的这样一个策略：每一次总是选择最大的没有被取过的数。

program game;
var
   hash:array[1..9]of boolean;
   i:integer;
begin
   assign(input,'game.in');
   reset(input);
   repeat
      read(i);
      hash[i]:=true;
   until eof;
   close(input);

   for i:=9 downto 1 do
      if not hash[i] then break;
   assign(output,'game.out');
   rewrite(output);
   writeln(i);
   close(output);
end.

评分方法
    该题目将通过选手之间的循环赛进行评分。
    在某两个选手对抗时，测试程序将导入这两个选手的源程序并进行编译，然后轮流为选手编写输入文件实时描述对战情况。选手的输出文件将作为此次选手的决策提交上来。当游戏已经出现获胜方或无法继续进行时，测试程序自动结束。每两个选手比赛时将分两场进行，一场对抗后先行者将进行交换。任一次对抗中，选手胜一场得2分，负一场得-2分，平一场得0分（这个分数不是选手该题的最后得分）。对比赛得分进行排名后，若总选手数为n，你的排名为i，那么你的得分为(n-i+1)*100/n。得分为小数则取下整。排名相同则平分该段得分。
    选手程序出现以下情况将作为该次对抗的负者处理：
        选手程序单着运行时间超过1秒；
        选手内存占用超过64M；
        选手程序未输出决策或输出错误；
        选手程序非正常退出；
        选手程序发生错误导致评测程序非法退出。

    大家有没有看出来，这个游戏就是一个井字棋游戏。3个数加起来等于15一共有8种情况，而这8种情况恰好对应一个3阶幻方中的三个横行、三个纵列和两个对角线。也就是说，如果把这个游戏想成在下面的棋盘中进行，那就和井字棋游戏没什么两样了。

   +—+—+—+
   | 8 | 1 | 6 |
   +—+—+—+
   | 3 | 5 | 7 |
   +—+—+—+
   | 4 | 9 | 2 |
   +—+—+—+

    关于井字棋游戏，之前我曾有过研究。
    原来学博弈论之类的东西时，我曾写过一个程序，计算井字棋游戏的最佳策略。但不管我怎么搞，这个程序总是先走最角落的位置，这是十分可笑的。我一直在想，我的程序哪点儿有问题。后来我想到了。我的程序没有任何问题，而是人的习惯性思考出的错。我的程序计算出来的结果是对的，在井字棋游戏中开局占领一个角的胜算最大。

    比如说，现在我占了最左下角的那一个位置。那么下一步如果你走的是画了“X”的位置，你就输了。

   +—+—+—+
   | X | X | X |
   +—+—+—+
   | X |   | X |
   +—+—+—+
   | O | X | X |
   +—+—+—+

    下面的图1到图4这四个棋谱，它包含了除第二步走中间以外所有的分支情况。可以看出，如果你第二步不占领中间的话，你是必败的。
    图5告诉我们，即使对手占住了中间，第四步棋也有2/6个陷阱可以置他于死地。而另外4/6将导致棋局最终打平。假设每一步对方都是随机走的话，打到图6的情况概率为(1/8) * (4/6)，约为8.33%。反过来，我的胜算超过了90%。这在理论上可能是最大的了。
    当然，对手没有那么傻。面对这种情况，理智的人第二步总会想要占领中间的格子。考虑到这一点的话，胜算或许不到50%。

    仔细思考，你会发现，如果你第一步占领了中间的话，胜算是可以达到50%的。图7表明了这样一种情况，如果你第一步走中间，而对手不小心走到了边上，那么他就完了。比起前面的那些来，这里的陷阱可能更隐蔽一些。
    剩下的三个图表明，对手走了4个角中的一个后，最终结果必然是平局。

    至于以上这么多棋谱到底该选用哪一个，这个决策是属于自己的。

    我们考虑自己先行的所有情况的同时，也看清了自己作为后行者可能遇到的陷阱。对照以上棋谱，我们可以轻易获得平局的结果。

    由于井字棋游戏的总的情况数也只有那么多，变数不大，因此这个东西是一个非常入门级的东西。实际写程序的时候，分类讨论的效果比博弈树更好。

Matrix67原创
转贴请注明出处