Combinatorial games procedures for Maple

Introduction

This page describes combgame, a set of procedures for working with finite combinatorial game theory in the mathematical software package Maple. These procedures have been tested in Maple V Release 4 and Maple 8. To read them from within Maple use the read statement.

combgame was inspired by David Wolfe's Gamesman's Toolkit, a toolkit written in C under Unix with a similar purpose. The current predominant combinatorial games toolkit is Aaron Siegel's cgsuite. I highly recommend these programs: indeed, mine is quite inefficient compared to them.

Contents

A game with left and right option sets l and r is represented by game(l,r). game is not defined as a function and does not evaluate.

The following is a list of the functions of the procedures. Some of these procedures (for instance cool2) were designed for internal use.

• zero: the game 0 = {|} (represented as game({},{}) )
• one: the game 1 = {0|} (represented game({game({},{})},{}) )
• two: the game 2 = {1|} (etc.)
• three: the game 3 = {2|}
• onehalf: the game 1/2 = {0|1}
• negone: the game -1 = {|0}
• negtwo: the game -2 = {|-1}
• star: the game * = {0|0}
• up: the game ^ = {0|*}
• upstar: the game ^* = {0,*|0}
• down: the game v = {*|0}
• downstar: the game v* = {0|0,*}
• leftoptions(g): the left options of g
• rightoptions(g): the right options of g
• ge(x,y): is x >= y?
• le(x,y): is x <= y?
• greater(x,y): is x > y?
• less(x,y): is x < y?
• equal(x,y): is x = y? (for x and y in canonical form x = y will serve the same purpose)
• confused(x,y): is x || y?
• compare(x,y): `=`, `<`, `>`, or `||` according as x = y, x < y, x > y, or x || y
• isnum(g): is the game g a number?
• nextleftsnum(n): the greater of the children of n in the tree of numbers, as on On Numbers and Games page 11
• numvalue(g): the value of the game g as a number
• deletedominated(g): the game resulting from deleting g's dominated options
• bypassreversible(g): the game resulting from bypassing reversible moves in g
• gsimp(g): g simplified to its canonical form
• neg(g): the negative of g
• plus(g,h): g plus h
• gminus(g,h): g minus h
• inttimes(g,n): the game g multiplied by the integer n
• isimpartial(g): is g impartial?
• leftstop(g): the left stop of g
• rightstop(g): the right stop of g
• numtogame(n): the game corresponding to the dyadic rational n
• cool(g,t): g cooled by t
• cool2(g,t): g 'overcooled' by t, that is, g cooled by t without the prohibition on cooling numbers further
• temperature(g): the temperature of g
• gfreeze(g): g cooled by its temperature
• meanvalue(g): the mean value of g
• heat(g,t): g heated by t
• overheat(g,s,t): g overheated by t starting from s
• leftincentives(g): the left incentives of g
• rightincentives(g): the right incentives of g
• nortonmult(g,u): Simon Norton's product of g with u
• nimber(n): the game *n (the nth nimber), for n a non-negative integer
• maxlength(g): the maximum number of moves that can be made in g
• farstar(g): a remote star for g (not necessarily the first one possible)
• isallsmall(g): is g all small?
• atomicweight(g): the atomic weight of g
• ordinalsum(g,h): the ordinal sum g:h
• nimadd1(n): the nim-sum of the integer n and 1
• upsstars(g): an ordered pair [a,b] such that g = a.^ + *b, or FAIL if no such pair exists
• commaop(s): the elements of set s, comma-delimited
• gprint(g): g displayed in a standard-like format
• gprint2(g): as gprint, but with less simplification
• gprint3(g): a kluged version of gprint so that * doesn't evaluate to a procedure, for use inside Maple's print
• gprintopts(g): g displayed as its sets of left and right options with braces and slash

The output format

Games that are numbers are displayed as Maple displays numbers of its internal numeric type. Infinitesimal games that are sums of ups and stars are recognized and displayed as such. ^ denotes up, v down, and a following number is a multiplier (which is omitted if one). Nimbers are represented as *n, where n is omitted if one. When these notations and numbers are catenated, a sum is intended.
For other games the standard notation with braces and slash is used. Multiple slashes are not currently supported.

A sample game using this package

The file toadsandfrogs contains the procedure toadsandfrogs, which evaluates positions in the game Toads-and-Frogs (described in Chapter 1 of Winning Ways). A Toads-and-Frogs position is represented as an ordered list (between square brackets) using 'F' or 'f' for a frog, 'T' or 't' for a toad, and anything else for a space.

Limitations

Due to properties of Maple's concatenation operator, gprint handles games like 1/2|0 poorly. gprint3 is a kluge to make * not evaluate to multiplication, and there are probably assorted other oddities related to the display procedures that I have not found. Many of these could probably be remedied by the use of strings, but the current version avoids strings for compatibility with Maple V release 4.

Changes

3 February 2003: leftoptions, rightoptions, and gsimp make sure that their arguments are games and print an appropriate error message otherwise. Toads-and-Frogs was added.