CS 2360
Spring 1996
Homework Assignments 6 and 7
Assignment 6 is due no later than 8:00am, Monday, May 13, 1996
Assignment 7 is due no later than 8:00am, Monday, May 20, 1996
Sure, there are competitors from 197 different countries coming to
Atlanta in a few weeks, but they're all here to play sissy sports.
Boxing? Feh. The marathon? Please. Rowing? Excuse me, how about
something that's really challenging...how about...HEXAPAWN!
Yes, it's time to get down and dirty with the game that the Olympic
folks forgot. Let's review the rules:
Hexapawn is played on a 3 x 3 chessboard. The two players face each other
across the board. Each player begins with three pawns, placed one to a square
in each of the three squares nearest that player. One player is somehow
randomly selected to begin. A player may choose to move one of his or her
pawns in one of these ways:
A pawn may be moved one square forward to an empty square
A pawn may be moved one square diagonally forward to a square occupied
by an opponent's pawn. The opponent's pawn is then removed.
The players alternate moving pawns until one of the players wins. A player
wins when:
A player's pawn has advanced to the other end of the board.
The opponent has no pawns remaining on the board.
It is the opponent's turn to move a pawn but is unable to do so.
As envisioned by its inventor, whose name is now forgotten but whose ideas live
on, hexapawn was intended to be played with only six pawns on a 3 x 3 board.
Now, however, we are extending the definition of hexapawn to include any
similar game involving n white pawns, n black pawns, and a n x n board. Over
the next two weeks, you are to construct a Common LISP function which takes as
input a representation of the state of a hexapawn game (i.e., a board
position), an integer representing the size of the board, an indication as to
which player is to move next, and an integer representing the number of moves
to look ahead. 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 hexapawn 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. You will need to devise a static board
evaluation function; feel free to use the one that was given in class or supply
a better or more interesting one. Your 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. You should be able to turn this printing on or off
via an additional parameter to the function.
Assume for now that the name of your top-level function is "pawnkiller". Your
function must then be ready to accept exactly five parameters when called. The
sample function call explains what goes where in the argument list:
(pawnkiller '((w w w)(nil nil nil)(b b b)) 3 'w 2 nil)
^ ^ ^ ^ ^
| | | | |
The first argument is an n-element list, | | | |
and each of these elements represents | | | |
a row of the board. The first element | | | |
is the first or "top" row, the second | | | |
element is the next row, and so on. | | | |
Each of these elements is itself an | | | |
n-element list. The elements of these | | | |
lists are either w to indicate a white | | | |
pawn on that square, b to indicate a | | | |
black pawn, or nil to indiate an empty | | | |
square. The leftmost element in one of | | | |
these nested lists represents the leftmost | | | |
square in the row represented by that | | | |
list, and so on. | | | |
| | | |
The second argument is an integer to ------+ | | |
indicate the size of the board being | | |
played on (or the number of pawns each | | |
player begins with). Thus, 3 here | | |
indicates a 3 x 3 board. | | |
| | |
The third argument will always be 'w or 'b,---+ | |
to indicate whether your function is playing | |
the side of the white pawns or the side of | |
the black pawns. There will never be any | |
other color of pawns. | |
| |
The fourth 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 fifth and last 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.
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:
((w nil w)(nil w nil)(b b b))
or some other board in this same format.
The deliverables for this assignment are due in two parts. First, we'd
like to see your static board evaluation function and your move generation
function by 8:00am, Monday, May 13. You can make upgrades to these
functions after that, but you must turn in a credible working version
of each of these functions by 8:00am, May 13. The board evaluation
function takes as input a board and returns a numeric value indicating
the "goodness" of the board. This function will probably also want to
know which side of the board your program is playing ('b or 'w -- for
example, if you pass 'b here, then you're playing the side of the black
pawns and the higher numbers should correspond to boards that are favorable
to black) and which side is supposed to move next. The move generator
function takes as input a board and an indication as to whose turn it is
next ('b or 'w again) and returns a list of all new boards that can
be generated in one move by the indicated player.
Then, by 8:00am, Monday, May 20, we'd like to see your entire hexapawn
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 pawn-crushing 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.
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 your 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.
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 have written 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.
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 move generator and get that done. Start working
on the rest of it as soon as you can. Get the search control structure
(i.e., everything else) working, then go back and tune your evaluator.
7) Your top-level function should be the first function defined in the
file you send us. Don't make us hunt for it. Also, do not name this
function "pawnkiller"---try to be at least a little bit creative.
8) Let the games begin!
Copyright 1996 by Kurt Eiselt. All rights reserved.
Last revised: May 6, 1996