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)