Chomp ©

字段是行和列的交叉点，标记为（行、列）。
图块是某部分区域上的图片。
位置由所有带有图块的区域组成。

让我们从简单的问题开始，也就是小位置。为了创建它们，我们点击'计算机：关闭'。如果我们再点击(2,1)，就只剩下一排图块了。

下一个玩家，即你的对手能做什么？
- 通过单击（1，2），只剩下（1，1）上的图块，因此您输了。

然后，让我们单击“新游戏”，然后在（3，1）和（2，2）上在第 2 行有一个图块，在第 1 行中有一个图块。

下一个玩家可以做什么？
- 通过单击（1，3），只剩下三个图块。你能看到你没有机会吗？

让我们点击“新游戏”，然后点击（3，1）和（2，3）。

下一个玩家可以做什么？
- 你的对手可以点击（1，4）。你能看到你没有机会吗？

你能总结一下在哪些位置只有 2 行的图块你没有机会赢得比赛吗？
- 如果顶行比第二行多一张图块，那么无论你做什么，你的对手总是可以采取行动，让顶行比第二排多一张图块。然后，无论您做什么，最终您都需要选择（1，1）图块并输掉游戏。

如果单击图块，则下方和右侧的所有图块也会被删除。这个规则是对称的;即整个游戏具有以下对称性：如果我们交换行和列，则规则保持不变：右侧的所有图块都变为下面的所有图块，下面的所有图块都变为已删除图块右侧的所有图块。换句话说，如果我们沿着穿过（1，1）和（2，2）的线镜像一个位置，那么新位置可能看起来不同，但它具有相同的状态。获胜的举动也将是相同的移动，只是镜像也是如此。

众所周知，第一行有 3 个图块，第二行有 2 个图块的位置是没有希望的。镜像位置有哪些图块？
- 镜像后，左列有 3 个图块，第二列有 2 个图块。

我们知道所有无望的位置都只在前两行有图块。对称性告诉我们所有无望的位置，只有在前两列中都有图块？
- 前两列中具有图块的绝望位置是第一列比第二列多一个图块的位置。

这是另一个没有机会的位置：单击“新游戏”，然后打开（4，1），（2，2）和（1，4）。

如果对手在这个位置上采取行动，你的回答是什么？
- 您需要确保在移动后，顶行和第一列的长度再次相同。通过重复这种模式，对手最终将不得不拿下（1，1）图块并输掉。

因此，如果第一行和第一列具有相同数量的图块并且没有其他图块，则位置是没有希望的。哪些职位可以换成这样的职位？
- 如果一个位置的行数和列数相同，无论其他位置有多少个图块：继续移动（2，2）只会留下第一行和第一列的长度相等，让对手没有机会。因此，如果一个位置在顶行中的图块数量与左列相同，那么您在（2，2）处玩并赢得游戏。

要玩好Chomp，需要了解输赢位置。获胜位置是指无论对方做什么，如果一个人发挥最佳状态，都可以强制执行胜利的位置。失败的位置是指如果另一方发挥最佳状态，则没有机会。以下几点是人们在数学中所说的定义。在Chomp中，输球和赢牌通过以下3点来定义：
1. 如果只剩下一个图块（在左上角），那么这是一个亏损的位置。
2. 如果存在导致对手失去位置的移动，则位置是获胜位置。
3. 如果每一步都为对手带来胜利，则位置是失败位置。
乍一看，上述各点可能看起来毫无用处，因为胜势是由败势解释的，而败势是由胜势解释的。然而，这个定义是以下棋为基础的，而每一连串的移动最终都会导致单一的图块位置，根据第1点，这就是一个输的位置。

