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

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

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

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

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

这个策略有什么问题吗?

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

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

这个过程可以抽象为一般的形式:
pick15_2.png

整个流程仅仅取决于前三个数字。显然,如果方框中的每个数字都不相同,且都属于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


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

如果您觉得本文还不错,欢迎点击下面的按钮对博主进行打赏。打赏并非要从中获得收益,而是希望知道科学空间获得了多少读者的真心关注。当然,如果你无视它,也不会影响你的阅读。再次表示欢迎和感谢!