Comp 212 Programming Assignment #3
An Othello Player
Due Dec 08, 2000 at 11:59:59 P.M. (Friday night)
Othello is played on a conventional 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, 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 *.java files and the Othello.jar file from the link Othello.
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 to get the job done. Do not change any of the java files in the given Othello package. Your code should run with the provided jar file.
We suggest you write your SmartPlayer class in two steps.
Write the code for the private method int evalBoard (int[][] boardStatus) 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 private 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 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 program should not try to construct the entire game tree to the specified depth. It 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.
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. You will find the following methods useful for your purpose.
Other parts of the library are essentially irrelevant in the purpose of computing the next "smart" move.
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.
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, enter the command (in Unix):
javac -classpath .:Othello.jar players/DumbPlayer.java
In Windows:
javac -classpath .;Othello.jar players\DumbPlayer.java
To run the DumbPlayer and get a white random machine player to play against human player, enter the command (in Unix):
java -classpath .:Othello.jar players.DumbPlayer
In Windows:
java -classpath .;Othello.jar players.DumbPlayer
Your SmartPlayer should be compiled and executed in the same manner.
The project is to be submitted electronically on or before Dec 08, 2000 at 11:59:59 P.M.. The complete project should contain the following:
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!