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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
|
#include <iostream>
#include <cassert>
#include <climits>
#include "ai_mm.h"
#include "util.h"
using namespace std;
#define SCORE_WIN 10000
#define SCORE_LOSE (-10000)
#define SCORE_TIE 0
#define INF (1e34)
#define MAXDEPTH 4
static int evaluate(Board &bd, uint8_t myclr) {
Bounds bounds = bd.computeBounds();
int score = 0;
#define CHECK(_xlim1, _xlim2, _ylim1, _ylim2, _dx, _dy) \
do { \
for (int y = (_ylim1); y <= (_ylim2); y++) { \
for (int x = (_xlim1); x <= (_xlim2); x++) { \
int idx = BSZ * y + x; \
uint8_t clr = bd[idx]; \
if (clr == 0) continue; \
for (int i = 1; i <= RLEN; i++, idx += BSZ * (_dy) + (_dx)) { \
if (bd[idx] != clr) break; \
score += i * (3 - 2 * clr); \
} \
} \
} \
} while (0)
CHECK(bounds.left , bounds.right - (RLEN-1), bounds.top, bounds.bottom , 1, 0);
CHECK(bounds.left , bounds.right - (RLEN-1), bounds.top, bounds.bottom - (RLEN-1), 1, 1);
CHECK(bounds.left , bounds.right , bounds.top, bounds.bottom - (RLEN-1), 0, 1);
CHECK(bounds.left + (RLEN-1), bounds.right , bounds.top, bounds.bottom - (RLEN-1), -1, 1);
#undef CHECK
if (myclr != 1) score = -score;
return score;
}
static float chanceNode(
Board &bd, uint8_t myclr, int idx, uint8_t onturn,
int depth, float alpha, float beta);
static float playNode(
Board &bd, uint8_t myclr, uint8_t onturn,
int depth, float alpha, float beta) {
if (depth == 0 || bd.bag.totalLeft() == 0) {
return evaluate(bd, myclr);
}
float value;
vector<int> edgeCells = bd.getEdgeCells();
if (onturn == myclr) {
value = -INF;
for (int idx : edgeCells) {
value = max(value, chanceNode(bd, myclr, idx, onturn, depth, alpha, beta));
alpha = max(alpha, value);
if (alpha >= beta) break;
}
} else {
value = +INF;
for (int idx : edgeCells) {
value = min(value, chanceNode(bd, myclr, idx, onturn, depth, alpha, beta));
beta = min(beta, value);
if (alpha >= beta) break;
}
}
return value;
}
static float chanceNode(
Board &bd, uint8_t myclr, int idx, uint8_t onturn,
int depth, float alpha, float beta) {
const float totalLeftF = bd.bag.totalLeft();
float score = 0;
for (uint8_t clr = 1; clr <= NC; clr++) {
int numLeft = bd.bag.numLeft(clr);
if (numLeft == 0) continue;
float probability = numLeft / totalLeftF;
bd.bag.drawColour(clr);
uint8_t win = bd.putCW(idx, clr);
if (win != 0) {
score += probability * (win == myclr ? SCORE_WIN : SCORE_LOSE);
} else {
score += probability * playNode(bd, myclr, NEXTTURN(onturn), depth - 1, alpha, beta);
}
bd.bag.replace(clr);
bd.undo(idx);
}
return score;
}
int MM::calcMove(Board &bd, uint8_t myclr) {
assert(bd.bag.totalLeft() > 0);
// The usage of a single score variable instead of an array works only if
// there are only two players.
static_assert(NC == 2, "MM only works with 2 players");
float maxscore = INT_MIN;
int maxat = -1;
vector<int> edgeCells = bd.getEdgeCells();
for (int idx : edgeCells) {
float score = chanceNode(bd, myclr, idx, myclr, MAXDEPTH, -INF, +INF);
if (score > maxscore) {
maxscore = score;
maxat = idx;
}
}
return maxat;
}
|
