井字棋优胜策略

井字棋可能是最简单的棋类游戏了,它简单到了成年人之间玩几乎总是平局的地步。因此,这个游戏貌似最多只能哄哄小孩子。
不过,对井字棋游戏中所有可能的情况进行一番细致的分析,你会发现一个你或许不会料到的惊人结论 ——
先手的最优策略不是稳坐正中央,而是先占一个角!

背景

因为怀旧电子宠物,在手机上下载了一个ios小游戏“Hatch”。
由于在这个电子宠物世界也存在金币,生存需要一定数量的金币,因此也同样存在几个挣金币的方法,其中一个就是井字棋。
考虑到挣金币的效率性,我放弃了几个简单无脑的游戏(包子剪子锤,概率性太大 / 接元宝,金币挣取效率低),最后决定研究一下井字棋优胜策略。
借助万能的搜索引擎,在果壳网搜到一篇井字棋下棋策略.

先手先占角

游戏开始后,二话不说先占上一个角(比如左下角吧),那么对方总共有五种本质不同的应对策略:

  1. 占据靠近你的那条边
  2. 占据靠近你的那个角
  3. 占据远离你的那条边
  4. 占据远离你的那个角(即对角)
  5. 占据正中央的位置

在这五种策略中,前面四种都是陷阱——如果对方不慎选择了前面四种策略中的任意一种,他就必然输掉。(同样,如果你是后手,被人先手占角,只有选择占中才不会被人牵着走)

tic-tac-toe-1

上图显示了在这四种情况下你可以如何把对方一步步逼上绝路。

假设对方走正下方,占据了一个靠近你的边(最左边的那个图),你就可以占据正中央来应对,逼迫对方不得不走右上角。
这时,只需要在左上角放下一子,你就赢定了——图中出现了两条只差一子的连线,对方不可能兼顾得了。

右边几个图显示了对方第一步棋的其它几种走法。选择合适的位置应对他,都可以在下一步迫使对方只剩一种走法,接下来你便可以下出“一箭双雕”的棋,让对方无法彻底封杀你。

也就是说,当你占据棋盘一角后,在对方下一步棋的八个可选位置中,其中七个位置都是必输的,陷阱摆满了几乎整个棋盘。
在面对“先走一角”的诡异开局时,你的朋友说不准就会慌了手脚,没能冷静地占住中间,决定了必败的命运。

tic-tac-toe-2

对方要是真的走了正中间,你仍然有赢的机会。你可以占住右上角的位置(如上图)。
如果对方不幸走了剩下的两个角中的一个(上图左),你便能故技重施,再次取得胜利。
只有对方选择了边上的位置(上图右),才能躲过这一系列的陷阱,最终变成平局。

后手还是先占角

tic-tac-toe-3

作为后行者,你遇到的往往是“先走中间”的经典开局。
此时,千万别忘了,先占角仍然是一条金科玉律。如果你不慎走了某条边的位置,对方可就赢定了!对方可以向上面的第一幅图那样,在正右方下子应对,逼迫你把下一步棋落在正左方。
此时,对方便可占据右上方的位置,同时产生出两条仅差一子的连线。右边三幅图则显示,如果你在角上应对,最终总会是一盘和棋。

反过来,先手第一步走中间,棋盘上剩下的八个位置中有四个位置都是会导致对方必败的陷阱,因此先手第一步走中间后,获胜的机会也并不小。
井字棋可以算是决策树最简单的游戏之一了。在历史上,对井字棋的类似分析很大程度上启发了人们对组合游戏的认识,在博弈论中起着举足轻重的作用。

转载自果壳网:http://www.guokr.com/article/4754/

博客推荐:http://www.matrix67.com , 一位数学爱好者的博客,里面有很多有趣的数学问题。