今天我们来继续研究tic-tac-toe这个游戏。
Tic-tac-toe的博弈树分析
当时还剩下最后一个问题，那就是，我们的策略一定能够得到平局结果吗？如果我们还想要得到C4范围内的棋局结果，还需要做哪些策略定制呢？
今天我们就来回答这个问题，先回顾一下视频：
视频1 tic-tac-toe的奇迹
//v.qq.com/txp/iframe/player.html? 除了这个平局所有可能情况所在的群的结构分析，我们并没有说清楚我们到底应该怎样下这个棋局能够保证赢，或者保证不输。关于这个问题所对应的策略，有一个非常好的工具叫决策树（在博弈论中也叫博弈树），因为每一步的状态都对应很多下法导致的不同结局，这恰好是状态到多个状态的一个没有环的关系（因为棋盘上棋子的数量一直在增加，不可能恢复），这恰好是DAG图的性质，不同的下法是可以到达同一个有马尔可夫性的状态的（即只关心目前的局面，不关心怎么下过来的）。若是以整个下法为状态而不作归并，那就是树了。用这个工具我们甚至可以去分析几乎所有的棋类游戏，复杂到围棋，简单到象棋，到我们今天讲的tic-tac-toe。
这是个复杂而庞大的议题，不过tic-tac-toe应该hai还是太简单了，以至于我们根据一下对称性，也就是叫等价棋局类的合并，可以在很有限的空间内，去穷举所有的棋局情况。
我们假设X，O两个符号是等价的，整个棋盘上D4群内的所有操作得到的棋盘结果等价，并且我们以靠左和上侧元素作为代表元素，剔除所有在对方听牌但是不堵以及有潜在成线不成的所有无效分支，多个可堵位置优先堵斜线以及左侧和上侧的原则（此时已经必输了）。于是我们有以下决策树的穷举结果：
图1 井字游戏先占中的所有可能下法
图中，标号上第一个元素0和1分别表示右手定则下的从头到手和反向方向，第二个表示站立以后要逆时针旋转的90度个数，其实也就是D4群内元素的表达了。
怎么样，如果粗略估计有C(9, 4)或2 ^ 9种结局甚至9!种路径确实放缩得有点厉害的话，那情况居然少到这么可怜恐怕也是没有想到的吧。这就是对称的威力，它在思维上直接像学会了用数来代表任何事物的多少比之于每个对象都需要重新画的人的优势一样。
在第2步也就是图中第二层处，根据C4的对称性，仅有角位和边位两种等效选择，我们取代表元素的原则是优先取左侧和上侧的位置落子，得到图中第二行的情况。
接着第3步的每种情况里都各有3种下法，而且是排除了轴对称的情况，只算左侧和上侧那一种情况。这里的对称蛮明显的，因为中心点处在中间，任何一个位置都可以连成对称轴，形成对称的两个等价位置。
注意这时候，因为我们规定能堵必须堵，而且要优先堵斜线，左上位置，加上有听必听，于是接着就在很多棋局情况下有必下策略，最常见的就是那种必须去堵的那唯一一个位置。于是在第4行的第4步里，分别有4,2,4,4种可能情况，其中在第5行的第一种情况还存在一个镜像的重合，只花了一个代表。
整个棋局最多也就5步（其实是最多4个可选下法，占中和必堵必听没有算）就确定结束了（这没什么好证明的，事实都全部摆在那了），要么以圈的先手胜利而告终，要么就是所谓的平局，只有唯一一种情况是后手能够获得胜利，注意我是指的双方都按照最基本的策略下：逢听必听，有堵必堵，先斜线，先左上。这应该也是最朴素的可行的下棋的感性逻辑，不见得都是最优的，更不一定是满足纳什均衡的。但是有堵必堵这一条，至少如果不这样下，一定更坏，是个dominating的策略，而逢听必听并不是。
先看看先手输的唯一情况。后手先占了角位，然后先手卡在了相邻的边位，最后选择了一一条虽然报听但是在一条边上听死的左下角位，才最终输掉。要防止这种情况，先手需要在被占角位以后，作死占同边位，再占同边的角位，这些条件都满足，才会真的输，不得不说，下得真菜。
那先手想赢有没有必胜策略呢？没有，因为可以看到，图中标有win的先手胜的结果都在第2层的第2个分支下，也就是说，只要第2步后手完成了占角，就可以保证不输了。而如果第一次没有占角，那么先手就存在像图中3行6列里占右上角后的必胜策略。如果错过，仍然还有两种必胜策略可供选择。总之，要保证必胜策略，得每一层往下对手可选路径内，都一直存在着必胜策略，直到到达叶子的胜局节点。而先手如果想赢，就只能期待对手会在第2步犯没有占角的错误，否则，只能是平局，下不好还有可能输。
而对于后手来说，是没有必胜策略的，因为只要按照图中的路线来走，只要先手在路径中某一避开了那唯一输的情况就好了。但是显然有必不输的策略，在第2步就能发现，只要占角就行了。
所以无论对于先手还是后手，要保证保平争胜，先下中间以后的策略都是优先占角，后手占角可以不输，先手占角在后手没有占角时有必胜策略，如果后手占了角，也能至少保证平局。
注意在最后的无论平局还是胜负的结果，都有很多完全重合的结果，最后的呈现相同，但是他们处在不同的分支路径下就代表不同的下法，只是关于结局对称而已。
还有一点是，我们这里只考察了先手会先下中心的下法。如果不这样下，那么假设后面任意步下了中心位，可以得到等效的棋局结果，但是前面的步骤略有不同。但是，占中是一个直觉上有先手优势的人必选的策略，讲不清道理，但是直觉上它能占据最多的优势，这里我就不详细分析不占中的下法了，那样情况较多，而且看起来都是一些很傻的下法，虽然符合规则，但繁琐一点也很容易分析清楚，这样下在博弈上是明显被另外策略统治的。
在matric67在果壳上的文章所说的，井字棋的最优策略是占角。哪怕是先手，不过这倒是可以看作是下棋风格和如何与人对抗了，在先占角的下法里，如果后手不占中就有必胜策略。如果占中后继续占角，尔后先手又占角了，那此时后手有必胜策略；否则，就是必然的平局。这看起来好像陷阱会比先占中好，不过也差不多，只是对抗和博弈的时候看对方在哪种下法中处于劣势，我们去对抗攻击就好了。
如果这里的议题是去研究先手和后手的必胜下法是否存在和怎么下的话，用到的数学理论则是纳什均衡以及逆向的状态固定倒推的思路，算法描述为min-max算法，这里不再展开，有机会我再单独写文章分享。
Tic-tac-toe的平局是怎么必现的？
最后我们来看下我们必然得到平局的游戏是怎么进行的。如果我们只是要D4的平局，那很简单，避开输的方法，剩下的再可赢的时候选择不赢即可。但是如果我们必须要平局而且是C4内的平局呢？这时候就要精挑细选下下棋的策略了。不必完备，只需要找到一组可行，且容易记忆的策略即可。
这个在商业道具井字游戏里有详细说明，这个我就不说了，说下我的记忆策略。我把最后平局的结果看做一个向前挥舞拳头的小人，竖直水平两条是头和手，另外两条是两只脚，我们以视线为法线方向看过去，用右手定则，规定我们想要的C4结果，是从头到手符合右手定则规定的。也就是上面元素标号第一个为0的情况。那具体要怎么下到这里呢？
我们选取的是1,1,3路径结果的镜像(0, 1)，这个策略最简单，对应的就是当观众第一步下在角位的时候，我们下在相邻边的边位上，并且使得从中心指向下到位置的向量左侧为观众的棋子，正好和图中的(1, 1)呈镜像关系。当观众第一步下在边位的时候，我们同样选择下在相邻边位上，并使得观众的棋子在新形成向量的右侧。这时候，对应图上，1,1,2路径的镜像结果，此时继续把右侧的两个子填满即为所求。中间可能出现可赢策略，但是我们选择放水。
综上，我的公式是：视线法向，右手头手，首次相邻，角左边右，右者继续。
以上。
其实，真正道具商卖的那个能够在背后拼出一个给定图案的下法，又是这些下法中的又一个更小的子集，因为你不能把拼图当成可以自由翻转的二面体啊，只能在C4的范围内的结果内变动。另外，每个棋子下哪个位置，落子顺序也是有讲究的，而且完全不能出错，因此最后其实就变成了，也只能变成了，一个我们下了中间位置以后，根据观众想下的位置我们选择对应的拼图块以及规划好后续的目标形状（C4中的一个）然后在后面的下法中，观众其实是没有任何自由度的。因为从第3块开始，每一块都必须方向和位置完全要固定才是，观众有任何真的位置选择，势必可能影响初始方向，哪怕调整好了正确的拼图块也无济于事，除非每个拼图块都本身就是C4图形，但那又何必自寻烦恼呢？
Bonus
这个魔术几乎可以看作是一个自动化魔术了，因为所见即所得，没有任何操作在观众的脑海里的推断是和真实发生不同的，只不过这个对象的数学结构较为复杂，也是没有这样的模型能力的人所不能够迅速反应的，这种差别才构造出如此的神奇效果。
因此我们就可以尝试着结合机器人技术来让机器完成这个表演了。下面这个视频是一个demo，其实并没有完全成型，不过也算是一个机器人变魔术的小成就吧！
视频2 icub机器人井字游戏魔术
//v.qq.com/txp/iframe/player.html?
下期的魔术表演先奉上，精彩下期继续！
视频3 五边形的奇迹
//v.qq.com/txp/iframe/player.html?