有没有可能双方都无法强制执行胜利？（难）
- 我们将提出一个小定理并加以证明。该证明将告诉我们如何达到完美的移动。该证明是一个归纳证明，即表明我们要证明的声明对一张图块来说是真的，然后表明如果它对任何数量的图块都是真的，那么它对多一张图块也一定是真的，即N+1张图块。既然这句话对N=1块图块是真的，那么它对N+1=1+1=2块图块也一定是真的。但既然对N=2来说是真的，那么对N+1=2+1=3块图块来说也一定是真的，以此类推；也就是说，对任何数量的图块都是如此。
- Lemma（小定理）：每个位置都是赢家或输家。
- 归纳证明：
- 推理基础：如果该位置只有一张图块，那么这张图块就在左上角，那么根据Chomp规则，该位置就是一个输的位置（表明如果只有N=1张图块，那么该定理就是真的）。
- 归纳假设： 我们假设该定理对所有有多达 N 张图块的局面都是真的，即有1,2,...,N 张图块的局面不是赢就是输。
- 感应步骤： 我们现在要证明，那么所有有N+1张图块的局面也必须是输或赢的局面。
- 在下文中，P 是一个有N+1块图块的任意位置。如果P被减少了一步，那么新的位置一定有≤N块图块，因此根据归纳假设，它是一个输棋或赢棋位置。如果P可以在一步棋中被减少到一个输的位置，那么P就是一个赢的位置。如果不能，那么P只能在一步棋中被还原为一个胜势。但是如果一个局面只能在一步棋中减少到一个赢的局面，那么P一定是一个输的局面。这就证明了P（有N+1块图块）要么是胜势，要么是败势。这表明所有的位置（有N+2,N+3,...块图块）不是赢就是输。
  
  证明结束 ∎
- 补充说明： 归纳步骤提供了一种方法来决定所有位置（达到一定规模）是赢还是输。它的定义如下：
  
  我们从N=1开始，将该位置标记为输的位置。然后确定所有有2块图块的位置的状态，然后是有3块图块的位置，以此类推，每次都使用较小位置的状态知识，并将新发现的输家位置添加到已知输家位置列表中。
- 这是一种非常有效的方法，可以找到一定规模的所有赢家和输家位置。随着数字越来越大，计算机程序会有所帮助。所需成分如下：
  - 一个过程，可以通过知道小于N个图块的所有位置有效地创建N个图块的所有位置
  - 可以有效地检查是否可以将位置减少到另一个给定位置的过程。
  我们将留给您更多考虑它，也许可以编写这样的计算机程序。

有多少输和赢的位置正好有 2 个图块？
- 只有两个可能的位置正好有 2 个图块、顶行有 2 个图块或左列有 2 个图块。这两个位置都是获胜位置。

有多少输和赢的位置正好有 3 个图块？
- 总共有 3 个可能的位置正好有 3 个图块。它们由 2 个获胜位置和 1 个失败位置组成。你能弄清楚他们是什么职位吗？

有多少输和赢的位置正好有 4 个图块？
- 有 5 个可能的位置正好有 4 个图块。所有这些位置都是获胜位置。

有多少输赢位置正好有 5 个图块？
- 总共有 7 个可能的位置正好有 5 个图块。从这些位置来看，3个是亏损位置，4个是获胜位置。你能弄清楚它们是哪些吗？

矩形位置是赢还是输的位置？
- 以下引理回答了这个问题。证明是存在证明。它只会证明一个获胜举动的存在，而不显示这个举动是什么。尽管如此，了解引理对您的游戏很有用，如下所述。
- 引理： 除 1 格位置外的所有矩形位置都是获胜位置。
- 证明： 为了证明这是真的，我们需要考虑两种可能的情况：
  1. 移除棋盘右下角的图块是一个成功的举动。
  2. 删除右下角的图块并不是一个成功的举动。
- 如果情况 1 为真，则意味着矩形是获胜位置，这支持引理。
- 如果情况 1 不成立，那么我们需要考虑情况 2。根据我们之前所做的证明，移除右下角图块所产生的位置必须是获胜位置，这意味着它必须存在获胜动作。但是，由于矩形中的每个移动都会移除右下角的图块，因此无论获胜移动是在角移动之后还是代替角移动，由第二个移动（获胜移动）产生的失败位置都是相同的。这意味着获胜的移动可以立即进行，从而证明矩形位置存在获胜的移动。
- 证明结束 ∎
- 补充说明： 虽然引理没有告诉我们获胜的举动是什么，但知道矩形位置是获胜位置已经很有帮助了。因此，不应进行创建矩形位置的移动（1x1 位置除外）。

你能确定任何方板的获胜动作是什么吗？
- 对于所有大小为 >1 的正方形，唯一的获胜步骤是（2，2）。

对于哪些类似于正方形的位置，相同的移动是成功的移动？
- 移动（2，2）对于第 1 行和第 1 列具有相同长度的任何位置来说也是一个成功的移动。

