Misere quotients for impartial games

December 4, 2006 at 11:45 pm (abstracts, algebra, math, papers, software)

Elwyn Berlekamp suggested that the title of my recent paper with Aaron Siegel, The Phi-values of various games, be changed:

I urge you to change the title. I think you have a good chance to make an impact well beyond the small circle of experts such as those who come to conferences like the one in Banff. There are many more mathematicians and algebraists out there, as well as a big computer Go community. Terms like “Phi-function” are unlikely to become buzzwords that stick, as there are many Phi functions defined by many different authors. “Misere Quotient” might well be a unique pair of words. It could quite plausibly become buzzword that would help stir up more interest in combinatorial games in general. So I think it important that your title include that pair of words.  I’d propose a short title such as “Misere Quotients for Impartial Games”.

It’s hard to argue with that, and it’s still a preprint. So Misere Quotients for Impartial Games it is!

Permalink Leave a Comment

The Phi-values of various games

October 2, 2006 at 3:29 am (papers, software)

Just in time for Richard K. Guy’s 90th birthday a few days ago (30 September 2006), Aaron Siegel and I finished our paper The Phi-values of various games.

It just appeared on the arXiv.  Check it out!

Permalink 1 Comment


July 19, 2005 at 1:24 am (software, solutions)

Aaron Siegel has already whipped together an amazing Java program for everything in my misere CGT paper, while also incorporating his own insights into algorithms for misere quotient semigroup computation. Given an octal game code as input, his program directly computes a presentation of its misere quotient semigroup to heap size n=1, 2, 3, in turn, together with the associated pretending functions and outcome partitions at each heap size n. He’s solved .15 (Guiles), .115, .114, and a bunch of wild quaternary games using this software.

Eventually his software will make into cgsuite, I hope.

Permalink Leave a Comment

Allemang’s thesis

August 3, 2004 at 2:25 am (papers, software)

Machine Computation with Finite Games

In 1984, Dean Allemang wrote an M.Sc. thesis at Cambridge University that is today [January 2003] still an excellent resource for results 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 cajoling Dean into sending me a photocopy, I scanned it in and converted it to PDF.

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…”.

Permalink 1 Comment