Winning Strategies and Complexity of Nim-Type Computer Game on Plane

Boris S. Verkhovsky
DOI: 10.4236/ijcns.2010.310106                

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.

Keywords

Nim-type Game, Two-person Strategy Game, Winning Strategies, Newton Algorithm, Fibonacci Numbers

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	C. L. Bouton, “Nim, a Game with a Complete Mathematical Theory,” Annals of Mathematics, Princeton 3, 35-39, 1901-1902.
[2]	M. Gardner, “Mathematical Games: Concerning the Game of Nim and its Mathematical Analysis,” Scientific American, 1958, pp. 104-111.
[3]	M. Gardner, “Nim and Hackenbush,” Chapter 14 in Wheels, Life, and Other Mathematical Amusements, W. H. Freeman, 1983.
[4]	E. Berry and S. Chung, “The Game of Nim,” Odyssey Project, Brandeis University, 1996.
[5]	S. Pheiffer, “Creating Nim Games,” Addison Wesley, 1997.
[6]	R. D. D. Arruda, “Nim-Type Computer Game of Strategy and Chance,” Master Project, CIS Department, NJIT, Summer, 1999.
[7]	R. Statica, “Dynamic Randomization and Audio-Visual Development of Computer Games of Chance and Strategy,” Master Thesis, CIS Department, NJIT, Fall, 1999.
[8]	J. von Neumann and O. Morgenstern, “Theory of Games and Economic Behavior,” 3rd edition, 1953.
[9]	R. D. Luce and H. Raiffa, “Games and Decisions- Introduction and Critical Survey,” 2nd edition, Dover Publications, 1989.
[10]	G. M. Adelson-Velsky, V. Arlazarov and M. V. Donskoy, “Algorithms for Games,” 1987.
[11]	H. Wozniakowski, “Private communication,” Columbia University, USA, March 2002.
[12]	D. Kahaner, C. Moler and S. Nash, “Numerical Methods and Software,” Prentice Hall, 1989.
[13]	C. Berge, “The Theory of Graphs and its Applications,” Bulletin of Mathematical Biolody, Vol. 24, No. 4, 1962, pp. 441-443.
[14]	W. A. Wythoff, “A Modification of the Game of Nim,” Nieuw Archiefvoor Wiskunde, 199-202, 1907-1908.
[15]	B. Verkhovsky, “Winning Strategies and Complexity of Whytoff's Nim Computer Game,” Advances in Computer Cybernetics, Vol. 11, 2002, pp. 37-41.