Combinatoric Game Theory references:

Winning Ways, Elwyn R. Berlekamp and John H. Conway and Richard K.
Guy, Academic Press, New York, 1982.

Blockbusting and Domineering, Elwyn R. Berlekamp, Journal of
Combinatorial Theory, 1988, Vol 49, No 1, Series A, September 1988.

On Numbers and Games, John H. Conway, Academic Press, London/New York, 1976.

Mathematical Go: Chilling Gets the Last Point, Elwyn Berlekamp and David
Wolfe, AKPeters, Ltd, 239 Linden Street, Wellesley, MA 02181, 1994.

Mathematical Go Endgames: Nightmares for the Professional Go Player,
(paperback version of Mathematical Go) Elwyn Berlekamp and David Wolfe,
Ishi Press International, 76 Bonaventura Drive, San Jose, CA 95134 OR
17 St. Martin's St, Wallingford, OXON, OX10 0EA, UK.

In the game of Clobber (due to Michael Albert, JP Grossman and Richard
Nowakowski) is played on a grid filled with black (x) and white (o)
pieces.  A move consists of moving one of your pieces onto an adjacent
square that contains an enemy piece which is then removed.

The input format is just like in domineering, but use X or x for black
pieces, and O or o for white pieces.  For example,

> clobber
Enter `clobber' position, then hit  twice.
xxxxx
ooooo

^2*|^,^*||v*,v|v2*

Domineering is a game played by two players, vertical (left) and
horizontal (right).  From a position, which is a grid of squares (such
as a checkerboard), left plays dominos vertically, covering up two
squares, removing them from play.  Right can play horizontally.  A
player who cannot play loses.

To evaluate a domineering position, type in a character other than
SPACE to represent each square.  End the input by hitting 
twice.  For example:

> domino
xxx
  x
  x

should return "0", since it's a win for the second player.  And

> domino
x
x
xx

should return "1/2".

To calculate the winner only of large positions, first type, say

> domino limit 24

This means, "Please use game theory on positions smaller than 24, and
use alpha-beta pruning on larger positions."  When evaluating a large
position, choice of this parameter will affect performance, since game
theory is employed to upper and lower bound positions.  This often
succeeds in pruning the search further.  "domino limit" turns this
feature off.

> domino length 3

This means dominos are 3x1 instead of 2x1.  Typing "domino length all"
says that each player can play any length of domino >=1.  This game is
all-small.  Typing "domino impartial" allows either player can play
vertical OR horizontal dominos.

Lastly, you can type
> play domino

After you've entered a domineering position, the computer will make a
move.  The board position after the move gets returned.  Very little
strategy yet:
	If there is a winning move, return one such move.
	If not, make the upper-left move.
	If there is no legal move, print nothing.

If you wish to always apply the same operator to every game before it
is printed.  For example, suppose that rather than outputing the game,
you'd prefer to always output game cooled by 1.  In this case, 
the command "map" followed by the function to apply to any game, g.

> map g[1]      % Turn on the feature, and always output g[1] (g cooled by 1)
> 1|* 
1/2             % 1|* cooled by 1 is 1/2
> map g         % Turn the feature back off (always output g unaltered)
> 1|*
1|*

One common mapping function is g[e], which is the simplest game
infinitesimally close to g.
________________________________________________________________

Sometimes (especially in one-point Go endgames) there's an invertable
operator which maps a game to simpler games.  In Go, the operator is
cooling by one point.  The inverse is given by a Norton multiply by 1*
(or, identically, overheating from 1* to 1).  If you suspect there's
such an operator for a game you're testing, then this is useful.

The way it's used is best described by example:

(1) type in "evaluate", turning on this feature:
> evaluate
(2) specify a chill function (this one happens to be the default):
> chill g[1]
(3) specify a warming function (for example, g.1*):
> warm g.1*

Now, if you type
> 2||1|*
The computer replies
1%1/4

The computer chilled 2||1|* and found that it evaluates to 5/4.  It
then tried warming back up the non-integer part (1/4), and found that
1 plus warmed 1/4 happend to equal the original game.  So, that's the
form the program outputed:  1%1/4 (the % represents your warming
function.)

Were you to type
> 1|0
the computer would have replied
1|0

since chilling 1|0 and warming it back up gives 1|*, which is not
identical to 1|0.

Summary:
evaluate                tries to chill and warm back up
chill g[1]              set chilling function --- g[1] is the default
warm g.1*               set warming function --- g.1* is the default

Help
help books	References on combinatorial game theory
help todo	Recent changes and proposed changes

help new	Find out how to code your own new game
help domino	The game Domineering
help konane	The Hawaiian game Konane
help toads	The game Toads & Frogs
help subtract	Partisan subtraction games
help clobber	The game of Clobber

help lattice	A few distributive lattice operations
help ons	Definitions of a few new games which generalize up-on
help eval	Apply a transormation to a game before outputing its value
Ancient and modern versions of the Hawaiian game of Konane are supported.


The rules of Modern Konane are:

  The game of Konane was played on a board with a rectangular grid of
  indentations in which to place the players' pieces.  ...  A marker is put
  in each indentation, with black and white markers alternating.  The first
  player removes a marker from one of the center spots or a corner; the other
  player removes an adjacent marker.  The color removed by each player
  determines which color that player plays with throughout the game.  On
  subsequent moves a player with his or her markers may jump and adjacent
  marker of the opponent, and remove the jumped piece.  If a player cannot
  jump an opponent's marker the player loses.
  [Walter S. Sizer, "Mathematical notions in preliterate societies",
  Mathematical Intelligencer, V13 #4, Fall 1991]

Ancient Konane permits multiple jumps to be made by a player, so long as
the jumps are in the same direction; jump as many stones as you like, but
don't turn the corner.

Use following commands to evaluate Konane positions:
akonane   evaluate Ancient Konane position
mkonane   evaluate Modern Konane position
konane    evaluate Konane position of the default type
ancient   make the default Konane position ancient
modern    make the default Konane position modern

When inputting a Konane position, any character other than SPACE is a
marker (but see below regarding |, -, and +).  Black and white markers
are distinguished only from their position.  The upper left-hand
position is a black square, and colors alternate in a checkerboard
fashion.  Input is terminated by an extra .

For example,
> konane
X
O
 OXO

returns 1/2.

The position could also be inputted:

> konane
x
x
 xxx

To specify board edges, use the characters
   -   for top or bottom edge)
   |   for left or right edge, or
   +   to simultaneously indicate two edges.
One or more of these characters should appear in the first or last row or
column; don't use them anywhere else, and don't leave an extra blank row or
column before the one with the edge characters.

For instance, here are three ways of specifying the same position:

> konane            > konane            > konane
+---		       -                +
|...		     abc                 xox
|..		    |de                  ox
|.		     f                   x


Three operations are implemented to describe the lattice of games born
on day n.  First, indicate which lattice you'd like to perform the
operations over by typing, say,

today = 2

g meet h
g join h
g -> h          (The pseudocomplement operation of a Heyting algebra,
                i.e., return the minimum x s.t. g meet x <= h )

For example,
^ meet ^*       -> 1/2

To implement a new game, I recommend looking at how domineering is
implemented.  To input a domineering position, you type just input the
command "domino" followed by a , and then input the position.

OK, back to the code.  You'll need to edit the following files:

parse.l:  Add a command which runs your game; for example,
newgame						{return NEWGAME;}

grammar.y:  Add the token representing the command; for example,
%token NEWGAME

Then add the command line; for example, under the expansion for line:
	| NEWGAME		{parser_output = newgame();}

Later, you'll implement a function newgame() which inputs a game
position and then returns the game evaluated.

externs.h:  Add a KEY, for example,
#define NEWGAME_KEY		(24 | EXPENDABLE_KEYS)

Makefile:  Add a newgame.c to list CFILES, newgame.h to HFILES,
newgame.o to dependency list grammar.o:, and create a dependency list
for newgame.o

If you implement help for the game, add H_NEWGAME to the list of
HELP_FILES.  Then create the file H_NEWGAME which is the help for your
game.  Edit the files HELP and H_HELP to include your new game.

Finally, you'll want to code your new game (placed, presumably, in
newgame.h and newgame.c).  Besides calls to functions in gameops.h,
you'll want to cache evaluations of board positions in the hash table
to avoid reevaluating them.  This is critical for efficiency if you
wish to solve large positions.  To do this, you'll need to encode a
position as a list of integers.  This is the format used for required
for the functions hash_test(), hash_put() and hash_get_last().  Review
domino.c and domino.h and you should get the idea.

If a segment of your code ought not be interrupted (e.g., memory
management routines), prepend the line "disable_interrupts;" and append
"enable_interrupts;".

Jeff Erickson included a means for a debugging flag in your code.  If
you want to use the "trace" debugging option in your code, review
toads.c to do this in a manner consistent with Jeff's.

If you want your new game to be included with the next distribution of
the code, send it to me, David Wolfe, at wolfe@cs.berkeley.edu ---
THANKS!
The program can recognize many games of the form G.  To turn on
the recogntion, enter 'ons'; it's one of the print options.

If you don't know already know about this particular generalization of
up-on, best not to worry about it.  But if you'd really like to
know....

The generalization of up^n (for example up-second) and upon are denoted G
and G, resp.  They are written in text "G" superscript "n" and "G"
superscript "--> n".  For G = 0|H in canonical form, define

G<0> = -H
G = 0 | {- G<0> - G<1> - G<2> - ... - G}

G = 0
G = G|H
        = G<1> + G<2> + ... + G

Also, negating G in the above definitions negates the right hand side.

These operations are define in Mathematical Go (type 'help books'.)
Partisan subtraction games are variants on nim.  Left can only take a
number of from a particular subtraction set (for example {1,3,4})
while Right may have a different subtraction set (for example
{1,2,6}).  So, if there is a pile of 10 tokens, and it's Left's move,
she can take 1, 3, or 4 tokens, leaving a pile of 9, 7 or 6 tokens,
respectively.

If any of the following commands are entered, a table of values is
produced, one for each possible size of pile.  (After 20 entries, the
program hesitates for a second to give you a chance to breath.)  You
can control-C and type 'a' for abort in order to stop the listing.
You can than use the variables g1, g2, g3, ... to investigate the
values of piles of sizes 1, 2, 3, ...

> sub 1 3 4 | 1 2 6	Left's subtraction set is {1,3,4}, Right's {1,2,6}
> sub 1 4 5		Both player's subtraction set is {1,4,5} (non-partisan)
> sub 1 3 4 | 1 6 (15)	Only print the first 15 values
> sub 1 4 5 (20)	Only print the first 20 values

Lastly, you may wish to test a hypothesis concerning the period and
saltus.  For instance, you can type:

> period 3  
> saltus ^*
> sub 1 2 | 1 3

Then, only those values, g(n), which fail to satisfy the recurrence
	g(n) = saltus + g(n - period)
are printed.  Naturally, for non-partisan games, the saltus will
always be 0 (the default).

This last feature works well with the "map" command (help eval).  For
example,

> map aw g
> period 3  
> saltus 1
> sub 1 2 | 1 3

Will confirm when the atomic weights satisfy period 3 and saltus 1.

Lastly, the game partisan kayles works the same way, except the player
who moved can also (optionally) split the remaining heap into two
heaps.  The same notation is used to play or analyze this game, only
use command "pk" or "pkayles":

> pk 1 3 | 2 4

An initial position of Toads & Frogs is a horizontal line of boxes,
some of which are occupied by a toad, some by a frog, and some empty.
Left move one toad to the right, or can leap one frog by moving two to
the right.  Similarly, Right moves frogs left.

To enter a position, type toads , followed by a line of
characters. Type a t for a toad, f for a frog, - for an empty box, and
| for a wall.  (Toads nor frogs can pass through walls.)

For example,

> toads
t-f

returns *.  Left could move a toad to the right to -tf = 0 and from
this position, only Right has a move to ft- = 1 from which Left has
a move to f-t = 0.

For another example,

t-tf = 1/2

Left moves to -ttf = 0, while Right moves to tft- = 1.

Lastly, the positions can be added together with a wall:

t-f|t-tf = 1/2*

Toads & Frogs was implemented by Jeff Erickson.

Possible improvements: 
* Include Bill Fraser's thermograph generation in the distribution
* BUG: Mean and temperature can fail when hash table is cleared.
    - temporary fixed by making them UNEXPENDABLE
* BUG: games_stat() g should go from 1 to game_cells-1.
* BUG: In printing variable names, there's a bug when
       two variables point to the same game, and one changes. (JP Grossman)
* Generalized history '$' to include $3 (third result)
  and $$$ (third to last result) (JP Grossman)
* Include a function 'bound' which gives simpler upper and lower
  bounds for a game (JP Grossman)
* Include a mechanism for entering and evaluating recurrences
* Use resizable hash tables and arrays, and make strings be arbitrary
  length.
* Change the mechanism for new games so that a new game can be
	included without changing so many files
* Rewrite main.c to include only .h files
* Rename "times" and "stat" and "init"
* Less cryptic parser
* Redesign so "konane.c" and "toads.c" etc, don't have to be included
- Make it possible to input and output files
- Let command line include any input, including game posititions
- Save space on game_struct's by using Union's
- Add loopy games such as on, ono, oof, hot, hi, lo, over, under, upon,...
- Thermal decomposition

________________________________________________________________
* Improvements for June, 2005
  I'm no longer working on the code, but made a few minor changes
  as suggested by Keith Briggs.
________________________________________________________________
* Improvement for August, 2001
  Added game clobber.
________________________________________________________________
* Improvements for April, 2000
- Mike Ernst fixed bug in Konane
- Changes to Makefile including control over maximum number of
  canonical forms of games stored and the hash table size.
- Made changes to remove warnings given by gcc

________________________________________________________________
* Improvements since January, 1998
- Add "play domino" to domineering (plays one move)
________________________________________________________________

* Improvements since January 23, 1997
- Tom VanDeGrift changed domino.c to calculate winner only 
  of large positions
- Added "map" command to apply transformations before output (help eval)
- Added partisan subtraction games
- Removed all of the ko stuff.  It was too flakey and was affecting
	the efficiency and (more importantly) the readability of the
	rest of the code.
- Removed Go corridors code.  The research was completed, and it
	was just clutter.
- Improved the efficiency of DOMINO by checking for symmetries.
	(Any game on a grid may wish to do same.  Search for
	B_symmetry in domino.c and bitmatrx.c for clues.)
________________________________________________________________
* Improvements since October 1, 1994
- Implement Dan Callistrate's chill by epsilon
	g[*] cools by * and g[e] cools by * and "projects".
	The latter is the simplest game infinitesimally near g!
	(To "project", remove all *'s from canonical form.)
________________________________________________________________
* Improvements since July 22, 1994
- control-C's are trapped in a nice way
- Fixed domino_input function to permit arbitrary size dominos
- Removed corridors and kos from the parser
- Print option 'ons' now defaults to being off
________________________________________________________________
* Improvements since June 28, 1994
- Make all filenames 8 or fewer characters for IBM PC's
- bug fix: games like -[2]|0<3> now are outputted properly
- bug fix: typing 'games evaluate "0 ? 3"' no longer leads to bus error
- Split HELP files into bite sized pieces
- Installed Jeff Erickson's Toads & Frogs
________________________________________________________________
* Improvements since Oct 5, 1993
- Append "..." to the ends of expressions too long to print
- Prints out warning if computing atomic weight of game G if (a) G is not all
	smalls or (b) the program fails to bound G between two hackenbush
	kites.  For example,  an error is reported for "aw +[2]", but reports
	an error for "aw 0||vv|-2".
- Put PRINT_FILE and HELP_FILE in Makefile --- changed HELP_FILE to LIB_DIR
- "#" is the comment character  ---  ignore through end of line
- 7 5/8 now parses
- variables names may now have digits mixed with letters --- e.g., x5yy
- normalizes results which are of the form number plus infinitesimal
	(Example 2|||2||2|-2 gets printed as 2{0|+[4]}.)
- outputs 0|g when appropriate, which means 0||||0|||0||...|g
	(Example 2||||2|||2||2|-2 returns 2{0<2>|+[4]}.)
________________________________________________________________
* Less recent improvements
- 0<3>|+[3]
- "quit" and "exit"
- errors when
	Norton unit does not exceed 0
	Atomic weight of non-infinitesimal
- +[3] is now the generalization of upon.  +[3]<(3)> still works, though.
- removed bug in hash_get_cell of hash.c
- vfork() changed to fork()
- TeX command \neg changed to \Neg