Due 27 Apr., 2001 at 11:59:59 P.M.
Othello is played on a conventional 8-by-8 board of alternating colors, as in checkers or chess.
There are two players, black and white, and they alternate turns, starting with black. Initially, the board has two white and two black pieces in the center four squares, aligned diagonally. On each turn, a player places a piece on the board. No piece can be moved once it is placed, but later moves can flip the color of a piece on the board. A piece must be placed so that it brackets one or more opposing pieces: i.e., there must be a vertical, horizontal, or diagonal line that goes through the piece just placed, through one or more opponent pieces (no empty squares in between), and finally through a piece of the same color as the one just placed. The bracketed opposing pieces are flipped to the other color. A player who does not have a legal move must pass. The game ends when neither player can move, and the player with the most pieces on the board wins.
For a more complete description of the rules of Othello including illustrations, consult the following web page.
For this project, we provide you with the following classes to manage
the playing of an Othello game including set up, processing inputs
submitted by the players, and displaying
the status of the board. Copy all the Othello
package
and the Othello.jar
file from the directory
~comp212/public_html/01-spring/assignments/othello/
.
OthBoard.java
-- the GUI view to displays the board.
OthEngine.java
-- the model to monitor board status and carry out moves.
OthManager.java
-- controller to coordinate
machine/machine and machine/human players to play the game.
OthMove.java
-- to represent an Othello board move.
OthPlayer.java
-- to represent an abstract Othello player capable of computing
the next move based on the current board status.
Othello.jar
-- the Java archive compiled code for all of the above classes.
The above source code is provided for you to study only. Do
not modify any of the above classes.
DumbPlayer.java
-- an example of a concrete subclass of OthPlayer
that computes the next move by randomly pick a move
from the set of legal moves.
SmartPlayer.java
-- a skeleton concrete subclass of OthPlayer
that knows how to evaluate the board in order to make the next move.
You need not concern yourself with the nested classes.
Here is the UML diagram of the design.
Your assignment is to write the code for SmartPlayer
so that it can compute the next move using the min-max principle discussed in
class. Use DumbPlayer
as an example. Do
not change any of the public methods of the classes provided to you.
Feel free to modify and add private methods to
SmartPlayer
, but change no other files.
Your code should run with the provided jar file.
We suggest you write your SmartPlayer
class in two steps:
Write the private method
int evalBoard(int[][] boardStatus)that assigns a value to a board configuration according some "smart" heuristic.
An example of such a heuristic is as follows. Assign each
square board[i][j]
a weight of your choosing.
The four corner squares are most valuable and edge squares are
more valuable than interior squares.
A weight of 8 for corner squares, 2 for edge squares,
and 1 for all other squares is a reasonable choice.
Compute a score that measures how favorable the given board
is for you by multiplying each square's weight by 1 if it
occupied by your piece, and -1 if it is occupied by an opposing
piece, and adding all these together.
The initial board configuration obviously has a score of 0.
Write the method
OthMove NextMove(int[][] boardStatus)to select your next move by evaluating the merit of each legal moves and evaluating their merit using
evalBoard()
.
Note that there may be no legal move. OthManager
is smart
enough to take care of this case and will let the other
player make the next move instead.
Each boardStatus[x][y]
has only 3 possible values:
OthPlayer.BLACK
,
OthPlayer.WHITE
, or
OthPlayer.EMPTY
,
x
and column
y
is occupied by the black or white player or just empty.
(Note: we consistently use x
to indicate row and
y
to indicate column. This is also the case for
OthMove
.)
Your job is to find the best move by evaluating the passed-in
boardStatus
and return a OthMove
object.
You will find the following methods useful:
OthManager.GetLegalMoves
to compute all the
immediate legal moves. This returns a
java.util.Vector
of OthMove
s.
A Java Vector
is much like an array -- see
the Java API for details.
OthManager.GetBoardStatus
to inquire the
current board configuration.
Write the private method
int eval(OthEngine engine, int depth, int playerColor)to evaluate the board position from your player's point of view using a bounded version on the ``min-max'' game tree analysis discussed in class. The parameter
playerColor
indicates the color of the next move. The parameter
depth
is the number of moves ahead the
min-max analysis should look. At the specified depth, you
would use evalBoard()
.
Once you have this implemented, make sure NextMove()
uses eval()
instead of evalBoard()
as
suggested above.
Review of min-max:
A min-max analysis examines the game tree depth
levels (moves) beyond the current position, evaluates the
resulting board positions, and assigns values to the various
intermediate board positions by ``backing-up'' the
best-achievable value from the set of succeeding board positions.
The analysis assumes that you always choose the maximum
achievable score from your available moves and the opponent
always chooses the minimum achievable score from its available
moves. Recall that the board scoring system measures the
favorability of the position to your side (which is exactly
the opposite of the favorability of the position to the opposing
side).
You must use min-max.
You may use alpha-beta pruning to improve its performance.
Your program should not construct the entire game tree
to the specified depth. It should simply generate nodes on
demand as needed to perform the min-max analysis.
When generating new positions, you will find the method
OthManager.GetEngineCopy
useful, as it clones
the model so that you don't change current game board.
In debugging your program, we recommend setting depth to very small values (say 1 and 2) so the amount of data involved is manageable.
For the convenience of debugging, we always dump a textual representation of the current change to board status to the standard output. You may redirect it to a file when you develop your game strategy.
While debugging, you may want to give your program more time to look
for a move. You can do this by changing the code and increasing the
value of OthManager.Timer.MOVE_TIME
.
To test your player with the rest of the system, you should model
the main
method in DumbPlayer
,
using the PlayOthello
or
PlayOthelloWithHuman
in OthManager
to hook up two machine players or one machine player against human
and play the game.
To compile DumbPlayer.java
, use the Unix command
javac -classpath .:Othello.jar players/DumbPlayer.javaTo run the
DumbPlayer
and get a white random machine
player to play against human player, use the Unix command
java -classpath .:Othello.jar players.DumbPlayerYour
SmartPlayer
should be compiled and executed in the
same manner.
Submit the project electronically by the deadline using project name
othello
.
You do not need to submit a UML diagram, since we've provided that.
Be sure to check back later. The following details may change.
We will hold an Othello computer game tournament during the finals week to determine the best game evaluation strategy. Tournament participation is optional and does not affect your grade in any negative way. The first place winner will get a full letter grade added to the final grade. The second place winner will get two third (2/3) of a letter grade added to the final grade. The third place winner will get one third (1/3) of a letter grade added to the final grade.
You may continue to work on your project after the official deadline but before the tournament starts. After you submit your project, make a copy of it and work on this copy for the tournament.
~comp212/public_html/01-spring/assignments/othello/tournament/game
is a script to play two programs against each other.
To play, copy your OthPlayer.class
to
~comp212/public_html/01-spring/assignments/othello/tournament/players/yourID/yourIDPlayer.class
.
You have permission to create your own directory there.
(To protect against cheating, don't copy your .java file.)
To have two programs compete, use
game blackID whiteIDPlease only submit working programs to the tournament!
The limit for each move is 15 seconds on an Sun UltraSparc 10 in the back of Ryon 102. If your program is too slow, it loses.
The tournmaent details will depend on how many students enter.
We will divide players into groups for a first round-robin.
Leaders will move on to a second round-robin.
We will put all results into the
~comp212/public_html/01-spring/assignments/othello/tournament/
directory.