一个位置可以有多个获胜动作吗？
- 是的，一个职位可以有多个获胜步骤。考虑以下位置：
  
  ###
  ##
  #
  
  这个题板位置有 3 种不同的获胜动作可以进行。你能确定它们是什么吗？

在Chomp获胜的一般策略是为对手创造失败的位置，这样他们就没有机会了。我们也希望避免创造获胜的位置，对手可以把我们变成失败的位置。

获胜的关键是知道尽可能多的失败位置，并在对手之前发现如何创建一个。让我们考虑以下可能的董事会，这是一个已知的亏损头寸：

#######
###
###
#
#
图 1

哪些位置可以一举变成这个亏损位置？

上述亏损位置可能来自下面标有 + 的任何走势：

#######+
###
###
#
#

#######
###+
###
#
#

#######
###
###
#+
#

#######
###
###
#
#
+

图 2

这些动作都位于切出的角落。任何这样的 + 移动也会剪切出可能出现在下图中的图块？：

#######+?
###
###
#
#

#######
###+???
###????
#
#

#######
###
###
#+?
#??

#######
###
###
#
#
+
?

图 3

+ 图块是必需的，而？图块是可选的。在左边的获胜位置，顶行可以用更多的“？”任意向右延伸，而在右边的获胜位置，第一列可以任意延伸到底部，有更多的“？”。所有这些位置也是获胜位置。如果我们要在这样的位置上采取行动，我们将采用 + 图块，因此所有？连接的图块也将被删除，导致我们开始时的损失位置。

赢的位置多还是输的位置多？
- 对于每一个输的局面，都有无限多的局面可以通过一步棋变成这个输的局面。因此，所有这些无限多的局面都是获胜的局面。
- 因此，赢的位置比输的位置多得多。因此，尽可能多地记住输的位置是最有效的，所有其他位置都是赢的位置。

列出您知道的亏损位置，并为每个位置写下所有相应的获胜位置以及如何检测它们

以下示例说明了我们的意思：

如前所示，当位置只有 2 行，顶行比第二行多一个图块时，这是亏损位置，如下所示：

#####
####
取这个已知的亏损位置，我们可以确定相应的胜算位置为：

#####+?
####

#####
####+

#####
####
+???
????

在左边的位置，可以有任意数量的？在顶行的右侧，在正确的位置，可以有任意数量的？下面。我们可以用文字总结如何检测这些获胜位置（您应该记住您的游戏）：

- 获胜位置，可简化为
  #####
  ####
- - 如果位置只有两行，并且第一行不比第二行长一个图块，或者
- - 如果位置有两行以上，并且第一行正好比第二行长一个图块。
但还有更多需要考虑的问题。我们不仅想在这样的获胜位置上正确比赛，我们还希望避免做出创造这种获胜位置的举动。这意味着我们不应该在只剩下两行的地方移动，或者第二行比第一行少一个图块。

总而言之，我们希望创建亏损位置，但我们也希望避免创建距离亏损位置一步之遥的头寸。

另一件需要注意的事情：由于前面提到的镜像对称性，上述所有注释都可以通过简单地将“行”一词替换为“列”一词来重复。

留给您更多的亏损位置及其相应的获胜位置，这些位置是一步之遥。

如果你不得不在失败的位置上比赛怎么办？
- 如果你意识到你必须在失败的位置上采取行动，那么理论上你没有机会。您所能做的就是希望您的对手不知道您可以在下一步中创建的位置的所有获胜动作。您只能从角落中删除单个图块。这为您的对手提供了一个最大大小的结果位置，并且使您的对手更难知道相应的获胜动作。

如果您不知道任何亏损位置怎么办？
- 人们必须执行所谓的完整树搜索。第一个玩家从猜测一个动作开始，然后第二个玩家猜测一个动作，依此类推，直到一个玩家（比如玩家 A）获胜。然后允许玩家 B 更改他们所做的最后一步，接下来轮到玩家 A 了。如果在下一个位置上，下一个玩家（例如B）因为所有移动都会导致失败而用完了移动，那么这是一个失败的位置，玩家B可以更改到达此失败位置之前所做的最后一步。
- 这种“树型搜索”一直持续到明确起始位置是亏损位置还是玩家 1 的哪个移动将其变成失败位置。
- 如果尝试在具有许多图块的初始板上执行此操作，这可能是一个非常漫长的过程。然而，我们知道的亏损位置越多，在达到这样的位置之前，移动序列就越短，因此整个搜索要快得多。如果我们知道所有都包含亏损位置，那么要么起始位置将被识别为亏损位置，要么只需要一次移动即可将其减少为亏损位置。

