1 | /* **************************************************************************** |
2 | This file is part of the game 'KJumpingCube' |
3 | |
4 | Copyright (C) 2012 by Ian Wadham <iandw.au@gmail.com> |
5 | |
6 | This program is free software; you can redistribute it and/or modify |
7 | it under the terms of the GNU General Public License as published by |
8 | the Free Software Foundation; either version 2 of the License, or |
9 | (at your option) any later version. |
10 | |
11 | This program is distributed in the hope that it will be useful, |
12 | but WITHOUT ANY WARRANTY; without even the implied warranty of |
13 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
14 | GNU General Public License for more details. |
15 | |
16 | You should have received a copy of the GNU General Public License |
17 | along with this program; if not, write to the Free Software |
18 | Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. |
19 | |
20 | **************************************************************************** */ |
21 | #ifndef AI_MAIN_H |
22 | #define AI_MAIN_H |
23 | |
24 | #include <QList> |
25 | #include <QThread> |
26 | #include <QMutex> |
27 | |
28 | #include <krandomsequence.h> |
29 | |
30 | #include "ai_base.h" |
31 | #include "ai_box.h" |
32 | |
33 | class ThreadedAI; |
34 | |
35 | struct Move |
36 | { |
37 | int index; |
38 | int val; |
39 | }; |
40 | |
41 | /** |
42 | * Class AI_Main computes a (good) possible move from a given position. |
43 | * |
44 | * It puts a value on every cube by looking at its neighbours and picks a |
45 | * short list of likely cubes to move (it takes too long to check every |
46 | * possible move). It then simulates what would happen if you click on |
47 | * these cubes. This is all done recursively to a certain depth and the |
48 | * position is valued. The move that leads to the best position is chosen. |
49 | * |
50 | * @short The "computer player" of KJumpingCube. |
51 | */ |
52 | |
53 | /** |
54 | * Number of available skill-levels for computer players. Must be consistent |
55 | * with the Qt Designer form and the file "settings.ui" that it generates. |
56 | */ |
57 | const int nSkillLevels = 5; |
58 | |
59 | /** |
60 | * Extent of lookahead for each computer skill-level. 0 = perform moves and |
61 | * evaluate the resulting positions, selecting the move with the best value |
62 | * of those being considered. n > 0 = perform n moves recursively, using |
63 | * the MiniMax algorithm, then perform one more move and evaluate it, e.g. |
64 | * depth 1 causes the computer to evaluate your responses to its moves. |
65 | */ |
66 | const int depths [nSkillLevels] = {0, 0, 1, 3, 5}; |
67 | |
68 | /** |
69 | * The maximum number of moves considered at each level of lookahead. This |
70 | * limits the size of the move-tree and the amount of computation involved. |
71 | * The most likely moves are chosen using values supplied by assessCube() |
72 | * (see the AI_Kepler and AI_Newton classes for examples). |
73 | */ |
74 | const int maxBreadth = 4; |
75 | |
76 | class AI_Main : public AI_Box |
77 | { |
78 | // NOTE: Inheriting AI_Box gives AI_Main direct access to AI_Box's protected |
79 | // data arrays. Speed of computation is essential here. |
80 | Q_OBJECT |
81 | public: |
82 | /** |
83 | * The constructor for the KJumpingCube AI (or "computer player"). |
84 | */ |
85 | explicit AI_Main (QObject * parent, int side); |
86 | virtual ~AI_Main(); |
87 | |
88 | /** |
89 | * Compute a good move for a player from a given position, providing either |
90 | * a computer-player move or a hint for a human player. The main calculation |
91 | * is threaded and returns its result via signal "done (int index)". |
92 | * |
93 | * @param player Player for whom a move is to be computed. |
94 | * @param box The player's position before the move. |
95 | */ |
96 | void getMove (const Player player, const AI_Box * box); |
97 | |
98 | int computeMove(); // The threaded part of the move calculation. |
99 | |
100 | // QMutex endMutex; // Use when stopping the threaded calculation? |
101 | |
102 | /** |
103 | * Stop the AI, but not till the end of the current cycle. The AI will |
104 | * then return the best move found so far, via signal "done (int index)". |
105 | */ |
106 | void stop(); |
107 | |
108 | /** |
109 | * Set skill and AI players according to current preferences or settings. |
110 | */ |
111 | void setSkill (int skill1, bool kepler1, bool newton1, |
112 | int skill2, bool kepler2, bool newton2); |
113 | |
114 | signals: |
115 | /** |
116 | * Signal the best move found after the AI search finishes or is stopped. |
117 | * |
118 | * @param index The index, within the cube box, of the cube to move. |
119 | */ |
120 | void done (int index); |
121 | |
122 | private: |
123 | ThreadedAI * m_thread; // A thread to run computeMove() and tryMoves(). |
124 | |
125 | Player m_player; // The player whose best move is to be found. |
126 | |
127 | int * m_randomSeq; // A random order for trying out moves. |
128 | |
129 | /** |
130 | * Recursively check and evaluate moves available at a given position, using |
131 | * the MiniMax algorithm. The AI_Box instance (m_box) is used to store |
132 | * positions and make moves that follow the KJumpingCube rules. Instances of |
133 | * AI_Base (such as m_AI_Kepler or m_AI_Newton) are used to assess possible |
134 | * moves and the resulting positions. |
135 | * |
136 | * @param player Player for whom moves are being evaluated. |
137 | * @param level Current level of recursion (i.e. level in move-tree). |
138 | * |
139 | * @return The best move found and the value of the position reached. |
140 | */ |
141 | Move tryMoves (Player player, int level); |
142 | |
143 | /** |
144 | * Check a position to find moves that are likely to give good results. |
145 | * Return at most maxBreadth moves, to reduce computation time in tryMoves(). |
146 | * |
147 | * @param c2m The array in which likely moves will be stored. |
148 | * @param player The player who is to move. |
149 | * @param owners The owner of each cube in the box. |
150 | * @param values The value of each cube in the box. |
151 | * @param maxValues The maximum value of each cube in the box. |
152 | * |
153 | * @return The number of likely moves found. |
154 | */ |
155 | int findCubesToMove (Move * c2m, const Player player, const Player * owners, |
156 | const int * values, const int * maxValues); |
157 | |
158 | /** |
159 | * Make sure a cube box of the correct size is available as a workspace. |
160 | * |
161 | * @param side The number of rows/columns in the cube box. |
162 | */ |
163 | void checkWorkspace (const int side); |
164 | |
165 | AI_Base * m_AI_Kepler; // Pointer to a Kepler-style player. |
166 | AI_Base * m_AI_Newton; // Pointer to a Newton-style player. |
167 | |
168 | AI_Base * m_ai [3]; // Pointers to AI players 1 and 2 (but not 0). |
169 | int m_ai_skill [3]; // Skills of AI players 1 and 2 (but not 0). |
170 | int m_ai_maxLevel [3]; // Lookahead of AI players 1 and 2 (but not 0). |
171 | |
172 | AI_Base * m_currentAI; // Pointer to AI for current player. |
173 | int m_skill; // Skill of the current player's AI. |
174 | int m_maxLevel; // Maximum search depth for current player. |
175 | |
176 | int m_currentLevel; // Current search depth (or lookahead). |
177 | |
178 | bool m_stopped; // True if the AI has to be stopped. |
179 | |
180 | KRandomSequence m_random; // Random number generator. |
181 | |
182 | #if AILog > 0 |
183 | public: |
184 | // Statistics-gathering procedures. |
185 | // ------------------------------- |
186 | void startStats(); |
187 | void postMove (Player player, int index, int side); |
188 | void dumpStats(); |
189 | #endif |
190 | |
191 | private: |
192 | // Statistical data and methods. |
193 | // ----------------------------- |
194 | struct SearchStats { |
195 | int n_moves; |
196 | }; |
197 | |
198 | struct MoveStats { |
199 | Player player; |
200 | int moveNo; |
201 | int x; |
202 | int y; |
203 | int value; |
204 | int n_simulate; |
205 | int n_assess; |
206 | int nLikelyMoves; |
207 | Move * likelyMoves; |
208 | QList<SearchStats *> * searchStats; |
209 | }; |
210 | |
211 | int m_currentMoveNo; |
212 | #if AILog > 0 |
213 | MoveStats * m_currentMove; |
214 | QList<MoveStats *> m_moveStats; |
215 | |
216 | int n_simulate; // Number of moves simulated in the search. |
217 | int n_assess; // Number of positions assessed in the search. |
218 | |
219 | void boxPrint (int side, int * owners, int * values); |
220 | |
221 | QString tag (int level); |
222 | void initStats (int player); |
223 | void saveStats (Move & move); |
224 | void saveLikelyMoves (int nMoves, Move * moves); |
225 | #endif |
226 | }; |
227 | |
228 | #endif //AI_MAIN_H |
229 | |