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.
Author(s): Aaron N. Siegel
Series: Graduate Studies in Mathematics, Vol. 146
Publisher: American Mathematical Society
Year: 2013
Language: English
Pages: C+xiv+523+B
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)
