IJCNS  Vol.3 No.10 , October 2010
Winning Strategies and Complexity of Nim-Type Computer Game on Plane
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.
Cite this paper: nullB. Verkhovsky, "Winning Strategies and Complexity of Nim-Type Computer Game on Plane," International Journal of Communications, Network and System Sciences, Vol. 3 No. 10, 2010, pp. 793-800. doi: 10.4236/ijcns.2010.310106.

[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.