Commit | Line | Data |
---|---|---|
7eeb782e AT |
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 | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 |