This is to display Grundy value of possible moves in a game of Chomp
a bar of chocolate at most size 11x11.
Warning: Initialization can be slow, so I start with bar size at most 3x3.
Increase this and see if your computer is still happy.
Max size chocolate bar is 11x11.
Currently max size bar is
number of rows shown in table below:
condition on positions shown:
Find the Grundy value of this position, given as sequence of lengths of rows
(characters 0-9 and x,y for 10, 11; other characters are ignored, and
increases in sequence are converted to non increasing sequences):
Grundy value 0
Highlight moves resulting in Grundy value:
Highlight responses when second player wins
change display window height:
Use in conjuction with changing rows
displayed by above input. Generally you have to scroll left/right/up/down to see all
For a text file of computations, click here:
Format in the downloaded file:
each row corresponds to a position, given as
first sequence in row. Subsequent entries in row correspond to
possible moves; these are three element arrays, consisting of
Grundy value of resulting position after making move corresponding
to position indicated by remaining two entries.
This file does not contain symmetric repeats, that is, if there are
two positions which are equal up to symmetry about the main diagonal,
only one is included.
"Feature": If you are looking at responses, but change
bar size, it will revert to looking at Grundy values,
so choose responses choice again. If you want to
see more positions remember to increase rows shown, since
otherwise not all computations will be shown, and in anycase, I have not set enough svg to show the maxiumum possible range of positions,
to keep file size down.
When second player responses are highlighted, only second player win positions are shown. The number chosen when looking at responses
just indicates going through
the squares of the position in sequence; the square
corresponding to the chosen number is highlighted blue, and
winning second player responses are highlighted magenta.
Default is highlighting moves with particular grundy value, in red,
and on loading page, the values corresponding to
Grundy value 0 are shown, that is, winning moves for
first player are red.
If you choose a position in the box, by a sequence of up to 11 numbers,
then the Grundy value is shown, and if you click "show",
this position is displayed. If the position is first player
win, the winning move or moves are shown, by showing the resulting position. If the position is a second player win, then the results of
winning pairs of moves are shown (ie., for any move, there is
a response such that the resulting position is still winning
for the second player; these resulting positions are shown, with the original position in the background for reference). If you change the
chosen value, you have to click on "show" again, or it reverts to
showing the positions given previous choice of conditions.
In the choice of conditions, "bitten rectangle" means the
results from taking one move from a starting rectangle.
If we choose "bitten 2nd player win", this means show the
results from chosing the winning move starting from a rectangle.
I have only tested this program running in Chrome
on a macbook. It can be very slow when the bar size is increased, so be prepared to wait if you don't have a suffciently powerful computer.
This program was written using a recursive method. Recurrsion seems not the fastest way to go, so will
probably rewrite sometime.
There has been vast amount of work done on Chomp.
just displays some data.
I have more data here.
A few references: