Menu
▾
▴
Tree [3823e8] master v0.2 / History
Kevin O'Gorman
Read Me
Chocoholic 0.2
Some random comments by the author:
The documentation on the sourceforge wiki is probably more recent than this. Browse
http://sourceforge.net/p/chocoholic/wiki/Instructions/
G
TERMINOLOGY
For clarity, rather than calling a position won or lost, it is usual in game theory to
call them N-positions (won by the "Next" player) or P-positions (won by the "Previous"
player.
THE GAME
The name of the game of Chomp comes out of the original idea: a bar of candy ruled into
squares, and plays that consist of "chomping" a region of the bar while avoiding the one
square that is poison.
The game is played on a rectangular grid of squares. Square boards have very simple
strategy, so squares boards are never used. The poison is one of the corner squares;
since the computer opponents I've seen all have it in the lower-left corner, I designed
this software around that idea and I will describe it that way. Another corner could be
used and the game would be essentially the same.
The players make moves in strict alternation. A move consists of "chomping" one of the
remaining squares in the grid, along with any squares that are above it, to the right of
it, or both. The player who chomps the poison loses the game.
COMPUTER OPPONENTS
As of October 2012, you can play Chomp here, so long as your browser can run a Java applet.
http://www.win.tue.nl/~aeb/games/rect.html. Games are limited to an 11x6 grid.
If you don't have Java, or don't have it enabled in your browser, there's a Javascript
version at http://www.math.ucla.edu/~tom/Games/chomp.html
THE PROJECT
This is a collection of programs to aid in the exploration of the solution space of the
game Chomp. It was inspired in part by a paper that won its high-school author
US$100,000, which must have helped with his tuition at Harvard. The paper was titled
"Poset Game Periodicity" and was the first paper to address this family of games in a
general way.
The present purpose is less grand. I'm just putting together some things that helped me
to explore the game of Chomp, and gave me a "cheat book" that allowed me to play against
the computer opponents currently known to me without embarrassing myself too much.
This was all written in C on a Linux OS -- Xubuntu "precise" to be precise -- and is
designed to work in the Unix shell command-line. For most things in this collection, a
good start would be to read the "chomp.h" header file.
THE RESULT
A run of the software is performed by the "chomploop.sh" script, which takes the board
geometry as an input and creates a file of positions, one per line, with 4 fields per
line. The lines are printable but slightly encoded text. The fields are:
1 the position, described by column heights encoded one character per column. The
encoding is an extension of hexadecimal with the groups (0-9)(A-Z)(a-z)(-_) for 64
valid numbers in all.
2 exactly 3 bytes: the letter P followed by the 0-based encoding of the column and row
of the best move. (3 bytes)
3 the game-theoretical value of the position. Negative numbers are for P-positions and
express how many moves the N-player can drag out the game against best play, and
positive numbers are for N-positions and express how quickly best play can finish the
game.
4 The number of winning moves (0 for P-positions).
Examples: The two winningest positions on a 12x12 board:
A88877655542 P27 54 7
CCBBA76411 P39 54 7
Note that these are reflections of eachother. They can be visualized as
x and xx
x xxxx
xx@x xxx@x
xxxxxx xxxxx
xxxxxxx xxxxx
xxxxxxxxxx xxxxxx
xxxxxxxxxxx xxxxxxx
xxxxxxxxxxx xxxxxxx
xxxxxxxxxxxx xxxxxxxx
xxxxxxxxxxxx xxxxxxxx
xxxxxxxx
xxxxxxxxxx
The indicated winning moves are not the reflections. This is because they have the same
value and the software does not distinguish among equally-good moves. Note also that
both of them will take 54 more moves (plies) to win against best defense. The board
position contains only 75 cells, so this seems surprising, but is a common feature of
the game. This leads to a conjecture.
SOME NUMBERS
On my 32-bit home machine with 4 cores, this software took just 10 minutes to derive the
values of the 2,704,155 positions that fit in a 12x12 board. The resulting file is 12
megabytes. 99.008% of the positions were N-positions. 84.55% of the postions have 1 or
2 winning responses. The exact counts are
26838 0 (all P-positions)
1079885 1 (N-positions)
1206570 2
357256 3
30424 4
3022 5
158 6
2 7
ON THE SOFTWARE
The heart of the matter is the board as expressed in the C struct "board_t" which
defines a bounding-box for any positions to be contained, and an array "cols" which
contains a list of column-heights. The current implementation imposes these limits:
- there can be up to 63 columns and each can have a height up to 63 cells.
These limits don't bother me much. A 63x63 arena would allow for 10^37 positions, which
is more than the present lifetime of the universe expressed in clock cycles of my machine's
CPU. You can calculate stuff like that if you can do factorials. The number of positions
in an arena of r rows and c columns is
factorial(r+c) / (factorial(r) * factorial(c))
I have run a solution of the 16x16 arena with this software, and the results are posted at
http://kosmanor.com/Chocoholic. The files have been compressed in several ways; take
your pick. I did not post the uncompressed files because I don't have infinite bandwidth.
RUNNING A SOLUTION
If you want a file that will help you play the Java applet, on a Linux system,
make
bash chomploop.sh 11 7
bash chompsmall.sh 11 7
This should take only a minute or so. Now you can use the file csort-11x7 to win on an
11x7 arena, or anthing that fits inside that size.