?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Moggy: Change all rates from 75 or 95 to 90
[pachi/peepo.git] / board.c
blobc11c3e5bbbe41f61f107d801bded5db73bb630fd
1 #include <alloca.h>
2 #include <assert.h>
3 #include <stdio.h>
4 #include <stdlib.h>
5 #include <string.h>
6
7 #include "board.h"
8 #include "debug.h"
9 #include "random.h"
10
11 int board_group_capture(struct board *board, group_t group);
12
13 bool random_pass = false;
14
15
16 #if 0
17 #define profiling_noinline __attribute__((noinline))
18 #else
19 #define profiling_noinline
20 #endif
21
22 #define gi_granularity 4
23 #define gi_allocsize(gids) ((1 << gi_granularity) + ((gids) >> gi_granularity) * (1 << gi_granularity))
24
25
26 static void
27 board_setup(struct board *b)
28 {
29 memset(b, 0, sizeof(*b));
30
31 struct move m = { pass, S_NONE };
32 b->last_move = b->ko = m;
33 }
34
35 struct board *
36 board_init(void)
37 {
38 struct board *b = malloc(sizeof(struct board));
39 board_setup(b);
40 return b;
41 }
42
43 struct board *
44 board_copy(struct board *b2, struct board *b1)
45 {
46 memcpy(b2, b1, sizeof(struct board));
47
48 int bsize = board_size2(b2) * sizeof(*b2->b);
49 int gsize = board_size2(b2) * sizeof(*b2->g);
50 int fsize = board_size2(b2) * sizeof(*b2->f);
51 int nsize = board_size2(b2) * sizeof(*b2->n);
52 int psize = board_size2(b2) * sizeof(*b2->p);
53 int hsize = board_size2(b2) * 2 * sizeof(*b2->h);
54 int gisize = board_size2(b2) * sizeof(*b2->gi);
55 #ifdef WANT_BOARD_C
56 int csize = board_size2(b2) * sizeof(*b2->c);
57 #else
58 int csize = 0;
59 #endif
60 void *x = malloc(bsize + gsize + fsize + psize + nsize + hsize + gisize + csize);
61 memcpy(x, b1->b, bsize + gsize + fsize + psize + nsize + hsize + gisize + csize);
62 b2->b = x; x += bsize;
63 b2->g = x; x += gsize;
64 b2->f = x; x += fsize;
65 b2->p = x; x += psize;
66 b2->n = x; x += nsize;
67 b2->h = x; x += hsize;
68 b2->gi = x; x += gisize;
69 #ifdef WANT_BOARD_C
70 b2->c = x; x += csize;
71 #endif
72
73 return b2;
74 }
75
76 void
77 board_done_noalloc(struct board *board)
78 {
79 if (board->b) free(board->b);
80 }
81
82 void
83 board_done(struct board *board)
84 {
85 board_done_noalloc(board);
86 free(board);
87 }
88
89 void
90 board_resize(struct board *board, int size)
91 {
92 #ifdef BOARD_SIZE
93 assert(board_size(board) == size + 2);
94 #else
95 board_size(board) = size + 2 /* S_OFFBOARD margin */;
96 board_size2(board) = board_size(board) * board_size(board);
97 #endif
98 if (board->b)
99 free(board->b);
100
101 int bsize = board_size2(board) * sizeof(*board->b);
102 int gsize = board_size2(board) * sizeof(*board->g);
103 int fsize = board_size2(board) * sizeof(*board->f);
104 int nsize = board_size2(board) * sizeof(*board->n);
105 int psize = board_size2(board) * sizeof(*board->p);
106 int hsize = board_size2(board) * 2 * sizeof(*board->h);
107 int gisize = board_size2(board) * sizeof(*board->gi);
108 #ifdef WANT_BOARD_C
109 int csize = board_size2(board) * sizeof(*board->c);
110 #else
111 int csize = 0;
112 #endif
113 void *x = malloc(bsize + gsize + fsize + psize + nsize + hsize + gisize + csize);
114 memset(x, 0, bsize + gsize + fsize + psize + nsize + hsize + gisize + csize);
115 board->b = x; x += bsize;
116 board->g = x; x += gsize;
117 board->f = x; x += fsize;
118 board->p = x; x += psize;
119 board->n = x; x += nsize;
120 board->h = x; x += hsize;
121 board->gi = x; x += gisize;
122 #ifdef WANT_BOARD_C
123 board->c = x; x += csize;
124 #endif
125 }
126
127 void
128 board_clear(struct board *board)
129 {
130 int size = board_size(board);
131
132 board_done_noalloc(board);
133 board_setup(board);
134 board_resize(board, size - 2 /* S_OFFBOARD margin */);
135
136 /* Setup initial symmetry */
137 board->symmetry.d = 1;
138 board->symmetry.x1 = board->symmetry.y1 = board->size / 2;
139 board->symmetry.x2 = board->symmetry.y2 = board->size - 1;
140 board->symmetry.type = SYM_FULL;
141
142 /* Draw the offboard margin */
143 int top_row = board_size2(board) - board_size(board);
144 int i;
145 for (i = 0; i < board_size(board); i++)
146 board->b[i] = board->b[top_row + i] = S_OFFBOARD;
147 for (i = 0; i <= top_row; i += board_size(board))
148 board->b[i] = board->b[board_size(board) - 1 + i] = S_OFFBOARD;
149
150 foreach_point(board) {
151 coord_t coord = c;
152 if (board_at(board, coord) == S_OFFBOARD)
153 continue;
154 foreach_neighbor(board, c, {
155 inc_neighbor_count_at(board, coord, board_at(board, c));
156 } );
157 } foreach_point_end;
158
159 /* First, pass is always a free position. */
160 board->f[board->flen++] = coord_raw(pass);
161 /* All positions are free! Except the margin. */
162 for (i = board_size(board); i < (board_size(board) - 1) * board_size(board); i++)
163 if (i % board_size(board) != 0 && i % board_size(board) != board_size(board) - 1)
164 board->f[board->flen++] = i;
165
166 /* Initialize zobrist hashtable. */
167 foreach_point(board) {
168 int max = (sizeof(hash_t) << history_hash_bits);
169 /* fast_random() is 16-bit only */
170 board->h[coord_raw(c) * 2] = ((hash_t) fast_random(max))
171 | ((hash_t) fast_random(max) << 16)
172 | ((hash_t) fast_random(max) << 32)
173 | ((hash_t) fast_random(max) << 48);
174 if (!board->h[coord_raw(c) * 2])
175 /* Would be kinda "oops". */
176 board->h[coord_raw(c) * 2] = 1;
177 /* And once again for white */
178 board->h[coord_raw(c) * 2 + 1] = ((hash_t) fast_random(max))
179 | ((hash_t) fast_random(max) << 16)
180 | ((hash_t) fast_random(max) << 32)
181 | ((hash_t) fast_random(max) << 48);
182 if (!board->h[coord_raw(c) * 2 + 1])
183 board->h[coord_raw(c) * 2 + 1] = 1;
184 } foreach_point_end;
185 }
186
187
188 void
189 board_print(struct board *board, FILE *f)
190 {
191 fprintf(f, "Move: % 3d Komi: %2.1f Captures B: %d W: %d\n ",
192 board->moves, board->komi,
193 board->captures[S_BLACK], board->captures[S_WHITE]);
194 int x, y;
195 char asdf[] = "ABCDEFGHJKLMNOPQRSTUVWXYZ";
196 for (x = 1; x < board_size(board) - 1; x++)
197 fprintf(f, "%c ", asdf[x - 1]);
198 fprintf(f, "\n +-");
199 for (x = 1; x < board_size(board) - 1; x++)
200 fprintf(f, "--");
201 fprintf(f, "+\n");
202 for (y = board_size(board) - 2; y >= 1; y--) {
203 fprintf(f, "%2d | ", y);
204 for (x = 1; x < board_size(board) - 1; x++) {
205 if (coord_x(board->last_move.coord, board) == x && coord_y(board->last_move.coord, board) == y)
206 fprintf(f, "%c)", stone2char(board_atxy(board, x, y)));
207 else
208 fprintf(f, "%c ", stone2char(board_atxy(board, x, y)));
209 }
210 if (DEBUGL(6)) {
211 fprintf(f, "| ");
212 for (x = 1; x < board_size(board) - 1; x++) {
213 fprintf(f, "%d ", group_base(group_atxy(board, x, y)));
214 }
215 }
216 fprintf(f, "|\n");
217 }
218 fprintf(f, " +-");
219 for (x = 1; x < board_size(board) - 1; x++)
220 fprintf(f, "--");
221 fprintf(f, "+\n\n");
222 }
223
224
225 /* Update board hash with given coordinate. */
226 static void profiling_noinline
227 board_hash_update(struct board *board, coord_t coord, enum stone color)
228 {
229 board->hash ^= hash_at(board, coord, color);
230 if (DEBUGL(8))
231 fprintf(stderr, "board_hash_update(%d,%d,%d) ^ %llx -> %llx\n", color, coord_x(coord, board), coord_y(coord, board), hash_at(board, coord, color), board->hash);
232 }
233
234 /* Commit current board hash to history. */
235 static void profiling_noinline
236 board_hash_commit(struct board *board)
237 {
238 if (DEBUGL(8))
239 fprintf(stderr, "board_hash_commit %llx\n", board->hash);
240 if (likely(board->history_hash[board->hash & history_hash_mask]) == 0) {
241 board->history_hash[board->hash & history_hash_mask] = board->hash;
242 } else {
243 hash_t i = board->hash;
244 while (board->history_hash[i & history_hash_mask]) {
245 if (board->history_hash[i & history_hash_mask] == board->hash) {
246 if (DEBUGL(5))
247 fprintf(stderr, "SUPERKO VIOLATION noted at %d,%d\n",
248 coord_x(board->last_move.coord, board), coord_y(board->last_move.coord, board));
249 board->superko_violation = true;
250 return;
251 }
252 i = history_hash_next(i);
253 }
254 board->history_hash[i & history_hash_mask] = board->hash;
255 }
256 }
257
258
259 void
260 board_symmetry_update(struct board *b, struct board_symmetry *symmetry, coord_t c)
261 {
262 if (likely(symmetry->type == SYM_NONE)) {
263 /* Fully degenerated already. We do not support detection
264 * of restoring of symmetry, assuming that this is too rare
265 * a case to handle. */
266 return;
267 }
268
269 int x = coord_x(c, b), y = coord_y(c, b), t = board_size(b) / 2;
270 int dx = board_size(b) - 1 - x; /* for SYM_DOWN */
271 if (DEBUGL(6)) {
272 fprintf(stderr, "SYMMETRY [%d,%d,%d,%d|%d=%d] update for %d,%d\n",
273 symmetry->x1, symmetry->y1, symmetry->x2, symmetry->y2,
274 symmetry->d, symmetry->type, x, y);
275 }
276
277 switch (symmetry->type) {
278 case SYM_FULL:
279 if (x == t && y == t) {
280 /* Tengen keeps full symmetry. */
281 return;
282 }
283 /* New symmetry now? */
284 if (x == y) {
285 symmetry->type = SYM_DIAG_UP;
286 symmetry->x1 = symmetry->y1 = 1;
287 symmetry->x2 = symmetry->y2 = board_size(b) - 1;
288 symmetry->d = 1;
289 } else if (dx == y) {
290 symmetry->type = SYM_DIAG_DOWN;
291 symmetry->x1 = symmetry->y1 = 1;
292 symmetry->x2 = symmetry->y2 = board_size(b) - 1;
293 symmetry->d = 1;
294 } else if (x == t) {
295 symmetry->type = SYM_HORIZ;
296 symmetry->y1 = 1;
297 symmetry->y2 = board_size(b) - 1;
298 symmetry->d = 0;
299 } else if (y == t) {
300 symmetry->type = SYM_VERT;
301 symmetry->x1 = 1;
302 symmetry->x2 = board_size(b) - 1;
303 symmetry->d = 0;
304 } else {
305 break_symmetry:
306 symmetry->type = SYM_NONE;
307 symmetry->x1 = symmetry->y1 = 1;
308 symmetry->x2 = symmetry->y2 = board_size(b) - 1;
309 symmetry->d = 0;
310 }
311 break;
312 case SYM_DIAG_UP:
313 if (x == y)
314 return;
315 goto break_symmetry;
316 case SYM_DIAG_DOWN:
317 if (dx == y)
318 return;
319 goto break_symmetry;
320 case SYM_HORIZ:
321 if (x == t)
322 return;
323 goto break_symmetry;
324 case SYM_VERT:
325 if (y == t)
326 return;
327 goto break_symmetry;
328 case SYM_NONE:
329 assert(0);
330 break;
331 }
332
333 if (DEBUGL(6)) {
334 fprintf(stderr, "NEW SYMMETRY [%d,%d,%d,%d|%d=%d]\n",
335 symmetry->x1, symmetry->y1, symmetry->x2, symmetry->y2,
336 symmetry->d, symmetry->type);
337 }
338 /* Whew. */
339 }
340
341
342 void
343 board_handicap_stone(struct board *board, int x, int y, FILE *f)
344 {
345 struct move m;
346 m.color = S_BLACK;
347 coord_xy(m.coord, x, y, board);
348
349 board_play(board, &m);
350
351 char *str = coord2str(m.coord, board);
352 if (DEBUGL(1))
353 fprintf(stderr, "choosing handicap %s (%d,%d)\n", str, x, y);
354 fprintf(f, "%s ", str);
355 free(str);
356 }
357
358 void
359 board_handicap(struct board *board, int stones, FILE *f)
360 {
361 int margin = 3 + (board_size(board) >= 13);
362 int min = margin;
363 int mid = board_size(board) / 2;
364 int max = board_size(board) - 1 - margin;
365 const int places[][2] = {
366 { min, min }, { max, max }, { max, min }, { min, max },
367 { min, mid }, { max, mid },
368 { mid, min }, { mid, max },
369 { mid, mid },
370 };
371
372 board->handicap = stones;
373
374 if (stones == 5 || stones == 7) {
375 board_handicap_stone(board, mid, mid, f);
376 stones--;
377 }
378
379 int i;
380 for (i = 0; i < stones; i++)
381 board_handicap_stone(board, places[i][0], places[i][1], f);
382 }
383
384
385 static void __attribute__((noinline))
386 check_libs_consistency(struct board *board, group_t g)
387 {
388 #ifdef DEBUG
389 if (!g) return;
390 struct group *gi = &board_group_info(board, g);
391 for (int i = 0; i < GROUP_KEEP_LIBS; i++)
392 if (gi->lib[i] && board_at(board, gi->lib[i]) != S_NONE) {
393 fprintf(stderr, "BOGUS LIBERTY %s of group %d[%s]\n", coord2sstr(gi->lib[i], board), g, coord2sstr(group_base(g), board));
394 assert(0);
395 }
396 #endif
397 }
398
399 static void
400 board_capturable_add(struct board *board, group_t group)
401 {
402 #ifdef WANT_BOARD_C
403 //fprintf(stderr, "add of group %d (%d)\n", group_base(group), board->clen);
404 assert(group);
405 assert(board->clen < board_size2(board));
406 board->c[board->clen++] = group;
407 #endif
408 }
409 static void
410 board_capturable_rm(struct board *board, group_t group)
411 {
412 #ifdef WANT_BOARD_C
413 //fprintf(stderr, "rm of group %d\n", group_base(group));
414 for (int i = 0; i < board->clen; i++) {
415 if (unlikely(board->c[i] == group)) {
416 board->c[i] = board->c[--board->clen];
417 return;
418 }
419 }
420 fprintf(stderr, "rm of bad group %d\n", group_base(group));
421 assert(0);
422 #endif
423 }
424
425 static void
426 board_group_addlib(struct board *board, group_t group, coord_t coord)
427 {
428 if (DEBUGL(7)) {
429 fprintf(stderr, "Group %d[%s] %d: Adding liberty %s\n",
430 group_base(group), coord2sstr(group_base(group), board),
431 board_group_info(board, group).libs, coord2sstr(coord, board));
432 }
433
434 check_libs_consistency(board, group);
435
436 struct group *gi = &board_group_info(board, group);
437 if (gi->libs < GROUP_KEEP_LIBS) {
438 for (int i = 0; i < GROUP_KEEP_LIBS; i++) {
439 #if 0
440 /* Seems extra branch just slows it down */
441 if (!gi->lib[i])
442 break;
443 #endif
444 if (unlikely(gi->lib[i] == coord))
445 return;
446 }
447 if (gi->libs == 0)
448 board_capturable_add(board, group);
449 else if (gi->libs == 1)
450 board_capturable_rm(board, group);
451 gi->lib[gi->libs++] = coord;
452 }
453
454 check_libs_consistency(board, group);
455 }
456
457 static void
458 board_group_find_extra_libs(struct board *board, group_t group, struct group *gi, coord_t avoid)
459 {
460 /* Add extra liberty from the board to our liberty list. */
461 enum stone watermark[board_size2(board)];
462 memcpy(watermark, board->b, sizeof(watermark));
463
464 for (int i = 0; i < GROUP_KEEP_LIBS - 1; i++)
465 watermark[coord_raw(gi->lib[i])] = S_OFFBOARD;
466 watermark[coord_raw(avoid)] = S_OFFBOARD;
467
468 foreach_in_group(board, group) {
469 coord_t coord2 = c;
470 foreach_neighbor(board, coord2, {
471 if (likely(watermark[coord_raw(c)] != S_NONE))
472 continue;
473 watermark[coord_raw(c)] = S_OFFBOARD;
474 gi->lib[gi->libs++] = c;
475 if (unlikely(gi->libs >= GROUP_KEEP_LIBS))
476 return;
477 } );
478 } foreach_in_group_end;
479 }
480
481 static void
482 board_group_rmlib(struct board *board, group_t group, coord_t coord)
483 {
484 if (DEBUGL(7)) {
485 fprintf(stderr, "Group %d[%s] %d: Removing liberty %s\n",
486 group_base(group), coord2sstr(group_base(group), board),
487 board_group_info(board, group).libs, coord2sstr(coord, board));
488 }
489
490 struct group *gi = &board_group_info(board, group);
491 for (int i = 0; i < GROUP_KEEP_LIBS; i++) {
492 #if 0
493 /* Seems extra branch just slows it down */
494 if (!gi->lib[i])
495 break;
496 #endif
497 if (likely(gi->lib[i] != coord))
498 continue;
499
500 gi->lib[i] = gi->lib[--gi->libs];
501 gi->lib[gi->libs] = 0;
502
503 check_libs_consistency(board, group);
504
505 /* Postpone refilling lib[] until we need to. */
506 assert(GROUP_REFILL_LIBS > 1);
507 if (gi->libs > GROUP_REFILL_LIBS)
508 return;
509 if (gi->libs == GROUP_REFILL_LIBS)
510 board_group_find_extra_libs(board, group, gi, coord);
511
512 if (gi->libs == 1)
513 board_capturable_add(board, group);
514 else if (gi->libs == 0)
515 board_capturable_rm(board, group);
516 return;
517 }
518
519 /* This is ok even if gi->libs < GROUP_KEEP_LIBS since we
520 * can call this multiple times per coord. */
521 check_libs_consistency(board, group);
522 return;
523 }
524
525
526 /* This is a low-level routine that doesn't maintain consistency
527 * of all the board data structures. Use board_group_capture() from
528 * your code. */
529 static void
530 board_remove_stone(struct board *board, coord_t c)
531 {
532 enum stone color = board_at(board, c);
533 board_at(board, c) = S_NONE;
534 group_at(board, c) = 0;
535 board_hash_update(board, c, color);
536
537 /* Increase liberties of surrounding groups */
538 coord_t coord = c;
539 foreach_neighbor(board, coord, {
540 dec_neighbor_count_at(board, c, color);
541 group_t g = group_at(board, c);
542 if (g)
543 board_group_addlib(board, g, coord);
544 });
545
546 if (DEBUGL(6))
547 fprintf(stderr, "pushing free move [%d]: %d,%d\n", board->flen, coord_x(c, board), coord_y(c, board));
548 board->f[board->flen++] = coord_raw(c);
549 }
550
551
552 static void profiling_noinline
553 add_to_group(struct board *board, group_t group, coord_t prevstone, coord_t coord)
554 {
555 foreach_neighbor(board, coord, {
556 if (board_at(board, c) == S_NONE)
557 board_group_addlib(board, group, c);
558 });
559
560 group_at(board, coord) = group;
561 groupnext_at(board, coord) = groupnext_at(board, prevstone);
562 groupnext_at(board, prevstone) = coord_raw(coord);
563
564 if (DEBUGL(8))
565 fprintf(stderr, "add_to_group: added (%d,%d ->) %d,%d (-> %d,%d) to group %d\n",
566 coord_x(prevstone, board), coord_y(prevstone, board),
567 coord_x(coord, board), coord_y(coord, board),
568 groupnext_at(board, coord) % board_size(board), groupnext_at(board, coord) / board_size(board),
569 group_base(group));
570 }
571
572 static void profiling_noinline
573 merge_groups(struct board *board, group_t group_to, group_t group_from)
574 {
575 if (DEBUGL(7))
576 fprintf(stderr, "board_play_raw: merging groups %d -> %d\n",
577 group_base(group_from), group_base(group_to));
578
579 coord_t last_in_group;
580 foreach_in_group(board, group_from) {
581 last_in_group = c;
582 group_at(board, c) = group_to;
583 } foreach_in_group_end;
584 groupnext_at(board, last_in_group) = groupnext_at(board, group_base(group_to));
585 groupnext_at(board, group_base(group_to)) = group_base(group_from);
586
587 struct group *gi_from = &board_group_info(board, group_from);
588 struct group *gi_to = &board_group_info(board, group_to);
589 if (gi_to->libs < GROUP_KEEP_LIBS) {
590 for (int i = 0; i < gi_from->libs; i++) {
591 for (int j = 0; j < gi_to->libs; j++)
592 if (gi_to->lib[j] == gi_from->lib[i])
593 goto next_from_lib;
594 if (gi_to->libs == 0)
595 board_capturable_add(board, group_to);
596 else if (gi_to->libs == 1)
597 board_capturable_rm(board, group_to);
598 gi_to->lib[gi_to->libs++] = gi_from->lib[i];
599 if (gi_to->libs >= GROUP_KEEP_LIBS)
600 break;
601 next_from_lib:;
602 }
603 }
604
605 if (gi_from->libs == 1)
606 board_capturable_rm(board, group_from);
607 memset(gi_from, 0, sizeof(struct group));
608
609 if (DEBUGL(7))
610 fprintf(stderr, "board_play_raw: merged group: %d\n",
611 group_base(group_to));
612 }
613
614 static group_t profiling_noinline
615 new_group(struct board *board, coord_t coord)
616 {
617 group_t group = coord_raw(coord);
618 struct group *gi = &board_group_info(board, group);
619 foreach_neighbor(board, coord, {
620 if (board_at(board, c) == S_NONE)
621 /* board_group_addlib is ridiculously expensive for us */
622 #if GROUP_KEEP_LIBS < 4
623 if (gi->libs < GROUP_KEEP_LIBS)
624 #endif
625 gi->lib[gi->libs++] = c;
626 });
627 if (gi->libs == 1)
628 board_capturable_add(board, group);
629 check_libs_consistency(board, group);
630
631 group_at(board, coord) = group;
632 groupnext_at(board, coord) = 0;
633
634 if (DEBUGL(8))
635 fprintf(stderr, "new_group: added %d,%d to group %d\n",
636 coord_x(coord, board), coord_y(coord, board),
637 group_base(group));
638
639 return group;
640 }
641
642 static inline group_t
643 play_one_neighbor(struct board *board,
644 coord_t coord, enum stone color, enum stone other_color,
645 coord_t c, group_t group)
646 {
647 enum stone ncolor = board_at(board, c);
648 group_t ngroup = group_at(board, c);
649
650 inc_neighbor_count_at(board, c, color);
651
652 if (!ngroup)
653 return group;
654
655 board_group_rmlib(board, ngroup, coord);
656 if (DEBUGL(7))
657 fprintf(stderr, "board_play_raw: reducing libs for group %d (%d:%d,%d)\n",
658 group_base(ngroup), ncolor, color, other_color);
659
660 if (ncolor == color && ngroup != group) {
661 if (!group) {
662 group = ngroup;
663 add_to_group(board, group, c, coord);
664 } else {
665 merge_groups(board, group, ngroup);
666 }
667 } else if (ncolor == other_color) {
668 if (DEBUGL(8)) {
669 struct group *gi = &board_group_info(board, ngroup);
670 fprintf(stderr, "testing captured group %d[%s]: ", group_base(ngroup), coord2sstr(group_base(ngroup), board));
671 for (int i = 0; i < GROUP_KEEP_LIBS; i++)
672 fprintf(stderr, "%s ", coord2sstr(gi->lib[i], board));
673 fprintf(stderr, "\n");
674 }
675 if (unlikely(board_group_captured(board, ngroup)))
676 board_group_capture(board, ngroup);
677 }
678 return group;
679 }
680
681 /* We played on a place with at least one liberty. We will become a member of
682 * some group for sure. */
683 static group_t profiling_noinline
684 board_play_outside(struct board *board, struct move *m, int f)
685 {
686 coord_t coord = m->coord;
687 enum stone color = m->color;
688 enum stone other_color = stone_other(color);
689 group_t group = 0;
690
691 board->f[f] = board->f[--board->flen];
692 if (DEBUGL(6))
693 fprintf(stderr, "popping free move [%d->%d]: %d\n", board->flen, f, board->f[f]);
694
695 foreach_neighbor(board, coord, {
696 group = play_one_neighbor(board, coord, color, other_color, c, group);
697 });
698
699 if (unlikely(!group))
700 group = new_group(board, coord);
701
702 board_at(board, coord) = color;
703 board->last_move = *m;
704 board->moves++;
705 board_hash_update(board, coord, color);
706 board_symmetry_update(board, &board->symmetry, coord);
707 struct move ko = { pass, S_NONE };
708 board->ko = ko;
709
710 return group;
711 }
712
713 /* We played in an eye-like shape. Either we capture at least one of the eye
714 * sides in the process of playing, or return -1. */
715 static int profiling_noinline
716 board_play_in_eye(struct board *board, struct move *m, int f)
717 {
718 coord_t coord = m->coord;
719 enum stone color = m->color;
720 /* Check ko: Capture at a position of ko capture one move ago */
721 if (unlikely(color == board->ko.color && coord_eq(coord, board->ko.coord))) {
722 if (DEBUGL(5))
723 fprintf(stderr, "board_check: ko at %d,%d color %d\n", coord_x(coord, board), coord_y(coord, board), color);
724 return -1;
725 } else if (DEBUGL(6)) {
726 fprintf(stderr, "board_check: no ko at %d,%d,%d - ko is %d,%d,%d\n",
727 color, coord_x(coord, board), coord_y(coord, board),
728 board->ko.color, coord_x(board->ko.coord, board), coord_y(board->ko.coord, board));
729 }
730
731 struct move ko = { pass, S_NONE };
732
733 int captured_groups = 0;
734
735 foreach_neighbor(board, coord, {
736 group_t g = group_at(board, c);
737 if (DEBUGL(7))
738 fprintf(stderr, "board_check: group %d has %d libs\n",
739 g, board_group_info(board, g).libs);
740 captured_groups += (board_group_info(board, g).libs == 1);
741 });
742
743 if (likely(captured_groups == 0)) {
744 if (DEBUGL(5)) {
745 if (DEBUGL(6))
746 board_print(board, stderr);
747 fprintf(stderr, "board_check: one-stone suicide\n");
748 }
749
750 return -1;
751 }
752
753 board->f[f] = board->f[--board->flen];
754 if (DEBUGL(6))
755 fprintf(stderr, "popping free move [%d->%d]: %d\n", board->flen, f, board->f[f]);
756
757 foreach_neighbor(board, coord, {
758 inc_neighbor_count_at(board, c, color);
759
760 group_t group = group_at(board, c);
761 if (!group)
762 continue;
763
764 board_group_rmlib(board, group, coord);
765 if (DEBUGL(7))
766 fprintf(stderr, "board_play_raw: reducing libs for group %d\n",
767 group_base(group));
768
769 if (board_group_captured(board, group)) {
770 if (board_group_capture(board, group) == 1) {
771 /* If we captured multiple groups at once,
772 * we can't be fighting ko so we don't need
773 * to check for that. */
774 ko.color = stone_other(color);
775 ko.coord = c;
776 if (DEBUGL(5))
777 fprintf(stderr, "guarding ko at %d,%d,%d\n", ko.color, coord_x(ko.coord, board), coord_y(ko.coord, board));
778 }
779 }
780 });
781
782 board_at(board, coord) = color;
783
784 board->last_move = *m;
785 board->moves++;
786 board_hash_update(board, coord, color);
787 board_hash_commit(board);
788 board_symmetry_update(board, &board->symmetry, coord);
789 board->ko = ko;
790
791 return !!new_group(board, coord);
792 }
793
794 static int __attribute__((flatten))
795 board_play_f(struct board *board, struct move *m, int f)
796 {
797 if (DEBUGL(7)) {
798 fprintf(stderr, "board_play(): ---- Playing %d,%d\n", coord_x(m->coord, board), coord_y(m->coord, board));
799 }
800 if (likely(!board_is_eyelike(board, &m->coord, stone_other(m->color)))) {
801 /* NOT playing in an eye. Thus this move has to succeed. (This
802 * is thanks to New Zealand rules. Otherwise, multi-stone
803 * suicide might fail.) */
804 group_t group = board_play_outside(board, m, f);
805 if (unlikely(board_group_captured(board, group))) {
806 board_group_capture(board, group);
807 }
808 board_hash_commit(board);
809 return 0;
810 } else {
811 return board_play_in_eye(board, m, f);
812 }
813 }
814
815 int
816 board_play(struct board *board, struct move *m)
817 {
818 if (unlikely(is_pass(m->coord) || is_resign(m->coord))) {
819 board->last_move = *m;
820 return 0;
821 }
822
823 int f;
824 for (f = 0; f < board->flen; f++)
825 if (board->f[f] == coord_raw(m->coord))
826 return board_play_f(board, m, f);
827
828 if (DEBUGL(7))
829 fprintf(stderr, "board_check: stone exists\n");
830 return -1;
831 }
832
833
834 static inline bool
835 board_try_random_move(struct board *b, enum stone color, coord_t *coord, int f)
836 {
837 coord_raw(*coord) = b->f[f];
838 if (unlikely(is_pass(*coord)))
839 return random_pass;
840 struct move m = { *coord, color };
841 if (DEBUGL(6))
842 fprintf(stderr, "trying random move %d: %d,%d\n", f, coord_x(*coord, b), coord_y(*coord, b));
843 return (likely(!board_is_one_point_eye(b, coord, color)) /* bad idea to play into one, usually */
844 && likely(board_play_f(b, &m, f) >= 0));
845 }
846
847 void
848 board_play_random(struct board *b, enum stone color, coord_t *coord)
849 {
850 int base = fast_random(b->flen);
851 coord_pos(*coord, base, b);
852 if (likely(board_try_random_move(b, color, coord, base)))
853 return;
854
855 int f;
856 for (f = base + 1; f < b->flen; f++)
857 if (board_try_random_move(b, color, coord, f))
858 return;
859 for (f = 0; f < base; f++)
860 if (board_try_random_move(b, color, coord, f))
861 return;
862
863 *coord = pass;
864 }
865
866
867 bool
868 board_is_eyelike(struct board *board, coord_t *coord, enum stone eye_color)
869 {
870 return (neighbor_count_at(board, *coord, eye_color) + neighbor_count_at(board, *coord, S_OFFBOARD)) == 4;
871 }
872
873 bool
874 board_is_one_point_eye(struct board *board, coord_t *coord, enum stone eye_color)
875 {
876 enum stone color_diag_libs[S_MAX] = {0, 0, 0, 0};
877
878 if (likely(neighbor_count_at(board, *coord, eye_color) + neighbor_count_at(board, *coord, S_OFFBOARD) < 4)) {
879 return false;
880 }
881
882 /* XXX: We attempt false eye detection but we will yield false
883 * positives in case of http://senseis.xmp.net/?TwoHeadedDragon :-( */
884
885 foreach_diag_neighbor(board, *coord) {
886 color_diag_libs[(enum stone) board_at(board, c)]++;
887 } foreach_diag_neighbor_end;
888 color_diag_libs[stone_other(eye_color)] += !!color_diag_libs[S_OFFBOARD];
889 return likely(color_diag_libs[stone_other(eye_color)] < 2);
890 }
891
892 enum stone
893 board_get_one_point_eye(struct board *board, coord_t *coord)
894 {
895 if (board_is_one_point_eye(board, coord, S_WHITE))
896 return S_WHITE;
897 else if (board_is_one_point_eye(board, coord, S_BLACK))
898 return S_BLACK;
899 else
900 return S_NONE;
901 }
902
903
904 int profiling_noinline
905 board_group_capture(struct board *board, group_t group)
906 {
907 int stones = 0;
908
909 foreach_in_group(board, group) {
910 board->captures[stone_other(board_at(board, c))]++;
911 board_remove_stone(board, c);
912 stones++;
913 } foreach_in_group_end;
914
915 if (board_group_info(board, group).libs == 1)
916 board_capturable_rm(board, group);
917 memset(&board_group_info(board, group), 0, sizeof(struct group));
918
919 return stones;
920 }
921
922 bool
923 board_group_in_atari(struct board *board, group_t group, coord_t *lastlib)
924 {
925 if (board_group_info(board, group).libs != 1)
926 return false;
927 *lastlib = board_group_info(board, group).lib[0];
928 return true;
929 }
930
931 bool
932 board_group_can_atari(struct board *board, group_t group, coord_t lastlib[2])
933 {
934 if (board_group_info(board, group).libs != 2)
935 return false;
936 lastlib[0] = board_group_info(board, group).lib[0];
937 lastlib[1] = board_group_info(board, group).lib[1];
938 return true;
939 }
940
941
942 static enum stone
943 board_tromp_taylor_owner(struct board *board, coord_t c)
944 {
945 int x = coord_x(c, board), y = coord_y(c, board);
946 enum stone color = S_NONE;
947 #define TEST_REACH(xx, yy) \
948 { \
949 enum stone c2 = board_atxy(board, xx, yy); \
950 if (c2 != S_NONE) { \
951 if (color != S_NONE && color != c2) \
952 return S_NONE; \
953 color = c2; \
954 break; \
955 } \
956 }
957 for (int i = x; i > 0; i--)
958 TEST_REACH(i, y);
959 for (int i = x; i < board_size(board) - 1; i++)
960 TEST_REACH(i, y);
961 for (int i = y; i > 0; i--)
962 TEST_REACH(x, i);
963 for (int i = y; i < board_size(board) - 1; i++)
964 TEST_REACH(x, i);
965 return color;
966 }
967
968 /* Tromp-Taylor Counting */
969 float
970 board_official_score(struct board *board)
971 {
972
973 /* A point P, not colored C, is said to reach C, if there is a path of
974 * (vertically or horizontally) adjacent points of P's color from P to
975 * a point of color C.
976 *
977 * A player's score is the number of points of her color, plus the
978 * number of empty points that reach only her color. */
979
980 int scores[S_MAX];
981 memset(scores, 0, sizeof(scores));
982
983 foreach_point(board) {
984 enum stone color = board_at(board, c);
985 if (color == S_NONE)
986 color = board_tromp_taylor_owner(board, c);
987 scores[color]++;
988 } foreach_point_end;
989
990 return board->komi + board->handicap + scores[S_WHITE] - scores[S_BLACK];
991 }
992
993 float
994 board_fast_score(struct board *board)
995 {
996 int scores[S_MAX];
997 memset(scores, 0, sizeof(scores));
998
999 foreach_point(board) {
1000 enum stone color = board_at(board, c);
1001 if (color == S_NONE)
1002 color = board_get_one_point_eye(board, &c);
1003 scores[color]++;
1004 // fprintf(stderr, "%d, %d ++%d = %d\n", coord_x(c, board), coord_y(c, board), color, scores[color]);
1005 } foreach_point_end;
1006
1007 return board->komi + board->handicap + scores[S_WHITE] - scores[S_BLACK];
1008 }
1009
1010
1011 bool
1012 valid_escape_route(struct board *b, enum stone color, coord_t to)
1013 {
1014 /* Assess if we actually gain any liberties by this escape route.
1015 * Note that this is not 100% as we cannot check whether we are
1016 * connecting out or just to ourselves. */
1017 /* Also, we prohibit 1-1 here:
1018 * X X X X |
1019 * O X O O |
1020 * O O X O |
1021 * .(O)X . |
1022 * --------+
1023 */
1024 int groupcts[S_MAX] = {};
1025 group_t groupids[S_MAX][4] = {};
1026 foreach_neighbor(b, to, {
1027 enum stone s = board_at(b, c);
1028 groupids[s][groupcts[s]++] = group_at(b, c);
1029 });
1030
1031 /* More than one immediate liberty, thumbs up! */
1032 if (groupcts[S_NONE] > 1)
1033 return true;
1034
1035 /* Leave unique friendly groups only */
1036 for (int i = 0; i < 4; i++) {
1037 /* We can escape by connecting to this group if it's
1038 * not in atari. */
1039 if (groupids[color][i] && board_group_info(b, groupids[color][i]).libs > 1)
1040 return true;
1041 }
1042 /* No way to pull out, no way to connect out. */
1043 return false;
1044 }
1045
1046
1047 bool
1048 board_stone_radar(struct board *b, coord_t coord, int distance)
1049 {
1050 int bounds[4] = {
1051 coord_x(coord, b) - distance,
1052 coord_y(coord, b) - distance,
1053 coord_x(coord, b) + distance,
1054 coord_y(coord, b) + distance
1055 };
1056 for (int i = 0; i < 4; i++)
1057 if (bounds[i] < 1)
1058 bounds[i] = 1;
1059 else if (bounds[i] > board_size(b) - 2)
1060 bounds[i] = board_size(b) - 2;
1061 for (int x = bounds[0]; x <= bounds[2]; x++)
1062 for (int y = bounds[1]; y <= bounds[3]; y++)
1063 if (board_atxy(b, x, y) != S_NONE) {
1064 //fprintf(stderr, "radar %d,%d,%d: %d,%d (%d)\n", coord_x(coord, b), coord_y(coord, b), distance, x, y, board_atxy(b, x, y));
1065 return true;
1066 }
1067 return false;
1068 }