1 /* Playout player based on probability distribution generated over
2 * the available moves. */
4 /* We use the ELO-based (Coulom, 2007) approach, where each board
5 * feature (matched pattern, self-atari, capture, MC owner?, ...)
6 * is pre-assigned "playing strength" (gamma).
8 * Then, the problem of choosing a move is basically a team
9 * competition in ELO terms - each spot is represented by a team
10 * of features appearing there; the team gamma is product of feature
11 * gammas. The team gammas make for a probability distribution of
14 * We use the general pattern classifier that will find the features
15 * for us, and external datasets that can be harvested from a set
16 * of game records (see the HACKING file for details): patterns.spat
17 * as a dictionary of spatial stone configurations, and patterns.gamma
18 * with strengths of particular features. */
29 #include "patternsp.h"
31 #include "playout/elo.h"
34 #include "uct/prior.h"
36 #define PLDEBUGL(n) DEBUGL_(p->debug_level, n)
39 /* Note that the context can be shared by multiple threads! */
43 struct pattern_config pc
;
44 struct features_gamma
*fg
;
49 struct patternset choose
, assess
;
53 /* This is the core of the policy - initializes and constructs the
54 * probability distribution over the move candidates. */
57 elo_get_probdist(struct playout_policy
*p
, struct patternset
*ps
, struct board
*b
, enum stone to_play
, struct probdist
*pd
)
59 //struct elo_policy *pp = p->data;
62 /* First, assign per-point probabilities. */
64 for (int f
= 0; f
< b
->flen
; f
++) {
65 struct move m
= { .coord
= b
->f
[f
], .color
= to_play
};
67 /* Skip pass (for now)? */
68 if (is_pass(m
.coord
)) {
70 probdist_set(pd
, f
, 0);
73 //fprintf(stderr, "<%d> %s\n", f, coord2sstr(m.coord, b));
75 /* Skip invalid moves. */
76 if (!board_is_valid_move(b
, &m
))
79 /* We shall never fill our own single-point eyes. */
80 /* XXX: In some rare situations, this prunes the best move:
81 * Bulk-five nakade with eye at 1-1 point. */
82 if (board_is_one_point_eye(b
, &m
.coord
, to_play
)) {
87 /* Each valid move starts with gamma 1. */
90 /* Some easy features: */
91 /* XXX: We just disable them for now since we call the
92 * pattern matcher; you need the gammas file. */
94 if (is_bad_selfatari(b
, to_play
, m
.coord
))
98 /* Match pattern features: */
100 pattern_match(&ps
->pc
, ps
->ps
, &p
, b
, &m
);
101 for (int i
= 0; i
< p
.n
; i
++) {
102 /* Multiply together gammas of all pattern features. */
103 float gamma
= feature_gamma(ps
->fg
, &p
.f
[i
], NULL
);
104 //char buf[256] = ""; feature2str(buf, &p.f[i]);
105 //fprintf(stderr, "<%d> %s feat %s gamma %f\n", f, coord2sstr(m.coord, b), buf, gamma);
109 probdist_set(pd
, f
, g
);
110 //fprintf(stderr, "<%d> %s %f (E %f)\n", f, coord2sstr(m.coord, b), probdist_one(pd, f), pd->items[f]);
118 playout_elo_choose(struct playout_policy
*p
, struct board
*b
, enum stone to_play
)
121 struct probdist
*pd
= &b
->prob
[to_play
- 1];
122 /* Make sure ko-prohibited move does not get picked. */
123 if (!is_pass(b
->ko
.coord
)) {
124 assert(b
->ko
.color
== to_play
);
125 probdist_set(pd
, b
->ko
.coord
, 0);
127 /* TODO: FEAT_CONTIGUITY support. */
129 coord_t c
= pd
->total
>= PROBDIST_EPSILON
? probdist_pick(pd
) : pass
;
130 /* Repair the damage. */
131 if (!is_pass(b
->ko
.coord
))
132 board_gamma_update(b
, b
->ko
.coord
, to_play
);
135 struct elo_policy
*pp
= p
->data
;
136 float pdi
[b
->flen
]; memset(pdi
, 0, sizeof(pdi
));
137 struct probdist pd
= { .n
= b
->flen
, .items
= pdi
, .total
= 0 };
138 elo_get_probdist(p
, &pp
->choose
, b
, to_play
, &pd
);
139 int f
= probdist_pick(&pd
);
145 playout_elo_assess(struct playout_policy
*p
, struct prior_map
*map
, int games
)
147 struct elo_policy
*pp
= p
->data
;
148 float pdi
[map
->b
->flen
]; memset(pdi
, 0, sizeof(pdi
));
149 struct probdist pd
= { .n
= map
->b
->flen
, .items
= pdi
, .total
= 0 };
152 moves
= elo_get_probdist(p
, &pp
->assess
, map
->b
, map
->to_play
, &pd
);
154 /* It is a question how to transform the gamma to won games; we use
155 * a naive approach currently, but not sure how well it works. */
156 /* TODO: Try sqrt(p), atan(p)/pi*2. */
158 for (int f
= 0; f
< map
->b
->flen
; f
++) {
159 coord_t c
= map
->b
->f
[f
];
160 if (!map
->consider
[c
])
162 add_prior_value(map
, c
, probdist_one(&pd
, f
) / probdist_total(&pd
), games
);
167 playout_elo_done(struct playout_policy
*p
)
169 struct elo_policy
*pp
= p
->data
;
170 features_gamma_done(pp
->choose
.fg
);
171 features_gamma_done(pp
->assess
.fg
);
175 struct playout_policy
*
176 playout_elo_init(char *arg
, struct board
*b
)
178 struct playout_policy
*p
= calloc(1, sizeof(*p
));
179 struct elo_policy
*pp
= calloc(1, sizeof(*pp
));
181 p
->choose
= playout_elo_choose
;
182 p
->assess
= playout_elo_assess
;
183 p
->done
= playout_elo_done
;
185 const char *gammafile
= features_gamma_filename
;
186 /* Some defaults based on the table in Remi Coulom's paper. */
187 pp
->selfatari
= 0.06;
189 struct pattern_config pc
= DEFAULT_PATTERN_CONFIG
;
193 char *optspec
, *next
= arg
;
196 next
+= strcspn(next
, ":");
197 if (*next
) { *next
++ = 0; } else { *next
= 0; }
199 char *optname
= optspec
;
200 char *optval
= strchr(optspec
, '=');
201 if (optval
) *optval
++ = 0;
203 if (!strcasecmp(optname
, "selfatari") && optval
) {
204 pp
->selfatari
= atof(optval
);
205 } else if (!strcasecmp(optname
, "gammafile") && optval
) {
206 /* patterns.gamma by default. We use this,
207 * and need also ${gammafile}f (e.g.
208 * patterns.gammaf) for fast (MC) features. */
209 gammafile
= strdup(optval
);
210 } else if (!strcasecmp(optname
, "xspat") && optval
) {
211 /* xspat==0: don't match spatial features
212 * xspat==1: match *only* spatial features */
213 xspat
= atoi(optval
);
215 fprintf(stderr
, "playout-elo: Invalid policy argument %s or missing value\n", optname
);
221 pc
.spat_dict
= spatial_dict_init(false);
224 pp
->assess
.fg
= features_gamma_init(&pp
->assess
.pc
, gammafile
);
225 memcpy(pp
->assess
.ps
, PATTERN_SPEC_MATCHALL
, sizeof(pattern_spec
));
226 for (int i
= 0; i
< FEAT_MAX
; i
++)
227 if ((xspat
== 0 && i
== FEAT_SPATIAL
) || (xspat
== 1 && i
!= FEAT_SPATIAL
))
228 pp
->assess
.ps
[i
] = 0;
230 /* In playouts, we need to operate with much smaller set of features
231 * in order to keep reasonable speed. */
232 /* TODO: Configurable. */ /* TODO: Tune. */
233 pp
->choose
.pc
= FAST_PATTERN_CONFIG
;
234 pp
->choose
.pc
.spat_dict
= pc
.spat_dict
;
235 char cgammafile
[256]; strcpy(stpcpy(cgammafile
, gammafile
), "f");
236 pp
->choose
.fg
= features_gamma_init(&pp
->choose
.pc
, cgammafile
);
237 memcpy(pp
->choose
.ps
, PATTERN_SPEC_MATCHFAST
, sizeof(pattern_spec
));
238 for (int i
= 0; i
< FEAT_MAX
; i
++)
239 if ((xspat
== 0 && i
== FEAT_SPATIAL
) || (xspat
== 1 && i
!= FEAT_SPATIAL
))
240 pp
->choose
.ps
[i
] = 0;
243 b
->gamma
= pp
->choose
.fg
;