tdegames/kreversi/Engine.cpp

/* Yo Emacs, this -*- C++ -*-
 *******************************************************************
 *******************************************************************
 *
 *
 * KREVERSI
 *
 *
 *******************************************************************
 *
 * A Reversi (or sometimes called Othello) game
 *
 *******************************************************************
 *
 * Created 1997 by Mario Weilguni <mweilguni@sime.com>. This file
 * is ported from Mats Luthman's <Mats.Luthman@sylog.se> JAVA applet.
 * Many thanks to Mr. Luthman who has allowed me to put this port
 * under the GNU GPL. Without his wonderful game engine kreversi
 * would be just another of those Reversi programs a five year old
 * child could beat easily. But with it it's a worthy opponent!
 *
 * If you are interested on the JAVA applet of Mr. Luthman take a
 * look at http://www.sylog.se/~mats/
 *
 *******************************************************************
 *
 * This file is part of the KDE project "KREVERSI"
 *
 * KREVERSI is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2, or (at your option)
 * any later version.
 *
 * KREVERSI is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with KREVERSI; see the file COPYING.  If not, write to
 * the Free Software Foundation, 51 Franklin Street, Fifth Floor,
 * Boston, MA 02110-1301, USA.
 *
 *******************************************************************
 */

// The class Engine produces moves from a Game object through calls to the
// function ComputeMove().
//
// First of all: this is meant to be a simple example of a game playing
// program. Not everything is done in the most clever way, particularly not
// the way the moves are searched, but it is hopefully made in a way that makes
// it easy to understand. The function ComputeMove2() that does all the work
// is actually not much more than a hundred lines. Much could be done to
// make the search faster though, I'm perfectly aware of that. Feel free
// to experiment.
//
// The method used to generate the moves is called minimax tree search with
// alpha-beta pruning to a fixed depth. In short this means that all possible
// moves a predefined number of moves ahead are either searched or refuted
// with a method called alpha-beta pruning. A more thorough explanation of
// this method could be found at the world wide web at http:
// //yoda.cis.temple.edu:8080/UGAIWWW/lectures96/search/minimax/alpha-beta.html
// at the time this was written. Searching for "minimax" would also point
// you to information on this subject. It is probably possible to understand
// this method by reading the source code though, it is not that complicated.
//
// At every leaf node at the search tree, the resulting position is evaluated.
// Two things are considered when evaluating a position: the number of pieces
// of each color and at which squares the pieces are located. Pieces at the
// corners are valuable and give a high value, and having pieces at squares
// next to a corner is not very good and they give a lower value. In the
// beginning of a game it is more important to have pieces on "good" squares,
// but towards the end the total number of pieces of each color is given a
// higher weight. Other things, like how many legal moves that can be made in a
// position, and the number of pieces that can never be turned would probably
// make the program stronger if they were considered in evaluating a position,
// but that would make things more complicated (this was meant to be very
// simple example) and would also slow down computation (considerably?).
//
// The member m_board[10][10]) holds the current position during the
// computation. It is initiated at the start of ComputeMove() and
// every move that is made during the search is made on this board. It should
// be noted that 1 to 8 is used for the actual board, but 0 and 9 can be
// used too (they are always empty). This is practical when turning pieces
// when moves are made on the board. Every piece that is put on the board
// or turned is saved in the stack m_squarestack (see class SquareStack) so
// every move can easily be reversed after the search in a node is completed.
//
// The member m_bc_board[][] holds board control values for each square
// and is initiated by a call to the function private void SetupBcBoard()
// from Engines constructor. It is used in evaluation of positions except
// when the game tree is searched all the way to the end of the game.
//
// The two members m_coord_bit[9][9] and m_neighbor_bits[9][9] are used to
// speed up the tree search. This goes against the principle of keeping things
// simple, but to understand the program you do not need to understand them
// at all. They are there to make it possible to throw away moves where
// the piece that is played is not adjacent to a piece of opposite color
// at an early stage (because they could never be legal). It should be
// pointed out that not all moves that pass this test are legal, there will
// just be fewer moves that have to be tested in a more time consuming way.
//
// There are also two other members that should be mentioned: Score m_score
// and Score m_bc_score. They hold the number of pieces of each color and
// the sum of the board control values for each color during the search
// (this is faster than counting at every leaf node).
//

// The classes SquareStackEntry and SquareStack implement a
// stack that is used by Engine to store pieces that are turned during
// searching (see ComputeMove()).
//
// The class MoveAndValue is used by Engine to store all possible moves
// at the first level and the values that were calculated for them.
// This makes it possible to select a random move among those with equal
// or nearly equal value after the search is completed.


