From 80067a55c55e0494e06bf44c1eb99df08671e48a Mon Sep 17 00:00:00 2001 From: Petr Baudis Date: Sat, 13 Feb 2010 23:47:45 +0100 Subject: [PATCH] Board BOARD_GAMMA: Support for incremental probability distribution setup --- board.c | 56 ++++++++++++++++++++++++++++++++++++++++++++++++++++---- board.h | 17 +++++++++++++++++ pattern.h | 6 ++++++ 3 files changed, 75 insertions(+), 4 deletions(-) diff --git a/board.c b/board.c index 4158f11..8b83e8b 100644 --- a/board.c +++ b/board.c @@ -15,6 +15,9 @@ #ifdef BOARD_PAT3 #include "pattern3.h" #endif +#ifdef BOARD_GAMMA +#include "pattern.h" +#endif bool random_pass = false; @@ -83,8 +86,13 @@ board_copy(struct board *b2, struct board *b1) #else int tsize = 0; #endif - void *x = malloc(bsize + gsize + fsize + psize + nsize + hsize + gisize + csize + ssize + p3size + tsize); - memcpy(x, b1->b, bsize + gsize + fsize + psize + nsize + hsize + gisize + csize + ssize + p3size + tsize); +#ifdef BOARD_GAMMA + int pbsize = board_size2(b2) * sizeof(*b2->prob[0].items); +#else + int pbsize = 0; +#endif + void *x = malloc(bsize + gsize + fsize + psize + nsize + hsize + gisize + csize + ssize + p3size + tsize + pbsize * 2); + memcpy(x, b1->b, bsize + gsize + fsize + psize + nsize + hsize + gisize + csize + ssize + p3size + tsize + pbsize * 2); b2->b = x; x += bsize; b2->g = x; x += gsize; b2->f = x; x += fsize; @@ -104,6 +112,10 @@ board_copy(struct board *b2, struct board *b1) #ifdef BOARD_TRAITS b2->t = x; x += tsize; #endif +#ifdef BOARD_GAMMA + b2->prob[0].items = x; x += pbsize; + b2->prob[1].items = x; x += pbsize; +#endif return b2; } @@ -160,8 +172,13 @@ board_resize(struct board *board, int size) #else int tsize = 0; #endif - void *x = malloc(bsize + gsize + fsize + psize + nsize + hsize + gisize + csize + ssize + p3size + tsize); - memset(x, 0, bsize + gsize + fsize + psize + nsize + hsize + gisize + csize + ssize + p3size + tsize); +#ifdef BOARD_GAMMA + int pbsize = board_size2(board) * sizeof(*board->prob[0].items); +#else + int pbsize = 0; +#endif + void *x = malloc(bsize + gsize + fsize + psize + nsize + hsize + gisize + csize + ssize + p3size + tsize + pbsize * 2); + memset(x, 0, bsize + gsize + fsize + psize + nsize + hsize + gisize + csize + ssize + p3size + tsize + pbsize * 2); board->b = x; x += bsize; board->g = x; x += gsize; board->f = x; x += fsize; @@ -181,6 +198,10 @@ board_resize(struct board *board, int size) #ifdef BOARD_TRAITS board->t = x; x += tsize; #endif +#ifdef BOARD_GAMMA + board->prob[0].items = x; x += pbsize; + board->prob[1].items = x; x += pbsize; +#endif } void @@ -289,6 +310,9 @@ board_clear(struct board *board) trait_at(board, c, S_WHITE).safe = true; } foreach_point_end; #endif +#ifdef BOARD_GAMMA + board->prob[0].n = board->prob[1].n = board_size2(board); +#endif } @@ -371,6 +395,26 @@ board_print(struct board *board, FILE *f) } +/* Update the probability distribution we maintain incrementally. */ +static void +board_gamma_update(struct board *board, coord_t coord, enum stone color) +{ +#ifdef BOARD_GAMMA + assert(board->gamma); + float value = 1.0f; + /* We just quickly replicate the general pattern matcher stuff + * here in the most bare-bone way. */ + if (trait_at(board, coord, color).cap) + value *= board->gamma->gamma[FEAT_CAPTURE][0]; + if (trait_at(board, coord, stone_other(color)).cap + && trait_at(board, coord, color).safe) + value *= board->gamma->gamma[FEAT_AESCAPE][0]; + if (!trait_at(board, coord, color).safe) + value *= board->gamma->gamma[FEAT_SELFATARI][0]; + probdist_set(&board->prob[color], coord, value); +#endif +} + /* Recompute some of the traits for given point from scratch. Note that * some traits are updated incrementally elsewhere. */ static void @@ -386,6 +430,8 @@ board_trait_recompute(struct board *board, coord_t coord) trait_at(board, coord, S_WHITE).cap, trait_at(board, coord, S_WHITE).safe); } #endif + board_gamma_update(board, coord, S_BLACK); + board_gamma_update(board, coord, S_WHITE); } /* Update board hash with given coordinate. */ @@ -429,6 +475,8 @@ board_hash_update(struct board *board, coord_t coord, enum stone color) assert(0); } #endif + board_gamma_update(board, c, S_BLACK); + board_gamma_update(board, c, S_WHITE); } foreach_8neighbor_end; #endif } diff --git a/board.h b/board.h index 9c1bdbc..ffd4352 100644 --- a/board.h +++ b/board.h @@ -7,8 +7,11 @@ #include "stone.h" #include "move.h" +#include "probdist.h" #include "util.h" +struct features_gamma; + /* The board implementation has bunch of optional features. * Turn them on below: */ @@ -23,6 +26,7 @@ #define BOARD_PAT3 // incremental 3x3 pattern codes //#define BOARD_TRAITS 1 // incremental point traits (see struct btraits) +//#define BOARD_GAMMA 1 // incremental probability distribution (requires BOARD_TRAITS, BOARD_PAT3) /* Allow board_play_random_move() to return pass even when @@ -160,6 +164,13 @@ struct board { /* The information is only valid for empty points. */ struct btraits (*t)[2]; #endif +#ifdef BOARD_GAMMA + /* Relative probabilities of moves being played next, computed by + * multiplying gammas of the appropriate pattern features based on + * pat3 and traits (see pattern.h). The probability distribution + * is maintained over the full board grid. */ + struct probdist prob[2]; +#endif /* Group information - indexed by gid (which is coord of base group stone) */ struct group *gi; @@ -192,6 +203,12 @@ struct board { * not be set outside of it. */ void *ps; +#ifdef BOARD_GAMMA + /* Gamma values for probability distribution; user must setup + * this pointer before any move is played. */ + struct features_gamma *gamma; +#endif + /* --- PRIVATE DATA --- */ diff --git a/pattern.h b/pattern.h index 7ad2d4d..e0c3ee5 100644 --- a/pattern.h +++ b/pattern.h @@ -12,6 +12,12 @@ * pattern _feature_. Another features may be is-a-selfatari, is-a-capture, * number of liberties, distance from last move, etc. */ +/* ! NOTE NOTE NOTE ! We provide infrastructure for matching patterns, but we + * also replicate the most bare-bone part of it for tiny subset of features + * in board.c:board_gamma_update() for fast incremental probability + * distribution maintenance. Aside of using the constants defined here, that + * implementation is completely independent and does not call back here. */ + /* Each feature is represented by its id and an optional 32-bit payload; * when matching, discrete (id,payload) pairs are considered. */ -- 2.11.4.GIT