1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\
2 * This is GNU Go, a Go program. Contact gnugo@gnu.org, or see *
3 * http://www.gnu.org/software/gnugo/ for more information. *
4 * *
5 * Copyright 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, *
6 * 2008 and 2009 by the Free Software Foundation. *
7 * *
8 * This program is free software; you can redistribute it and/or *
9 * modify it under the terms of the GNU General Public License as *
10 * published by the Free Software Foundation - version 3 or *
11 * (at your option) any later version. *
12 * *
13 * This program is distributed in the hope that it will be useful, *
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of *
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
16 * GNU General Public License in file COPYING for more details. *
17 * *
18 * You should have received a copy of the GNU General Public *
19 * License along with this program; if not, write to the Free *
20 * Software Foundation, Inc., 51 Franklin Street, Fifth Floor, *
21 * Boston, MA 02111, USA. *
22 \* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
23
24 #include "gnugo.h"
25
26 #include <stdio.h>
27 #include <stdlib.h>
28
29 #include "liberty.h"
30 #include "patterns.h"
31 #include "random.h"
32
33 #include "sgftree.h"
34
35
36 /* Pointless to do fuseki database pattern matching after this number
37 * of stones have been placed on the board.
38 *
39 * Notice that we are not talking of the move number here but the
40 * number of stones actually residing on the board. This does in
41 * particular include handicap stones.
42 */
43 #define MAX_FUSEKI_DATABASE_STONES 30
44
45
46 #define UPPER_LEFT 0
47 #define UPPER_RIGHT 1
48 #define LOWER_LEFT 2
49 #define LOWER_RIGHT 3
50
51 /* Global variables remembering which symmetries the position has. */
52 static int horizontally_symmetric; /* symmetry with respect to K column */
53 static int vertically_symmetric; /* symmetry with respect to 10 row */
54 static int diagonally_symmetric; /* with respect to diagonal from UR to LL */
55
56 /* This value must be lower than the value for an ongoing joseki.
57 * (Gets multiplied with board_size / 19.)
58 */
59 #define EMPTY_CORNER_VALUE 25
60
61 /* check if region from i1, j1 to i2, j2 is open */
62
63 static int
openregion(int i1,int i2,int j1,int j2)64 openregion(int i1, int i2, int j1, int j2)
65 {
66 int x, y;
67
68 if (i1 > i2)
69 return openregion(i2, i1, j1, j2);
70 if (j1 > j2)
71 return openregion(i1, i2, j2, j1);
72
73 /* Disregard parts of the region off the board. This is convenient
74 * in order not to have to special-case tiny boards. It also secures
75 * against potential reading outside the board[] array boundaries.
76 */
77 if (i1 < 0)
78 i1 = 0;
79 if (j1 < 0)
80 j1 = 0;
81 if (i2 >= board_size)
82 i2 = board_size - 1;
83 if (j2 >= board_size)
84 j2 = board_size - 1;
85
86 for (x = i1; x <= i2; x++)
87 for (y = j1; y <= j2; y++)
88 if (BOARD(x, y) != EMPTY)
89 return 0;
90 return 1;
91 }
92
93 /* This function sets the global variables indicating symmetries of the
94 * position. (Important for etiquette.)
95 */
96 static void
set_symmetries(void)97 set_symmetries(void)
98 {
99 int i, j;
100 horizontally_symmetric = 1;
101 vertically_symmetric = 1;
102 diagonally_symmetric = 1;
103 for (i = 0; i < board_size
104 && (vertically_symmetric || horizontally_symmetric
105 || diagonally_symmetric); i++)
106 for (j = 0; j < board_size; j++) {
107 if (board[POS(i, j)] != board[POS(i, board_size - 1 - j)])
108 horizontally_symmetric = 0;
109 if (board[POS(i, j)] != board[POS(board_size - 1 - i, j)])
110 vertically_symmetric = 0;
111 if (board[POS(i, j)]
112 != board[POS(board_size - 1 - j, board_size - 1 - i)])
113 diagonally_symmetric = 0;
114 }
115 }
116
117 /* The corner moves. */
118
119 static int corners[][2] =
120 {
121 {3, 3},
122 {3, 4},
123 {4, 3},
124 {4, 4},
125 {5, 3},
126 {3, 5},
127 {5, 4},
128 {4, 5},
129 };
130
131 /* Relative weights for different corner moves at different board
132 sizes. */
133
134 /* up to 11x11 */
135 static int small_board[] =
136 {
137 50, /* 3-3 */
138 18, /* 3-4 */
139 17, /* 4-3 */
140 15, /* 4-4 */
141 0, /* 5-3 */
142 0, /* 3-5 */
143 0, /* 5-4 */
144 0, /* 4-5 */
145 };
146
147 /* 12x12 to 15x15 */
148 static int medium_board[] =
149 {
150 30, /* 3-3 */
151 20, /* 3-4 */
152 20, /* 4-3 */
153 22, /* 4-4 */
154 2, /* 5-3 */
155 2, /* 3-5 */
156 2, /* 5-4 */
157 2, /* 4-5 */
158 };
159
160 /* 16x16 and larger */
161 static int large_board[] =
162 {
163 15, /* 3-3 */
164 15, /* 3-4 */
165 15, /* 4-3 */
166 35, /* 4-4 */
167 5, /* 5-3 */
168 5, /* 3-5 */
169 5, /* 5-4 */
170 5, /* 4-5 */
171 };
172
173 static void
choose_corner_move(int corner,int * m,int * n)174 choose_corner_move(int corner, int *m, int *n)
175 {
176 int *table = 0;
177 int sum_of_weights = 0;
178 int i;
179 int q;
180
181 if (board_size <= 11)
182 table = small_board;
183 else if (board_size <= 15)
184 table = medium_board;
185 else
186 table = large_board;
187
188 for (i = 0; i < 8; i++)
189 sum_of_weights += table[i];
190
191 q = gg_rand() % sum_of_weights;
192 for (i = 0; i < 8; i++) {
193 q -= table[i];
194 if (q < 0)
195 break;
196 }
197
198 *m = corners[i][0];
199 *n = corners[i][1];
200
201 switch (corner) {
202 case UPPER_LEFT:
203 *m = *m - 1;
204 *n = *n - 1;
205 break;
206 case UPPER_RIGHT:
207 *m = *m - 1;
208 *n = board_size - *n;
209 break;
210 case LOWER_LEFT:
211 *m = board_size - *m;
212 *n = *n - 1;
213 break;
214 case LOWER_RIGHT:
215 *m = board_size - *m;
216 *n = board_size - *n;
217 break;
218 }
219 }
220
221
222 /* Announce move, but check for politeness first. */
223 static void
announce_move(int move,int value,int color)224 announce_move(int move, int value, int color)
225 {
226 int i, j;
227 /* This shouldn't happen. */
228 if (board[move] != EMPTY)
229 return;
230
231 /* Politeness: Black plays in lower right half of upper right corner first.
232 * White plays in upper left half of lower left corner first.
233 * (Not sure whether this is correct for handicap games. Is this an
234 * urgent FIXME? :-) )
235 */
236 if (horizontally_symmetric) {
237 i = I(move);
238 j = J(move);
239 if ((2 * j < board_size - 1) ^ (color == WHITE))
240 move = POS(i, board_size - 1 - j);
241 }
242 if (vertically_symmetric) {
243 i = I(move);
244 j = J(move);
245 if ((2 * i > board_size - 1) ^ (color == WHITE))
246 move = POS(board_size - 1 - i, j);
247 }
248 if (diagonally_symmetric) {
249 i = I(move);
250 j = J(move);
251 if ((board_size - 1 - j > i) ^ (color == WHITE))
252 move = POS(board_size - 1 - j, board_size - 1 - i);
253 }
254
255 if (set_minimum_move_value(move, value))
256 TRACE("Fuseki Player suggests %1m with value %d\n", move, value);
257 }
258
259
260 /* Storage for values collected during pattern matching. */
261 static int fuseki_moves[MAX_BOARD * MAX_BOARD];
262 static int fuseki_value[MAX_BOARD * MAX_BOARD];
263 static int num_fuseki_moves;
264 static int fuseki_total_value;
265
266 /* Callback for fuseki database pattern matching. */
267 static void
fuseki_callback(int move,struct fullboard_pattern * pattern,int ll)268 fuseki_callback(int move, struct fullboard_pattern *pattern, int ll)
269 {
270 TRACE("Fuseki database move at %1m with relative weight %d, pattern %s+%d\n",
271 move, pattern->value, pattern->name, ll);
272
273 /* Store coordinates and relative weight for the found move. */
274 fuseki_moves[num_fuseki_moves] = move;
275 fuseki_value[num_fuseki_moves] = pattern->value;
276 fuseki_total_value += pattern->value;
277 num_fuseki_moves++;
278 }
279
280 /* Full board matching in database for fuseki moves. Return 1 if any
281 * pattern found.
282 */
283 static int
search_fuseki_database(int color)284 search_fuseki_database(int color)
285 {
286 struct fullboard_pattern *database;
287 int q;
288 int k;
289
290 /* Disable matching after a certain number of stones are placed on
291 * the board.
292 */
293 if (stones_on_board(BLACK | WHITE) > MAX_FUSEKI_DATABASE_STONES)
294 return 0;
295
296 /* We only have databases for 9x9, 13x13 and 19x19. */
297 if (board_size == 9)
298 database = fuseki9;
299 else if (board_size == 13)
300 database = fuseki13;
301 else if (board_size == 19)
302 database = fuseki19;
303 else
304 return 0;
305
306 /* Do the matching. */
307 num_fuseki_moves = 0;
308 fuseki_total_value = 0;
309 fullboard_matchpat(fuseki_callback, color, database);
310
311 /* No match. */
312 if (num_fuseki_moves == 0)
313 return 0;
314
315 /* Choose randomly with respect to relative weights for matched moves.
316 */
317 q = gg_rand() % fuseki_total_value;
318 for (k = 0; k < num_fuseki_moves; k++) {
319 q -= fuseki_value[k];
320 if (q < 0)
321 break;
322 }
323
324 gg_assert(k < num_fuseki_moves);
325 /* Give this move an arbitrary value of 75. The actual value doesn't
326 * matter much since the intention is that we should play this move
327 * whatever the rest of the analysis thinks.
328 */
329 announce_move(fuseki_moves[k], 75, color);
330
331 /* Also make sure the other considered moves can be seen in the
332 * traces and in the output file.
333 */
334 for (k = 0; k < num_fuseki_moves; k++)
335 set_minimum_move_value(fuseki_moves[k], 74);
336
337 return 1;
338 }
339
340 /* Generate move in empty corner or in middle of small board.*/
341 void
fuseki(int color)342 fuseki(int color)
343 {
344 int i = -1;
345 int j = -1;
346 int width; /* Side of the open region required in the corner. */
347 int empty_corner_value = EMPTY_CORNER_VALUE * board_size/19;
348
349 /* Return immediately if --disable_fuseki option used. */
350 if (disable_fuseki)
351 return;
352
353 set_symmetries();
354
355 /* Search in fuseki database unless disabled by --nofusekidb option. */
356 if (fusekidb && search_fuseki_database(color))
357 return;
358
359 /* On 9x9, only play open corners after the first move if nothing
360 * else useful is found.
361 */
362 if (board_size == 9 && stones_on_board(color) > 0)
363 empty_corner_value = 5;
364
365 if (board_size <= 11) {
366 /* For boards of size 11x11 or smaller we first go for the center point. */
367 int middle = board_size/2;
368 if (openregion(middle-2, middle+2, middle-2, middle+2)) {
369 announce_move(POS(middle, middle), 45, color);
370 }
371 }
372
373 if (board_size < 9)
374 return;
375
376 if (board_size >= 18)
377 width = 8;
378 else if (board_size == 9)
379 width = 5;
380 else
381 width = board_size/2;
382
383 if (openregion(0, width-1, board_size-width, board_size-1)) {
384 choose_corner_move(UPPER_RIGHT, &i, &j);
385 announce_move(POS(i, j), empty_corner_value, color);
386 }
387
388 if (openregion(board_size-width, board_size-1, 0, width-1)) {
389 choose_corner_move(LOWER_LEFT, &i, &j);
390 announce_move(POS(i, j), empty_corner_value, color);
391 }
392 if (openregion(board_size-width, board_size-1,
393 board_size-width, board_size-1)) {
394 choose_corner_move(LOWER_RIGHT, &i, &j);
395 announce_move(POS(i, j), empty_corner_value, color);
396 }
397
398 if (openregion(0, width-1, 0, width-1)) {
399 choose_corner_move(UPPER_LEFT, &i, &j);
400 announce_move(POS(i, j), empty_corner_value, color);
401 }
402 }
403
404 /*
405 * Local Variables:
406 * tab-width: 8
407 * c-basic-offset: 2
408 * End:
409 */
410
411