dumpdebug
[pachi.git] / montecarlo / montecarlo.c
blob82744d38fffcdd3b3a4ede4bab07c78ca039b814
1 #include <assert.h>
2 #include <stdio.h>
3 #include <stdlib.h>
4 #include <string.h>
6 #include "board.h"
7 #include "engine.h"
8 #include "move.h"
9 #include "playout/moggy.h"
10 #include "playout/old.h"
11 #include "playout/light.h"
12 #include "montecarlo/internal.h"
13 #include "montecarlo/montecarlo.h"
14 #include "playout.h"
17 /* This is simple monte-carlo engine. It plays MC_GAMES random games from the
18 * current board and records win/loss ratio for each first move. The move with
19 * the biggest number of winning games gets played. */
20 /* Note that while the library is based on New Zealand rules, this engine
21 * returns moves according to Chinese rules. Thus, it does not return suicide
22 * moves. It of course respects positional superko too. */
24 /* Pass me arguments like a=b,c=d,...
25 * Supported arguments:
26 * debug[=DEBUG_LEVEL] 1 is the default; more means more debugging prints
27 * games=MC_GAMES number of random games to play
28 * gamelen=MC_GAMELEN maximal length of played random game
29 * playout={old,moggy}[:playout_params]
33 #define MC_GAMES 40000
34 #define MC_GAMELEN 400
37 /* FIXME: Cutoff rule for simulations. Currently we are so fast that this
38 * simply does not matter; even 100000 simulations are fast enough to
39 * play 5 minutes S.D. on 19x19 and anything more sounds too ridiculous
40 * already. */
41 /* FIXME: We cannot handle seki. Any good ideas are welcome. A possibility is
42 * to consider 'pass' among the moves, but this seems tricky. */
45 void
46 board_stats_print(struct board *board, struct move_stat *moves, FILE *f)
48 fprintf(f, "\n ");
49 int x, y;
50 char asdf[] = "ABCDEFGHJKLMNOPQRSTUVWXYZ";
51 for (x = 1; x < board_size(board) - 1; x++)
52 fprintf(f, "%c ", asdf[x - 1]);
53 fprintf(f, "\n +-");
54 for (x = 1; x < board_size(board) - 1; x++)
55 fprintf(f, "-----");
56 fprintf(f, "+\n");
57 for (y = board_size(board) - 2; y >= 1; y--) {
58 fprintf(f, "%2d | ", y);
59 for (x = 1; x < board_size(board) - 1; x++)
60 if (moves[y * board_size(board) + x].games)
61 fprintf(f, "%0.2f ", (float) moves[y * board_size(board) + x].wins / moves[y * board_size(board) + x].games);
62 else
63 fprintf(f, "---- ");
64 fprintf(f, "| ");
65 for (x = 1; x < board_size(board) - 1; x++)
66 fprintf(f, "%4d ", moves[y * board_size(board) + x].games);
67 fprintf(f, "|\n");
69 fprintf(f, " +-");
70 for (x = 1; x < board_size(board) - 1; x++)
71 fprintf(f, "-----");
72 fprintf(f, "+\n");
76 static coord_t *
77 montecarlo_genmove(struct engine *e, struct board *b, enum stone color)
79 struct montecarlo *mc = e->data;
81 /* resign when the hope for win vanishes */
82 coord_t top_coord = resign;
83 float top_ratio = mc->resign_ratio;
85 /* We use [0] for pass. Normally, this is an inaccessible corner
86 * of board margin. */
87 struct move_stat moves[board_size2(b)];
88 memset(moves, 0, sizeof(moves));
90 int losses = 0;
91 int i, superko = 0, good_games = 0;
92 for (i = 0; i < mc->games; i++) {
93 assert(!b->superko_violation);
95 struct board b2;
96 board_copy(&b2, b);
98 coord_t coord;
99 board_play_random(&b2, color, &coord);
100 if (!is_pass(coord) && !group_at(&b2, coord)) {
101 /* Multi-stone suicide. We play chinese rules,
102 * so we can't consider this. (Note that we
103 * unfortunately still consider this in playouts.) */
104 if (DEBUGL(4)) {
105 fprintf(stderr, "SUICIDE DETECTED at %d,%d:\n", coord_x(coord, b), coord_y(coord, b));
106 board_print(b, stderr);
108 continue;
111 if (DEBUGL(3))
112 fprintf(stderr, "[%d,%d color %d] playing random game\n", coord_x(coord, b), coord_y(coord, b), color);
114 int result = play_random_game(&b2, color, mc->gamelen, NULL, mc->playout);
116 board_done_noalloc(&b2);
118 if (result < 0) {
119 /* Superko. We just ignore this playout.
120 * And play again. */
121 if (unlikely(superko > 2 * mc->games)) {
122 /* Uhh. Triple ko, or something? */
123 if (MCDEBUGL(0))
124 fprintf(stderr, "SUPERKO LOOP. I will pass. Did we hit triple ko?\n");
125 goto pass_wins;
127 /* This playout didn't count; we should not
128 * disadvantage moves that lead to a superko.
129 * And it is supposed to be rare. */
130 i--, superko++;
131 continue;
134 if (MCDEBUGL(3))
135 fprintf(stderr, "\tresult for other player: %d\n", result);
137 int pos = is_pass(coord) ? 0 : coord_raw(coord);
139 good_games++;
140 moves[pos].games++;
142 losses += result;
143 moves[pos].wins += 1 - result;
145 if (unlikely(!losses && i == mc->loss_threshold)) {
146 /* We played out many games and didn't lose once yet.
147 * This game is over. */
148 break;
152 if (!good_games) {
153 /* No moves to try??? */
154 if (MCDEBUGL(0)) {
155 fprintf(stderr, "OUT OF MOVES! I will pass. But how did this happen?\n");
156 board_print(b, stderr);
158 pass_wins:
159 top_coord = pass; top_ratio = 0.5;
160 goto move_found;
163 foreach_point(b) {
164 if (b->moves < 3) {
165 /* Simple heuristic: avoid opening too low. Do not
166 * play on second or first line as first white or
167 * first two black moves.*/
168 if (coord_x(c, b) < 3 || coord_x(c, b) > board_size(b) - 4
169 || coord_y(c, b) < 3 || coord_y(c, b) > board_size(b) - 4)
170 continue;
173 float ratio = (float) moves[coord_raw(c)].wins / moves[coord_raw(c)].games;
174 /* Since pass is [0,0], we will pass only when we have nothing
175 * better to do. */
176 if (ratio >= top_ratio) {
177 top_ratio = ratio;
178 top_coord = coord_raw(c) == 0 ? pass : c;
180 } foreach_point_end;
182 if (MCDEBUGL(2)) {
183 board_stats_print(b, moves, stderr);
186 move_found:
187 if (MCDEBUGL(1))
188 fprintf(stderr, "*** WINNER is %d,%d with score %1.4f (%d games, %d superko)\n", coord_x(top_coord, b), coord_y(top_coord, b), top_ratio, i, superko);
190 return coord_copy(top_coord);
194 struct montecarlo *
195 montecarlo_state_init(char *arg)
197 struct montecarlo *mc = calloc(1, sizeof(struct montecarlo));
199 mc->debug_level = 1;
200 mc->games = MC_GAMES;
201 mc->gamelen = MC_GAMELEN;
203 if (arg) {
204 char *optspec, *next = arg;
205 while (*next) {
206 optspec = next;
207 next += strcspn(next, ",");
208 if (*next) { *next++ = 0; } else { *next = 0; }
210 char *optname = optspec;
211 char *optval = strchr(optspec, '=');
212 if (optval) *optval++ = 0;
214 if (!strcasecmp(optname, "debug")) {
215 if (optval)
216 mc->debug_level = atoi(optval);
217 else
218 mc->debug_level++;
219 } else if (!strcasecmp(optname, "games") && optval) {
220 mc->games = atoi(optval);
221 } else if (!strcasecmp(optname, "gamelen") && optval) {
222 mc->gamelen = atoi(optval);
223 } else if (!strcasecmp(optname, "playout") && optval) {
224 char *playoutarg = strchr(optval, ':');
225 if (playoutarg)
226 *playoutarg++ = 0;
227 if (!strcasecmp(optval, "old")) {
228 mc->playout = playout_old_init(playoutarg);
229 } else if (!strcasecmp(optval, "moggy")) {
230 mc->playout = playout_moggy_init(playoutarg);
231 } else if (!strcasecmp(optval, "light")) {
232 mc->playout = playout_light_init(playoutarg);
233 } else {
234 fprintf(stderr, "MonteCarlo: Invalid playout policy %s\n", optval);
236 } else {
237 fprintf(stderr, "MonteCarlo: Invalid engine argument %s or missing value\n", optname);
242 if (!mc->playout)
243 mc->playout = playout_light_init(NULL);
244 mc->playout->debug_level = mc->debug_level;
246 mc->resign_ratio = 0.1; /* Resign when most games are lost. */
247 mc->loss_threshold = mc->games / 10; /* Stop reading if no loss encountered in first n games. */
249 return mc;
253 struct engine *
254 engine_montecarlo_init(char *arg)
256 struct montecarlo *mc = montecarlo_state_init(arg);
257 struct engine *e = calloc(1, sizeof(struct engine));
258 e->name = "MonteCarlo Engine";
259 e->comment = "I'm playing in Monte Carlo. When we both pass, I will consider all the stones on the board alive. If you are reading this, write 'yes'. Please bear with me at the game end, I need to fill the whole board; if you help me, we will both be happier. Filling the board will not lose points (NZ rules).";
260 e->genmove = montecarlo_genmove;
261 e->data = mc;
263 return e;