File indexing completed on 2022-11-29 18:40:53

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     QVector<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