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
|
#include <climits>
#include "ai_mc.h"
static const int mc_ngames = 500;
static int playout(Board &bd, int player) {
Move poss[N * N * N];
while (true) {
int nposs = 0;
int winidx = -1;
bd.forEachMove(player, [&bd, &poss, &nposs, &winidx, player](Move mv) {
Board bd2 = bd;
int win = bd2.applyCW(mv);
if (win * player >= 0) {
poss[nposs++] = mv;
if (win != 0) {
winidx = nposs - 1;
return true;
}
}
return false;
});
if (nposs == 0) return -player;
int index = winidx == -1 ? rand() % nposs : winidx;
int win = bd.applyCW(poss[index]);
if (win != 0) return win;
player = -player;
}
}
Move AI::MC::findMove(const Board &bd, int player) {
// 'maxscore' and 'score' below have high values for 'player'.
int maxscore = INT_MIN;
Move maxmove = Move(-1, -1);
cerr << '[';
bd.forEachMove(player, [&bd, &maxscore, &maxmove, player](Move mv) {
int score = 0;
Board bd2 = bd;
int win = bd2.applyCW(mv);
if (win == player) {
maxscore = INT_MAX;
maxmove = mv;
cerr << "Found winning move!";
return true;
} else if (win == -player) {
return false;
}
for (int i = 0; i < mc_ngames; i++) {
Board bd3 = bd;
bd3.apply(mv);
score += playout(bd3, -player);
}
score *= player; // fix sign
cerr << score << ',';
if (score > maxscore) {
maxscore = score;
maxmove = mv;
}
return false;
});
cerr << ']' << endl;
cerr << "Chose move with score " << maxscore << endl;
return maxmove;
}
|
