CS 2360
Winter 1998
Homework Assignments 7 and 8
Assignment 7 is due no later than 8:00am, Monday, March 2, 1998.
Assignment 8 is due no later than 8:00am, Monday, March 9, 1998.
You're probably familiar with the game of checkers or draughts (as it is
known in Europe), but did you know that the history of the game goes back
thousands of years? The earliest known ancestor of checkers has been
traced back to ancient Egypt. Boards for this unnamed game were found
carved into the giant roofing slabs of the temple at Kurna in Egypt, which
was built about 1400 BC. Somewhere in the next two thousand years, the
name was given the Arabic name Quirkat. Quirkat migrated to Spain when the
Moors invaded Spain and along the way it became El-quirkat. Sometime
around 1250 AD, the game was first documented under the Spanish name it is
known by today, Alquerque. The game went with the Spanish explorers to
North America. The Spaniards who settled in what is now New Mexico
introduced a modified Alquerque to the Zuni Indians, who turned that game
into another that is known as The Game of The Stone Warriors. Is it a
coincidence that a big city in New Mexico today is named Albuquerque?
Beats me. But I digress...let's get back to the game of Alquerque.
Alquerque is a two-player game played on a 5x5 board. Each player begins
with 12 playing pieces, initially arranged as shown below (the center space
is empty at the start of the game).
W -- W -- W -- W -- W
| \ | / | \ | / |
| \ | / | \ | / |
W -- W -- W -- W -- W
| / | \ | / | \ |
| / | \ | / | \ |
W -- W -- -- B -- B
| \ | / | \ | / |
| \ | / | \ | / |
B -- B -- B -- B -- B
| / | \ | / | \ |
| / | \ | / | \ |
B -- B -- B -- B -- B
The player with the white pieces makes the first move, and the players
alternate moves after that. The pieces move from any point to any adjacent
empty point along the marked lines shown above. If the adjacent point is
occupied by an enemy piece and the next point beyond it is empty, the
player's piece can make a short jump over the hostile piece to the empty
point and remove the hostile piece from the board. Pieces can move
forward, diagonally forward, or sideways; they cannot move backwards.
NO PIECE MAY RETURN TO THE POINT IT MOST RECENTLY VACATED, EXCEPT IF
THAT PIECE JUMPS TO THAT POINT WHILE CAPTURING AN OPPONENT'S PIECE
(which essentially means that a piece can't slide sideways back
and forth...this rule has no bearing on forward movement). Also, a piece
that reaches the opponent's back line can only move by making a sideways
leap over an enemy piece and capturing that piece; it cannont slide to
an adjacent empty point.
How does a player win this game? There are THREE winning conditions. The
first is obvious: if you remove all the opponent's pieces from the board,
you win. THE SECOND CONDITION IS: IF IT'S THE BEGINNING OF YOUR OPPONENT'S
TURN, AND HE OR SHE CAN'T MAKE A LEGAL MOVE, YOU WIN. The THIRD condition
is one we've invented for the computer-based version of this game: the
game is over when all the white pieces have moved below all the black
pieces (or all the black pieces are above all the white pieces, depending
on your perspective) and the winner is the player with the most pieces
remaining on the board. (If both players have the same number of pieces
remaining, the game is a draw.) Simple, huh?
Well LISPlings, you're all gonna get a chance to find out just how simple
this game really is. Over the next two weeks, you are to construct a
Common LISP program that takes as input a representation of the state of an
Alquerque game (i.e., a sequence of board positions), an indication as to
which color (black or white) is being played by the program you have
created, an integer representing the number of moves that your program
should look ahead, and a flag to turn the tracing on or off.
Your Alquerque program will return the best next move that the program
(playing the designated color) can make from that given board position.
The returned result should be in the form of a new Alquerque board, using
the same format as the board that was passed to your program.
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, assuming
that everything else works well. You will need to supply your own static
board evaluation function. 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 a parameter passed to the function.
The name of your top-level function must be "alquerque". Your function
must then be ready to accept exactly four parameters when called. The
sample function call and subsequent discussion below explains what goes
where in the argument list:
(alquerque [history of moves made] [color of pieces used by the program]
[number of moves to look ahead] [trace flag])
HISTORY OF MOVES MADE: This will be a list of successive boards. The
first element 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 will be initialized as follows:
(
((w01 w02 w03 w04 w05)
(w06 w07 w08 w09 w10)
(w11 w12 nil b12 b11)
(b10 b09 b08 b07 b06)
(b05 b04 b03 b02 b01))
)
That's the list that will be passed to the program that makes the first
move. If everything works right, that program will be playing the white
pieces, and it will return a move (not a list of moves) represented by a
single board. Here's one possible move that the white program might return:
((w01 w02 w03 w04 w05)
(w06 w07 nil w09 w10)
(w11 w12 w08 b12 b11)
(b10 b09 b08 b07 b06)
(b05 b04 b03 b02 b01))
After white makes this move, the history list that would be passed to the
opposing program would look like this:
(
((w01 w02 w03 w04 w05)
(w06 w07 nil w09 w10)
(w11 w12 w08 b12 b11)
(b10 b09 b08 b07 b06)
(b05 b04 b03 b02 b01))
((w01 w02 w03 w04 w05)
(w06 w07 w08 w09 w10)
(w11 w12 nil b12 b11)
(b10 b09 b08 b07 b06)
(b05 b04 b03 b02 b01))
)
Of course, I've made these structures pretty for purposes of readability in
this document, but they won't necessarily be formatted like this when you
display them on your workstation unless you apply some pretty-printing.
Two other things to note here. First, I've given each piece in my
representation a unique identifier. That's information that you may find
useful. Second, the representation I'm using to pass information to your
program isn't necessarily the representation that you'll want to manipulate
internally. The representation that your programs use internally is up to
you, but your program will communicate to us using our representation.
COLOR OF PIECES USED BY THE PROGRAM: This argument will always be 'w (for
white) or 'b (for black) to indicate whether your program is playing the
side of the white pieces or the side of the black pieces. There will never
be any other color used.
NUMBER OF MOVES TO LOOK AHEAD: This argument will always be an integer to
indicate how many moves ahead your minimax search should be looking. Your
program must not look any further than that.
TRACE FLAG: The fourth and last argument is the flag to turn the trace
function off or on. Nil here means don't print the trace, and a non-nil
value here means that the trace should be displayed.
As noted above, your program returns the next best move as determined by
your search function and static board evaluator. The next best move might
be:
((w01 w02 w03 w04 w05)
(w06 w07 nil w09 w10)
(w11 w12 w08 b12 b11)
(b10 b09 b08 b07 b06)
(b05 b04 b03 b02 b01))
which would correspond to this diagram:
W -- W -- W -- W -- W
| \ | / | \ | / |
| \ | / | \ | / |
W -- W -- -- W -- W
| / | \ | / | \ |
| / | \ | / | \ |
W -- W -- W -- B -- B
| \ | / | \ | / |
| \ | / | \ | / |
B -- B -- B -- B -- B
| / | \ | / | \ |
| / | \ | / | \ |
B -- B -- B -- B -- B
The deliverables for this assignment are due in two parts. The first due
date is Monday, March 2. At this time we want you to turn in the following
components:
1) Static board evaluation function - This function takes as an input
argument a history list of game boards (the same history list that is
passed to your top-level "alquerque" function) and returns a numeric value
indicating the "goodness" of the board. The numbers should range from
positive N to negative N where N is a value of your choosing. This function
will also want to know from whose perspective the board is being evaluated.
That is, your evaluation function needs to know if "alquerque" is playing from
the white pawns' perspective or the black pawns' perspective. If you passed
'b here, for example, then your program is playing the side of the black
pieces and your evaluation function should return positive numbers for
boards that are favorable to black and negative numbers for boards that are
favorable to white. In addition, as your evaluation function looks at a
given board position, it needs to know which color is going to take the
next turn from that particular position. Remember the example from
hexapawn: if you're looking at a board where nobody can make a move, then
that board is a winning board for you if it's the opponents turn, and it's
a losing board for you if it's your turn. Call this function
"board-evaluator". You'll be allowed to tweak your board evaluator after
the March 2 due date if you want to participate in the tournament (more
about that later), but you must turn in a credible working evaluator on
March 2.
2) Move generator - This function takes as input a history list of game
boards (again, the history list is the same as the one passed to the
top-level "alquerque" function that you construct) and returns a list of
all possible game boards (not a list of all possible history lists of game
boards!) that can be generated by moving one piece of the appropriate color.
Obviously, this function will also need to know which color is going to move
next from that input board, else how will it know which pieces to move in
generating those moves? Call this function "move-generator".
3) Board converters - As we mentioned earlier, the board representation
that we've given you isn't necessarily what you want to use throughout your
program. If you want to use a different representation internally, that's
fine with us. But your program needs to talk to our programs using our
representation. So you'll need to provide two conversion functions. One
function converts our external board representation to your internal board
representation. Call this one "external-to-internal". The other function
converts your internal representation to our external representation. Call
this one (what else?) "internal-to-external". If you use our external
representation as your internal representation, you still have to provide
these functions, but they'll just return exactly what's passed to them as
input.
For this first part, we want you to stay entirely within the programming
guidelines that we used for the previous assignment, but you can add the
use of "let".
Then, by 8:00am, Monday, March 9, we'd like to see your entire Alquerque
program -- minimax search, alpha-beta pruning if you want to give it a try,
plus your move generator, board evaluator, board converters, and anything
else you might need to create -- all merged into one lean mean Alquerque
machine. And although those constraints on how you program your board
evaluator, move generator, and board converters still apply, you can use
any and all side effects for the other stuff, just so long as you don't do
the stupid things we warned you about in class today.
Some extra notes:
1) We'll be refining specifications as we go. You can expect detailed
interface specifications for the board evaluator, move generator,
and board converters to be posted by the TAs by Thursday night.
And we may forget something. So try to be flexible. Don't whine.
2) A static board evaluation function is exactly that -- static. It
doesn't search ahead. Ever.
3) As mentioned previously, 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, move generator, board
converters, and 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'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 an upcoming lab).
5) Do not redefine existing LISP functions. Before you "invent" a
function name, make sure that LISP doesn't already use that name.
In particular, the name "eval" is already taken...don't use it.
(Here's a fun experiment you can try at home. Redefine the
function "eval" then try to do something useful in LISP.
Make sure you know how to reboot your machine if necessary.)
6) Program early and often. The board evaluator is easy in comparison
to the rest of the stuff. Get the board evaluator out of the way in
a hurry, then start working on the rest of it as soon as you can.
Once you get the rest of it working, you can 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. Make sure you
call this function "alquerque". It will make life easier for
the TAs.
8) Before writing any code, play the game a few times. All you TAs out
there should play a few games too.
9) Just for the sake of accuracy, you should know that we've modified
the Alquerque rules somewhat. For example, we've eliminated the
rule that says that you can make multiple jumps in the same move
(as is allowed by checkers). That should make your move generator
a bit easier to construct, although it does water the game down at
the same time. We've also eliminated the rule that requires a
player to make a jump if one is possible (again as in checkers) or
forfeit a piece. Again a simplification that works to your benefit,
but at the same time changes the strategy.
Copyright 1998 by Kurt Eiselt, except where already copyrighted by the
authors of the books that we borrowed all this Alquerque stuff from ("Board
and Table Games from Many Civilizations" by R.C. Bell, and "Board Games
Round the World" by Robbie Bell and Michael Cornelius).
Last revised: February 27, 1998