CS 2360
Winter 1997
Homework Assignments 6 and 7
Assignment 6 is due no later than 8:00am, Wednesday, February 26, 1997
Assignment 7 is due no later than 8:00am, Wednesday, March 5, 1997
Consider the game of Oska, whose rules are as follows:
Oska is played on a board like that shown below. The two players face
each other across the board. Each player begins with four pieces, placed
one to a square in each of the four squares nearest that player.
---------------
| W | W | W | W |
---------------
| | | |
-----------
| | |
-----------
| | | |
---------------
| B | B | B | B |
---------------
The player with the white pieces makes the first move, and the players
alternate moves after that. A player may choose to move one of his or
her pieces in one of these ways:
A piece may be moved forward on the diagonal, one space at a time,
to an empty space, as in checkers or draughts.
A piece may jump forward on the diagonal over an opponent's piece
to an empty space, thereby capturing the opponent's piece and
removing it from the board. This capturing move is again like that
seen in checkers or draughts. Unlike checkers, however, only a
single capture is permitted on one turn; multiple jumps are not
allowed. Also, even if a capture is possible, it does not have to
be made if other moves are possible.
The players alternate moving pieces until one of the players wins. If
a player can't make a legal move on a given turn, the player loses that
turn and the opponent makes another move. A player wins when:
All the opponent's pieces have been removed from the board, or
All the player's REMAINING pieces have been moved to the opponent's
starting (or back) row. Note that this rule makes the strategy for
this game most interesting. A player may want to sacrifice pieces
in order to have fewer pieces to move to the opponent's starting
row. But this approach carries some risk in that every sacrificed
brings the player closer to having all of his or her pieces
removed from the board, thereby losing the game.
As envisioned by its inventor, Bryn Jones (with refinements by Michael
Woodward, who has now made this charming game available commercially),
the game of Oska was intended to be played with only four pieces on
each side. Now, however, we are extending the definition of Oska to
include any similar game involving n white pieces, n black pieces, and
a correspondingly larger board of 2n - 3 rows (where n is greater than
or equal to 4). Thus, an Oska game with 5 pieces on each side would
look like this:
--- --- --- --- ---
| W | W | W | W | W |
-------------------
| | | | |
---------------
| | | |
-----------
| | |
-----------
| | | |
---------------
| | | | |
-------------------
| B | B | B | B | B |
-------------------
Over the next two weeks, you are to construct a Common LISP function which
takes as input a representation of the state of an Oska game (i.e., a board
position), an indication as to which color (black or white) is being
played by the function you have created, 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 an Oska 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. 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 "oskamaniac". Your
function must then be ready to accept exactly four parameters when called. The
sample function call explains what goes where in the argument list:
(oskamaniac '((w w w w)(nil nil nil)(nil nil)(nil nil nil)(b b b b))
'w 2 nil)
^ ^ ^ ^
| | | |
The first argument is an list of 2n - 3, | | |
elements. Each of these elements is | | |
a row of the board. The first element | | |
is the first or "top" row, and contains | | |
n elements. The second element is the | | |
next row, and contains n - 1 elements. | | |
The elements of each of these sub- | | |
lists are either w to indicate a white | | |
piece on that square, b to indicate a | | |
black piece, or nil to indicate 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 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 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 w w nil)(nil nil w)(nil nil)(nil nil nil)(b b b b))
or some other board in this same format. That result corresponds to
the following diagram:
---------------
| W | W | W | |
---------------
| | | W |
-----------
| | |
-----------
| | | |
---------------
| 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 by 8:00am, Wednesday, February 26.
You can make upgrades to it after that, but you must turn in a credible working
version by 8:00am, February 26. 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 pieces and the higher numbers should correspond to
boards that are favorable to black) and which side is supposed to move next.
The code for your board evaluation function must adhere to functional
programming guidelines.
Then, by 8:00am, Wednesday, March 5, we'd like to see your entire Oska 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 Oska-playing machine. After the upcoming exam, you'll be allowed to take
advantage of some side effects, and you can use those non-functional
programming techniques on everything but the static board evaluation function.
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 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'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.
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 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 "oskamaniac"---try to be at least a little bit creative.
8) Before writing any code, play the game a few times. All you TAs out
there should play a few games too.
9) If the final move of the game leaves both players with all their
remaining pieces on their opponent's starting (or back) row, the
player with the most pieces remaining wins. If both players have
the same number of pieces, the game is a draw.
Copyright 1997 by Kurt Eiselt, except where already copyrighted
by Bryn Jones and Michael Woodward. All remaining rights reserved,
not that there would be many.
Last revised: February 20, 1997