Commit | Line | Data |
---|---|---|
7eeb782e AT |
1 | /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\ |
2 | * This is GNU Go, a Go program. Contact gnugo@gnu.org, or see * | |
3 | * http://www.gnu.org/software/gnugo/ for more information. * | |
4 | * * | |
5 | * Copyright 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, * | |
6 | * 2008 and 2009 by the Free Software Foundation. * | |
7 | * * | |
8 | * This program is free software; you can redistribute it and/or * | |
9 | * modify it under the terms of the GNU General Public License as * | |
10 | * published by the Free Software Foundation - version 3 or * | |
11 | * (at your option) any later version. * | |
12 | * * | |
13 | * This program is distributed in the hope that it will be useful, * | |
14 | * but WITHOUT ANY WARRANTY; without even the implied warranty of * | |
15 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * | |
16 | * GNU General Public License in file COPYING for more details. * | |
17 | * * | |
18 | * You should have received a copy of the GNU General Public * | |
19 | * License along with this program; if not, write to the Free * | |
20 | * Software Foundation, Inc., 51 Franklin Street, Fifth Floor, * | |
21 | * Boston, MA 02111, USA. * | |
22 | \* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ | |
23 | ||
24 | #include "gnugo.h" | |
25 | ||
26 | #include <stdio.h> | |
27 | #include <stdlib.h> | |
28 | #include <string.h> | |
29 | ||
30 | #include "liberty.h" | |
31 | #include "sgftree.h" | |
32 | #include "gg_utils.h" | |
33 | ||
34 | #include "random.h" | |
35 | #include <math.h> | |
36 | ||
37 | /* FIXME: Replace with a DEBUG_MC symbol for use with -d. */ | |
38 | static int mc_debug = 0; | |
39 | ||
40 | #define TURN_OFF_ASSERTIONS 1 | |
41 | ||
42 | ||
43 | /* Special board code for Monte Carlo simulations. | |
44 | * | |
45 | * A liberty edge is the combination of the position of the liberty | |
46 | * and the direction to a string given by the index into the delta[] | |
47 | * array. A liberty edge at lib with corresponding string in direction | |
48 | * delta[dir] is encoded as (lib << 2 | dir). | |
49 | * | |
50 | * The stones of a string are linked in a cyclic list through the | |
51 | * next_stone field, just like the global board does. | |
52 | * | |
53 | * Likewise the liberty edges corresponding to each string are | |
54 | * connected in a doubly linked cyclic list through the | |
55 | * previous_liberty_edge and next_liberty_edge fields. | |
56 | * | |
57 | * The reference stone has to be the same for every stone in a string | |
58 | * but it doesn't have to be a predictable one, in contrast to the | |
59 | * origin in the global board. The reference stone is the only one | |
60 | * which is guaranteed to have a valid pointer to the "first" liberty | |
61 | * edge (just an arbitrary element in the circular list). | |
62 | * | |
63 | * The local_context field contains information about the surrounding | |
64 | * 8 points. The bit layout is | |
65 | * | |
66 | * 23 : Black suicide. | |
67 | * 22 : White suicide. | |
68 | * 21 : Black self-atari. | |
69 | * 20 : White self-atari. | |
70 | * 19,18: Number of stones captured by black move. | |
71 | * 17,16: Number of stones captured by white move. | |
72 | * 15,14: Color to the southeast. | |
73 | * 13,12: Color to the northeast. | |
74 | * 11,10: Color to the northwest. | |
75 | * 9, 8: Color to the southwest. | |
76 | * 7, 6: Color to the east. | |
77 | * 5, 4: Color to the north. | |
78 | * 3, 2: Color to the west. | |
79 | * 1, 0: Color to the south. | |
80 | * | |
81 | * The number of stones in atari is 0 if empty or not atari, 1 if one | |
82 | * stone in atari, 2 if two stones in atari, and 3 if three or more stones | |
83 | * in atari. | |
84 | * | |
85 | * The queue array is used to form a linked single list data structure | |
86 | * with O(1) add, O(1) lookup, and O(n) delete operations. The | |
87 | * assumption is that v1 = queue[0] points to the first board vertex | |
88 | * in the list, v2 = queue[v1] points to the second vertex and so on. | |
89 | * The list ends when the next vertex is the off-board point 1. Board | |
90 | * vertices not included in the list have queue[v1] = 0. Thus an empty | |
91 | * list is characterized by queue[0] = 1 and queue[v] = 0 for all | |
92 | * vertices on the board. Generally queue[v] can be used to test for | |
93 | * membership in the list. The list is used to keep track of points | |
94 | * needing updated local context or value information. | |
95 | * | |
96 | * The move_values_*, partitioned_move_value_sums_*, | |
97 | * move_partition_lists_*, and move_value_sum_* fields are together | |
98 | * used to track move values and quickly sample according the | |
99 | * distribution determined by the move values. | |
100 | * | |
101 | * The move_values_* arrays naturally hold the values of each move. | |
102 | * | |
103 | * The move_partition_lists_* arrays form a two-level access to the | |
104 | * legal moves of respective color. Depending on the MAX_BOARD size, | |
105 | * the vertices are split into 2, 4, 8, or 16 partitions (see below) | |
106 | * where the partition number of each vertex is given by the 1, 2, 3, | |
107 | * or 4 least significant bits of the vertex index respectively. The | |
108 | * legal moves in each partition are linked together just like the | |
109 | * queue array described above. The only difference is that multiple | |
110 | * partition linked lists are represented in the same array by | |
111 | * starting from out of board indices 0..1, 0..3, 0..7, and 0..15 | |
112 | * respectively. | |
113 | * | |
114 | * The partitioned_move_value_sums_* arrays are simply the sums of | |
115 | * move values in each partition and the move_value_sum_white_* fields | |
116 | * are the sum of the values of all legal moves. | |
117 | */ | |
118 | ||
119 | #if MAX_BOARD < 4 | |
120 | #define NUM_MOVE_PARTITIONS 2 | |
121 | #elif MAX_BOARD < 8 | |
122 | #define NUM_MOVE_PARTITIONS 4 | |
123 | #elif MAX_BOARD < 16 | |
124 | #define NUM_MOVE_PARTITIONS 8 | |
125 | #else | |
126 | #define NUM_MOVE_PARTITIONS 16 | |
127 | #endif | |
128 | ||
129 | struct mc_board { | |
130 | Intersection board[BOARDSIZE]; | |
131 | int local_context[BOARDSIZE]; | |
132 | int queue[BOARDMAX]; | |
133 | unsigned int move_values_white[BOARDMAX]; | |
134 | unsigned int move_values_black[BOARDMAX]; | |
135 | unsigned int partitioned_move_value_sums_white[NUM_MOVE_PARTITIONS]; | |
136 | unsigned int partitioned_move_value_sums_black[NUM_MOVE_PARTITIONS]; | |
137 | int move_partition_lists_white[BOARDMAX]; | |
138 | int move_partition_lists_black[BOARDMAX]; | |
139 | unsigned int move_value_sum_white; | |
140 | unsigned int move_value_sum_black; | |
141 | int board_ko_pos; | |
142 | int reference_stone[BOARDMAX]; | |
143 | int next_stone[BOARDMAX]; | |
144 | int first_liberty_edge[BOARDMAX]; | |
145 | int previous_liberty_edge[4 * BOARDMAX]; | |
146 | int next_liberty_edge[4 * BOARDMAX]; | |
147 | Hash_data hash; | |
148 | }; | |
149 | ||
150 | #define MC_ADD_TO_UPDATE_QUEUE(mc, pos) \ | |
151 | do { \ | |
152 | if (!mc->queue[pos]) { \ | |
153 | mc->queue[pos] = mc->queue[0]; \ | |
154 | mc->queue[0] = pos; \ | |
155 | } \ | |
156 | } while (0) | |
157 | ||
158 | #define MC_ON_BOARD(pos) (mc->board[pos] != GRAY) | |
159 | ||
160 | /* Add a liberty edge for a string at pos with liberty at lib and | |
161 | * direction dir. | |
162 | */ | |
163 | static void | |
164 | mc_add_liberty_edge(struct mc_board *mc, int pos, int lib, int dir) | |
165 | { | |
166 | int this_liberty_edge = (lib << 2) | dir; | |
167 | int reference = mc->reference_stone[pos]; | |
168 | int first_liberty_edge = mc->first_liberty_edge[reference]; | |
169 | ||
170 | #if !TURN_OFF_ASSERTIONS | |
171 | gg_assert(lib + delta[dir] == pos); | |
172 | #endif | |
173 | ||
174 | if (first_liberty_edge) { | |
175 | int second_liberty_edge = mc->next_liberty_edge[first_liberty_edge]; | |
176 | mc->previous_liberty_edge[this_liberty_edge] = first_liberty_edge; | |
177 | mc->next_liberty_edge[this_liberty_edge] = second_liberty_edge; | |
178 | mc->next_liberty_edge[first_liberty_edge] = this_liberty_edge; | |
179 | mc->previous_liberty_edge[second_liberty_edge] = this_liberty_edge; | |
180 | } | |
181 | else { | |
182 | mc->first_liberty_edge[reference] = this_liberty_edge; | |
183 | mc->next_liberty_edge[this_liberty_edge] = this_liberty_edge; | |
184 | mc->previous_liberty_edge[this_liberty_edge] = this_liberty_edge; | |
185 | } | |
186 | } | |
187 | ||
188 | ||
189 | /* Remove a liberty edge for a string at pos with liberty at lib and | |
190 | * direction dir. | |
191 | */ | |
192 | static int | |
193 | mc_remove_liberty_edge(struct mc_board *mc, int pos, int lib, int dir) | |
194 | { | |
195 | int reference = mc->reference_stone[pos]; | |
196 | int this_liberty_edge = (lib << 2) | dir; | |
197 | int next = mc->next_liberty_edge[this_liberty_edge]; | |
198 | int previous = mc->previous_liberty_edge[this_liberty_edge]; | |
199 | ||
200 | #if !TURN_OFF_ASSERTIONS | |
201 | gg_assert(lib + delta[dir] == pos); | |
202 | #endif | |
203 | ||
204 | if (next == this_liberty_edge) { | |
205 | mc->first_liberty_edge[reference] = 0; | |
206 | return 0; | |
207 | } | |
208 | ||
209 | mc->next_liberty_edge[previous] = next; | |
210 | mc->previous_liberty_edge[next] = previous; | |
211 | if (mc->first_liberty_edge[reference] == this_liberty_edge) | |
212 | mc->first_liberty_edge[reference] = next; | |
213 | ||
214 | return next; | |
215 | } | |
216 | ||
217 | ||
218 | /* Join the strings at str1 and str2. It is assumed that str1 is a | |
219 | * newly placed stone (possibly already joined with other strings) and | |
220 | * that the liberty edge corresponding to the liberty at the newly | |
221 | * placed stone has not yet been removed. | |
222 | */ | |
223 | static void | |
224 | mc_join_strings(struct mc_board *mc, int str1, int str2) | |
225 | { | |
226 | int reference = mc->reference_stone[str2]; | |
227 | int liberty_edge2 = mc->first_liberty_edge[reference]; | |
228 | int liberty_edge1 = mc->first_liberty_edge[mc->reference_stone[str1]]; | |
229 | int next1; | |
230 | int next2; | |
231 | int pos = str1; | |
232 | ||
233 | /* Update the reference stone for str1. */ | |
234 | do { | |
235 | mc->reference_stone[pos] = reference; | |
236 | pos = mc->next_stone[pos]; | |
237 | } while (pos != str1); | |
238 | ||
239 | /* Switch next_stone pointers to join the strings. */ | |
240 | next1 = mc->next_stone[str1]; | |
241 | mc->next_stone[str1] = mc->next_stone[str2]; | |
242 | mc->next_stone[str2] = next1; | |
243 | ||
244 | /* Join the circular liberty_edge structures. We know that str2 | |
245 | * still has a liberty listed at the newly added stone so | |
246 | * liberty_edge2 is guaranteed to be non-zero. | |
247 | */ | |
248 | if (liberty_edge1 != 0) { | |
249 | next1 = mc->next_liberty_edge[liberty_edge1]; | |
250 | next2 = mc->next_liberty_edge[liberty_edge2]; | |
251 | mc->next_liberty_edge[liberty_edge1] = next2; | |
252 | mc->next_liberty_edge[liberty_edge2] = next1; | |
253 | mc->previous_liberty_edge[next1] = liberty_edge2; | |
254 | mc->previous_liberty_edge[next2] = liberty_edge1; | |
255 | } | |
256 | } | |
257 | ||
258 | ||
259 | /* Does the string at str have at most two liberties? In that case, | |
260 | * add them to the update queue. | |
261 | */ | |
262 | static void | |
263 | mc_queue_max_two_liberties(struct mc_board *mc, int str) | |
264 | { | |
265 | int reference = mc->reference_stone[str]; | |
266 | int first_liberty_edge = mc->first_liberty_edge[reference]; | |
267 | int first_liberty = first_liberty_edge >> 2; | |
268 | int liberty_edge = mc->next_liberty_edge[first_liberty_edge]; | |
269 | int second_liberty; | |
270 | #if !TURN_OFF_ASSERTIONS | |
271 | ASSERT1(IS_STONE(mc->board[str]), str); | |
272 | #endif | |
273 | if (first_liberty == NO_MOVE) | |
274 | return; | |
275 | while (liberty_edge != first_liberty_edge) { | |
276 | if ((liberty_edge >> 2) != first_liberty) { | |
277 | second_liberty = liberty_edge >> 2; | |
278 | while (liberty_edge != first_liberty_edge) { | |
279 | if ((liberty_edge >> 2) != first_liberty | |
280 | && (liberty_edge >> 2) != second_liberty) | |
281 | return; | |
282 | liberty_edge = mc->next_liberty_edge[liberty_edge]; | |
283 | } | |
284 | MC_ADD_TO_UPDATE_QUEUE(mc, first_liberty); | |
285 | MC_ADD_TO_UPDATE_QUEUE(mc, second_liberty); | |
286 | return; | |
287 | } | |
288 | liberty_edge = mc->next_liberty_edge[liberty_edge]; | |
289 | } | |
290 | ||
291 | MC_ADD_TO_UPDATE_QUEUE(mc, first_liberty); | |
292 | } | |
293 | ||
294 | ||
295 | /* Remove the string at str from the board. */ | |
296 | static int | |
297 | mc_remove_string(struct mc_board *mc, int str) | |
298 | { | |
299 | int color = mc->board[str]; | |
300 | int other = OTHER_COLOR(color); | |
301 | int pos = str; | |
302 | int num_removed_stones = 0; | |
303 | int k; | |
304 | ||
305 | do { | |
306 | for (k = 0; k < 8; k++) { | |
307 | if (k < 4 && mc->board[pos + delta[k]] == other) { | |
308 | mc_queue_max_two_liberties(mc, pos + delta[k]); | |
309 | mc_add_liberty_edge(mc, pos + delta[k], pos, k); | |
310 | } | |
311 | if (mc->board[pos + delta[k]] == EMPTY) | |
312 | MC_ADD_TO_UPDATE_QUEUE(mc, pos + delta[k]); | |
313 | } | |
314 | mc->board[pos] = EMPTY; | |
315 | mc->local_context[NW(pos)] ^= color << 14; | |
316 | mc->local_context[SW(pos)] ^= color << 12; | |
317 | mc->local_context[SE(pos)] ^= color << 10; | |
318 | mc->local_context[NE(pos)] ^= color << 8; | |
319 | mc->local_context[WEST(pos)] ^= color << 6; | |
320 | mc->local_context[SOUTH(pos)] ^= color << 4; | |
321 | mc->local_context[EAST(pos)] ^= color << 2; | |
322 | mc->local_context[NORTH(pos)] ^= color; | |
323 | hashdata_invert_stone(&(mc->hash), pos, color); | |
324 | MC_ADD_TO_UPDATE_QUEUE(mc, pos); | |
325 | num_removed_stones++; | |
326 | pos = mc->next_stone[pos]; | |
327 | } while (pos != str); | |
328 | ||
329 | return num_removed_stones; | |
330 | } | |
331 | ||
332 | ||
333 | /* Initialize a Monte Carlo board struct from the global board. */ | |
334 | static void | |
335 | mc_init_board_from_global_board(struct mc_board *mc) | |
336 | { | |
337 | int stones[BOARDMAX]; | |
338 | int num_stones; | |
339 | int pos; | |
340 | int k; | |
341 | int r; | |
342 | ||
343 | memcpy(mc->board, board, sizeof(mc->board)); | |
344 | mc->board_ko_pos = board_ko_pos; | |
345 | mc->hash = board_hash; | |
346 | memset(mc->queue, 0, sizeof(mc->queue)); | |
347 | mc->queue[0] = 1; | |
348 | ||
349 | memset(mc->next_stone, 0, sizeof(mc->next_stone)); | |
350 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
351 | int geometry = ((mc->board[SE(pos)] << 14) | |
352 | | (mc->board[NE(pos)] << 12) | |
353 | | (mc->board[NW(pos)] << 10) | |
354 | | (mc->board[SW(pos)] << 8) | |
355 | | (mc->board[EAST(pos)] << 6) | |
356 | | (mc->board[NORTH(pos)] << 4) | |
357 | | (mc->board[WEST(pos)] << 2) | |
358 | | mc->board[SOUTH(pos)]); | |
359 | mc->local_context[pos] = geometry; | |
360 | if (board[pos] == EMPTY) { | |
361 | int s; | |
362 | int captured_black_stones = 0; | |
363 | int captured_white_stones = 0; | |
364 | if (is_self_atari(pos, WHITE)) | |
365 | mc->local_context[pos] |= 1 << 20; | |
366 | if (is_self_atari(pos, BLACK)) | |
367 | mc->local_context[pos] |= 1 << 21; | |
368 | if (is_suicide(pos, WHITE)) | |
369 | mc->local_context[pos] |= 1 << 22; | |
370 | if (is_suicide(pos, BLACK)) | |
371 | mc->local_context[pos] |= 1 << 23; | |
372 | for (s = 0; s < 4; s++) { | |
373 | if (board[pos + delta[s]] == BLACK | |
374 | && countlib(pos + delta[s]) == 1) | |
375 | captured_black_stones += countstones(pos + delta[s]); | |
376 | else if (board[pos + delta[s]] == WHITE | |
377 | && countlib(pos + delta[s]) == 1) | |
378 | captured_white_stones += countstones(pos + delta[s]); | |
379 | } | |
380 | if (captured_black_stones > 3) | |
381 | captured_black_stones = 3; | |
382 | if (captured_white_stones > 3) | |
383 | captured_white_stones = 3; | |
384 | mc->local_context[pos] |= captured_black_stones << 16; | |
385 | mc->local_context[pos] |= captured_white_stones << 18; | |
386 | } | |
387 | ||
388 | if (IS_STONE(board[pos]) && mc->next_stone[pos] == 0) { | |
389 | num_stones = findstones(pos, BOARDMAX, stones); | |
390 | mc->first_liberty_edge[pos] = 0; | |
391 | for (r = 0; r < num_stones; r++) { | |
392 | mc->next_stone[stones[r]] = stones[(r + 1) % num_stones]; | |
393 | mc->reference_stone[stones[r]] = pos; | |
394 | for (k = 0; k < 4; k++) { | |
395 | if (board[stones[r] + delta[k]] == EMPTY) | |
396 | mc_add_liberty_edge(mc, stones[r], stones[r] + delta[k], | |
397 | (k + 2) % 4); | |
398 | } | |
399 | } | |
400 | } | |
401 | } | |
402 | } | |
403 | ||
404 | ||
405 | #if 0 | |
406 | /* Debug tool. */ | |
407 | static void | |
408 | mc_check_consistency_with_global_board(struct mc_board *mc) | |
409 | { | |
410 | int pos; | |
411 | ||
412 | ASSERT1(board_ko_pos == mc->board_ko_pos, mc->board_ko_pos); | |
413 | for (pos = 0; pos < BOARDSIZE; pos++) { | |
414 | ASSERT1(board[pos] == mc->board[pos], pos); | |
415 | if (IS_STONE(board[pos])) { | |
416 | ASSERT1(same_string(pos, mc->reference_stone[pos]), pos); | |
417 | if (find_origin(pos) == pos) { | |
418 | int reference = mc->reference_stone[pos]; | |
419 | int pos2 = pos; | |
420 | int num_stones = 0; | |
421 | int first_liberty_edge; | |
422 | int liberty_edge; | |
423 | int num_liberty_edges = 0; | |
424 | int k; | |
425 | int ml[4 * BOARDMAX]; | |
426 | memset(ml, 0, sizeof(ml)); | |
427 | ||
428 | do { | |
429 | ASSERT1(mc->reference_stone[pos2] == reference, pos2); | |
430 | ASSERT1(num_stones < countstones(pos), pos); | |
431 | num_stones++; | |
432 | for (k = 0; k < 4; k++) | |
433 | if (board[pos2 + delta[k]] == EMPTY) { | |
434 | ml[(pos2 + delta[k]) << 2 | (k + 2) % 4] = 1; | |
435 | num_liberty_edges++; | |
436 | } | |
437 | pos2 = mc->next_stone[pos2]; | |
438 | } while (pos2 != pos); | |
439 | ASSERT1(num_stones == countstones(pos), pos); | |
440 | ||
441 | first_liberty_edge = mc->first_liberty_edge[reference]; | |
442 | liberty_edge = first_liberty_edge; | |
443 | do { | |
444 | int previous = mc->previous_liberty_edge[liberty_edge]; | |
445 | int next = mc->next_liberty_edge[liberty_edge]; | |
446 | ASSERT1(ml[liberty_edge] == 1, pos); | |
447 | ml[liberty_edge] = 0; | |
448 | num_liberty_edges--; | |
449 | ASSERT1(mc->next_liberty_edge[previous] == liberty_edge, pos); | |
450 | ASSERT1(mc->previous_liberty_edge[next] == liberty_edge, pos); | |
451 | ASSERT1(liberty_of_string(liberty_edge >> 2, pos), pos); | |
452 | liberty_edge = mc->next_liberty_edge[liberty_edge]; | |
453 | } while (liberty_edge != first_liberty_edge); | |
454 | ASSERT1(num_liberty_edges == 0, pos); | |
455 | } | |
456 | } | |
457 | } | |
458 | } | |
459 | #endif | |
460 | ||
461 | ||
462 | /* Write the Monte Carlo board to outfile. */ | |
463 | static void | |
464 | mc_showboard(struct mc_board *mc, FILE *outfile) | |
465 | { | |
466 | int i, j; | |
467 | ||
468 | draw_letter_coordinates(outfile); | |
469 | ||
470 | for (i = 0; i < board_size; i++) { | |
471 | fprintf(outfile, "\n%2d", board_size - i); | |
472 | ||
473 | for (j = 0; j < board_size; j++) { | |
474 | if (mc->board[POS(i, j)] == EMPTY) | |
475 | fprintf(outfile, " %c", is_hoshi_point(i, j) ? '+' : '.'); | |
476 | else | |
477 | fprintf(outfile, " %c", mc->board[POS(i, j)] == BLACK ? 'X' : 'O'); | |
478 | } | |
479 | } | |
480 | ||
481 | fprintf(outfile, "\n"); | |
482 | draw_letter_coordinates(outfile); | |
483 | } | |
484 | ||
485 | ||
486 | /* Count the number of stones in the string at str. Stop counting if | |
487 | * maxstones is reached. | |
488 | */ | |
489 | static int | |
490 | mc_countstones(struct mc_board *mc, int str, int maxstones) | |
491 | { | |
492 | int stone = str; | |
493 | int num_stones = 0; | |
494 | do { | |
495 | num_stones++; | |
496 | stone = mc->next_stone[stone]; | |
497 | } while (stone != str && num_stones < maxstones); | |
498 | ||
499 | return num_stones; | |
500 | } | |
501 | ||
502 | ||
503 | /* Suicide is incrementally tracked by the local context information. */ | |
504 | #define mc_is_suicide(mc, pos, color) \ | |
505 | ((mc->local_context[pos] >> (21 + color)) & 1) | |
506 | ||
507 | ||
508 | #if !TURN_OFF_ASSERTIONS | |
509 | /* Is a move at pos by color legal? */ | |
510 | static int | |
511 | mc_is_legal(struct mc_board *mc, int pos, int color) | |
512 | { | |
513 | if (pos == PASS_MOVE) | |
514 | return 1; | |
515 | ||
516 | if (mc->board[pos] != EMPTY) | |
517 | return 0; | |
518 | ||
519 | if (pos == mc->board_ko_pos) { | |
520 | if (mc->board[WEST(pos)] == OTHER_COLOR(color) | |
521 | || mc->board[EAST(pos)] == OTHER_COLOR(color)) { | |
522 | return 0; | |
523 | } | |
524 | } | |
525 | ||
526 | return !mc_is_suicide(mc, pos, color); | |
527 | } | |
528 | #endif | |
529 | ||
530 | ||
531 | /* Is the string at str in atari? Always place one liberty of the | |
532 | * string in lib, unless it's a null pointer. | |
533 | */ | |
534 | static int | |
535 | mc_is_in_atari(struct mc_board *mc, int str, int *lib) | |
536 | { | |
537 | int reference = mc->reference_stone[str]; | |
538 | int first_liberty_edge = mc->first_liberty_edge[reference]; | |
539 | int liberty = first_liberty_edge >> 2; | |
540 | int liberty_edge = mc->next_liberty_edge[first_liberty_edge]; | |
541 | #if !TURN_OFF_ASSERTIONS | |
542 | ASSERT1(IS_STONE(mc->board[str]), str); | |
543 | #endif | |
544 | if (lib) | |
545 | *lib = liberty; | |
546 | while (liberty_edge != first_liberty_edge) { | |
547 | if ((liberty_edge >> 2) != liberty) | |
548 | return 0; | |
549 | liberty_edge = mc->next_liberty_edge[liberty_edge]; | |
550 | } | |
551 | ||
552 | return 1; | |
553 | } | |
554 | ||
555 | ||
556 | /* Does the liberty edge chain at first_liberty_edge contain more than | |
557 | * one distinct liberty? | |
558 | */ | |
559 | static int | |
560 | mc_is_in_atari2(struct mc_board *mc, int first_liberty, int first_liberty_edge) | |
561 | { | |
562 | int liberty_edge = mc->next_liberty_edge[first_liberty_edge]; | |
563 | while (liberty_edge != first_liberty_edge) { | |
564 | if ((liberty_edge >> 2) != first_liberty) | |
565 | return 0; | |
566 | liberty_edge = mc->next_liberty_edge[liberty_edge]; | |
567 | } | |
568 | ||
569 | return 1; | |
570 | } | |
571 | ||
572 | ||
573 | /* Count the number of stones that would be captured if color played at move. | |
574 | * Return at most the number given by maxstones. | |
575 | */ | |
576 | static int | |
577 | mc_stones_in_atari(struct mc_board *mc, int move, int color, int maxstones) | |
578 | { | |
579 | int k; | |
580 | int stones_in_atari = 0; | |
581 | for (k = 0; k < 4 && stones_in_atari < maxstones; k++) { | |
582 | int pos = move + delta[k]; | |
583 | if (mc->board[pos] == OTHER_COLOR(color) | |
584 | && mc_is_in_atari(mc, pos, NULL)) | |
585 | stones_in_atari += mc_countstones(mc, pos, maxstones - stones_in_atari); | |
586 | } | |
587 | ||
588 | return stones_in_atari; | |
589 | } | |
590 | ||
591 | ||
592 | /* Does the string at str have exactly two liberties? One liberty is | |
593 | * assumed to be known and passed in first_liberty, whereas the second | |
594 | * is placed in second_liberty. | |
595 | */ | |
596 | static int | |
597 | mc_has_two_liberties_one_given(struct mc_board *mc, int str, | |
598 | int first_liberty, int *second_liberty) | |
599 | { | |
600 | int reference = mc->reference_stone[str]; | |
601 | int first_liberty_edge = mc->first_liberty_edge[reference]; | |
602 | int liberty_edge = first_liberty_edge; | |
603 | *second_liberty = NO_MOVE; | |
604 | do { | |
605 | int liberty = liberty_edge >> 2; | |
606 | if (liberty != first_liberty) { | |
607 | if (*second_liberty == NO_MOVE) | |
608 | *second_liberty = liberty; | |
609 | else if (liberty != *second_liberty) | |
610 | return 0; | |
611 | } | |
612 | liberty_edge = mc->next_liberty_edge[liberty_edge]; | |
613 | } while (liberty_edge != first_liberty_edge); | |
614 | ||
615 | return (*second_liberty != NO_MOVE); | |
616 | } | |
617 | ||
618 | ||
619 | /* Is a move at pos by color a self atari? */ | |
620 | static int | |
621 | mc_is_self_atari(struct mc_board *mc, int pos, int color) | |
622 | { | |
623 | int k; | |
624 | int captured = NO_MOVE; | |
625 | int liberty = NO_MOVE; | |
626 | int reference; | |
627 | int other; | |
628 | ||
629 | /* Quick test which is often effective. */ | |
630 | if (((mc->board[SOUTH(pos)] == EMPTY) | |
631 | + (mc->board[WEST(pos)] == EMPTY) | |
632 | + (mc->board[NORTH(pos)] == EMPTY) | |
633 | + (mc->board[EAST(pos)] == EMPTY)) > 1) | |
634 | return 0; | |
635 | ||
636 | /* Otherwise look closer. */ | |
637 | for (k = 0; k < 4; k++) { | |
638 | int first_liberty_edge; | |
639 | int liberty_edge; | |
640 | int additional_liberty = 0; | |
641 | int pos2 = pos + delta[k]; | |
642 | if (mc->board[pos2] == EMPTY) { | |
643 | if (pos2 != liberty) { | |
644 | if (liberty != NO_MOVE) | |
645 | return 0; | |
646 | else | |
647 | liberty = pos2; | |
648 | } | |
649 | } | |
650 | else if (IS_STONE(mc->board[pos2])) { | |
651 | first_liberty_edge = (pos << 2) | k; | |
652 | liberty_edge = mc->next_liberty_edge[first_liberty_edge]; | |
653 | while (liberty_edge != first_liberty_edge) { | |
654 | int lib = liberty_edge >> 2; | |
655 | if (lib != pos) { | |
656 | additional_liberty = 1; | |
657 | if (mc->board[pos2] == color) { | |
658 | if (lib != liberty) { | |
659 | if (liberty != NO_MOVE) | |
660 | return 0; | |
661 | else | |
662 | liberty = lib; | |
663 | } | |
664 | } | |
665 | else | |
666 | break; | |
667 | } | |
668 | liberty_edge = mc->next_liberty_edge[liberty_edge]; | |
669 | } | |
670 | ||
671 | if (mc->board[pos2] != color && additional_liberty == 0) { | |
672 | captured = pos2; | |
673 | if (pos2 != liberty) { | |
674 | if (liberty != NO_MOVE) | |
675 | return 0; | |
676 | else | |
677 | liberty = pos2; | |
678 | } | |
679 | } | |
680 | } | |
681 | } | |
682 | ||
683 | if (liberty == NO_MOVE || captured == NO_MOVE) | |
684 | return 1; | |
685 | ||
686 | /* Now only the difficult case remains where there was no adjacent | |
687 | * empty stone, no adjacent friendly stone with an extra liberty, | |
688 | * and exactly one neighbor was captured. Then the question is | |
689 | * whether the capture produced a second liberty elsewhere. | |
690 | */ | |
691 | reference = mc->reference_stone[captured]; | |
692 | other = OTHER_COLOR(color); | |
693 | for (k = 0; k < 4; k++) { | |
694 | if (mc->board[pos + delta[k]] == color) { | |
695 | int stone = pos + delta[k]; | |
696 | do { | |
697 | int m; | |
698 | for (m = 0; m < 4; m++) { | |
699 | int pos2 = stone + delta[m]; | |
700 | if (mc->board[pos2] == other | |
701 | && pos2 != captured | |
702 | && mc->reference_stone[pos2] == reference) | |
703 | return 0; | |
704 | } | |
705 | stone = mc->next_stone[stone]; | |
706 | } while (stone != pos + delta[k]); | |
707 | } | |
708 | } | |
709 | ||
710 | return 1; | |
711 | } | |
712 | ||
713 | ||
714 | /* Update the local context information at pos, except the geometric | |
715 | * information, by recomputing it. Most of the information is obtained | |
716 | * by analyzing the presence of empty vertices or stones in atari | |
717 | * adjacent to pos. | |
718 | * | |
719 | * FIXME: There's some computations wasted by calling the full | |
720 | * mc_is_self_atari() and mc_stones_in_atari() functions when parts of | |
721 | * the relevant information is already available. | |
722 | */ | |
723 | static void | |
724 | mc_update_local_context(struct mc_board *mc, int pos) | |
725 | { | |
726 | int min_white_liberties = 0; | |
727 | int min_black_liberties = 0; | |
728 | int white_liberty_through_stones = 0; | |
729 | int black_liberty_through_stones = 0; | |
730 | int min_white_captured_stones = 0; | |
731 | int min_black_captured_stones = 0; | |
732 | int white_suicide = 0; | |
733 | int black_suicide = 0; | |
734 | int white_self_atari = 0; | |
735 | int black_self_atari = 0; | |
736 | int white_captured_stones = 0; | |
737 | int black_captured_stones = 0; | |
738 | int k; | |
739 | for (k = 0; k < 4; k++) { | |
740 | int pos2 = pos + delta[k]; | |
741 | switch (mc->board[pos2]) { | |
742 | case EMPTY: | |
743 | min_white_liberties++; | |
744 | min_black_liberties++; | |
745 | break; | |
746 | case WHITE: | |
747 | if (mc_is_in_atari2(mc, pos, (pos << 2) | k)) { | |
748 | min_black_liberties++; | |
749 | min_white_captured_stones++; | |
750 | } | |
751 | else | |
752 | white_liberty_through_stones = 1; | |
753 | break; | |
754 | case BLACK: | |
755 | if (mc_is_in_atari2(mc, pos, (pos << 2) | k)) { | |
756 | min_white_liberties++; | |
757 | min_black_captured_stones++; | |
758 | } | |
759 | else | |
760 | black_liberty_through_stones = 1; | |
761 | break; | |
762 | } | |
763 | } | |
764 | ||
765 | if (min_white_liberties + white_liberty_through_stones == 0) { | |
766 | white_suicide = 1; | |
767 | white_self_atari = 1; | |
768 | } | |
769 | else if (min_white_liberties <= 1) | |
770 | white_self_atari = mc_is_self_atari(mc, pos, WHITE); | |
771 | ||
772 | if (min_black_liberties + black_liberty_through_stones == 0) { | |
773 | black_suicide = 1; | |
774 | black_self_atari = 1; | |
775 | } | |
776 | else if (min_black_liberties <= 1) | |
777 | black_self_atari = mc_is_self_atari(mc, pos, BLACK); | |
778 | ||
779 | if (min_white_captured_stones >= 3) | |
780 | white_captured_stones = 3; | |
781 | else if (min_white_captured_stones > 0) | |
782 | white_captured_stones = mc_stones_in_atari(mc, pos, BLACK, 3); | |
783 | ||
784 | if (min_black_captured_stones >= 3) | |
785 | black_captured_stones = 3; | |
786 | else if (min_black_captured_stones > 0) | |
787 | black_captured_stones = mc_stones_in_atari(mc, pos, WHITE, 3); | |
788 | ||
789 | mc->local_context[pos] &= 0xffff; | |
790 | mc->local_context[pos] |= black_captured_stones << 16; | |
791 | mc->local_context[pos] |= white_captured_stones << 18; | |
792 | mc->local_context[pos] |= white_self_atari << 20; | |
793 | mc->local_context[pos] |= black_self_atari << 21; | |
794 | mc->local_context[pos] |= white_suicide << 22; | |
795 | mc->local_context[pos] |= black_suicide << 23; | |
796 | } | |
797 | ||
798 | ||
799 | /* Play the move at pos by color. */ | |
800 | static int | |
801 | mc_play_move(struct mc_board *mc, int pos, int color) | |
802 | { | |
803 | int k; | |
804 | int captured_stones = 0; | |
805 | int num_direct_liberties = 0; | |
806 | int pos2; | |
807 | ||
808 | /* Clear the update queue. */ | |
809 | while (mc->queue[0] != 1) { | |
810 | pos2 = mc->queue[0]; | |
811 | mc->queue[0] = mc->queue[pos2]; | |
812 | mc->queue[pos2] = 0; | |
813 | } | |
814 | ||
815 | if (pos == PASS_MOVE) { | |
816 | if (mc->board_ko_pos != NO_MOVE) | |
817 | hashdata_invert_ko(&mc->hash, mc->board_ko_pos); | |
818 | mc->board_ko_pos = NO_MOVE; | |
819 | return 1; | |
820 | } | |
821 | ||
822 | /* The move must not be the ko point. */ | |
823 | if (pos == mc->board_ko_pos) { | |
824 | if (mc->board[WEST(pos)] == OTHER_COLOR(color) | |
825 | || mc->board[EAST(pos)] == OTHER_COLOR(color)) { | |
826 | return 0; | |
827 | } | |
828 | } | |
829 | ||
830 | /* Test for suicide. */ | |
831 | if (mc_is_suicide(mc, pos, color)) | |
832 | return 0; | |
833 | ||
834 | if (mc->board_ko_pos != NO_MOVE) | |
835 | hashdata_invert_ko(&mc->hash, mc->board_ko_pos); | |
836 | mc->board_ko_pos = NO_MOVE; | |
837 | ||
838 | #if !TURN_OFF_ASSERTIONS | |
839 | ASSERT1(mc->board[pos] == EMPTY, pos); | |
840 | #endif | |
841 | mc->board[pos] = color; | |
842 | hashdata_invert_stone(&mc->hash, pos, color); | |
843 | mc->next_stone[pos] = pos; | |
844 | ||
845 | /* Update the geometry part of the local context. */ | |
846 | mc->local_context[NW(pos)] |= color << 14; | |
847 | mc->local_context[SW(pos)] |= color << 12; | |
848 | mc->local_context[SE(pos)] |= color << 10; | |
849 | mc->local_context[NE(pos)] |= color << 8; | |
850 | mc->local_context[WEST(pos)] |= color << 6; | |
851 | mc->local_context[SOUTH(pos)] |= color << 4; | |
852 | mc->local_context[EAST(pos)] |= color << 2; | |
853 | mc->local_context[NORTH(pos)] |= color; | |
854 | ||
855 | mc->reference_stone[pos] = pos; | |
856 | mc->first_liberty_edge[pos] = 0; | |
857 | ||
858 | for (k = 0; k < 4; k++) { | |
859 | pos2 = pos + delta[k]; | |
860 | if (mc->board[pos2] == EMPTY) { | |
861 | mc_add_liberty_edge(mc, pos, pos2, (k + 2) % 4); | |
862 | num_direct_liberties++; | |
863 | MC_ADD_TO_UPDATE_QUEUE(mc, pos2); | |
864 | } | |
865 | } | |
866 | ||
867 | for (k = 0; k < 4; k++) { | |
868 | int liberty; | |
869 | pos2 = pos + delta[k]; | |
870 | if (mc->board[pos2] == color) { | |
871 | if (mc->reference_stone[pos] != mc->reference_stone[pos2]) { | |
872 | if (mc_has_two_liberties_one_given(mc, pos2, pos, &liberty)) | |
873 | MC_ADD_TO_UPDATE_QUEUE(mc, liberty); | |
874 | mc_join_strings(mc, pos, pos2); | |
875 | } | |
876 | mc_remove_liberty_edge(mc, pos2, pos, k); | |
877 | } | |
878 | } | |
879 | ||
880 | for (k = 0; k < 4; k++) { | |
881 | pos2 = pos + delta[k]; | |
882 | if (mc->board[pos2] == OTHER_COLOR(color)) { | |
883 | if (mc_remove_liberty_edge(mc, pos2, pos, k) == 0) | |
884 | captured_stones += mc_remove_string(mc, pos2); | |
885 | else | |
886 | mc_queue_max_two_liberties(mc, pos2); | |
887 | } | |
888 | } | |
889 | ||
890 | if (captured_stones == 1 | |
891 | && mc->next_stone[pos] == pos | |
892 | && num_direct_liberties == 0) { | |
893 | mc->board_ko_pos = mc->first_liberty_edge[pos] >> 2; | |
894 | hashdata_invert_ko(&mc->hash, mc->board_ko_pos); | |
895 | } | |
896 | ||
897 | mc_queue_max_two_liberties(mc, pos); | |
898 | ||
899 | /* Traverse the update queue and update the local context for queued | |
900 | * points. | |
901 | */ | |
902 | for (pos2 = mc->queue[0]; pos2 != 1; pos2 = mc->queue[pos2]) | |
903 | if (pos2 != pos) | |
904 | mc_update_local_context(mc, pos2); | |
905 | ||
906 | /* Add the immediate neighborhood of the move to the update queue | |
907 | * for recomputation of move values later on. | |
908 | */ | |
909 | MC_ADD_TO_UPDATE_QUEUE(mc, pos); | |
910 | for (k = 0; k < 8; k++) | |
911 | if (mc->board[pos + delta[k]] == EMPTY) | |
912 | MC_ADD_TO_UPDATE_QUEUE(mc, pos + delta[k]); | |
913 | ||
914 | return 1; | |
915 | } | |
916 | ||
917 | ||
918 | /***************************************************/ | |
919 | ||
920 | #define NUM_GEOMETRIES 1107 | |
921 | #define NUM_PROPERTIES 256 | |
922 | ||
923 | struct mc_pattern_table | |
924 | { | |
925 | unsigned short geometry_table[65536]; | |
926 | unsigned int values[(NUM_GEOMETRIES + 1) * NUM_PROPERTIES]; | |
927 | }; | |
928 | ||
929 | static struct mc_pattern_table mc_patterns; | |
930 | ||
931 | /* The pattern number is determined by the following bit layout: | |
932 | * 18-8: Geometry number (range 1..1107) | |
933 | * 7 : Opponent suicide | |
934 | * 6 : Our self-atari | |
935 | * 5 : Opponent self-atari | |
936 | * 4,3 : Our captures | |
937 | * 2,1 : Opponent captures | |
938 | * 0 : Near | |
939 | */ | |
940 | static int | |
941 | mc_find_pattern_number(struct mc_board *mc, int move, int color, | |
942 | int near_previous_move) | |
943 | { | |
944 | int local_context = mc->local_context[move]; | |
945 | int properties; | |
946 | int geometry; | |
947 | ||
948 | if (color == WHITE) { | |
949 | properties = (((local_context >> 16) & 0xa0) | |
950 | | ((local_context >> 14) & 0x40) | |
951 | | ((local_context >> 17) & 0x06) | |
952 | | ((local_context >> 13) & 0x18)); | |
953 | geometry = local_context & 0xffff; | |
954 | } | |
955 | else { | |
956 | properties = (local_context >> 15) & 0xfe; | |
957 | geometry = (((local_context & 0x5555) << 1) | |
958 | | ((local_context & 0xaaaa) >> 1)); | |
959 | } | |
960 | ||
961 | return ((mc_patterns.geometry_table[geometry] << 8) | |
962 | | properties | |
963 | | near_previous_move); | |
964 | } | |
965 | ||
966 | ||
967 | /* Geometry patterns have the neighborhood defined by the order | |
968 | * | |
969 | * 637 | |
970 | * 2*4 | |
971 | * 518 | |
972 | * | |
973 | * where * is the point to play. The reason for this seemingly | |
974 | * arbitrary order is to be consistent with the delta[] array | |
975 | * of point offsets. | |
976 | * | |
977 | * The 8 rotation/mirror transformations are given by reordering the | |
978 | * points like this: | |
979 | * 12345678 no transform | |
980 | * 41238567 rotation 90 | |
981 | * 34127856 rotation 180 | |
982 | * 23416785 rotation 270 | |
983 | * 14328765 mirror | |
984 | * 21435876 mirror + rotation 90 | |
985 | * 32146587 mirror + rotation 180 | |
986 | * 43217658 mirror + rotation 270 | |
987 | * | |
988 | * The geometry is encoded by a 16-bit integer where point 1 goes into | |
989 | * the 2 least significant bits and point 8 into the 2 most | |
990 | * significant bits. Each pair of bits contain the corresponding | |
991 | * EMPTY, WHITE, BLACK, GRAY (off board) values. | |
992 | */ | |
993 | static unsigned short | |
994 | mc_register_geometry_pattern(unsigned int pattern, unsigned short n) | |
995 | { | |
996 | int k; | |
997 | int j; | |
998 | unsigned int transformed_pattern; | |
999 | ||
1000 | if (mc_patterns.geometry_table[pattern] != 0) | |
1001 | return 0; | |
1002 | ||
1003 | for (k = 0; k < 8; k++) { | |
1004 | transformed_pattern = pattern; | |
1005 | if (k >= 4) { | |
1006 | /* Mirror pattern. */ | |
1007 | transformed_pattern = (((pattern & 0x0300) << 6) | |
1008 | | ((pattern & 0x000c) << 4) | |
1009 | | ((pattern & 0x0c00) << 2) | |
1010 | | (pattern & 0x0033) | |
1011 | | ((pattern & 0x3000) >> 2) | |
1012 | | ((pattern & 0x00c0) >> 4) | |
1013 | | ((pattern & 0xc000) >> 6)); | |
1014 | } | |
1015 | ||
1016 | /* Rotate pattern. */ | |
1017 | for (j = 0; j < k % 4; j++) { | |
1018 | transformed_pattern = (((transformed_pattern & 0xc0c0) >> 6) | |
1019 | | ((transformed_pattern & 0x3f3f) << 2)); | |
1020 | } | |
1021 | mc_patterns.geometry_table[transformed_pattern] = n; | |
1022 | } | |
1023 | ||
1024 | return 1; | |
1025 | } | |
1026 | ||
1027 | ||
1028 | /* Compute the mapping from 8-point local neighborhoods to rotation | |
1029 | * invariant geometry numbers. | |
1030 | */ | |
1031 | static void | |
1032 | mc_init_pattern_geometries(void) | |
1033 | { | |
1034 | unsigned int pattern; | |
1035 | unsigned short n = 1; | |
1036 | ||
1037 | static int initialized = 0; | |
1038 | if (initialized) | |
1039 | return; | |
1040 | initialized = 1; | |
1041 | ||
1042 | memset(mc_patterns.geometry_table, 0, sizeof(mc_patterns.geometry_table)); | |
1043 | ||
1044 | for (pattern = 0; pattern < 65536; pattern++) { | |
1045 | unsigned int off_board = (pattern & (pattern >> 1)) & 0x5555; | |
1046 | if (off_board == 0x0 || off_board == 0x1410 || off_board == 0x5450) | |
1047 | n += mc_register_geometry_pattern(pattern, n); | |
1048 | } | |
1049 | ||
1050 | gg_assert(n == NUM_GEOMETRIES + 1); | |
1051 | } | |
1052 | ||
1053 | ||
1054 | /* Determine which geometry numbers are matched by a pattern with | |
1055 | * possible wildcards, for use when loading pattern databases. | |
1056 | * | |
1057 | * This function is recursive with the argument n determining which | |
1058 | * point in the neighborhood is expanded for wildcards. | |
1059 | */ | |
1060 | static void | |
1061 | mc_match_geometries(int pattern[8], int *matching_geometries, int n) | |
1062 | { | |
1063 | int k; | |
1064 | int geometry = 0; | |
1065 | if (n == 8) { | |
1066 | /* The pattern has been fully expanded. Find the geometry number. */ | |
1067 | for (k = 0; k < 8; k++) { | |
1068 | if (pattern[k] == 'O') | |
1069 | geometry |= WHITE << (2 * k); | |
1070 | else if (pattern[k] == 'X') | |
1071 | geometry |= BLACK << (2 * k); | |
1072 | else if (pattern[k] == '+' || pattern[k] == '|' || pattern[k] == '-') | |
1073 | geometry |= (WHITE | BLACK) << (2 * k); | |
1074 | } | |
1075 | if (mc_patterns.geometry_table[geometry] != 0) { | |
1076 | matching_geometries[mc_patterns.geometry_table[geometry]] = 1; | |
1077 | } | |
1078 | } | |
1079 | else { | |
1080 | /* Recurse with all possible expansions of the current | |
1081 | * neighborhood point. | |
1082 | */ | |
1083 | int new_pattern[8]; | |
1084 | memcpy(new_pattern, pattern, sizeof(new_pattern)); | |
1085 | switch (pattern[n]) { | |
1086 | case '.': | |
1087 | case 'O': | |
1088 | case 'X': | |
1089 | case '|': | |
1090 | case '-': | |
1091 | case '+': | |
1092 | mc_match_geometries(new_pattern, matching_geometries, n + 1); | |
1093 | break; | |
1094 | case 'o': | |
1095 | new_pattern[n] = '.'; | |
1096 | mc_match_geometries(new_pattern, matching_geometries, n + 1); | |
1097 | new_pattern[n] = 'O'; | |
1098 | mc_match_geometries(new_pattern, matching_geometries, n + 1); | |
1099 | break; | |
1100 | case 'x': | |
1101 | new_pattern[n] = '.'; | |
1102 | mc_match_geometries(new_pattern, matching_geometries, n + 1); | |
1103 | new_pattern[n] = 'X'; | |
1104 | mc_match_geometries(new_pattern, matching_geometries, n + 1); | |
1105 | break; | |
1106 | case '?': | |
1107 | new_pattern[n] = '.'; | |
1108 | mc_match_geometries(new_pattern, matching_geometries, n + 1); | |
1109 | new_pattern[n] = 'O'; | |
1110 | mc_match_geometries(new_pattern, matching_geometries, n + 1); | |
1111 | new_pattern[n] = 'X'; | |
1112 | mc_match_geometries(new_pattern, matching_geometries, n + 1); | |
1113 | break; | |
1114 | case '%': | |
1115 | new_pattern[n] = '.'; | |
1116 | mc_match_geometries(new_pattern, matching_geometries, n + 1); | |
1117 | new_pattern[n] = 'O'; | |
1118 | mc_match_geometries(new_pattern, matching_geometries, n + 1); | |
1119 | new_pattern[n] = 'X'; | |
1120 | mc_match_geometries(new_pattern, matching_geometries, n + 1); | |
1121 | new_pattern[n] = '+'; | |
1122 | mc_match_geometries(new_pattern, matching_geometries, n + 1); | |
1123 | break; | |
1124 | } | |
1125 | } | |
1126 | } | |
1127 | ||
1128 | ||
1129 | /* Clear a subset of the property combinations determined by shift, | |
1130 | * mask, and value. | |
1131 | */ | |
1132 | static void | |
1133 | mc_clear_properties(int *properties, int shift, int mask, int value) | |
1134 | { | |
1135 | int k; | |
1136 | for (k = 0; k < NUM_PROPERTIES; k++) | |
1137 | if (((k >> shift) & mask) == value) | |
1138 | properties[k] = 0; | |
1139 | } | |
1140 | ||
1141 | ||
1142 | /* Find which property combinations are consistent with the rules | |
1143 | * given in buf. | |
1144 | */ | |
1145 | static void | |
1146 | mc_analyze_properties(char *buf, int *properties) | |
1147 | { | |
1148 | int k; | |
1149 | ||
1150 | /* First set all properties. */ | |
1151 | for (k = 0; k < NUM_PROPERTIES; k++) | |
1152 | properties[k] = 1; | |
1153 | ||
1154 | /* Then reset the ones which are inconsistent. */ | |
1155 | if (strstr(buf, "near")) | |
1156 | mc_clear_properties(properties, 0, 1, 0); | |
1157 | if (strstr(buf, "far")) | |
1158 | mc_clear_properties(properties, 0, 1, 1); | |
1159 | if (strstr(buf, "xcap0")) { | |
1160 | mc_clear_properties(properties, 1, 3, 1); | |
1161 | mc_clear_properties(properties, 1, 3, 2); | |
1162 | mc_clear_properties(properties, 1, 3, 3); | |
1163 | } | |
1164 | if (strstr(buf, "xcap1+")) | |
1165 | mc_clear_properties(properties, 1, 3, 0); | |
1166 | else if (strstr(buf, "xcap1-")) { | |
1167 | mc_clear_properties(properties, 1, 3, 2); | |
1168 | mc_clear_properties(properties, 1, 3, 3); | |
1169 | } | |
1170 | else if (strstr(buf, "xcap1")) { | |
1171 | mc_clear_properties(properties, 1, 3, 0); | |
1172 | mc_clear_properties(properties, 1, 3, 2); | |
1173 | mc_clear_properties(properties, 1, 3, 3); | |
1174 | } | |
1175 | if (strstr(buf, "xcap2+")) { | |
1176 | mc_clear_properties(properties, 1, 3, 0); | |
1177 | mc_clear_properties(properties, 1, 3, 1); | |
1178 | } | |
1179 | else if (strstr(buf, "xcap2-")) | |
1180 | mc_clear_properties(properties, 1, 3, 3); | |
1181 | else if (strstr(buf, "xcap2")) { | |
1182 | mc_clear_properties(properties, 1, 3, 0); | |
1183 | mc_clear_properties(properties, 1, 3, 1); | |
1184 | mc_clear_properties(properties, 1, 3, 3); | |
1185 | } | |
1186 | if (strstr(buf, "xcap3")) { | |
1187 | mc_clear_properties(properties, 1, 3, 0); | |
1188 | mc_clear_properties(properties, 1, 3, 1); | |
1189 | mc_clear_properties(properties, 1, 3, 2); | |
1190 | } | |
1191 | if (strstr(buf, "ocap0")) { | |
1192 | mc_clear_properties(properties, 3, 3, 1); | |
1193 | mc_clear_properties(properties, 3, 3, 2); | |
1194 | mc_clear_properties(properties, 3, 3, 3); | |
1195 | } | |
1196 | if (strstr(buf, "ocap1+")) | |
1197 | mc_clear_properties(properties, 3, 3, 0); | |
1198 | else if (strstr(buf, "ocap1-")) { | |
1199 | mc_clear_properties(properties, 3, 3, 2); | |
1200 | mc_clear_properties(properties, 3, 3, 3); | |
1201 | } | |
1202 | else if (strstr(buf, "ocap1")) { | |
1203 | mc_clear_properties(properties, 3, 3, 0); | |
1204 | mc_clear_properties(properties, 3, 3, 2); | |
1205 | mc_clear_properties(properties, 3, 3, 3); | |
1206 | } | |
1207 | if (strstr(buf, "ocap2+")) { | |
1208 | mc_clear_properties(properties, 3, 3, 0); | |
1209 | mc_clear_properties(properties, 3, 3, 1); | |
1210 | } | |
1211 | else if (strstr(buf, "ocap2-")) | |
1212 | mc_clear_properties(properties, 3, 3, 3); | |
1213 | else if (strstr(buf, "ocap2")) { | |
1214 | mc_clear_properties(properties, 3, 3, 0); | |
1215 | mc_clear_properties(properties, 3, 3, 1); | |
1216 | mc_clear_properties(properties, 3, 3, 3); | |
1217 | } | |
1218 | if (strstr(buf, "ocap3")) { | |
1219 | mc_clear_properties(properties, 3, 3, 0); | |
1220 | mc_clear_properties(properties, 3, 3, 1); | |
1221 | mc_clear_properties(properties, 3, 3, 2); | |
1222 | } | |
1223 | if (strstr(buf, "xsafe")) | |
1224 | mc_clear_properties(properties, 5, 1, 1); | |
1225 | if (strstr(buf, "xunsafe")) | |
1226 | mc_clear_properties(properties, 5, 1, 0); | |
1227 | if (strstr(buf, "osafe")) | |
1228 | mc_clear_properties(properties, 6, 1, 1); | |
1229 | if (strstr(buf, "ounsafe")) | |
1230 | mc_clear_properties(properties, 6, 1, 0); | |
1231 | if (strstr(buf, "xsuicide")) | |
1232 | mc_clear_properties(properties, 7, 1, 0); | |
1233 | if (strstr(buf, "xnosuicide")) | |
1234 | mc_clear_properties(properties, 7, 1, 1); | |
1235 | } | |
1236 | ||
1237 | ||
1238 | /* Export the size of the array mc_patterns.values so that external | |
1239 | * callers of mc_load_patterns_from_db() know how big arrays to | |
1240 | * allocate. | |
1241 | */ | |
1242 | int | |
1243 | mc_get_size_of_pattern_values_table(void) | |
1244 | { | |
1245 | return (NUM_GEOMETRIES + 1) * NUM_PROPERTIES; | |
1246 | } | |
1247 | ||
1248 | ||
1249 | /* Load Monte Carlo patterns from file in .db format. If values is | |
1250 | * NULL, load directly into mc_patterns.values. | |
1251 | */ | |
1252 | int | |
1253 | mc_load_patterns_from_db(const char *filename, unsigned int *values) | |
1254 | { | |
1255 | FILE *pattern_file; | |
1256 | char buf[80]; | |
1257 | unsigned int value; | |
1258 | int pattern_line = 0; | |
1259 | int current_pattern[8]; | |
1260 | int patterns_expanded = 0; | |
1261 | int *matching_geometries; | |
1262 | int properties[NUM_PROPERTIES]; | |
1263 | int k; | |
1264 | int m; | |
1265 | ||
1266 | if (!values) | |
1267 | values = mc_patterns.values; | |
1268 | ||
1269 | mc_init_pattern_geometries(); | |
1270 | ||
1271 | pattern_file = fopen(filename, "r"); | |
1272 | if (!pattern_file) { | |
1273 | gprintf("Failed to open %s file.\n", filename); | |
1274 | return 0; | |
1275 | } | |
1276 | ||
1277 | matching_geometries = malloc((NUM_GEOMETRIES + 1) | |
1278 | * sizeof(*matching_geometries)); | |
1279 | ||
1280 | /* Set unloaded patterns to a "-1" value. */ | |
1281 | for (k = 1; k <= NUM_GEOMETRIES; k++) | |
1282 | for (m = 0; m < NUM_PROPERTIES; m++) | |
1283 | values[k * NUM_PROPERTIES + m] = 0xffffffffU; | |
1284 | ||
1285 | /* Loop over the rows of the pattern database. */ | |
1286 | while (fgets(buf, 80, pattern_file)) { | |
1287 | if (strchr(".xXoO|+-?%", buf[0])) { | |
1288 | /* Pattern line found */ | |
1289 | patterns_expanded = 0; | |
1290 | if (pattern_line == 0) { | |
1291 | current_pattern[5] = buf[0]; | |
1292 | current_pattern[2] = buf[1]; | |
1293 | current_pattern[6] = buf[2]; | |
1294 | } | |
1295 | else if (pattern_line == 1) { | |
1296 | current_pattern[1] = buf[0]; | |
1297 | current_pattern[3] = buf[2]; | |
1298 | } | |
1299 | else if (pattern_line == 2) { | |
1300 | current_pattern[4] = buf[0]; | |
1301 | current_pattern[0] = buf[1]; | |
1302 | current_pattern[7] = buf[2]; | |
1303 | } | |
1304 | pattern_line++; | |
1305 | } | |
1306 | else if (sscanf(buf, ":%u", &value) == 1) { | |
1307 | /* Colon line found. */ | |
1308 | if (value > 10000000) | |
1309 | fprintf(stderr, "Warning: pattern values should be at most 10000000."); | |
1310 | ||
1311 | if (!patterns_expanded) { | |
1312 | /* Find the set of rotation invariant geometries matching the | |
1313 | * pattern. | |
1314 | */ | |
1315 | memset(matching_geometries, 0, | |
1316 | (NUM_GEOMETRIES + 1) * sizeof(*matching_geometries)); | |
1317 | mc_match_geometries(current_pattern, matching_geometries, 0); | |
1318 | patterns_expanded = 1; | |
1319 | } | |
1320 | ||
1321 | /* Find the set of matching property values. */ | |
1322 | mc_analyze_properties(buf, properties); | |
1323 | ||
1324 | /* Set the value for the combinations of matched geometries and | |
1325 | * properties, except those which have already been matched by a | |
1326 | * previous pattern. | |
1327 | */ | |
1328 | for (k = 1; k <= NUM_GEOMETRIES; k++) | |
1329 | if (matching_geometries[k]) | |
1330 | for (m = 0; m < NUM_PROPERTIES; m++) | |
1331 | if (properties[m] && values[k * NUM_PROPERTIES + m] == 0xffffffffU) | |
1332 | values[k * NUM_PROPERTIES + m] = value; | |
1333 | ||
1334 | pattern_line = 0; | |
1335 | } | |
1336 | } | |
1337 | ||
1338 | fclose(pattern_file); | |
1339 | ||
1340 | /* Set unmatched patterns/properties to a value of 1. */ | |
1341 | for (k = 1; k <= NUM_GEOMETRIES; k++) | |
1342 | for (m = 0; m < NUM_PROPERTIES; m++) | |
1343 | if (values[k * NUM_PROPERTIES + m] == 0xffffffffU) | |
1344 | values[k * NUM_PROPERTIES + m] = 1; | |
1345 | ||
1346 | free(matching_geometries); | |
1347 | return 1; | |
1348 | } | |
1349 | ||
1350 | ||
1351 | /* Set up local pattern values. */ | |
1352 | void | |
1353 | mc_init_patterns(const unsigned int *values) | |
1354 | { | |
1355 | mc_init_pattern_geometries(); | |
1356 | memcpy(mc_patterns.values, values, sizeof(mc_patterns.values)); | |
1357 | } | |
1358 | ||
1359 | ||
1360 | /* Initialize the data structures used to keep track of the local | |
1361 | * pattern values. | |
1362 | */ | |
1363 | static void | |
1364 | mc_init_move_values(struct mc_board *mc) | |
1365 | { | |
1366 | int pos; | |
1367 | int k; | |
1368 | ||
1369 | memset(mc->move_values_white, 0, sizeof(mc->move_values_white)); | |
1370 | memset(mc->move_values_black, 0, sizeof(mc->move_values_black)); | |
1371 | memset(mc->partitioned_move_value_sums_white, 0, | |
1372 | sizeof(mc->partitioned_move_value_sums_white)); | |
1373 | memset(mc->partitioned_move_value_sums_black, 0, | |
1374 | sizeof(mc->partitioned_move_value_sums_black)); | |
1375 | memset(mc->move_partition_lists_white, 0, | |
1376 | sizeof(mc->move_partition_lists_white)); | |
1377 | memset(mc->move_partition_lists_black, 0, | |
1378 | sizeof(mc->move_partition_lists_black)); | |
1379 | ||
1380 | mc->move_value_sum_white = 0.0; | |
1381 | mc->move_value_sum_black = 0.0; | |
1382 | ||
1383 | for (k = 0; k < NUM_MOVE_PARTITIONS; k++) { | |
1384 | mc->move_partition_lists_white[k] = 1; | |
1385 | mc->move_partition_lists_black[k] = 1; | |
1386 | } | |
1387 | ||
1388 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
1389 | if (mc->board[pos] == EMPTY) { | |
1390 | int partition = pos & (NUM_MOVE_PARTITIONS - 1); | |
1391 | if (!mc_is_suicide(mc, pos, WHITE)) { | |
1392 | int pattern = mc_find_pattern_number(mc, pos, WHITE, 0); | |
1393 | unsigned int value = mc_patterns.values[pattern]; | |
1394 | mc->move_values_white[pos] = value; | |
1395 | mc->partitioned_move_value_sums_white[partition] += value; | |
1396 | mc->move_value_sum_white += value; | |
1397 | mc->move_partition_lists_white[pos] = mc->move_partition_lists_white[partition]; | |
1398 | mc->move_partition_lists_white[partition] = pos; | |
1399 | } | |
1400 | if (!mc_is_suicide(mc, pos, BLACK)) { | |
1401 | int pattern = mc_find_pattern_number(mc, pos, BLACK, 0); | |
1402 | unsigned int value = mc_patterns.values[pattern]; | |
1403 | mc->move_values_black[pos] = value; | |
1404 | mc->partitioned_move_value_sums_black[partition] += value; | |
1405 | mc->move_value_sum_black += value; | |
1406 | mc->move_partition_lists_black[pos] = mc->move_partition_lists_black[partition]; | |
1407 | mc->move_partition_lists_black[partition] = pos; | |
1408 | } | |
1409 | } | |
1410 | } | |
1411 | } | |
1412 | ||
1413 | ||
1414 | /* Add a move at a vertex which was previously not a legal move. */ | |
1415 | static void | |
1416 | mc_add_move(struct mc_board *mc, int pos, int color, int partition, | |
1417 | unsigned int *move_values, int *partition_lists, | |
1418 | unsigned int *partition_sums, unsigned int *move_value_sum) | |
1419 | { | |
1420 | int pattern = mc_find_pattern_number(mc, pos, color, 0); | |
1421 | unsigned int value = mc_patterns.values[pattern]; | |
1422 | partition_lists[pos] = partition_lists[partition]; | |
1423 | partition_lists[partition] = pos; | |
1424 | move_values[pos] = value; | |
1425 | partition_sums[partition] += value; | |
1426 | *move_value_sum += value; | |
1427 | } | |
1428 | ||
1429 | ||
1430 | /* Update a move value. */ | |
1431 | static void | |
1432 | mc_update_move(struct mc_board *mc, int pos, int color, int partition, | |
1433 | unsigned int *move_values, unsigned int *partition_sums, | |
1434 | unsigned int *move_value_sum) | |
1435 | { | |
1436 | int pattern = mc_find_pattern_number(mc, pos, color, 0); | |
1437 | unsigned int value = mc_patterns.values[pattern]; | |
1438 | partition_sums[partition] += value - move_values[pos]; | |
1439 | *move_value_sum += value - move_values[pos]; | |
1440 | move_values[pos] = value; | |
1441 | } | |
1442 | ||
1443 | ||
1444 | /* Remove a move because it has been played or has become suicide. */ | |
1445 | static void | |
1446 | mc_remove_move(int pos, int partition, unsigned int *move_values, | |
1447 | int *partition_lists, unsigned int *partition_sums, | |
1448 | unsigned int *move_value_sum) | |
1449 | { | |
1450 | int pos2; | |
1451 | int pos3; | |
1452 | for (pos2 = partition; partition_lists[pos2] != 1; pos2 = partition_lists[pos2]) { | |
1453 | if (partition_lists[pos2] == pos) | |
1454 | break; | |
1455 | } | |
1456 | pos3 = partition_lists[pos2]; | |
1457 | partition_lists[pos2] = partition_lists[pos3]; | |
1458 | partition_lists[pos3] = 0; | |
1459 | partition_sums[partition] -= move_values[pos]; | |
1460 | *move_value_sum -= move_values[pos]; | |
1461 | move_values[pos] = 0.0; | |
1462 | } | |
1463 | ||
1464 | ||
1465 | /* Update move values for the moves listed in the update queue. */ | |
1466 | static void | |
1467 | mc_update_move_values(struct mc_board *mc) | |
1468 | { | |
1469 | int pos; | |
1470 | int partition; | |
1471 | for (pos = mc->queue[0]; pos != 1; pos = mc->queue[pos]) { | |
1472 | partition = pos & (NUM_MOVE_PARTITIONS - 1); | |
1473 | if ((mc->board[pos] != EMPTY || mc_is_suicide(mc, pos, WHITE))) { | |
1474 | if (mc->move_partition_lists_white[pos] != 0) { | |
1475 | mc_remove_move(pos, partition, mc->move_values_white, | |
1476 | mc->move_partition_lists_white, | |
1477 | mc->partitioned_move_value_sums_white, | |
1478 | &mc->move_value_sum_white); | |
1479 | } | |
1480 | } | |
1481 | else { | |
1482 | if (mc->move_partition_lists_white[pos] == 0) | |
1483 | mc_add_move(mc, pos, WHITE, partition, mc->move_values_white, | |
1484 | mc->move_partition_lists_white, | |
1485 | mc->partitioned_move_value_sums_white, | |
1486 | &mc->move_value_sum_white); | |
1487 | else | |
1488 | mc_update_move(mc, pos, WHITE, partition, mc->move_values_white, | |
1489 | mc->partitioned_move_value_sums_white, | |
1490 | &mc->move_value_sum_white); | |
1491 | } | |
1492 | ||
1493 | if ((mc->board[pos] != EMPTY || mc_is_suicide(mc, pos, BLACK))) { | |
1494 | if (mc->move_partition_lists_black[pos] != 0) { | |
1495 | mc_remove_move(pos, partition, mc->move_values_black, | |
1496 | mc->move_partition_lists_black, | |
1497 | mc->partitioned_move_value_sums_black, | |
1498 | &mc->move_value_sum_black); | |
1499 | } | |
1500 | } | |
1501 | else { | |
1502 | if (mc->move_partition_lists_black[pos] == 0) | |
1503 | mc_add_move(mc, pos, BLACK, partition, mc->move_values_black, | |
1504 | mc->move_partition_lists_black, | |
1505 | mc->partitioned_move_value_sums_black, | |
1506 | &mc->move_value_sum_black); | |
1507 | else | |
1508 | mc_update_move(mc, pos, BLACK, partition, mc->move_values_black, | |
1509 | mc->partitioned_move_value_sums_black, | |
1510 | &mc->move_value_sum_black); | |
1511 | } | |
1512 | } | |
1513 | } | |
1514 | ||
1515 | ||
1516 | /***************************************************/ | |
1517 | ||
1518 | #define ASSERT_LEGAL 1 | |
1519 | ||
1520 | struct mc_game { | |
1521 | struct mc_board mc; | |
1522 | int move_history[600]; | |
1523 | unsigned char settled[BOARDMAX]; | |
1524 | int color_to_move; | |
1525 | int last_move; | |
1526 | int consecutive_passes; | |
1527 | int consecutive_ko_captures; | |
1528 | int depth; | |
1529 | }; | |
1530 | ||
1531 | ||
1532 | /* Generate a random move. */ | |
1533 | static int | |
1534 | mc_generate_random_move(struct mc_game *game) | |
1535 | { | |
1536 | struct mc_board *mc = &game->mc; | |
1537 | int last_move = game->last_move; | |
1538 | int color = game->color_to_move; | |
1539 | int depth = game->depth; | |
1540 | ||
1541 | int pos; | |
1542 | ||
1543 | int near_moves[BOARDMAX]; | |
1544 | unsigned int saved_near_move_values[BOARDMAX]; | |
1545 | int num_near_moves; | |
1546 | unsigned int *move_values; | |
1547 | unsigned int *partition_sums; | |
1548 | int *partition_lists; | |
1549 | unsigned int *move_value_sum; | |
1550 | unsigned int saved_ko_value = 0; | |
1551 | int partition; | |
1552 | int move; | |
1553 | int k; | |
1554 | int x; | |
1555 | ||
1556 | /* If we get this deep we are almost certainly playing triple ko | |
1557 | * without alternative options, so just give up and score as is. | |
1558 | * | |
1559 | * FIXME: Handle this in some proper way. | |
1560 | */ | |
1561 | if (depth > 600) { | |
1562 | if (mc_debug) { | |
1563 | int pos; | |
1564 | fprintf(stderr, "Reached 600 iterations.\n"); | |
1565 | mc_showboard(mc, stderr); | |
1566 | for (k = 0; k < game->depth; k++) | |
1567 | gprintf("%1m ", game->move_history[k]); | |
1568 | gprintf("\n"); | |
1569 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) | |
1570 | if (mc->board[pos] == EMPTY) { | |
1571 | gprintf("%1m ", pos); | |
1572 | fprintf(stderr, "white %7d black %7d white near %7d black near %7d\n", | |
1573 | (int) mc->move_values_white[pos], | |
1574 | (int) mc->move_values_black[pos], | |
1575 | mc_patterns.values[mc_find_pattern_number(mc, pos, WHITE, 1)], | |
1576 | mc_patterns.values[mc_find_pattern_number(mc, pos, BLACK, 1)]); | |
1577 | } | |
1578 | } | |
1579 | return PASS_MOVE; | |
1580 | } | |
1581 | ||
1582 | if (color == WHITE) { | |
1583 | move_values = mc->move_values_white; | |
1584 | partition_sums = mc->partitioned_move_value_sums_white; | |
1585 | partition_lists = mc->move_partition_lists_white; | |
1586 | move_value_sum = &mc->move_value_sum_white; | |
1587 | } | |
1588 | else { | |
1589 | move_values = mc->move_values_black; | |
1590 | partition_sums = mc->partitioned_move_value_sums_black; | |
1591 | partition_lists = mc->move_partition_lists_black; | |
1592 | move_value_sum = &mc->move_value_sum_black; | |
1593 | } | |
1594 | ||
1595 | /* Temporarily update pattern values for NEAR moves. We define | |
1596 | * NEAR moves as those which had their values updated during the | |
1597 | * previous mc_play_move() call and can be found by traversing the | |
1598 | * update queue. | |
1599 | */ | |
1600 | num_near_moves = 0; | |
1601 | if (last_move != PASS_MOVE) { | |
1602 | for (pos = mc->queue[0]; pos != 1; pos = mc->queue[pos]) { | |
1603 | if (mc->board[pos] == EMPTY && partition_lists[pos] != 0) { | |
1604 | unsigned int old_value = move_values[pos]; | |
1605 | int pattern = mc_find_pattern_number(mc, pos, color, 1); | |
1606 | unsigned int new_value = mc_patterns.values[pattern]; | |
1607 | partition = pos & (NUM_MOVE_PARTITIONS - 1); | |
1608 | saved_near_move_values[num_near_moves] = old_value; | |
1609 | near_moves[num_near_moves++] = pos; | |
1610 | move_values[pos] = new_value; | |
1611 | partition_sums[partition] += new_value - old_value; | |
1612 | *move_value_sum += new_value - old_value; | |
1613 | } | |
1614 | } | |
1615 | } | |
1616 | ||
1617 | /* Temporarily clear the move value of an illegal ko capture. */ | |
1618 | if (mc->board_ko_pos != NO_MOVE) { | |
1619 | if (mc->board[WEST(mc->board_ko_pos)] == OTHER_COLOR(color) | |
1620 | || mc->board[EAST(mc->board_ko_pos)] == OTHER_COLOR(color)) { | |
1621 | partition = mc->board_ko_pos & (NUM_MOVE_PARTITIONS - 1); | |
1622 | saved_ko_value = move_values[mc->board_ko_pos]; | |
1623 | move_values[mc->board_ko_pos] = 0; | |
1624 | partition_sums[partition] -= saved_ko_value; | |
1625 | *move_value_sum -= saved_ko_value; | |
1626 | } | |
1627 | } | |
1628 | ||
1629 | /* Sample a move randomly according to the distribution given by | |
1630 | * the move values. | |
1631 | */ | |
1632 | if (*move_value_sum == 0) | |
1633 | move = PASS_MOVE; | |
1634 | else { | |
1635 | /* First choose a partition. */ | |
1636 | x = (int) (gg_drand() * *move_value_sum); | |
1637 | for (k = 0; k < NUM_MOVE_PARTITIONS; k++) { | |
1638 | x -= partition_sums[k]; | |
1639 | if (x < 0) | |
1640 | break; | |
1641 | } | |
1642 | ||
1643 | /* Then choose a move in that partition. */ | |
1644 | x = (unsigned int) (gg_drand() * partition_sums[k]); | |
1645 | for (pos = partition_lists[k]; pos != 1; pos = partition_lists[pos]) { | |
1646 | x -= move_values[pos]; | |
1647 | if (x < 0) | |
1648 | break; | |
1649 | } | |
1650 | ||
1651 | move = pos; | |
1652 | #if !TURN_OFF_ASSERTIONS | |
1653 | ASSERT1(move == PASS_MOVE || move_values[move] > 0, move); | |
1654 | ASSERT1(move == PASS_MOVE || mc->board[move] == EMPTY, move); | |
1655 | ASSERT1(mc_is_legal(mc, move, color), move); | |
1656 | #endif | |
1657 | } | |
1658 | ||
1659 | /* Reset the value of an illegal ko capture. */ | |
1660 | if (saved_ko_value > 0) { | |
1661 | partition = mc->board_ko_pos & (NUM_MOVE_PARTITIONS - 1); | |
1662 | partition_sums[partition] += saved_ko_value - move_values[mc->board_ko_pos]; | |
1663 | *move_value_sum += saved_ko_value - move_values[mc->board_ko_pos]; | |
1664 | move_values[mc->board_ko_pos] = saved_ko_value; | |
1665 | } | |
1666 | ||
1667 | /* Reset move values for NEAR moves. */ | |
1668 | for (k = 0; k < num_near_moves; k++) { | |
1669 | unsigned int old_value; | |
1670 | unsigned int new_value; | |
1671 | pos = near_moves[k]; | |
1672 | partition = pos & (NUM_MOVE_PARTITIONS - 1); | |
1673 | old_value = move_values[pos]; | |
1674 | new_value = saved_near_move_values[k]; | |
1675 | move_values[pos] = new_value; | |
1676 | partition_sums[partition] += new_value - old_value; | |
1677 | *move_value_sum += new_value - old_value; | |
1678 | } | |
1679 | ||
1680 | return move; | |
1681 | } | |
1682 | ||
1683 | ||
1684 | static int mc_play_random_move(struct mc_game *game, int move) | |
1685 | { | |
1686 | int result = mc_play_move(&game->mc, move, game->color_to_move); | |
1687 | mc_update_move_values(&game->mc); | |
1688 | ||
1689 | if (result) { | |
1690 | if (is_pass(move)) | |
1691 | game->consecutive_passes++; | |
1692 | else { | |
1693 | game->consecutive_passes = 0; | |
1694 | } | |
1695 | ||
1696 | if (game->mc.board_ko_pos != NO_MOVE) | |
1697 | game->consecutive_ko_captures++; | |
1698 | else | |
1699 | game->consecutive_ko_captures = 0; | |
1700 | ||
1701 | game->move_history[game->depth] = move; | |
1702 | game->last_move = move; | |
1703 | game->color_to_move = OTHER_COLOR(game->color_to_move); | |
1704 | game->depth++; | |
1705 | } | |
1706 | ||
1707 | return result; | |
1708 | } | |
1709 | ||
1710 | static int mc_play_random_game(struct mc_game *game) | |
1711 | { | |
1712 | struct mc_board *mc = &game->mc; | |
1713 | ||
1714 | int score = 0; | |
1715 | int pos; | |
1716 | int k; | |
1717 | int result; | |
1718 | int move; | |
1719 | ||
1720 | /* First finish the game, if it isn't already. */ | |
1721 | while (game->consecutive_passes < 3) { | |
1722 | move = mc_generate_random_move(game); | |
1723 | result = mc_play_random_move(game, move); | |
1724 | ASSERT1(result, move); | |
1725 | } | |
1726 | ||
1727 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) | |
1728 | if (MC_ON_BOARD(pos)) { | |
1729 | if (game->settled[pos] == WHITE) | |
1730 | score++; | |
1731 | else if (game->settled[pos] == BLACK) | |
1732 | score--; | |
1733 | else { | |
1734 | int pos2 = pos; | |
1735 | if (mc->board[pos] == EMPTY) | |
1736 | for (k = 0; k < 4; k++) { | |
1737 | pos2 = pos + delta[k]; | |
1738 | if (IS_STONE(mc->board[pos2])) | |
1739 | break; | |
1740 | } | |
1741 | ||
1742 | score += 2 * (mc->board[pos2] == WHITE) - 1; | |
1743 | } | |
1744 | } | |
1745 | ||
1746 | return score; | |
1747 | } | |
1748 | ||
1749 | /******************* UCT search ***********************/ | |
1750 | ||
1751 | #define UCT_MAX_SEARCH_DEPTH BOARDMAX | |
1752 | ||
1753 | struct bitboard { | |
1754 | /* FIXME: Do this properly. */ | |
1755 | unsigned int bits[1 + BOARDMAX / 32]; | |
1756 | }; | |
1757 | ||
1758 | struct uct_arc { | |
1759 | int move; | |
1760 | struct uct_node *node; | |
1761 | struct uct_arc *next; | |
1762 | }; | |
1763 | ||
1764 | struct uct_node { | |
1765 | int wins; | |
1766 | int games; | |
1767 | float sum_scores; | |
1768 | float sum_scores2; | |
1769 | struct uct_arc *child; | |
1770 | struct bitboard untested; | |
1771 | Hash_data boardhash; | |
1772 | }; | |
1773 | ||
1774 | struct uct_tree { | |
1775 | struct uct_node *nodes; | |
1776 | struct uct_arc *arcs; | |
1777 | unsigned int *hashtable_odd; | |
1778 | unsigned int *hashtable_even; | |
1779 | unsigned int hashtable_size; | |
1780 | int num_nodes; | |
1781 | int num_used_nodes; | |
1782 | int num_arcs; | |
1783 | int num_used_arcs; | |
1784 | int *forbidden_moves; | |
1785 | struct mc_game game; | |
1786 | int move_score[BOARDSIZE]; | |
1787 | int move_ordering[BOARDSIZE]; | |
1788 | int inverse_move_ordering[BOARDSIZE]; | |
1789 | int num_ordered_moves; | |
1790 | }; | |
1791 | ||
1792 | ||
1793 | static struct uct_node * | |
1794 | uct_init_node(struct uct_tree *tree, int *allowed_moves) | |
1795 | { | |
1796 | int pos; | |
1797 | struct uct_node *node = &tree->nodes[tree->num_used_nodes++]; | |
1798 | ||
1799 | node->wins = 0; | |
1800 | node->games = 0; | |
1801 | node->sum_scores = 0.0; | |
1802 | node->sum_scores2 = 0.0; | |
1803 | node->child = NULL; | |
1804 | memset(node->untested.bits, 0, sizeof(node->untested.bits)); | |
1805 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
1806 | if (tree->game.mc.board[pos] == EMPTY | |
1807 | && !tree->forbidden_moves[pos] | |
1808 | && (!allowed_moves || allowed_moves[pos])) { | |
1809 | node->untested.bits[pos / 32] |= 1 << pos % 32; | |
1810 | } | |
1811 | } | |
1812 | node->boardhash = tree->game.mc.hash; | |
1813 | ||
1814 | return node; | |
1815 | } | |
1816 | ||
1817 | static struct uct_node * | |
1818 | uct_find_node(struct uct_tree *tree, struct uct_node *parent, int move) | |
1819 | { | |
1820 | struct uct_node *node = NULL; | |
1821 | Hash_data *boardhash = &tree->game.mc.hash; | |
1822 | unsigned int hash_index = hashdata_remainder(*boardhash, | |
1823 | tree->hashtable_size); | |
1824 | unsigned int *hashtable = tree->hashtable_even; | |
1825 | if (tree->game.depth & 1) | |
1826 | hashtable = tree->hashtable_odd; | |
1827 | ||
1828 | while (hashtable[hash_index] != 0) { | |
1829 | int node_index = hashtable[hash_index]; | |
1830 | gg_assert(node_index > 0 && node_index < tree->num_nodes); | |
1831 | if (hashdata_is_equal(tree->nodes[node_index].boardhash, *boardhash)) { | |
1832 | node = &tree->nodes[node_index]; | |
1833 | break; | |
1834 | } | |
1835 | hash_index++; | |
1836 | if (hash_index >= tree->hashtable_size) | |
1837 | hash_index = 0; | |
1838 | } | |
1839 | ||
1840 | if (!node) { | |
1841 | node = uct_init_node(tree, NULL); | |
1842 | gg_assert(hash_index < tree->hashtable_size); | |
1843 | hashtable[hash_index] = node - tree->nodes; | |
1844 | } | |
1845 | ||
1846 | /* Add the node as the first of the siblings. */ | |
1847 | if (parent) { | |
1848 | struct uct_arc *arc = &tree->arcs[tree->num_used_arcs++]; | |
1849 | gg_assert(tree->num_used_arcs < tree->num_arcs); | |
1850 | arc->move = move; | |
1851 | arc->node = node; | |
1852 | if (parent->child) | |
1853 | arc->next = parent->child; | |
1854 | else | |
1855 | arc->next = NULL; | |
1856 | parent->child = arc; | |
1857 | } | |
1858 | ||
1859 | return node; | |
1860 | } | |
1861 | ||
1862 | ||
1863 | static void | |
1864 | uct_update_move_ordering(struct uct_tree *tree, int move) | |
1865 | { | |
1866 | int score = ++tree->move_score[move]; | |
1867 | while (1) { | |
1868 | int n = tree->inverse_move_ordering[move]; | |
1869 | int preceding_move; | |
1870 | if (n == 0) | |
1871 | return; | |
1872 | preceding_move = tree->move_ordering[n - 1]; | |
1873 | if (tree->move_score[preceding_move] >= score) | |
1874 | return; | |
1875 | ||
1876 | /* Swap move ordering. */ | |
1877 | tree->move_ordering[n - 1] = move; | |
1878 | tree->move_ordering[n] = preceding_move; | |
1879 | tree->inverse_move_ordering[move] = n - 1; | |
1880 | tree->inverse_move_ordering[preceding_move] = n; | |
1881 | } | |
1882 | } | |
1883 | ||
1884 | ||
1885 | static void | |
1886 | uct_init_move_ordering(struct uct_tree *tree) | |
1887 | { | |
1888 | int pos; | |
1889 | int k = 0; | |
1890 | /* FIXME: Exclude forbidden moves. */ | |
1891 | memset(tree->move_score, 0, sizeof(tree->move_score)); | |
1892 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) | |
1893 | if (ON_BOARD(pos)) { | |
1894 | tree->move_ordering[k] = pos; | |
1895 | tree->inverse_move_ordering[pos] = k; | |
1896 | k++; | |
1897 | } | |
1898 | ||
1899 | tree->num_ordered_moves = k; | |
1900 | ||
1901 | /* FIXME: Quick and dirty experiment. */ | |
1902 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) { | |
1903 | if (ON_BOARD(pos)) { | |
1904 | tree->move_score[pos] = (int) (10 * potential_moves[pos]) - 1; | |
1905 | uct_update_move_ordering(tree, pos); | |
1906 | } | |
1907 | } | |
1908 | } | |
1909 | ||
1910 | ||
1911 | static float | |
1912 | uct_finish_and_score_game(struct mc_game *game) | |
1913 | { | |
1914 | return komi + mc_play_random_game(game); | |
1915 | } | |
1916 | ||
1917 | static struct uct_node * | |
1918 | uct_play_move(struct uct_tree *tree, struct uct_node *node, float alpha, | |
1919 | float *gamma, int *move) | |
1920 | { | |
1921 | struct uct_arc *child_arc; | |
1922 | int pos; | |
1923 | struct uct_arc *next_arc = NULL; | |
1924 | struct uct_arc *best_winrate_arc = NULL; | |
1925 | float best_uct_value = 0.0; | |
1926 | float best_winrate = 0.0; | |
1927 | ||
1928 | for (child_arc = node->child; child_arc; child_arc = child_arc->next) { | |
1929 | struct uct_node *child_node = child_arc->node; | |
1930 | float winrate = (float) child_node->wins / child_node->games; | |
1931 | float uct_value; | |
1932 | float log_games_ratio = log(node->games) / child_node->games; | |
1933 | float x = winrate * (1.0 - winrate) + sqrt(2.0 * log_games_ratio); | |
1934 | if (x < 0.25) | |
1935 | x = 0.25; | |
1936 | uct_value = winrate + sqrt(2 * log_games_ratio * x / (1 + tree->game.depth)); | |
1937 | if (uct_value > best_uct_value) { | |
1938 | next_arc = child_arc; | |
1939 | best_uct_value = uct_value; | |
1940 | } | |
1941 | ||
1942 | if (winrate > best_winrate) { | |
1943 | best_winrate_arc = child_arc; | |
1944 | best_winrate = winrate; | |
1945 | } | |
1946 | } | |
1947 | ||
1948 | *gamma = best_winrate; | |
1949 | if (best_winrate > alpha) | |
1950 | next_arc = best_winrate_arc; | |
1951 | else { | |
1952 | /* First play a random previously unplayed move, if any. */ | |
1953 | int k; | |
1954 | for (k = -1; k < tree->num_ordered_moves; k++) { | |
1955 | if (k == -1 && best_uct_value > 0.0) | |
1956 | continue; | |
1957 | else if (k == -1) | |
1958 | pos = mc_generate_random_move(&tree->game); | |
1959 | else | |
1960 | pos = tree->move_ordering[k]; | |
1961 | ||
1962 | if (node->untested.bits[pos / 32] & (1 << (pos % 32))) { | |
1963 | int r; | |
1964 | int proper_small_eye = 1; | |
1965 | struct mc_board *mc = &tree->game.mc; | |
1966 | *move = pos; | |
1967 | node->untested.bits[*move / 32] &= ~(1 << *move % 32); | |
1968 | ||
1969 | for (r = 0; r < 4; r++) { | |
1970 | if (mc->board[pos + delta[r]] == EMPTY | |
1971 | || mc->board[pos + delta[r]] == OTHER_COLOR(tree->game.color_to_move)) { | |
1972 | proper_small_eye = 0; | |
1973 | break; | |
1974 | } | |
1975 | } | |
1976 | ||
1977 | if (proper_small_eye) { | |
1978 | int diagonal_value = 0; | |
1979 | for (r = 4; r < 8; r++) { | |
1980 | int pos2 = pos + delta[r]; | |
1981 | if (!MC_ON_BOARD(pos2)) | |
1982 | diagonal_value++; | |
1983 | else if (mc->board[pos2] == OTHER_COLOR(tree->game.color_to_move)) | |
1984 | diagonal_value += 2; | |
1985 | } | |
1986 | if (diagonal_value > 3) | |
1987 | proper_small_eye = 0; | |
1988 | } | |
1989 | ||
1990 | if (!proper_small_eye && mc_play_random_move(&tree->game, *move)) | |
1991 | return uct_find_node(tree, node, *move); | |
1992 | } | |
1993 | } | |
1994 | } | |
1995 | ||
1996 | if (!next_arc) { | |
1997 | mc_play_random_move(&tree->game, PASS_MOVE); | |
1998 | *move = PASS_MOVE; | |
1999 | return uct_find_node(tree, node, PASS_MOVE); | |
2000 | } | |
2001 | ||
2002 | *move = next_arc->move; | |
2003 | mc_play_random_move(&tree->game, next_arc->move); | |
2004 | ||
2005 | return next_arc->node; | |
2006 | } | |
2007 | ||
2008 | static float | |
2009 | uct_traverse_tree(struct uct_tree *tree, struct uct_node *node, | |
2010 | float alpha, float beta) | |
2011 | { | |
2012 | int color = tree->game.color_to_move; | |
2013 | int num_passes = tree->game.consecutive_passes; | |
2014 | float result; | |
2015 | float gamma; | |
2016 | int move = PASS_MOVE; | |
2017 | ||
2018 | /* FIXME: Unify these. */ | |
2019 | if (num_passes == 3 || tree->game.depth >= UCT_MAX_SEARCH_DEPTH | |
2020 | || (node->games == 0 && node != tree->nodes)) | |
2021 | result = uct_finish_and_score_game(&tree->game); | |
2022 | else { | |
2023 | struct uct_node *next_node; | |
2024 | next_node = uct_play_move(tree, node, alpha, &gamma, &move); | |
2025 | ||
2026 | gamma += 0.00; | |
2027 | if (gamma > 0.8) | |
2028 | gamma = 0.8; | |
2029 | result = uct_traverse_tree(tree, next_node, beta, gamma); | |
2030 | } | |
2031 | ||
2032 | node->games++; | |
2033 | if ((result > 0) ^ (color == WHITE)) { | |
2034 | node->wins++; | |
2035 | if (move != PASS_MOVE) | |
2036 | uct_update_move_ordering(tree, move); | |
2037 | } | |
2038 | ||
2039 | node->sum_scores += result; | |
2040 | node->sum_scores2 += result * result; | |
2041 | ||
2042 | return result; | |
2043 | } | |
2044 | ||
2045 | static int | |
2046 | uct_find_best_children(struct uct_node *node, struct uct_arc **children, | |
2047 | int n) | |
2048 | { | |
2049 | struct uct_arc *child_arc; | |
2050 | float best_score; | |
2051 | struct uct_arc *best_child; | |
2052 | int found_moves[BOARDMAX]; | |
2053 | int k; | |
2054 | ||
2055 | memset(found_moves, 0, sizeof(found_moves)); | |
2056 | for (k = 0; k < n; k++) { | |
2057 | best_score = 0.0; | |
2058 | best_child = NULL; | |
2059 | for (child_arc = node->child; child_arc; child_arc = child_arc->next) { | |
2060 | struct uct_node *child_node = child_arc->node; | |
2061 | if (!found_moves[child_arc->move] | |
2062 | && best_score * child_node->games < child_node->wins) { | |
2063 | best_child = child_arc; | |
2064 | best_score = (float) child_node->wins / child_node->games; | |
2065 | } | |
2066 | } | |
2067 | if (!best_child) | |
2068 | break; | |
2069 | children[k] = best_child; | |
2070 | found_moves[best_child->move] = 1; | |
2071 | } | |
2072 | ||
2073 | return k; | |
2074 | } | |
2075 | ||
2076 | static void | |
2077 | uct_dump_tree_recursive(struct uct_node *node, SGFTree *sgf_tree, int color, | |
2078 | int cutoff, int depth) | |
2079 | { | |
2080 | struct uct_arc *child_arc; | |
2081 | char buf[100]; | |
2082 | if (depth > 50) | |
2083 | return; | |
2084 | for (child_arc = node->child; child_arc; child_arc = child_arc->next) { | |
2085 | struct uct_node *child_node = child_arc->node; | |
2086 | sgftreeAddPlayLast(sgf_tree, color, | |
2087 | I(child_arc->move), J(child_arc->move)); | |
2088 | gg_snprintf(buf, 100, "%d/%d (%5.3f)", child_node->wins, child_node->games, | |
2089 | (float) child_node->wins / child_node->games); | |
2090 | sgftreeAddComment(sgf_tree, buf); | |
2091 | if (child_node->games >= cutoff) | |
2092 | uct_dump_tree_recursive(child_node, sgf_tree, OTHER_COLOR(color), cutoff, depth + 1); | |
2093 | sgf_tree->lastnode = sgf_tree->lastnode->parent; | |
2094 | } | |
2095 | } | |
2096 | ||
2097 | ||
2098 | static void | |
2099 | uct_dump_tree(struct uct_tree *tree, const char *filename, int color, | |
2100 | int cutoff) | |
2101 | { | |
2102 | SGFTree sgf_tree; | |
2103 | sgftree_clear(&sgf_tree); | |
2104 | sgftreeCreateHeaderNode(&sgf_tree, board_size, komi, 0); | |
2105 | sgffile_printboard(&sgf_tree); | |
2106 | ||
2107 | uct_dump_tree_recursive(&tree->nodes[0], &sgf_tree, color, cutoff, 0); | |
2108 | ||
2109 | writesgf(sgf_tree.root, filename); | |
2110 | sgfFreeNode(sgf_tree.root); | |
2111 | } | |
2112 | ||
2113 | ||
2114 | void | |
2115 | uct_genmove(int color, int *move, int *forbidden_moves, int *allowed_moves, | |
2116 | int nodes, float *move_values, int *move_frequencies) | |
2117 | { | |
2118 | struct uct_tree tree; | |
2119 | float best_score; | |
2120 | struct uct_arc *arc; | |
2121 | struct uct_node *node; | |
2122 | struct mc_game starting_position; | |
2123 | int most_games; | |
2124 | struct uct_node *most_games_node; | |
2125 | struct uct_arc *most_games_arc; | |
2126 | int pos; | |
2127 | ||
2128 | mc_init_board_from_global_board(&starting_position.mc); | |
2129 | mc_init_move_values(&starting_position.mc); | |
2130 | starting_position.color_to_move = color; | |
2131 | /* FIXME: Fill in correct information. */ | |
2132 | starting_position.consecutive_passes = 0; | |
2133 | starting_position.consecutive_ko_captures = 0; | |
2134 | starting_position.last_move = get_last_move(); | |
2135 | starting_position.depth = 0; | |
2136 | for (pos = BOARDMIN; pos < BOARDMAX; pos++) | |
2137 | starting_position.settled[pos] = forbidden_moves[pos]; | |
2138 | ||
2139 | tree.game = starting_position; | |
2140 | /* FIXME: Don't reallocate between moves. */ | |
2141 | tree.nodes = malloc(nodes * sizeof(*tree.nodes)); | |
2142 | gg_assert(tree.nodes); | |
2143 | tree.arcs = malloc(nodes * sizeof(*tree.arcs)); | |
2144 | gg_assert(tree.arcs); | |
2145 | tree.hashtable_size = nodes; | |
2146 | tree.hashtable_odd = calloc(tree.hashtable_size, | |
2147 | sizeof(*tree.hashtable_odd)); | |
2148 | tree.hashtable_even = calloc(tree.hashtable_size, | |
2149 | sizeof(*tree.hashtable_even)); | |
2150 | gg_assert(tree.hashtable_odd); | |
2151 | gg_assert(tree.hashtable_even); | |
2152 | tree.num_nodes = nodes; | |
2153 | tree.num_arcs = nodes; | |
2154 | tree.num_used_nodes = 0; | |
2155 | tree.num_used_arcs = 0; | |
2156 | tree.forbidden_moves = forbidden_moves; | |
2157 | uct_init_node(&tree, allowed_moves); | |
2158 | uct_init_move_ordering(&tree); | |
2159 | ||
2160 | /* Play simulations. FIXME: Terribly dirty fix. */ | |
2161 | while (tree.num_used_arcs < tree.num_arcs - 10) { | |
2162 | int last_used_arcs = tree.num_used_arcs; | |
2163 | tree.game = starting_position; | |
2164 | uct_traverse_tree(&tree, &tree.nodes[0], 1.0, 0.9); | |
2165 | /* FIXME: Ugly workaround for solved positions before running out | |
2166 | * of nodes. | |
2167 | */ | |
2168 | if (tree.num_used_arcs == last_used_arcs) | |
2169 | break; | |
2170 | } | |
2171 | ||
2172 | /* Identify the best move on the top level. */ | |
2173 | best_score = 0.0; | |
2174 | *move = PASS_MOVE; | |
2175 | for (arc = tree.nodes[0].child; arc; arc = arc->next) { | |
2176 | node = arc->node; | |
2177 | move_frequencies[arc->move] = node->games; | |
2178 | move_values[arc->move] = (float) node->wins / node->games; | |
2179 | if (best_score * node->games < node->wins) { | |
2180 | *move = arc->move; | |
2181 | best_score = (float) node->wins / node->games; | |
2182 | } | |
2183 | } | |
2184 | ||
2185 | /* Dump sgf tree of the significant part of the search tree. */ | |
2186 | if (0) | |
2187 | uct_dump_tree(&tree, "/tmp/ucttree.sgf", color, 50); | |
2188 | ||
2189 | /* Print information about the search tree. */ | |
2190 | if (mc_debug) { | |
2191 | while (1) { | |
2192 | float mean; | |
2193 | float std; | |
2194 | ||
2195 | most_games = 0; | |
2196 | most_games_node = NULL; | |
2197 | most_games_arc = NULL; | |
2198 | ||
2199 | for (arc = tree.nodes[0].child; arc; arc = arc->next) { | |
2200 | node = arc->node; | |
2201 | if (most_games < node->games) { | |
2202 | most_games = node->games; | |
2203 | most_games_node = node; | |
2204 | most_games_arc = arc; | |
2205 | } | |
2206 | } | |
2207 | ||
2208 | if (most_games == 0) | |
2209 | break; | |
2210 | ||
2211 | mean = most_games_node->sum_scores / most_games_node->games; | |
2212 | std = sqrt((most_games_node->sum_scores2 - most_games_node->sum_scores * mean) / (most_games_node->games - 1)); | |
2213 | gprintf("%1m ", most_games_arc->move); | |
2214 | fprintf(stderr, "%6d %6d %5.3f %5.3f %5.3f %5.3f\n", | |
2215 | most_games_node->wins, most_games_node->games, | |
2216 | (float) most_games_node->wins / most_games_node->games, | |
2217 | mean, std, mean / (std + 0.001)); | |
2218 | most_games_node->games = -most_games_node->games; | |
2219 | } | |
2220 | for (arc = tree.nodes[0].child; arc; arc = arc->next) | |
2221 | arc->node->games = -arc->node->games; | |
2222 | ||
2223 | { | |
2224 | int n; | |
2225 | struct uct_arc *arcs[7]; | |
2226 | int depth = 0; | |
2227 | n = uct_find_best_children(&tree.nodes[0], arcs, 7); | |
2228 | gprintf("Principal variation:\n"); | |
2229 | while (n > 0 && depth < 80) { | |
2230 | int k; | |
2231 | gprintf("%C ", color); | |
2232 | for (k = 0; k < n; k++) { | |
2233 | node = arcs[k]->node; | |
2234 | gprintf("%1m ", arcs[k]->move); | |
2235 | fprintf(stderr, "%5.3f", (float) node->wins / node->games); | |
2236 | if (k == 0) | |
2237 | gprintf(" (%d games)", node->games); | |
2238 | if (k < n - 1) | |
2239 | gprintf(", "); | |
2240 | } | |
2241 | gprintf("\n"); | |
2242 | color = OTHER_COLOR(color); | |
2243 | n = uct_find_best_children(arcs[0]->node, arcs, 7); | |
2244 | depth++; | |
2245 | } | |
2246 | gprintf("\n"); | |
2247 | } | |
2248 | } | |
2249 | ||
2250 | free(tree.nodes); | |
2251 | free(tree.arcs); | |
2252 | free(tree.hashtable_odd); | |
2253 | free(tree.hashtable_even); | |
2254 | } | |
2255 | ||
2256 | ||
2257 | /* | |
2258 | * Local Variables: | |
2259 | * tab-width: 8 | |
2260 | * c-basic-offset: 2 | |
2261 | * End: | |
2262 | */ |