From becb95acdf3af9cb84442216ea05ce67ae6e8eed Mon Sep 17 00:00:00 2001 From: Petr Baudis Date: Fri, 22 Oct 2010 02:57:42 +0200 Subject: [PATCH] 3x3 patterns: Include atari information for direct neighbors This was not considered in the original Mogo paper, but seems to be a common practice nowadays and promises a good strength increase. --- board.c | 82 +++++++++++++++++++++++++++++++++++++++++++++-------- board.h | 2 +- pattern3.c | 94 ++++++++++++++++++++++++++++++++++++++++++++++++++++++------- pattern3.h | 23 ++++++++++++--- patternsp.c | 4 +++ 5 files changed, 179 insertions(+), 26 deletions(-) diff --git a/board.c b/board.c index a1687b4..370183c 100644 --- a/board.c +++ b/board.c @@ -526,21 +526,27 @@ board_hash_update(struct board *board, coord_t coord, enum stone color) #if defined(BOARD_PAT3) /* @color is not what we need in case of capture. */ + static const int ataribits[8] = { -1, 0, -1, 1, 2, -1, 3, -1 }; enum stone new_color = board_at(board, coord); - if (new_color == S_NONE) + bool in_atari = false; + if (new_color == S_NONE) { board->pat3[coord] = pattern3_hash(board, coord); - foreach_8neighbor(board, coord) { // internally, the loop uses fn__i=[0..7] + } else { + in_atari = (board_group_info(board, group_at(board, coord)).libs == 1); + } + foreach_8neighbor(board, coord) { + /* Internally, the loop uses fn__i=[0..7]. We can use + * it directly to address bits within the bitmap of the + * neighbors since the bitmap order is reverse to the + * loop order. */ if (board_at(board, c) != S_NONE) continue; board->pat3[c] &= ~(3 << (fn__i*2)); board->pat3[c] |= new_color << (fn__i*2); -#if 0 - if (board_at(board, c) != S_OFFBOARD && pattern3_hash(board, c) != board->pat3[c]) { - board_print(board, stderr); - fprintf(stderr, "%s->%s %x != %x (%d-%d:%d)\n", coord2sstr(coord, board), coord2sstr(c, board), pattern3_hash(board, c), board->pat3[c], coord, c, fn__i); - assert(0); + if (ataribits[fn__i] >= 0) { + board->pat3[c] &= ~(1 << (16 + ataribits[fn__i])); + board->pat3[c] |= in_atari << (16 + ataribits[fn__i]); } -#endif #if defined(BOARD_TRAITS) board_trait_queue(board, c); #elif defined(BOARD_GAMMA) @@ -723,6 +729,20 @@ check_libs_consistency(struct board *board, group_t g) } static void +check_pat3_consistency(struct board *board, coord_t coord) +{ +#ifdef DEBUG + foreach_8neighbor(board, coord) { + if (board_at(board, c) == S_NONE && pattern3_hash(board, c) != board->pat3[c]) { + board_print(board, stderr); + fprintf(stderr, "%s(%d)->%s(%d) computed %x != stored %x (%d)\n", coord2sstr(coord, board), coord, coord2sstr(c, board), c, pattern3_hash(board, c), board->pat3[c], fn__i); + assert(0); + } + } foreach_8neighbor_end; +#endif +} + +static void board_capturable_add(struct board *board, group_t group, coord_t lib, bool onestone) { //fprintf(stderr, "group %s cap %s\n", coord2sstr(group, board), coord2sstr(lib, boarD)); @@ -739,6 +759,14 @@ board_capturable_add(struct board *board, group_t group, coord_t lib, bool onest board_trait_queue(board, lib); #endif +#ifdef BOARD_PAT3 + int fn__i = 0; + foreach_neighbor(board, lib, { + board->pat3[lib] |= (group_at(board, c) == group) << (16 + 3 - fn__i); + fn__i++; + }); +#endif + #ifdef WANT_BOARD_C /* Update the list of capturable groups. */ assert(group); @@ -763,6 +791,14 @@ board_capturable_rm(struct board *board, group_t group, coord_t lib, bool onesto board_trait_queue(board, lib); #endif +#ifdef BOARD_PAT3 + int fn__i = 0; + foreach_neighbor(board, lib, { + board->pat3[lib] &= ~((group_at(board, c) == group) << (16 + 3 - fn__i)); + fn__i++; + }); +#endif + #ifdef WANT_BOARD_C /* Update the list of capturable groups. */ for (int i = 0; i < board->clen; i++) { @@ -934,6 +970,13 @@ board_remove_stone(struct board *board, group_t group, coord_t c) board_group_addlib(board, g, coord); }); +#ifdef BOARD_PAT3 + /* board_hash_update() might have seen the freed up point as able + * to capture another group in atari that only after the loop + * above gained enough liberties. Reset pat3 again. */ + board->pat3[c] = pattern3_hash(board, c); +#endif + if (DEBUGL(6)) fprintf(stderr, "pushing free move [%d]: %d,%d\n", board->flen, coord_x(c, board), coord_y(c, board)); board->f[board->flen++] = c; @@ -1050,15 +1093,15 @@ next_from_lib:; } } -#ifdef BOARD_TRAITS if (gi_to->libs == 1) { + coord_t lib = board_group_info(board, group_to).lib[0]; +#ifdef BOARD_TRAITS enum stone capturing_color = stone_other(board_at(board, group_to)); assert(capturing_color == S_BLACK || capturing_color == S_WHITE); /* Our group is currently in atari; make sure we properly * count in even the neighbors from the other group in the * capturable counter. */ - coord_t lib = board_group_info(board, group_to).lib[0]; foreach_neighbor(board, lib, { if (DEBUGL(8) && group_at(board, c) == group_from) fprintf(stderr, "%s[%d] cap bump\n", coord2sstr(lib, board), trait_at(board, lib, capturing_color).cap); @@ -1076,8 +1119,21 @@ next_from_lib:; board_trait_queue(board, c); }); } - } #endif +#ifdef BOARD_PAT3 + if (gi_from->libs == 1) { + /* We removed group_from from capturable groups, + * therefore switching the atari flag off. + * We need to set it again since group_to is also + * capturable. */ + int fn__i = 0; + foreach_neighbor(board, lib, { + board->pat3[lib] |= (group_at(board, c) == group_from) << (16 + 3 - fn__i); + fn__i++; + }); + } +#endif + } coord_t last_in_group; foreach_in_group(board, group_from) { @@ -1212,6 +1268,8 @@ board_play_outside(struct board *board, struct move *m, int f) struct move ko = { pass, S_NONE }; board->ko = ko; + check_pat3_consistency(board, coord); + return group; } @@ -1309,6 +1367,8 @@ board_play_in_eye(struct board *board, struct move *m, int f) board_symmetry_update(board, &board->symmetry, coord); board->ko = ko; + check_pat3_consistency(board, coord); + return !!group; } diff --git a/board.h b/board.h index cf1e0ad..7d621f5 100644 --- a/board.h +++ b/board.h @@ -67,7 +67,7 @@ typedef uint64_t hash_t; /* XXX: This really belongs in pattern3.h, unfortunately that would mean * a dependency hell. */ -typedef uint16_t hash3_t; // 3x3 pattern hash +typedef uint32_t hash3_t; // 3x3 pattern hash /* Note that "group" is only chain of stones that is solidly diff --git a/pattern3.c b/pattern3.c index 19c322a..cf68fd0 100644 --- a/pattern3.c +++ b/pattern3.c @@ -23,19 +23,25 @@ pattern_record(struct pattern3s *p, char *str, hash3_t pat, int fixed_color) static int pat_vmirror(hash3_t pat) { - /* V mirror pattern; reverse order of 3-2-3 chunks */ - return ((pat & 0xfc00) >> 10) | (pat & 0x03c0) | ((pat & 0x003f) << 10); + /* V mirror pattern; reverse order of 3-2-3 color chunks and + * 1-2-1 atari chunks */ + return ((pat & 0xfc00) >> 10) | (pat & 0x03c0) | ((pat & 0x003f) << 10) + | ((pat & 0x80000) >> 3) | (pat & 0x60000) | ((pat & 0x10000) << 3); } static int pat_hmirror(hash3_t pat) { - /* H mirror pattern; reverse order of 2-bit values within the chunks */ + /* H mirror pattern; reverse order of 2-bit values within the chunks, + * and the 2-bit middle atari chunk. */ #define rev3(p) ((p >> 4) | (p & 0xc) | ((p & 0x3) << 4)) #define rev2(p) ((p >> 2) | ((p & 0x3) << 2)) return (rev3((pat & 0xfc00) >> 10) << 10) | (rev2((pat & 0x03c0) >> 6) << 6) - | rev3((pat & 0x003f)); + | rev3((pat & 0x003f)) + | ((pat & 0x20000) << 1) + | ((pat & 0x40000) >> 1) + | (pat & 0x90000); #undef rev3 #undef rev2 } @@ -44,10 +50,14 @@ static int pat_90rot(hash3_t pat) { /* Rotate by 90 degrees: - * 5 6 7 7 4 2 - * 3 4 -> 6 1 - * 0 1 2 5 3 0 */ + * 5 6 7 3 7 4 2 2 + * 3 4 1 2 -> 6 1 -> 3 0 + * 0 1 2 0 5 3 0 1 */ /* I'm too lazy to optimize this :) */ + + int p2 = 0; + + /* Stone info */ int vals[8]; for (int i = 0; i < 8; i++) vals[i] = (pat >> (i * 2)) & 0x3; @@ -55,9 +65,20 @@ pat_90rot(hash3_t pat) vals2[0] = vals[5]; vals2[1] = vals[3]; vals2[2] = vals[0]; vals2[3] = vals[6]; vals2[4] = vals[1]; vals2[5] = vals[7]; vals2[6] = vals[4]; vals2[7] = vals[2]; - int p2 = 0; for (int i = 0; i < 8; i++) p2 |= vals2[i] << (i * 2); + + /* Atari info */ + int avals[4]; + for (int i = 0; i < 4; i++) + vals[i] = (pat >> (16 + i)) & 0x1; + int avals2[4]; + avals2[3] = avals[2]; + avals2[1] = avals[3]; avals2[2] = avals[0]; + avals2[0] = avals[1]; + for (int i = 0; i < 4; i++) + p2 |= avals2[i] << (16 + i); + return p2; } @@ -81,8 +102,10 @@ pattern_gen(struct pattern3s *p, hash3_t pat, char *src, int srclen, int fixed_c for (; srclen > 0; src++, srclen--) { if (srclen == 5) continue; + static const int ataribits[] = { -1, 0, -1, 1, 2, -1, 3, -1 }; int patofs = (srclen > 5 ? srclen - 1 : srclen) - 1; switch (*src) { + /* Wildcards. */ case '?': *src = '.'; pattern_gen(p, pat, src, srclen, fixed_color); *src = 'X'; pattern_gen(p, pat, src, srclen, fixed_color); @@ -102,9 +125,60 @@ pattern_gen(struct pattern3s *p, hash3_t pat, char *src, int srclen, int fixed_c *src = '#'; pattern_gen(p, pat, src, srclen, fixed_color); *src = 'o'; // for future recursions return; + + case 'X': + *src = 'Y'; pattern_gen(p, pat, src, srclen, fixed_color); + if (ataribits[patofs] >= 0) + *src = '|'; pattern_gen(p, pat, src, srclen, fixed_color); + *src = 'X'; // for future recursions + return; + case 'O': + *src = 'Q'; pattern_gen(p, pat, src, srclen, fixed_color); + if (ataribits[patofs] >= 0) + *src = '@'; pattern_gen(p, pat, src, srclen, fixed_color); + *src = 'O'; // for future recursions + return; + + case 'y': + *src = '.'; pattern_gen(p, pat, src, srclen, fixed_color); + *src = '|'; pattern_gen(p, pat, src, srclen, fixed_color); + *src = 'O'; pattern_gen(p, pat, src, srclen, fixed_color); + *src = '#'; pattern_gen(p, pat, src, srclen, fixed_color); + *src = 'y'; // for future recursions + return; + case 'q': + *src = '.'; pattern_gen(p, pat, src, srclen, fixed_color); + *src = '@'; pattern_gen(p, pat, src, srclen, fixed_color); + *src = 'X'; pattern_gen(p, pat, src, srclen, fixed_color); + *src = '#'; pattern_gen(p, pat, src, srclen, fixed_color); + *src = 'q'; // for future recursions + return; + + case '=': + *src = '.'; pattern_gen(p, pat, src, srclen, fixed_color); + *src = 'Y'; pattern_gen(p, pat, src, srclen, fixed_color); + *src = 'O'; pattern_gen(p, pat, src, srclen, fixed_color); + *src = '#'; pattern_gen(p, pat, src, srclen, fixed_color); + *src = '='; // for future recursions + return; + case '0': + *src = '.'; pattern_gen(p, pat, src, srclen, fixed_color); + *src = 'Q'; pattern_gen(p, pat, src, srclen, fixed_color); + *src = 'X'; pattern_gen(p, pat, src, srclen, fixed_color); + *src = '#'; pattern_gen(p, pat, src, srclen, fixed_color); + *src = '0'; // for future recursions + return; + + /* Atoms. */ case '.': /* 0 */ break; - case 'X': pat |= S_BLACK << (patofs * 2); break; - case 'O': pat |= S_WHITE << (patofs * 2); break; + case 'Y': pat |= S_BLACK << (patofs * 2); break; + case 'Q': pat |= S_WHITE << (patofs * 2); break; + case '|': assert(ataribits[patofs] >= 0); + pat |= (S_BLACK << (patofs * 2)) | (1 << (16 + ataribits[patofs])); + break; + case '@': assert(ataribits[patofs] >= 0); + pat |= (S_WHITE << (patofs * 2)) | (1 << (16 + ataribits[patofs])); + break; case '#': pat |= S_OFFBOARD << (patofs * 2); break; } } diff --git a/pattern3.h b/pattern3.h index cdef9f0..a76a647 100644 --- a/pattern3.h +++ b/pattern3.h @@ -11,8 +11,11 @@ struct board; struct move; -/* hash3_t pattern: 8*2 bits - * (ignore middle point, 2 bits (color) per intersection) */ +/* hash3_t pattern: ignore middle point, 2 bits per intersection (color) + * plus 1 bit per each direct neighbor => 8*2 + 4 bits. Bitmap point order: + * 7 6 5 b + * 4 3 a 9 + * 2 1 0 8 */ /* Value bit 0: black pattern; bit 1: white pattern */ /* XXX: See for hash3_t typedef. */ @@ -27,7 +30,7 @@ struct pattern3s { * is going to change very soon! */ /* In case of a collision, following hash entries are * used. value==0 indicated an unoccupied hash entry. */ -#define pattern3_hash_bits 16 +#define pattern3_hash_bits 19 #define pattern3_hash_size (1 << pattern3_hash_bits) #define pattern3_hash_mask (pattern3_hash_size - 1) struct pattern2p hash[pattern3_hash_size]; @@ -37,6 +40,10 @@ struct pattern3s { * X: black; O: white; .: empty; #: edge * x: !black; o: !white; ?: any * + * |/=: black in atari/anything but black in atari + * @/0: white in atari + * Y/y: black notin atari; Q/q: white notin atari + * * extra X: pattern valid only for one side; * middle point ignored. */ @@ -61,6 +68,7 @@ pattern3_hash(struct board *b, coord_t c) { hash3_t pat = 0; int x = coord_x(c, b), y = coord_y(c, b); + /* Stone info. */ pat |= (board_atxy(b, x - 1, y - 1) << 14) | (board_atxy(b, x, y - 1) << 12) | (board_atxy(b, x + 1, y - 1) << 10); @@ -69,6 +77,13 @@ pattern3_hash(struct board *b, coord_t c) pat |= (board_atxy(b, x - 1, y + 1) << 4) | (board_atxy(b, x, y + 1) << 2) | (board_atxy(b, x + 1, y + 1)); + /* Atari info. */ +#define atari_atxy(b, x, y) (group_atxy(b, x, y) && board_group_info(b, group_atxy(b, x, y)).libs == 1) + pat |= (atari_atxy(b, x, y - 1) << 19); + pat |= (atari_atxy(b, x - 1, y) << 18) + | (atari_atxy(b, x + 1, y) << 17); + pat |= (atari_atxy(b, x, y + 1) << 16); +#undef atari_atxy return pat; } @@ -90,7 +105,7 @@ static inline hash3_t pattern3_reverse(hash3_t pat) { /* Reverse color assignment - achieved by swapping odd and even bits */ - return ((pat >> 1) & 0x5555) | ((pat & 0x5555) << 1); + return ((pat >> 1) & 0x5555) | ((pat & 0x5555) << 1) | (pat & 0xf0000); } #endif diff --git a/patternsp.c b/patternsp.c index 17d72b1..5212f93 100644 --- a/patternsp.c +++ b/patternsp.c @@ -421,6 +421,10 @@ hash_store: static const int p3bits[] = { -1, 1, 6, 3, 4, 0, 2, 5, 7 }; +/* XXX: Spatial patterns do not carry the atari informations; + * we just ignore it when converting to spatial, and assume "no atari" + * when converting from spatial. */ + static hash_t pattern3_to_spatial(int r, hash3_t pat3) { -- 2.11.4.GIT