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

.
DOI: 10.4236/ijcns.2010.310106   PDF   HTML     5,151 Downloads   8,964 Views  

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.

Share and Cite:

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

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.

  
comments powered by Disqus

Copyright © 2020 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.