论文标题
通过限制NIM
Restricted Nim with a Pass
论文作者
论文摘要
本文介绍了一项通过通过的限制性NIM的研究。在这项研究中考虑的NIM受限的限制中，两名参与者轮流从桩中取出石头。在每个回合中，当石头数量为m时，每个玩家都可以从一堆M石头上取下至少一块石头，最多是M/2石头的天花板。对游戏的标准规则进行了修改，以允许一次性通行证，也就是说，可以在游戏中最多使用一次通行证，而不是从终端位置使用。一旦两个玩家都使用了通行证，就不再可用。众所周知，在古典NIM中，通行证的引入改变了游戏的基本结构，从而大大提高了其复杂性。在这项研究中考虑的NIM限制中，发现通行移动的影响很小。在限制性的NIM数量和通过通过的限制性NIM数量之间存在简单的关系，其中堆的数量可以是任何自然数量。因此，作者在组合游戏理论中解决了一个长期存在的开放问题：将传球引入游戏的程度会影响其行为。我们开发的游戏似乎是NIM的第一个变体，当不允许通行证并在引入通行证移动后仍能完全解决时，它是完全可解决的。
This paper presents a study of restricted Nim with a pass. In the restricted Nim considered in this study, two players take turns and remove stones from the piles. In each turn, when the number of stones is m, each player is allowed to remove at least one stone and at most the ceiling of m/2 stones from a pile of m stones. The standard rules of the game are modified to allow a one-time pass, that is, a pass move that may be used at most once in the game and not from a terminal position. Once a pass has been used by either player, it is no longer available. It is well-known that in classical Nim, the introduction of the pass alters the underlying structure of the game, significantly increasing its complexity. In the restricted Nim considered in this study, the pass move was found to have a minimal impact. There is a simple relationship between the Grundy numbers of restricted Nim and the Grundy numbers of restricted Nim with a pass, where the number of piles can be any natural number. Therefore, the authors address a longstanding open question in combinatorial game theory: the extent to which the introduction of a pass into a game affects its behavior. The game that we developed appears to be the first variant of Nim that is fully solvable when a pass is not allowed and remains fully solvable following the introduction of a pass move.
