Chomp类游戏——必胜策略分析

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

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

Chomp!游戏

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

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

证明如下：

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

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

类Chomp游戏

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

Chomp类游戏——必胜策略分析

原文：https://www.cnblogs.com/lfri/p/11626187.html