| 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 | */ |