cgt intro, nim

hist   nim  

cgt history

  • Bouton nim analysis

  • Conway

  • Berlekamp, Conway, RK Guy

  • Go endgames

  • ugrad

    • Lessons in Play

    • Intro to CGT

  • grad

    • Aaron

game space

  • state space tree or dag

    • nodes: states (position, player-to-move)

    • edges: moves

  • winning node: has a transition to opponent-losing node

  • losing node: every transition is to opponent-winning node

  • impartial game, partisan game

  • in impartial game, nodes are winning (for ptm) or losing (for ptm)


  • rules

  • nim(a, b, c, …)

  • nim(a)     1-pile     who wins?

  • nim(a, b)     2-piles     who wins?

  • nim(a, b, c)     3-piles     who wins?

  • general nim formula

    • proof of correctness

  • misere nim

    • who wins


  • ugrads and grads

    • weekly homework 0 marks (not marked)

    • weekly in-class homework quizzes 40 marks

    • 3-hour final exam 40 marks

    • class project, broken into bi-weekly assignments 20 marks (grads 40 marks)

  • grads also give a final project presentation 10 marks

  • final grade

    • ugrad (grad) score divided by 100 (130)

    • breakpoints historically close to 95 90 … 45 for A+ A ... D, but this year's breakpoints might differ

texts etc

An Introduction to Combinatorial Game Theory by L R Haff and W J Garner     (ugrad level)

  • order from (not amazon) to get the most recent edition

  • Len Haff is an emeritus professor of mathematics at UC San Diego. He is also an enthusiastic Go player who became interested in Combinatorial Game Theory long ago. He's been teaching a course on combinatorial game theory for many years. Will Garner is his former student, who joined him in teaching CGT for several years. Like Lessons in Play, by Albert, Nowakowski, and Wolfe, An Introduction to Combinatorial Game Theory by Haff & Garner is a textbook for an undergraduate course. It addresses the transition from lower division (freshman & sophomore) collegiate mathematics to upper division, with increased emphasis on rigorous proofs. I think everyone who teaches an undergraduate course on CGT should take a close look at it. – Elwyn Berlekamp

Lessons in Play by M Albert, R Nowakowski, D Wolfe     (ugrad level)

  • text website, with errata

  • Combinatorial games are games of pure strategy involving two players, with perfect information and no element of chance. Starting from the very basics of gameplay and strategy, the authors cover a wide range of topics, from game algebra to special classes of games. Classic techniques are introduced and applied in novel ways to analyze both old and new games, several appearing for the first time in this book.

Game Theory: A Playful Introduction by Matt Devos and Deborah A Kent     (ugrad level)

  • text website, with errata

  • This book offers a gentle introduction to the mathematics of both sides of game theory: combinatorial and classical. The combination allows for a dynamic and rich tour of the subject united by a common theme of strategic reasoning. The first four chapters develop combinatorial game theory, beginning with an introduction to game trees and mathematical induction, then investigating the games of Nim and Hackenbush. The analysis of these games concludes with the cornerstones of the Sprague-Grundy Theorem and the Simplicity Principle. The last eight chapters of the book offer a scenic journey through the mathematical highlights of classical game theory. This contains a thorough treatment of zero-sum games and the von Neumann Minimax Theorem, as well as a student-friendly development and proof of the Nash Equilibrium Theorem. The Folk Theorem, Arrow's voting paradox, evolutionary biology, cake cutting, and other engaging auxiliary topics also appear. The book is designed as a textbook for an undergraduate mathematics class. With ample material and limited dependencies between the chapters, the book is adaptable to a variety of situations and a range of audiences. Instructors, students, and independent readers alike will appreciate the flexibility in content choices as well as the generous sets of exercises at various levels.

Combinatorial Game Theory by Aaron N Siegel     (expert level)

  • text website

  • For those wishing to know about combinatorial games in depth this is the book to read. … Aaron Siegel is currently the strongest researcher in the field and has been involved with many of the central developments. In this book, he has brought them together. Moreover, he includes asides and details that explain how and why certain directions were taken; important insights from an expert. … He has kept the tone of the book light and infused it with history, anecdotes, and important observations making it an entertaining as well as an educational read. – Richard Nowakowski, MAA Reviews

slides by A Kumar and M K Bera

intro from sensei's library