CS 2360
Summer 1998
Homework Assignments 6 and 7
Assignment 6 is due no later than 8:00am, Tuesday, August 11, 1998
Assignment 7 is due no later than 8:00am, Tuesday, August 18, 1998
Click here to see the "revision history" of
the assignment.
Note that changes in the text of the assignment
appear in bold text.
In the past few quarters, CS 2360 has had students write some rather
exotic (and often made-up) board games. This quarter we shall try
something a little more familar: checkers. Actually, we've cooked up
our own modified version of checkers just for you, so perhaps the game
_will_ seem a little strange.
The Rules
The rules are as follows. The board is played on an NxN grid of
squares (N>4), or rather, half of the squares on such a grid. Each
player starts with two rows of checkers of his color, on alternating
squares in the back two rows of the board. For example, if N=5 or N=6,
the initial board configurations would be:
N=5 N=6
W W W W W W
W W W W W
- - - - - -
B B - - -
B B B B B B
B B B
Notice that the upper-left square is always occupied by a white piece.
Moves
White moves first. On each move, a player can do one of two things:
move or jump. A move happens by sliding a checker forward to one of
the two next squares on the diagonal. For example, on the board below
Board Labels (for discussion below)
W - - 1 2 3
- - 4 5
- - - 6 7 8
W B 9 10
- - - 11 12 13
White could move his checker from 9 to either 11 or 12. His checker at
1 has only one legal move: 4. Black can move his checker at 10 to
either 7 or 8. So, if it were black's turn in the board above, and he
chose to move 10-7, the board would then look like:
W - -
- -
- B -
W -
- - -
Simple enough, right?
Jumps
The other type of move is a jump. Jumps allow you to capture an
opponent's piece. If an opponent occupies a square that you could move
to if it were empty, and the square behind that one (in the same
direction) is empty, then you can jump over your opponent and capture
his piece. For example, if the board looked like this:
W - -
W W
- B -
B -
- - -
then white has exactly one legal jump (along with a couple other
legal moves). If white jumps, the board would look like this:
W - -
- W
- - -
B W
- - -
White jumped from square 4 to 10 (using the labels above), jumping over
and capturing his opponent's piece at square 7.
One can only jump a single piece during a turn. Only the opponent's
pieces can be jumped. The square one "lands on" must be empty prior to
jumping. Multiple jumps on one turn are not allowed.
Kings
In addition to these basic rules for moving, pieces may be "promoted"
into "kings" if they reach the other side of the board. We shall label
these promoted pieces as follows:
White kings: X
Black kings: C
which were chosen as the next-highest letters of the alphabet for their
normal-checker counterparts, to make the letters easy for you to
remember. Kings move just like normal checkers except that they may
move and jump both forwards _and_ backwards. Thus, in the boards
below, the black piece at the center can get to any of the positions
marked with asterisks on his next turn:
- - * - - *
* X * X
- B - - C -
- W * W
- - - - - *
Note that the black checker at the center of the left board can only
move forward, while the black king at the center of the right board can
move forward or backward.
Any piece (kings or normal checkers) can capture any other opponent's
piece (kings or checkers) during a legal move. (That is, there are no
restrictions like "only kings can capture other kings".)
Winning
A player wins the game by doing one of the following:
(1) capturing all of his opponent's pieces
(2) leaving his opponent with no legal moves
(3) getting his king all the way back to his end of the board (that
is, making a round-trip across the board and back with a piece)
Each of these is demonstrated in a win for black below (move labelled
with an asterisk):
(1) (2) (3)
- - - W W - - - -
B * B B W W
- W - B * B - B X
B - - B C -
- - - - - - * B -
Black wins by Black wins by Black wins by
jumping white's sliding forward, moving his king
last piece leaving no moves back to his side
for white of the board
The representation
We've chosen a simple representation for boards. For example, the
boards below:
W W W - - -
W W W W
- - - - B X
B B C -
B B B - B -
would be represented as the lists
'(W W W W W - - - B B B B B)
and
'(- - - W W - B X C - - B -)
respectively.
This representation may not be the most convenient for you to work
with--indeed, there are probably many alternatives that are better.
You are free to convert this representation into your own
representation, so you may do all your processing with some other board
format. However all of our functions use this representation for
parameters and results, so if you use your own board representation,
you'll have to write conversion functions to convert your
representation to ours, and vice versa.
Finally--and this is _very_ important--your code should not contain any
explicit references to the symbols B C W X and -. Rather, you should
assume these definitions:
;; The pieces
(defconstant *white* 'w)
(defconstant *black* 'b)
(defconstant *white-king* 'x)
(defconstant *black-king* 'c)
(defconstant *blank* '-)
;; The players
(defconstant *white-player* 'wp)
(defconstant *black-player* 'bp)
You can effectively reference *white* and the rest as "global" constants
anywhere in your code. You should _not_ have values like 'w appear
anywhere in your code. If you do, your code won't work when we test it
out. The code examples in this assignment all use lists like
'(W W W W W - - - B B B B B)
to make things readable, but to be totally correct, the lists should
really be like
(list *white* *white* *white* *white* *white* *blank* *blank* *blank*
*black* *black* *black* *black* *black*)
Put another way, your code should continue to work if we decided to
change the symbol for a checker, for example
(defconstant *white* 'g) ; now "g" instead of "w"
If your code has lines like
(eql (first board) 'w) ; test to see if first checker is white
it would fail under the new definition, but if it were written
correctly
(eql (first board) *white*) ; test to see if first checker is white
then things will work, even if the constant is redefined. (This extra
layer of indirection is necessary to prevent symbol conflicts across
multiple packages.)
Your assignment
There will be a number of deliverables for this assignment:
- the board printer
- the static board evaluator
- the move generator
- the board conversion functions
- the minimax move selector
- (optionally) the minimax move selector with alpha-beta pruning
Each of these is described in more detail below.
The board printer
The board printer pretty-prints a board. Calling
(print-board '(W W W W W - - - B B B B B))
would print something that looks like
W W W
W W
- - -
B B
B B B
The static board evaluator
The static board evaluator takes three parameters: a board, a
point-of-view, and whose-turn, and evaluates the "goodness" of the
board from that person's point of view. It might be called like this:
(board-eval '(- - - W W - B X C - - B -) 'bp 'bp)
It should return a numerical estimate of the "goodness" of the board.
The scale you use (for instance, -10 to +10) is up to you.
The move generator
The move generator takes two parameters: a board and a "whose move"
parameter. It generates a list of all the possible "next board"
configurations. It might be called like this:
(move-gen '(W W W W W - - - B B B B B) 'wp)
and return a list of boards like so:
( (W W W - W W - - B B B B B)
(W W W - W - W - B B B B B)
(W W W W - - - W B B B B B)
(W W W W - - W - B B B B B) )
The board conversion functions
These functions convert your representation to ours, and vice-versa.
They might work like
(board-from their-rep) --> my-rep
(board-to my-rep) --> their-rep
The minimax move selector
This is the major piece of the assignment. It will be invoked as
follows:
(checkers '(W W W W W - - - B B B B B) 'wp 3 nil)
^ ^ ^ ^
| | | |
The first argument is the current board. | | |
| | |
The next argument tells whose turn it is.--+ | |
| |
The next argument tells how many moves ahead | |
your minimax search should look (the depth).--+ |
|
The final argument tells whether or not a trace |
should be printed. NIL=no trace, anything else |
(true) means you should print a trace. --+
If you get the whole assignment working, you can write another function
called "checkers-ec" which does minimax with alpha-beta pruning. This
is for extra credit, and will only be graded if the rest of the
assignment works.
The deliverables
This assignment is due in two parts: hw6 and hw7 (see due date/times at
the top of the assignment).
For part one (hw6), you must turn in your static board evaluation
function, your board printer, your move generator, and your board
conversion functions. 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.
For part two (hw7), you should turn in your entire checkers program,
including move generation, minimax, alpha-beta pruning if you like, and
your (possibly new and improved) static board evaluator. 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.
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.
Note that it may be simpler to have your board evaluator and move
generator expect your own representation as a parameter. Then you
can just "rig" a version to satisfy our needs, which simply calls
the conversion function to transform our board into your board and
then call your own version of the function.
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 "checkers". Nothing else
will do. If you do the extra credit, submit an additional program
called "checkers-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.