论文标题
多维巧克力和NIM带有通行证
Multi-Dimensional Chocolate and Nim with a Pass
论文作者
论文摘要
巧克力棒游戏是CHOMP游戏的变体。一个三维巧克力棒包括一组1 x 1 x 1的立方盒子，位于位置的圆柱底部有一个苦的立方盒（0,0）。对于非阴性整数u，w使得u <x和w \ <z，位置（u，w）处的列的高度为min（f（f（u，w），y），y）+1，其中f是单调增加的函数。我们将此巧克力棒表示为CB（F，X，Y，Z）。每个玩家又在沿凹槽的水平或垂直的飞机上切断了杠铃，并吃掉了碎片。设法离开对手的球员是赢家。在这项研究中，函数f使得Cb（F，X，Y，Z）的Sprague-grundy值是xor y xor z的。我们已经发表了有关三维巧克力游戏的研究。在本文中，作者研究了一个多维巧克力游戏，其中维度超过三个，并将理论应用于NIM的通行问题。我们修改了游戏的标准规则以允许一次性通行证，也就是说，通过游戏中最多可以使用一次通行证，而不是从终端位置使用。一旦两个玩家都使用了通行证，就不再可用。众所周知，在古典NIM中，通行证的引入改变了游戏的基本结构，从而大大提高了其复杂性。多维巧克力游戏可以通过通行证显示NIM游戏的复杂性。因此，作者解决了组合游戏理论中的一个长期开放问题。作者介绍了本文，因为他们的发现似乎很重要。作者看来，巧克力游戏与NIM与通行证之间的关系很快将是一个必不可少的研究主题。
Chocolate-bar games are variants of the CHOMP game. A three-dimensional chocolate bar comprises a set of cubic boxes sized 1 X 1 X 1, with a bitter cubic box at the bottom of the column at position (0,0). For non-negative integers u,w such that u < x and w \< z, the height of the column at position (u,w) is min (F(u,w),y) +1, where F is a monotonically increasing function. We denote this chocolate bar as CB(F,x,y,z). Each player, in turn, cuts the bar on a plane that is horizontal or vertical along the grooves, and eats the broken piece. The player who manages to leave the opponent with the single bitter cubic box is the winner. In this study, functions F such that the Sprague--Grundy value of CB(F,x,y,z) is x xor y xor z are characterized. We have already published the research on three-dimensional chocolate games. In this paper, the authors study a multi-dimensional chocolate game, where the dimension is more than three, and apply the theory to the problem of pass move in Nim. We modify the standard rules of the game 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. A multi-dimensional chocolate game can show a perspective on the complexity of the game of Nim with a pass. Therefore, the authors address a longstanding open question in combinatorial game theory. The authors present this paper, since their discovery seems to be significant. It appears to the authors that the relation between chocolate games and Nim with a pass will be an essential research topic soon.
