Aiur

zellux 的博客

Chomp 游戏

Permalink

把一堆石子排成n行m列,两人轮流从里面取出石子,条件是取出一个石子后所有在它右边和上面的石子也要被取走。谁取走最后一个石子就算输。以3*5的棋盘举例来说,先手取了(2,5),因此(3,5)也要被取走;后手取了(3,3),同时也要取走(3,4)。现在棋盘的状态如下(O代表这个位子的石子还没被取走,x代表已经被取走):

1
2
3
4
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),于是第二排和第三排就一颗石子都不剩了

1
2
3
4
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)

1
2
3
4
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,这个理论保证在这样一种游戏中(两人博弈,信息完全公开,不存在偶然事件且能在有限步里面决出胜负),先手或后手肯定存在一种必胜策略。

相关链接:

评论