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
33class ThreadedAI;
34
35struct 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 */
57const 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 */
66const 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 */
74const int maxBreadth = 4;
75
76class 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
81public:
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
114signals:
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
122private:
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
183public:
184 // Statistics-gathering procedures.
185 // -------------------------------
186 void startStats();
187 void postMove (Player player, int index, int side);
188 void dumpStats();
189#endif
190
191private:
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