Chomp 游戏
把一堆石子排成n行m列,两人轮流从里面取出石子,条件是取出一个石子后所有在它右边和上面的石子也要被取走。谁取走最后一个石子就算输。以3*5的棋盘举例来说,先手取了(2,5),因此(3,5)也要被取走;后手取了(3,3),同时也要取走(3,4)。现在棋盘的状态如下(O代表这个位子的石子还没被取走,x代表已经被取走):
3 O O x x x
2 O O O O x
1 O O O O O
1 2 3 4 5
接下来先手又取了(2,1),于是第二排和第三排就一颗石子都不剩了
3 x x x x x
2 x x x x x
1 O O O O O
1 2 3 4 5
后手取(1,2)
3 x x x x x
2 x x x x x
1 O x x x x
1 2 3 4 5
接下来先手就只能取最后一个石子了,后手胜。
这个游戏像是 Nim Game 的二维版本。于是问题也来了,能不能保证先手或者后手有必胜策略呢?
答案是除了 1 * 1 的棋盘,对于其他大小的棋盘,先手总能赢。有一个很巧妙的证明可以保证先手存在必胜策略,可惜这个证明不是构造性的,也就是说没有给出先手怎么下才能赢。证明如下:
如果后手能赢,也就是说后手有必胜策略,使得无论先手第一次取哪个石子,后手都能获得最后的胜利。那么现在假设先手取最右上角的石子(n,m),接下来后手通过某种取法使得自己进入必胜的局面。但事实上,先手在第一次取的时候就可以和后手这次取的一样,进入必胜局面了,与假设矛盾。
另外这个证明是基于 Zermelo’s theory,这个理论保证在这样一种游戏中(两人博弈,信息完全公开,不存在偶然事件且能在有限步里面决出胜负),先手或后手肯定存在一种必胜策略。
相关链接:
- [http://en.wikipedia.org/wiki/Zermelo’s_theorem_(game_theory)](Zermelo’s theorem)
- http://www.win.tue.nl/~aeb/games/chomp.html
本作品采用知识共享署名-非商业性使用 3.0 版本许可协议进行许可,欢迎转载,演绎,但是必须保留本文的署名 zellux(包含链接),且不得用于商业目的。