The happy game elves here at the Game Research Laboratory have concocted
a game to keep all you 1321Xers busy. We call the game Capture the Flag,
or just Capture for short. You may eventually call it $%^#@&.
Capture is played on a square board with N spaces to a side. The number
of pieces that each player may start with is variable, but each player
will start with one flag and at least one pawn. Here's an example
of an initial Capture board where N = 5:
-- WP W* WP --
-- WP WP WP --
-- -- -- -- --
-- BP BP BP --
-- BP B* BP --
In Capture, the two opponents are "white" and "black". Each side starts
with one flag (indicated by W* for the white flag and B* for the black
flag) and one or more pawns (indicated by WP or BP). Players alternate
moves and try to win by achieving one of four different goal states:
1) A player wins if all the opponent's pawns have been captured
2) A player wins if the opponent's flag has been captured
3) A player wins if it's the opponent's turn to move and the
opponent can't make a legal move
4) A player wins if he moves his flag forward past all the opponent's
pawns without his flag being captured.
How does a piece move? How does it capture another piece? It depends
on what kind of piece it is.
Pawn movement:
Pawns can move one space forward (to the opponent's end of the board),
to the left, or to the right, so long as the pawn moves to an unoccupied
space. Pawns can never move backward (toward its own end of the board),
and they can never move diagonally.
Pawns can jump two spaces forward, to the left, or to the right, so long
as the pawn moves to an unoccupied space AND the pawn jumps over an
opponent's piece. The opponent's piece is then captured and removed from
the board. Pawns can never jump backward, and they can never jump
diagonally. Multiple jumps are not permitted.
A flag can move one space forward, to the left, to the right, or backward.
A flag can never move diagonally, and it can never move more than one space
on a turn. Thus, a flag can neither jump nor capture.
Oh, there's one more constraint on movement. No piece may make a move that
results in a board configuration that has occurred previously in the game.
This constraint prevents the "infinite cha-cha" where one player moves left,
the other player moves left, the first player moves back, the other
player moves back, the first player moves left, and so on. It will
be easy for you to prevent this sort of annoying behavior by checking
the history list of moves that will be passed to your program.
Over the next three weeks, you are to construct a Scheme function,
along with all the necessary supporting functions, which takes as input a
representation of the state of a Capture game (i.e., a board position), an
indication as to which player is to move next, and an integer representing
the number of moves to look ahead. (As you read on, you'll find that the
current board position is actually the first element on a list containing
all the boards or states that the game has passed through, from the initial
board to the most recent board.) Your function, which you will call
"capture", will also be passed a parameter indicating whether a trace should
be printed (described in a little bit more detail below), and an integer
representing N (the number of spaces along one side of the board).
This function returns as output the best next move that the designated player
can make from that given board position. The output should be represented as
a Capture board position in the same format that was used for the input board
position.
Your function must select the best next move by using MiniMax search. You will
have to devise a static board evaluation function to embody the strategy you
want your Capture program to employ, and you'll have to construct the
necessary move generation capability.
As noted above, your Capture function should also be able to print a trace of
its behavior as it carries out the search. This trace should show at the very
least what boards or nodes are being searched and what values are being
propagated upwards. This printing will be turned on or off via the
parameter mentioned above.
Here's an example of how your Capture function will be called. Assume
that we want your function to make the very first move in a game of
Capture, and that N is set to 5. As we noted above, that beginning board
might look like this:
-- WP W* WP --
-- WP WP WP --
-- -- -- -- --
-- BP BP BP --
-- BP B* BP --
Your Capture function must then be ready to accept exactly five parameters
when called. The sample function call explains what goes where in the
argument list:
(capture '((-- wp w* wp -- -- wp wp wp --
-- -- -- -- -- -- bp bp bp -- -- bp b* bp --))
'w 2 #f 5)
^ ^ ^ ^ ^
| | | | |
The first argument is a list of lists. | | | |
That list represents a history of the | | | |
game, board by board. The first sublist | | | |
on this list will be the most recent board. | | | |
The last element of the list will be the | | | |
initial board before either player has | | | |
moved. This history list is initialized | | | |
as shown above. Each sublist is a list | | | |
of symbols which can be either wp, w*, | | | |
bp, b*, or --. | | | |
| | | |
Each of these elements represents a | | | |
space on the board. The first N elements | | | |
are the first or "top" row (left to | | | |
right), the next N elements are the | | | |
second row, and so on. | | | |
| | | |
The second argument will always be 'w or 'b,+ | | |
to indicate whether your function is playing | | |
the side of the white pieces or the side of | | |
the black pieces. There will never be any | | |
other color used. | | |
| | |
The third argument is an integer to indicate -+ | |
how many moves ahead your minimax search is to | |
look ahead. Your function had better not look | |
any further than that. | |
| |
The fourth argument is the flag to turn the -----+ |
trace function off or on. #f means don't |
print the trace, and a non-#f value here means |
that the trace should be displayed. |
|
The fifth argument is an integer representing N, ---+
the dimensions of the board. The value 5 passed
here says that this board has 5 spaces along
each of its sides.
This function should then return the next best move, according to your search
function and static board evaluator. So, in this case, the function might
return:
(-- wp w* wp -- -- wp -- wp -- -- -- wp -- --
-- bp bp bp -- -- bp b* bp --)
or some other board in this same format. That result corresponds to
the following diagram:
-- WP W* WP --
-- WP -- WP --
-- -- WP -- --
-- BP BP BP --
-- BP B* BP --
One other thing: Your Capture program can't assume anything about
the initial board layout other than that the board will be square,
each side will start with only one flag, and each side will start
with at least one pawn. So there's a whole lot of possible starting
boards for any given N. Your program will just have to deal with it.
The deliverables for this assignment are due in two parts. First, we'd like
to see your static board evaluation function, your move generator, and
your board conversion functions by 11:00pm, Tuesday, Nov. 25. You can make
upgrades to them after that, but you must submit credible working versions
by 11:00pm, Nov. 25. When you submit these functions, make sure you provide
sufficient documentation explaining what arguments these functions are
expecting, so that your teaching assistants can test them out.
Then, by 11:00pm, Wednesday, Dec. 3, we'd like to see your entire Capture
program -- move generation, minimax, alpha-beta pruning if you want, and your
possibly new, improved secret weapon static board evaluator, all merged into
one lean, mean flag-capturing machine.
Some extra notes:
1) We may need to modify the specifications a bit here or there in case
we forgot something. Try to be flexible. Don't whine. Remember,
we invented this game. It may suck. Do the best you can with it.
2) A static board evaluation function is exactly that -- static. It
doesn't search ahead. Ever.
3) You can convert our board representation to anything you want, just
as long as when we talk to your functions or they talk to us, those
functions are using our representation. Thus the interface to your
board evaluator and move generator must be in terms of our board
representation, and the interface to your top level function must be in
terms of our board representation. This is not intended as an
endorsement of the board representation we've chosen here; you could
easily come up with a more convenient representation scheme. We're
only using this representation to give you the opportunity to think
about your knowledge representation scheme.
4) We are not asking you to write the human-computer interface so that
your program can play against a human. You can if you want to, just
for fun, but we don't want to see it. We'll write a driver program
that will allow your function to play against the functions written
by your classmates. Your function will be loaded alongside your
opponent's functions. Yes, two functions, trying to do exactly the
same thing, sharing the same space...yikes! The potential for
disaster is tremendous, because you're now programming in a very
communal environment. Practice safe programming.
5) Do not redefine existing Scheme functions. Before you "invent" a
function name, make sure that Scheme doesn't already use that name.
6) Program early and often. The board evaluator is easy. The rest is much
more difficult. Get the board evaluator out of the way in a hurry, then
start working on the rest of it as soon as you can. Get everything
else working, then go back and tune your evaluator.
7) Your top-level function should be named "capture". Nothing else
will do.
8) Before writing any code, play the game a few times. You TAs should
play the game a few times too.
9) Very shortly, your TAs will post specific interface requirements for
your move generator, your board evaluation function, and your board
converters. Stay tuned.
10) You are to work on these assignments in teams of two. Team members
must be currently enrolled in CS 1321X. Send email to Mitch
(mphalpin@cc.gatech.edu) to let us know who you've teamed up with.
Send that email no later than Wednesday, November 19.
11) You'll get one or two more small homework assignments while you're
working on this one. Don't panic.
Copyright 2003 by Kurt Eiselt, except where already copyrighted
by somebody else.
Last revised: November 12, 2003