跟电脑对战时，如何学习亏损的位置？
- 在难度级别 "非常难 "和不大于8x15的位置中，计算机下得非常完美，所以计算机下出的每一个位置都是一个失败的位置! 人们应该从很小的棋盘开始，在 "非常难 "级别中与计算机对弈，学习计算机产生的所有局面。对于每一个这样的局面，想一想你的每一步棋会如何被计算机回应，使之再次变成一个更小的输棋局面。对于每个失败的局面，镜像的局面（行<-->列）也是一个失败的局面。
- 什么是最佳的第一步？
  - 在比赛中，起始位置将是一个长方形的糖果。正如前面所证明的那样，长方形是一个获胜的位置，但是什么是改变它成为对手失败位置的第一步棋？我们先前了解到，正方形的最佳棋步是(2,2)牌，但如果长方形不是正方形呢？
  - 只需换到 "非常难 "的难度级别，让电脑走第一步。只要矩形不大于8x15，电脑就会以最佳状态下棋，并显示出完美的第一步棋。试试不同的矩形尺寸，并记住最佳的第一步移动，因为在比赛日，电脑移动将无法使用:)。
- 很快，你就会在简单和中等难度的水平上成为无敌手。

是否有无穷无尽的亏损位置？
- 我们已经遇到了这两个系列的输位。N是任何正整数。
- 这里有更多：

游戏中内置的计算机玩家针对不同的游戏级别使用不同的技术。

- 容易- 每回合随机移动。如果检测到一个简单的获胜位置，它将移动到那里。
- 中等- 仍然是随机移动，但对赢和输位置有更深入的了解。将避免让对手获得简单获胜动作的动作。
- 难- 对获胜位置有更深入的了解。主动搜索题板，寻找可以迫使对手自己做出失败的动作。
- 很难 - 将始终为适合 8x15 大小矩形的任何位置进行最佳移动。
难度级别越高，迫使计算机处于亏损状态的难度就越大。每个级别知道的赢家和输家位置比前一个级别多得多，难度越大，您需要知道的赢和输位置就越多，以尝试迫使计算机进入失败位置。

下面的评论无助于在 Chomp 中变得更强大，但它们会提供一些有趣的事实，并为我们提供另一个通过归纳练习证明的机会。

有多少个不同的位置，包括空板，适合一个带有 P 行和 Q 列的矩形？
- 如果我们包括空矩形，我们可以使用以下公式计算可能的位置总数： \[\frac{(P+Q)!}{P!Q!}\]你能为一个小的P和Q计算这个数字，并验证它是否正确吗？
- 递归公式的首次推导
  - 设 f（P，Q）是大小为 PxQ 的矩形中的位置数。一个重要的观察结果是，所有位置都具有楼梯的形状，其中每行最多具有与上一行一样多的图块，但不会更多。
  - 让我们首先从我们可以表示所有这些楼梯的方式开始。轻松创建楼梯的一种方法是从棋盘的左下角开始，然后向右或向上移动。人们可以继续做这些右上移动，直到它们到达题板的右上角。我们将这称为从（P，0）到（0，Q）的路径。
  - 位置数与从（P，0）到（0，Q）的路径数相同，只要只允许向上或向右移动即可。从（P，0）到（0，Q+1）的路径数 f（P，Q+1）是从（P，0）到（0，Q）的路径数 f（P，Q），然后是（0，Q+1） + 从（P，0）到（1，Q）的路径数 f（P-1，Q），然后是（1，Q+1）和（0，Q+1），依此类推。对应的公式如下：\[f(P,Q+1) = f(P,Q) + f(P-1,Q) + f(P-2,Q) + \ldots + f(1,Q) + f(0,Q)\]
  - 我们现在将采用这个公式并将 P 替换为 P + 1。如果我们将 P + 1 而不是 P 代入公式，我们会得到以下内容： \[f(P+1,Q+1) = f(P+1,Q) + f(P,Q) + f(P-1,Q) + \ldots + f(0,Q)\] \[f(P+1,Q+1) = f(P+1,Q) + f(P,Q+1)\]从这个新的推导中，我们可以确定公式 \(f(P,Q) = f(P,Q-1) + f(P-1,Q)\) 哪里 \(f(P,0) = 1\) 和 \(f(0,Q) = 1\).
