CS 2360
Spring 1998
Homework Assignments 6 and 7
Assignment 6 is due no later than 8:00am, Monday, May 18, 1998
Assignment 7 is due no later than 8:00am, Monday, May 25, 1998
As of May 22, Assignment 7 due date is postponed to 8:00am, Tuesday, May 26
It sure is hard finding new games for you LISPlings to work on every
quarter, but here at the Game Research Laboratory at Rancho Kurt we
work around the clock to assure a steady supply of fresh challenges.
We've recently come up with a new game called Crusher, which is a hybrid
of two other games, Hoppers and Abalone. Hoppers has been used in
a previous 2360 class and the pieces had a fun "leapfrog" style of
movement. But pieces in Hoppers can't capture opposing pieces, which
leads to two problems: 1) the number of pieces on the board never
decreases, which means the branching factor on the state space search
stays pretty constant, and that translates into a slow program, and 2)
the lack of capturing mayhem leads to boring games. Abalone hasn't
been used in 2360 before because of the complexity of move and capture rules,
but it's played on a hexagonal board and a player needs a numerical
advantage in pieces to capture an opposing piece. We've extracted those
features from Abalone and munged them together with Hoppers to produce
our new, albeit experimental, product that we call Crusher.
As mentioned above, Crusher is played on a hexagonal board with
N hexes to a side. Each player starts with 2N-1 pieces arranged in
two rows at opposite ends of the board. Here's an example of an
initial Crusher board where N = 3:
W W W
- W W -
- - - - -
- B B -
B B B
White always begins at the top of the board, and white always makes
the first move.
In Crusher, players alternate moves and try to win by obliterating
the other player's pieces. A piece can move in one of two ways.
First, a piece can slide to any one of six adjacent spaces so long
as the adjacent space is empty. So in the diagram below, the black
piece can slide to any of the spaces indicated by a "*":
W W W
- * * -
- * B * -
- * * -
B B B
The other type of movement is a leap. A piece can leap over an adjacent
piece of the same color in any of six directions. The space that
the piece leaps to may be empty, or it may be occupied by an opponent's
piece. If the space is occupied by an opponent's piece, that piece is
removed from the game. Thus leaping is not only a means of movement,
but it's the only means of capturing an opponent's piece. Also,
note that a player must line up two pieces in order to capture an
opponent's piece. Here's an example of leaping. Let's say the
board looks like this:
W W -
- W - -
- - B - -
- - B -
- - -
If it's now black's turn, black has two possible leaps available
(in addition to several slides). Black could leap like this and
crush the white piece (hence the name Crusher...we we're going to
use Squash, but that's already been taken):
W W -
- B - -
- - B - -
- - - -
- - -
This would seem to be a pretty good move for black, as it results
in one less white piece on the board and no immediate threat to
black. The other possible leap shows black running away for no
obvious reason:
W W -
- W - -
- - - - -
- - B -
- - B
Note that a piece may not leap over more than one piece. Oh, there's
one more constraint on movement. No player 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 forward,
the other player moves forward, the first player moves back, the other
player moves back, the first player moves forward, 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.
How does a game end? Who wins? One player wins when he or she has removed
N (i.e., more than half) of the opponent's pieces from the board.
That was easy, wasn't it? A player also wins if it's the opponent's
turn and the opponent can't make a legal move. (This last condition
was added on May 13.)
Over the next two weeks, you are to construct a Common LISP function, along
with all the necessary supporting functions, which takes as input a
representation of the state of a Crusher 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
"crusher", 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 hexes or 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 Crusher 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. The use
of Alpha-Beta pruning is optional, and will earn extra credit if done
correctly (assuming the rest of the program works too). You will need to
devise a static board evaluation function to embody the strategy you want your
Crusher program to employ, and you'll need to construct the necessary move
generation capability.
As noted above, your Crusher 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 Crusher function will be called. Assume
that we want your function to make the very first move in a game of
Crusher, and that N is set to 3. As we noted above, that beginning board
would look like this:
W W W
- W W -
- - - - -
- B B -
B B B
Your Crusher function must then be ready to accept exactly five parameters
when called. The sample function call explains what goes where in the
argument list:
(crusher '((w w w nil w w nil nil nil nil nil nil nil b b nil b b b))
'w 2 nil 3)
^ ^ ^ ^ ^
| | | | |
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 w, b, or | | | |
nil. 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+1 elements are the | | | |
second row, and so on. (The number of | | | |
spaces or hexes in each row increases | | | |
by 1 to a maximum of 2n-1 and then | | | |
decreases by 1 in each of the following | | | |
rows until the bottom row, which contains | | | |
n hexes or spaces. | | | |
| | | |
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. Nil means don't |
print the trace, and a non-nil value here means |
that the trace should be displayed. |
|
The fifth argument is an integer representing N, ---+
the dimensions of the board. The value 3 passed
here says that this board has 3 spaces or hexes
along each of its six 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:
(nil w w nil w w nil nil nil w nil nil nil b b nil b b b)
or some other board in this same format. That result corresponds to
the following diagram:
- W W
- W W -
- - W - -
- B B -
B B B
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 8:00am, Monday, May 18. You can make
upgrades to them after that, but you must submit credible working versions
by 8:00am, May 18. 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. If your
TAs can't figure out how to test these functions, your score for homework 6
is likely to be pretty low. And of course, the code for your board
evaluation, move generation, and board conversion functions must adhere to
functional programming guidelines.
Then, by 8:00am, Monday, May 25, we'd like to see your entire Crusher
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 crushing machine. After the upcoming exam, we'll be
introducing you to some useful side effects, and you can use those
non-functional programming techniques on everything but the static board
evaluation function and the move generator.
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 just 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...use packages
(they'll be covered in a lab).
5) Do not redefine existing LISP functions. Before you "invent" a
function name, make sure that LISP 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 "crusher". Nothing else
will do. If you do the extra credit, submit an additional program
called "crusher-ec".
8) Before writing any code, play the game a few times. All you TAs out
there should play a few games too.
9) Very shortly, we'll be posting specific interface requirements for
your move generator, your board evaluation function, and your board
converters. Stay tuned.
Copyright 1998 by Kurt Eiselt, except where already copyrighted
by somebody else.
Last revised: May 22, 1998