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
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
|
#include "ct1986.h"
// ===================================================================
// Globals
// ===================================================================
char ct1986_ptn[9];
void (*ct1986_display_progress)(const uint8_t);
// ===================================================================
// Implementation of a small convolutional neural network
// ===================================================================
static float flattened[CONV_NUM+2];
static float dense1[DENSE1_NUM];
static float dense2[DENSE2_NUM];
#define RELU(x) ((x) = ((x)<0)?0:(x))
float
ct1986_evaluate_black_win(void) {
/* ------------------ *
* Convolution layer *
* ------------------ */
// for each kernel
for (uint8_t kern = 0; kern < KERN_NUM; kern++) {
// the stride is 1, march across the board
for (uint8_t bx = 0; bx < KERN_OSIZE; bx++) {
for (uint8_t by = 0; by < KERN_OSIZE; by++) {
flattened[kern+KERN_NUM*(bx+by*KERN_OSIZE)] =
conv2d_biases[kern];
// Compute the convolution for this position
for (uint8_t ky = 0; ky < KERN_SIZE; ky++) {
for (uint8_t kx = 0; kx < KERN_SIZE; kx++) {
for (uint8_t c = 0; c < KERN_CHAN; c++) {
// Where we are on the board
const uint8_t loc = kx+by+(ky+bx)*board_size;
// Look up what's on the board at this location, and
// multiply it. For c=0 we have to do some extra work
float lookup = 0;
if (COUNT_AT(loc)>c) {
if (c==0) {
if (STONE_AT(loc) == STONE_STANDING) {
lookup = (colours[loc] & 1) ? +0.25 : -0.25;
} else if (STONE_AT(loc) == STONE_CAPSTONE) {
lookup = (colours[loc] & 1) ? +1.00 : -1.00;
} else {
lookup = (colours[loc] & 1) ? +0.50 : -0.50;
}
} else {
lookup = (colours[loc] & (1<<c)) ? +0.50 : -0.50;
}
}
flattened[kern+KERN_NUM*(bx+by*KERN_OSIZE)]
+= lookup*conv2d_weights[kern][ky][kx][c];
}
}
}
RELU(flattened[kern+KERN_NUM*(bx+by*KERN_OSIZE)]);
}
}
}
// Add input of flat counts
flattened[CONV_NUM] = (float)(white_count & 127)/21.0;
flattened[CONV_NUM+1] = (float)(black_count & 127)/21.0;
/* ------------------ *
* First dense layer *
* ------------------ */
for (uint8_t d1 = 0; d1 < DENSE1_NUM; d1++) {
dense1[d1] = dense1_biases[d1];
for (uint8_t fl = 0; fl < CONV_NUM+2; fl++) {
dense1[d1] += flattened[fl]*dense1_weights[d1][fl];
}
RELU(dense1[d1]);
}
/* ------------------- *
* Second dense layer *
* ------------------- */
for (uint8_t d2 = 0; d2 < DENSE2_NUM; d2++) {
dense2[d2] = dense2_biases[d2];
for (uint8_t d1 = 0; d1 < DENSE1_NUM; d1++) {
dense2[d2] += dense1[d1]*dense2_weights[d2][d1];
}
RELU(dense2[d2]);
}
/* ------------- *
* Output layer *
* ------------- */
float output = output_bias;
for (uint8_t d2 = 0; d2 < DENSE2_NUM; d2++) {
output += dense2[d2]*output_weights[d2];
}
// Truncated Pade approximant of logistic function
output = (12.0+output+50.0*output/(output*output+10.0))/24.0;
/*
* // Truncated Pade approximant of tanh
* output = output/6+25*output/(6*(2*output*output+5));
*/
if (output > 1.0) return 1.0;
else if (output < 0.0) return 0.0;
return output;
}
// ===================================================================
// Minimax using the above evaluator
// ===================================================================
static void
previous_ply(void) {
if (ply>0) ply--;
if (ply == 1) {
current_colour = C_WHITE;
} else {
if (current_colour == C_BLACK) current_colour = C_WHITE;
else current_colour = C_BLACK;
}
}
float
ct1986_minimax(const uint8_t cur_depth, const uint8_t max_depth,
const uint8_t min) {
enum E_RESULT r;
uint16_t colours_backup[board_size];
uint8_t celldat_backup[board_size], drops[board_size];
const uint8_t white_count_backup = white_count,
black_count_backup = black_count;
// 1.0 is a `certain' black win, -1.0 is a `certain' white win.
float this = 0, optimal = (min) ? 2.0 : -2.0;
// Step across the board
for (uint8_t row = 0; row < board_size; row++) {
for (uint8_t col = 0; col < board_size; col++) {
// Try all valid actions for this square. Is it empty?
const uint8_t loc = THE_COORDS(col, row);
const uint8_t count = COUNT_AT(loc);
// Only try moves after CPS
if (count && ((colours[loc] & 1) == current_colour) && ply>2) {
// There are stones, can we move them in a given direction?
// I'm not a huge fan of looping through enums, but it's
// better than manually unrolling this. Sufficiently smart
// compilers?
// Back up the row of the board
for (uint8_t y = 0; y < board_size; y++) {
colours_backup[y] = colours[THE_COORDS(col, y)];
celldat_backup[y] = celldat[THE_COORDS(col, y)];
}
for (enum MOVE_DIRECTION dir = M_UP; dir <= M_RIGHT; dir++) {
// Back-up the column once we start looking horizontally
if (dir == M_LEFT) {
for (uint8_t x = 0; x < board_size; x++) {
colours_backup[x] = colours[THE_COORDS(x, row)];
celldat_backup[x] = celldat[THE_COORDS(x, row)];
}
}
// We don't do anything terribly efficient or smart here,
// just try everything...
// For every number of steps
for (uint8_t steps = 1; steps < board_size && steps <= count; steps++) {
uint8_t idx, carry;
for (idx = 0; idx < steps; idx++) drops[idx]=0;
idx = 0;
while (idx < steps) {
// Increment the drop sequence
carry = 0;
drops[idx]++;
do {
if (carry) { drops[++idx]++; carry = 0;}
if (drops[idx] > count || drops[idx] > board_size) {
drops[idx] = 1; carry = 1;
}
} while (carry && idx < steps);
// If carry is still set here we're done
if (carry == 0) {
// Try it, and note that try_move will never return
// GAME_END. It does not check for winners. We don't
// presently do that either, trust in the magic
// numbers :)
r = try_move(loc, dir, steps, drops);
if (r == ACT_OK) {
// Decide what to do based on our depth
if (cur_depth == max_depth) {
// We're at the bottom, evaluate
this = ct1986_evaluate_black_win();
} else {
// We're not at the bottom, recurse first
next_ply();
this = ct1986_minimax(cur_depth + 1, max_depth, 1-min);
previous_ply();
}
// Update depending on min and optimal
if ( (min && (this < optimal))
|| ((min==0) && (this > optimal))) {
optimal = this;
if (cur_depth == 0)
generate_move(loc, dir, steps, drops, ct1986_ptn);
}
// Reset the board data
if (dir <= M_DOWN) {
for (uint8_t y = 0; y < board_size; y++) {
colours[THE_COORDS(col, y)] = colours_backup[y];
celldat[THE_COORDS(col, y)] = celldat_backup[y];
}
} else {
for (uint8_t x = 0; x < board_size; x++) {
colours[THE_COORDS(x, row)] = colours_backup[x];
celldat[THE_COORDS(x, row)] = celldat_backup[x];
}
}
}
}
}
}
}
} else if (count == 0) {
// Empty square, try the three placements. Again, looping
// through enums, sigh.
for (enum STONE_VARIANT stone = STONE_FLAT;
stone <= STONE_CAPSTONE; stone++) {
// try_place will never check for winning, and we don't do
// that either here
r = try_place(loc, current_colour, stone);
// Legal placement, evaluate it
if (r == ACT_OK) {
// Decide what to do based on our depth
if (cur_depth == max_depth) {
// We're at the bottom, evaluate
this = ct1986_evaluate_black_win();
} else {
// We're not at the bottom, recurse first
next_ply();
this = ct1986_minimax(cur_depth + 1, max_depth, 1-min);
previous_ply();
}
// Update depending on min and optimal
if ( (min && (this < optimal))
|| ((min==0) && (this > optimal))) {
optimal = this;
// Store the result if we're at the top
if (cur_depth == 0)
generate_place(loc, stone, ct1986_ptn);
}
// Reset the state
celldat[loc] = 0;
white_count = white_count_backup;
black_count = black_count_backup;
}
}
}
ct1986_display_progress(cur_depth);
}
}
return optimal;
}
|
