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
piece brings the player closer to having all of his or her pieces
removed from the board, thereby losing the game.
For your term project, you are to construct a CILOG proof procedure (and
many many supporting procedures, of course) which takes as arguments 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
procedure you have created, and an integer representing the number of moves
to look ahead. This predicate is true if the if the fourth argument
contains the best next move, represented as an Oska board, given the
values contained in the first three arguments. The format of the fourth
argument should be the same as the format for the first argument. Of
course, if the fourth argument is a variable, then CILOG would decide
which board meets these criteria and bind the representation of that
board to the variable. Your proof procedure must select the best next move
by using MiniMax search.
Assume for now that the name of your top-level procedure is "oskamaniac".
Your procedure must then be ready to accept exactly four arguments when
invoked. The sample invocation below and subsequent descriptions explain
in more detail what goes where in the argument list:
oskamaniac([[w,w,w,w],[e,e,e],[e,e],[e,e,e],[b,b,b,b]], /* first argument */
w, /* second argument */
2, /* third argument */
[[w,w,w,e],[e,e,w],[e,e],[e,e,e],[b,b,b,b]]). /* fourth argument */
The first argument is a list of five elements, with each element being
a list. Each of these sub-lists represents a row of the board. The first
sub-list is the first or "top" row of the Oska board, and itself contains
four elements. The second element is the next row, and contains three
elements. This is followed by a sub-list of two elements, then one with
three elements, and the last sub-list with four 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 e 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. (IMPORTANT NOTE: In the
PowerPoint slides for the term project, I inadvertently left out a lot of
the commas that are necessary in the CILOG list representation: I was
thinking CILOG but my fingers were typing Scheme. Sorry for the confusion.
Don't forget your commas to separate elements of a list.)
The second argument will always be w or b, to indicate whether your procedure
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 proof procedure had better not look any further
than that.
The fourth and last argument is the next best move as determined by your
Oska-playing proof procedure. So depending on how your static board evaluator
and your minimax search work, the next best move might be represented as:
[[w,w,w,e],[e,e,w],[e,e],[e,e,e],[b,b,b,b]]
or some other board in this same format. Thw result above corresponds to
the following diagram:
---------------
| W | W | W | |
---------------
| | | W |
-----------
| | |
-----------
| | | |
---------------
| B | B | B | B |
---------------
For purposes of satisfying the term project requirements, your Oska program
need only be able to play games in which there are four pieces on each side.
If you want to compete for prizes and glory as mentioned in class, your program
must be able to play competitive Oska on larger boards with five, six, or more
pieces on each side of the board. These more general Oska programs should detect
the size of the board from the board representation passed in the first argument.
So for those of you who are going above and beyond, 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 |
-------------------
Your term project, when completed, should be submitted through the handin program.
For handin purposes, this submission is named "term". Your CILOG code should be
organized so that the three main pieces (the minimax component, the board evaluation
component, and the move generation component) are easy to find and are clearly
separated. Documentation should include an overview of the whole program and how it
works, as well as more detailed descriptions of the three main pieces listed above.
In addition, you are to include a "CILOG wish list" -- a descriptive list of not
only the features or abilities that you wish had been included in CILOG while you
were working on your term project, but also those shortcomings or problems you
encountered that you wish could be fixed before the next generation of CPSC 322
students become CILOG programmers. I'll forward those wish lists, without
identifying the specific authors, to the CILOG gurus. While we're talking about it,
add one other thing to the pile of stuff you submit through handin: turn in a
transcript of your Oska program playing against itself. You don't have to construct
yet another program to make that happen; just type in the queries manually and
show us what happens.
As mentioned in class, you can work on this project individually, or in teams of
two if you've sent me electronic mail telling me who you're paired with, but you
cannot work in larger groups. To repeat, you may work with a partner if you or your
partner have let me know that you are a team, but then neither you nor your partner
may work with anyone else on this term project. If you have not informed me that
you are working with a partner, then you must work on this project alone. This
collaboration policy will be strictly enforced on this term project, and failure
to abide by this policy will be dealt with as a case of academic misconduct.
Some extra notes:
1) We may need to modify the specifications a bit here or there in case
we forgot something. Expect that you might have 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 top level procedure or it talks to us,
that procedure is using our 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, and we'd like to see it if you do write one, but it's not
a requirement.)
5) It is possible (and in the case of the people who are going to try to tackle
the variable-size-board problem, it's extremely likely) that we'll load your
CILOG program alongside somebody else's program and attempt to have them play
each other. That, however, opens up the possibility of conflicts caused by
having the same predicate names used by different programs. For example, if
both of you call your top-level procedure "oskamaniac", then which how will
CILOG know which one I intend to invoke when I type "ask oskamaniac([....."?
Here's our crude and tedious solution to this problem: stick a unique suffix
on the end of every CILOG predicate you create, and use the same suffix
throughout your CILOG program. For example, instead of "oskamaniac", you could
add your UBC CS undergrad email address to the end of the predicate names, like
this: "oskamaniac_a1b2". It's a pain, I know, but I don't know a better way
to get around this problem in this particular environment.
6) You don't have to call your top-level program "oskamaniac". It's just an
example. Please, call it something else. Be creative, be different, but
be something other than "oskamaniac". And it should go without saying, but
just in case, don't be rude or offensive...it's possible that other people in
the CS department will see these programs, so don't give them a reason to
remember you in a negative way.
7) As a reminder, white always starts on the top row of the Oska board, and
white always makes the first move of the game.
8) Program early and often.
9) Before writing any code, play the game a few times.
10) 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.
11) You'll get other small homework assignments while you're working on
the term project. Remain calm. Don't panic. And don't let it deter you from
becoming the 2004 (and most likely first ever) Computer Oska Champion
of Canada.
Copyright 2004 by Kurt Eiselt, except where already copyrighted
by Bryn Jones and Michael Woodward, the creators of Oska. All remaining
rights reserved, not that there would be many.
Last revised: November 8, 2004