File indexing completed on 2024-05-19 07:52:01
0001 /* 0002 This file is part of the game 'KJumpingCube' 0003 0004 SPDX-FileCopyrightText: 2012 Ian Wadham <iandw.au@gmail.com> 0005 0006 SPDX-License-Identifier: GPL-2.0-or-later 0007 */ 0008 0009 #ifndef AI_MAIN_H 0010 #define AI_MAIN_H 0011 0012 #include <QList> 0013 #include <QThread> 0014 #include <QMutex> 0015 #include <QRandomGenerator> 0016 0017 #include "ai_base.h" 0018 #include "ai_box.h" 0019 0020 class ThreadedAI; 0021 0022 struct Move 0023 { 0024 int index; 0025 int val; 0026 }; 0027 0028 /** 0029 * Class AI_Main computes a (good) possible move from a given position. 0030 * 0031 * It puts a value on every cube by looking at its neighbours and picks a 0032 * short list of likely cubes to move (it takes too long to check every 0033 * possible move). It then simulates what would happen if you click on 0034 * these cubes. This is all done recursively to a certain depth and the 0035 * position is valued. The move that leads to the best position is chosen. 0036 * 0037 * @short The "computer player" of KJumpingCube. 0038 */ 0039 0040 /** 0041 * Number of available skill-levels for computer players. Must be consistent 0042 * with the Qt Designer form and the file "settings.ui" that it generates. 0043 */ 0044 const int nSkillLevels = 5; 0045 0046 /** 0047 * Extent of lookahead for each computer skill-level. 0 = perform moves and 0048 * evaluate the resulting positions, selecting the move with the best value 0049 * of those being considered. n > 0 = perform n moves recursively, using 0050 * the MiniMax algorithm, then perform one more move and evaluate it, e.g. 0051 * depth 1 causes the computer to evaluate your responses to its moves. 0052 */ 0053 const int depths [nSkillLevels] = {0, 0, 1, 3, 5}; 0054 0055 /** 0056 * The maximum number of moves considered at each level of lookahead. This 0057 * limits the size of the move-tree and the amount of computation involved. 0058 * The most likely moves are chosen using values supplied by assessCube() 0059 * (see the AI_Kepler and AI_Newton classes for examples). 0060 */ 0061 const int maxBreadth = 4; 0062 0063 class AI_Main : public AI_Box 0064 { 0065 // NOTE: Inheriting AI_Box gives AI_Main direct access to AI_Box's protected 0066 // data arrays. Speed of computation is essential here. 0067 Q_OBJECT 0068 public: 0069 /** 0070 * The constructor for the KJumpingCube AI (or "computer player"). 0071 */ 0072 explicit AI_Main (QObject * parent, int side); 0073 ~AI_Main() override; 0074 0075 /** 0076 * Compute a good move for a player from a given position, providing either 0077 * a computer-player move or a hint for a human player. The main calculation 0078 * is threaded and returns its result via signal "done (int index)". 0079 * 0080 * @param player Player for whom a move is to be computed. 0081 * @param box The player's position before the move. 0082 */ 0083 void getMove (const Player player, const AI_Box * box); 0084 0085 int computeMove(); // The threaded part of the move calculation. 0086 0087 // QMutex endMutex; // Use when stopping the threaded calculation? 0088 0089 /** 0090 * Stop the AI, but not till the end of the current cycle. The AI will 0091 * then return the best move found so far, via signal "done (int index)". 0092 */ 0093 void stop(); 0094 0095 /** 0096 * Set skill and AI players according to current preferences or settings. 0097 */ 0098 void setSkill (int skill1, bool kepler1, bool newton1, 0099 int skill2, bool kepler2, bool newton2); 0100 0101 Q_SIGNALS: 0102 /** 0103 * Signal the best move found after the AI search finishes or is stopped. 0104 * 0105 * @param index The index, within the cube box, of the cube to move. 0106 */ 0107 void done (int index); 0108 0109 private: 0110 ThreadedAI * m_thread; // A thread to run computeMove() and tryMoves(). 0111 0112 Player m_player; // The player whose best move is to be found. 0113 0114 int * m_randomSeq; // A random order for trying out moves. 0115 0116 /** 0117 * Recursively check and evaluate moves available at a given position, using 0118 * the MiniMax algorithm. The AI_Box instance (m_box) is used to store 0119 * positions and make moves that follow the KJumpingCube rules. Instances of 0120 * AI_Base (such as m_AI_Kepler or m_AI_Newton) are used to assess possible 0121 * moves and the resulting positions. 0122 * 0123 * @param player Player for whom moves are being evaluated. 0124 * @param level Current level of recursion (i.e. level in move-tree). 0125 * 0126 * @return The best move found and the value of the position reached. 0127 */ 0128 Move tryMoves (Player player, int level); 0129 0130 /** 0131 * Check a position to find moves that are likely to give good results. 0132 * Return at most maxBreadth moves, to reduce computation time in tryMoves(). 0133 * 0134 * @param c2m The array in which likely moves will be stored. 0135 * @param player The player who is to move. 0136 * @param owners The owner of each cube in the box. 0137 * @param values The value of each cube in the box. 0138 * @param maxValues The maximum value of each cube in the box. 0139 * 0140 * @return The number of likely moves found. 0141 */ 0142 int findCubesToMove (Move * c2m, const Player player, const Player * owners, 0143 const int * values, const int * maxValues); 0144 0145 /** 0146 * Make sure a cube box of the correct size is available as a workspace. 0147 * 0148 * @param side The number of rows/columns in the cube box. 0149 */ 0150 void checkWorkspace (const int side); 0151 0152 AI_Base * m_AI_Kepler; // Pointer to a Kepler-style player. 0153 AI_Base * m_AI_Newton; // Pointer to a Newton-style player. 0154 0155 AI_Base * m_ai [3]; // Pointers to AI players 1 and 2 (but not 0). 0156 int m_ai_skill [3]; // Skills of AI players 1 and 2 (but not 0). 0157 int m_ai_maxLevel [3]; // Lookahead of AI players 1 and 2 (but not 0). 0158 0159 AI_Base * m_currentAI; // Pointer to AI for current player. 0160 int m_skill; // Skill of the current player's AI. 0161 int m_maxLevel; // Maximum search depth for current player. 0162 0163 int m_currentLevel; // Current search depth (or lookahead). 0164 0165 bool m_stopped; // True if the AI has to be stopped. 0166 0167 QRandomGenerator m_random; // Random number generator. 0168 0169 #if AILog > 0 0170 public: 0171 // Statistics-gathering procedures. 0172 // ------------------------------- 0173 void startStats(); 0174 void postMove (Player player, int index, int side); 0175 void dumpStats(); 0176 #endif 0177 0178 private: 0179 // Statistical data and methods. 0180 // ----------------------------- 0181 struct SearchStats { 0182 int n_moves; 0183 }; 0184 0185 struct MoveStats { 0186 Player player; 0187 int moveNo; 0188 int x; 0189 int y; 0190 int value; 0191 int n_simulate; 0192 int n_assess; 0193 int nLikelyMoves; 0194 Move * likelyMoves; 0195 QList<SearchStats *> * searchStats; 0196 }; 0197 0198 int m_currentMoveNo; 0199 #if AILog > 0 0200 MoveStats * m_currentMove; 0201 QList<MoveStats *> m_moveStats; 0202 0203 int n_simulate; // Number of moves simulated in the search. 0204 int n_assess; // Number of positions assessed in the search. 0205 0206 void boxPrint (int side, int * owners, int * values); 0207 0208 QString tag (int level); 0209 void initStats (int player); 0210 void saveStats (Move & move); 0211 void saveLikelyMoves (int nMoves, Move * moves); 0212 #endif 0213 }; 0214 0215 #endif //AI_MAIN_H