#include <tqapplication.h>

#include "Engine.h"


// ================================================================
//                          Class ULONG64


#if !defined(__GNUC__)


ULONG64::ULONG64() : TQBitArray(64) 
{
  fill(0);
}


// Initialize an ULONG64 from a 32 bit value.
//

ULONG64::ULONG64( unsigned int value ) : TQBitArray(64) 
{
  fill(0);
  for(int i = 0; i < 32; i++) {
    setBit(i, (bool)(value & 1));
    value >>= 1;
  }
}


// Shift an ULONG64 left one bit.
//

void ULONG64::shl() 
{
  for(int i = 63; i > 0; i--)
    setBit(i, testBit(i - 1));
  setBit(0, 0);
}

#endif


// ================================================================
//           Classes SquareStackEntry and SquareStack


// A SquareStack is used to store changes to the squares on the board
// during search.


inline void SquareStackEntry::setXY(int x, int y) {
  m_x = x;
  m_y = y;
}


SquareStackEntry::SquareStackEntry()
{
  setXY(0,0);
}


// ----------------------------------------------------------------


SquareStack::SquareStack() {
  init(0);
}


SquareStack::SquareStack(int size) {
  init(size);
}


void SquareStack::resize(int size) 
{
  m_squarestack.resize(size);
}


// (Re)initialize the stack so that is empty, and at the same time
// resize it to 'size'.
//

void SquareStack::init(int size) 
{
  resize(size);

  m_top = 0;
  for (int i = 0; i < size; i++)
    m_squarestack[i].setXY(0,0);
}



inline SquareStackEntry SquareStack::Pop() 
{
  return m_squarestack[--m_top];
}


inline void SquareStack::Push(int x, int y)
{
  m_squarestack[m_top].m_x = x;
  m_squarestack[m_top++].m_y = y;
}


// ================================================================
//                       Class MoveAndValue


// Class MoveAndValue aggregates a move with its value.
//


inline void MoveAndValue::setXYV(int x, int y, int value) 
{
  m_x     = x;
  m_y     = y;
  m_value = value;
}


MoveAndValue::MoveAndValue() 
{
  setXYV(0,0,0);
}


MoveAndValue::MoveAndValue(int x, int y, int value) 
{
  setXYV(x, y, value);
}


// ================================================================
//                        The Engine itself


// Some special values used in the search.
const int Engine::LARGEINT      = 99999;
const int Engine::ILLEGAL_VALUE = 8888888;
const int Engine::BC_WEIGHT     = 3;


Engine::Engine(int st, int sd) : SuperEngine(st, sd) 
{
  SetupBcBoard();
  SetupBits();
}


Engine::Engine(int st) : SuperEngine(st) 
{
  SetupBcBoard();
  SetupBits();
}


Engine::Engine() : SuperEngine(1) 
{
  SetupBcBoard();
  SetupBits();
}


// keep GUI alive
void Engine::yield() 
{
  tqApp->processEvents();
}


// Calculate the best move from the current position, and return it.

