Comp 212 Spring 2001, Project 3: Othello

Due 27 Apr., 2001 at 11:59:59 P.M.

The Game

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.

Implementation

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/.

You need not concern yourself with the nested classes.

Here is the UML diagram of the design.

othello.png (22798 bytes)

Assignment

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:

  1. 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:

    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 boardStatus and return a OthMove object. You will find the following methods useful:

    Other parts of the library are essentially irrelevant in the purpose of computing the next move.

  2. 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.java
To run the DumbPlayer and get a white random machine player to play against human player, use the Unix command 
     java -classpath .:Othello.jar players.DumbPlayer
Your SmartPlayer should be compiled and executed in the same manner.

Turning it in

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.

Tournament

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 whiteID
Please 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.