File indexing completed on 2022-09-27 13:15:56

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