2
$\begingroup$

We consider "games" in the sense of ONAG. Conway's definition of a game $G$ as a pair $G = \{L \mid R \}$ of sets of games, together with the definitions of inequality and the arithmetic operations (ONAG, p.78), may be taken directly as a decision procedure for equality at least in the case of short games (i.e., games with a finite number of positions). See, for example, this naive Haskell implementation. However, the naive decision procedure seems to be hopelessly inefficient for all but the simplest examples (e.g., my laptop and patience are too limited to decide 3*3=9). In particular, this definition of the arithmetic operations leads to very large normal forms for games.

So my question is: has anyone tried to develop efficient algorithms for doing arithmetic with Conway games and deciding (in)equality? For simplicity (and to avoid issues of undecidability), you can limit to the case of short games. In particular, I wonder whether it is possible to compute efficiently with "the simplest form of a short game" (p.111)?

$\endgroup$
1
  • $\begingroup$ Your choice of Haskell - a functional programming language is very interesting considering the recursive nature of Conway games. Nathan Siegel's CGSuite is written in Java. It was last updated in 2011. You may wish to build off his code or start your own. $\endgroup$ Dec 5, 2013 at 18:41

1 Answer 1

8
$\begingroup$

There are indeed (relatively) efficient algorithms to do this (computing canonical form in particular, deciding equality etc.) They are implemented in the CGSuite software package written by Aaron Siegel. They are also discussed at a relatively high level in Aaron's recent book, Combinatorial Game Theory.

$\endgroup$
4
  • $\begingroup$ This is great, thanks! I downloaded CGSuite, and will have a look at the book. $\endgroup$ Dec 5, 2013 at 20:06
  • $\begingroup$ I don't have a copy of the book yet, but I see that CGSuite fails evaluating multiplications like "{0|{0|0}} * {0|0}" ('No method "op *" for class CanonicalShortGame.'). Is the general case of arithmetic with short games still open (or known to be hard)? $\endgroup$ Dec 6, 2013 at 10:12
  • $\begingroup$ Am on the road, so don't have references handy, but just from memory there is no well-defined multiplication for games in general (the multiplication in On Numbers and Games works for an extended field of numbers, but not for all games). $\endgroup$ Dec 6, 2013 at 22:55
  • $\begingroup$ yes, I see now that Conway mentions this in "More Infinite Games" (library.msri.org/books/Book42/files/conway.pdf), though I'm curious as to why there is a valid definition of multiplication for Nimbers/impartial games. $\endgroup$ Dec 7, 2013 at 13:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.