K-L-Nim博弈
K-L-Nim Game
DOI: 10.12677/AAM.2017.63027, PDF, HTML, XML, 下载: 2,260  浏览: 6,885  国家自然科学基金支持
作者: 徐荣兴, 吕新忠, 田贵贤：浙江师范大学数理与信息工程学院，浙江 金华
关键词: Nim博弈；Sprague-Grundy定理；Bouton定理；P态；Nim Game； Sprague-Grundy Theorem； Bouton Theorem； P-position
摘要: Nim博弈是博弈论中最经典的模型之一，1902年C.L. Bouton给出其完全解。其变形版本的玩法日益受到人们的喜爱，这篇文章介绍了一个Nim博弈的变形玩法，K-L-Nim博弈。其中一个玩家每次不能拿走k个石子(但可拿走多于或者少于k个石子)，而另外一个玩家不能拿走l个石子(但可拿走多于或者少于l个石子)。这篇文章巧妙地借助了Sprague-Grundy定理研究了k=l 时的组合解。并用数学归纳法和Bouton定理给出了k≠l 时所有组合解。
Abstract: Perhaps the most famous combinatorial game is Nim, which was completely analyzed by C.L. Bouton in 1902. From then on, the variant of Nim game is getting more and more popular. This paper introduces a new variant of Nim game, K-L-Nim game, one player’s illegal move is to remove k stones from one pile, while the other player’s illegal move is to remove l stones from one pile. This paper gives a complete solution for the game by using Sprague-Grundy Theorem, Bouton Theorem and mathematical induction.
文章引用：徐荣兴, 吕新忠, 田贵贤. K-L-Nim博弈[J]. 应用数学进展, 2017, 6(3): 232-237. https://doi.org/10.12677/AAM.2017.63027

参考文献

[1] Bouton, C.L. (1902) Nim, a Game with a Complete Mathematical Theory. Annals of Mathematics, 3, 35-39.
https://doi.org/10.2307/1967631
[2] Albert, M.H. and Nowakowski, R.J. (2001) The Game of End-Nim. The Electronic Journal of Combinatorics, 8, Research Paper 1, 12p.
[3] Albert, M.H. and Nowakowski, R.J. (2004) Nim Restrictions, Integers. Electronic Journal of Combinatorial Number Theory, 4, #G 01.
[4] Fukuyama, M. (2003) A Nim Game Played on Graphs. Theoretical Computer Science, 304, 387-399.
https://doi.org/10.1016/S0304-3975(03)00292-5
[5] Li, S.-Y.R. (1978) N-Person Nim and N-person Moore's Games. International Journal of Game Theory, 7, 31-36.
https://doi.org/10.1007/BF01763118
[6] Lim, C.-W. (2005) Partial Nim, INTEGERS: Electronic Journal of Combinatorial Number Theory, 5, # G 02.
[7] Moore, E.H. (1910) A Generalization of a Game Called Nim. Annals of Mathematics, 11, 93-94.
https://doi.org/10.2307/1967321
[8] Schwartz, B.L. (1971) Some Extensions of Nim. Mathematics Magazine, 44, 252-257.
https://doi.org/10.2307/2688631
[9] Schwenk, A.J. (1970) Take-Away Games. Fibonacci Quarterly, 8, 225-234.
[10] Sprague, R.P. (1936) Uber Mathematische Kampfspiele. Tohoku Mathematical Journal, 41, 438-444.
[11] Wythoff, W.A. (1907) A Modification of the Game of Nim. Nieuw Archief voor Wiskunde, 7, 199-202
[12] Xu, R. and Zhu, X. (2016) Bounded Greedy Nim Game. Theoretical Computer Science, Submitted

为你推荐