- 递归公式的替代推导
  - 在组合问题中，通常有几种计算方法。以下推导将提供一种不同且更优雅的方法来派生公式。
  - 我们将使用与之前相同的表示形式，其中我们想要找到将我们从（P，0）带到（0，Q）的路径总数。我们可以将这些路径分为两组。
  - 从从（P，0）到（P，1）向右移动的第一个移动开始的路径。我们知道，在这个组中，我们将总共有从（P，1）到（0，Q）的f（P，Q-1）路径。我们知道这一点，因为将一个矩形向右移动后剩余的矩形大小为 P x （Q-1）。
  - 另一组是从第一步开始的路径，从（P，0）上升一步到（P-1，0）。在这个组中，我们知道有 f（P-1，Q）总路径，因为生成的矩形的大小为（P-1） x Q。
  - 因此，由于每个可能的路径都将属于这两个组之一，因此路径总数是这些组的总和。这给了我们相同的公式 \(f(P,Q) = f(P,Q-1) + f(P-1,Q)\).
- 显式公式的推导
  - 让我们旋转矩形，使点（P，0）位于顶部，而不是从右下角开始路径。现在，我们可以通过下图可视化路径：
  - 这种类型的关系图称为树。这种模式将继续重复，直到我们从（P，0）到（0，Q）。当这种情况发生时，树将包含可以全面采用的所有可能路径。
  - 在此树中，从顶部（P，1）到节点（I，J）的方法数是到达（I-1，J）的方法数，然后向下到（I，J），加上到达（I，J-1）的方法数，然后向左向下到（I，J）。换句话说，这是帕斯卡三角形中的数字。
  - 帕斯卡三角形中的每个数字都是上面两个数字的总和。左列中的数字计算板的行数，从 0 开始，空板。三角形下方的数字表示左起的位置，也从 0 开始。位置 K 的第 N 行中的数字等于 \({N \choose K} = \frac{N!}{(N-K)!K!}\).
  - 我们想找到数字f（p，q），这是从（P，0）到（0，Q）的方法的数量。要做到这一点，必须从顶部的P次向下，从Q次向下向下。使用我们之前定义的树结构，这与从（0，0）到（P，Q）在树中只向左和向右移动相同。
  - 但是，这会导致我们进行 P+Q 步骤，因此我们在树中的 P+Q 行中。由于我们知道我们已经将 Q 时间向右移动，因此帕斯卡三角形中这个位置的数字是 \({P+Q \choose Q} = \frac{(P+Q)!}{P!Q!}\).
