首先介绍一个重要定理——策梅洛定理(Zermelo)

策梅洛定理,表明在二人参与的游戏/博弈中,如果满足:
--------游戏的步骤数有限
--------信息完备(二人都了解游戏规则,了解游戏曾经所发生过的信息)
--------不会产生平局
--------确定性(游戏中不会加入随机因素)
则先行一方有必胜策略,或者后行一方有必胜策略。

Chomp!游戏

问题:有一个n*m的棋盘,每次可以取走一个方格并拿掉它右边和上边的所有方格。拿到左下角的格子(1,1)者输,那么谁会赢呢?

先给结论:除了(1, 1)先手必败外,其他都是先手必胜。

证明如下:

根据策梅洛定理,这个问题至少有一方存在必胜策略。

如果后手必胜,也就是说无论先手取哪个石子,后手都能获得必胜策略。那么假设先手取得最右上角得石子,接下来后手通过某种方法让自己进入必胜局面。但事实上,先手在第一次取得时候就可以和后手这次取得一样,抢先进入必胜局面,与假设矛盾。

类Chomp游戏

例1:
 有n张卡片,第i张纸片上写着数字i,每次可以取走一张纸片和数字是该纸片因数的纸片,那么谁会赢呢?
solve:除了n=1的情况,先手必赢。
例2:
现在有一颗含n个节点的有根树,根节点是1,每个点初始时都为白色。每次可以把任意一个白色节点到根节点经过的所有的点(包括该节点)变成黑色。谁最后把整棵树染黑了,谁就输了。
solve: 除了n=1的情况,先手必赢。
 
 

参考链接;https://blog.csdn.net/TSY_1222/article/details/83277648

05-21 04:22