Warning, file /games/kreversi/src/Engine.cpp was not indexed or was modified since last indexation (in which case cross-reference links may be missing, inaccurate or erroneous).
0001 /* 0002 SPDX-FileCopyrightText: 1997 Mario Weilguni <mweilguni@sime.com> 0003 0004 SPDX-License-Identifier: GPL-2.0-or-later 0005 */ 0006 0007 /******************************************************************* 0008 * 0009 * 0010 * KREVERSI 0011 * 0012 * 0013 ******************************************************************* 0014 * 0015 * A Reversi (or sometimes called Othello) game 0016 * 0017 ******************************************************************* 0018 * 0019 * Created 1997 by Mario Weilguni <mweilguni@sime.com>. This file 0020 * is ported from Mats Luthman's <Mats.Luthman@sylog.se> JAVA applet. 0021 * Many thanks to Mr. Luthman who has allowed me to put this port 0022 * under the GNU GPL. Without his wonderful game engine kreversi 0023 * would be just another of those Reversi programs a five year old 0024 * child could beat easily. But with it it's a worthy opponent! 0025 * 0026 * If you are interested on the JAVA applet of Mr. Luthman take a 0027 * look at http://www.luthman.nu/Othello/Othello.html 0028 */ 0029 0030 // The class Engine produces moves from a Game object through calls to the 0031 // function ComputeMove(). 0032 // 0033 // First of all: this is meant to be a simple example of a game playing 0034 // program. Not everything is done in the most clever way, particularly not 0035 // the way the moves are searched, but it is hopefully made in a way that makes 0036 // it easy to understand. The function ComputeMove2() that does all the work 0037 // is actually not much more than a hundred lines. Much could be done to 0038 // make the search faster though, I'm perfectly aware of that. Feel free 0039 // to experiment. 0040 // 0041 // The method used to generate the moves is called minimax tree search with 0042 // alpha-beta pruning to a fixed depth. In short this means that all possible 0043 // moves a predefined number of moves ahead are either searched or refuted 0044 // with a method called alpha-beta pruning. A more thorough explanation of 0045 // this method could be found at the world wide web at 0046 // https://cis.temple.edu/~ingargio/cis587/readings/alpha-beta.html 0047 // at the time this was written. Searching for "minimax" would also point 0048 // you to information on this subject. It is probably possible to understand 0049 // this method by reading the source code though, it is not that complicated. 0050 // 0051 // At every leaf node at the search tree, the resulting position is evaluated. 0052 // Two things are considered when evaluating a position: the number of pieces 0053 // of each color and at which squares the pieces are located. Pieces at the 0054 // corners are valuable and give a high value, and having pieces at squares 0055 // next to a corner is not very good and they give a lower value. In the 0056 // beginning of a game it is more important to have pieces on "good" squares, 0057 // but towards the end the total number of pieces of each color is given a 0058 // higher weight. Other things, like how many legal moves that can be made in a 0059 // position, and the number of pieces that can never be turned would probably 0060 // make the program stronger if they were considered in evaluating a position, 0061 // but that would make things more complicated (this was meant to be very 0062 // simple example) and would also slow down computation (considerably?). 0063 // 0064 // The member m_board[10][10]) holds the current position during the 0065 // computation. It is initiated at the start of ComputeMove() and 0066 // every move that is made during the search is made on this board. It should 0067 // be noted that 1 to 8 is used for the actual board, but 0 and 9 can be 0068 // used too (they are always empty). This is practical when turning pieces 0069 // when moves are made on the board. Every piece that is put on the board 0070 // or turned is saved in the stack m_squarestack (see class SquareStack) so 0071 // every move can easily be reversed after the search in a node is completed. 0072 // 0073 // The member m_bc_board[][] holds board control values for each square 0074 // and is initiated by a call to the function private void SetupBcBoard() 0075 // from Engines constructor. It is used in evaluation of positions except 0076 // when the game tree is searched all the way to the end of the game. 0077 // 0078 // The two members m_coord_bit[9][9] and m_neighbor_bits[9][9] are used to 0079 // speed up the tree search. This goes against the principle of keeping things 0080 // simple, but to understand the program you do not need to understand them 0081 // at all. They are there to make it possible to throw away moves where 0082 // the piece that is played is not adjacent to a piece of opposite color 0083 // at an early stage (because they could never be legal). It should be 0084 // pointed out that not all moves that pass this test are legal, there will 0085 // just be fewer moves that have to be tested in a more time consuming way. 0086 // 0087 // There are also two other members that should be mentioned: Score m_score 0088 // and Score m_bc_score. They hold the number of pieces of each color and 0089 // the sum of the board control values for each color during the search 0090 // (this is faster than counting at every leaf node). 0091 // 0092 0093 // The classes SquareStackEntry and SquareStack implement a 0094 // stack that is used by Engine to store pieces that are turned during 0095 // searching (see ComputeMove()). 0096 // 0097 // The class MoveAndValue is used by Engine to store all possible moves 0098 // at the first level and the values that were calculated for them. 0099 // This makes it possible to select a random move among those with equal 0100 // or nearly equal value after the search is completed. 0101 0102 #include "Engine.h" 0103 0104 #include <QApplication> 0105 0106 // ================================================================ 0107 // Classes SquareStackEntry and SquareStack 0108 0109 0110 // A SquareStack is used to store changes to the squares on the board 0111 // during search. 0112 0113 0114 inline void SquareStackEntry::setXY(int x, int y) 0115 { 0116 m_x = x; 0117 m_y = y; 0118 } 0119 0120 0121 SquareStackEntry::SquareStackEntry() 0122 { 0123 setXY(0, 0); 0124 } 0125 0126 0127 // ---------------------------------------------------------------- 0128 0129 0130 SquareStack::SquareStack() 0131 { 0132 init(0); 0133 } 0134 0135 0136 SquareStack::SquareStack(int size) 0137 { 0138 init(size); 0139 } 0140 0141 0142 void SquareStack::resize(int size) 0143 { 0144 m_squarestack.resize(size); 0145 } 0146 0147 0148 // (Re)initialize the stack so that is empty, and at the same time 0149 // resize it to 'size'. 0150 // 0151 0152 void SquareStack::init(int size) 0153 { 0154 resize(size); 0155 0156 m_top = 0; 0157 for (int i = 0; i < size; i++) 0158 m_squarestack[i].setXY(0, 0); 0159 } 0160 0161 0162 0163 inline SquareStackEntry SquareStack::Pop() 0164 { 0165 return m_squarestack[--m_top]; 0166 } 0167 0168 0169 inline void SquareStack::Push(int x, int y) 0170 { 0171 m_squarestack[m_top].m_x = x; 0172 m_squarestack[m_top++].m_y = y; 0173 } 0174 0175 0176 // ================================================================ 0177 // Class MoveAndValue 0178 0179 0180 // Class MoveAndValue aggregates a move with its value. 0181 // 0182 0183 0184 inline void MoveAndValue::setXYV(int x, int y, int value) 0185 { 0186 m_x = x; 0187 m_y = y; 0188 m_value = value; 0189 } 0190 0191 0192 MoveAndValue::MoveAndValue() 0193 { 0194 setXYV(0, 0, 0); 0195 } 0196 0197 0198 MoveAndValue::MoveAndValue(int x, int y, int value) 0199 { 0200 setXYV(x, y, value); 0201 } 0202 0203 // ================================================================ 0204 // class Score 0205 0206 /* This class keeps track of the score for both colors. Such a score 0207 * could be either the number of pieces, the score from the evaluation 0208 * function or anything similar. 0209 */ 0210 class Score 0211 { 0212 public: 0213 Score() { 0214 m_score[White] = 0; 0215 m_score[Black] = 0; 0216 } 0217 0218 uint score(ChipColor color) const { 0219 return m_score[color]; 0220 } 0221 0222 void set(ChipColor color, uint score) { 0223 m_score[color] = score; 0224 } 0225 void inc(ChipColor color) { 0226 m_score[color]++; 0227 } 0228 void dec(ChipColor color) { 0229 m_score[color]--; 0230 } 0231 void add(ChipColor color, uint s) { 0232 m_score[color] += s; 0233 } 0234 void sub(ChipColor color, uint s) { 0235 m_score[color] -= s; 0236 } 0237 0238 private: 0239 uint m_score[2]; 0240 }; 0241 0242 // ================================================================ 0243 // The Engine itself 0244 0245 0246 // Some special values used in the search. 0247 static const int LARGEINT = 99999; 0248 static const int ILLEGAL_VALUE = 8888888; 0249 static const int BC_WEIGHT = 3; 0250 0251 0252 Engine::Engine(int st, int sd)/* : SuperEngine(st, sd) */ 0253 : m_strength(st) 0254 , m_random(sd) 0255 , m_computingMove(false) 0256 { 0257 m_score = new Score; 0258 m_bc_score = new Score; 0259 SetupBcBoard(); 0260 SetupBits(); 0261 } 0262 0263 0264 Engine::Engine(int st) //: SuperEngine(st) 0265 : m_strength(st) 0266 , m_random(QRandomGenerator::global()->generate()) 0267 , m_computingMove(false) 0268 { 0269 m_score = new Score; 0270 m_bc_score = new Score; 0271 SetupBcBoard(); 0272 SetupBits(); 0273 } 0274 0275 0276 Engine::Engine()// : SuperEngine(1) 0277 : m_strength(1) 0278 , m_random(QRandomGenerator::global()->generate()) 0279 , m_computingMove(false) 0280 { 0281 m_score = new Score; 0282 m_bc_score = new Score; 0283 SetupBcBoard(); 0284 SetupBits(); 0285 } 0286 0287 Engine::~Engine() 0288 { 0289 delete m_score; 0290 delete m_bc_score; 0291 } 0292 0293 // keep GUI alive 0294 void Engine::yield() 0295 { 0296 qApp->processEvents(); 0297 } 0298 0299 0300 // Calculate the best move from the current position, and return it. 0301 0302 KReversiMove Engine::computeMove(const KReversiGame& game, bool competitive) 0303 { 0304 if (m_computingMove) 0305 return KReversiMove(); 0306 0307 m_computingMove = true; 0308 0309 ChipColor color; 0310 0311 // A competitive game is one where we try our damnedest to make the 0312 // best move. The opposite is a casual game where the engine might 0313 // make "a mistake". The idea behind this is not to scare away 0314 // newbies. The member m_competitive is used during search for this 0315 // very move. 0316 m_competitive = competitive; 0317 0318 // Suppose that we should give a heuristic evaluation. If we are 0319 // close to the end of the game we can make an exhaustive search, 0320 // but that case is determined further down. 0321 m_exhaustive = false; 0322 0323 // Get the color to calculate the move for. 0324 color = game.currentPlayer(); 0325 if (color == NoColor) { 0326 m_computingMove = false; 0327 return KReversiMove(); 0328 } 0329 0330 // Figure out the current score 0331 m_score->set(White, game.playerScore(White)); 0332 m_score->set(Black, game.playerScore(Black)); 0333 0334 // Treat the first move as a special case (we can basically just 0335 // pick a move at random). 0336 if (m_score->score(White) + m_score->score(Black) == 4) { 0337 m_computingMove = false; 0338 return ComputeFirstMove(game); 0339 } 0340 0341 // Let there be room for 3000 changes during the recursive search. 0342 // This is more than will ever be needed. 0343 m_squarestack.init(3000); 0344 0345 // Get the search depth. If we are close to the end of the game, 0346 // the number of possible moves goes down, so we can search deeper 0347 // without using more time. 0348 m_depth = m_strength; 0349 if (m_score->score(White) + m_score->score(Black) + m_depth + 3 >= 64) 0350 m_depth = 64 - m_score->score(White) - m_score->score(Black); 0351 else if (m_score->score(White) + m_score->score(Black) + m_depth + 4 >= 64) 0352 m_depth += 2; 0353 else if (m_score->score(White) + m_score->score(Black) + m_depth + 5 >= 64) 0354 m_depth++; 0355 0356 // If we are very close to the end, we can even make the search 0357 // exhaustive. 0358 if (m_score->score(White) + m_score->score(Black) + m_depth >= 64) 0359 m_exhaustive = true; 0360 0361 // The evaluation is a linear combination of the score (number of 0362 // pieces) and the sum of the scores for the squares (given by 0363 // m_bc_score). The earlier in the game, the more we use the square 0364 // values and the later in the game the more we use the number of 0365 // pieces. 0366 m_coeff = 100 - (100 * 0367 (m_score->score(White) + m_score->score(Black) 0368 + m_depth - 4)) / 60; 0369 0370 // Initialize the board that we use for the search. 0371 for (uint x = 0; x < 10; x++) 0372 for (uint y = 0; y < 10; y++) { 0373 if (1 <= x && x <= 8 0374 && 1 <= y && y <= 8) 0375 m_board[x][y] = game.chipColorAt(KReversiPos(y - 1, x - 1)); 0376 else 0377 m_board[x][y] = NoColor; 0378 } 0379 0380 // Initialize a lot of stuff that we will use in the search. 0381 0382 // Initialize m_bc_score to the current bc score. This is kept 0383 // up-to-date incrementally so that way we won't have to calculate 0384 // it from scratch for each evaluation. 0385 m_bc_score->set(White, CalcBcScore(White)); 0386 m_bc_score->set(Black, CalcBcScore(Black)); 0387 0388 quint64 colorbits = ComputeOccupiedBits(color); 0389 quint64 opponentbits = ComputeOccupiedBits(Utils::opponentColorFor(color)); 0390 0391 int maxval = -LARGEINT; 0392 int max_x = 0; 0393 int max_y = 0; 0394 0395 MoveAndValue moves[60]; 0396 int number_of_moves = 0; 0397 int number_of_maxval = 0; 0398 0399 setInterrupt(false); 0400 0401 quint64 null_bits; 0402 null_bits = 0; 0403 0404 // The main search loop. Step through all possible moves and keep 0405 // track of the most valuable one. This move is stored in 0406 // (max_x, max_y) and the value is stored in maxval. 0407 m_nodes_searched = 0; 0408 for (int x = 1; x < 9; x++) { 0409 for (int y = 1; y < 9; y++) { 0410 // Don't bother with non-empty squares and squares that aren't 0411 // neighbors to opponent pieces. 0412 if (m_board[x][y] != NoColor 0413 || (m_neighbor_bits[x][y] & opponentbits) == null_bits) 0414 continue; 0415 0416 0417 int val = ComputeMove2(x, y, color, 1, maxval, 0418 colorbits, opponentbits); 0419 0420 if (val != ILLEGAL_VALUE) { 0421 moves[number_of_moves++].setXYV(x, y, val); 0422 0423 // If the move is better than all previous moves, then record 0424 // this fact... 0425 if (val > maxval) { 0426 0427 // ...except that we want to make the computer miss some 0428 // good moves so that beginners can play against the program 0429 // and not always lose. However, we only do this if the 0430 // user wants a casual game, which is set in the settings 0431 // dialog. 0432 int randi = m_random.bounded(7); 0433 if (maxval == -LARGEINT 0434 || m_competitive 0435 || randi < (int) m_strength) { 0436 maxval = val; 0437 max_x = x; 0438 max_y = y; 0439 0440 number_of_maxval = 1; 0441 } 0442 } else if (val == maxval) 0443 number_of_maxval++; 0444 } 0445 0446 // Jump out prematurely if interrupt is set. 0447 if (interrupted()) 0448 break; 0449 } 0450 } 0451 0452 // long endtime = times(&tmsdummy); 0453 0454 // If there are more than one best move, the pick one randomly. 0455 if (number_of_maxval > 1) { 0456 int r = m_random.bounded(number_of_maxval) + 1; 0457 int i; 0458 0459 for (i = 0; i < number_of_moves; ++i) { 0460 if (moves[i].m_value == maxval && --r <= 0) 0461 break; 0462 } 0463 0464 max_x = moves[i].m_x; 0465 max_y = moves[i].m_y; 0466 } 0467 0468 m_computingMove = false; 0469 // Return a suitable move. 0470 if (interrupted()) 0471 return KReversiMove(NoColor, -1, -1); 0472 else if (maxval != -LARGEINT) 0473 return KReversiMove(color, max_y - 1, max_x - 1); 0474 else 0475 return KReversiMove(NoColor, -1, -1); 0476 } 0477 0478 0479 // Get the first move. We can pick any move at random. 0480 // 0481 0482 KReversiMove Engine::ComputeFirstMove(const KReversiGame& game) 0483 { 0484 int r; 0485 ChipColor color = game.currentPlayer(); 0486 0487 r = m_random.bounded(4) + 1; 0488 0489 if (color == White) { 0490 if (r == 1) return KReversiMove(color, 4, 2); 0491 else if (r == 2) return KReversiMove(color, 5, 3); 0492 else if (r == 3) return KReversiMove(color, 2, 4); 0493 else return KReversiMove(color, 3, 5); 0494 } else { 0495 if (r == 1) return KReversiMove(color, 3, 2); 0496 else if (r == 2) return KReversiMove(color, 5, 4); 0497 else if (r == 3) return KReversiMove(color, 2, 3); 0498 else return KReversiMove(color, 4, 5); 0499 } 0500 } 0501 0502 0503 // Play a move at (xplay, yplay) and generate a value for it. If we 0504 // are at the maximum search depth, we get the value by calling 0505 // EvaluatePosition(), otherwise we get it by performing an alphabeta 0506 // search. 0507 // 0508 0509 int Engine::ComputeMove2(int xplay, int yplay, ChipColor color, int level, 0510 int cutoffval, quint64 colorbits, 0511 quint64 opponentbits) 0512 { 0513 int number_of_turned = 0; 0514 SquareStackEntry mse; 0515 ChipColor opponent = Utils::opponentColorFor(color); 0516 0517 m_nodes_searched++; 0518 0519 // Put the piece on the board and incrementally update scores and bitmaps. 0520 m_board[xplay][yplay] = color; 0521 colorbits |= m_coord_bit[xplay][yplay]; 0522 m_score->inc(color); 0523 m_bc_score->add(color, m_bc_board[xplay][yplay]); 0524 0525 // Loop through all 8 directions and turn the pieces that can be turned. 0526 for (int xinc = -1; xinc <= 1; xinc++) 0527 for (int yinc = -1; yinc <= 1; yinc++) { 0528 if (xinc == 0 && yinc == 0) 0529 continue; 0530 0531 int x, y; 0532 0533 for (x = xplay + xinc, y = yplay + yinc; m_board[x][y] == opponent; 0534 x += xinc, y += yinc) 0535 ; 0536 0537 // If we found the end of a turnable row, then go back and turn 0538 // all pieces on the way back. Also push the squares with 0539 // turned pieces on the squarestack so that we can undo the move 0540 // later. 0541 if (m_board[x][y] == color) 0542 for (x -= xinc, y -= yinc; x != xplay || y != yplay; 0543 x -= xinc, y -= yinc) { 0544 m_board[x][y] = color; 0545 colorbits |= m_coord_bit[x][y]; 0546 opponentbits &= ~m_coord_bit[x][y]; 0547 0548 m_squarestack.Push(x, y); 0549 0550 m_bc_score->add(color, m_bc_board[x][y]); 0551 m_bc_score->sub(opponent, m_bc_board[x][y]); 0552 number_of_turned++; 0553 } 0554 } 0555 0556 int retval = -LARGEINT; 0557 0558 // If we managed to turn at least one piece, then (xplay, yplay) was 0559 // a legal move. Now find out the value of the move. 0560 if (number_of_turned > 0) { 0561 0562 // First adjust the number of pieces for each side. 0563 m_score->add(color, number_of_turned); 0564 m_score->sub(opponent, number_of_turned); 0565 0566 // If we are at the bottom of the search, get the evaluation. 0567 if (level >= m_depth) 0568 retval = EvaluatePosition(color); // Terminal node 0569 else { 0570 int maxval = TryAllMoves(opponent, level, cutoffval, opponentbits, 0571 colorbits); 0572 0573 if (maxval != -LARGEINT) 0574 retval = -maxval; 0575 else { 0576 0577 // No possible move for the opponent, it is colors turn again: 0578 retval = TryAllMoves(color, level, -LARGEINT, colorbits, opponentbits); 0579 0580 if (retval == -LARGEINT) { 0581 0582 // No possible move for anybody => end of game: 0583 int finalscore = m_score->score(color) - m_score->score(opponent); 0584 0585 if (m_exhaustive) 0586 retval = finalscore; 0587 else { 0588 // Take a sure win and avoid a sure loss (may not be optimal): 0589 0590 if (finalscore > 0) 0591 retval = LARGEINT - 65 + finalscore; 0592 else if (finalscore < 0) 0593 retval = -(LARGEINT - 65 + finalscore); 0594 else 0595 retval = 0; 0596 } 0597 } 0598 } 0599 } 0600 0601 m_score->add(opponent, number_of_turned); 0602 m_score->sub(color, number_of_turned); 0603 } 0604 0605 // Undo the move. Start by unturning the turned pieces. 0606 for (int i = number_of_turned; i > 0; i--) { 0607 mse = m_squarestack.Pop(); 0608 m_bc_score->add(opponent, m_bc_board[mse.m_x][mse.m_y]); 0609 m_bc_score->sub(color, m_bc_board[mse.m_x][mse.m_y]); 0610 m_board[mse.m_x][mse.m_y] = opponent; 0611 } 0612 0613 // Now remove the new piece that we put down. 0614 m_board[xplay][yplay] = NoColor; 0615 m_score->sub(color, 1); 0616 m_bc_score->sub(color, m_bc_board[xplay][yplay]); 0617 0618 // Return a suitable value. 0619 if (number_of_turned < 1 || interrupted()) 0620 return ILLEGAL_VALUE; 0621 else 0622 return retval; 0623 } 0624 0625 0626 // Generate all legal moves from the current position, and do a search 0627 // to see the value of them. This function returns the value of the 0628 // most valuable move, but not the move itself. 0629 // 0630 0631 int Engine::TryAllMoves(ChipColor opponent, int level, int cutoffval, 0632 quint64 opponentbits, quint64 colorbits) 0633 { 0634 int maxval = -LARGEINT; 0635 0636 // Keep GUI alive by calling the event loop. 0637 yield(); 0638 0639 quint64 null_bits; 0640 null_bits = 0; 0641 0642 for (int x = 1; x < 9; x++) { 0643 for (int y = 1; y < 9; y++) { 0644 if (m_board[x][y] == NoColor 0645 && (m_neighbor_bits[x][y] & colorbits) != null_bits) { 0646 int val = ComputeMove2(x, y, opponent, level + 1, maxval, opponentbits, 0647 colorbits); 0648 0649 if (val != ILLEGAL_VALUE && val > maxval) { 0650 maxval = val; 0651 if (maxval > -cutoffval || interrupted()) 0652 break; 0653 } 0654 } 0655 } 0656 0657 if (maxval > -cutoffval || interrupted()) 0658 break; 0659 } 0660 0661 if (interrupted()) 0662 return -LARGEINT; 0663 0664 return maxval; 0665 } 0666 0667 0668 // Calculate a heuristic value for the current position. If we are at 0669 // the end of the game, do this by counting the pieces. Otherwise do 0670 // it by combining the score using the number of pieces, and the score 0671 // using the board control values. 0672 // 0673 0674 int Engine::EvaluatePosition(ChipColor color) 0675 { 0676 int retval; 0677 0678 ChipColor opponent = Utils::opponentColorFor(color); 0679 0680 int score_color = m_score->score(color); 0681 int score_opponent = m_score->score(opponent); 0682 0683 if (m_exhaustive) 0684 retval = score_color - score_opponent; 0685 else { 0686 retval = (100 - m_coeff) * 0687 (m_score->score(color) - m_score->score(opponent)) 0688 + m_coeff * BC_WEIGHT * (m_bc_score->score(color) 0689 - m_bc_score->score(opponent)); 0690 } 0691 0692 return retval; 0693 } 0694 0695 0696 // Calculate bitmaps for each square, and also for neighbors of each 0697 // square. 0698 // 0699 0700 void Engine::SetupBits() 0701 { 0702 //m_coord_bit = new long[9][9]; 0703 //m_neighbor_bits = new long[9][9]; 0704 0705 quint64 bits = 1; 0706 0707 // Store a 64 bit unsigned it with the corresponding bit set for 0708 // each square. 0709 for (int i = 1; i < 9; i++) 0710 for (int j = 1; j < 9; j++) { 0711 m_coord_bit[i][j] = bits; 0712 bits *= 2; 0713 } 0714 0715 // Store a bitmap consisting of all neighbors for each square. 0716 for (int i = 1; i < 9; i++) 0717 for (int j = 1; j < 9; j++) { 0718 m_neighbor_bits[i][j] = 0; 0719 0720 for (int xinc = -1; xinc <= 1; xinc++) 0721 for (int yinc = -1; yinc <= 1; yinc++) { 0722 if (xinc != 0 || yinc != 0) 0723 if (i + xinc > 0 && i + xinc < 9 && j + yinc > 0 && j + yinc < 9) 0724 m_neighbor_bits[i][j] |= m_coord_bit[i + xinc][j + yinc]; 0725 } 0726 } 0727 } 0728 0729 0730 // Set up the board control values that will be used in evaluation of 0731 // the position. 0732 // 0733 0734 void Engine::SetupBcBoard() 0735 { 0736 // JAVA m_bc_board = new int[9][9]; 0737 0738 for (int i = 1; i < 9; i++) 0739 for (int j = 1; j < 9; j++) { 0740 if (i == 2 || i == 7) 0741 m_bc_board[i][j] = -1; 0742 else 0743 m_bc_board[i][j] = 0; 0744 0745 if (j == 2 || j == 7) 0746 m_bc_board[i][j] -= 1; 0747 } 0748 0749 m_bc_board[1][1] = 2; 0750 m_bc_board[8][1] = 2; 0751 m_bc_board[1][8] = 2; 0752 m_bc_board[8][8] = 2; 0753 0754 m_bc_board[1][2] = -1; 0755 m_bc_board[2][1] = -1; 0756 m_bc_board[1][7] = -1; 0757 m_bc_board[7][1] = -1; 0758 m_bc_board[8][2] = -1; 0759 m_bc_board[2][8] = -1; 0760 m_bc_board[8][7] = -1; 0761 m_bc_board[7][8] = -1; 0762 } 0763 0764 0765 // Calculate the board control score. 0766 // 0767 0768 int Engine::CalcBcScore(ChipColor color) 0769 { 0770 int sum = 0; 0771 0772 for (int i = 1; i < 9; i++) 0773 for (int j = 1; j < 9; j++) 0774 if (m_board[i][j] == color) 0775 sum += m_bc_board[i][j]; 0776 0777 return sum; 0778 } 0779 0780 0781 // Calculate a bitmap of the occupied squares for a certain color. 0782 // 0783 0784 quint64 Engine::ComputeOccupiedBits(ChipColor color) 0785 { 0786 quint64 retval = 0; 0787 0788 for (int i = 1; i < 9; i++) 0789 for (int j = 1; j < 9; j++) 0790 if (m_board[i][j] == color) retval |= m_coord_bit[i][j]; 0791 0792 return retval; 0793 } 0794