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 "liberty.h" | |
27 | #include "patterns.h" | |
28 | #include "random.h" | |
29 | ||
30 | /* ================================================================ */ | |
31 | /* Set up fixed placement handicap stones for black side */ | |
32 | /* ================================================================ */ | |
33 | ||
34 | ||
35 | /* Handicap stones are set up according to the following diagrams: | |
36 | * | |
37 | * 2 stones: 3 stones: | |
38 | * | |
39 | * A B C D E F G H J A B C D E F G H J | |
40 | * 9 . . . . . . . . . 9 9 . . . . . . . . . 9 | |
41 | * 8 . . . . . . . . . 8 8 . . . . . . . . . 8 | |
42 | * 7 . . + . . . X . . 7 7 . . X . . . X . . 7 | |
43 | * 6 . . . . . . . . . 6 6 . . . . . . . . . 6 | |
44 | * 5 . . . . + . . . . 5 5 . . . . + . . . . 5 | |
45 | * 4 . . . . . . . . . 4 4 . . . . . . . . . 4 | |
46 | * 3 . . X . . . + . . 3 3 . . X . . . + . . 3 | |
47 | * 2 . . . . . . . . . 2 2 . . . . . . . . . 2 | |
48 | * 1 . . . . . . . . . 1 1 . . . . . . . . . 1 | |
49 | * A B C D E F G H J A B C D E F G H J | |
50 | * | |
51 | * 4 stones: 5 stones: | |
52 | * | |
53 | * A B C D E F G H J A B C D E F G H J | |
54 | * 9 . . . . . . . . . 9 9 . . . . . . . . . 9 | |
55 | * 8 . . . . . . . . . 8 8 . . . . . . . . . 8 | |
56 | * 7 . . X . . . X . . 7 7 . . X . . . X . . 7 | |
57 | * 6 . . . . . . . . . 6 6 . . . . . . . . . 6 | |
58 | * 5 . . . . + . . . . 5 5 . . . . X . . . . 5 | |
59 | * 4 . . . . . . . . . 4 4 . . . . . . . . . 4 | |
60 | * 3 . . X . . . X . . 3 3 . . X . . . X . . 3 | |
61 | * 2 . . . . . . . . . 2 2 . . . . . . . . . 2 | |
62 | * 1 . . . . . . . . . 1 1 . . . . . . . . . 1 | |
63 | * A B C D E F G H J A B C D E F G H J | |
64 | * | |
65 | * 6 stones: 7 stones: | |
66 | * | |
67 | * A B C D E F G H J A B C D E F G H J | |
68 | * 9 . . . . . . . . . 9 9 . . . . . . . . . 9 | |
69 | * 8 . . . . . . . . . 8 8 . . . . . . . . . 8 | |
70 | * 7 . . X . . . X . . 7 7 . . X . . . X . . 7 | |
71 | * 6 . . . . . . . . . 6 6 . . . . . . . . . 6 | |
72 | * 5 . . X . + . X . . 5 5 . . X . X . X . . 5 | |
73 | * 4 . . . . . . . . . 4 4 . . . . . . . . . 4 | |
74 | * 3 . . X . . . X . . 3 3 . . X . . . X . . 3 | |
75 | * 2 . . . . . . . . . 2 2 . . . . . . . . . 2 | |
76 | * 1 . . . . . . . . . 1 1 . . . . . . . . . 1 | |
77 | * A B C D E F G H J A B C D E F G H J | |
78 | * | |
79 | * 8 stones: 9 stones: | |
80 | * | |
81 | * A B C D E F G H J A B C D E F G H J | |
82 | * 9 . . . . . . . . . 9 9 . . . . . . . . . 9 | |
83 | * 8 . . . . . . . . . 8 8 . . . . . . . . . 8 | |
84 | * 7 . . X . X . X . . 7 7 . . X . X . X . . 7 | |
85 | * 6 . . . . . . . . . 6 6 . . . . . . . . . 6 | |
86 | * 5 . . X . + . X . . 5 5 . . X . X . X . . 5 | |
87 | * 4 . . . . . . . . . 4 4 . . . . . . . . . 4 | |
88 | * 3 . . X . X . X . . 3 3 . . X . X . X . . 3 | |
89 | * 2 . . . . . . . . . 2 2 . . . . . . . . . 2 | |
90 | * 1 . . . . . . . . . 1 1 . . . . . . . . . 1 | |
91 | * A B C D E F G H J A B C D E F G H J | |
92 | * | |
93 | * For odd-sized boards larger than 9x9, the same pattern is followed, | |
94 | * except that the edge stones are moved to the fourth line for 13x13 | |
95 | * boards and larger. | |
96 | * | |
97 | * For even-sized boards at least 8x8, only the four first diagrams | |
98 | * are used, because there is no way to place the center stones | |
99 | * symmetrically. As for odd-sized boards, the edge stones are moved | |
100 | * to the fourth line for boards larger than 11x11. | |
101 | * | |
102 | * At most four stones are placed on 7x7 boards too (this size may or | |
103 | * may not be supported by the rest of the engine). No handicap stones | |
104 | * are ever placed on smaller boards. | |
105 | * | |
106 | * Notice that this function only deals with fixed handicap placement. | |
107 | * Larger handicaps can be added by free placement if the used | |
108 | * interface supports it. | |
109 | */ | |
110 | ||
111 | ||
112 | /* This table contains the (coded) positions of the stones. | |
113 | * 2 maps to 2 or 3, depending on board size | |
114 | * 0 maps to center | |
115 | * -ve numbers map to board_size - number | |
116 | * | |
117 | * The stones are placed in this order, *except* if there are | |
118 | * 5 or 7 stones, in which case center ({0, 0}) is placed, and | |
119 | * then as for 4 or 6. | |
120 | */ | |
121 | ||
122 | static const int places[][2] = { | |
123 | ||
124 | {2, -2}, {-2, 2}, {2, 2}, {-2, -2}, /* first 4 are easy */ | |
125 | /* for 5, {0,0} is explicitly placed */ | |
126 | ||
127 | {0, 2}, {0, -2}, /* for 6 these two are placed */ | |
128 | /* for 7, {0,0} is explicitly placed */ | |
129 | ||
130 | {2, 0}, {-2, 0}, /* for 8, these two are placed */ | |
131 | ||
132 | {0, 0}, /* finally tengen for 9 */ | |
133 | }; | |
134 | ||
135 | ||
136 | /* | |
137 | * Sets up fixed handicap placement stones, returning the number of | |
138 | * placed handicap stones and also setting the global variable | |
139 | * handicap to the same value. | |
140 | */ | |
141 | ||
142 | int | |
143 | place_fixed_handicap(int desired_handicap) | |
144 | { | |
145 | int r; | |
146 | int max_handicap; | |
147 | int remaining_stones; | |
148 | int three = board_size > 11 ? 3 : 2; | |
149 | int mid = board_size/2; | |
150 | ||
151 | /* A handicap of 1 just means that B plays first, no komi. | |
152 | * Black is not told where to play the first stone so no handicap | |
153 | * is set. | |
154 | */ | |
155 | if (desired_handicap < 2) { | |
156 | handicap = 0; | |
157 | return 0; | |
158 | } | |
159 | ||
160 | if ((board_size % 2 == 1) && (board_size >= 9)) | |
161 | max_handicap = 9; | |
162 | else if (board_size >= 7) | |
163 | max_handicap = 4; | |
164 | else | |
165 | max_handicap = 0; | |
166 | ||
167 | /* It's up to the caller of this function to notice if the handicap | |
168 | * was too large for fixed placement and act upon that. | |
169 | */ | |
170 | if (desired_handicap > max_handicap) | |
171 | handicap = max_handicap; | |
172 | else | |
173 | handicap = desired_handicap; | |
174 | ||
175 | remaining_stones = handicap; | |
176 | /* special cases: 5 and 7 */ | |
177 | if (desired_handicap == 5 || desired_handicap == 7) { | |
178 | add_stone(POS(mid, mid), BLACK); | |
179 | remaining_stones--; | |
180 | } | |
181 | ||
182 | for (r = 0; r < remaining_stones; r++) { | |
183 | int i = places[r][0]; | |
184 | int j = places[r][1]; | |
185 | ||
186 | /* Translate the encoded values to board co-ordinates. */ | |
187 | if (i == 2) | |
188 | i = three; /* 2 or 3 */ | |
189 | else if (i == 0) | |
190 | i = mid; | |
191 | else if (i == -2) | |
192 | i = board_size - 1 - three; | |
193 | ||
194 | if (j == 2) | |
195 | j = three; | |
196 | else if (j == 0) | |
197 | j = mid; | |
198 | else if (j == -2) | |
199 | j = board_size - 1 - three; | |
200 | ||
201 | add_stone(POS(i, j), BLACK); | |
202 | } | |
203 | ||
204 | return handicap; | |
205 | } | |
206 | ||
207 | ||
208 | /* ================================================================ */ | |
209 | /* Set up free placement handicap stones for black side */ | |
210 | /* ================================================================ */ | |
211 | ||
212 | ||
213 | /* | |
214 | * Sets up free handicap placement stones, returning the number of | |
215 | * placed handicap stones. | |
216 | */ | |
217 | ||
218 | static int remaining_handicap_stones = -1; | |
219 | static int total_handicap_stones = -1; | |
220 | ||
221 | static int find_free_handicap_pattern(void); | |
222 | static void free_handicap_callback(int anchor, int color, | |
223 | struct pattern *pattern, | |
224 | int ll, void *data); | |
225 | ||
226 | /* | |
227 | * Sets up free placement handicap stones, returning the number of | |
228 | * placed handicap stones and also setting the global variable | |
229 | * handicap to the same value. | |
230 | */ | |
231 | int | |
232 | place_free_handicap(int desired_handicap) | |
233 | { | |
234 | gg_assert(desired_handicap == 0 || desired_handicap >= 2); | |
235 | ||
236 | if (desired_handicap == 0) { | |
237 | handicap = 0; | |
238 | return 0; | |
239 | } | |
240 | ||
241 | total_handicap_stones = desired_handicap; | |
242 | remaining_handicap_stones = desired_handicap; | |
243 | ||
244 | /* First place black stones in the four corners to enable the | |
245 | * pattern matching scheme. | |
246 | */ | |
247 | add_stone(POS(0, 0), BLACK); | |
248 | add_stone(POS(0, board_size - 1), BLACK); | |
249 | add_stone(POS(board_size - 1, 0), BLACK); | |
250 | add_stone(POS(board_size - 1, board_size - 1), BLACK); | |
251 | ||
252 | /* Find and place free handicap stones by pattern matching. */ | |
253 | while (remaining_handicap_stones > 0) { | |
254 | if (!find_free_handicap_pattern()) | |
255 | break; | |
256 | } | |
257 | ||
258 | /* Remove the artificial corner stones. */ | |
259 | remove_stone(POS(0, 0)); | |
260 | remove_stone(POS(0, board_size - 1)); | |
261 | remove_stone(POS(board_size - 1, 0)); | |
262 | remove_stone(POS(board_size - 1, board_size - 1)); | |
263 | ||
264 | /* Find and place additional free handicap stones by the aftermath | |
265 | * algorithm. | |
266 | */ | |
267 | while (remaining_handicap_stones > 0) { | |
268 | int move; | |
269 | /* Call genmove_conservative() in order to prepare the engine for | |
270 | * an aftermath_genmove() call. We discard the genmove result. | |
271 | */ | |
272 | genmove_conservative(BLACK, NULL); | |
273 | move = aftermath_genmove(BLACK, 0, NULL); | |
274 | if (move != PASS_MOVE) { | |
275 | add_stone(move, BLACK); | |
276 | remaining_handicap_stones--; | |
277 | } | |
278 | else | |
279 | break; | |
280 | } | |
281 | ||
282 | /* Set handicap to the number of actually placed stones. */ | |
283 | handicap = desired_handicap - remaining_handicap_stones; | |
284 | ||
285 | /* Reset these to invalid values, so that improper use of handicap | |
286 | * helper functions can be detected. | |
287 | */ | |
288 | total_handicap_stones = -1; | |
289 | remaining_handicap_stones = -1; | |
290 | ||
291 | return handicap; | |
292 | } | |
293 | ||
294 | struct handicap_match { | |
295 | int value; | |
296 | int anchor; | |
297 | struct pattern *pattern; | |
298 | int ll; | |
299 | }; | |
300 | ||
301 | #define MAX_HANDICAP_MATCHES 40 | |
302 | ||
303 | static struct handicap_match handicap_matches[MAX_HANDICAP_MATCHES]; | |
304 | static int number_of_matches; | |
305 | ||
306 | static int | |
307 | find_free_handicap_pattern() | |
308 | { | |
309 | int k; | |
310 | int highest_value = -1; | |
311 | int sum_values = 0; | |
312 | int r; | |
313 | int anchor; | |
314 | struct pattern *pattern; | |
315 | int ll; | |
316 | int move; | |
317 | ||
318 | number_of_matches = 0; | |
319 | matchpat(free_handicap_callback, BLACK, &handipat_db, NULL, NULL); | |
320 | ||
321 | if (number_of_matches == 0) | |
322 | return 0; | |
323 | ||
324 | /* Find the highest value among the matched patterns. */ | |
325 | for (k = 0; k < number_of_matches; k++) | |
326 | if (highest_value < handicap_matches[k].value) | |
327 | highest_value = handicap_matches[k].value; | |
328 | ||
329 | /* Replace the values by 2^(value - highest_value + 10) and compute | |
330 | * the sum of these values. Fractional values are discarded. | |
331 | */ | |
332 | for (k = 0; k < number_of_matches; k++) { | |
333 | if (handicap_matches[k].value < highest_value - 10) | |
334 | handicap_matches[k].value = 0; | |
335 | else | |
336 | handicap_matches[k].value = 1 << (handicap_matches[k].value | |
337 | - highest_value + 10); | |
338 | sum_values += handicap_matches[k].value; | |
339 | } | |
340 | ||
341 | /* Pick a random number between 0 and sum_values. Don't bother with | |
342 | * the fact that lower numbers will tend to be very slightly | |
343 | * overrepresented. | |
344 | */ | |
345 | r = gg_rand() % sum_values; | |
346 | ||
347 | /* Find the chosen pattern. */ | |
348 | for (k = 0; k < number_of_matches; k++) { | |
349 | r -= handicap_matches[k].value; | |
350 | if (r < 0) | |
351 | break; | |
352 | } | |
353 | ||
354 | /* Place handicap stones according to pattern k. */ | |
355 | anchor = handicap_matches[k].anchor; | |
356 | pattern = handicap_matches[k].pattern; | |
357 | ll = handicap_matches[k].ll; | |
358 | ||
359 | /* Pick up the location of the move */ | |
360 | move = AFFINE_TRANSFORM(pattern->move_offset, ll, anchor); | |
361 | add_stone(move, BLACK); | |
362 | remaining_handicap_stones--; | |
363 | ||
364 | /* Add stones at all '!' in the pattern. */ | |
365 | for (k = 0; k < pattern->patlen; k++) { | |
366 | if (pattern->patn[k].att == ATT_not) { | |
367 | int pos = AFFINE_TRANSFORM(pattern->patn[k].offset, ll, anchor); | |
368 | add_stone(pos, BLACK); | |
369 | remaining_handicap_stones--; | |
370 | } | |
371 | } | |
372 | ||
373 | return 1; | |
374 | } | |
375 | ||
376 | static void | |
377 | free_handicap_callback(int anchor, int color, struct pattern *pattern, | |
378 | int ll, void *data) | |
379 | { | |
380 | int r = -1; | |
381 | int k; | |
382 | int number_of_stones = 1; | |
383 | ||
384 | /* Pick up the location of the move */ | |
385 | int move = AFFINE_TRANSFORM(pattern->move_offset, ll, anchor); | |
386 | ||
387 | UNUSED(data); | |
388 | ||
389 | /* Check how many stones are placed by the pattern. This must not be | |
390 | * larger than the number of remaining handicap stones. | |
391 | */ | |
392 | for (k = 0; k < pattern->patlen; k++) { | |
393 | if (pattern->patn[k].att == ATT_not) | |
394 | number_of_stones++; | |
395 | } | |
396 | if (number_of_stones > remaining_handicap_stones) | |
397 | return; | |
398 | ||
399 | /* If the pattern has a constraint, call the autohelper to see | |
400 | * if the pattern must be rejected. | |
401 | */ | |
402 | if (pattern->autohelper_flag & HAVE_CONSTRAINT) { | |
403 | if (!pattern->autohelper(ll, move, color, 0)) | |
404 | return; | |
405 | } | |
406 | ||
407 | if (number_of_matches < MAX_HANDICAP_MATCHES) { | |
408 | r = number_of_matches; | |
409 | number_of_matches++; | |
410 | } | |
411 | else { | |
412 | int least_value = handicap_matches[0].value + 1; | |
413 | for (k = 0; k < number_of_matches; k++) { | |
414 | if (handicap_matches[k].value < least_value) { | |
415 | r = k; | |
416 | least_value = handicap_matches[k].value; | |
417 | } | |
418 | } | |
419 | } | |
420 | gg_assert(r >= 0 && r < MAX_HANDICAP_MATCHES); | |
421 | handicap_matches[r].value = pattern->value; | |
422 | handicap_matches[r].anchor = anchor; | |
423 | handicap_matches[r].pattern = pattern; | |
424 | handicap_matches[r].ll = ll; | |
425 | } | |
426 | ||
427 | int | |
428 | free_handicap_remaining_stones() | |
429 | { | |
430 | gg_assert(remaining_handicap_stones >= 0); | |
431 | return remaining_handicap_stones; | |
432 | } | |
433 | ||
434 | int | |
435 | free_handicap_total_stones() | |
436 | { | |
437 | gg_assert(total_handicap_stones >= 0); | |
438 | return total_handicap_stones; | |
439 | } | |
440 | ||
441 | /* | |
442 | * Local Variables: | |
443 | * tab-width: 8 | |
444 | * c-basic-offset: 2 | |
445 | * End: | |
446 | */ |