summaryrefslogtreecommitdiffstats
path: root/kreversi/Engine.h
blob: a84be895284885979e19bf905e51c51b56b45520 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
/* 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.

#ifndef __ENGINE__H__
#define __ENGINE__H__

#include "SuperEngine.h"
#include "Position.h"
#include "Game.h"
#include "Move.h"
#include "Score.h"
#include <qmemarray.h>
#include <sys/times.h>
#include <qbitarray.h>


// Class ULONG64 is used as a bitmap for the squares.

#if defined(__GNUC__)
#define ULONG64 unsigned long long int
#else
class ULONG64 : public QBitArray {
public:
  ULONG64();
  ULONG64( unsigned int );
  void shl();
};
#endif


// SquareStackEntry and SquareStack are used during search to keep
// track of turned pieces.

class SquareStackEntry
{
public:
  SquareStackEntry();

  void setXY(int x, int y);

public:
  int  m_x;
  int  m_y;
};


class SquareStack
{
public:
  SquareStack();
  SquareStack(int size);

  void              resize(int size);
  void              init(int size);
  SquareStackEntry  Pop();
  void              Push(int x, int y);

private:
  QMemArray<SquareStackEntry>  m_squarestack;
  int                          m_top;
};


// Connect a move with its value.

class MoveAndValue
{
public:
  MoveAndValue();
  MoveAndValue(int x, int y, int value);

  void  setXYV(int x, int y, int value);

public:
  int  m_x;
  int  m_y;
  int  m_value;
};


// The real beef of this program: the engine that finds good moves for
// the computer player.
//
class Engine : public SuperEngine {
public:
  Engine(int st, int sd);
  Engine(int st);
  Engine();

  Move     computeMove(Game *game, bool competitive);

private:
  Move     ComputeFirstMove(Game *game);
  int      ComputeMove2(int xplay, int yplay, Color color, int level,
			int cutoffval,
			ULONG64 colorbits, ULONG64 opponentbits);

  int      TryAllMoves(Color opponent, int level, int cutoffval,
		       ULONG64 opponentbits, ULONG64 colorbits);

  int      EvaluatePosition(Color color);
  void     SetupBcBoard();
  void     SetupBits();
  int      CalcBcScore(Color color);
  ULONG64  ComputeOccupiedBits(Color color);

  void yield();

private:
  static const int  LARGEINT;
  static const int  ILLEGAL_VALUE;
  static const int  BC_WEIGHT;

  Color        m_board[10][10];
  int          m_bc_board[9][9];
  Score        m_score;
  Score        m_bc_score;
  SquareStack  m_squarestack;
  
  int          m_depth;
  int          m_coeff;
  int          m_nodes_searched;
  bool         m_exhaustive;
  bool         m_competitive;

  ULONG64      m_coord_bit[9][9];
  ULONG64      m_neighbor_bits[9][9];
};

#endif