Chomp游戏（必胜策略分析）

游戏简介

Chomp是一个双人游戏，有m x n块曲奇饼排成一个矩形格状，称作棋盘。

----两个玩家轮流自选一块还剩下的曲奇饼，而且还要把它右边和下边所有的曲奇饼都取走（如果存在）

----先吃到左上角(1,1)那块曲奇饼的玩家为失败

如图所示

------红方选择(3,3)---> ------蓝方选择(1,4)---->

----红方选择(1,2)---> -----蓝方选择(2,1)-->

------------>红方玩家只能选左上角那一块，失败

分析

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

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

下面证明：除去 1 x 1大小的棋盘外，其他大小的棋盘，先手存在必胜策略。

证明：（反证法）

假设棋盘规模为m x n。

首先，游戏不可能产生平局。

其次，由于每一步移动至少吃掉1块曲奇饼干，因此不超过 mn 步后游戏必定结束。

由策梅洛定理，这个确定性二人有限游戏信息完备，且不存在平局，则或者先行一方有必胜策略，或者后行一方有必胜策略。

如果后手有必胜策略，使得无论先手第一次取哪个石子，后手都能获得最后的胜利。

那么现在假设先手取最右下角的石子(m,n) ，接下来后手可以取某块曲奇(a,b) 使得自己进入必胜的局面。

事实上，先手在第一次取的时候就可以取曲奇 (a,b) ，之后完全模仿后手的必胜步骤，迫使后手失败。

于是产生矛盾。因此不存在后手必胜策略，先手存在必胜策略。

注意：这个证明是非构造性存在性证明，也即只是证明了先手必胜策略的存在性，但没有构造出具体必胜策略。而且目前还没有人给出Chomp一般性的必胜策略。

其中一些简单的情况，可以找到必胜策略：

1、棋盘只有一行，但多于一格

-------先手拿去除左上角的全部即可

2、棋盘是正方形，但多于一格

-------先手选取(2,2),之后无论后手做什么，先手只要模仿即可（即关于对角线对称选取）

3、棋盘只有两行

------先手取第二行最后一个，之后无论后手选什么，先手总能采取合适的选择，使得第一行比第二行多一个

类似问题

1、三维Chomp游戏

将曲奇排成 P x Q x R 的立方体，两个玩家轮流自选吃掉一块剩下的曲奇饼，若取走的曲奇饼为 (i,j,k) ，则也要取走所有满足 i ≤ a ≤ P，j ≤ b ≤ Q ， k ≤ c ≤ R 的曲奇饼(a,b,c)（如果存在）。

可以类似地将Chomp游戏扩展到任意维，并可以类似地证明，先手都存在必胜策略。

2、有限偏序集上的Chomp游戏

Chomp游戏可以推广到在任意一个存在最小元 a 的有限偏序集(S,≤)上：两名游戏者轮流选择S中的元素 x ，移走 x 以及所有 S 中比 x 大的元素。失败者是被迫选择最小元 a 的玩家。

如果  (S,≤) 有最大元素 b ，那么在偏序集上的Chomp游戏存在一个获胜策略.

3、约数游戏

 给定一个大于1的自然数 N ，两个游戏参与者轮流选择N的大于1的正约数，但不可选择之前被选择过的因子的倍数（例如 N = 72，有一方之前选择了4，则之后任一方都不可以再选择36）

4、删数游戏

给定整数集合 {1,2,...n} ，两个人轮流从中选择一个数字，并将它和它的约数从集合中删除，删除最后一个数的人获胜。

以上几个游戏，类似Chomp游戏，得到结论就是无论 n 是几，都是先手必胜。

转载自：Liu言杂记

参考链接：中国大学mooc 离散数学 刘铎

__EOF__

本文作者： Rogn's Blog 本文链接： https://www.cnblogs.com/lfri/p/9899014.html 关于博主： 评论和私信会在第一时间回复。或者直接私信我。 版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！ 声援博主： 如果您觉得文章对您有帮助，可以点击文章右下角【推荐】一下。

相关知识

游戏必胜策略问题.pptx
讲题比赛游戏中的必胜策略问题(取棋子游戏)课件
讲题比赛游戏中的必胜策略问题(取棋子游戏).ppt
军棋怎么摆必胜 军棋的基本玩法和策略
五子棋必胜阵法有什么 必胜阵法汇总
猛鬼宿舍怎么玩可以必胜猛鬼宿舍必胜攻略
游戏策略
必胜最强补习班好玩吗 必胜最强补习班玩法简介
尼姆游戏的必胜策略，用二进制解~
军棋必胜阵法100赢