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)?

Improve this question
$\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$
    – john mangual
    Commented Dec 5, 2013 at 18:41

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ This is great, thanks! I downloaded CGSuite, and will have a look at the book. $\endgroup$
    – Noam Zeilberger
    Commented 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$
    – Noam Zeilberger
    Commented 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$
    – Michael Albert
    Commented 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$
    – Noam Zeilberger
    Commented Dec 7, 2013 at 13:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .