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> |
126 | class KReversiGame; |
127 | |
128 | |
129 | // SquareStackEntry and SquareStack are used during search to keep |
130 | // track of turned pieces. |
131 | |
132 | class SquareStackEntry |
133 | { |
134 | public: |
135 | SquareStackEntry(); |
136 | |
137 | void setXY(int x, int y); |
138 | |
139 | public: |
140 | int m_x; |
141 | int m_y; |
142 | }; |
143 | |
144 | |
145 | class SquareStack |
146 | { |
147 | public: |
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 | |
156 | private: |
157 | QVector<SquareStackEntry> m_squarestack; |
158 | int m_top; |
159 | }; |
160 | |
161 | |
162 | // Connect a move with its value. |
163 | |
164 | class MoveAndValue |
165 | { |
166 | public: |
167 | MoveAndValue(); |
168 | MoveAndValue(int x, int y, int value); |
169 | |
170 | void setXYV(int x, int y, int value); |
171 | |
172 | public: |
173 | int m_x; |
174 | int m_y; |
175 | int m_value; |
176 | }; |
177 | |
178 | class Score; |
179 | |
180 | // The real beef of this program: the engine that finds good moves for |
181 | // the computer player. |
182 | // |
183 | class Engine |
184 | { |
185 | public: |
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 | } |
210 | private: |
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 | |
227 | private: |
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 | |