Lessons in Play Lessons in Play An Introduction to Combinatorial Game Theory Michael H. Nowakowski David Wolfe A K Peters, Ltd. Wellesley, Massachusetts CRC Press Taylor & Francis Group 6000 Broken Sound Parkway NW, Suite 300 Boca Raton, FL 33487-2742 © 2007 by Taylor & Francis Group, LLC CRC Press is an imprint of Taylor & Francis Group, an Informa business No claim to original U. Government works Version Date: 20110714 International Standard Book Number-13: 978-1-4398-6437-1 (eBook - PDF) This book contains information obtained from authentic and highly regarded sources.
Reason- able efforts have been made to publish reliable data and information, but the author and publisher cannot assume responsibility for the validity of all materials or the consequences of their use. The authors and publishers have attempted to trace the copyright holders of all material reproduced in this publication and apologize to copyright holders if permission to publish in this form has not been obtained. If any copyright material has not been acknowledged please write and let us know so we may rectify in any future reprint. Except as permitted under U.
Copyright Law, no part of this book may be reprinted, reproduced, transmitted, or utilized in any form by any electronic, mechanical, or other means, now known or hereafter invented, including photocopying, microfilming, and recording, or in any information storage or retrieval system, without written permission from the publishers. For permission to photocopy or use material electronically from this work, please access www.com (http://www.com/) or contact the Copyright Clearance Center, Inc. (CCC), 222 Rosewood Drive, Danvers, MA 01923, 978-750-8400. CCC is a not-for-profit organiza- tion that provides licenses and registration for a variety of users.
For organizations that have been granted a photocopy license by the CCC, a separate system of payment has been arranged. Trademark Notice: Product or corporate names may be trademarks or registered trademarks, and are used only for identification and explanation without intent to infringe. Visit the Taylor & Francis Web site at http://www.com and the CRC Press Web site at http://www.com To Richard K. Guy, a gentleman and a mathematician Contents Preface xi 0 Combinatorial Games 1 0.1 Basic Terminology 3 Problems 7 1 Basic Techniques 11 1.3 Change the Game! 16 1.5 Give Them Enough Rope! 17 1.7 Case Study: Long Chains in Dots & Boxes 21 Problems 29 2 Outcome Classes 35 2.1 Game Positions and Options 36 2.2 Impartial Games: Minding Your Ps and N s 41 2.3 Case Study: Partizan Endnim 43 Problems 47 3 Motivational Interlude: Sums of Games 51 3.3 Equality and Identity 57 3.4 Case Study: Domineering Rectangles 59 Problems 62 vii viii Contents 4 The Algebra of Games 65 4.1 The Fundamental Definitions 65 4.2 Games Form a Group with a Partial Order 74 4.4 Incentives 83 Problems 83 5 Values of Games 87 5.2 A Few All-Smalls: Up, Down, and Star 100 5.4 Tiny and Miny 108 5.5 Case Study: Toppling Dominoes 110 Problems 112 6 Structure 117 6.1 Games Born by Day 2 117 6.2 Extremal Games Born By Day n 119 6.4 More About Numbers 125 6.5 The Distributive Lattice of Games Born by Day n 127 6.6 Group Structure 130 Problems 130 7 Impartial Games 135 7.1 A Star-Studded Game 136 7.2 The Analysis of Nim 138 7.4 A More Succinct Notation 142 7.5 Taking-and-Breaking Games 144 7.6 Subtraction Games 145 Problems 155 8 Hot Games 159 8.1 Comparing Games and Numbers 160 8.2 Coping with Confusion 163 8.3 Cooling Things Down 166 8.4 Strategies for Playing Hot Games 173 8.5 Norton Products 175 Problems 180 Contents ix 9 All-Small Games 185 9.1 Cast of Characters 185 9.2 Motivation: The Scale of Ups 193 9.5 All-Small Shove 201 9.6 More Toppling Dominoes 202 9.7 Clobber 203 Problems 207 ω Further Directions 211 ω.2 Algorithms and Complexity 212 ω.4 Kos: Repeated Local Positions 214 ω.5 Top-Down Thermography 214 ω.8 Misère Play 215 ω.9 Dynamical Systems 216 A Top-Down Induction 219 A.1 Top-Down Induction 219 A.3 Why is Top-Down Induction Better? 224 A.4 Strengthening the Induction Hypothesis 226 A.5 Inductive Reasoning 227 Problems 228 B CGSuite 231 B.3 Programming in CGSuite’s Language 235 B.4 Inserting a Newline in CGSuite 237 B.5 Programming in Java for CGSuite 237 C Solutions to Exercises 239 D Rulesets 263 Bibliography 277 Index 281 Preface It should be noted that children’s games are not merely games.
One should regard them as their most serious activities. Michel Eyquem de Montaigne Herein we study games of pure strategy, in which there are only two players1 who alternate moves, without using dice, cards or other random devices and where the players have perfect information about the current state of the game. Familiar games of this type include: tic tac toe, dots & boxes, checkers and chess. Obviously, card games such as gin rummy, and dice games such as backgammon are not of this type.
The game of battleship has alternate play, and no chance elements, but fails to include perfect information — in fact that’s rather the point of battleship. The games we study have been dubbed combinatorial games to distinguish them from the games usually found under the heading of game theory, which are games that arise in economics and biology. For most of history, the mathematical study of games consisted largely of separate analyses of extremely simple games. This was true up until the 1930s when the Sprague-Grundy theory provided the beginnings of a mathematical foundation for a more general study of games.
In the 1970s, the twin tomes On Numbers and Games by Conway and Winning Ways by Berlekamp, Conway, and Guy established and publicized a complete and deep theory, which can be deployed to analyze countless games. One cornerstone of the theory is the notion of a disjunctive sum of games, introduced by John Conway for normal- play games. This scheme is particularly useful for games that split naturally into components. On Numbers and Games describes these mathematical ideas at a sophisticated level.
Winning Ways develops these ideas, and many more, through playing games with the aid of many a pun and witticism. Both books 1 In 1972, Conway’s first words to one of the authors, who was an undergraduate at the time, was “What’s 1 + 1 + 1?” alluding to three-player games. This question has still not been satisfactorily answered. xi xii Preface have a tremendous number of ideas and we acknowledge our debt to the books and to the authors for their kind words and teachings throughout our careers.
The aim of our book is less grand in scale than either of the two tomes. We aim to provide a guide to the evaluation scheme for normal-play, two-player, finite games. The guide has two threads, the theory and the applications. The theory is accessible to any student who has a smattering of general algebra and discrete math.
Generally, a third year college student, but any good high school student should be able to follow the development with a little help. We have attempted to be as complete as possible, though some proofs in Chapters 8 and 9 have been omitted, because the theory is more complex or is still in the process of being developed. Indeed, in the last few months of writing, Conway prevailed on us to change some notation for a class of all-small games. This uptimal notation turned out to be very useful and it makes its debut in this book.
We have liberally laced the theory with examples of actual games, exercises and problems. One way to understand a game is to have someone explain it to you; a better way is to muse while pushing some pieces around; and the best way is to play it against an opponent. Completely solving a game is generally hard, so we often present solutions to only some of the positions that occur within a game. The authors invented more games than they solved during the writing of this book.
While many found their way into the book, most of these games never made it to the rulesets found at the end. A challenge for you, the reader of our missive, and as a test of your understanding, is to create and solve your own games as you progress through the chapters. Since the first appearance of On Numbers and Games and Winning Ways there have been several conferences specifically on combinatorial games. The subject has moved forward and we present some of these developments.
How- ever, the interested reader will need to read further afield to find the theories of loopy games, misère-play games, other (non-disjunctive) sums of games, and the computer science approach to games. The proceedings of these conferences [Guy91, Now96, Now02, FN04] would be good places to start. Organization of the Book The main idea of this part of the theory of combinatorial games is the assigning of values to games, values that can be used to replace the actual games when deciding who wins and what the winning strategies might be. Each chapter has a prelude which includes problems for the student to use as a warm-up for the mathematics to be found in the following chapter.
The prelude also contains guidance to the instructor for how one can wisely deviate from the material covered in the chapter. Preface xiii Exercises are sprinkled throughout each chapter. These are intended to reinforce, and check the understanding of, the preceding material. Ideally then, a student should try every exercise as it is encountered.
However, there should be no shame associated with consulting the solutions to the exercises found at the back of the book if one or more of them should prove to be intractable. If that still fails to clear matters up satisfactorily, then it may be time to consult a games guru. Chapter 0 introduces basic definitions and loosely defines that portion of game theory which we will address in the book. Chapter 1 covers some general strategies for playing or analyzing games and is recommended for those who have not played many games.
Others can safely skim the chapter and review sections on an as-needed basis while reading the body of the work. Chapters 2, 4, and 5 contain the core of the general mathematical theory. Chapter 2 in- troduces the first main goal of the theory, that being to determine a game’s outcome class or who should win from any position. Curiously, a great deal of the structure of some games can be understood solely by looking at outcome classes.
Chapter 3 motivates the direction the theory takes next. Chapters 4, 5, and 6 then develop this theory (i., assigning values and the consequences of these values.) Chapters 7, 8, and 9 look at specific parts of the universe of combinatorial games and as a result, these are a little more challenging but also more concrete since they are tied more closely to actual games. Chapter 7 takes an in-depth look at impartial games. The study of these games pre-dates the full theory.
We place them in the new context and show some of the new classes of games under present study. Chapter 8 addresses hot games, games such as go and amazons in which there is a great incentive to move first. There is much research in this area and we can only give an introduction to this material. Chapter 9 looks at the analysis of all-small games.
Most of the research emphasis has been on impartial and hot games. Only recently have there been developments in this area and we present the original and latest results in light of all the new developments in combinatorial game theory. Chapter ω is a brief listing of other areas of active research that we could not fit into an introductory text. In Appendix A, we present top-down induction, an approach that we use often in the text.