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
22#include "ai_main.h"
23#include "ai_kepler.h"
24#include "ai_newton.h"
25#include "ai_box.h"
26
27#include <QApplication>
28
29#include <QDebug>
30#include <QTime>
31
32#include "prefs.h"
33
34// Use a thread and return the move via a signal.
35class ThreadedAI : public QThread
36{
37 Q_OBJECT
38public:
39 ThreadedAI (AI_Main * ai)
40 : m_ai (ai)
41 { }
42
43 virtual void run() {
44 int index = m_ai->computeMove();
45 emit done (index);
46 }
47/* IDW test. TODO - This is not actually used. Is it needed?
48 * I think AI_Main::stop() sets m_stopped atomically and even
49 * if it does not, the thread will see it next time around. And
50 * the thread is read-only with respect to m_stopped ...
51 *
52 * ATM, KCubeBoxWidget calls AI_Main::stop() not this stop()
53 * and it works ...
54 *
55 * IDW test. TODO - See AI_Main::stop(). It works, but does it need a QMutex?
56 *
57 void stop() {
58 qDebug() << "STOP THREAD REQUESTED";
59 { QMutexLocker lock (&m_ai->endMutex); m_ai->stop(); }
60 wait();
61 qDebug() << "STOP THREAD DONE";
62 }
63*/
64signals:
65 void done (int index);
66
67private:
68 AI_Main * m_ai;
69};
70
71const char * text[] = {"TakeOrBeTaken", "EqualOpponent", "CanTake",
72 "OccupyCorner", "OccupyEdge", "OccupyCenter",
73 "CanConsolidate", "CanReachMaximum", "CanExpand",
74 "IncreaseEdge", "IncreaseCenter", "PlayHereAnyway"};
75
76void test (int array[4]) {
77 for (int n = 0; n < 4; n++) {
78 printf ("nb %d %d: ", n, array[n]);
79 }
80 printf ("\n");
81}
82
83void makeRandomSequence (int nMax, int * seq, KRandomSequence & random)
84{
85 // Helper routine. Sets up a random sequence of integers 0 to (nMax - 1).
86 for (int n = 0; n < nMax; n++) {
87 seq[n] = n;
88 }
89
90 int last = nMax;
91 int z, temp;
92 for (int n = 0; n < nMax; n++) {
93 z = random.getLong (last);
94 last--;
95 temp = seq[z];
96 seq[z] = seq[last];
97 seq[last] = temp;
98 }
99 return;
100 for (int n = 0; n < nMax; n++) {
101 fprintf (stderr, " %d", seq[n]);
102 }
103 fprintf (stderr, "\n");
104}
105
106AI_Main::AI_Main (QObject * parent, int side) : AI_Box (parent, side)
107{
108 qDebug() << "AI_Main CONSTRUCTOR";
109 m_thread = new ThreadedAI (this);
110 m_randomSeq = new int [m_nCubes];
111#if AILog > 0
112 startStats();
113#endif
114
115 m_AI_Kepler = new AI_Kepler();
116 m_AI_Newton = new AI_Newton();
117
118 setSkill (Prefs::EnumSkill1::Beginner, true, false,
119 Prefs::EnumSkill2::Beginner, true, false);
120
121 m_stopped = false;
122 m_currentLevel = 0;
123
124 m_random.setSeed (0);
125
126 connect (m_thread, SIGNAL(done(int)), this, SIGNAL(done(int)));
127}
128
129AI_Main::~AI_Main()
130{
131 delete m_AI_Kepler;
132 delete m_AI_Newton;
133 delete m_thread;
134}
135
136void AI_Main::setSkill (int skill1, bool kepler1, bool newton1,
137 int skill2, bool kepler2, bool newton2)
138{
139 m_ai[0] = 0;
140 m_ai[1] = kepler1 ? m_AI_Kepler : m_AI_Newton;
141 m_ai[2] = kepler2 ? m_AI_Kepler : m_AI_Newton;
142
143 m_ai_skill[0] = 0;
144 m_ai_skill[1] = skill1;
145 m_ai_skill[2] = skill2;
146
147 m_ai_maxLevel[0] = 0;
148 m_ai_maxLevel[1] = depths[skill1];
149 m_ai_maxLevel[2] = depths[skill2];
150
151 for (int player = 1; player <= 2; player++) {
152 qDebug() << "AI_Main::setSkill: Player" << player << m_ai[player]->whoami()
153 << "skill" << m_ai_skill[player]
154 << "maxLevel" << m_ai_maxLevel[player];
155 }
156}
157
158void AI_Main::stop()
159{
160 m_stopped = true;
161 m_thread->wait();
162}
163
164void AI_Main::getMove (const Player player, const AI_Box * box)
165{
166#if AILog > 1
167 qDebug() << "\nEntering AI_Main::getMove() for player" << player;
168#endif
169 // These settings are immutable once the thread starts and getMove() returns.
170 // If AI_Main::setSkill() is called when the thread is active, the new values
171 // will not take effect until the next move or hint.
172 m_currentAI = m_ai[player];
173 m_skill = m_ai_skill[player];
174 m_maxLevel = m_ai_maxLevel[player];
175
176#if AILog > 0
177 initStats (player); // IDW test. Statistics collection.
178#endif
179#if AILog > 1
180 qDebug() << tag(0) << "PLAYER" << player << m_currentAI->whoami() << "skill" << m_skill << "max level" << m_maxLevel;
181#endif
182
183 m_stopped = false;
184 m_player = player;
185
186 checkWorkspace (box->side());
187 initPosition (box, player, true);
188
189#if AILog > 1
190 qDebug() << "INITIAL POSITION";
191 printBox();
192#endif
193
194 m_thread->start (QThread::IdlePriority); // Run computeMove() on thread.
195 return;
196}
197
198int AI_Main::computeMove()
199{
200 // IDW test. // Set up a random sequence of integers 0 to (m_nCubes - 1).
201 // IDW test. makeRandomSequence (m_side * m_side, m_randomSeq, m_random);
202
203 // Start the recursive MiniMax algorithm on a copy of the current cube box.
204#if AILog > 2
205 qDebug() << tag(0) << "Calling tryMoves(), level zero, player" << m_player;
206#endif
207
208 Move move = tryMoves (m_player, 0);
209
210#if AILog > 2
211 qDebug() << tag(0) << "Returned from tryMoves(), level zero, player"
212 << m_player << "value" << move.val
213 << "simulate" << n_simulate << "assess" << n_assess;
214#endif
215
216#if AILog > 0
217 saveStats (move); // IDW test. Statistics collection.
218#endif
219
220#if AILog > 1
221 qDebug() << "==============================================================";
222 qDebug() << tag(0) << "MOVE" << m_currentMoveNo << "for PLAYER" << m_player
223 << "X" << move.index/m_side << "Y" << move.index%m_side;
224#endif
225
226 return (move.index); // Return the best move found, via a signal.
227}
228
229Move AI_Main::tryMoves (Player player, int level)
230{
231 m_currentLevel = level; // IDW test. To limit qDebug() in findCubesToMove().
232 long maxValue = -WinnerPlus1;
233
234 Move bestMove = {-1, -WinnerPlus1};
235
236 // Find likely cubes to move.
237 Move * cubesToMove = new Move [m_nCubes];
238#if AILog > 3
239 qDebug() << "FIND CUBES TO MOVE for Player" << player
240 << "from POSITION AT LEVEL" << level;
241 if (level > 0) boxPrint (m_side, (int *) m_owners, m_values); // IDW test.
242#endif
243 int moves = findCubesToMove (cubesToMove, player,
244 m_owners, m_values, m_maxValues);
245
246#if AILog > 2
247 qDebug() << tag(level) << "Level" << level << "Player" << player
248 << "number of likely moves" << moves;
249 if (level == 0) {
250 for (int n = 0; n < moves; n++) {
251 int v = cubesToMove[n].val;
252 QString s = "";
253 if ((v > 0) && (v <= 12)) s = QString(text[v-1]);
254 qDebug() << tag(level) << " " << "X" << cubesToMove[n].index/m_side
255 << "Y" << cubesToMove[n].index%m_side
256 << "val" << cubesToMove[n].val << s;
257 }
258 saveLikelyMoves (moves, cubesToMove); // IDW test.
259 }
260
261 m_currentMove->searchStats->at(level)->n_moves += moves;
262#endif
263
264 // IDW TODO - Sort the moves by priority in findCubesToMove() (1 first),
265 // shuffle moves that have the same value (to avoid repetitious openings).
266 // IDW TODO - Apply alpha-beta pruning to the sorted moves. Maybe we can
267 // allow low-priority moves and sacrifices ...
268
269 for (int n = 0; n < moves; n++) {
270#if AILog > 2
271 if (level == 0) qDebug()
272 << "==============================================================";
273 qDebug() << tag(level) << "TRY" << (n+1) << "at level" << level
274 << "Player" << player
275 << "X"<< cubesToMove[n].index/m_side
276 << "Y" << cubesToMove[n].index%m_side
277 << "val" << cubesToMove[n].val;
278#endif
279
280 MoveUndodata undodata;
281 bool won = doMove (player, cubesToMove[n].index, &undodata);
282
283#if AILog > 2
284 n_simulate++;
285#endif
286
287 long val;
288 if (won) {
289 // Accept a winning move.
290 bestMove = cubesToMove[n];
291 bestMove.val = WinnerPlus1 - 1;
292#if AILog > 2
293 n_assess++;
294#endif
295 cubesToMove[n].val = bestMove.val; // IDW test. For debug output.
296#if AILog > 2
297 qDebug() << tag(level) << "Player" << player
298 << "wins at level" << level
299 << "move" << cubesToMove[n].index/m_side
300 << cubesToMove[n].index%m_side;
301#endif
302 undoMove(&undodata);
303 break;
304 }
305 else if (level >= m_maxLevel) {
306 // Stop the recursion.
307 val = m_currentAI->assessPosition (player, m_nCubes,
308 m_owners, m_values);
309#if AILog > 2
310 n_assess++;
311#endif
312 cubesToMove[n].val = val; // IDW test. For debug output.
313#if AILog > 3
314 qDebug() << tag(level) << "END RECURSION: Player" << player
315 << "X" << cubesToMove[n].index/m_side
316 << "Y" << cubesToMove[n].index%m_side
317 << "assessment" << val << "on POSITION";
318 boxPrint (m_side, (int *)(m_owners), m_values);// IDW test.
319#endif
320 }
321 else {
322 // Switch players.
323 Player opponent = (player == One) ? Two : One;
324
325 // Do the MiniMax calculation for the next recursion level.
326/* qDebug() << tag(level) << "CALL tryMoves: Player" << opponent
327 << "level" << level+1; */
328 Move move = tryMoves (opponent, level + 1);
329 val = move.val;
330 cubesToMove[n].val = val; // IDW test. For debug output.
331/* qDebug() << tag(level) << "RETURN to level" << level
332 << "Player" << player << "X" << move.index/m_side
333 << "Y" << move.index%m_side << "assessment" << val; */
334 }
335
336 if (val > maxValue) {
337 maxValue = val;
338 bestMove = cubesToMove[n];
339 bestMove.val = val;
340 cubesToMove[n].val = val; // IDW test. For debug output.
341#if AILog > 2
342 qDebug() << tag(level) << "NEW MAXIMUM at level" << level
343 << "Player" << player << "X" << bestMove.index/m_side
344 << "Y" << bestMove.index%m_side << "assessment" << val;
345#endif
346 }
347 Player p = player;
348 undoMove(&undodata);
349 if (p != player) qDebug() << "ERROR: PLAYER CHANGED: from" << p <<
350 "to" << player;
351 if (m_stopped) {
352 qDebug() << "STOPPED AT LEVEL" << level;
353 break;
354 }
355 }
356
357#if AILog > 2
358 if (level == 0) {
359 qDebug() << tag(level) << "VALUES OF MOVES - Player" << player
360 << "number of moves" << moves;
361 for (int n = 0; n < moves; n++) {
362 qDebug() << tag(level) << " " << "X" << cubesToMove[n].index/m_side
363 << "Y" << cubesToMove[n].index%m_side
364 << "val" << cubesToMove[n].val;
365 }
366 }
367#endif
368
369 delete [] cubesToMove;
370
371#if AILog > 2
372 qDebug();
373 qDebug() << tag(level) << "BEST MOVE at level" << level << "Player" << player
374 << "X" << bestMove.index/m_side << "Y" << bestMove.index%m_side
375 << "assessment" << bestMove.val;
376#endif
377
378 // Apply the MiniMax rule.
379 if (level > 0) {
380#if AILog > 2
381 qDebug() << tag(level) << "CHANGE SIGN" << bestMove.val
382 << "to" << -bestMove.val;
383#endif
384 bestMove.val = - bestMove.val;
385 }
386
387 return bestMove;
388}
389
390int AI_Main::findCubesToMove (Move * c2m, const Player player,
391 const Player * owners, const int * values,
392 const int * maxValues)
393{
394 int index, n;
395 int opponent = (player == One) ? Two : One;
396 int moves = 0;
397 int min = VeryHighValue;
398 bool beginner = (m_skill == Prefs::EnumSkill1::Beginner);
399 int secondMin = min;
400
401 // Set up a random sequence of integers 0 to (m_nCubes - 1).
402 makeRandomSequence (m_nCubes, m_randomSeq, m_random);
403
404 // Put values on the cubes.
405 int * neighbors = m_neighbors;
406 int val;
407 for (n = 0; n < m_nCubes; n++) {
408 index = m_randomSeq [n];
409
410 // Use only cubes that do not belong to the opponent.
411 if (owners[index] == opponent) {
412 continue;
413 }
414
415 // The beginner selects the cubes with the most pips on them:
416 // other players check the neighbours of each cube.
417 val = beginner ? (5 - values [index]) :
418 m_currentAI->assessCube (index, player,
419 (neighbors + 4 * index),
420 owners, values, maxValues);
421 if (val < min) {
422 secondMin = min;
423 min = val;
424 }
425 else if ((val > min) && (val < secondMin)) {
426 secondMin = val;
427 }
428
429 // Store the move.
430 c2m[moves].index = index;
431 c2m[moves].val = val;
432 moves++;
433 }
434#if AILog > 2
435 if (m_currentLevel == 0) qDebug() << "\nMinimum is" << min
436 << ", second minimum is" << secondMin << "available moves" << moves;
437#endif
438
439 if (moves == 0) {
440 // Should not happen? Even bad moves are given a value > 0.
441 qDebug() << "NO LIKELY MOVES AVAILABLE: selecting" << moves
442 << "min" << min;
443 return moves;
444 }
445
446 int counter = 0;
447 // Find all moves with minimum assessment
448 for (n = 0; n < moves; n++) {
449 if (c2m[n].val == min) {
450 c2m[counter].index = c2m[n].index;
451 c2m[counter].val = c2m[n].val;
452 counter++;
453 }
454 }
455
456 // IDW TODO - Finalise the logic for limiting the number of moves tried.
457 // The 1/3 gizmo is to limit searches on an empty cube box.
458 // Should not use secondMin on Expert level?
459 // Should not use secondMin on deeper recursion levels?
460 // Should it all depend on how many moves are at "min"?
461 // Should AI_Newton have overlapping values of move types?
462
463 // if (true || m_skill == Prefs::EnumSkill1::Average) // IDW test.
464 // if ((counter <= 2) || (m_skill == Prefs::EnumSkill1::Average))
465 // if ((m_skill == Prefs::EnumSkill1::Average) &&
466 if (m_currentMoveNo > (m_nCubes / 3)) { // If board > 1/3 full.
467 for (n = 0; n < moves; n++) {
468 if (c2m[n].val == secondMin) {
469 c2m[counter].index = c2m[n].index;
470 c2m[counter].val = c2m[n].val;
471 counter++;
472 }
473 }
474 }
475
476 if (counter != 0) {
477 moves = counter;
478 }
479
480 // IDW TODO - Can we find a more subtle rule?
481
482 // If more than maxMoves moves are favorable, take maxMoves random
483 // moves because it will take too long to check more.
484 return qMin (moves, maxBreadth);
485}
486
487void AI_Main::checkWorkspace (int side)
488{
489 if (m_side != side) {
490 qDebug() << "NEW AI_Box SIZE NEEDED: was" << m_side << "now" << side;
491 delete m_randomSeq;
492 resizeBox (side);
493 m_randomSeq = new int [side * side];
494 }
495}
496
497#if AILog > 0
498/*
499 * Debugging methods for the AI.
500 */
501void AI_Main::boxPrint (int side, int * owners, int * values)
502{
503 // Print out a position reached during or after recursion.
504 // fprintf (stderr, "AI_Main::boxPrint (%d, %lu, %lu)\n",
505 // side, (long) owners, (long) values); // Tests push and pop logic.
506 for (int y = 0; y < side; y++) {
507 fprintf (stderr, " ");
508 for (int x = 0; x < side; x++) {
509 int index = x * side + y;
510 if (owners[index] == Nobody) fprintf (stderr, " .");
511 else fprintf (stderr, " %2d", (owners[index] == One) ?
512 values[index] : -values[index]);
513 }
514 fprintf (stderr, "\n");
515 }
516}
517
518void AI_Main::startStats()
519{
520 // IDW test. For debugging.
521 m_currentMoveNo = 0;
522 m_moveStats.clear();
523}
524
525void AI_Main::postMove (Player player, int index, int side)
526{
527 // IDW test. Statistics collection.
528 // Used to record a move by a human player.
529 checkWorkspace (side);
530
531 int x = index / m_side;
532 int y = index % m_side;
533#if AILog > 1
534 qDebug() << "AI_Main::postMove(): index" << index << "at" << x << y << "m_side" << m_side;
535#endif
536 m_maxLevel = m_ai_maxLevel[player];
537 m_currentMove = new MoveStats [1];
538
539 m_currentMoveNo++;
540 m_currentMove->player = player;
541 m_currentMove->moveNo = m_currentMoveNo;
542 m_currentMove->n_simulate = 0;
543 m_currentMove->n_assess = 0;
544 m_currentMove->nLikelyMoves = 0;
545 m_currentMove->likelyMoves = 0;
546 m_currentMove->searchStats = new QList<SearchStats *>();
547
548 m_currentMove->x = x;
549 m_currentMove->y = y;
550 m_currentMove->value = 0;
551 m_moveStats.append (m_currentMove);
552#if AILog > 1
553 qDebug() << "==============================================================";
554 qDebug() << tag(0) << "MOVE" << m_currentMoveNo << "for PLAYER" << player
555 << "X" << x << "Y" << y;
556 qDebug() << "==============================================================";
557#endif
558}
559
560void AI_Main::initStats (int player)
561{
562 // IDW test. For debugging.
563 m_currentMove = new MoveStats [1];
564
565 m_currentMoveNo++;
566 m_currentMove->player = (Player) player;
567 m_currentMove->moveNo = m_currentMoveNo;
568 m_currentMove->n_simulate = 0;
569 m_currentMove->n_assess = 0;
570 m_currentMove->nLikelyMoves = 0;
571 m_currentMove->likelyMoves = 0;
572 m_currentMove->searchStats = new QList<SearchStats *>();
573
574 for (int n = 0; n <= m_maxLevel; n++) {
575 SearchStats * s = new SearchStats [1];
576 s->n_moves = 0;
577 m_currentMove->searchStats->append (s);
578 }
579
580 n_simulate = 0;
581 n_assess = 0;
582}
583
584void AI_Main::saveLikelyMoves (int nMoves, Move * moves)
585{
586 Move * m = new Move [nMoves];
587 m_currentMove->nLikelyMoves = nMoves;
588 m_currentMove->likelyMoves = m;
589 for (int n = 0; n < nMoves; n++) {
590 m [n] = moves [n];
591 }
592}
593
594void AI_Main::saveStats (Move & move)
595{
596 // IDW test. For debugging.
597 m_currentMove->x = move.index/m_side;
598 m_currentMove->y = move.index%m_side;
599 m_currentMove->value = move.val;
600 m_currentMove->n_simulate = n_simulate;
601 m_currentMove->n_assess = n_assess;
602 m_moveStats.append (m_currentMove);
603}
604
605void AI_Main::dumpStats()
606{
607 // IDW test. For debugging. Replay all the moves, with statistics for each.
608 qDebug() << m_moveStats.count() << "MOVES IN THIS GAME";
609 AI_Box * statsBox = new AI_Box (0, m_side);
610 statsBox->printBox();
611 foreach (MoveStats * m, m_moveStats) {
612 QList<int> l;
613 int nMax = m->searchStats->count();
614 for (int n = 0; n < nMax; n++) {
615 l.append (m->searchStats->at(n)->n_moves);
616 }
617 qDebug() << ((m->player == 1) ? "p1" : "p2") << "move" << m->moveNo
618 << "X" << m->x << "Y" << m->y
619 << "value" << m->value << m->n_simulate << m->n_assess << l;
620
621 if (m->nLikelyMoves > 0) {
622 qDebug() << " Number of likely moves" << m->nLikelyMoves;
623 for (int n = 0; n < m->nLikelyMoves; n++) {
624 int v = m->likelyMoves[n].val;
625 QString s = "";
626 if ((v > 0) && (v <= 12)) s = QString(text[v-1]);
627 qDebug() << " " << "X" << m->likelyMoves[n].index/m_side
628 << "Y" << m->likelyMoves[n].index%m_side
629 << "val" << m->likelyMoves[n].val << s;
630 }
631 delete m->likelyMoves;
632 }
633 bool won = statsBox->doMove (m->player, m->x * m_side + m->y);
634 statsBox->printBox();
635 qDeleteAll (*(m->searchStats));
636 delete m;
637 }
638 m_moveStats.clear();
639 delete statsBox;
640}
641
642QString AI_Main::tag (int level)
643{
644 QString indent ("");
645 indent.fill ('-', 2 * level);
646 indent = indent.prepend (QString::number (level));
647 indent = indent.leftJustified (2 * m_maxLevel + 1);
648 QString mv = QString::number(m_currentMoveNo).rightJustified(3, '0');
649 return (QString ("%1 %2 %3")).arg(m_currentMove->player).arg(mv).arg(indent);
650}
651#endif
652
653/**
654 * This is the default definition of virtual long AI_Base::assessPosition().
655 * Inheritors of AI_Base can declare and define other versions.
656 */
657long AI_Base::assessPosition (const Player player, const int nCubes,
658 const Player owners[], const int values[]) const
659{
660 int cubesOne = 0;
661 int cubesTwo = 0;
662 int pointsOne = 0;
663 int pointsTwo = 0;
664 Player otherPlayer = (player == One) ? Two : One;
665 int index, points;
666
667 for (index = 0; index < nCubes; index++) {
668 points = values[index];
669 if (owners[index] == One) {
670 cubesOne++;
671 pointsOne += points * points;
672 }
673 else if (owners[index] == Two) {
674 cubesTwo++;
675 pointsTwo += points * points;
676 }
677 }
678
679 if (player == One) {
680 return cubesOne * cubesOne + pointsOne - cubesTwo * cubesTwo - pointsTwo;
681 }
682 else {
683 return cubesTwo * cubesTwo + pointsTwo - cubesOne * cubesOne - pointsOne;
684 }
685}
686
687#include "ai_main.moc"
688#include "moc_ai_main.cpp"
689