Move Engine::computeMove(Game *game, bool competitive) 
{
  Color color;

  // A competitive game is one where we try our damnedest to make the
  // best move.  The opposite is a casual game where the engine might
  // make "a mistake".  The idea behind this is not to scare away
  // newbies.  The member m_competitive is used during search for this
  // very move.
  m_competitive = competitive;

  // Suppose that we should give a heuristic evaluation.  If we are
  // close to the end of the game we can make an exhaustive search,
  // but that case is determined further down.
  m_exhaustive = false;

  // Get the color to calculate the move for.
  color = game->toMove();
  if (color == Nobody)
    return Move(Nobody, -1, -1);

  // Figure out the current score
  m_score.set(White, game->score(White));
  m_score.set(Black, game->score(Black));

  // Treat the first move as a special case (we can basically just
  // pick a move at random).
  if (m_score.score(White) + m_score.score(Black) == 4)
    return ComputeFirstMove(game);

  // Let there be room for 3000 changes during the recursive search.
  // This is more than will ever be needed.
  m_squarestack.init(3000);

  // Get the search depth.  If we are close to the end of the game,
  // the number of possible moves goes down, so we can search deeper
  // without using more time.  
  m_depth = m_strength;
  if (m_score.score(White) + m_score.score(Black) + m_depth + 3 >= 64)
    m_depth = 64 - m_score.score(White) - m_score.score(Black);
  else if (m_score.score(White) + m_score.score(Black) + m_depth + 4 >= 64)
    m_depth += 2;
  else if (m_score.score(White) + m_score.score(Black) + m_depth + 5 >= 64)
    m_depth++;

  // If we are very close to the end, we can even make the search
  // exhaustive.
  if (m_score.score(White) + m_score.score(Black) + m_depth >= 64)
    m_exhaustive = true;

  // The evaluation is a linear combination of the score (number of
  // pieces) and the sum of the scores for the squares (given by
  // m_bc_score).  The earlier in the game, the more we use the square
  // values and the later in the game the more we use the number of
  // pieces.
  m_coeff = 100 - (100*
		   (m_score.score(White) + m_score.score(Black) 
		    + m_depth - 4)) / 60;

  // Initialize the board that we use for the search.
  for (uint x = 0; x < 10; x++)
    for (uint y = 0; y < 10; y++) {
      if (1 <= x && x <= 8
	  && 1 <= y && y <= 8)
	m_board[x][y] = game->color(x, y);
      else
	m_board[x][y] = Nobody;
    }

  // Initialize a lot of stuff that we will use in the search.

  // Initialize m_bc_score to the current bc score.  This is kept
  // up-to-date incrementally so that way we won't have to calculate
  // it from scratch for each evaluation.
  m_bc_score.set(White, CalcBcScore(White));
  m_bc_score.set(Black, CalcBcScore(Black));

  ULONG64 colorbits    = ComputeOccupiedBits(color);
  ULONG64 opponentbits = ComputeOccupiedBits(opponent(color));

  int maxval = -LARGEINT;
  int max_x = 0;
  int max_y = 0;

  MoveAndValue moves[60];
  int number_of_moves = 0;
  int number_of_maxval = 0;

  setInterrupt(false);

  ULONG64 null_bits;
  null_bits = 0;

  // The main search loop.  Step through all possible moves and keep
  // track of the most valuable one.  This move is stored in 
  // (max_x, max_y) and the value is stored in maxval.
  m_nodes_searched = 0;
  for (int x = 1; x < 9; x++) {
    for (int y = 1; y < 9; y++) {
      // Don't bother with non-empty squares and squares that aren't
      // neighbors to opponent pieces.
      if (m_board[x][y] != Nobody
	  || (m_neighbor_bits[x][y] & opponentbits) == null_bits)
	continue;


      int val = ComputeMove2(x, y, color, 1, maxval,
			     colorbits, opponentbits);

      if (val != ILLEGAL_VALUE) {
	moves[number_of_moves++].setXYV(x, y, val);

	// If the move is better than all previous moves, then record
	// this fact...
	if (val > maxval) {

	  // ...except that we want to make the computer miss some
	  // good moves so that beginners can play against the program
	  // and not always lose.  However, we only do this if the
	  // user wants a casual game, which is set in the settings
	  // dialog.
	  int randi = m_random.getLong(7);
	  if (maxval == -LARGEINT 
	      || m_competitive 
	      || randi < (int) m_strength) {
	    maxval = val;
	    max_x  = x;
	    max_y  = y;

	    number_of_maxval = 1;
	  }
	}
	else if (val == maxval)
	  number_of_maxval++;
      }

      // Jump out prematurely if interrupt is set.
      if (interrupted()) 
	break;
    }
  }

  // long endtime = times(&tmsdummy);

  // If there are more than one best move, the pick one randomly.
  if (number_of_maxval > 1) {
    int  r = m_random.getLong(number_of_maxval) + 1;
    int  i;

    for (i = 0; i < number_of_moves; i++) {
      if (moves[i].m_value == maxval && --r <= 0) 
	break;
    }

    max_x = moves[i].m_x;
    max_y = moves[i].m_y;
  }

  // Return a suitable move.
  if (interrupted())
    return Move(Nobody, -1, -1);
  else if (maxval != -LARGEINT)
    return Move(color, max_x, max_y);
  else
    return Move(Nobody, -1, -1);
}


// Get the first move.  We can pick any move at random.
//

Move Engine::ComputeFirstMove(Game *game) 
{
  int    r;
  Color  color = game->toMove();

  r = m_random.getLong(4) + 1;

  if (color == White) {
    if (r == 1)      return  Move(color, 3, 5);
    else if (r == 2) return  Move(color, 4, 6);
    else if (r == 3) return  Move(color, 5, 3);
    else             return  Move(color, 6, 4);
  }
  else {
    if (r == 1)      return  Move(color, 3, 4);
    else if (r == 2) return  Move(color, 5, 6);
    else if (r == 3) return  Move(color, 4, 3);
    else             return  Move(color, 6, 5);
  }
}


