1/*******************************************************************
2 *
3 * Copyright 1997 Mario Weilguni <mweilguni@sime.com>
4 *
5 * This file is part of the KDE project "KREVERSI"
6 *
7 * KREVERSI is free software; you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation; either version 2, or (at your option)
10 * any later version.
11 *
12 * KREVERSI is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with KREVERSI; see the file COPYING. If not, write to
19 * the Free Software Foundation, 51 Franklin Street, Fifth Floor,
20 * Boston, MA 02110-1301, USA.
21 *
22 *******************************************************************
23 ********************************************************************
24 *******************************************************************
25 *
26 *
27 * KREVERSI
28 *
29 *
30 *******************************************************************
31 *
32 * A Reversi (or sometimes called Othello) game
33 *
34 *******************************************************************
35 *
36 * Created 1997 by Mario Weilguni <mweilguni@sime.com>. This file
37 * is ported from Mats Luthman's <Mats.Luthman@sylog.se> JAVA applet.
38 * Many thanks to Mr. Luthman who has allowed me to put this port
39 * under the GNU GPL. Without his wonderful game engine kreversi
40 * would be just another of those Reversi programs a five year old
41 * child could beat easily. But with it it's a worthy opponent!
42 *
43 * If you are interested on the JAVA applet of Mr. Luthman take a
44 * look at http://www.sylog.se/~mats/
45 */
46
47// The class Engine produces moves from a Game object through calls to the
48// function ComputeMove().
49//
50// First of all: this is meant to be a simple example of a game playing
51// program. Not everything is done in the most clever way, particularly not
52// the way the moves are searched, but it is hopefully made in a way that makes
53// it easy to understand. The function ComputeMove2() that does all the work
54// is actually not much more than a hundred lines. Much could be done to
55// make the search faster though, I'm perfectly aware of that. Feel free
56// to experiment.
57//
58// The method used to generate the moves is called minimax tree search with
59// alpha-beta pruning to a fixed depth. In short this means that all possible
60// moves a predefined number of moves ahead are either searched or refuted
61// with a method called alpha-beta pruning. A more thorough explanation of
62// this method could be found at the world wide web at http:
63// //yoda.cis.temple.edu:8080/UGAIWWW/lectures96/search/minimax/alpha-beta.html
64// at the time this was written. Searching for "minimax" would also point
65// you to information on this subject. It is probably possible to understand
66// this method by reading the source code though, it is not that complicated.
67//
68// At every leaf node at the search tree, the resulting position is evaluated.
69// Two things are considered when evaluating a position: the number of pieces
70// of each color and at which squares the pieces are located. Pieces at the
71// corners are valuable and give a high value, and having pieces at squares
72// next to a corner is not very good and they give a lower value. In the
73// beginning of a game it is more important to have pieces on "good" squares,
74// but towards the end the total number of pieces of each color is given a
75// higher weight. Other things, like how many legal moves that can be made in a
76// position, and the number of pieces that can never be turned would probably
77// make the program stronger if they were considered in evaluating a position,
78// but that would make things more complicated (this was meant to be very
79// simple example) and would also slow down computation (considerably?).
80//
81// The member m_board[10][10]) holds the current position during the
82// computation. It is initiated at the start of ComputeMove() and
83// every move that is made during the search is made on this board. It should
84// be noted that 1 to 8 is used for the actual board, but 0 and 9 can be
85// used too (they are always empty). This is practical when turning pieces
86// when moves are made on the board. Every piece that is put on the board
87// or turned is saved in the stack m_squarestack (see class SquareStack) so
88// every move can easily be reversed after the search in a node is completed.
89//
90// The member m_bc_board[][] holds board control values for each square
91// and is initiated by a call to the function private void SetupBcBoard()
92// from Engines constructor. It is used in evaluation of positions except
93// when the game tree is searched all the way to the end of the game.
94//
95// The two members m_coord_bit[9][9] and m_neighbor_bits[9][9] are used to
96// speed up the tree search. This goes against the principle of keeping things
97// simple, but to understand the program you do not need to understand them
98// at all. They are there to make it possible to throw away moves where
99// the piece that is played is not adjacent to a piece of opposite color
100// at an early stage (because they could never be legal). It should be
101// pointed out that not all moves that pass this test are legal, there will
102// just be fewer moves that have to be tested in a more time consuming way.
103//
104// There are also two other members that should be mentioned: Score m_score
105// and Score m_bc_score. They hold the number of pieces of each color and
106// the sum of the board control values for each color during the search
107// (this is faster than counting at every leaf node).
108//
109
110// The classes SquareStackEntry and SquareStack implement a
111// stack that is used by Engine to store pieces that are turned during
112// searching (see ComputeMove()).
113//
114// The class MoveAndValue is used by Engine to store all possible moves
115// at the first level and the values that were calculated for them.
116// This makes it possible to select a random move among those with equal
117// or nearly equal value after the search is completed.
118
119#ifndef KREVERSI_ENGINE_H
120#define KREVERSI_ENGINE_H
121
122#include <KRandomSequence>
123
124#include <commondefs.h>
125#include <kreversigame.h>
126class KReversiGame;
127
128
129// SquareStackEntry and SquareStack are used during search to keep
130// track of turned pieces.
131
132class SquareStackEntry
133{
134public:
135 SquareStackEntry();
136
137 void setXY(int x, int y);
138
139public:
140 int m_x;
141 int m_y;
142};
143
144
145class SquareStack
146{
147public:
148 SquareStack();
149 explicit SquareStack(int size);
150
151 void resize(int size);
152 void init(int size);
153 SquareStackEntry Pop();
154 void Push(int x, int y);
155
156private:
157 QVector<SquareStackEntry> m_squarestack;
158 int m_top;
159};
160
161
162// Connect a move with its value.
163
164class MoveAndValue
165{
166public:
167 MoveAndValue();
168 MoveAndValue(int x, int y, int value);
169
170 void setXYV(int x, int y, int value);
171
172public:
173 int m_x;
174 int m_y;
175 int m_value;
176};
177
178class Score;
179
180// The real beef of this program: the engine that finds good moves for
181// the computer player.
182//
183class Engine
184{
185public:
186 Engine(int st, int sd);
187 explicit Engine(int st);
188 Engine();
189
190 ~Engine();
191
192 KReversiMove computeMove(const KReversiGame& game, bool competitive);
193 bool isThinking() const {
194 return m_computingMove;
195 }
196
197 void setInterrupt(bool intr) {
198 m_interrupt = intr;
199 }
200 bool interrupted() const {
201 return m_interrupt;
202 }
203
204 void setStrength(uint strength) {
205 m_strength = strength;
206 }
207 uint strength() const {
208 return m_strength;
209 }
210private:
211 KReversiMove ComputeFirstMove(const KReversiGame& game);
212 int ComputeMove2(int xplay, int yplay, ChipColor color, int level,
213 int cutoffval,
214 quint64 colorbits, quint64 opponentbits);
215
216 int TryAllMoves(ChipColor opponent, int level, int cutoffval,
217 quint64 opponentbits, quint64 colorbits);
218
219 int EvaluatePosition(ChipColor color);
220 void SetupBcBoard();
221 void SetupBits();
222 int CalcBcScore(ChipColor color);
223 quint64 ComputeOccupiedBits(ChipColor color);
224
225 void yield();
226
227private:
228
229 ChipColor m_board[10][10];
230 int m_bc_board[9][9];
231 Score* m_score;
232 Score* m_bc_score;
233 SquareStack m_squarestack;
234
235 int m_depth;
236 int m_coeff;
237 int m_nodes_searched;
238 bool m_exhaustive;
239 bool m_competitive;
240
241 uint m_strength;
242 KRandomSequence m_random;
243 bool m_interrupt;
244
245 quint64 m_coord_bit[9][9];
246 quint64 m_neighbor_bits[9][9];
247
248 bool m_computingMove;
249};
250
251#endif
252