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 | * KREVERSI |
26 | * |
27 | * |
28 | ******************************************************************* |
29 | * |
30 | * A Reversi (or sometimes called Othello) game |
31 | * |
32 | ******************************************************************* |
33 | * |
34 | * Created 1997 by Mario Weilguni <mweilguni@sime.com>. This file |
35 | * is ported from Mats Luthman's <Mats.Luthman@sylog.se> JAVA applet. |
36 | * Many thanks to Mr. Luthman who has allowed me to put this port |
37 | * under the GNU GPL. Without his wonderful game engine kreversi |
38 | * would be just another of those Reversi programs a five year old |
39 | * child could beat easily. But with it it's a worthy opponent! |
40 | * |
41 | * If you are interested on the JAVA applet of Mr. Luthman take a |
42 | * look at http://www.sylog.se/~mats/ |
43 | */ |
44 | |
45 | // The class Engine produces moves from a Game object through calls to the |
46 | // function ComputeMove(). |
47 | // |
48 | // First of all: this is meant to be a simple example of a game playing |
49 | // program. Not everything is done in the most clever way, particularly not |
50 | // the way the moves are searched, but it is hopefully made in a way that makes |
51 | // it easy to understand. The function ComputeMove2() that does all the work |
52 | // is actually not much more than a hundred lines. Much could be done to |
53 | // make the search faster though, I'm perfectly aware of that. Feel free |
54 | // to experiment. |
55 | // |
56 | // The method used to generate the moves is called minimax tree search with |
57 | // alpha-beta pruning to a fixed depth. In short this means that all possible |
58 | // moves a predefined number of moves ahead are either searched or refuted |
59 | // with a method called alpha-beta pruning. A more thorough explanation of |
60 | // this method could be found at the world wide web at http: |
61 | // //yoda.cis.temple.edu:8080/UGAIWWW/lectures96/search/minimax/alpha-beta.html |
62 | // at the time this was written. Searching for "minimax" would also point |
63 | // you to information on this subject. It is probably possible to understand |
64 | // this method by reading the source code though, it is not that complicated. |
65 | // |
66 | // At every leaf node at the search tree, the resulting position is evaluated. |
67 | // Two things are considered when evaluating a position: the number of pieces |
68 | // of each color and at which squares the pieces are located. Pieces at the |
69 | // corners are valuable and give a high value, and having pieces at squares |
70 | // next to a corner is not very good and they give a lower value. In the |
71 | // beginning of a game it is more important to have pieces on "good" squares, |
72 | // but towards the end the total number of pieces of each color is given a |
73 | // higher weight. Other things, like how many legal moves that can be made in a |
74 | // position, and the number of pieces that can never be turned would probably |
75 | // make the program stronger if they were considered in evaluating a position, |
76 | // but that would make things more complicated (this was meant to be very |
77 | // simple example) and would also slow down computation (considerably?). |
78 | // |
79 | // The member m_board[10][10]) holds the current position during the |
80 | // computation. It is initiated at the start of ComputeMove() and |
81 | // every move that is made during the search is made on this board. It should |
82 | // be noted that 1 to 8 is used for the actual board, but 0 and 9 can be |
83 | // used too (they are always empty). This is practical when turning pieces |
84 | // when moves are made on the board. Every piece that is put on the board |
85 | // or turned is saved in the stack m_squarestack (see class SquareStack) so |
86 | // every move can easily be reversed after the search in a node is completed. |
87 | // |
88 | // The member m_bc_board[][] holds board control values for each square |
89 | // and is initiated by a call to the function private void SetupBcBoard() |
90 | // from Engines constructor. It is used in evaluation of positions except |
91 | // when the game tree is searched all the way to the end of the game. |
92 | // |
93 | // The two members m_coord_bit[9][9] and m_neighbor_bits[9][9] are used to |
94 | // speed up the tree search. This goes against the principle of keeping things |
95 | // simple, but to understand the program you do not need to understand them |
96 | // at all. They are there to make it possible to throw away moves where |
97 | // the piece that is played is not adjacent to a piece of opposite color |
98 | // at an early stage (because they could never be legal). It should be |
99 | // pointed out that not all moves that pass this test are legal, there will |
100 | // just be fewer moves that have to be tested in a more time consuming way. |
101 | // |
102 | // There are also two other members that should be mentioned: Score m_score |
103 | // and Score m_bc_score. They hold the number of pieces of each color and |
104 | // the sum of the board control values for each color during the search |
105 | // (this is faster than counting at every leaf node). |
106 | // |
107 | |
108 | // The classes SquareStackEntry and SquareStack implement a |
109 | // stack that is used by Engine to store pieces that are turned during |
110 | // searching (see ComputeMove()). |
111 | // |
112 | // The class MoveAndValue is used by Engine to store all possible moves |
113 | // at the first level and the values that were calculated for them. |
114 | // This makes it possible to select a random move among those with equal |
115 | // or nearly equal value after the search is completed. |
116 | |
117 | #include <Engine.h> |
118 | |
119 | #include <QVector> |
120 | #include <QApplication> |
121 | |
122 | #include <KDebug> |
123 | |
124 | // ================================================================ |
125 | // Classes SquareStackEntry and SquareStack |
126 | |
127 | |
128 | // A SquareStack is used to store changes to the squares on the board |
129 | // during search. |
130 | |
131 | |
132 | inline void SquareStackEntry::setXY(int x, int y) |
133 | { |
134 | m_x = x; |
135 | m_y = y; |
136 | } |
137 | |
138 | |
139 | SquareStackEntry::SquareStackEntry() |
140 | { |
141 | setXY(0, 0); |
142 | } |
143 | |
144 | |
145 | // ---------------------------------------------------------------- |
146 | |
147 | |
148 | SquareStack::SquareStack() |
149 | { |
150 | init(0); |
151 | } |
152 | |
153 | |
154 | SquareStack::SquareStack(int size) |
155 | { |
156 | init(size); |
157 | } |
158 | |
159 | |
160 | void SquareStack::resize(int size) |
161 | { |
162 | m_squarestack.resize(size); |
163 | } |
164 | |
165 | |
166 | // (Re)initialize the stack so that is empty, and at the same time |
167 | // resize it to 'size'. |
168 | // |
169 | |
170 | void SquareStack::init(int size) |
171 | { |
172 | resize(size); |
173 | |
174 | m_top = 0; |
175 | for (int i = 0; i < size; i++) |
176 | m_squarestack[i].setXY(0, 0); |
177 | } |
178 | |
179 | |
180 | |
181 | inline SquareStackEntry SquareStack::Pop() |
182 | { |
183 | return m_squarestack[--m_top]; |
184 | } |
185 | |
186 | |
187 | inline void SquareStack::Push(int x, int y) |
188 | { |
189 | m_squarestack[m_top].m_x = x; |
190 | m_squarestack[m_top++].m_y = y; |
191 | } |
192 | |
193 | |
194 | // ================================================================ |
195 | // Class MoveAndValue |
196 | |
197 | |
198 | // Class MoveAndValue aggregates a move with its value. |
199 | // |
200 | |
201 | |
202 | inline void MoveAndValue::setXYV(int x, int y, int value) |
203 | { |
204 | m_x = x; |
205 | m_y = y; |
206 | m_value = value; |
207 | } |
208 | |
209 | |
210 | MoveAndValue::MoveAndValue() |
211 | { |
212 | setXYV(0, 0, 0); |
213 | } |
214 | |
215 | |
216 | MoveAndValue::MoveAndValue(int x, int y, int value) |
217 | { |
218 | setXYV(x, y, value); |
219 | } |
220 | |
221 | // ================================================================ |
222 | // class Score |
223 | |
224 | /* This class keeps track of the score for both colors. Such a score |
225 | * could be either the number of pieces, the score from the evaluation |
226 | * function or anything similar. |
227 | */ |
228 | class Score |
229 | { |
230 | public: |
231 | Score() { |
232 | m_score[White] = 0; |
233 | m_score[Black] = 0; |
234 | } |
235 | |
236 | uint score(ChipColor color) const { |
237 | return m_score[color]; |
238 | } |
239 | |
240 | void set(ChipColor color, uint score) { |
241 | m_score[color] = score; |
242 | } |
243 | void inc(ChipColor color) { |
244 | m_score[color]++; |
245 | } |
246 | void dec(ChipColor color) { |
247 | m_score[color]--; |
248 | } |
249 | void add(ChipColor color, uint s) { |
250 | m_score[color] += s; |
251 | } |
252 | void sub(ChipColor color, uint s) { |
253 | m_score[color] -= s; |
254 | } |
255 | |
256 | private: |
257 | uint m_score[2]; |
258 | }; |
259 | |
260 | // ================================================================ |
261 | // The Engine itself |
262 | |
263 | |
264 | // Some special values used in the search. |
265 | static const int LARGEINT = 99999; |
266 | static const int ILLEGAL_VALUE = 8888888; |
267 | static const int BC_WEIGHT = 3; |
268 | |
269 | |
270 | Engine::Engine(int st, int sd)/* : SuperEngine(st, sd) */ |
271 | : m_strength(st), m_computingMove(false) |
272 | { |
273 | m_random.setSeed(sd); |
274 | m_score = new Score; |
275 | m_bc_score = new Score; |
276 | SetupBcBoard(); |
277 | SetupBits(); |
278 | } |
279 | |
280 | |
281 | Engine::Engine(int st) //: SuperEngine(st) |
282 | : m_strength(st), m_computingMove(false) |
283 | { |
284 | m_random.setSeed(0); |
285 | m_score = new Score; |
286 | m_bc_score = new Score; |
287 | SetupBcBoard(); |
288 | SetupBits(); |
289 | } |
290 | |
291 | |
292 | Engine::Engine()// : SuperEngine(1) |
293 | : m_strength(1), m_computingMove(false) |
294 | { |
295 | m_random.setSeed(0); |
296 | m_score = new Score; |
297 | m_bc_score = new Score; |
298 | SetupBcBoard(); |
299 | SetupBits(); |
300 | } |
301 | |
302 | Engine::~Engine() |
303 | { |
304 | delete m_score; |
305 | delete m_bc_score; |
306 | } |
307 | |
308 | // keep GUI alive |
309 | void Engine::yield() |
310 | { |
311 | qApp->processEvents(); |
312 | } |
313 | |
314 | |
315 | // Calculate the best move from the current position, and return it. |
316 | |
317 | KReversiMove Engine::computeMove(const KReversiGame& game, bool competitive) |
318 | { |
319 | if (m_computingMove) |
320 | return KReversiMove(); |
321 | |
322 | m_computingMove = true; |
323 | |
324 | ChipColor color; |
325 | |
326 | // A competitive game is one where we try our damnedest to make the |
327 | // best move. The opposite is a casual game where the engine might |
328 | // make "a mistake". The idea behind this is not to scare away |
329 | // newbies. The member m_competitive is used during search for this |
330 | // very move. |
331 | m_competitive = competitive; |
332 | |
333 | // Suppose that we should give a heuristic evaluation. If we are |
334 | // close to the end of the game we can make an exhaustive search, |
335 | // but that case is determined further down. |
336 | m_exhaustive = false; |
337 | |
338 | // Get the color to calculate the move for. |
339 | color = game.currentPlayer(); |
340 | if (color == NoColor) { |
341 | m_computingMove = false; |
342 | return KReversiMove(); |
343 | } |
344 | |
345 | // Figure out the current score |
346 | m_score->set(White, game.playerScore(White)); |
347 | m_score->set(Black, game.playerScore(Black)); |
348 | |
349 | // Treat the first move as a special case (we can basically just |
350 | // pick a move at random). |
351 | if (m_score->score(White) + m_score->score(Black) == 4) { |
352 | m_computingMove = false; |
353 | return ComputeFirstMove(game); |
354 | } |
355 | |
356 | // Let there be room for 3000 changes during the recursive search. |
357 | // This is more than will ever be needed. |
358 | m_squarestack.init(3000); |
359 | |
360 | // Get the search depth. If we are close to the end of the game, |
361 | // the number of possible moves goes down, so we can search deeper |
362 | // without using more time. |
363 | m_depth = m_strength; |
364 | if (m_score->score(White) + m_score->score(Black) + m_depth + 3 >= 64) |
365 | m_depth = 64 - m_score->score(White) - m_score->score(Black); |
366 | else if (m_score->score(White) + m_score->score(Black) + m_depth + 4 >= 64) |
367 | m_depth += 2; |
368 | else if (m_score->score(White) + m_score->score(Black) + m_depth + 5 >= 64) |
369 | m_depth++; |
370 | |
371 | // If we are very close to the end, we can even make the search |
372 | // exhaustive. |
373 | if (m_score->score(White) + m_score->score(Black) + m_depth >= 64) |
374 | m_exhaustive = true; |
375 | |
376 | // The evaluation is a linear combination of the score (number of |
377 | // pieces) and the sum of the scores for the squares (given by |
378 | // m_bc_score). The earlier in the game, the more we use the square |
379 | // values and the later in the game the more we use the number of |
380 | // pieces. |
381 | m_coeff = 100 - (100 * |
382 | (m_score->score(White) + m_score->score(Black) |
383 | + m_depth - 4)) / 60; |
384 | |
385 | // Initialize the board that we use for the search. |
386 | for (uint x = 0; x < 10; x++) |
387 | for (uint y = 0; y < 10; y++) { |
388 | if (1 <= x && x <= 8 |
389 | && 1 <= y && y <= 8) |
390 | m_board[x][y] = game.chipColorAt(KReversiPos(y - 1, x - 1)); |
391 | else |
392 | m_board[x][y] = NoColor; |
393 | } |
394 | |
395 | // Initialize a lot of stuff that we will use in the search. |
396 | |
397 | // Initialize m_bc_score to the current bc score. This is kept |
398 | // up-to-date incrementally so that way we won't have to calculate |
399 | // it from scratch for each evaluation. |
400 | m_bc_score->set(White, CalcBcScore(White)); |
401 | m_bc_score->set(Black, CalcBcScore(Black)); |
402 | |
403 | quint64 colorbits = ComputeOccupiedBits(color); |
404 | quint64 opponentbits = ComputeOccupiedBits(Utils::opponentColorFor(color)); |
405 | |
406 | int maxval = -LARGEINT; |
407 | int max_x = 0; |
408 | int max_y = 0; |
409 | |
410 | MoveAndValue moves[60]; |
411 | int number_of_moves = 0; |
412 | int number_of_maxval = 0; |
413 | |
414 | setInterrupt(false); |
415 | |
416 | quint64 null_bits; |
417 | null_bits = 0; |
418 | |
419 | // The main search loop. Step through all possible moves and keep |
420 | // track of the most valuable one. This move is stored in |
421 | // (max_x, max_y) and the value is stored in maxval. |
422 | m_nodes_searched = 0; |
423 | for (int x = 1; x < 9; x++) { |
424 | for (int y = 1; y < 9; y++) { |
425 | // Don't bother with non-empty squares and squares that aren't |
426 | // neighbors to opponent pieces. |
427 | if (m_board[x][y] != NoColor |
428 | || (m_neighbor_bits[x][y] & opponentbits) == null_bits) |
429 | continue; |
430 | |
431 | |
432 | int val = ComputeMove2(x, y, color, 1, maxval, |
433 | colorbits, opponentbits); |
434 | |
435 | if (val != ILLEGAL_VALUE) { |
436 | moves[number_of_moves++].setXYV(x, y, val); |
437 | |
438 | // If the move is better than all previous moves, then record |
439 | // this fact... |
440 | if (val > maxval) { |
441 | |
442 | // ...except that we want to make the computer miss some |
443 | // good moves so that beginners can play against the program |
444 | // and not always lose. However, we only do this if the |
445 | // user wants a casual game, which is set in the settings |
446 | // dialog. |
447 | int randi = m_random.getLong(7); |
448 | if (maxval == -LARGEINT |
449 | || m_competitive |
450 | || randi < (int) m_strength) { |
451 | maxval = val; |
452 | max_x = x; |
453 | max_y = y; |
454 | |
455 | number_of_maxval = 1; |
456 | } |
457 | } else if (val == maxval) |
458 | number_of_maxval++; |
459 | } |
460 | |
461 | // Jump out prematurely if interrupt is set. |
462 | if (interrupted()) |
463 | break; |
464 | } |
465 | } |
466 | |
467 | // long endtime = times(&tmsdummy); |
468 | |
469 | // If there are more than one best move, the pick one randomly. |
470 | if (number_of_maxval > 1) { |
471 | int r = m_random.getLong(number_of_maxval) + 1; |
472 | int i; |
473 | |
474 | for (i = 0; i < number_of_moves; ++i) { |
475 | if (moves[i].m_value == maxval && --r <= 0) |
476 | break; |
477 | } |
478 | |
479 | max_x = moves[i].m_x; |
480 | max_y = moves[i].m_y; |
481 | } |
482 | |
483 | m_computingMove = false; |
484 | // Return a suitable move. |
485 | if (interrupted()) |
486 | return KReversiMove(NoColor, -1, -1); |
487 | else if (maxval != -LARGEINT) |
488 | return KReversiMove(color, max_y - 1, max_x - 1); |
489 | else |
490 | return KReversiMove(NoColor, -1, -1); |
491 | } |
492 | |
493 | |
494 | // Get the first move. We can pick any move at random. |
495 | // |
496 | |
497 | KReversiMove Engine::ComputeFirstMove(const KReversiGame& game) |
498 | { |
499 | int r; |
500 | ChipColor color = game.currentPlayer(); |
501 | |
502 | r = m_random.getLong(4) + 1; |
503 | |
504 | if (color == White) { |
505 | if (r == 1) return KReversiMove(color, 4, 2); |
506 | else if (r == 2) return KReversiMove(color, 5, 3); |
507 | else if (r == 3) return KReversiMove(color, 2, 4); |
508 | else return KReversiMove(color, 3, 5); |
509 | } else { |
510 | if (r == 1) return KReversiMove(color, 3, 2); |
511 | else if (r == 2) return KReversiMove(color, 5, 4); |
512 | else if (r == 3) return KReversiMove(color, 2, 3); |
513 | else return KReversiMove(color, 4, 5); |
514 | } |
515 | } |
516 | |
517 | |
518 | // Play a move at (xplay, yplay) and generate a value for it. If we |
519 | // are at the maximum search depth, we get the value by calling |
520 | // EvaluatePosition(), otherwise we get it by performing an alphabeta |
521 | // search. |
522 | // |
523 | |
524 | int Engine::ComputeMove2(int xplay, int yplay, ChipColor color, int level, |
525 | int cutoffval, quint64 colorbits, |
526 | quint64 opponentbits) |
527 | { |
528 | int number_of_turned = 0; |
529 | SquareStackEntry mse; |
530 | ChipColor opponent = Utils::opponentColorFor(color); |
531 | |
532 | m_nodes_searched++; |
533 | |
534 | // Put the piece on the board and incrementally update scores and bitmaps. |
535 | m_board[xplay][yplay] = color; |
536 | colorbits |= m_coord_bit[xplay][yplay]; |
537 | m_score->inc(color); |
538 | m_bc_score->add(color, m_bc_board[xplay][yplay]); |
539 | |
540 | // Loop through all 8 directions and turn the pieces that can be turned. |
541 | for (int xinc = -1; xinc <= 1; xinc++) |
542 | for (int yinc = -1; yinc <= 1; yinc++) { |
543 | if (xinc == 0 && yinc == 0) |
544 | continue; |
545 | |
546 | int x, y; |
547 | |
548 | for (x = xplay + xinc, y = yplay + yinc; m_board[x][y] == opponent; |
549 | x += xinc, y += yinc) |
550 | ; |
551 | |
552 | // If we found the end of a turnable row, then go back and turn |
553 | // all pieces on the way back. Also push the squares with |
554 | // turned pieces on the squarestack so that we can undo the move |
555 | // later. |
556 | if (m_board[x][y] == color) |
557 | for (x -= xinc, y -= yinc; x != xplay || y != yplay; |
558 | x -= xinc, y -= yinc) { |
559 | m_board[x][y] = color; |
560 | colorbits |= m_coord_bit[x][y]; |
561 | opponentbits &= ~m_coord_bit[x][y]; |
562 | |
563 | m_squarestack.Push(x, y); |
564 | |
565 | m_bc_score->add(color, m_bc_board[x][y]); |
566 | m_bc_score->sub(opponent, m_bc_board[x][y]); |
567 | number_of_turned++; |
568 | } |
569 | } |
570 | |
571 | int retval = -LARGEINT; |
572 | |
573 | // If we managed to turn at least one piece, then (xplay, yplay) was |
574 | // a legal move. Now find out the value of the move. |
575 | if (number_of_turned > 0) { |
576 | |
577 | // First adjust the number of pieces for each side. |
578 | m_score->add(color, number_of_turned); |
579 | m_score->sub(opponent, number_of_turned); |
580 | |
581 | // If we are at the bottom of the search, get the evaluation. |
582 | if (level >= m_depth) |
583 | retval = EvaluatePosition(color); // Terminal node |
584 | else { |
585 | int maxval = TryAllMoves(opponent, level, cutoffval, opponentbits, |
586 | colorbits); |
587 | |
588 | if (maxval != -LARGEINT) |
589 | retval = -maxval; |
590 | else { |
591 | |
592 | // No possible move for the opponent, it is colors turn again: |
593 | retval = TryAllMoves(color, level, -LARGEINT, colorbits, opponentbits); |
594 | |
595 | if (retval == -LARGEINT) { |
596 | |
597 | // No possible move for anybody => end of game: |
598 | int finalscore = m_score->score(color) - m_score->score(opponent); |
599 | |
600 | if (m_exhaustive) |
601 | retval = finalscore; |
602 | else { |
603 | // Take a sure win and avoid a sure loss (may not be optimal): |
604 | |
605 | if (finalscore > 0) |
606 | retval = LARGEINT - 65 + finalscore; |
607 | else if (finalscore < 0) |
608 | retval = -(LARGEINT - 65 + finalscore); |
609 | else |
610 | retval = 0; |
611 | } |
612 | } |
613 | } |
614 | } |
615 | |
616 | m_score->add(opponent, number_of_turned); |
617 | m_score->sub(color, number_of_turned); |
618 | } |
619 | |
620 | // Undo the move. Start by unturning the turned pieces. |
621 | for (int i = number_of_turned; i > 0; i--) { |
622 | mse = m_squarestack.Pop(); |
623 | m_bc_score->add(opponent, m_bc_board[mse.m_x][mse.m_y]); |
624 | m_bc_score->sub(color, m_bc_board[mse.m_x][mse.m_y]); |
625 | m_board[mse.m_x][mse.m_y] = opponent; |
626 | } |
627 | |
628 | // Now remove the new piece that we put down. |
629 | m_board[xplay][yplay] = NoColor; |
630 | m_score->sub(color, 1); |
631 | m_bc_score->sub(color, m_bc_board[xplay][yplay]); |
632 | |
633 | // Return a suitable value. |
634 | if (number_of_turned < 1 || interrupted()) |
635 | return ILLEGAL_VALUE; |
636 | else |
637 | return retval; |
638 | } |
639 | |
640 | |
641 | // Generate all legal moves from the current position, and do a search |
642 | // to see the value of them. This function returns the value of the |
643 | // most valuable move, but not the move itself. |
644 | // |
645 | |
646 | int Engine::TryAllMoves(ChipColor opponent, int level, int cutoffval, |
647 | quint64 opponentbits, quint64 colorbits) |
648 | { |
649 | int maxval = -LARGEINT; |
650 | |
651 | // Keep GUI alive by calling the event loop. |
652 | yield(); |
653 | |
654 | quint64 null_bits; |
655 | null_bits = 0; |
656 | |
657 | for (int x = 1; x < 9; x++) { |
658 | for (int y = 1; y < 9; y++) { |
659 | if (m_board[x][y] == NoColor |
660 | && (m_neighbor_bits[x][y] & colorbits) != null_bits) { |
661 | int val = ComputeMove2(x, y, opponent, level + 1, maxval, opponentbits, |
662 | colorbits); |
663 | |
664 | if (val != ILLEGAL_VALUE && val > maxval) { |
665 | maxval = val; |
666 | if (maxval > -cutoffval || interrupted()) |
667 | break; |
668 | } |
669 | } |
670 | } |
671 | |
672 | if (maxval > -cutoffval || interrupted()) |
673 | break; |
674 | } |
675 | |
676 | if (interrupted()) |
677 | return -LARGEINT; |
678 | |
679 | return maxval; |
680 | } |
681 | |
682 | |
683 | // Calculate a heuristic value for the current position. If we are at |
684 | // the end of the game, do this by counting the pieces. Otherwise do |
685 | // it by combining the score using the number of pieces, and the score |
686 | // using the board control values. |
687 | // |
688 | |
689 | int Engine::EvaluatePosition(ChipColor color) |
690 | { |
691 | int retval; |
692 | |
693 | ChipColor opponent = Utils::opponentColorFor(color); |
694 | |
695 | int score_color = m_score->score(color); |
696 | int score_opponent = m_score->score(opponent); |
697 | |
698 | if (m_exhaustive) |
699 | retval = score_color - score_opponent; |
700 | else { |
701 | retval = (100 - m_coeff) * |
702 | (m_score->score(color) - m_score->score(opponent)) |
703 | + m_coeff * BC_WEIGHT * (m_bc_score->score(color) |
704 | - m_bc_score->score(opponent)); |
705 | } |
706 | |
707 | return retval; |
708 | } |
709 | |
710 | |
711 | // Calculate bitmaps for each square, and also for neighbors of each |
712 | // square. |
713 | // |
714 | |
715 | void Engine::SetupBits() |
716 | { |
717 | //m_coord_bit = new long[9][9]; |
718 | //m_neighbor_bits = new long[9][9]; |
719 | |
720 | quint64 bits = 1; |
721 | |
722 | // Store a 64 bit unsigned it with the corresponding bit set for |
723 | // each square. |
724 | for (int i = 1; i < 9; i++) |
725 | for (int j = 1; j < 9; j++) { |
726 | m_coord_bit[i][j] = bits; |
727 | bits *= 2; |
728 | } |
729 | |
730 | // Store a bitmap consisting of all neighbors for each square. |
731 | for (int i = 1; i < 9; i++) |
732 | for (int j = 1; j < 9; j++) { |
733 | m_neighbor_bits[i][j] = 0; |
734 | |
735 | for (int xinc = -1; xinc <= 1; xinc++) |
736 | for (int yinc = -1; yinc <= 1; yinc++) { |
737 | if (xinc != 0 || yinc != 0) |
738 | if (i + xinc > 0 && i + xinc < 9 && j + yinc > 0 && j + yinc < 9) |
739 | m_neighbor_bits[i][j] |= m_coord_bit[i + xinc][j + yinc]; |
740 | } |
741 | } |
742 | } |
743 | |
744 | |
745 | // Set up the board control values that will be used in evaluation of |
746 | // the position. |
747 | // |
748 | |
749 | void Engine::SetupBcBoard() |
750 | { |
751 | // JAVA m_bc_board = new int[9][9]; |
752 | |
753 | for (int i = 1; i < 9; i++) |
754 | for (int j = 1; j < 9; j++) { |
755 | if (i == 2 || i == 7) |
756 | m_bc_board[i][j] = -1; |
757 | else |
758 | m_bc_board[i][j] = 0; |
759 | |
760 | if (j == 2 || j == 7) |
761 | m_bc_board[i][j] -= 1; |
762 | } |
763 | |
764 | m_bc_board[1][1] = 2; |
765 | m_bc_board[8][1] = 2; |
766 | m_bc_board[1][8] = 2; |
767 | m_bc_board[8][8] = 2; |
768 | |
769 | m_bc_board[1][2] = -1; |
770 | m_bc_board[2][1] = -1; |
771 | m_bc_board[1][7] = -1; |
772 | m_bc_board[7][1] = -1; |
773 | m_bc_board[8][2] = -1; |
774 | m_bc_board[2][8] = -1; |
775 | m_bc_board[8][7] = -1; |
776 | m_bc_board[7][8] = -1; |
777 | } |
778 | |
779 | |
780 | // Calculate the board control score. |
781 | // |
782 | |
783 | int Engine::CalcBcScore(ChipColor color) |
784 | { |
785 | int sum = 0; |
786 | |
787 | for (int i = 1; i < 9; i++) |
788 | for (int j = 1; j < 9; j++) |
789 | if (m_board[i][j] == color) |
790 | sum += m_bc_board[i][j]; |
791 | |
792 | return sum; |
793 | } |
794 | |
795 | |
796 | // Calculate a bitmap of the occupied squares for a certain color. |
797 | // |
798 | |
799 | quint64 Engine::ComputeOccupiedBits(ChipColor color) |
800 | { |
801 | quint64 retval = 0; |
802 | |
803 | for (int i = 1; i < 9; i++) |
804 | for (int j = 1; j < 9; j++) |
805 | if (m_board[i][j] == color) retval |= m_coord_bit[i][j]; |
806 | |
807 | return retval; |
808 | } |
809 | |
810 | |