Comp 212 Programming Assignment #3
An Othello Player
Due 99.December.5 at 11:59:59 P.M. (Sunday night)
After returning from a recent trip to Las Vegas, J. H. Acker decided to abandon the electronic calendar business and start producing game playing programs. His first product is a program to play Othello. Acker plan to participate in an Othello tournament during the final week of the semester.
Othello is played on a conventioal 8-by-8 ``checker'' board, which initially has two white and two black pieces in the center four squares with the white pieces and black pieces aligned diagonally.
There are two players, black and white, and they alternate turns. Black moves first by placing a black 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. On each turn, a piece must be placed so that it brackets one or more opposing pieces: 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, the course staff is providing 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 *.class and *.java files from the link Othello.
Click here for documentation in JavaDoc.
OthBoard.class -- the GUI view to displays the Othello
board.
OthEngine.class -- the model to monitor chessboard status
and carry out moves.
OthManager.class -- controller to coordinate
machine/machine and machine/human players to play the Othello 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.
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.
You need not concern yourself with the nested classes.
Here is the UML diagram of the design.
You are given a skeleton concrete subclass of OthPlayer called SmartPlayer, and your assignment is to write 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 spelling of given methods. Feel free to add private methods to SmartPlayer to get the job done.
We suggest that you write your SmartPlayer class in phases.
Write the code for the protected method int evalBoard (int[][] boardStatus, int playerColor) that assigns a value to a board configuration according some "smart" rule. An example of such a rule 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 your color as follows: multiply each square's weight by 1 if it occupied by a piece of your color and -1 if it is occupied by a piece of the opposing color, add all the square weights together. The initial board configuration obviously has a score of 0.
The method OthMove nextMove(...) selects 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.
Write the code for the protected method int eval(int[][] boardStatus,int depth, in 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 variable depth determines how many moves ahead the ``min-max'' analysis looks.
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 analyis 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 postion to the opposing side).
You program should not try to construct the entire game tree to the specified depth. I should simply generate nodes on demand as needed to perform the min-max analysis.
In debugging your program, I recommend setting depth to very small values (say 1 and 2) so the amount of data involved in manageable.
Your course staff have been trying hard to modularize the supporting library in a way to simplify your job to interface with it. Although we provide the UML diagram here for your understanding of what's going on under the hood, what you really need to concern is the NextMove abstract method in OthPlayer. This method takes 2D int array board_status[][] as input, in which any board_status[x][y] has only 3 possible values: OthPlayer.BLACK, OthPlayer.WHITE, OthPlayer.EMPTY, indicating the board cell at row 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 board_status and return a OthMove object. Other part of the library is essentially irrelevant in this purpose.
For the convenience of debugging, we always dump a textual representation of the current change to board status to stdout. You may redirect it to a file when you develop your game strategy.
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. Try command java DumbPlayer to get a white random machine player to play against human player.
Stay tuned for electronic submission instruction.
We will hold an Othello computer game tournament during the week of the final 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.
After you submit your project, make a copy of it and work on this copy for the tournament. You will be given tournament instructions at a later date. You must notify your grader of your intention to participate in the tournament at the time of your project submission to qualify.
Enjoy!