meisterpropper

A highly modular Othello program based on the ESPRIT generic two player strategic game framework.

The ESPRIT Generic Two Player Strategic Game Framework

ServerGame starts a game at the server and then until end of the game repeats to get the game status and the current board from the server (Server.getBoard()), passes it to the player (Player.setBoard()) and commands the player to return a move (Player.move()) which is sent to the server again.

Board is the abstract representation of the status of a two player strategic game. Its subclasses must define all rules of the specific game (Board.getPossibleMove(), Board.isValidMove(), Board.isFinished()). Action represents a player's action which usually will contain a Move, but could be retirement or requesting a new game as well (if it is a human player).

The task of a Strategy (used by ComputerPlayer) is to calculate the "best" move on a given board. It may contain an "innerStrategy" to do parts of its work. meisterpropper for instance uses an OpeningStrategy that tries to find a move in its opening database. If it fails, it calls its inner strategy IterDepthStrategy that performs iterative deepening using aspiration window search (AspirationStrategy) with help of an alpha-beta search algorithm (NegaMaxStrategy) :-).

Last piece of the jigsaw puzzle: estimating the quality of a given board (rating).
To support multiple criterias when rating a board and different rating functions for different game phases, the actual Rater can be composed of multiple Raters like the LinearRater that combines several ratings into a weighted sum. The PhasesRater contains a set of raters for the different phases of a game.

meisterpropper feature description

Opening library

The opening library consists of roughly 300 boards with the recommended move(s) for each color. If several moves are possible one is chosen randomly.

Evaluated position characteristics

meisterpropper uses the following position characteristics to rate a board:
  1. disc difference
  2. stable disc difference
  3. actual mobility difference
  4. potential mobility difference
  5. corner penalty
  6. patterns
The rating of a board is a weighted sum of the values of these ratings. The weights have been set manually first and then been tuned by a genetic algorithm. They can be replaced easily for they are stored in an ini-file.

Game phases

meisterpropper plays in 15 phases of 4 moves each. Each phase has its special pattern valuations and weights. A statistic tuning of these weights has been tried with a database of roughly 100000 games, but has brought no improvements.

Iterative Deepening NegaMax search strategy

meisterpropper uses iterative deepening on NegaMax to search for the best move. In each depth the moves are sorted by their cut probability. The maximum depth depends on the amount of time granted by a sinus shaped time controlling function (approximated by a parabola). On a Pentium 166 under Windows NT the maximum depth in a 5 minute game grows from 4 to 9 during the game.

Game finalization

Every turn meisterpropper estimates the number of boards that are left until game's end dependent on the actual mobility. If it is less than the estimated number of boards that can be evaluated in the total remaining time, it calculates all moves until game's end and maximizes the game result. On a Pentium 166 under Windows NT this final depth is about 14 in a 5 minute game.

Code example

The following code, method isValidMove out of class OthelloBoard, checks whether the player on turn can move to position (row,col): 

  public boolean isValidMove(int row, int col) {
    int arow, acol;
    byte piece;
    
    if (board[row][col] != NONE) return false;

    // look in upper direction
    arow = row-1;
    if (arow>0 && isEnemyPieceAt(arow, col)) {
      for(;;) {
	--arow;
	if (arow<0 || (piece = board[arow][col]) == NONE) break;
	if (isOwnPiece(turn,piece))  return true;
      }
    }

    // look in lower direction
    arow = row+1;
    if (arow<rows-1 && isEnemyPieceAt(arow, col)) {
      for(;;) {
	++arow;
	if (arow>=rows || (piece = board[arow][col]) == NONE) break;
	if (isOwnPiece(turn,piece)) return true;
      }
    }

    // look in left direction
    acol = col-1;
    if (acol>0 && isEnemyPieceAt(row, acol)) {
      for(;;) {
	--acol;
	if (acol<0 || (piece = board[row][acol]) == NONE) break;
	if (isOwnPiece(turn,piece))  return true;
      }																	
    }

    // look in right direction
    acol = col+1;
    if (acol<cols-1 && isEnemyPieceAt(row, acol)) {
      for(;;) {
	++acol;
	if (acol>=cols || (piece = board[row][acol]) == NONE) break;
	if (isOwnPiece(turn,piece))  return true;
      }
    }

    // look in left upper direction
    arow = row-1;
    acol = col-1;
    if (arow>0 && acol>0 && isEnemyPieceAt(arow, acol)) {
      for(;;) {
	--arow;
	--acol;
	if (arow<0 || acol<0 || (piece = board[arow][acol]) == NONE) break;
	if (isOwnPiece(turn,piece))  return true;
      }
    }
    
    // look in right upper direction
    arow = row+1;
    acol = col-1;
    if (arow<rows-1 && acol>0 && isEnemyPieceAt(arow, acol)) {
      for(;;) {
	++arow;
	--acol;
	if (arow>=rows || acol<0 || (piece = board[arow][acol]) == NONE) break;
	if (isOwnPiece(turn,piece))  return true;
      }
    }
    
    // look in right lower direction
    arow = row+1;
    acol = col+1;
    if (arow<rows-1 && acol<cols-1 && isEnemyPieceAt(arow, acol)) {
      for(;;) {
	++arow;
	++acol;
	if (arow>=rows || acol>=cols || (piece = board[arow][acol]) == NONE) break;
	if (isOwnPiece(turn,piece))  return true;
      }
    }
    
    // look in left lower direction
    arow = row-1;
    acol = col+1;
    if (arow>0 && acol<cols-1 && isEnemyPieceAt(arow, acol)) {
      for(;;) {
	--arow;
	++acol;
	if (arow<0 || acol>=cols || (piece = board[arow][acol]) == NONE) break;
	if (isOwnPiece(turn,piece))  return true;
      }
    }

    return false;
  }
Last Modified: 1998/02/21
ESPRIT (Andreas Abel & Peter Buchmann)