### Paper Menu >>

### Journal Menu >>

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, [1]. 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 [6] an d [7] 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 [15]. 2. Two-player Game on Plane 1) The Game starts after two distinct non-negative inte- gers 00 ,SL are selected randomly; here. 0 1pS < ;; (1) 00 qS L0 :;:SSLL 0 Remark 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 <L holds, otherwise we swap the co- ordinates. 2) Three types of moves that allowed are: horizontal, vertical and diagonal. The players on their move may decrease either a). The first coordinate on an integer t, (S, L)(S – t, L), {horizontal move, h-move, for short} or b). The second coordinate on an integer u, *© Boris S. Verkhovsky April, 2001 794 B. VERKHOVSKY (S, L)(S, L – u), {vertical move, v-mo ve, for short} or c). Both coordinates on the same integer x, (S, L) (S – x, L – x), {diagonal move , d-move, for short}; The first player that reaches (0,0)-point on her/his move is the winner of the Game. An analogous Nim game was introduced by Wythoff [14]. Whytoff’ game is played with two heaps of coun ters: a player is allowed to take any number from either heap or the same number from both. The player taking the last counter wins. As in every two-person game with complete informa- tion, this Game has a winning strategy for one of the players [8-10]. In the following discussion we consider that a Human (Hugo) plays against a Computer (Cora). All points can be divided onto two classes: winning points for Cora and losing points for Cora. It is clear that a winning point for Cora is a losing point for Hugo, and vice versa. Definition 1: We will say that the Game is in a win- ning state if after Cora’s move it is in a winning point. Let’s denote Cora’s winning states as, for. Here = (0, 0). n w0n 0 Example 1: The 1= (1, 2) point is a Cora’s winning point, because Hugo cannot reach 0= (0, 0) point on his move. The 2= (3, 5) is another winning point for Cora, because on his move Hugo cannot reach either = (0,0) point or = (1,2) point. ww w w w 0 w1 On the other hand, after any move by Hugo, Cora reaches either (0,0) or (1,2). 3. Seven Properties of Winning Points P1. It is easy to see that if (c,d) is a winning point, then (d,c) is also a winning point. P2. With exception of the (0 ,0)-point, in all other win- ning points . Indeed, let (c,c) be a winning point for Cora. Then Hugo can reach the (0,0)-point using a diagonal move, {via subtracting the same y = c from both coordinates}. cd P3. If the Game is in a winning point w after Cora’s move, then there is no move by which Hugo can reach another winning state . On the other hand, if the Ga me is in a losing point l, then there exists at least one move that transforms the Game into a winning state. For ex- ample, if after Hugo’s move the Game is in the state (7, 9), then there are two winning moves for Cora: (4,7) and (3,5). w In general, let W be a set of all winning points and L be a set of all losing points. Then after one move the Game is transformed from W to L. However, if the Game is in L, then there exists at least one move that transforms the game into W. Formally it means that, if (,)SL W , then for any positive integer u, or (,)L WSu (, )SL uW or (,)SuLu W k w, kk cd ii kk dcdc . P4. Proposition 1: There are no two winning points = () and = () such that i w, ii cd r (2) where r is an integer. Proof: Let's assume that for i < k Equation (2) holds and i :k vdd i w i w , ii cd Then after Cora’s move Hugo can reach via a diagonal move, i.e., by subtracting from both coordinates the same integer v. k w P5. Let and be two distinct winning points. Then all , are distinct integers, otherwise Hugo would be able to transform the Game into another winning state. k w , kk cd ,SL nn dcn P6. Proposition 2: Let . Then for every n=1,2,…holds W ) m: . (3) Proof: Let’s assume that there exists at least one win- ning point , for which , and m is the smallest integer; and let (, m cd mm dcm mm s dc ) . Consider(, s s: if s < m, then since by assumption m is the smallest. cd ss dcs Therefore, mm ss dcsdc ms c, or ms ddc ms dc c . Let :zd ms ) . Then there is a diagonal move that transforms one winning point into another winning point(, (, ) mm cd s s cd , which contradicts with the definition of a winning point. Therefore, 1sm is impossible. Let’s now assume that . 1sm 1 mk dd Observe that , otherwise for k1m . km cc 1 m d Consider Hugo’s move(, , 1) mm cd m cm where mm cd 1) . But in this case Cora cannot make either a horizontal move or a diagonal move that transforms the Game into a winning state. The latter im- plies that (, is a winning state, which in its turn contradicts the earlier assumption that is the winning state. Q.E.D. (, ) mm cd P7. Theorem 1: {Fundamental property of the win- ning point s}: a) Let 0 1x2; and for all 0k 2 :1/2 kk k xx x 1 1 k ; (4) b) Let limGx k ; c) (S, L) is a winning point if SLSG (5) Copyright © 2010 SciRes. IJCNS B. VERKHOVSKY Copyright © 2010 SciRes. IJCNS 795 StepL6: : nn ban . For the sake of simplicity of further discussion, we assume that in every point (c,d) c<d. Then the conditions (9)-(11) also hold for k = n. Q.E.D. Applying the Steps L1-L6, we sequentially generate the winning points 4. Game in Progress: An Example W={(1,2); (3,5); (4,7); (6,10); (8,13); (9,15); (11,18); (12,20); (14,23); (16,26); (17,28); (19,31); (21,34); (22,36); (24,39); (25,41); (27,44);…}, Let (S0,L0) = (29,51) be a randomly generated initial point; Hugo makes the 1st move; in italics are shown Hugo’s moves; in bold are Cora’s winning points Table 1. i.e., 17 17 ,ab= (27,44). Therefore from the StepL3 J = {11, 12, 13, 14, 15, 16, 17}, and u = 29. 5. System of Equations with Infinite Sequ ences Then 18 18 ,ab = (29,47). Proposition 3: 1). Let A:={n a}; B:={n b} be monotone increasing sequences of positive integers; here 11a and n = 1,2,…; 6. Alternative Formulation of L1-L6 Algo- rithm 2). Let the sequences A and B satisfy the following system of equations: W1: BA (6) BAN (7) BAN (8) where in (7) ={ , BA} nn ba i.e. is a sequence of pair-wise differences of corresponding elements of B and A, and N is the set of all natural numbers {1,2,3,…}. Then the system of Equa- tions (6)-(8) with unknown sequences A and B has a so- lution. BA Proof {by induction}: The following algorithm is a constructive proof that a solution of (6)-(8) exists. Indeed, the sequences A={ n can be itera- tively generated using an analogue of the Sieve of Eratosthenes: };{ } n aBb StepL1: ; 11 ,:(1,2ab :{A ) 1 StepL2: Let }; 1k ..,b12 1 112 1k be sequences such that for every k<n the following conditions hold: ,,.., k aaa : k B ,,bb 12 .. k aaa ; 12 .. k bb b 1 (9) 11kk AB (10) and for every 11ik ii ba i (11) StepL3: Let J = {j: ; 1 StepL4: Compute an integer u := minx, where x > 1} jn ba 1n a and for all x; iJ:ai b StepL5: u; n 1:1;a 1:2;c 1:1;j W2: for n=1,2,… do 1: n a1; n c W3: if 11 n nj aa n : then 1n c 1;cn 1n:j ; n j else 1: n c2; n c 1: n j1; n j 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 {} n acand j j ab for jn [11]. 7. Sequences A, B and Winning Points Theorem 2: For every integer 1n :, nnn wab (12) Proof: The following sequence of steps is a construc- tive proof of Th eorem1. Indeed, let :mLS (13) T1. If m Sa , then by (3), (7) and (13) m bL ; {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 ma mm LS mb Sa . T3. {If m , then Cora finds either an index k < m such that k aS or an index i < m such that i bS }. T3a. If there exists an integer k < m such that k aS , then we select :k Lb ; {both m and k SaaS imply that k < m and k. Indeed, an assumption that leads to a contradiction, because implies that S < Lb kmmk m aa k , but k aS }. Table1 Player Hugo Cora Hugo Cora Hugo Cora Examples of moves (23,51) (14,23) (6,15) (6,10) (4,6) (3,5) Type of move h-move v-move d-move v-move v-move d-move B. VERKHOVSKY Copyright © 2010 SciRes. IJCNS 796 T3b. If there exists an integer i < t such that i bS , then we assign ; ; {since implies that : }, [6]. :LS ii ab:i Sa SL i bS i aL 8. Iterative Algorithm and its Complexity In applications for computer games, an iterative compu- tation of n a for a large n is time consuming, since its time complexity T(n) and space complexities S(n) are both of order O(n). For instance, if , then we need to generate and store one trillion pairs of integers. A brief analysis shows that this is well beyond of current size of memory for PC. A more efficient algo- rithm is described below. and n b ) n t t 12 10n 9. Direct Computation of an and bn To decrease the complexity of computation of an and bn and avoid excessive storage, let's find a closed-form ex- pression for:= v(n). Then from (11) n a : n bv(n)+n (14) Conjecture 1: (prope rties of winnin g points): C1. ; /( m amzom and (15) lim / m mamz where z is a constant. C2. For every integer 1n n anz (16) The property (16) and the asymptotic behavior (15) are observed in numerous computer experiments. Conjecture 2: For large n / n ba= z + o(n) (17) Remark 2: The Conjecture 2 is also based on extensive computer experiments. Theorem 3: Conjecture 1 implies that z is an irrational number. Proof: An assumption that z is a rational number leads to contradiction. Assume that z = q/s, where both q and s are relatively prime integers. Then there exis ts an infinite number of pairs and such that =. Indeed, select n ar bn ar b n := (q+s)st and r := qst (18) Then for the integer t = 1,2,3,… it follows from (16) and (14) that n aqsq (19) and , (20) 2 r bqtqs which is a violation of the conditions (6) and (10). Conjecture 3: z=g+1, where g is a golden ratio, i.e., 51/2g (21) The property (21) is observed in numerous computer experiments. It plausibility follows from the following: Since for a large n = nz + o(n) n a and = (z+1)n + o(n) (22) n b then it follows from (17) and (22) that / n ba n (z+1)/zz (23) Then for large n's, z is a positive solution of the equa- tion. 210xx (24) i.e., z (51 )/2, {the value of the golden ratio +1}. Let the Game be in the state (S, L) after Hugo’s move and let m := (13). LS Then the Game is implicitly in one of five states {where by convention holds that S < L}: A. (S, L) = (), {the game is in a winning state for Hugo}; , mm ab B. (S, L) = () , where ; , ij aa ,abij C. (S, L) = (); where either or ; ij ,ba ijij D. (S, L) = (), ij ij ; E. (S, L) = (), ,bb ij ij . However, from th e condition (11) alone we do not know yet in which of the states A, B, C, D or E the Gam e is. 10. Algorithm for Winning Points (AWP) A1: Let m := LS ; A2: Using (16) and (21), compute ; m if m a aS then by (11) ; {Hugo is now in the winning state }; m bL m w a A3: if then do y :=; S := m Sm SaSy and L := Ly ; A4: if there exists an integer k < m such that k aS then :; k Lb else find an integer i < m such that ; i bS:LS ; :i Sa . 11. Validation of AWP V1. In A3, S > am implies that L > bm. Then mm LSmamb Sa ; V2. If m , then there exists either an integer k < m such that k aS or an integer i < m such that i bS ; V3. Both m Sa and k imply that k < m and k. Indeed, an assumption that leads to a contradiction, because aS mk Lbkm implies that S<mk aa , but k aS ; B. VERKHOVSKY 797 V4. In A4, implies that . Hence . i bS S i aL ii abSL Example 2 {case m}: Let the Game be in the state (S, L) = (19, 26) after the Hugo’s move. a Because m = 26 –19 = 7, compu te =11 and 18. 7 a7( 1)g 7 Since 11 < 19 and 18 < 26, then Cora moves b S := S – m = S – 7 and L := L – m = L – 7; Example 3 {case}: Let now after Hugo’s move (S, L) = (15, 32). m Sa Since m = 32–15 =17, compute =27. 17 Since 17 , but 15 = , then Cora’s move is L := 15 and S := L – 6 = 9. a17( 1)g 15 a6 b Example 4: {case}: Let (S, L) = (14, 29) after Hugo’s move. m Sa Since m = 15, compute 15 a 15( 1)g =24. Since , but 14 =, then Cora moves 15 L := 29 – 6 = 23. 14ab9 a 9 Example 5: {casem}: Then , and the game is in the winning state for Hugo. aSm bL 12. Fibonacci Properties of Winning Points 1. If n is an odd Fibonacci number, i.e., if 21k nF , then n a=2k F (25) 2. If n is an even Fibonacci number, i.e., if 2k nF , then n a= (26) 21 1 k F Indeed, ; 357 9 3; 8;21; 55 FFF F aaa a 1;4; 12;aaa 33a But . 24 6 FF F8 F 13. Solution of Equation with Un known Index On the step A4 of the algorithm we must solve either equation k or i in order to respectively determine the indices k or i. In order to determine the indices we must solve either the equation aSbS k aS (27) or the equation i bS (28) This can be done by using (16) k a==S (29) (1)kg S I 1) Find the smallest integer satisfying the ine- quality kg > S; if then * k * kg S * k=; ; (30) k* k a I 2) If is the smallest integer satisfying the ine- quality (g+1) > S * i * i then i = and (31) * i* i bS 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 i bS . Then from (1 4) and (29) i b (1)ig + i = S (33) Example 6: Find an integer index k such that 102 k a . Then * k 64 is the smallest integer for which holds * k102/(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 2 12 /10/10 ../10.. n n gd dd (34) where is the i-th decimal digit of g i d and g(t):= = 10 /10 tt g 2 /10 /10dd 12 .. /10t t d (35) i.e., g(t) contains only the first t decimal digits of g. Theorem 4: Let 10k n . an = S (36) Then for all also holds that kt : t n angt = 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 2 1:1/2 rr r xxx 1 , Where 0:1.618x (38) The process (38) has the following properties: a).It converges to (15)/2, i.e., for large r r x (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 2 00 r r r x g , i.e., it has a quadratic rate of convergence, and 3 00.001 10 , [12]. (40) Then from the inequality 32 10 10 rk 32 rk n we derive that (41) Thus 2 log/ 3rk 210 1010 loglog/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. n In 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, =103 64( 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 . 102 k a b 39(g 102 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 r x ; (43) R0.3. Let * g := r x ; (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 * k k* g >S (45) if ** kg S then k=; ; (46) * k* k aS R2. If is the smallest integer satisfying the ine- quality * i * i (* g +1) > S (47) Table 2. Logarithmic growth of r(n). 10k n [0,3] [4,6] [7,12] [13,24] r(n) 0 1 2 3 then i = and (48) * i* i bS 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 6 10 32 r * 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 0 S0 L 00 1LeSQ (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 2 1:(1)/(21) kk k xx x ; :r Gx ; ; : m aGm 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 m Sa zS then :;:;: m aLLzS Sz; goto V; else :/kSG ; (50) kG S then :;:ymkLLy; (51) else :/(1)iSG ; ; : i aGi :;:;:;: i uLatempSS LuL temp ; goto V. Copyright © 2010 SciRes. IJCNS B. VERKHOVSKY 799 0 S Remark 3: In order to assure that the first randomly generated point is not a winning point, it is sufficient to select such and that 0 S0 L 000 (1)SLSg (52) That is guaranteed by (47) and (15), since 00 1.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. n n b n 1k aM k bM a Then b n /( 1) a nMMg and (53) 2 /( 1) b nMM 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, . ab nM 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). k aS bS Example 8: If M = 50, then 50 31 a n 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 19 b n au2 g = 0.382 there exists an index i such that . i bu 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). w w w Winning points k f 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 2k kw=, (55) k w i.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 kk f w , otherwise kk f w. (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 [1] C. L. Bouton, “Nim, a Game with a Complete Mathe- matical 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 Ameri- can, 1958, pp. 104-111. [3] M. Gardner, “Nim and Hackenbush,” Chapter 14 in Wheels, Life, and Other Mathematical Amusements, W. H. Free- man, 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, 1999. [7] R. Statica, “Dynamic Randomization and Audio-Visual Development of Computer Games of Chance and Strat- egy,” Master Thesis, CIS Department, NJIT, 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 ed ition, 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. |