Warning, file /games/kreversi/src/Engine.h 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 #ifndef KREVERSI_ENGINE_H 0103 #define KREVERSI_ENGINE_H 0104 0105 #include <QRandomGenerator> 0106 0107 #include "commondefs.h" 0108 #include "kreversigame.h" 0109 class KReversiGame; 0110 0111 0112 // SquareStackEntry and SquareStack are used during search to keep 0113 // track of turned pieces. 0114 0115 class SquareStackEntry 0116 { 0117 public: 0118 SquareStackEntry(); 0119 0120 void setXY(int x, int y); 0121 0122 public: 0123 int m_x; 0124 int m_y; 0125 }; 0126 0127 0128 class SquareStack 0129 { 0130 public: 0131 SquareStack(); 0132 explicit SquareStack(int size); 0133 0134 void resize(int size); 0135 void init(int size); 0136 SquareStackEntry Pop(); 0137 void Push(int x, int y); 0138 0139 private: 0140 QList<SquareStackEntry> m_squarestack; 0141 int m_top; 0142 }; 0143 0144 0145 // Connect a move with its value. 0146 0147 class MoveAndValue 0148 { 0149 public: 0150 MoveAndValue(); 0151 MoveAndValue(int x, int y, int value); 0152 0153 void setXYV(int x, int y, int value); 0154 0155 public: 0156 int m_x; 0157 int m_y; 0158 int m_value; 0159 }; 0160 0161 class Score; 0162 0163 // The real beef of this program: the engine that finds good moves for 0164 // the computer player. 0165 // 0166 class Engine 0167 { 0168 public: 0169 Engine(int st, int sd); 0170 explicit Engine(int st); 0171 Engine(); 0172 0173 ~Engine(); 0174 0175 KReversiMove computeMove(const KReversiGame& game, bool competitive); 0176 bool isThinking() const { 0177 return m_computingMove; 0178 } 0179 0180 void setInterrupt(bool intr) { 0181 m_interrupt = intr; 0182 } 0183 bool interrupted() const { 0184 return m_interrupt; 0185 } 0186 0187 void setStrength(uint strength) { 0188 m_strength = strength; 0189 } 0190 uint strength() const { 0191 return m_strength; 0192 } 0193 private: 0194 KReversiMove ComputeFirstMove(const KReversiGame& game); 0195 int ComputeMove2(int xplay, int yplay, ChipColor color, int level, 0196 int cutoffval, 0197 quint64 colorbits, quint64 opponentbits); 0198 0199 int TryAllMoves(ChipColor opponent, int level, int cutoffval, 0200 quint64 opponentbits, quint64 colorbits); 0201 0202 int EvaluatePosition(ChipColor color); 0203 void SetupBcBoard(); 0204 void SetupBits(); 0205 int CalcBcScore(ChipColor color); 0206 quint64 ComputeOccupiedBits(ChipColor color); 0207 0208 void yield(); 0209 0210 private: 0211 0212 ChipColor m_board[10][10]; 0213 int m_bc_board[9][9]; 0214 Score* m_score; 0215 Score* m_bc_score; 0216 SquareStack m_squarestack; 0217 0218 int m_depth; 0219 int m_coeff; 0220 int m_nodes_searched; 0221 bool m_exhaustive; 0222 bool m_competitive; 0223 0224 uint m_strength; 0225 QRandomGenerator m_random; 0226 bool m_interrupt; 0227 0228 quint64 m_coord_bit[9][9]; 0229 quint64 m_neighbor_bits[9][9]; 0230 0231 bool m_computingMove; 0232 }; 0233 0234 #endif