diff options
author | toma <toma@283d02a7-25f6-0310-bc7c-ecb5cbfe19da> | 2009-11-25 17:56:58 +0000 |
---|---|---|
committer | toma <toma@283d02a7-25f6-0310-bc7c-ecb5cbfe19da> | 2009-11-25 17:56:58 +0000 |
commit | c90c389a8a8d9d8661e9772ec4144c5cf2039f23 (patch) | |
tree | 6d8391395bce9eaea4ad78958617edb20c6a7573 /kreversi/Engine.cpp | |
download | tdegames-c90c389a8a8d9d8661e9772ec4144c5cf2039f23.tar.gz tdegames-c90c389a8a8d9d8661e9772ec4144c5cf2039f23.zip |
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
Diffstat (limited to 'kreversi/Engine.cpp')
-rw-r--r-- | kreversi/Engine.cpp | 787 |
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 <[email protected]>. This file + * is ported from Mats Luthman's <[email protected]> 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; +} + |