Sprague–Grundy 定理 / nim 游戏 / Bowlingpins hackerrank
Sprague–Grundy theorem / Game of nim / Bowlingpins hackerrank
我一直在尝试在 HackerRank 中解决这个名为 Bowling Pins 的问题。基本上你必须编写一个程序来预测谁会赢谁会输。游戏规则为：
- 保龄球瓶是水平放置的，它们表示为一串大写字母 i --> “IIII”（4 个瓶瓶颈）
- 您可以击倒一个引脚“I”或两个相邻的引脚“II”
- “X”代表被击倒的别针
- 最后击倒的玩家获胜
给定字符串“XIIX”，这是一个胜利，因为我可以击倒中间的两个别针。
给定字符串“IXIX”，输了，因为下一位玩家将走最后一步
现在，我试图对组合博弈定理有一个基本的了解。我知道我必须计算 mex 和 grundy 以便在不实际玩游戏的情况下知道谁赢谁输。
现在我的问题是我是否有三个引脚“III”
mex {1,2} = 0 ，这意味着输了。但是如果我击倒中间的单个销钉会发生什么？
下一个玩家回合将看起来像这个“IXI”，he/she 可以击倒左边或右边的瓶，不管我得到最后一个瓶并获胜。对吗？
我对这些概念还很陌生，我不确定我是否为这个游戏正确地实现了 Sprague–Grundy 定理。有人可以给我解释一下吗？
这是我要解决的问题的 link --> https://www.hackerrank.com/challenges/bowling-pins/problem
我认为这篇文档对相关理论的解释非常好：https://web.mit.edu/sp.268/www/nim.pdf。就我个人而言，我花了一些时间才读完这份文件；起初我只是尝试阅读，但通过写下一些 lemmas/theorems 并自己练习一下，我从中得到了更多。我认为“从游戏到图表”和“Sprague-Grundy 函数”部分下的图表对这个问题特别有帮助。
我是这样开始思考的：一组大头针就是一个游戏位置。每个游戏位置要么是终端，要么有追随者，这是可以移动到的其他游戏位置。每个游戏位置都可以根据其追随者的 SG 值分配一个 Sprague-Grundy (SG)。现在尝试创建游戏位置图：
唯一的终端位置是没有引脚剩余，我们可以写成 X 或 XX 或者根据你的引脚数量写成 X从...开始。这个位置有 SG(X) = 0 因为它是终端。
游戏位置I可以击倒一根大头针，这样就X。所以 X 是 I 的追随者，并且 SG(I) = mex{SG(X)} = mex{0} = 1
游戏位置 II 可以有一个引脚被击倒，使其成为 XI == IX == I，或者两个, 使其 XX == X。所以它有这两个追随者，SG(II) = mex{SG(I), SG(X)} = mex{0, 1} = 2.
现在让我们看看 III，因为这是我们开始使用文档中的其他一些信息的地方。追随者是 XII（SG of 2）、XXI（SG of 1）和 IXI。对于最后一个，我们 可以 看到它只有一个追随者并得到这样的 SG，或者我们可以使用 Sprague-Grundy 定理。这表示“图上游戏总和的 SG 函数只是其组件的 SG 函数的 Nim 和”。对于 IXI，它有两个 I 的游戏，每个游戏的 SG 都是 1。当我们取 nim 和（xor 二进制表示）时，我们得到 0。所以总而言之，SG(III) = mex{2, 1, 0} = 3 .
并且您可以通过一次取走 1 或 2 II 并计算 nim 总和来继续从下到上获取其他 SG。
我一直在尝试在 HackerRank 中解决这个名为 Bowling Pins 的问题。基本上你必须编写一个程序来预测谁会赢谁会输。游戏规则为：
- 保龄球瓶是水平放置的，它们表示为一串大写字母 i --> “IIII”（4 个瓶瓶颈）
- 您可以击倒一个引脚“I”或两个相邻的引脚“II”
- “X”代表被击倒的别针
- 最后击倒的玩家获胜
给定字符串“XIIX”，这是一个胜利，因为我可以击倒中间的两个别针。
给定字符串“IXIX”，输了，因为下一位玩家将走最后一步
现在，我试图对组合博弈定理有一个基本的了解。我知道我必须计算 mex 和 grundy 以便在不实际玩游戏的情况下知道谁赢谁输。
现在我的问题是我是否有三个引脚“III” mex {1,2} = 0 ，这意味着输了。但是如果我击倒中间的单个销钉会发生什么？ 下一个玩家回合将看起来像这个“IXI”，he/she 可以击倒左边或右边的瓶，不管我得到最后一个瓶并获胜。对吗？
我对这些概念还很陌生，我不确定我是否为这个游戏正确地实现了 Sprague–Grundy 定理。有人可以给我解释一下吗？
这是我要解决的问题的 link --> https://www.hackerrank.com/challenges/bowling-pins/problem
我认为这篇文档对相关理论的解释非常好：https://web.mit.edu/sp.268/www/nim.pdf。就我个人而言，我花了一些时间才读完这份文件；起初我只是尝试阅读，但通过写下一些 lemmas/theorems 并自己练习一下，我从中得到了更多。我认为“从游戏到图表”和“Sprague-Grundy 函数”部分下的图表对这个问题特别有帮助。
我是这样开始思考的：一组大头针就是一个游戏位置。每个游戏位置要么是终端，要么有追随者，这是可以移动到的其他游戏位置。每个游戏位置都可以根据其追随者的 SG 值分配一个 Sprague-Grundy (SG)。现在尝试创建游戏位置图：
唯一的终端位置是没有引脚剩余，我们可以写成
X或XX或者根据你的引脚数量写成X从...开始。这个位置有SG(X) = 0因为它是终端。游戏位置
I可以击倒一根大头针，这样就X。所以X是I的追随者，并且SG(I) = mex{SG(X)} = mex{0} = 1游戏位置
II可以有一个引脚被击倒，使其成为XI==IX==I，或者两个, 使其XX==X。所以它有这两个追随者，SG(II) = mex{SG(I), SG(X)} = mex{0, 1} = 2.现在让我们看看
III，因为这是我们开始使用文档中的其他一些信息的地方。追随者是XII（SG of 2）、XXI（SG of 1）和IXI。对于最后一个，我们 可以 看到它只有一个追随者并得到这样的 SG，或者我们可以使用 Sprague-Grundy 定理。这表示“图上游戏总和的 SG 函数只是其组件的 SG 函数的 Nim 和”。对于IXI，它有两个I的游戏，每个游戏的 SG 都是 1。当我们取 nim 和（xor 二进制表示）时，我们得到 0。所以总而言之，SG(III) = mex{2, 1, 0} = 3.
并且您可以通过一次取走 1 或 2 II 并计算 nim 总和来继续从下到上获取其他 SG。