Mathematical Sciences Research Institute

Home » Overview of Combinatorial Game Theory


Overview of Combinatorial Game Theory April 25, 2013 (02:00 PM PDT - 03:00 PM PDT)
Parent Program: --
Location: MSRI: Simons Auditorium
Speaker(s) Elwyn Berlekamp
Description No Description
No Video Uploaded

This talk will present an overview of the Theory of Combinatorial Games (CG)

In 1901, a Harvard math professor named Bouton published his mathematical solution to the then-popular barroom game called Nim.
This marked the birth of a subject call combinatorial game theory, which seeks to determine optimal strategies for positions in board games. The theory has been most successful for games whose positions tend to breakup into disjoint regions, which are treated as sums.
Examples of such games include classics such as Go, Dots-and-Boxes, Fox-and-Geese, and Konane (also known as Hawaiian checkers), as well as more modern games such as Domineering, Hackenbush, Amazons, and Clobber.
Combinatorial Game Theory yields insights into endgame positions in all of these games, as well as a few special positions in chess and Anglo-American checkers.

The mathematical emphasis of the theory is on a partial order and the behavior of equivalence classes of combinatorial game positions under the operation of addition. This enables CG to be treated as a large commutative monoid, which contains some well-known groups. The dyadic rationals appear immediately, and provide numerical bounds on all other CG. Among the most interesting CG are the infinitesimals. One common class of infinitesimals is the nimbers, a countably infinite group in which every element has order two. There is also a first order of infinitesimals, and many higher orders, none of which can be viewed as the "second" order. By allowing games with infinitely many positions while imposing other severe restrictions, one obtains Conway\'s elegant constructions of the real, transfinite, and surreal numbers.

The set of finite CG also naturally contains several idempotents with useful properties. And more: There are some powerful theorems which can be viewed as properties of other "contrived" idempotents.

This talk will explain some of these results. No prior background is assumed.

No Notes/Supplements Uploaded No Video Files Uploaded