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.jar file from the directory
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
OthPlayerthat computes the next move by randomly pick a move from the set of legal moves.
SmartPlayer.java-- a skeleton concrete subclass of
OthPlayerthat 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
so that it can compute the next move using the min-max principle discussed in
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
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.
OthManageris smart enough to take care of this case and will let the other player make the next move instead.
boardStatus[x][y] has only 3 possible values:
yis occupied by the black or white player or just empty. (Note: we consistently use
xto indicate row and
yto indicate column. This is also the case for
Your job is to find the best move by evaluating the passed-in
boardStatus and return a
You will find the following methods useful:
OthManager.GetLegalMovesto compute all the immediate legal moves. This returns a
OthMoves. A Java
Vectoris much like an array -- see the Java API for details.
OthManager.GetBoardStatusto 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
playerColorindicates the color of the next move. The parameter
depthis the number of moves ahead the min-max analysis should look. At the specified depth, you would use
Once you have this implemented, make sure
eval() instead of
Review of min-max:
A min-max analysis examines the game tree
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
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
To test your player with the rest of the system, you should model
main method in
to hook up two machine players or one machine player against human
and play the game.
DumbPlayer.java, use the Unix command
javac -classpath .:Othello.jar players/DumbPlayer.javaTo run the
DumbPlayerand get a white random machine player to play against human player, use the Unix command
java -classpath .:Othello.jar players.DumbPlayerYour
SmartPlayershould be compiled and executed in the same manner.
Submit the project electronically by the deadline using project name
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.
is a script to play two programs against each other.
To play, copy your
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