// Play a move at (xplay, yplay) and generate a value for it.  If we
// are at the maximum search depth, we get the value by calling
// EvaluatePosition(), otherwise we get it by performing an alphabeta
// search.
//

int Engine::ComputeMove2(int xplay, int yplay, Color color, int level,
			 int cutoffval, ULONG64 colorbits,
			 ULONG64 opponentbits)
{
  int               number_of_turned = 0;
  SquareStackEntry  mse;
  Color             opponent = ::opponent(color);

  m_nodes_searched++;

  // Put the piece on the board and incrementally update scores and bitmaps.
  m_board[xplay][yplay] = color;
  colorbits |= m_coord_bit[xplay][yplay];
  m_score.inc(color);
  m_bc_score.add(color, m_bc_board[xplay][yplay]);

  // Loop through all 8 directions and turn the pieces that can be turned.
  for (int xinc = -1; xinc <= 1; xinc++)
    for (int yinc = -1; yinc <= 1; yinc++) {
      if (xinc == 0 && yinc == 0) 
	continue;

      int x, y;

      for (x = xplay + xinc, y = yplay + yinc; m_board[x][y] == opponent;
	   x += xinc, y += yinc)
	;

      // If we found the end of a turnable row, then go back and turn
      // all pieces on the way back.  Also push the squares with
      // turned pieces on the squarestack so that we can undo the move
      // later.
      if (m_board[x][y] == color)
	for (x -= xinc, y -= yinc; x != xplay || y != yplay;
	     x -= xinc, y -= yinc) {
	  m_board[x][y] = color;
	  colorbits |= m_coord_bit[x][y];
	  opponentbits &= ~m_coord_bit[x][y];

	  m_squarestack.Push(x, y);

	  m_bc_score.add(color, m_bc_board[x][y]);
	  m_bc_score.sub(opponent, m_bc_board[x][y]);
	  number_of_turned++;
	}
    }

  int retval = -LARGEINT;

  // If we managed to turn at least one piece, then (xplay, yplay) was
  // a legal move.  Now find out the value of the move.
  if (number_of_turned > 0) {

    // First adjust the number of pieces for each side.
    m_score.add(color, number_of_turned);
    m_score.sub(opponent, number_of_turned);

    // If we are at the bottom of the search, get the evaluation.
    if (level >= m_depth)
      retval = EvaluatePosition(color); // Terminal node
    else {
      int maxval = TryAllMoves(opponent, level, cutoffval, opponentbits,
			       colorbits);

      if (maxval != -LARGEINT)
	retval = -maxval;
      else {

	// No possible move for the opponent, it is colors turn again:
	retval = TryAllMoves(color, level, -LARGEINT, colorbits, opponentbits);

	if (retval == -LARGEINT) {

	  // No possible move for anybody => end of game:
	  int finalscore = m_score.score(color) - m_score.score(opponent);

	  if (m_exhaustive)
	    retval = finalscore;
	  else {
	    // Take a sure win and avoid a sure loss (may not be optimal):

	    if (finalscore > 0) 
	      retval = LARGEINT - 65 + finalscore;
	    else if (finalscore < 0)
	      retval = -(LARGEINT - 65 + finalscore);
	    else
	      retval = 0;
	  }
	}
      }
    }

    m_score.add(opponent, number_of_turned);
    m_score.sub(color, number_of_turned);
  }

  // Undo the move.  Start by unturning the turned pieces.
  for (int i = number_of_turned; i > 0; i--) {
    mse = m_squarestack.Pop();
    m_bc_score.add(opponent, m_bc_board[mse.m_x][mse.m_y]);
    m_bc_score.sub(color, m_bc_board[mse.m_x][mse.m_y]);
    m_board[mse.m_x][mse.m_y] = opponent;
  }

  // Now remove the new piece that we put down.
  m_board[xplay][yplay] = Nobody;
  m_score.sub(color, 1);
  m_bc_score.sub(color, m_bc_board[xplay][yplay]);

  // Return a suitable value.
  if (number_of_turned < 1 || interrupted())
    return ILLEGAL_VALUE;
  else
    return retval;
}


// Generate all legal moves from the current position, and do a search
// to see the value of them.  This function returns the value of the
// most valuable move, but not the move itself.
//