- 通过归纳法证明显式公式
  - 我们将证明以下公式是等效的。 \[f(P,Q) = \begin{cases}1 & for & P=0 \\1 & for & Q=0 \\f(P,Q-1) + f(P-1,Q) & for & \text{P>0 and Q>0}\end{cases} = \Bigg\{{P+Q \choose Q} = \frac{(P+Q)!}{P!Q!}\]
  - 感应底座： 我们已经知道 f（0，0） = 1 根据公式定义。如果我们将 P=0 和 Q=0 代入公式，我们得到 \(\frac{(0+0)!}{0!0!} = \frac{0!}{1} = 1\). 这表明基本公式是等效的，从而完成了感应基础。
  - 归纳假设： 假设公式对于 P+Q = N 的所有 P，Q 值都是等价的。
  - 感应步骤： 使用归纳假设，我们证明了所有值 P，Q 的等价性，P+Q=N+1。对于 P+Q=N+1 的任何值 P，Q，我们有 3 种情况：
  - 案例1：
  - 案例2：
  - 案例3： \(P,Q > 0\) \[ \begin{align} f(P,Q) &= f(P,Q-1) + f(P-1,Q)\qquad\qquad (+)\\ &= \frac{(P+Q-1)!}{P!(Q-1)!} + \frac{(P-1+Q)!}{(P-1)!Q!}\\ &= \frac{(P+Q-1)!Q}{P!(Q-1)!Q} + \frac{(P-1+Q)!P}{(P-1)!PQ!}\\ &= \frac{(P+Q-1)!}{P!Q!} (Q+P)\\ &= \frac{(P+Q)!}{P!Q!} \end{align} \]
  - （+）：如果 P + Q = N + 1，则 P + Q-1 = N，即通过归纳假设。
    f(P,Q-1) = \(\frac{(P+(Q-1))!}{(P!(Q-1)!)}\), 同样，对于f（P-1，Q）
  - 这表明 f（P，Q）的两个公式是等价的。
  - 证明结束。∎

有多少个不同的位置有 P 行和 Q 列？
- 可以简单地对适合具有 P-1 行和 Q-1 列的矩形的所有位置使用相同的公式，即 f（P-1，Q-1）。

是有更多的赢位还是更多的亏损位置？
- 如果一个位置有 N 个图块，则玩家 1 有 N 个选项用于第一步。能够先移动会给玩家 1 带来优势，这应该意味着获胜位置多于失败位置。在较早的项目中，确定了具有 2、3、4 或 5 个图块的位置中有多少亏损位置。这里有一些数字证实了一个趋势，即一个位置的图块越多，它成为获胜位置的概率就越高。
- # 个图块 # 位置 # 亏损位置亏损位置百分比
  20 627 42 6.69
  30 5604 220 3.92
  40 37338 1022 2.73
  50 204226 4976 2.43
  60 966467 20106 2.08
  70 4087968 76688 1.87
  80 15796476 270142 1.71
  90 56634173 897964 1.58
- 2 个参数“# 位置”和“# 亏损位置”的哪个函数为上表的每一行给出大致相同的值？
  - 答案在以下发现项中给出。

# 个图块	# 位置	# 亏损位置	亏损位置百分比
20	627	42	6.69
30	5604	220	3.92
40	37338	1022	2.73
50	204226	4976	2.43
60	966467	20106	2.08
70	4087968	76688	1.87
80	15796476	270142	1.71
90	56634173	897964	1.58

驯鹿的假设

之前我们展示了每个位置要么是赢位，要么是输位。该证明为我们提供了一种直接的方法，可以逐步确定所有位置是输还是赢。特别的是，这种方法不需要任何搜索（尝试移动）。它让我们想起了“埃拉托色尼筛”，以确定所有大小的素数。

例如在互联网上阅读有关Sieve of Eratosthenes的信息
- 要找到大小不超过 N² 的所有素数，其中 N 是某个整数，请执行以下操作：
- - 答：从质数 p=2 开始。
  - B：划掉 p 的所有倍数，直到 N²。
  - C：找到尚未划掉的下一个最大数字>p。如果该数字> N，则算法停止。否则，请拨打此号码 p 并继续执行步骤 B。
- 所有未划掉的 N 2 以内的数字都是 N² <质数。人们可以在以下位置找到该算法的模拟 https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

这个类比启发我们思考素数和亏损位置之间的更多相似之处。它导致了一个类似于“素数定理”的失去位置假设。以下是详细信息。

表：在 chomp 和素数中失去位置之间的类比：

数字	Chomp
整数有无限多个。	有无限多的 Chomp 位置。
有质数和可分解数。	有亏损位置和获胜位置。
有无限多个素数。	有无限多的亏损位置。
可分解数是质数和数的乘积。	获胜位置是亏损位置和位置的总和（因为在移动中切出的东西具有楼梯的形状，因此是一个位置）。
一旦知道一个素数，人们就会立即知道无限多个可分解数（素数的所有倍数）。	一旦知道亏损位置，就会立即知道无限多个获胜位置（所有位置都是由填充角矩形产生的，包括沿顶行和左列的无限长的位置）。
大数比大素数更容易被小素数整除。	大位置更有可能被简化为小亏损位置，而不是大亏损位置。
要确定一个数字 N 是否是素数，知道所有素数 P 到 N 的平方根是非常有效的。然后，可以检查N是否可以通过除法（即通过试验除法N / P）简化为P。	要确定 P 是否为亏损位置，有必要知道 P 中包含的所有亏损位置 L。然后可以有效地检查P是否可以在一次移动中减少到L。
“Sieve of Eratosthenes”是确定所有素数（直到某个数N）的有效方法，也是检查给定数是否为素数的有效方法。此算法如上所述。	与“埃拉托色尼筛”类似，从{1}的失败位置开始，并在一次移动中划掉所有减少到失败位置的获胜位置。然后，使用另外一个图块检查所有位置。所有未划掉的位置都是亏损位置。
筛子算法的剩余低效率包括重复划掉可分解的数字。	sieve algorithm的剩余低效率在于重复划掉获胜位置。
素数的密度随着它们的大小而减小;即比率（#素数到某个整数N）/ N随着N的增加而减小。	亏损位置的密度随着其规模而减小;即比率（#最多有N个图块的亏损位置）/（#个有N个图块的所有位置）随着N个图块的增加而降低。（挑战：这个比率对N的依赖性公式是什么，与素数密度的公式相比如何？
素数定理：（# 素数 ≤ N） / （N / log（N）） → 1 作为 N →无穷大。	类似的假设：（# 有 N 个图块的亏损位置）/（（# 个有 N 个图块的位置）/log（# 个有 N 个图块的位置）） → 0.283...作为 N →无穷大。

表：Chomp 亏损头寸和质数之间的差异：

数字	Chomp
所有整数的集合是一个完全有序的集合;即在任何两个数字之间，人们知道哪个更大。	所有 Chomp 位置的集合是偏序集合。位置可以完全包含在其他位置中，但不需要。
将数字减少到其主要因素之一的操作是除法。	将位置减少到亏损位置的操作是减去图块。
数字可以可视化为一维数字线上的线段。	位置是通过按大小排序的数字列表定义的，因此是一个 2D 对象。

开放性问题：

假设（#失去N个图块的位置）/（#个有N个图块的位置）/log（#个有N个图块的位置））→0.283...因为N→无穷大吗？

你能证明吗？（我们还不能：-））

上面玩的Chomp游戏是2D Chomp的一个版本。这意味着题板只有二维的，具有宽度和高度。

你能想象一个版本的3D Chomp吗？
- 想象为游戏添加新维度的最简单方法是向题板添加第三个维度。新板不仅有宽度和高度，还有长度、宽度和高度。如果一个人有小立方体可以玩，比如骰子，他们可以玩这个3D游戏，如下图所示。
- 移动时，将删除所选立方体，以及所选立方体左侧、上方和顶部的每个立方体。示例移动在图像中以黄色突出显示，这也将删除图像中的所有绿色图块。拿走最后一个图块的人（由图像中的红色图块显示）是输掉游戏的玩家。
- 为了使使用真正的立方体更容易玩游戏，可以将立方体推到角落，例如鞋盒的角落，这样红色图块就位于盒子的最角落，并且只有在所有其他立方体也被移除后才能访问。使用盒子不是必需的，但它会稳定立方体，更容易移除立方体而不会撞倒整个结构。

在更多的维度上玩Chomp怎么样？
- 早些时候，我们确定为Chomp游戏添加新维度很容易。如果有人想在比3D更高的维度上玩Chomp，他们将继续为Chomp板添加新的维度。但是，在3D之后，无法再使用块来模拟Chomp板。然而，有一种方法可以使用铅笔和纸来模拟 chomp 游戏，这种方法允许我们在任意数量的维度上玩游戏，而不仅仅是 2D 或 3D。
- 我们将从在纸上玩 2D Chomp 游戏开始。模拟游戏的一种方法是首先选择一个只有 2 个不同质因数的数字。例如，72 = 2 3 x³ ²。然后，我们以矩形的形式写下该数字的所有因子，如下所示。
- 72 36 18 9
  24 12 6 3
  8 4 2 1
- 任何右邻数都小 2 倍，下面的任何相邻数都小 3 倍。要在这个板上采取行动，人们会选择一个数字。然后，您将删除该数字及其任何因素。谁拿了72号，谁就输掉了比赛。
- 要获得更大的初始矩形，可以使用公式 2^P x 3^Q 找到更大的数字。通过将P和Q替换为更大的数字，人们将获得越来越大的2D Chomp板。
- 如何将这种模拟推广到更高维度？
  - 要将 Chomp 的铅笔和纸版本从 2D 扩展到 3D，只需扩展用于查找起始数字的公式即可。与其选择一个只有 2 个不同素因数的数字，不如选择一个有 3 个不同素因数的数字。我们可以使用一个新公式来找到这个数字，如下所示：2^P x 3^Q x 5^R。然后，使用与以前相同的方法，可以在 3 个维度上模拟游戏。转到更大的维度只需要在公式中添加新的素数，具体取决于所需的维度数。