主题
Search

尼姆值


每个无偏博弈的每个位置都有一个尼姆值,使其等同于一个尼姆堆。要找到尼姆值(也称为 Sprague-Grundy 数),取可能移动的尼姆值的mex。尼姆值也可以通过以二进制写出每个堆中计数器的数量,添加相应的二进制数字(模 2),并将结果的二进制字符串解释为十进制数来找到。

如果在游戏的任何时候,给定玩家的尼姆值为 0,则该位置是安全的(即,如果他正确地玩,他将总是赢);否则,它是不安全的(即,如果对方玩家正确地玩,他将总是输)。在尼姆游戏的两个堆中,唯一的安全位置是 (x,x)。对于三个堆(假设尼姆堆的最大尺寸为 7),安全位置是 (1, 2, 3)、(1, 4, 5)、(1, 6, 7)、(2, 4, 6)、(2, 5, 7)、(3, 4, 7) 和 (3, 5, 6)。对于四个最大尺寸为 7 的尼姆堆,安全位置是 (x,x,x,x), (x,x,y,y), 和 (1, 2, 4, 7), (1, 2, 5, 6), (1, 3, 4, 6), (1, 3, 5, 7), (2, 3, 4, 5), (2, 3, 6, 7) 和 (4, 5, 6, 7)。位置 (1, 3, 5, 7) 对应于游戏 马里恩巴德的起始状态,因此是一个不公平游戏


另请参阅

格朗迪博弈, 无偏博弈, 马里恩巴德, Mex, 尼姆, 安全, 不安全

使用 Wolfram|Alpha 探索

参考文献

Ball, W. W. R. 和 Coxeter, H. S. M. Mathematical Recreations and Essays, 13th ed. New York: Dover, pp. 36-38, 1987.Grundy, P. M. "Mathematics and Games." Eureka 2, 6-8, 1939.Sprague, R. "Über mathematische Kampfspiele." Tôhoku J. Math. 41, 438-444, 1936.

在 Wolfram|Alpha 上引用

尼姆值

请这样引用

Weisstein, Eric W. “尼姆值。” 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/Nim-Value.html

主题分类