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
25AI_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
34AI_Box::~AI_Box()
35{
36 destroyBox();
37}
38
39void 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
58void 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
68void AI_Box::resizeBox (int side)
69{
70 destroyBox();
71 createBox (side);
72}
73
74
75// ----------------------------------------------------------------
76// Moves
77
78
79bool 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
208void 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
226void 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
253bool 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
264bool 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
279bool 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
296void 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
317void 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
329void 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
345void AI_Box::discard (Position * pos)
346{
347 delete pos->owners;
348 delete pos->values;
349 delete pos;
350}
351
352AI_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
361void 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
377void 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
410void 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