1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
|
#include <climits>
#include <cassert>
#include "ai_mm.h"
static const int mm_depth = 4;
// 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, int win);
static int minimaxWhite(const Board &bd, int depth, int alpha, int beta, int win) {
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;
int win = bd2.applyCW(mv);
int value = minimaxBlack(bd2, depth - 1, alpha, beta, win);
// 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) {
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;
int win = bd2.applyCW(mv);
int value = minimaxWhite(bd2, depth - 1, alpha, beta, win);
// 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 win, int player) {
if (player == 1) return minimaxWhite(bd, depth, alpha, beta, win);
else return minimaxBlack(bd, depth, alpha, beta, win);
}
Move AI::MM::findMove(const Board &bd, int player) {
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;
int win = bd2.applyCW(mv);
int score = player * minimaxGeneric(bd2, mm_depth, INT_MIN, INT_MAX, win, -player);
// cerr << "fM: " << mv << ": " << score << endl;
cerr << score << ',';
if (score > bestScore) {
bestScore = score;
bestMove = mv;
}
return false;
});
cerr << ']' << endl;
return bestMove;
}
|
