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
place_fixed_handicap(int desired_handicap)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
place_free_handicap(int desired_handicap)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
find_free_handicap_pattern()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
free_handicap_callback(int anchor,int color,struct pattern * pattern,int ll,void * data)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
free_handicap_remaining_stones()428 free_handicap_remaining_stones()
429 {
430 gg_assert(remaining_handicap_stones >= 0);
431 return remaining_handicap_stones;
432 }
433
434 int
free_handicap_total_stones()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 */
447