int Engine::TryAllMoves(Color opponent, int level, int cutoffval,
			ULONG64 opponentbits, ULONG64 colorbits)
{
  int maxval = -LARGEINT;

  // Keep GUI alive by calling the event loop.
  yield();

  ULONG64  null_bits;
  null_bits = 0;

  for (int x = 1; x < 9; x++) {
    for (int y = 1; y < 9; y++) {
      if (m_board[x][y] == Nobody 
	  && (m_neighbor_bits[x][y] & colorbits) != null_bits) {
	int val = ComputeMove2(x, y, opponent, level+1, maxval, opponentbits,
			       colorbits);

	if (val != ILLEGAL_VALUE && val > maxval) {
	  maxval = val;
	  if (maxval > -cutoffval || interrupted()) 
	    break;
	}
      }
    }

    if (maxval > -cutoffval || interrupted())
      break;
  }

  if (interrupted()) 
    return -LARGEINT;

  return maxval;
}


// Calculate a heuristic value for the current position.  If we are at
// the end of the game, do this by counting the pieces.  Otherwise do
// it by combining the score using the number of pieces, and the score
// using the board control values.
//

int Engine::EvaluatePosition(Color color)
{
  int retval;

  Color  opponent = ::opponent(color);

  int    score_color    = m_score.score(color);
  int    score_opponent = m_score.score(opponent);

  if (m_exhaustive)
    retval = score_color - score_opponent;
  else {
    retval = (100-m_coeff) *
      (m_score.score(color) - m_score.score(opponent)) 
      + m_coeff * BC_WEIGHT * (m_bc_score.score(color)
			       - m_bc_score.score(opponent));
  }

  return retval;
}


// Calculate bitmaps for each square, and also for neighbors of each
// square.
//

void Engine::SetupBits()
{
  //m_coord_bit = new long[9][9];
  //m_neighbor_bits = new long[9][9];

  ULONG64 bits = 1;

  // Store a 64 bit unsigned it with the corresponding bit set for
  // each square.
  for (int i=1; i < 9; i++)
    for (int j=1; j < 9; j++) {
      m_coord_bit[i][j] = bits;
#if !defined(__GNUC__)
      bits.shl();
#else
      bits *= 2;
#endif
    }

  // Store a bitmap consisting of all neighbors for each square.
  for (int i=1; i < 9; i++)
    for (int j=1; j < 9; j++) {
      m_neighbor_bits[i][j] = 0;

      for (int xinc=-1; xinc<=1; xinc++)
	for (int yinc=-1; yinc<=1; yinc++) {
	  if (xinc != 0 || yinc != 0)
	    if (i + xinc > 0 && i + xinc < 9 && j + yinc > 0 && j + yinc < 9)
	      m_neighbor_bits[i][j] |= m_coord_bit[i + xinc][j + yinc];
	}
    }
}


// Set up the board control values that will be used in evaluation of
// the position.
//

void Engine::SetupBcBoard()
{
  // JAVA m_bc_board = new int[9][9];

  for (int i=1; i < 9; i++)
    for (int j=1; j < 9; j++) {
      if (i == 2 || i == 7)
	m_bc_board[i][j] = -1;
      else
	m_bc_board[i][j] = 0;

      if (j == 2 || j == 7)
	m_bc_board[i][j] -= 1;
    }

  m_bc_board[1][1] = 2;
  m_bc_board[8][1] = 2;
  m_bc_board[1][8] = 2;
  m_bc_board[8][8] = 2;

  m_bc_board[1][2] = -1;
  m_bc_board[2][1] = -1;
  m_bc_board[1][7] = -1;
  m_bc_board[7][1] = -1;
  m_bc_board[8][2] = -1;
  m_bc_board[2][8] = -1;
  m_bc_board[8][7] = -1;
  m_bc_board[7][8] = -1;
}


// Calculate the board control score.
//

int Engine::CalcBcScore(Color color)
{
  int sum = 0;

  for (int i=1; i < 9; i++)
    for (int j=1; j < 9; j++)
      if (m_board[i][j] == color)
	sum += m_bc_board[i][j];

  return sum;
}


// Calculate a bitmap of the occupied squares for a certain color.
//

ULONG64 Engine::ComputeOccupiedBits(Color color)
{
  ULONG64 retval = 0;

  for (int i=1; i < 9; i++)
    for (int j=1; j < 9; j++)
      if (m_board[i][j] == color) retval |= m_coord_bit[i][j];

  return retval;
}