“抢15”游戏简析

昨天在上“科学计算软件”课时，讲到了一个“抢15”游戏（Pick15），就是在1~9这9个数字中，双方轮流选一个数字，不可重复，谁的数字中有三个数字的和为15的，谁就是赢家。

这是个简单的游戏，属于博弈论范畴。在博弈论中有一个著名的“策梅洛定理”（Zermelo's theorem），它指出在二人的有限游戏中，如果双方皆拥有完全的资讯，并且运气因素并不牵涉在游戏中，那先行或后行者当一必有一方有必胜/必不败的策略。比如中国象棋就属于这一类游戏，它告诉我们对于其中一方必有一种必不败策略（有可能和棋，有可能胜，反正不会输）。当然，策梅洛定理只是告诉我们其存在性，并没有告诉我们怎么发现这个策略，甚至连哪一方有这种最优策略都没有给出判别方法。这是幸运的，因为如果真有一天发现了这种策略，那么像象棋这类博弈就失去了意义了。

上述的抢15游戏当然也属于这类游戏。不同于象棋的千变万化，它的变化比较简单，而且很容易看出它对先手有着明显的优势。下面我们来分析一下。

在我们的课程中的Matlab的Pick15程序中，人是先手，而电脑遵循一个“三步走策略”

●如果可以，走制胜之着。
●如果需要，阻止对手制胜一击。
●否则，随机占一个空的小正方形。

这个策略有什么问题吗？

我们先来看一种情况，比如先手选4；那么后手可以在其他8个数字随便选，比如后手选7；接着先手选8；后手只能选3；接着先手只能选5，但这时候后手就败了，因为为了“堵住”先手的胜利，后手必须选6和1，两者不可兼得，因此必败。整个流程如下：

这个情况至少告诉我们，上述“三步走”策略是不够完美的，因为按照它的规则，先手选4，后方就有可能选7，但是后方选7却导致了必输的结果。

这个过程可以抽象为一般的形式：

整个流程仅仅取决于前三个数字。显然，如果方框中的每个数字都不相同，且都属于1~9这9个数字，那么红方就胜利了。红方当然愿意让这件事情发生了。但是上述描述有相当多的约束条件，有这么容易实现吗？其实真的很容易实现...我用不等式简单分析了一下，发现这些条件有相当多的部分是兼容的，有些满足了一个条件，就顺带满足了一大片条件了。这样说似乎不大形象，用公式分析也不大好，于是用Matlab编写了一个“很挫”的程序，得出了下表：

先 后 先

1 2 6
1 4 8
2 1 4
2 1 5
2 3 5
2 3 6
2 4 7
2 4 8
2 6 8
2 6 9
3 2 4
3 6 8
4 1 2
4 1 5
4 2 3
4 2 6
4 7 5
4 7 8
4 8 6
4 8 9
5 1 2
5 1 4
5 3 2
5 3 6
5 7 4
5 7 8
5 9 6
5 9 8
6 2 1
6 2 4
6 3 2
6 3 5
6 8 4
6 8 7
6 9 5
6 9 8
7 4 2
7 8 6
8 4 1
8 4 2
8 6 2
8 6 3
8 7 4
8 7 5
8 9 5
8 9 6
9 6 2
9 8 4

这个表说的是假如先手取第一个数字，而后手取第二个数字，那么先手再取第三个数字，那么先手就胜利了！这里边就包含了48种必胜情况了！！当然，必胜情况还不仅仅这些。

假如$a+c-b < 1$或者$a+c-b > 9$又怎样呢？这对于先手来说也是一种优势，因为它告诉我们这一步不论先手选什么，后手都不会胜利，先手免除了“后顾之忧”，因此可以尽可能选择让自己有利的数字。如果先手选择了该数字后，会导致后手下一步无法“堵住”，那么先手也就胜利了。这种情况有多少呢？让人非常意外，这种情况居然有80种！！必胜法则如下：

先 后 先 后 先
1 7 5 9 6
1 7 5 9 8
1 7 6 8 5
2 6 4 9 8
2 7 4 9 5
2 7 4 9 8
2 7 5 8 4
2 7 5 8 9
2 8 4 9 6
2 8 6 7 4
2 9 5 8 6
2 9 5 8 7
2 9 6 7 5
2 9 6 7 8
2 9 7 6 5
3 1 8 4 5
3 9 4 8 5
3 9 5 7 4
3 9 5 7 8
4 1 8 3 2
4 1 8 3 5
4 2 8 3 6
4 3 9 2 5
4 6 2 9 8
4 7 2 9 5
4 7 2 9 8
4 8 2 9 6
4 9 3 8 5
4 9 5 6 3
4 9 5 6 8
5 1 6 4 2
5 1 6 4 7
5 1 7 3 2
5 1 7 3 6
5 1 8 2 3
5 1 8 2 4
5 3 8 2 1
5 3 8 2 6
5 3 9 1 2
5 3 9 1 4
5 7 1 9 6
5 7 1 9 8
5 7 2 8 4
5 7 2 8 9
5 9 2 8 6
5 9 2 8 7
5 9 3 7 4
5 9 3 7 8
5 9 4 6 3
5 9 4 6 8
6 1 5 4 2
6 1 5 4 7
6 1 7 2 5
6 2 8 1 4
6 3 8 1 2
6 3 8 1 5
6 4 8 1 2
6 7 1 8 5
6 8 2 7 4
6 9 2 7 5
6 9 2 7 8
7 1 5 3 2
7 1 5 3 6
7 1 6 2 5
7 9 2 6 5
8 1 3 4 5
8 1 4 3 2
8 1 4 3 5
8 1 5 2 3
8 1 5 2 4
8 2 4 3 6
8 2 6 1 4
8 3 5 2 1
8 3 5 2 6
8 3 6 1 2
8 3 6 1 5
8 4 6 1 2
9 3 4 2 5
9 3 5 1 2
9 3 5 1 4

从统计的结果来看，如果先手选偶数，那么后手必须选5，否则必输！！（当然假设先手按照最优法则）。因此上面的“三步走”策略不仅仅是有问题，而是相当有问题，因为我们将有$\frac{7}{8}$的胜率！还有没有其他必胜法则呢？我觉得没有了，因为5个字都没有胜利的话，那么我觉得后手再选了一个数字后，只剩下三个数字可选，没有什么选择自由了，应该已经是和局了。

当然，这种纯粹用计算机分析的方法顶多提供了一些实用的信息，而没有给我们带来多少美感。有一种方法可以让我们从另一个角度看待这个问题，我们下回分解（当然网上已经有这方面的分析）。下面附上我那很挫的程序：
三子即胜判断_Matlab.txt

五子即胜判断_Matlab.txt

胜局结果.xls

转载到请包括本文地址：https://kexue.fm/archives/1973

更详细的转载事宜请参考：《科学空间FAQ》