diff options
Diffstat (limited to 'ai_mm.cpp')
-rw-r--r-- | ai_mm.cpp | 115 |
1 files changed, 115 insertions, 0 deletions
diff --git a/ai_mm.cpp b/ai_mm.cpp new file mode 100644 index 0000000..8d61e20 --- /dev/null +++ b/ai_mm.cpp @@ -0,0 +1,115 @@ +#include <climits> +#include <cassert> +#include "ai_mm.h" + + +static const int mm_depth = 3; + + +// Positive scores for white +static int evaluate(const Board &bd, int win) { + const int large = 10000; + + int score = -large; // to counteract the +=large for KING + score += 8; // to counteract the imbalance in white/black stones + + for (int i = 0; i < N * N; i++) { + switch (bd.cells[i]) { + case EMPTY: break; + case WHITE: score += 1; break; + case KING: score += large; break; + case BLACK: score -= 1; break; + } + } + + if (win == 1) score += large; + + return score; +} + +static int minimaxBlack(const Board &bd, int depth, int alpha, int beta); + +static int minimaxWhite(const Board &bd, int depth, int alpha, int beta) { + int win = bd.checkWin(); + if (depth == 0 || win != 0) { + return evaluate(bd, win); + } + + int bestValue = INT_MIN; + + bd.forEachMove(1, [&bd, depth, &alpha, &beta, &bestValue](Move mv) { + Board bd2 = bd; + bd2.apply(mv); + int value = minimaxBlack(bd2, depth - 1, alpha, beta); + // cerr << string(6 - 2 * depth, ' ') << "mmW: " << mv << ": " << value << endl; + bestValue = max(bestValue, value); + alpha = max(alpha, bestValue); + if (beta <= alpha) return true; + return false; + }); + + return bestValue; +} + +static int minimaxBlack(const Board &bd, int depth, int alpha, int beta) { + int win = bd.checkWin(); + if (depth == 0 || win != 0) { + return evaluate(bd, win); + } + + int bestValue = INT_MAX; + + bd.forEachMove(-1, [&bd, depth, &alpha, &beta, &bestValue](Move mv) { + Board bd2 = bd; + bd2.apply(mv); + int value = minimaxWhite(bd2, depth - 1, alpha, beta); + // cerr << string(6 - 2 * depth, ' ') << "mmB: " << mv << ": " << value << endl; + bestValue = min(bestValue, value); + beta = min(beta, bestValue); + if (beta <= alpha) return true; + return false; + }); + + return bestValue; +} + +static int minimaxGeneric(const Board &bd, int depth, int alpha, int beta, int player) { + if (player == 1) return minimaxWhite(bd, depth, alpha, beta); + else return minimaxBlack(bd, depth, alpha, beta); +} + +Move AI::MM::findMove(const Board &bd, int player) { + /* { + int pl = player; + Board bd2 = bd; + Move mv; + mv = Move(3, 30); assert(bd2.isValid(mv, pl)); bd2.apply(mv); pl = -pl; + mv = Move(22, 21); assert(bd2.isValid(mv, pl)); bd2.apply(mv); pl = -pl; + cerr << bd2 << endl; + // mv = Move(77, 80); assert(bd2.isValid(mv, pl)); bd2.apply(mv); pl = -pl; + cerr << "## " << evaluate(bd2, 0) << endl; + } */ + + Move bestMove(-1, -1); + int bestScore = INT_MIN; + // 'bestScore', and 'score' below, have positive values good for 'player'. + + // cerr << "MM::findMove(player=" << player << "):" << endl; + cerr << '['; + + bd.forEachMove(player, [&bd, player, &bestScore, &bestMove](Move mv) { + Board bd2 = bd; + bd2.apply(mv); + int score = player * minimaxGeneric(bd2, mm_depth, INT_MIN, INT_MAX, -player); + // cerr << "fM: " << mv << ": " << score << endl; + cerr << score << ','; + if (score > bestScore) { + bestScore = score; + bestMove = mv; + } + }); + + cerr << ']' << endl; + + return bestMove; +} |