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原创
转贴请注明出处