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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
|
#include <iostream>
#include <cstring>
#include <cassert>
#include <climits>
#include "ai_mm2.h"
#include "util.h"
using namespace std;
#define SCORE_WIN 10000
#define SCORE_LOSE (-10000)
#define SCORE_TIE 0
#define INF (1e34)
#define MAXDEPTH 3
static int scoreTable[ipow(3, RLEN)];
__attribute__((constructor))
static void initScoreTable() {
int len = sizeof(scoreTable) / sizeof(scoreTable[0]);
uint8_t values[RLEN];
memset(values, 0, RLEN);
for (int i = 0; i < len; i++) {
int numempty = 0;
uint8_t clr = 0;
for (int j = 0; j < RLEN; j++) {
if (values[j] == 0) numempty++;
else if (clr == 0) clr = values[j];
else if (clr != values[j]) {scoreTable[i] = 0; goto nope;}
}
if (numempty == RLEN) {
scoreTable[i] = 0;
} else {
scoreTable[i] = (3 - 2 * clr) * (1 << (RLEN - 1 - numempty));
}
nope:
for (int j = 0; j < RLEN; j++) {
values[j]++;
if (values[j] == 3) values[j] = 0;
else break;
}
}
}
static int evaluate(Board &bd, uint8_t myclr) {
Bounds bounds = bd.computeBounds();
int score = 0;
#define CHECK(_ident, _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; \
int scidx = 0; \
for (int i = 1; i <= RLEN; i++, idx += BSZ * (_dy) + (_dx)) { \
scidx *= 3; \
scidx += bd[idx]; \
} \
score += scoreTable[scidx]; \
} \
} \
} while (0)
CHECK(1, bounds.left , bounds.right - (RLEN-1), bounds.top, bounds.bottom , 1, 0);
CHECK(2, bounds.left , bounds.right - (RLEN-1), bounds.top, bounds.bottom - (RLEN-1), 1, 1);
CHECK(3, bounds.left , bounds.right , bounds.top, bounds.bottom - (RLEN-1), 0, 1);
CHECK(4, 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 MM2::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;
}
|
