Copy the KDE 3.5 branch to branches/trinity for new KDE 3.5 features.

BUG:215923


git-svn-id: svn://anonsvn.kde.org/home/kde/branches/trinity/kdegames@1054174 283d02a7-25f6-0310-bc7c-ecb5cbfe19da

1 files changed, 787 insertions, 0 deletions

diff --git a/kreversi/Engine.cpp b/kreversi/Engine.cpp
new file mode 100644
index 00000000..da7750ce
--- /dev/null
+++ b/kreversi/Engine.cpp
@@ -0,0 +1,787 @@
+/* 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 <qapplication.h>
+
+#include "Engine.h"
+
+
+// ================================================================
+//                          Class ULONG64
+
+
+#if !defined(__GNUC__)
+
+
+ULONG64::ULONG64() : QBitArray(64) 
+{
+  fill(0);
+}
+
+
+// Initialize an ULONG64 from a 32 bit value.
+//
+
+ULONG64::ULONG64( unsigned int value ) : QBitArray(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() 
+{
+  qApp->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;
+}
+