One of My
Favorite Assignments
"Chomp"ing
into Computer Science
Edward Siegfried
Milton Academy
Simple strategy games often provide good projects in beginning
programming
courses. For seven or eight years, I have used a game tournament as
the culminating
activity of the first semester of a programming course. This coincides
with
a week at our school devoted to 90-minute examinations and provides a
change
of pace from the usual sort of exam preparation.
The game is "Chomp", invented by the mathematician David Gale and
introduced
by Martin Gardner in his Scientific American column of January
1973.
Chomp is complex enough to have nontrivial strategies but simple
enough to allow
board positions to be easily represented in any programming language.
I first
taught Chomp in Pascal, using Macintosh QuickDraw graphics. When I
moved my
introductory programming course to JavaScript in 1998, Chomp was
easily translated,
with graphics simplified to HTML tables and JPEG images. For the past
two years,
a colleague taught our introductory course in Java, using the game
once again.
Below, I have written code fragments in Pascal, because Pascal serves
as pseudo-code
for other languages and, with it I can easily indicate the allowable
ranges
for integer values.
The analysis of Chomp not only leads to some interesting programming
and some
interesting mathematics but also becomes a worthwhile amusement for a
teacher.
Although the contest format looks competitive on the surface, it is
actually
an experience in cooperative learning, because I encourage sharing of
strategic
and programming ideas and because actually winning the tournament does
not count
toward the grade. My examination itself works like this:
- Students prepare "Chomp player" subprograms. Each of these is
required to
take a board position as a parameter and return a legal move. The
students
also submit well-commented copies of their code
- Each participant makes a poster describing his or her strategy.
These are
available for the audience's inspection. Each student speaks briefly
about
strategy and any interesting issues he or she had considered
- The tournament proper consists of the incorporation of the
"player" subprograms,
submitted electronically, into a "Chomp referee" program written by
me. This
referee then generates a series of 200 games between each pair of
players,
and wins and losses are dramatically recorded on a scoreboard
- In the classes following the tournament several topics of computer
science
can be raised. The foundation for these is laid in the
pre-tournament preparation
Some of the issues that come up in this activity are
- parameter passing and local variables
- recursion, because this game's winning strategy is best analyzed
in recursive
terms; an
- structured coding. For example, a student's first approach to this
problem
will often be an accumulation of special cases, and he or she can
easily get
tangled in the complexity
Besides all the pedagogical benefit, tournaments are a lot of fun.
The audience
enjoys them, and they validate the efforts students have made in
preparation.
Rules of
Chomp
Chomp is a member of the "Nim" family of games. Two players take
turns removing
counters from a board. The player who has to take the last counter
loses. At
the start of the game, the counters are arranged in a rectangular
array of arbitrary
size, up to a limit of 10 by 10. A player may remove any remaining
counter,
and all counters above or to the right of it are also removed. For
example,
look at the following board position:
Figure 1.
If the player specifies counter A as his or her move, then counter B
is also
removed. If counter E is removed, so are counters C and F. If counter
B is removed,
no other counter goes off with it, while specifying counter D as one's
move
leaves just three counters on the board. Thus, a move can be seen as a
bite
taken out of the array of counters, which is the source of the name
Chomp. As
a result of the rule, taking the leftmost counter in the bottom row is
always
the last play of the game.
Although the game board seems naturally two-dimensional, a position
may best
be described by a list of numbers, each number indicating how many
counters
there are in the corresponding row, bottom to top. With this notation,
the position
in Figure 1 is denoted (4, 3, 2, 0, 0, 0, 0, 0, 0, 0) which we
abbreviate to
(4, 3, 2), All rows are flush to the left edge of the board, but they
may be
of different lengths. A move is simply the column and row
indices of
the counter to be taken. Limiting the largest allowable board to 10 by
10 leads
to the following Pascal declarations. In other languages, programmers
will use
zero-based arrays.
const
N = 10;
type
position = array[1..N] of 0..N;
move = record
row, column: 1..N
end;
Chomp
Players
Chomp is a game of "perfect information." That is, the situation at
any time
is completely described by the arrangement of the counters. There is
no need
to know the history leading up to that arrangement. Therefore a player
function
need have only one parameter—the board position—and because
it should
return a move, its function heading will be:
function my_player( A: position ): move;
An example of a simple player is:
function my_player( A: position ): move;
begin
if A[2] >= 2
then begin
my_player.row := 2;
my_player.column := 2
end
else begin
my_player.row := 1;
my_player.column := A[1]
end
end;
This player takes the counter at row 2, column 2, if it is available.
Otherwise,
it takes the rightmost counter in row 1. Such a player wins few, if
any, games.
A Chomp Board
Program
To assist students in developing their players, I prepared a program
that displayed
a board and counters. By clicking on the board's cells one could add
or remove
counters to set the board to any position he or she wished to study.
There was
a feature by which students could insert their own "player" code and
see how
it behaved in various positions. I also presented some weak sample
players.
Chomp
Tournaments
A "Chomp player" subprogram need not be deterministic, for it might
make a
random move in certain positions. However, there is no advantage to
random moves
if one has some idea of strategy, and hence there is no reason to
repeat games
with the same starting position. Therefore, I extended the Chomp Board
program
to a referee that conducted automatic play between two players. Each
series
consisted of 100 games, one game starting with each of the allowable
starting
positions, which are rectangles with sides not exceeding 10. To
neutralize any
advantage there might be to having the first move, we actually played
two
series of 100 games between each pair of players, with each player
going first
throughout one of the series. On a 300 MHz PC, a series takes less
than a minute,
making a round-robin tournament feasible.
Administrative decisions must be made about contestant players who
make illegal
moves, crash, or hang. The best defense is to test players thoroughly
first.
I made a version of the referee available beforehand so that a student
could
weed out problems by running practice series of his or her player
against itself.
I also encouraged groups of students to run the referee against one
another,
because group learning, not competition, was really the focus of the
tournament.
Chomp
Strategies
An appreciation for Chomp strategy develops from having played a
number of
games, and students should have some experience with the game before
they embark
on designing players. Playing Chomp for an hour with friends or
parents is a
useful homework assignment.
Gardner observes that victory can always be forced by a player who
can find
a move leaving just two rows of counters, with row 1 (the bottom row)
having
exactly one more counter than row 2:
Figure 2.
Verification of this by checking all possible cases reveals the
recursive nature
of Chomp strategy. See the Technical Appendix
for a
presentation of this in mathematical language. Discussions students
have with
one another in the course of developing their players build their
intuitive
understanding of recursion.
Similarly, there is a "two-column" strategy and a strategy based on
an L-shaped
position with equal legs. Coding the two-row strategy is
straightforward. A
Pascal pseudo-code fragment, with A[ ]denoting the current position,
might be
written (remembering that the rows in question have indices 1 and 2)
this way:
if (A[3] = 0) and (A[2] > 0) { if exactly 2 rows
are non-zero }
then
if A[1] = A[2] { if the rows are equal }
then
take( row 2, column A[1] ) { take one off the corner }
else if A[1] > A[2] + 1
then
take( row 1, column A[2] + 2 ) { shorten bottom row }
else { here there is no safe move }
take( anything )
Strategies for three rows or threee columns are much more elusive.
Complete
analysis of the game by brute student force is out of reach, but many
partial
strategies emerge. This is what makes the game so suitable for a
tournament,
for if a complete strategy can be readily found, the game is too easy.
A key concept for those who have gained some intuition for Chomp is
that of
"winning position." A winning position is one from which the opponent
has no
safe move. That is, if I leave a winning position and it is my
opponent's turn,
he or she will have to make a move from which I can then move to
another winning
position. If I have knowledge of all the winning positions, I am sure
to win.
Thinking about finding winning positions confers a big advantage,
because it
eliminates the need to repeatedly imagine, "If he does this, then I
can do that,
and if he does …, then …"
To elaborate on this idea, we may imagine two ways an experienced
Chomp player
can remember his or her strategy. The first is to remember what move
is best
from each of a large group of positions. The second is to record a
chart of
winning positions. The latter is far more efficient, because there are
so few
winning positions, and because it is easy to spot moves resulting in a
winning
position.
An even more flexible approach to strategy can be based on pattern
matching.
Most students will not discover this without hints, but a
pattern-matching study
is part of the richness of this problem. One student, Dan Bauer, wrote
down
a list of all the winning positions he knew, and then his player tried
to check
a given position to see whether it could be reduced to one of the
positions
on his list by a single move. If so, his player made that move. In
Dan's case
he used 28 verified winning positions and approximately 50 other
positions he
called traps. The traps were not known to be winning positions,
but they
exploited weaknesses of the strategies he expected his opponents would
be using.
Extensions of the
Activity
Martin Gardner's columns of that era contain a number of interesting
games.
Classic Nim is simpler than Chomp and correspondingly easier to
analyze and
program. A version of Nim was called "Force-Out" in the handheld
Little Professor
game toy of 1977, and I use the term Force-Out for Nim variations when
I use
them in a course.
Gardner also presents examples of games that "learn" their own
strategy. One
such game he calls "Hexapawn" and is played on a 3-by-3 chess board
with three
pawns for each player. Gardner constructs a physical model of a
Hexapawn player
that plays randomly, except that each time it loses, it reduces the
probability
of choosing its last, losing, move. Over time, the model improves its
performance.
Because Gardner wrote about Hexapawn before the days of
microcomputers, it is
an interesting exercise to replicate his ideas with a program.
An exhaustive analysis of Chomp can lead to the discovery of all
winning positions
on a board 10 by 10 or smaller. This is, of course, a job for a
computer. To
achieve this, one first needs a way to generate all possible Chomp
positions,
ordered from smallest to largest. Then one needs a way to match each
position
generated against the known winning positions. If the new position can
be reduced
to a winning position by a single move, it is discarded. Otherwise it
must be
a winning position itself, so it is added to the list of winning
positions.
Thinking about the combinatorial mathematics involved here was
enjoyable for
me, even though it was strictly beyond the scope of my course.
Available
Code
Code for the above Chomp programs, in Think Pascal and JavaScript
1.1, is available
from the author at es@milton.edu.
[Author:
Could we post it as a second appendix?]
Reference
Gardner, M. (1973). Mathematical games. Scientific American,
228(1),
108–115
Contributor
Edward Siegfried is the director of academic technology at Milton
Academy and
has taught many flavors of high school computing since 1981. He also
enjoys
teaching math, managing an electronic mailing list, and intense
discussions
with people about the significance of computing in schools.
Edward Siegfried
Milton Academy
170 Centre St.
Milton, MA 02186
es@milton.edu
Technical
Appendix
Formal Description of
"Winning Position"
All Chomp positions fall into one of two disjoint classes. The
"winning positions,"
or W for short, and the other positions, abbreviated X.
These
classes have a critical relationship:
For any position in X, there is some legal move that
will result
in a position in W.
For each position in W, any conceivable legal move
results in
a position in X.
The consequence of this is that if I make a move resulting in a
position in
W, my opponent's move surely results in a position in X.
Then,
on my next turn, I can again achieve a position in W. We
continue recursively
to the end of the game and my opponent cannot escape.
Proof That Two Rows with Lengths Differing by 1 is a Winning
Position
In formal mathematical language, we may prove this assertion by
induction.
In the notation used earlier, such a position is denoted (n + 1, n, 0,
0, ...
) or simply (n + 1, n ). We want to show this is true for all values
of n. Induction
proofs proceed by establishing a "base case" and then showing that the
truth
of the n-th assertion follows from the hypothesis that all the
previous assertions
are true.
As a base case, position (1), which is the same as (1, 0), is a
winning position.
Assume that (k + 1, k) is a winning position for every k
with 1 ?
k< n. Then to show that (n + 1, n) is also a winning
position,
observe that a move from position (n + 1, n) must
result in one
of
- an empty board, if the opponent took all the
counters;
- position (n + 1, a - 1) if the opponent's move was from row 2,
column a,
with 1 ? a ? n; or
- position (a - 1, a - 1) if the opponent's move was from row 1,
column a.
with 2 ? a ? n + 1.
These are all the possible moves.
In case (a), we have won already. In case (b), we may take the
counter from
row 1, column a + 1, which reduces the position to (a, a - 1). In case
(c),
we may take the counter from row 2, column a, which reduces the
position to
(a - 1, a - 2). By the Induction Hypothesis,
both of
these are in W, which completes the proof.
An Algorithm to Generate All N-by-N Chomp Positions
This iterative algorithm generates a sequence of positions
reminiscent of those
produced by the well-known backtracking method used in the solution of
the Eight
Queens problem.
First, recall that no Chomp position can have a row longer than the
row below
it or a column taller than the column to its left. This follows from
the restriction
that Chomp games always start from a rectangle of some size. To
produce a list
of all Chomp positions, begin with the empty Chomp position and step
from position
to position as shown:
Given any position, add one counter to the lowest incomplete row and
shorten
any rows below it to the same length.
In Pascal the procedure to pass to the next position as follows. We
assume
that entry A is not the final position (the one with all rows having N
counters.)
procedure next_position( var A: position );
var
r, s: 1..N;
begin
r := 1;
while (r < N) and (A[r] = N) do
r := r + 1;
{ at this point, r is the lowest incomplete row }
for s := 1 to r do
A[s] := A[r] + 1;
end;
Copyright ©
2002, ISTE (International Society for Technology in Education). All
rights reserved.
|
