300000
English | Français | فارسی | 中文 | Українська | Azerbaijani | ខ្មែរ | Tiếng Việt | Bahasa Melayu | Deutsch | O'zbek | РусскийiChomp©
游戏次数: 775601
胜局数: 486693
胜局数: 486693
如何玩i糖果游戏
- 每位玩家轮流从棋盘上取糖果。
- 将被移走的糖果取决于所选糖果处在的象限
- 第四象限从所选糖果的上方和左侧移除所有糖果,第一象限从上方和右侧移除,第三象限移除下方和左侧,第二象限移除所选糖果的下方和右侧。
如何获胜:
- 移走最后糖果的玩家赢得游戏。
轮到玩家1
题板宽度:
题板高度:
Access to 'Some food for thought' (SFFT) for the iChomp game can be purchased in the online shop
您将在本教程中学习的算法能够以最佳方式玩一大类游戏,因此花一些时间学习它是值得的。关键将是著名的 Sprague-Grundy 理论。如果您想了解在不学习 Sprague-Grundy 理论的情况下玩 iChomp 的提示,请向下滚动到相应的部分。在详细介绍之前,我们需要澄清一些术语。
-
组合游戏:两人游戏,信息完美,输赢结果,没有机会移动。
公正游戏:组合游戏,其中允许的移动仅取决于位置,而不取决于两个玩家中的哪一个当前正在移动。此外,回报是对称的。换句话说,玩家 1 和玩家 2 之间的唯一区别是玩家 1 先走。示例:Chomp。
党派游戏:不公正的游戏。示例:国际象棋。
正常游戏:走最后一步的玩家获胜,即无法移动的玩家,即没有什么可带走的玩家输了。
Misère Play:最后一步的玩家输了。
Chomp:在我们的游戏网站上推出的游戏,它使用一个象限和 Misère Play。
- 我们的 Nim 游戏使用 misère 游戏,因为拿下最后一场比赛的玩家输掉了比赛。
- 我们游戏页面上玩的 Chomp 游戏使用 misère 游戏,因为拿走最后一颗糖果的玩家输了。
- 使用正常游戏意味着谁拿走了最后一张牌,谁就赢了。因此,先移动的玩家可以通过拿走左上角的图块立即获胜。
- 在 iChomp 中,拿走最后一张牌的玩家获胜,因此本游戏使用普通游戏。
-
可以从左上角的(有毒)糖果从一开始就不见的位置开始。从这样的棋盘上拿走最后一颗糖果意味着一个人将在正常游戏中获胜。在Misère Play中,有了这个牌,那么另一个玩家将不得不接受它并输掉,这是相同的结果。
因此,拥有左上角图块并使用 Misère Play 或从游戏开始时就没有此图块并使用 Normal Play 都是完全相同的游戏。
- iChomp 游戏被设计为四个的结合 Chomp 同时进行的游戏,均在正常游戏规则下进行。这使得游戏在两个方面更加漂亮,下面将对此进行解释。此外,如果应用 Sprague-Grundy 理论,iChomp 并不比 Chomp 更难玩,该理论也将在下面描述。
-
它适用于的游戏类别是 公正的组合博弈. 这个理论为我们做了两件事:
- 它为我们提供了一种算法,该算法为每个游戏(即每个位置)确定一个数字(我们称之为 SG 值),使得该数字为0,当且仅当它是失败的位置时(在组合博弈论文献中称为“P 位置”,“P”表示“p”玩家打出了获胜的一步)。这意味着如果此 SG 值为 1、2、3、...那么这是一个获胜的位置(在文献中称为“N”位)。在这种情况下,如果玩得最好,谁移动 'n'ext 都可以强制获胜。
- SG理论的第二个目的是描述如何赢得由多个位置同时进行的比赛。在这种组合游戏中,通过在组合的任何一个位置上移动一步来完成的。
需要知道的是每个组合头寸的 SG 值。要获得它们,需要知道在这些组合位置中的任何一个中每次移动后的 SG 值。这些也是发挥最佳状态所必需的。
例如:在 Nim 游戏中,一个人有一两堆或多堆火柴。如果我们知道单独玩每个牌堆的 SG 值,那么 SG 理论告诉我们如何通过从这些牌堆中的任何一个中取出适当数量的匹配来最佳地玩所有这些牌。
-
iChomp 是 Caribou Contests 推出的 Chomp 的新版本,在此网页上播放。iChomp 中的“i”代表“各向同性”,即所有方向都得到平等对待。
在普通的 Chomp 中,移除一个图块也会移除其东面和南面的所有图块。因此,东方和南方的方向起着特殊的作用。
在 iChomp 中,其他方向的所有图块也可以被移除,具体取决于移除的图块最靠近中心的位置。例如,如果此图块位于中心的西北方向,则北或西的所有图块也会被移除。
删除人为的规则,例如,东和南是特殊的规则通常被认为可以使游戏在数学上更漂亮。
与 Chomp 相比,iChomp 还有另一种美化。
在Chomp中,与其他图块相比,左上角的图块起着特殊的作用。如果这是棋盘上唯一的图块,游戏就结束了。如果另一个图块被移除,游戏将继续。人们可以在没有该角图块的情况下开始 Chomp,因此所有图块都被视为相同,但这本身就是一个人为的规则,说明为什么在没有该图块的情况下开始游戏,而不是没有其他图块。
在 iChomp 中,所有图块都出现在开始时,并且所有图块都受到相同的处理。任何图块都可以在不自动结束游戏的情况下被移除。
出现了一些问题:
-
答案是否定的。例如,只有一堆火柴的 Nim 游戏是微不足道的。在“正常游戏”下,一个人可以一举清除整堆并获胜。在尼姆下 《悲惨剧》, 除了一场比赛之外,一个人可以删除所有比赛并获胜。尽管如此,像我们的 Nim 游戏页面上那样,将这样的 1 堆 Nim 游戏与多堆 Nim 游戏相结合并非易事。
同样在这里:使用角牌和“正常游戏”的单一 chomp 游戏是微不足道的,因为一个人可以一步移除所有牌并获胜。但 4 款此类游戏的组合并非易事。
- IChomp 在数学上比 Chomp 更漂亮,因为它不会人为地挑出东南方向,也不会给一块图块一个特殊的角色。代价似乎是 iChomp 比 Chomp 更难玩,但 SG 理论有所帮助。知道 Chomp 位置的 SG 值就足够了,最多可以计算出 4 倍大小的 iChomp 位置的 SG 值,从而知道如何以最佳方式玩 iChomp 直到 4 倍大的大小。
-
答案是否定的。例如,只有一堆火柴的 Nim 游戏是微不足道的。在“正常游戏”下,一个人可以一举清除整堆并获胜。在尼姆下 《悲惨剧》, 除了一场比赛之外,一个人可以删除所有比赛并获胜。尽管如此,像我们的 Nim 游戏页面上那样,将这样的 1 堆 Nim 游戏与多堆 Nim 游戏相结合并非易事。
在SG理论中,需要一种称为XOR的数学运算。如果您不熟悉它,以下部分将很有用。
-
Exclusive Or,简称 XOR,是对二进制数据执行的逻辑运算。使用二进制数据,我们可以有两个值之一,true (=1) 或 false (=0)。对两个二进制值的 XOR 运算通过下表定义。
a b a XOR b 1 1 0 1 0 1 0 1 1 0 0 0
虽然对 1 (true) 或 0 (false) 的值使用此操作很容易,但对于我们的计算,我们需要能够对两个数字执行 XOR。这也可以完成,但是在执行异或之前需要一个新步骤。
首先要发生的是需要将数字转换为二进制,即将其从以 10 为基数转换为以 2 为基数。
-
以下算法可用于将以 10 为基数的数字 n 转换为以 2 为基数的格式。(请注意,20 = 1):
- 求 2 的最高指数 p,使 2p ≤ n。
- 记录一个 1 并从 n 中减去 2p 。
- 如果 p = 0,则停止,否则从 p 中减去 1 并继续。
- 如果 2 p > n,则记录 0,否则从 n 中减去 2p,然后记录 1。
- 返回步骤 3。
您按照此算法记录的 1 和 0 序列将是数字 n 的二进制表示。例:
让我们将数字 13 转换为以 2 为基数的格式。我们首先找到 2 小于或等于 13 的最高幂,即 23 或 8。然后我们记录一个 1 并从 13 中减去 8,得到 5。接下来我们检查 2(3−1) = 22 = 4。从 4 ≤ 5 开始,我们记录一个 1,然后从 5 中减去 4,得到 1。下一个 2 的下限幂是 21 = 2。2 > 1,所以我们记录一个 0。2 的下一个幂是 2 0 = 1,它等于我们的 n of 1,所以我们记录一个 1 并从 1 中减去 1,得到0 。由于 p = 0,我们停止算法。因此 13(以 10 为基数)= 1101(以 2 为基数)。
将两个数字转换为二进制表示后,我们现在可以对两个二进制数的相应数字执行异或运算。结果是一个二进制数,如果将来使用该 XOR 值更方便,则可以将其转换回以 10 为基数。例:
让我们计算数字 6 和 13 的异或。这两个数字的二进制表示是 6 = 110 和 13 = 1101。首先,我们在较小数字的左侧添加 0,以便两者具有相同的位数,因此 6 = 0110。然后,我们可以通过将它们排列起来并对每个单独的数字执行操作来执行 XOR:
0110 XOR 1101 ------ 1011
因此,6 异或 13 = 1011(基数 2)= 1×23+0×22+1×2 1+1×20 = 8+2+1 = 11(基数10)。
让我们通过几个问题来检查我们对XOR的理解。
- 对于任何数字 m,我们有 m 异或 m = 0,因为 0 异或 0 = 0 以及 1 异或 1 = 0。
- 是的,因为 1 XOR 0 = 0 XOR 1 (=1)。
- 0 XOR m = m,因为 0 XOR 0 = 0 和 0 XOR 1 = 1。
- 如果 m 中的数字与 0 进行异或运算,则该数字保持不变(因为 0 异或 0 = 0 和 1 异或 0 = 1)。如果 m 中的数字与 1 进行异或运算,则该数字被翻转(因为 0 异或 1 = 1 和 1 异或 1 = 0)。因此,异或 n 翻转 n 中对应数字为 1 的所有数字。
-
以下算法可用于将以 10 为基数的数字 n 转换为以 2 为基数的格式。(请注意,20 = 1):
-
以下算法计算任何公正组合博弈中任何位置 P 的 SG 值。我们使用 Chomp 游戏来解释它。
- 每个亏损位置的博弈位置都会获得 SG 值 0。在 Chomp 中,单个图块(在西北角)是唯一没有后续移动的位置,因此是 SG 值为 0 的亏损位置。
- 我们需要从位置 P 一次移动到的所有位置的 SG 值。因此,如果位置 P 有 n 个图块,则有 n-1 个可能的移动:除了西北角的图块外,所有其他图块都可以与该图块南/东的所有图块一起移除。
- 位置 P 的 SG 值是最小的非负数,不在此 n-1 个可到达的 SG 值列表中。
该算法是递归的,因为要计算位置 P 的 SG 值,我们需要一次性从 P 到达的所有位置的 SG 值。它仍然有效,因为所需的 SG 值涉及较少图块的较小位置,并且最小可能位置(西北角的一个图块)的 SG 值是已知的。
- 当您将鼠标移到图块上时,此图块和将要删除的其他磁贴将突出显示。该图块中的数字是“正常游戏”(不是“Misère Play”)下象限的 SG 值,如果单击此图块,将产生该图块。您可以检查象限旁边的文本“SG value Base Ten:”中显示的数字是否是象限中未显示的最小数字。您还可以检查,如果您单击一个图块,那么其中的数字现在是否显示为新位置的“SG value Base Ten:”。
如何加快SG值的测定:
因为同一位置可以在一次移动中从不同的位置到达,并且在计算较大位置的SG值时可能会重复出现,因此一次又一次地计算它将是浪费精力。因此,一旦计算出位置 P 的 SG 值,就应将其存储起来以备后用。
如果要计算所有位置的 SG 值,直到一定规模,那么以下方法很有用。我们首先为唯一一个带有一个图块的位置(在西北角)分配 SG 值为零。然后,我们使用上述算法计算具有 2 个图块的所有位置的 SG 值,然后计算 3 个图块的位置,依此类推。
-
iChomp 位置由 4 个 Chomp 位置组成,每个象限一个。
- 首先,我们使用 Chomp 'Misère Play' 规则确定 4 个 Chomp 位置中每个位置的 SG 值。空象限不是 Chomp 位置,因此我们给它的值 −1。
- 然后,我们为每个值添加 1。
- 对于 4 个结果数字中的每一个,我们计算二进制表示。
- 我们计算 4 个二进制值的 XOR 值,并获得该位置的 SG 值(二进制形式)。如果此值为零,则为亏损位置,否则为盈利位置。
-
我们加一个 1,以便从“Misère Play”下的 SG 值获得 Chomp 位置在 “Normal Play” 下的 SG 值。以下定理对此进行了解释。
定理:
--------
要获得“正常游戏”下 Chomp 位置的 SG 值(即拿最后一张牌赢得游戏,这不是玩 Chomp 的常见方式),需要将 1 添加到“Misère Play”下相同位置的 SG 值(即拿最后一张牌输掉,这是玩 Chomp 的常见方式)。
-
证明(通过归纳(并且非常详细)):
基本情况(1 个格):
-------------------
在“正常游戏”下,没有牌的空棋盘是亏损位置,因此SG值为零。此外,在“正常游戏”下,对于一个有一张牌的棋盘(在左上角),唯一可能的动作是删除这个牌,产生一个SG值为0的位置。因此,在“正常玩法”下,移动无法达到的最小非负 SG 值为 1,因此这是在“正常玩法”下具有一张牌的头寸的 SG 值。
在“Misère Play”下,拥有一张牌是 SG 值为 0 的亏损位置。
因此,对于 1 个图块,“正常游戏”SG 值比“Misère 游戏”值大 1。
感应步进
---------------
归纳假说(n 个图块):
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
我们假设存在一个数字 n,因此对于所有具有 ≥1 和 ≤n 图块的位置,“正常游戏”下的 SG 值比“Misère 游戏”下的 SG 值大 1。入职申请(n+1 格):
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
我们将证明,所有具有 n+1 图块的位置也是如此。
感应步骤(n 个瓦片→ n+1 个瓦片):
~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
对于任何位置,“Misère Play”和“Normal Play”允许相同的移动,但“Normal Play”还允许将所有图块穿过左上角的图块。
如果该位置有 n+1 个图块,则移动会生成一个最多包含 n 个图块的位置,我们可以将归纳假设应用于该位置:
因此,“正常游戏”下可获得的 SG 值列表是从“Misère Play”下的可获得 SG 值列表中获得的,每增加 1,并通过获取所有图块将值 0 相加。
因此,在“正常游戏”下无法获得的最小非负数比在“Misère Play”下无法获得的最小非负数高 1。换言之,对于具有 n+1 个图块的原始位置,“正常游戏”下的 SG 值比“Misère 游戏”下的 SG 值高 1。∎ (这样就完成了证明。
-
证明(通过归纳(并且非常详细)):
-
目的是使得结果位置的 SG 值为零。无论一个人做出什么举动,它都必须在 4 个象限之一。这意味着已移动的位置的 SG 值和其他 3 个未更改象限的 SG 值(所有 XOR'ed)必须为零。当且仅当其他 3 个 SG 值 XOR 在移动后准确给出新象限的 SG 值时,才会出现这种情况(有关此陈述的证明,请参阅下文)。因此,程序如下:
- (简单)情况:4 个象限中的两个象限具有相同的 SG 值。然后这两个相等值的异或将给出零,因此两个象限都将被忽略。
- 如果其他两个象限的 SG 值也相等,则整个位置的 SG 值为零,该位置为亏损位置。然后从任何象限中移除一个图块以延迟失败,并有更多机会让对手不发挥最佳水平。
- 如果其他两个象限的 SG 值不相等,则选择具有较大 SG 值的象限。通过单击一个刻有数字的图块来移动,该数字等于另一个象限的 SG 值。结果是 2 对象限,成对相等的 SG 值和总 XOR 值为零 - 亏损位置。
- (一般)箱:
- 计算 4 个 iChomp-SG 值,比如 4 个象限的 w、x、y、z(每个象限的 Chomp-SG 值加 1)并将它们转换为基数 2。
- 然后找到最左边的位置,使得这 4 个数字中的奇数在这个位置有一个 1。例如,如果 4 个数字是
w=11011
那么最左边的 1 位置是第 5 个位置(我们从右边开始计算位置)。w 和 y 那里有 1,即两个数字(w 和 y)那里有 1。二是偶数,因此我们需要忽略这个位置。下一个位置是第 4 个位置,再次从右边开始计算。在这里,偶数个数字也有一个 1(w 和 x)。我们也需要忽略这一立场。第 3 位有 3 个数字,其中有一个 1 (x, y, z)。3 是奇数,所以我们选择这 3 个数字中的任何一个,例如,y=10100。
x= 1101
y=10100
z= 100- 如果所有位置都有偶数个 1,则所有 4 个数字的 XOR 值为零,这是一个亏损位置。例如
w'=11011
每个位置都有偶数个 1。这 4 个数字的 XOR 为零,这是一个亏损位置。在这种情况下,人们只需从任何象限中移除一个图块,以延迟失败,并有更多机会让对手不发挥最佳水平。
x'= 1011
y'=10110
z'= 110 - 如果至少一个位置有奇数个 1,那么我们找到一个数字,如上面的 y(不是 y')。
- 我们对其他 3 个数字进行异运算,在本例中为 w XOR x XOR z = 11011 XOR 1101 XOR 100 = 10011。这个值总是小于我们选择的数字,这里 y = 10100(参见下面的证明)。
- 在具有选取值的象限中,这里是 y,我们进行移动,导致 SG 值等于其他 3 个值的异或的位置,在我们的示例中为 10011。
- 要知道要单击哪个图块,我们要么将 10011 转换为十进制 (= 1×1 + 1×2 + 0×4 + 0×8 + 1×16 = 19) 并单击数字为 19 的图块,或者我们以二进制形式计算 10100 − 10011 = 1 并将其转换为十进制 (= 1),并知道要单击的图块的值应小于 y (=20), 即单击刻有数字 19 的图块。
-
请提醒自己注意XOR的属性,如前面所示,以回答以下问题。
-
通过使用前面学习的 XOR 规则,我们得到
y XOR u
= y XOR w XOR x XOR y XOR z
= y XOR y XOR w XOR x XOR z
= 0 XOR w XOR x XOR z
= w XOR x XOR z.
-
新的 XOR 将是
(y XOR u) XOR w XOR x XOR z
= (w XOR x XOR z) XOR (w XOR x XOR z)
= 0
因为 m XOR m = 0 对于任何数字 m。
这意味着整个委员会的新SG值将为零,因此这将是预期的亏损位置。
- 根据定义:当且仅当存在生成 SG 值为 0,1,..,(y-1) 的位置的移动时,位置的 SG 值为 y。因此,如果 y > (y XOR u),则必须存在生成 SG 值 (y XOR u) 的移动 < y.
还有待回答的是:
-
温馨提示:
早些时候,当我们了解 XOR 的性质时,我们看到:XOR u 翻转 u 中对应数字为 1 的所有数字。
如果≠ 0,则 U 包含 2 的最高幂,比如 2p。这个 2 的幂必须出现在 4 个 SG 值中的奇数中,所以至少在一个 SG 值中,比如 y。
这意味着,在计算 y XOR u 时,y 中的这个 1 被 u 中的相应 1 翻转为 0。可能还有其他二进制数字翻转在 y 中,位于此 1 的右侧。如果 1 右边的 y 中的数字是零,而 1 右边的 u 中的数字是 1,则会出现 y − (y XOR u) 的最大可能值。在这种情况下,u = 111..111 将 y = *100..00(其中 * 代表任意数量的位数)更改为 y XOR u = *011..11。它们的区别在于:
y − (y XOR u)
= 2p − (2p−1 + 2p−2+ ... +20)
= 2p − (2p−1 + 2p−2+ ... +20)× (2-1)/(2-1)
= 2p − (2p−1)/(2-1)
= 1.
这意味着 y 至少比 (y XOR u) 大 1。∎
-
通过使用前面学习的 XOR 规则,我们得到
-
首先,选择“难度:困难”,以确保最佳的电脑游戏。如果你仍然赢了,那么你就把每一步都发挥得最佳。
每个象限的 SG 值以 10 为基数和以 2 为基数显示。检查此数字是否是象限中未显示的最小值。
在下面,显示了所有 4 个称为 u 的 SG 值的 XOR。如果两个 1 位于同一位置,则只需将 4 个 SG 值中的任意一对两个 1 更改为 0 即可验证 U 的值。然后将剩余的 1 放入一个二进制数并将其转换为以 10 为基数。
要进行移动,请按上述方式进行操作:
- 找到 4 个 SG 值之一,比如 y,它有一个 1 与 u 中最左边的 1 位于同一位置。
- 以二进制形式计算 y XOR u,然后将其转换为以 10 为基数。
- 在 y 象限中,单击计算出的 y XOR u 的图块。
- 以这种方式玩你的动作,直到你赢了。
- 再玩一次,但这次从随机移动开始。除非你很幸运,不小心玩了一个获胜的棋,否则即使你试图以最佳方式玩,你也无法赢得这场比赛。
上述所有说明都假设一个人知道 4 个象限的 SG 值,这意味着在每次可能的移动后都知道每个象限的 SG 值。
-
为了计算位置的 SG 值,需要知道一次移动中可以从该位置到达的所有位置的 SG 值。这是一个递归过程。因此,我们需要从方块数量最少的位置开始,然后逐步向上。
-
只有 1 个图块(在左上角)是亏损位置,因此 SG 值为 0。
有 2 个图块(在顶行或左列),唯一可能的移动是取一个图块获得 SG 值为 0 的上述位置。因此,移动无法实现的最小非负 SG 值为 1,因此具有 2 个图块的头寸的 SG 值为 1。
顶行有 3 个图块,可以取 1 或 2 个图块并获得 SG 值 1 和 0,因此 SG 值为 2。
同样,顶行中 n 个图块的 SG 值为 n-1。
让我们考虑 3 个图块,2 个在顶行,2 个在左列。我们只能删除 1 个图块并达到 SG 值 1 但不能达到 0,因此无法获得的最小 SG 值为 0,因此是该位置的 SG 值。这是一个亏损的位置。
- 只能从顶行或左列中删除图块。因此,SG 值与具有两个象限相同,一个象限在顶行有 n 个图块,另一个在左列中有 m 个图块。因此,SG值为(m-1)异或(n-1)。这与玩两堆 NIM 和“正常游戏”规则相同,其中一场比赛只能从一堆中移除火柴。
-
这些职位的公式更复杂。据我们所知,它们以前从未发表过。您可以尝试验证少量图块的图块。
设 n 和 m 为顶行和第二行的图块数。
如果 n 是偶数,则
k = (n-2)/2
如果 m 是偶数,则
a = m/2
SG值 = 2*k+a+1
否则(m 为奇数)
a = (m-1)/2
如果≤ (k/2),则 SG 值 = 2*k-a
else SG-值 = 3*(k-a)
否则(n 为奇数)
k = (n-1)/2
如果 m 是偶数,则
a = m/2
如果≤ (k/2),则 SG 值 = 2*k-a
else SG-值 = 3*(k-a)
否则(m 为奇数)
a = (m-1)/2
SG值 = 2*k+a+1
- 选择最小板高度,以便象限只有两行图块。应用上述公式后,您应该获得比“SG Value Base Ten:”下显示的值低 1 的 SG 值,因为这些公式用于“Misère Play”,而 iChomp 使用“Normal Play”。
-
只有 1 个图块(在左上角)是亏损位置,因此 SG 值为 0。
-
我们从观察开始:Chomp 的规则在东方向和南方向之间没有区别。
- 由于东方向和南方向相互镜像,这意味着两者必须具有相同的 SG 值。
- 两个象限都可以忽略。为什么?两个象限在 misère play 下具有相同的 SG 值,在添加 1 后,在正常 play 下也具有相同的 SG 值。这两个相等值的异或为零。因此,两个象限对整个董事会位置的SG值没有贡献。
-
应该移动,创建两对象限,以便每对象限具有相等 SG 值的对称位置,例如 A 和 A,以及 B 和 B。然后,所有 4 个象限组合的 SG 值为 A XOR A XOR B XOR B = 0 XOR 0 = 0 或 (A XOR B) XOR (A XOR B) = 0,因此始终为 0。一个创造了一个亏损的头寸。
同样,一个人不应该做出留下两个对称象限和另外两个象限的动作,其中一个可以被对手一步换成另一个象限。这将允许对手创造一个失败的位置。
-
这里有一些问题,您可以在其中测试您对 Chomp、iChomp 和 SG 理论的理解。
- 是的。如果位置的SG值为零,则为亏损位置(因为不存在使其为零的走势,因此不存在盈利的走势,因此为亏损位置)。如果 SG 值大于零,则意味着有一个移动使结果位置的 SG 值为零,因此有一个获胜移动。
- 不。要玩 Chomp,我们需要找到一个产生失败位置的动作。如果不存在这样的动作,那么它就是一个失败的位置,任何动作都可以玩。但是,如果发现这样的举动,则可以停止搜索。不需要 SG 值。
- 它们只需要作为新游戏并行玩几个 Chomp 游戏,就像在 iChomp 中一样。
-
要玩 Chomp,我们需要找到一个产生失败位置的动作。如果不存在这样的动作,那么它就是一个失败的位置,任何动作都可以玩。但是,如果发现这样的举动,则可以停止搜索。
寻找位置的SG值的工作量通常更高。为了找到 SG 值,人们总是必须搜索所有移动,以便找到结果位置的所有 SG 值,并找到移动中无法达到的最小非负值。此值是位置的 SG 值。
例如,在我们的(驯鹿)计算中,我们能够确定所有输仓(从而赢仓),最多有 93 个图块。通过类似的计算工作,我们能够计算出多达 82 个图块的所有 Chomp 位置的 SG 值。
从这个意义上说,确定 SG 值在计算上比确定获胜的移动更昂贵。
-
在 Nim 中,一个桩的 SG 值只是该桩中的匹配数。(请通过应用上述注释来确认这一点,如何在 Nim 中将 SG 值计算到单个堆栈。在 Nim 中打几根桩的唯一复杂性是异或这些桩的不同 SG 值,以获得所有桩的 SG 值组合。
在 Chomp 中,获取位置(位于一个象限中)的 SG 值在计算上成本很高。在 iChomp 中,一旦知道 4 个象限的 SG 值,这些值也需要进行异或处理,但这比找到一个象限的 SG 值要容易得多。
要想以最佳状态玩 Chomp,不需要知道位置的 SG 值,知道获胜的一步就足够了,但如上图所示,差异并没有那么大。
所以答案是否定的,以最佳方式玩 iChomp 并不比 Chomp 难多少。
- 是的。位置的SG值是移动不能产生的最小值。
-
是的。您可以通过增加题板尺寸并单击“显示移动的 SG 值”按钮来查看示例。例如,位置
###
##
#
有 3 个获胜的动作,都创建了一个 SG 值为 0 的位置。我们甚至找到了一个有 7 个获胜动作的位置:
+ 10 6 15 2 20 21 14 22 11 0 23 7 26 13 7 11 9 14 0 19 5 17 11 14 18 0 24 23 8 3 19 2 0 20 11 4 0 5 1 8 0 0 4 23 25 24
关注或订阅更新: