1 | /* **************************************************************************** |
2 | Copyright (C) 2012 Ian Wadham <iandw.au@gmail.com> |
3 | |
4 | This program is free software; you can redistribute it and/or modify |
5 | it under the terms of the GNU General Public License as published by |
6 | the Free Software Foundation; either version 2 of the License, or |
7 | (at your option) any later version. |
8 | |
9 | This program is distributed in the hope that it will be useful, |
10 | but WITHOUT ANY WARRANTY; without even the implied warranty of |
11 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
12 | GNU General Public License for more details. |
13 | |
14 | You should have received a copy of the GNU General Public License |
15 | along with this program; if not, write to the Free Software Foundation, Inc., |
16 | 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. |
17 | **************************************************************************** */ |
18 | |
19 | #include "ai_box.h" |
20 | // #include <QStack> |
21 | |
22 | #include <QDebug> |
23 | #include "stdio.h" |
24 | |
25 | AI_Box::AI_Box (QObject * parent, int side) |
26 | : |
27 | QObject (parent) |
28 | { |
29 | m_parent = parent; // IDW test. |
30 | fprintf (stderr, "\nAI_Box CONSTRUCTOR, side = %d\n" , side); |
31 | createBox (side); |
32 | } |
33 | |
34 | AI_Box::~AI_Box() |
35 | { |
36 | destroyBox(); |
37 | } |
38 | |
39 | void AI_Box::createBox (int side) |
40 | { |
41 | m_side = ((side >= minSide) && (side <= maxSide)) ? side : 5; |
42 | m_nCubes = side * side; |
43 | Position * pos = emptyPosition (m_nCubes); |
44 | pos->player = One; |
45 | pos->isAI = false; |
46 | pos->index = 0; |
47 | m_maxValues = new int [m_nCubes]; |
48 | m_neighbors = new int [4 * m_nCubes]; |
49 | m_stack = new int [m_nCubes]; |
50 | m_stackPtr = -1; |
51 | m_owners = pos->owners; |
52 | m_values = pos->values; |
53 | indexNeighbors(); |
54 | clear(); |
55 | m_undoList.append (pos); |
56 | } |
57 | |
58 | void AI_Box::destroyBox() |
59 | { |
60 | delete m_maxValues; |
61 | delete m_neighbors; |
62 | delete m_stack; |
63 | while (! m_undoList.isEmpty()) { |
64 | discard (m_undoList.takeLast()); |
65 | } |
66 | } |
67 | |
68 | void AI_Box::resizeBox (int side) |
69 | { |
70 | destroyBox(); |
71 | createBox (side); |
72 | } |
73 | |
74 | |
75 | // ---------------------------------------------------------------- |
76 | // Moves |
77 | |
78 | |
79 | bool AI_Box::doMove (Player player, int index, MoveUndodata * undodata, QList<int> * steps) |
80 | { |
81 | // Check for move legality. |
82 | Player oldOwner = m_owners[index]; |
83 | if ((oldOwner != player) && (oldOwner != Nobody)) { |
84 | qDebug() << "ILLEGAL MOVE: player" << player << "old" << oldOwner |
85 | << "at" << index/m_side << index%m_side; |
86 | |
87 | return false; // The move is not valid. |
88 | } |
89 | |
90 | if (undodata) { |
91 | undodata->oldCubesToWin[Nobody] = m_cubesToWin[Nobody]; |
92 | undodata->oldCubesToWin[One] = m_cubesToWin[One]; |
93 | undodata->oldCubesToWin[Two] = m_cubesToWin[Two]; |
94 | } |
95 | |
96 | // Bitfield to mark saved cube indices. |
97 | quint64 savedCubes[(maxSide * maxSide - 1) / 64 + 1]; |
98 | for (int i = 0; i < (maxSide * maxSide - 1) / 64 + 1; ++i) |
99 | savedCubes[i] = 0ULL; |
100 | |
101 | // Save old values of changed cubes (owner + value) into the |
102 | // MoveUndodata to be restored by undoMove(). |
103 | int saveCubes = 0; |
104 | if (undodata) { |
105 | undodata->changedCubes[saveCubes++] = ((index << 8) |
106 | | (m_owners[index] << 4) |
107 | | (m_values[index] << 0)); |
108 | savedCubes[index / 64] |= 1ULL << (index % 64); |
109 | |
110 | } |
111 | |
112 | m_stackPtr = -1; |
113 | m_owners[index] = player; // Take ownership if not already owned. |
114 | if (m_maxValues [index] == m_values [index]++) { // Increase the cube. |
115 | m_stack [++m_stackPtr] = index; // Stack an expansion step. |
116 | // fprintf (stderr, "Overload at %d, value %d\n", index, m_values[index]); |
117 | } |
118 | if (steps) { |
119 | steps->append (index + 1); // Record the beginning of the move. |
120 | } |
121 | if (oldOwner != player) { // If owner changed, update cubesToWin. |
122 | m_cubesToWin [oldOwner]++; |
123 | m_cubesToWin [player]--; |
124 | if (m_cubesToWin [player] <= 0) { |
125 | // Append 0 to the move-step list and return player-won. |
126 | if (steps) { |
127 | steps->append (0); |
128 | } |
129 | // printBox(); |
130 | // fprintf (stderr, "PLAYER WON\n"); |
131 | return true;; |
132 | } |
133 | } |
134 | |
135 | while (m_stackPtr >= 0) { |
136 | // Pop the stack and decrease an overloaded cube. |
137 | index = m_stack [m_stackPtr--]; |
138 | |
139 | // fprintf (stderr, " Expand at %d, value %d\n", index, m_values[index]); |
140 | m_values[index] = m_values[index] - m_maxValues[index]; |
141 | |
142 | // Append -index-1 to move list, if not still overloaded. |
143 | if (steps && (m_values[index] <= m_maxValues[index])) { |
144 | steps->append (-index - 1); // Record the end of a step or move. |
145 | } |
146 | |
147 | // Move each neighbor. |
148 | int indexN; |
149 | int offset = index * 4; |
150 | for (int nb = 0; nb < 4; nb++) { |
151 | if ((indexN = m_neighbors [offset + nb]) < 0) |
152 | continue; // No neighbor on this side. |
153 | |
154 | if (undodata && !(savedCubes[indexN / 64] & (1ULL << (indexN % 64)))) { |
155 | undodata->changedCubes[saveCubes++] = ((indexN << 8) |
156 | | (m_owners[indexN] << 4) |
157 | | (m_values[indexN] << 0)); |
158 | savedCubes[indexN / 64] |= 1ULL << (indexN % 64); |
159 | } |
160 | |
161 | // Increase the neighbor and take over ownership. |
162 | oldOwner = m_owners[indexN]; |
163 | m_owners[indexN] = player; |
164 | if (m_maxValues [indexN] == m_values [indexN]++) { |
165 | // Continue a cascade by pushing a new step onto the stack. |
166 | m_stack [++m_stackPtr] = indexN; |
167 | // fprintf (stderr, "Overload at %d, value %d\n", indexN, m_values[indexN]); |
168 | } |
169 | if (steps) { |
170 | steps->append (indexN + 1); // Record beginning of move-step. |
171 | } |
172 | if (oldOwner != player) { // If owner changed, update cubesToWin. |
173 | m_cubesToWin [oldOwner]++; |
174 | m_cubesToWin [player]--; |
175 | } |
176 | } |
177 | if (m_values[index] > m_maxValues[index]) { |
178 | // The cube is still overloaded, so push it back onto the stack. |
179 | m_stack [++m_stackPtr] = index; |
180 | // fprintf (stderr, " RE-Overload at %d, value %d\n", index, m_values[index]); |
181 | } |
182 | if (m_cubesToWin [player] <= 0) { |
183 | // Append 0 to the move-step list and return player-won. |
184 | if (steps) { |
185 | steps->append (0); |
186 | } |
187 | |
188 | // Mark the end of changed cubes in the undodata. |
189 | if (undodata) { |
190 | undodata->changedCubes[saveCubes++] = 0xffff; |
191 | } |
192 | |
193 | // printBox(); |
194 | // fprintf (stderr, "PLAYER WON\n"); |
195 | return true; |
196 | } |
197 | // printBox(); |
198 | } // End while() |
199 | |
200 | if (undodata) { |
201 | undodata->changedCubes[saveCubes++] = 0xffff; |
202 | } |
203 | |
204 | // printBox(); |
205 | return false; |
206 | } |
207 | |
208 | void AI_Box::undoMove (MoveUndodata * undodata) |
209 | { |
210 | m_cubesToWin[Nobody] = undodata->oldCubesToWin[Nobody]; |
211 | m_cubesToWin[One] = undodata->oldCubesToWin[One]; |
212 | m_cubesToWin[Two] = undodata->oldCubesToWin[Two]; |
213 | |
214 | for (int i = 0; undodata->changedCubes[i] != 0xffff; ++i) { |
215 | int index = (undodata->changedCubes[i] >> 8) & 0xff; |
216 | m_owners[index] = Player((undodata->changedCubes[i] >> 4) & 0xf); |
217 | m_values[index] = (undodata->changedCubes[i] >> 0) & 0xf; |
218 | } |
219 | } |
220 | |
221 | |
222 | // ---------------------------------------------------------------- |
223 | // Game history |
224 | |
225 | |
226 | void AI_Box::copyPosition (Player player, bool isAI, int index) |
227 | { |
228 | #if AILog > 4 |
229 | qDebug() << "AI_Box::copyPosition (" << player << "," << isAI << ")" ; |
230 | printBox(); |
231 | #endif |
232 | if (m_undoIndex >= m_undoList.count()) { |
233 | #if AILog > 4 |
234 | qDebug() << "Call emptyPosition (" << m_nCubes << ")" ; |
235 | #endif |
236 | m_undoList.append (emptyPosition (m_nCubes)); |
237 | } |
238 | #if AILog > 4 |
239 | qDebug() << "m_undoIndex" << m_undoIndex << "m_undoList.count()" << m_undoList.count(); |
240 | #endif |
241 | Position * pos = m_undoList.at (m_undoIndex); |
242 | save (pos, player, isAI); |
243 | pos->index = index; // IDW TODO - Do this in save()? |
244 | m_owners = pos->owners; |
245 | m_values = pos->values; |
246 | #if AILog > 4 |
247 | printBox(); |
248 | #endif |
249 | m_undoIndex++; |
250 | m_redoLimit = m_undoIndex; |
251 | } |
252 | |
253 | bool AI_Box::undoPosition (Player & player, bool & isAI, int & index) |
254 | { |
255 | bool result = undoPosition (player); |
256 | if (m_undoIndex > 0) { |
257 | Position * pos = m_undoList.at (m_undoIndex); |
258 | isAI = pos->isAI; |
259 | index = pos->index; |
260 | } |
261 | return result; |
262 | } |
263 | |
264 | bool AI_Box::undoPosition (Player & player) |
265 | { |
266 | if (m_undoIndex > 1) { |
267 | m_undoIndex--; |
268 | Position * pos = m_undoList.at (m_undoIndex - 1); |
269 | restore (pos); |
270 | player = pos->player; |
271 | } |
272 | #if AILog > 4 |
273 | qDebug() << "AI_Box::undoPosition (player =" << player << "), m_undoIndex" << m_undoIndex << "UNDONE POSITION" ; |
274 | printBox(); |
275 | #endif |
276 | return (m_undoIndex > 1); |
277 | } |
278 | |
279 | bool AI_Box::redoPosition (Player & player, bool & isAI, int & index) |
280 | { |
281 | if (m_undoIndex < m_redoLimit) { |
282 | Position * pos = m_undoList.at (m_undoIndex); |
283 | restore (pos); |
284 | player = pos->player; |
285 | isAI = pos->isAI; |
286 | index = pos->index; |
287 | m_undoIndex++; |
288 | } |
289 | #if AILog > 4 |
290 | qDebug() << "AI_Box::redoPosition (player =" << player << "), m_undoIndex" << m_undoIndex << "REDONE POSITION" ; |
291 | printBox(); |
292 | #endif |
293 | return (m_undoIndex < m_redoLimit); |
294 | } |
295 | |
296 | void AI_Box::initPosition (const AI_Box * box, Player player, bool isAI) |
297 | { |
298 | if (box->side() != m_side) return; |
299 | |
300 | Position * pos = m_undoList.at (0); |
301 | m_owners = pos->owners; |
302 | m_values = pos->values; |
303 | |
304 | for (int n = 0; n < m_nCubes; n++) { |
305 | m_owners [n] = box->owner (n); |
306 | m_values [n] = box->value (n); |
307 | } |
308 | restore (pos); |
309 | pos->player = player; |
310 | pos->isAI = isAI; |
311 | // IDW TODO - Need index parameter? initPosition() is used only by AI_Main. |
312 | pos->index = 0; |
313 | m_undoIndex = 1; |
314 | m_redoLimit = m_undoIndex; |
315 | } |
316 | |
317 | void AI_Box::save (Position * pos, Player player, bool isAI) |
318 | { |
319 | // The NEXT player will face this position, after THIS player has moved. |
320 | pos->player = (player == Two) ? One : Two; |
321 | pos->isAI = isAI; |
322 | pos->nCubes = m_nCubes; |
323 | for (int n = 0; n < m_nCubes; n++) { |
324 | pos->owners [n] = m_owners [n]; |
325 | pos->values [n] = m_values [n]; |
326 | } |
327 | } |
328 | |
329 | void AI_Box::restore (Position * pos) |
330 | { |
331 | if (pos->nCubes != m_nCubes) return; |
332 | |
333 | m_owners = pos->owners; |
334 | m_values = pos->values; |
335 | |
336 | m_cubesToWin [Nobody] = m_nCubes; |
337 | m_cubesToWin [One] = m_nCubes; |
338 | m_cubesToWin [Two] = m_nCubes; |
339 | |
340 | for (int n = 0; n < m_nCubes; n++) { |
341 | m_cubesToWin [m_owners [n]]--; |
342 | } |
343 | } |
344 | |
345 | void AI_Box::discard (Position * pos) |
346 | { |
347 | delete pos->owners; |
348 | delete pos->values; |
349 | delete pos; |
350 | } |
351 | |
352 | AI_Box::Position * AI_Box::emptyPosition (int nCubes) |
353 | { |
354 | Position * pos = new Position; |
355 | pos->nCubes = nCubes; |
356 | pos->owners = new Player [nCubes]; |
357 | pos->values = new int [nCubes]; |
358 | return pos; |
359 | } |
360 | |
361 | void AI_Box::clear() |
362 | { |
363 | for (int index = 0; index < m_nCubes; index++) { |
364 | m_owners [index] = Nobody; |
365 | m_values [index] = 1; |
366 | } |
367 | m_stackPtr = -1; |
368 | |
369 | m_cubesToWin [Nobody] = 0; |
370 | m_cubesToWin [One] = m_nCubes; |
371 | m_cubesToWin [Two] = m_nCubes; |
372 | |
373 | m_undoIndex = 1; |
374 | m_redoLimit = m_undoIndex; |
375 | } |
376 | |
377 | void AI_Box::indexNeighbors() |
378 | { |
379 | int offset = 0; |
380 | for (int index = 0; index < m_nCubes; index++) { |
381 | m_maxValues [index] = 0; |
382 | for (int nb = 0; nb < 4; nb++) { |
383 | m_neighbors [offset + nb] = -1; |
384 | } |
385 | |
386 | int x = index / m_side; |
387 | int y = index % m_side; |
388 | int limit = m_side - 1; |
389 | if (y > 0) { |
390 | m_maxValues [index]++; // Has a neighbor on the North side. |
391 | m_neighbors [offset] = index - 1; |
392 | } |
393 | if (y < limit) { |
394 | m_maxValues [index]++; // Has a neighbor on the South side. |
395 | m_neighbors [offset + 1] = index + 1; |
396 | } |
397 | if (x < limit) { |
398 | m_maxValues [index]++; // Has a neighbor on the East side. |
399 | m_neighbors [offset + 2] = index + m_side; |
400 | } |
401 | if (x > 0) { |
402 | m_maxValues [index]++; // Has a neighbor on the West side. |
403 | m_neighbors [offset + 3] = index - m_side; |
404 | } |
405 | offset = offset + 4; |
406 | } |
407 | } |
408 | |
409 | #if AILog > 0 |
410 | void AI_Box::printBox() |
411 | { |
412 | // return; |
413 | // IDW test. For debugging. |
414 | for (int y = 0; y < m_side; y++) { |
415 | fprintf (stderr, " " ); |
416 | for (int x = 0; x < m_side; x++) { |
417 | int index = x * m_side + y; |
418 | if (m_owners[index] == Nobody) fprintf (stderr, " ." ); |
419 | else fprintf (stderr, " %2d" , (m_owners[index] == One) ? |
420 | m_values[index] : -m_values[index]); |
421 | } |
422 | fprintf (stderr, "\n" ); |
423 | } |
424 | /* IDW test. |
425 | fprintf (stderr, " %2d %2d %2d to win, pointers %lu %lu\n", |
426 | m_cubesToWin [Nobody], m_cubesToWin [One], m_cubesToWin [Two], |
427 | (long) m_owners, (long) m_values); |
428 | fprintf (stderr, "\n"); |
429 | */ |
430 | } |
431 | #endif |
432 | |
433 | #include "ai_box.moc" |
434 | |