Research ArticleOpen AccessGoogle Scholar indexed
Winning Strategies and Complexity of Nim-Type Computer Game on Plane
- 1
International Journal of Communications, Network and System Sciences·Volume 03 (2010)·Pages 793–800·Published 27 October 2010·DOI10.4236/ijcns.2010.310106
Copy link · social · email
Abstract
A Nim-type computer game of strategy on plane is described in this paper. It is demonstrated that winning strategies of this two-person game are determined by a system of equations with two unknown integer sequences. Properties of winning points/states are discussed and an O(loglogn) algorithm for the winning states is provided. Two varieties of the Game are also introduced and their winning strategies are analyzed.
KeywordsNim-type GameTwo-person Strategy GameWinning StrategiesNewton AlgorithmFibonacci Numbers
- C. L. Bouton, “Nim, a Game with a Complete Mathematical Theory,” Annals of Mathematics, Princeton 3, 35-39, 1901-1902.
- M. Gardner, “Mathematical Games: Concerning the Game of Nim and its Mathematical Analysis,” Scientific American, 1958, pp. 104-111.
- M. Gardner, “Nim and Hackenbush,” Chapter 14 in Wheels, Life, and Other Mathematical Amusements, W. H. Freeman, 1983.
- E. Berry and S. Chung, “The Game of Nim,” Odyssey Project, Brandeis University, 1996.
- S. Pheiffer, “Creating Nim Games,” Addison Wesley, 1997.
- R. D. D. Arruda, “Nim-Type Computer Game of Strategy and Chance,” Master Project, CIS Department, NJIT, Summer, 1999.
- R. Statica, “Dynamic Randomization and Audio-Visual Development of Computer Games of Chance and Strategy,” Master Thesis, CIS Department, NJIT, Fall, 1999.
- J. von Neumann and O. Morgenstern, “Theory of Games and Economic Behavior,” 3rd edition, 1953.
- R. D. Luce and H. Raiffa, “Games and Decisions- Introduction and Critical Survey,” 2nd edition, Dover Publications, 1989.
- G. M. Adelson-Velsky, V. Arlazarov and M. V. Donskoy, “Algorithms for Games,” 1987.
- H. Wozniakowski, “Private communication,” Columbia University, USA, March 2002.
- D. Kahaner, C. Moler and S. Nash, “Numerical Methods and Software,” Prentice Hall, 1989.
- C. Berge, “The Theory of Graphs and its Applications,” Bulletin of Mathematical Biolody, Vol. 24, No. 4, 1962, pp. 441-443.
- W. A. Wythoff, “A Modification of the Game of Nim,” Nieuw Archiefvoor Wiskunde, 199-202, 1907-1908.
- B. Verkhovsky, “Winning Strategies and Complexity of Whytoff's Nim Computer Game,” Advances in Computer Cybernetics, Vol. 11, 2002, pp. 37-41.