非传统题型练习:解析一道循环赛题目

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