 Int. J. Communications, Network and System Sciences, 2010, 3, 793-800 doi: 10.4236/ijcns.2010.310106 Published Online October 2010 (http://www.SciRP.org/journal/ijcns) Copyright © 2010 SciRes. IJCNS Winning Strategies and Complexity of Nim-Type Computer Game on Plane* Boris S. Verkhovsky Computer Science Department, College of Computing Sciences New Jersey Institute of Techno logy, Newark, USA E-mail: verb@njit.edu Received June 10, 2010; revised July 17, 2010; accepted August 22, 2010 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 se-quences. 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 1. Introduction A Nim game is probably one of the most ancient of all known games. There are several varieties of Nim: cate-gorical games in which no draw is possible; futile games which permit a tie (draw); Grundy’s game is a special type of Nim. The game is played by the following rules: given a heap of size n, two players alternately select a sub-heap and divide it into two unequal parts. A player loses if he or she cannot make a legal move. The Misere form of Nim is a version in which the player taking the last piece is the loser, . In Fibonacci Nim, two players deal with a pile of n stones, where n>1. The first player may remove any number of stones, provided that at least one stone is left. Players alternate moves under the condition that if one player removed x stones, then another one may remove at most 2x stones. Some of them are described in [1-5]. Several years ago the author of this paper introduced a Nim game with a heap of N stones, where each player is allowed to take at most m stones, provided that he/she does not repeat the last move of her/his opponent (“do not be a copycat”). The player taking the last stone is the winner. However, a player loses if he/she cannot make a feasible move. Winning strategies for an arbitrary m>1 were provided by the author of this paper and imple-mented in  an d  by his graduate students. In the late 1980’s the author also introduced a variety of the Nim-game that is discussed in this paper. In the paper we study properties of winning points, provide an algorithm for direct computation of winning points and analyze its complexity. It is demonstrated that the algo-rithm has O(loglogn) time complexity and does not re-quire any storage, save a couple of numbers that are pre-computed at the beginning of the game. Preliminary results of this paper are published in . 2. Two-player Game on Plane 1) The Game starts after two distinct non-negative inte-gers 00,SL are selected randomly; here. 01pS< ;; (1) 00qS L0:;:SSLL0Remark 1: In the following discussion (S, L) is a point on a two-dimensional plane with integer coordinates; all further points are located in the positive quadrant of the plane; p and q determine a “level” of the Game. It is as-sumed that 0S 1}jnba1na and for all x; iJ:aibStepL5: u; n1:1;a 1:2;c 1:1;j W2: for n=1,2,… do 1:na1;ncW3: if 11nnjaan: then 1nc1;cn 1n:j;nj else 1:nc2;nc 1:nj1;nj Here, n stands for the largest index k of k that was used in , and n stands for the largest number of the set {1,2,...,k} which we cover for j b{}nacandjjab for jn . 7. Sequences A, B and Winning Points Theorem 2: For every integer 1n:,nnnwab (12) Proof: The following sequence of steps is a construc-tive proof of Th eorem1. Indeed, let :mLS (13) T1. If mSa, then by (3), (7) and (13) mbL; {Hugo is now in the winning point}. T2. If m, then Cora selects y := S – am; S := S – y and L := L – y; since S > am implies that L > bm. Indeed SamammLS mbSa. T3. {If m, then Cora finds either an index k < m such that kaS or an index i < m such that ibS}. T3a. If there exists an integer k < m such that kaS, then we select :kLb; {both m and kSaaS imply that k < m and k. Indeed, an assumption that leads to a contradiction, because implies that S am implies that L > bm. Then mmLSmamb Sa ; V2. If m, then there exists either an integer k < m such that kaS or an integer i < m such that ibS; V3. Both mSa and k imply that k < m and k. Indeed, an assumption that leads to a contradiction, because aSmkLbkm implies that S S; if then *k*kg S*k=; ; (30) k*kaI 2) If is the smallest integer satisfying the ine-quality (g+1) > S *i*ithen i = and (31) *i*ibSIf (16) has an integer solution, then from (29) we find the smallest integer k = satisfying the inequality *k*k(g+1)>S (32) Otherwise, {if (1)kgS} we solve the equation ibS. Then from (1 4) and (29) ib(1)ig+ i = S (33) Example 6: Find an integer index k such that 102ka. Then *k64 is the smallest integer for which holds *k102/(g+1) {see (29)}. 14. Required Accuracy for g It is assumed that in the Examples 3-6 and 8 we know the exact value of an irrational number g. However, to find an integer solution of (17) for an arbitrary large index k or i we must compute g with a high precision. Let 212/10/10 ../10..nngd dd (34) where is the i-th decimal digit of g idand g(t):= = 10 /10ttg2/10 /10dd12.. /10ttd (35) i.e., g(t) contains only the first t decimal digits of g. Theorem 4: Let 10kn. an = S (36) Then for all also holds that kt:tnangt= S. (37) 15. O(loglogn) Time Complexity for Win-ning Strategies It is easy to verify that a positive root of (24) can be computed using a Newton iterative process 21:1/2rr rxxx1, Where 0:1.618x (38) The process (38) has the following properties: a).It converges to (15)/2, i.e., for large r rx (15)/2+ r, (39) where r is a degree of accuracy ( error) after r iterati on s. Copyright © 2010 SciRes. IJCNS 798 B. VERKHOVSKY b). The error r satisfies the inequality 200rrrxg , i.e., it has a quadratic rate of convergence, and 300.001 10, . (40) Then from the inequality 3210 10rk32rkn we derive that (41) Thus 2log/ 3rk210 1010loglog/3log logn (42) The inequalities (42) are derived from (36), (40) and (41). Then from analysis of (37) it follows that the time complexity T(n) for solution of (16) is equal T(n)=O(loglogn). The Table 2 shows how many Newton iterations r(n) are required to compute as a function of n. nIn addition, we do not need to store any winning points. Instead, as it is demonstrated below, only a single real value of a*g must be stored. However, =10364( 1)g102. Hence the equa-tion does not have a solution. On the other hand, i does have a solution. Indeed, from (33) it follows that i102/(g+2)=38.961, i.e., =39. And finally . 102kab39(g102 2) 102*i 16. Solution of Index Equations Revisited R0.1. Let S := s; L := l; where both integers (s, l) are gen-erated randomly at the beginning of the Game; let t :=L – S; R0.2. r := ; using the iterative process (36), compute logtrx; (43) R0.3. Let *g:= rx; (44) {during the entire Game use *g as an approximation of g in the Equations (29) or (33)}; R1. Find the smallest integer satisfying the ine-quality *kk*g>S (45) if **kg Sthen k=; ; (46) *k*kaSR2. If is the smallest integer satisfying the ine-quality *i*i (*g+1) > S (47) Table 2. Logarithmic growth of r(n). 10kn [0,3] [4,6] [7,12] [13,24] r(n) 0 1 2 3 then i = and (48) *i*ibSExample 7: Let at the beginning of the Game s := 2,718,282 and l := 3,141,593. Then m :=L – S = l – s = 323,311<. From the ine-quality 6, {see (40) and (41)}, it follows that r =1. Hence, only one iteration of (38) is necessary to find 61032r*g with required accuracy. 17. The Algorithm It is assumed that Hugo makes the first move by ran-domly generating positive integers and such that 0S0L001LeSQ  (49) where e is Euler number, {see Remark3 belo w}; V: m := L – S; if m = 0 then z := S; S := S – z; L := L – z; {end of the Game: Cora is the winner}; else 10:log;tm; 2:log /3rt; 0:1.618;xfor k from 0 to 1r do 21:(1)/(21)kk kxx x; :rGx; ; :maGmif S =m then the Game is already in the winning state for Hugo; a{Nevertheless Cora might decide to continue the Game hoping that Hugo will make a mistake, i.e., he will “miss the point”}; if L > 3 then with prob = 1/2 c: = 1 or 2; :LLc}; goto V; else if mSazSthen :;:;:maLLzS Sz; goto V; else :/kSG; (50) kG S then :;:ymkLLy; (51) else :/(1)iSG; ; :iaGi:;:;:;:iuLatempSS LuL temp; goto V. Copyright © 2010 SciRes. IJCNS B. VERKHOVSKY 7990SRemark 3: In order to assure that the first randomly generated point is not a winning point, it is sufficient to select such and that 0S0L000(1)SLSg  (52) That is guaranteed by (47) and (15), since 001.718 1.618LS. 18. Randomization Let a and be the number of integers on inte rval [1, M] such that and 1 respectively, i.e., + =M. nnbn1kaM kbMaThen bn/( 1)anMMg and (53) 2/( 1)bnMM gHence, if a pair of integers (S, L) is generated ran-domly, then it is more likely that they will be elements of the sequence A, than the sequence B. Remark 4: The sequence of the operations (50) and (51) in the Algorithm is based on the observation that for every M, .  abnM nMThat is why on the A4 we first check whether there is a solution of and only then whether there is a solution of i. This sequence of verifications de-creases the average complexity of the algorithm. Another approach is to randomize the sequence of these operators: Namely, with the probability g = 0.618 to execute (50) and then, if necessary, to execute (51). And with the probability g = 0.382 to execute (51) and only then, if necessary, to execute (50). kaSbSExample 8: If M = 50, then 50 31an and . Thus, if u is an arbitrary selected integer on the interval [1, 50], then with probability g there exists an index k such that k, and with probability 50 19bnau2g= 0.382 there exists an index i such that . ibu 19. The First Move With out a th ird independent party, it seems impossible to introduce a random and trustworthy mechanism for de-ciding whose move is the first. As a palliative solution, the following procedure is suggested: immediately, after the first point (0,0) is generated, Hugo has a short period of time (say, a couple of seconds) to decide who must make the first move. One way to preclude Hugo from cheating and to introduce more variety to the Game, select Q := 2Q on every consecutive run of the Game with the same player. More detailed analysis of possible alternatives is beyond the scope of this paper. S L 20. Varieties of Nim-Game on Plane Of many possible varieties I consider only two: the Attri-tion game and the Flip-Flop game. In both games the moves are the same as in the Game described above in this paper. Only the goals are differ-ent. Attrition game: The first player that reaches point (0, 0) is a loser. Flip-flop game: Only once during the Game players on their move can change the goal of the Game if 27LS (54) 21. Winning Strategies Let the winning points k in the Attrition game. It is clear that both 1= (0,1) and 2= (2,2) are the win-ning points for Cora. Indeed, after Cora’s move (0, 1) Hugo is losing the Game. The same is with (2,2): after that move Hugo is forced to reach (0,0), because Hugo can make either (0,2) or (1,1) or (1,2) move. Then Cora moves (0,1) and Hugo has no other choice but move (0,0). ww wWinning points kf in Flip-Flop game: Although it seems confusing, actually the winning points for the Flip-Flop Game are very simple. It follows from an ob-servation that for all 2kkw=, (55) kwi.e., 2w (3,5); 3w (4,7); and only and 1(2,2)w0w(1, 0). Hence, if the Game is in the attrition phase, then kkfw, otherwise kkfw. (56) From the (56) winning strategy it follows that “Only once during the Game” — requirement is inessential and it is introduced for a psychological reason only. The Game can be further modified if the flipper must pay for every flip, and the winner gets the “bank”. After this paper was completed, the author discovered that the Game has been described in [13,14] . 22. Acknowledgements I appreciate H. Wozniakowski for his suggestion, an anonymous reviewer for several corrections and B. Blake for comments that improved the style of this paper. Copyright © 2010 SciRes. IJCNS B. VERKHOVSKY Copyright © 2010 SciRes. IJCNS 800 23. References  C. L. Bouton, “Nim, a Game with a Complete Mathe-matical Theory,” Annals of Mathematics, Princeton 3, 35-39, 1901-1902.  M. Gardner, “Mathematical Games: Concerning the Game of Nim and its Mathematical Analysis,” Scientific Ameri-can, 1958, pp. 104-111.  M. Gardner, “Nim and Hackenbush,” Chapter 14 in Wheels, Life, and Other Mathematical Amusements, W. H. Free-man, 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, 1999.  R. Statica, “Dynamic Randomization and Audio-Visual Development of Computer Games of Chance and Strat-egy,” Master Thesis, CIS Department, NJIT, 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 ed ition, 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.