Machine Computation with Finite Games


Machine Computation with Finite Games

In 1984, Dean Allemang wrote an M.Sc. thesis at Cambridge University on misère octal games. The title of his thesis is Machine Computation with Finite Games.

In many cases the contents of Allemang's thesis go beyond what is contained in Chapter 13 of the 1985 (third printing) of Winning Ways ("the last and most complicated theory in this book," according to the authors, Berlekamp, Conway, and Guy).

The original electronic version of Allemang's thesis has been lost. After I (Thane Plambeck) cajoled Dean into sending me a photocopy, I scanned it in and converted it into PDF. Some typographical errors were introduced by the scanning and conversion, but it's mostly still readable.

I've split the document into two parts. Here's a rough outline of the contents.

Part I [PDF, 48 pages, 2.56 MB]
Declaration by Author
Misère Play of Impartial games
Normal play
Misère play
Conway's Cancellation
The Genus Sequence Algorithm
Grundy's Game
Other Games
The octal game .17
Errors in Winning Ways
A Bigger Genus Sequence
The Generalized Genus Statement
Periodicity in Genus Sequences
An Algorithm for Generalized Genera
Errors in Winning Ways
The Game of Knots Ties Up all Genus Sequences
Which sequences arise as genus sequences?
Part II [PDF, 33 pages, 15.2 MB]
Complete Analysis for Misère Games
A Catalogue of Octal Games
Appendix III: "An implementation of many of the computations necessary for the analysis of normal partizan games, as treated in Conway, On Numbers and Games...".
[Back to]
These pages were last modified by Thane Plambeck
Last updated Tue 15 May 2007, 8:43pm Pacific