From: bruno@cerberus.csd.uwm.edu (Bruno Wolff III) Newsgroups: rec.games.abstract Subject: Re: Dots and boxes (was: Top Ten Abstract Games) Date: 19 Aug 1997 21:04:06 GMT >From article <5tcra7$500$1@gannett.math.niu.edu>, by rusin@vesuvius.math.niu.edu (Dave Rusin): ] So what _is_ the status of dots-and-boxes as an abstract game? Anyone ] have any references to studies of winning strategies, expected run times, ] and so on? (Perhaps most important: any clues how one can snatch defeat ] from the jaws of victory when playing against a child? :-) ) ] ] (It's too close to the start of the semester for me to analyze myself...) ] ] dave ] Winning Ways volume 2 has a very good discussion on how to play Dots and Boxes well. -- I no longer accept email from all places. Some email to me may result in automated replies to the sender and to direct and indirect providers of their internet service. ============================================================================== From: mwdaly@kodak.com (Matthew Daly) Newsgroups: rec.games.abstract Subject: Re: Dots and boxes (was: Top Ten Abstract Games) Date: Thu, 21 Aug 1997 16:19:07 GMT rusin@vesuvius.math.niu.edu (Dave Rusin), if that is your REAL name, said: >So what _is_ the status of dots-and-boxes as an abstract game? Anyone >have any references to studies of winning strategies, expected run times, >and so on? (Perhaps most important: any clues how one can snatch defeat >from the jaws of victory when playing against a child? :-) ) Having searched for any edition of any volume of "Winning Ways" has been futile for me, so I'll assume that quoting it as a source of answers isn't as productive as it should be. Perhaps someone can paraphrase the strategy they describe? It seems to me that the game has two phases: - the opening (where you and your opponent create a maximal grid with the property that no square has three filled-in edges) - the endgame (where you and your opponent trade the rights to certain groups of squares) (I'm assuming that there is no profit in ceding a square to your opponent before you have a maximally filled board -- this might be a rash assumption) Think of the board as a graph where two squares are connected if the line between them is NOT filled in. Then, at the end of the opening, the graph is a forest: i.e. it has no cycles. It seems that it would be a relatively easy question to discover the best way to play the endgame for a given forest and whether the first player or the second player would win if such a forest came up at the end of the opening. Once you've figured that out, and categorized the winning configuration of forests, it's just a matter of playing the opening in such a way as to achieve a fortuitous forest for your endgame. Whether that is easy or not is open to debate, but I should think that it would be easy to learn enough to defeat someone who didn't recognize the importance and significance of the opening moves. -Matthew -- Matthew Daly I feel that if a person has problems communicating mwdaly@kodak.com the very least he can do is to shut up - Tom Lehrer My opinions are not necessarily those of my employer, of course. --- Support the anti-Spam amendment! Join at http://www.cauce.org --- ============================================================================== From: bruno@cerberus.csd.uwm.edu (Bruno Wolff III) Newsgroups: rec.games.abstract Subject: Re: Dots and boxes (was: Top Ten Abstract Games) Date: 21 Aug 1997 20:53:21 GMT >From article <34016706.68576078@newsserver.rdcs.kodak.com>, by mwdaly@kodak.com (Matthew Daly): > rusin@vesuvius.math.niu.edu (Dave Rusin), if that is your REAL name, said: > >>So what _is_ the status of dots-and-boxes as an abstract game? Anyone >>have any references to studies of winning strategies, expected run times, >>and so on? (Perhaps most important: any clues how one can snatch defeat >>from the jaws of victory when playing against a child? :-) ) > > Having searched for any edition of any volume of "Winning Ways" has been > futile for me, so I'll assume that quoting it as a source of answers isn't > as productive as it should be. Perhaps someone can paraphrase the > strategy they describe? > > It seems to me that the game has two phases: > - the opening (where you and your opponent create a maximal grid with the > property that no square has three filled-in edges) > - the endgame (where you and your opponent trade the rights to certain > groups of squares) > The very endgame is usually pretty simple. Whoever has control wins. There are some endgames where the person who has control will lose (or at least will have to give up control at the correct time). Solving the general end game is NP complete. After the idea of keeping control (giving away the last two boxes in a chain or the last four in a loop), the next big step is converting the game to nimstrings. Nimstrings is about making sure you end up with control of the game. It doesn't count boxes so there are some unusual situations where you can win at nimstrings, but loses at dots and boxes. Nimstring is an impartial game. Combinatorial game theory works well for it (the values of isolated positions can be easily combined to provide a value for the full position). You can produce catalogs of positions that will help you play well. Getting exact analysis of big grids isn't feasible (as far as I know - I don't remember seeing an proof of this). So who will win when two good players play is generally going to be who has the better catalog of position values. In big games you can usually make sure that the nimstring winner will win the dots and boxes game. You might find copies of Winning Ways in some libraries, especially college libraries. The Dots and Boxes analysis also may have been published elsewhere by the authors. You might try a literature search for Dots and Boxes or for Berlekamp, Conway or Guy. -- I no longer accept email from all places. Some email to me may result in automated replies to the sender and to direct and indirect providers of their internet service. ============================================================================== From: mykey Newsgroups: rec.games.abstract Subject: Re: Dots and boxes (was: Top Ten Abstract Games) Date: Thu, 21 Aug 1997 13:20:45 -0700 Matthew Daly wrote: > > Having searched for any edition of any volume of "Winning Ways" has been > futile for me, so I'll assume that quoting it as a source of answers isn't > as productive as it should be. Perhaps someone can paraphrase the > strategy they describe? > > It seems to me that the game has two phases: > - the opening (where you and your opponent create a maximal grid with the > property that no square has three filled-in edges) > - the endgame (where you and your opponent trade the rights to certain > groups of squares) > > (I'm assuming that there is no profit in ceding a square to your opponent > before you have a maximally filled board -- this might be a rash > assumption) > > Think of the board as a graph where two squares are connected if the line > between them is NOT filled in. Then, at the end of the opening, the graph > is a forest: i.e. it has no cycles. It seems that it would be a relatively > easy question to discover the best way to play the endgame for a given > forest and whether the first player or the second player would win if such > a forest came up at the end of the opening. > > Once you've figured that out, and categorized the winning configuration of > forests, it's just a matter of playing the opening in such a way as to > achieve a fortuitous forest for your endgame. Whether that is easy or not > is open to debate, but I should think that it would be easy to learn enough > to defeat someone who didn't recognize the importance and significance of > the opening moves. > > -Matthew > -- > Matthew Daly I feel that if a person has problems communicating > mwdaly@kodak.com the very least he can do is to shut up - Tom Lehrer > > My opinions are not necessarily those of my employer, of course. > > --- Support the anti-Spam amendment! Join at http://www.cauce.org --- At first glance: The important abilities would be to evaluate the value of a sequence. +--+--+--+--+--+ ! ! ! + +--+ + + + ! ! +--+--+--+--+--+ In this example the ability to recognize the left portion at a value of 6, and the right portion as a 4. At the "maximal grid" state, you would just have a list of values. You wish to give the smaller values to your opponent. The question then becomes one of parity. It may be worth while to cede an sequence in order to change who gets the last sequence. Parity is important in this example: A B C D E F G H I J K +--+--+--+--+--+--+--+--+--+--+--+ 1 ! ! + +--+--+--+ + +--+--+--+--+--+ 2 ! ! ! ! +--+--+ +--+--+ + +--+--+--+ + 3 ! ! ! ! ! ! + + +--+--+ + + + +--+--+--+ 4 ! ! ! ! ! + +--+--+--+--+--+--+--+--+--+ + >From here what's your best move? A1e = +4 (-20 +24) A4s = -24 (-10 +10 -24) K1e = -24 (-24 +10 -10) mykey ============================================================================== From: mykey Newsgroups: rec.games.abstract Subject: Re: Dots and boxes (was: Top Ten Abstract Games) Date: Thu, 21 Aug 1997 16:44:30 -0700 Bruno Wolff III wrote: > > From article <33FCA31D.4660@geocities.com>, by mykey : > ] > ] Parity is important in this example: > > No it isn't. > > ] > ] A B C D E F G H I J K > ] +--+--+--+--+--+--+--+--+--+--+--+ > ] 1 ! ! > ] + +--+--+--+ + +--+--+--+--+--+ > ] 2 ! ! ! ! > ] +--+--+ +--+--+ + +--+--+--+ + > ] 3 ! ! ! ! ! ! > ] + + +--+--+ + + + +--+--+--+ > ] 4 ! ! ! ! ! > ] + +--+--+--+--+--+--+--+--+--+ + > ] > ]>From here what's your best move? > ] > ] A1e = +4 (-20 +24) > ] A4s = -24 (-10 +10 -24) > ] K1e = -24 (-24 +10 -10) > ] > ] mykey > ] > > While the person to move should always losse against a competent opponent, > some moves will result in a more lopsided scores than others. > > The best thing to do is move in the lower left first. The other player will > take that chain and leave you the last two boxes. You take these and then > move into the upper left (which you just made into a loop). The other player > will take this except for the last 4 boxes. You take these and then give > him the big chain. Getting 6 boxes is the best you can do against a > competent opponent. > -- > I no longer accept email from all places. Some email to me may result in > automated replies to the sender and to direct and indirect providers of their > internet service. When I read your post previous to this one, I just knew the hammer was coming down on me. Yes, for some reason I completely overlooked the option to take incomplete sequences. Now that I see that idea, 6 - 38 does appear correct. Don't I feel stupid. :) mykey ============================================================================== From: bruno@cerberus.csd.uwm.edu (Bruno Wolff III) Newsgroups: rec.games.abstract Subject: Re: Dots and boxes (was: Top Ten Abstract Games) Date: 22 Aug 1997 14:21:49 GMT >From article <33FCD2DE.46AF@geocities.com>, by mykey : > > When I read your post previous to this one, I just knew the hammer was > coming down on me. > Yes, for some reason I completely overlooked the option to take > incomplete sequences. > > Now that I see that idea, 6 - 38 does appear correct. Don't I feel > stupid. :) > > mykey > But, now you know the most important trick to winning dots and boxes. You can probably beat most people the first time you play them. Unfortunately this trick is easily figured out once someone does it to you. Note you want to make sure that your 2 and 4 box handouts are hard hearted so that they can't be handed back to you. For example if you have just been handed: * *--* | | * *--* + other disconnected stuff | | * * Don't move to this if you want to keep control: *--*--* | | | * *--* + other disconnected stuff | | * * Or you will get this back: *--*--* | | | * *--* + other disconnected stuff | | *--* Instead do this: * *--* | | | *--*--* + other disconnected stuff | | * * -- I no longer accept email from all places. Some email to me may result in automated replies to the sender and to direct and indirect providers of their internet service. ============================================================================== From: rusin@vesuvius.math.niu.edu (Dave Rusin) Newsgroups: rec.games.abstract Subject: Re: Dots and boxes -- literature review (esp _Winning Ways_) Date: 25 Aug 1997 05:10:41 GMT One respondent to my query abouts Dots and Boxes suggested I do the old-fashioned thing and look up library references. Sure enough, I found seven relevant items which I reprint below. I have not looked through all these papers. Winning Ways is the last citation; I've listed its Table of Contents. Data come from the AMS' MathSciNet. dave [Here is a more detailed version of the information in that post -- djr.] 97h:90004 90-06 05-06 90D46 Games of no chance. (English) Papers from the Combinatorial Games Workshop held in Berkeley, CA, July 11--21, 1994. Edited by Richard J. Nowakowski. Mathematical Sciences Research Institute Publications, 29. Cambridge University Press, Cambridge, 1996. xii+537 pp. $49.95. ISBN 0-521-57411-0 Contents: John H. Conway, The angel problem (3--12); Aviezri S. Fraenkel, Scenic trails ascending from sea-level Nim to alpine chess (13--42); Richard K. Guy, What is a game? (43--60); Richard K. Guy, Impartial games (61--78); Julian West, Championship-level play of dots-and-boxes (79--84); Julian West, Championship-level play of domineering (85--91); David Wolfe, The Gamesman's Toolkit (93--98); Ralph Gasser, Solving Nine Men's Morris (101--113); Jonathan Schaeffer, Marion Tinsley: human perfection at checkers? (115--118); Jonathan Schaeffer and Robert Lake, Solving the game of checkers (119--133); Noam D. Elkies, On numbers and endgames: combinatorial game theory in chess endgames (135--150); Lewis Stiller, Multilinear algebra and chess endgames (151--192). Yasuhito Kawano, Using similar positions to search game trees (193--202); Elwyn Berlekamp and Yonghoan Kim, Where is the "Thousand-Dollar Ko"? (203--226); Howard A. Landman, Eyespace values in Go (227--257); David Moews, Loopy games and Go (259--272); Martin Muller [Martin Muller 2] and Ralph Gasser, Experiments in computer Go endgames (273--284); Jeff Erickson, Sowing games (287--297); Jeff Erickson, New Toads and Frogs results (299--310); Dan Garcia, Xdom: a graphical, X-based front-end for Domineering (311--313); David Moews, Infinitesimals and coin-sliding (315--327); Richard J. Nowakowski and David G. Poole, Geography played on products of directed cycles (329--337); Hilarie K. Orman, Pentominoes: a first player win (339--344); Julian West, New values for Top Entails (345--350); Michael Zieve, Take-away games (351--361). Elwyn Berlekamp, The economist's view of combinatorial games (365--405); David Blackwell, Games with infinitely many moves and slightly imperfect information (extended abstract) (407--408); Dan Calistrate, The reduced canonical form of a game (409--416); Aviezri S. Fraenkel, Error-correcting codes derived from combinatorial games (417--431); Hiroyuki Iida, Yoshiyuki Kotani and Jos W. H. M. Uiterwijk, Tutoring strategies in game-tree search (extended abstract) (433--435); James G. Propp, About David Richman (437); Andrew J. Lazarus, Daniel E. Loeb, James G. Propp and Daniel Ullman, Richman games (439--449); Daniel E. Loeb, Stable winning coalitions (451--471); Richard K. Guy, Unsolved problems in combinatorial games (475--491); Aviezri S. Fraenkel, Combinatorial games: selected bibliography with a succinct gourmet introduction (493--537). 92d:90138 90D46 05-06 90-06 Combinatorial games. (English) Lecture notes prepared for the American Mathematical Society Short Course held in Columbus, Ohio, August 6--7, 1990. Edited by Richard K. Guy. AMS Short Course Lecture Notes. Proceedings of Symposia in Applied Mathematics, 43. American Mathematical Society, Providence, RI, 1991. xii+233 pp. $52.00. ISBN 0-8218-0166-X Contents: Richard K. Guy, What is a game? (pp. 1--21); John Horton Conway, Numbers and games (pp. 23--34); Richard K. Guy, Impartial games (pp. 35--55); John Horton Conway, More ways of combining games (pp. 57--71); Elwyn Berlekamp, Introductory overview of mathematical Go endgames (pp.\ 73--100); Vera Pless, Games and codes (pp. 101--110); Aviezri S. Fraenkel, Complexity of games (pp. 111--153); Richard J. Nowakowski, $\ldots$, Welter's Game, Sylver Coinage, Dots-and-Boxes,$\,\ldots$ (pp. 155--182); Richard K. Guy, Unsolved problems in combinatorial games (pp. 183--189); Aviezri S. Fraenkel, Selected bibliography on combinatorial games and some related material (pp. 191--226). The book appears in the AMS Short Course Lecture Notes series and it indeed constitutes a very good short course on the subject of combinatorial games. It is a series of eight introductory papers, well chosen and fitting well together. The result is an informative and readable text, useful both for those who want to get acquainted with the basics and for those interested in some special attractive topics in the area. The series starts with Guy's article discussing definitions and examples, and presenting (one possible) formal definition of a game. Guy is also the author of another article discussing impartial games. The second article, by Conway, concerns his approach to numbers as special games. Conway also discusses in the fourth article several ways of combining games. The article by Berlekamp is devoted to attractive and deep problems of Go. Next, Pless discusses the relation of codes and games, a very useful topic. Then there is an article by Fraenkel on the complexity of games, a topic which may well be crucial in the area, and an article of Nowakowski discussing several concrete games. The text is completed by a selection of (well-explained) unsolved problems by Guy, and by a voluminous bibliography with an informative introduction by Fraenkel. Reviewed by A. Pultr 91i:68053 68Q25 05C70 05C85 68R10 Berman, Fran(1-UCSD); Johnson, David(1-BELL); Leighton, Tom(1-MIT); Shor, Peter W.(1-BELL); Snyder, Larry(1-WA-C) Generalized planar matching. (English) J. Algorithms 11 (1990), no. 2, 153--184. The authors prove that it is NP-hard to find the maximum number of vertex disjoint copies of a fixed planar graph $H$ in some arbitrary planar graph $G$, provided that $H$ has at least three vertices. This substantially strengthens the similar result of D. G. Kirkpatrick and P. Hell [in Conference Record of the Tenth Annual ACM Symposium on Theory of Computing (San Diego, CA, 1978), 240--245, ACM, New York, 1978; MR 80d:68053] which dealt with the general nonplanar case. They also give some approximation algorithms based on the Lipton-Tarjan planar separation algorithm. They use the techniques developed in the paper to prove the NP-completeness of a tile salvage problem and one related to a classic game of "dots and boxes". Reviewed by Alan M. Frieze 91g:90180 90D05 00A08 Berlekamp, Elwyn(1-CA) Two-person, perfect-information games. (English) The legacy of John von Neumann (Hempstead, NY, 1988), 275--287, Proc. Sympos. Pure Math., 50, Amer. Math. Soc., Providence, RI, 1990. Some survey results are presented on the recent extensions of the theory of the sums of two-person perfect-information games. The following aspects are dealt with: recursions, algebras and fundamental axioms. Concepts of domineering and blockbusting are discussed in relation to Conway's axioms, which underlie such games and introduce partial order and the concept of sum of such games. The implications of this extended theory are discussed briefly in relation to the following aspects: (a) complete and perfect strategies for arbitrary sums of solved games, (b) solutions of more complicated games solved to within "best numerical approximations" or "asymptotically", and (c) specific situations of the games of "dots and boxes". Reviewed by Jati K. Sengupta 89f:05111 05C40 90D05 Meyniel, Henry(F-PARIS6); Roudneff, Jean-Pierre(F-PARIS6) The vertex picking game and a variation of the game of dots and boxes. (English) Discrete Math. 70 (1988), no. 3, 311--313. This paper analyzes a game played on a graph. The players alternatively select edges, scoring when vertices become isolated as a result of their edge removal. This game is nearly a generalization of dots and boxes, except that each player removes one edge at his turn even if he succeeds in isolating a vertex. The winner is the player who isolates the most vertices. The main theorem of the paper is: If $G$ is a graph with an odd number of edges, then the first player has a winning strategy. The paper concludes with a theorem on optimal strategies for the special case in which $G$ is a grid of boxes. This game is nearly the same as dots and boxes. Reviewed by Harold Reiter 85a:05076 05C99 90D42 Harary, Frank(1-MI) From dots and boxes to maps and regions, and beyond. (English) J. Recreational Math. 16 (1983/84), no. 1, 22--32. The author considers a natural generalization to planar graphs of four common dots and boxes games. The usual version of dots and boxes in which each player attempts to accumulate the majority of the boxes is called a multiplicity game. Its misere version can be described as a multiplicity avoidance game. The two other types of dots and boxes games considered are First Box Wins and First Box Loses. For the generalization, consider a given planar graph $G$ and a plane realization $M$ of $G$. The first player chooses any edge and colors it red. The second then colors some other edge blue. The players continue, alternating the coloring of an edge. As soon as one of the regions of $M$ is enclosed by all edges of the same color, the player who completed it puts his or her initial inside it and moves again. In the multiplicity game, the player whose initial appears in more regions is the winner. The other three games generalize in the natural way. Reviewed by Harold Reiter 84h:90091a 90Dxx 05-02 90-02 Berlekamp, Elwyn R.; Conway, John H.; Guy, Richard K. Winning ways for your mathematical plays. Vol. 1. (English) Games in general. Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London-New York, 1982. xxxi+426+xi pp. ar64.50 ($22.50 paperbound) the two volume set. ISBN 0-12-091150-7; 0-12-091101-9 84h:90091b 90Dxx 05-02 90-02 Berlekamp, Elwyn R.; Conway, John H.; Guy, Richard K. Winning ways for your mathematical plays. Vol. 2. (English) Games in particular. Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London-New York, 1982. pp. i--xxxiii and 429--850 and i--xix. $64.50 (\$22.50 paperbound) the two volume set. ISBN 0-12-091152-3; 0-12-091102-7 The two volumes are crammed to the brim with information, colored illustrations and examples, and it is possible here to indicate only the main topics included in each chapter. The first 13 chapters constitute Volume 1, entitled "Games in general". Chapter 1: Notion of partizan games, illustrated by means of a number of examples, especially Blue-Red Hackenbush, which plays a fundamental role in partizan games, analogous to that played by Nim in impartial games: In a blue-red string figure, Left removes any blue edge and all edges not connected to ground anymore. Right moves similarly on red edges. The player first unable to move loses. Chapter 2: Tools for working with partizan games, such as the simplicity principle: The value of a game (L{vert}R), if a number, is the simplest number in (L, R). Positive, negative, zero and fuzzy positions. Notion of sum of games. Impartial games: Green Hackenbush (either player may remove a green edge), Nim, Nimbers (the values of impartial games). Chapter 3: Variations on Nim, mex rule, Sprague - Grundy theory: Every impartial game is just a bogus Nim-heap. (From a computational standpoint, there may be considerable differences between impartial games. Thus, nobody knows whether or not there is a polynomial-time strategy for sums of Wythoff games, whereas Nim is trivially polynomial.) In the second part of Chapter 3, attention is shifted back to partizan games: Reversible moves, dominated positions, the size of small fuzzy games. Chapter 4: Back to impartial games: P and N-positions. Octal games such as Kayles and Dawson's Kayles. It is conjectured that Grundy's game (divide any pile of tokens into two unequal piles) is ultimately periodic. Chapter 5: More on partizan games. Sums of switches and numbers: Move in a switch (x{vert}y) (x >= y) with largest temperature {1/2}(x - y). Hot games, tiny games. Examples: Domineering, Toads and Frogs. Chapter 6: Deeper analysis of hot games whose options are not necessarily numbers. Mean values and stop values. Thermographs. Equitable and Excitable games. Chapter 7: All about Hackenbush. The colon principle, parity and fusion principles for analyzing Green Hackenbush. Blue-Red Hackenbush is always a number, which may be hard to find even for the subset of redwood furniture. Finding the value of a redwood bed is NP-hard. Analysis of Hackenbush Hotchpotch -- which may involve all three colors -- using atomic weights. Brief partial survey of transpolynomial games. For the Exptime-completeness of chess, see an article by the reviewer and D. Lichtenstein [J. Combin. Theory Ser. A 31 (1981), 199 - 214; MR 83b:68044]. This also implies the Pspace-hardness of chess. Chapter 8: All small games, remote stars, computing atomic weights for analysing Hackenbush. Chapter 9: Analysis of the join (move in every component game) of partizan and impartial games, normal and misere play. The remoteness function. Chapter 10: Analysis of the union (move in any number of component games) of partizan games, normal play. (Smith's result for impartial unions is cited in Chapter 11.) Analysis of urgent unions (the game ends as soon as its first component does) of partizan games, normal and misere play. Chapter 11: Games with infinitely many positions but only finitely many moves: infinite ordinal numbers. Games which may not end: loopy partizan games [see also the reviewer and U. Tassa, Math. Proc. Cambridge Philos. Soc. 92 (1982), 193 - 204]. Loopy Hackenbush. Chapter 12: Loopy impartial games: to win need remoteness in addition to P, N labeling. Entailing move games such as the following: either split a stack of coins into two smaller ones, or remove the top coin from a stack. In the latter case, the opponent has to move in the same stack. Chapter 13: The subtle analysis of misere play. The notion of "genus" and how it helps to shed light on tame, restive and even some restless games via the Noah's Ark theorem. The remaining chapters 14 - 25 are grouped into Volume 2, entitled "Games in particular". Chapter 14: Games played by turning coins. Connection with Nim- multiplication. Chapter 15: Games played by moving coins on strips, such as silver dollar, Antonim, Synonim, Simonim, Welter (a form of Nim with unequal piles), Kotzig's Nim. Bounded Nim, Moore's Nim{sub}k, d-Nim. Chapter 16: Various suboptimal strategies for Dots-and-Boxes and a connection to Kayles and Dawson's Kayles. Dots-and-Boxes is NP-hard. Chapter 17: Games of joining two spots by a curve satisfying various conditions, such as Lucas' game (including misere play). Sprouts. Chapter 18: Analysis of Sylver Coinage (name an integer not the linear combination of previously named integers). See also Guy's research problem [Amer. Math. Monthly 83 (1976), 634 - 637]. The chapter also includes Chomp (arithmetic and geometric versions) and Zig-Zag. These (together with von Neumann's Hackenbush mentioned at the end of Chapter 17) are special cases of poset games. Chapter 19: Games played on a chessboard with a King and Go stones (Kinggo) or a duke and Go stones (Dukego). The Angel and the Square-Eater. Wolves-and-sheep and variations thereof. Chapter 20: Analysis of Fox and Geese: Four "geese" moving upwards on a checkerboard try to trap a "fox" who moves like a King in Checkers. (This game, played with tokens of two types on a digraph, is Pspace-hard.) Chapter 21: The French Military Game: A game of pursuit similar to Fox and Geese. Chapter 22: Tic-Tac-Toe and similar games. Go-Moku and the Hales - Jewett pairing strategy [A. W. Hales and R. I. Jewett, Trans. Amer. Math. Soc. 106 (1963), 222 - 229; MR 26 #1265]. Hex and the Shannon Switching game. Phutball. Chapter 23: Analysis of peg solitaire games. Beasley's proof that 18 moves are necessary for central peg solitaire. Variations of peg solitaire. Chapter 24: Puzzles with cubes, puzzles with wire and string, the Tower of Hanoi and ternary numbers, the 15 puzzle. Analysis of the Hungarian cube puzzle, tactics for solving other "Hungarian" puzzles. Examples of other puzzles: paradoxical pennies, paradoxical dice, magic squares. The chapter ends with some calendar-theoretic computations, including the dates of Easter and Rosh Hashanah. Chapter 25: The "game" of Life. The main result is a reduction of difficult mathematical problems such as Fermat's Last Theorem to the predictability problem of the final fate of an initial life pattern. This is done by computer simulation with appropriate life patterns. Each chapter ends with a section called "Extras", where underlying principles or additional details are given. Instead of formal proofs, short convincing arguments or examples are provided. This tends to increase considerably the amount of material packed in the 850 pages of the book. Together with the wit, humour and originality of approach, it also increases the readability or apparent readability. To really understand and prove everything in the book, not to mention to attempt solutions of the many questions inspired on every page of the book, will engage many people for many years. As the authors state, the book is not an encyclopedia, since there are many games, theories and puzzles not included in it. In fact, there are certain directions not pursued in the book, such as transpolynomiality of games or questions of undecidability or computability of strategies. The thrust of the book lies in the direction of formulating exact or suboptimal polynomial strategies for very broad classes of combinatorial games. It is likely to remain an eminent leader in this field for many years to come. Reviewed by Aviezri S. Fraenkel © Copyright American Mathematical Society 1991, 1997