Combinatorial Game Theory (Graduate Studies in Mathematics) (Graduate Studies in Mathematics, 146)

Combinatorial game theory is the study of two-player games with no hidden information and no chance elements. The theory assigns algebraic values to positions in such games and seeks to quantify the algebraic and combinatorial structure of their interactions. Its modern form was introduced thirty years ago, with the publication of the classic Winning Ways for Your Mathematical Plays by Berlekamp, Conway, and Guy, and interest has rapidly increased in recent decades. This book is a comprehensive and up-to-date introduction to the subject, tracing its development from first principles and examples through many of its most recent advances. Roughly half the book is devoted to a rigorous treatment of the classical theory; the remaining material is an in-depth presentation of topics that appear for the first time in textbook form, including the theory of misère quotients and Berlekamp's generalized temperature theory. Packed with hundreds of examples and exercises and meticulously cross-referenced, Combinatorial Game Theory will appeal equally to students, instructors, and research professionals. More than forty open problems and conjectures are mentioned in the text, highlighting the many mysteries that still remain in this young and exciting field. Aaron Siegel holds a Ph.D. in mathematics from the University of California, Berkeley and has held positions at the Mathematical Sciences Research Institute and the Institute for Advanced Study. He was a partner at Berkeley Quantitative, a technology-driven hedge fund, and is presently employed by Twitter, Inc. Readership: Graduate students and research mathematicians interested in combinatorial game theory. Cover Combinatorial Game Theory Copyright © 2013 by the American Mathematical Society ISBN 978-0-8218-5190-6 QA269.S5735 2013 519.3-dc23 2012043675 Dedicated To Elwyn Berlekamp Various systems of numbers and games. Contents Preface Chapter I Combinatorial Games 1. Introduction NiM Outcomes and Solutio DAWSON'S KAYLES HACKENBUSH DOMINEERING Games, Options, Rulesets The Fundamental Theorem Disjunctive Sum The Fundamental Equivalence Other Kinds of Values Exercises 2. HACKENBUSH: A Detailed Example Zero Positions Half a Point GREEN HACKENBUSH Tricolor HACKENBUSH Exercises 3. How to Read This Book Notation Standard References Other Resources 4. A Survey of the Landscape FOX AND GEESE Go CHESS ENTREPRENEURIAL CHESS Various Classes of Games What's a Solution? Games Farther Afield Exercises Notes Chapter II Short Games 1. The Group G Outcomes and Values G Is a Group Partial-Order Structure Some Simple Games Game Trees Birthday Incentives Exercises Notes 2. Canonical Form Dominated and Reversible Options Canonical Form Exercises Notes 3. Numbers The Simplicity Theorem Number Avoidance The Number Tree Confusion Intervals Number Avoidance, Revisited The Mean Value Theorem A Theorem on Incentives Exercises Notes 4. Infinitesimals Nimbers Up and Down The Sums Tiny and Miny Ordinal Sum Flowers Uptimals The Values Exercises Notes 5. Temperature Cooling Thermographs Rational Trajectories The Thermographic Calculus Properties of Cooling Hot, Cold, and Tepid Heating Temperature Can Be Misleading Overheating Thermal Dissociation Example: AMAZONS Exercises Notes 6. Reduced Canonical Form Infinitesimal Equivalence Inf-Dominated and Inf-Reversible Options Reduced Canonical Form The Analysis of SUBTRACTION(1, 3 1 213) Temper The Group G/Inf Transitive Games Exercises Notes 7. Atomic Weight Remote Stars Atomic Weight The Atomic Weight Calculus CLOBBER Exercises Notes Chapter III The Structure of G 1. Hereditary Structure Extrema G° and Gn/Inf Exercises Notes 2. Lattice Structure Join-Irreducible Elements of Gn Symmetries of Gn Exercises Notes 3. Group Structure Group Structure of Divisibility of G Group Structure of G Exercises Notes Chapter IV Impartial Games 1. Nim Values The Sprague-Grundy Theorem Exercises Notes 2. Heap Games Periodicity Finite Subtraction Games Octal Games Sparse Spaces Hexadecimal Games Exercises Notes 3. WYTHOFF The g-Values of WYTHOFF Exercises Notes 4. Generalized Sprague-Grundy Theory Formal Definitions Outcomes Loopy Nim Values Algebra of Loopy Nim Values Exercises Notes 5. Nim Arithmetic Exercises Notes Chapter V Misere Play 1. Misere NIM Simplification The Misere Mex Rule Misere Nim Value Notes 2. Genus Theory Strategies for Tame Sums Periodicity Some Notation Restive and Restless Games General Reversibility Extended Genus Exercises Notes 3. Misere Canonical Form The Mate of G The Simplest Form Theorem Games Born by Day 4 Exercises Notes 4. Misere Quotients Example: KAYLES Closure Tame Quotients Example: 0.75 Periodicity Exercises Notes 5. The Structure of Finite Misere Quotients Quotients of Small Order The Kernel and Normal Play The Mex Function Exercises Notes 6. Partizan Misere Canonical Form Ends and Adjoints Dominated and Reversible Options Misere Canonical Form Partizan Misere Quotients Exercises Notes Chapter VI Loopy Games 1. Coping with Cycles Formal Definitions Outcomes and Values Example: on + off = dud Strategies The Swivel Chair Exercises Notes 2. Stoppers Stoppers as Limits Sidling More Loopy Infinitesimals Atomic Weights of Stoppers Exercises Notes 3. Simplification of Stoppers Fusion Canonical Form Longer Cycles Exercises Notes 4. Sides Concentrating Strategies Plumtrees Bach's Carousel The Sidling Theorem Upsum and Downsum Exercises Notes 5. Idempotents Example: Varieties of t°n Properties of Degrees and Classes Varieties The Stability Conjecture Algebra of Varieties Exercises Notes Chapter VII Temperature Theory 1. Enriched Environments Negative Temperatures Exercises Notes 2. Orthodoxy Ambient Temperature A Naive Strategy: hotstrat A Refined Strategy: sentestrat Orthodox Accounting Exercises Notes 3. Generalized Temperature Toward a Temperature Theory Lt (G) and Rt(G) Some Examples A Refined Orthodoxy Cold Kos Simple Loopy Games Complex Loops 4. Generalized Thermography Thermographic Intersection Thermal Intensity The Thermographic Calculus Proof of the Thermographic Calculus Exercises Notes 5. Komaster Thermography Threat Environments The Komaster Calculus Generalized Orthodox Accounting Komonster Thermography Exercises Notes Chapter VIII Transfinite Games 1. The Group PG The Reals ... ... and the Surreals From Infinitesimal to Small Large Numbers and PG°° The Small Group Structure of PG Lattice Structure of PG Exercises has value on & 2. 2. Surreal Numbers Field Structure Sign Sequences The Number Tree Berlekamp's Sign-Expansion Rule Elements of M, Exercises Notes 3. The Structure of Surreal Numbers Surreal w-Powers Normal Form Algebra of Normal Forms Power Series Algebraic Properties of SN Exercises Notes 4. Transfinite Nim Arithmetic Nim Product and the Field ON2 The Algebraic Closure of P2 Nim Arithmetic in P Transcendental Extensions of PT Exercises Notes Appendix A Open Problems Chapter II Chapter III Chapter IV Chapter V Chapter VII Chapter VIII Appendix B Mathematical Prerequisites .1. Abelian Groups Finitely Generated Abelian Groups General Abelian Groups 2. Partial Orders Lattices Join-Irreducibles 3. Ordinals Successor and Limit Ordinals Ordinal Arithmetic Normal Form Natural Sum and Product 4. Commutative Semigroups Generators and Relations Finite Semigroups The Kernel Appendix C A Finite LoopfreeHistory Origins NIM and the Impartial Theory Richard Guy The 1950s John Conway Elwyn Berlekamp Winning Ways Toward Publication Aviezri Fraenkel Mathematical Go Games Past and Future Notes Bibliography Glossary of Notation Author Index Index of Games Index Back Cover © 2014 MicrosoftTermsPrivacyDevelopersEnglish (United States) It is wonderful to see advanced combinatorial game theory made accessible. Siegel's expertise and enjoyable writing style make this book a perfect resource for anyone wanting to learn the latest developments and open problems in the field. —Erik Demaine, MIT Aaron Siegel has been the major contributor to Combinatorial Game Theory over the last decade or so. Now, in this authoritative work, he has made the latest results in the theory accessible, so that the subject will achieve the place in mathematics that it deserves. —Richard Guy, University of Calgary Combinatorial game theory is the study of two-player games with no hidden information and no chance elements. The theory assigns algebraic values to positions in such games and seeks to quantify the algebraic and combinatorial structure of their interactions. Its modern form was introduced thirty years ago, with the publication of the classic Winning Ways for Your Mathematical Plays by Berlekamp, Conway, and Guy, and interest has rapidly increased in recent decades. This book is a comprehensive and up-to-date introduction to the subject, tracing its development from first principles and examples through many of its most recent advances. Roughly half the book is devoted to a rigorous treatment of the classical theory; the remaining material is an in-depth presentation of topics that appear for the first time in textbook form, including the theory of misère quotients and Berlekamp's generalized temperature theory. Packed with hundreds of examples and exercises and meticulously cross-referenced, Combinatorial Game Theory will appeal equally to students, instructors, and research professionals. More than forty open problems and conjectures are mentioned in the text, highlighting the many mysteries that still remain in this young and exciting field. Aaron Siegel holds a Ph.D. in mathematics from the University of California, Berkeley and has held positions at the Mathematical Sciences Research Institute and the Institute for Advanced Study. He was a partner at Berkeley Quantitative, a technology-driven hedge fund, and is presently employed by Twitter, Inc. Machine Generated Contents Note: 1. Introduction -- 2. Hackenbush: A Detailed Example -- 3. How To Read This Book -- 4. A Survey Of The Landscape -- 1. The Group G -- 2. Canonical Form -- 3. Numbers -- 4. Infinitesimals -- 5. Temperature -- 6. Reduced Canonical Form -- 7. Atomic Weight -- 1. Hereditary Structure -- 2. Lattice Structure -- 3. Group Structure -- 1. Nim Values -- 2. Heap Games -- 3. Wythoff -- 4. Generalized Sprague-grundy Theory -- 5. Nim Arithmetic -- 1. Misere Nim -- 2. Genus Theory -- 3. Misere Canonical Form -- 4. Misere Quotients -- 5. The Structure Of Finite Misere Quotients -- 6. Partizan Misere Canonical Form -- 1. Coping With Cycles -- 2. Stoppers -- 3. Simplification Of Stoppers -- 4. Sides -- 5. Idempotents -- 1. Enriched Environments -- 2. Orthodoxy -- 3. Generalized Temperature -- 4. Generalized Thermography -- 5. Komaster Thermography -- 1. The Group Pg -- 2. Surreal Numbers -- 3. The Structure Of Surreal Numbers -- 4. Transfinite Nim Arithmetic -- 1. Abelian Groups -- 2. Partial Orders -- 3. Ordinals -- 4. Commutative Semigroups. Aaron N. Siegel. Includes Bibliographical References (pages 493-504) And Indexes. David Eppstein offers a collection of Internet resources about combinatorial game theory, which studies strategies and mathematics of two-player games of perfect knowledge. Topics include basic research, bibliographies, binary games, puzzles, FAQs, mathematical games, and more