File: | src/games/gomoku/pickmove.c |
Warning: | line 1223, column 11 Dereference of null pointer |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
1 | /* $OpenBSD: pickmove.c,v 1.16 2016/01/08 21:38:33 mestre Exp $ */ | |||
2 | /* | |||
3 | * Copyright (c) 1994 | |||
4 | * The Regents of the University of California. All rights reserved. | |||
5 | * | |||
6 | * This code is derived from software contributed to Berkeley by | |||
7 | * Ralph Campbell. | |||
8 | * | |||
9 | * Redistribution and use in source and binary forms, with or without | |||
10 | * modification, are permitted provided that the following conditions | |||
11 | * are met: | |||
12 | * 1. Redistributions of source code must retain the above copyright | |||
13 | * notice, this list of conditions and the following disclaimer. | |||
14 | * 2. Redistributions in binary form must reproduce the above copyright | |||
15 | * notice, this list of conditions and the following disclaimer in the | |||
16 | * documentation and/or other materials provided with the distribution. | |||
17 | * 3. Neither the name of the University nor the names of its contributors | |||
18 | * may be used to endorse or promote products derived from this software | |||
19 | * without specific prior written permission. | |||
20 | * | |||
21 | * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND | |||
22 | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | |||
23 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE | |||
24 | * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE | |||
25 | * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL | |||
26 | * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS | |||
27 | * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) | |||
28 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT | |||
29 | * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY | |||
30 | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF | |||
31 | * SUCH DAMAGE. | |||
32 | */ | |||
33 | ||||
34 | #include <curses.h> | |||
35 | #include <limits.h> | |||
36 | #include <stdlib.h> | |||
37 | #include <string.h> | |||
38 | ||||
39 | #include "gomoku.h" | |||
40 | ||||
41 | #define BITS_PER_INT(sizeof(int) * 8) (sizeof(int) * CHAR_BIT8) | |||
42 | #define MAPSZ(((19 +2)*(19 +1)+1) / (sizeof(int) * 8)) (BAREA((19 +2)*(19 +1)+1) / BITS_PER_INT(sizeof(int) * 8)) | |||
43 | ||||
44 | #define BIT_SET(a, b)((a)[(b)/(sizeof(int) * 8)] |= (1 << ((b) % (sizeof(int ) * 8)))) ((a)[(b)/BITS_PER_INT(sizeof(int) * 8)] |= (1 << ((b) % BITS_PER_INT(sizeof(int) * 8)))) | |||
45 | #define BIT_CLR(a, b)((a)[(b)/(sizeof(int) * 8)] &= ~(1 << ((b) % (sizeof (int) * 8)))) ((a)[(b)/BITS_PER_INT(sizeof(int) * 8)] &= ~(1 << ((b) % BITS_PER_INT(sizeof(int) * 8)))) | |||
46 | #define BIT_TEST(a, b)((a)[(b)/(sizeof(int) * 8)] & (1 << ((b) % (sizeof( int) * 8)))) ((a)[(b)/BITS_PER_INT(sizeof(int) * 8)] & (1 << ((b) % BITS_PER_INT(sizeof(int) * 8)))) | |||
47 | ||||
48 | struct combostr *hashcombos[FAREA(19*(19 -4) + (19 -4)*(19 -4) + 19*(19 -4) + (19 -4)*(19 -4))]; /* hash list for finding duplicates */ | |||
49 | struct combostr *sortcombos; /* combos at higher levels */ | |||
50 | int combolen; /* number of combos in sortcombos */ | |||
51 | int nextcolor; /* color of next move */ | |||
52 | int elistcnt; /* count of struct elist allocated */ | |||
53 | int combocnt; /* count of struct combostr allocated */ | |||
54 | int forcemap[MAPSZ(((19 +2)*(19 +1)+1) / (sizeof(int) * 8))]; /* map for blocking <1,x> combos */ | |||
55 | int tmpmap[MAPSZ(((19 +2)*(19 +1)+1) / (sizeof(int) * 8))]; /* map for blocking <1,x> combos */ | |||
56 | int nforce; /* count of opponent <1,x> combos */ | |||
57 | ||||
58 | int | |||
59 | pickmove(int us) | |||
60 | { | |||
61 | struct spotstr *sp, *sp1, *sp2; | |||
62 | union comboval *Ocp, *Tcp; | |||
63 | int m; | |||
64 | ||||
65 | /* first move is easy */ | |||
66 | if (movenum == 1) | |||
67 | return (PT(K,10)((10) + (19 +1) * (10))); | |||
68 | ||||
69 | /* initialize all the board values */ | |||
70 | for (sp = &board[PT(T,20)((19) + (19 +1) * (20))]; --sp >= &board[PT(A,1)((1) + (19 +1) * (1))]; ) { | |||
71 | sp->s_combo[BLACK0].s = MAXCOMBO0x600 + 1; | |||
72 | sp->s_combo[WHITE1].s = MAXCOMBO0x600 + 1; | |||
73 | sp->s_level[BLACK0] = 255; | |||
74 | sp->s_level[WHITE1] = 255; | |||
75 | sp->s_nforce[BLACK0] = 0; | |||
76 | sp->s_nforce[WHITE1] = 0; | |||
77 | sp->s_flg &= ~(FFLAGALL0x000F00 | MFLAGALL0x00F000); | |||
78 | } | |||
79 | nforce = 0; | |||
80 | memset(forcemap, 0, sizeof(forcemap)); | |||
81 | ||||
82 | /* compute new values */ | |||
83 | nextcolor = us; | |||
84 | scanframes(BLACK0); | |||
85 | scanframes(WHITE1); | |||
86 | ||||
87 | /* find the spot with the highest value */ | |||
88 | for (sp = sp1 = sp2 = &board[PT(T,19)((19) + (19 +1) * (19))]; --sp >= &board[PT(A,1)((1) + (19 +1) * (1))]; ) { | |||
89 | if (sp->s_occ != EMPTY2) | |||
90 | continue; | |||
91 | if (debug && (sp->s_combo[BLACK0].c.a == 1 || | |||
92 | sp->s_combo[WHITE1].c.a == 1)) { | |||
93 | snprintf(fmtbuf, sizeof fmtbuf, | |||
94 | "- %s %x/%d %d %x/%d %d %d", stoc(sp - board), | |||
95 | sp->s_combo[BLACK0].s, sp->s_level[BLACK0], | |||
96 | sp->s_nforce[BLACK0], | |||
97 | sp->s_combo[WHITE1].s, sp->s_level[WHITE1], | |||
98 | sp->s_nforce[WHITE1], | |||
99 | sp->s_wval); | |||
100 | dlog(fmtbuf); | |||
101 | } | |||
102 | /* pick the best black move */ | |||
103 | if (better(sp, sp1, BLACK0)) | |||
104 | sp1 = sp; | |||
105 | /* pick the best white move */ | |||
106 | if (better(sp, sp2, WHITE1)) | |||
107 | sp2 = sp; | |||
108 | } | |||
109 | ||||
110 | if (debug) { | |||
111 | snprintf(fmtbuf, sizeof fmtbuf, | |||
112 | "B %s %x/%d %d %x/%d %d %d", | |||
113 | stoc(sp1 - board), | |||
114 | sp1->s_combo[BLACK0].s, sp1->s_level[BLACK0], | |||
115 | sp1->s_nforce[BLACK0], | |||
116 | sp1->s_combo[WHITE1].s, sp1->s_level[WHITE1], | |||
117 | sp1->s_nforce[WHITE1], sp1->s_wval); | |||
118 | dlog(fmtbuf); | |||
119 | snprintf(fmtbuf, sizeof fmtbuf, | |||
120 | "W %s %x/%d %d %x/%d %d %d", | |||
121 | stoc(sp2 - board), | |||
122 | sp2->s_combo[WHITE1].s, sp2->s_level[WHITE1], | |||
123 | sp2->s_nforce[WHITE1], | |||
124 | sp2->s_combo[BLACK0].s, sp2->s_level[BLACK0], | |||
125 | sp2->s_nforce[BLACK0], sp2->s_wval); | |||
126 | dlog(fmtbuf); | |||
127 | /* | |||
128 | * Check for more than one force that can't | |||
129 | * all be blocked with one move. | |||
130 | */ | |||
131 | sp = (us == BLACK0) ? sp2 : sp1; | |||
132 | m = sp - board; | |||
133 | if (sp->s_combo[!us].c.a == 1 && !BIT_TEST(forcemap, m)((forcemap)[(m)/(sizeof(int) * 8)] & (1 << ((m) % ( sizeof(int) * 8))))) | |||
134 | dlog("*** Can't be blocked"); | |||
135 | } | |||
136 | if (us == BLACK0) { | |||
137 | Ocp = &sp1->s_combo[BLACK0]; | |||
138 | Tcp = &sp2->s_combo[WHITE1]; | |||
139 | } else { | |||
140 | Tcp = &sp1->s_combo[BLACK0]; | |||
141 | Ocp = &sp2->s_combo[WHITE1]; | |||
142 | sp = sp1; | |||
143 | sp1 = sp2; | |||
144 | sp2 = sp; | |||
145 | } | |||
146 | /* | |||
147 | * Block their combo only if we have to (i.e., if they are one move | |||
148 | * away from completing a force and we don't have a force that | |||
149 | * we can complete which takes fewer moves to win). | |||
150 | */ | |||
151 | if (Tcp->c.a <= 1 && (Ocp->c.a > 1 || | |||
152 | Tcp->c.a + Tcp->c.b < Ocp->c.a + Ocp->c.b)) | |||
153 | return (sp2 - board); | |||
154 | return (sp1 - board); | |||
155 | } | |||
156 | ||||
157 | /* | |||
158 | * Return true if spot 'sp' is better than spot 'sp1' for color 'us'. | |||
159 | */ | |||
160 | int | |||
161 | better(struct spotstr *sp, struct spotstr *sp1, int us) | |||
162 | { | |||
163 | int them, s, s1; | |||
164 | ||||
165 | if (sp->s_combo[us].s < sp1->s_combo[us].s) | |||
166 | return (1); | |||
167 | if (sp->s_combo[us].s != sp1->s_combo[us].s) | |||
168 | return (0); | |||
169 | if (sp->s_level[us] < sp1->s_level[us]) | |||
170 | return (1); | |||
171 | if (sp->s_level[us] != sp1->s_level[us]) | |||
172 | return (0); | |||
173 | if (sp->s_nforce[us] > sp1->s_nforce[us]) | |||
174 | return (1); | |||
175 | if (sp->s_nforce[us] != sp1->s_nforce[us]) | |||
176 | return (0); | |||
177 | ||||
178 | them = !us; | |||
179 | s = sp - board; | |||
180 | s1 = sp1 - board; | |||
181 | if (BIT_TEST(forcemap, s)((forcemap)[(s)/(sizeof(int) * 8)] & (1 << ((s) % ( sizeof(int) * 8)))) && !BIT_TEST(forcemap, s1)((forcemap)[(s1)/(sizeof(int) * 8)] & (1 << ((s1) % (sizeof(int) * 8))))) | |||
182 | return (1); | |||
183 | if (!BIT_TEST(forcemap, s)((forcemap)[(s)/(sizeof(int) * 8)] & (1 << ((s) % ( sizeof(int) * 8)))) && BIT_TEST(forcemap, s1)((forcemap)[(s1)/(sizeof(int) * 8)] & (1 << ((s1) % (sizeof(int) * 8))))) | |||
184 | return (0); | |||
185 | if (sp->s_combo[them].s < sp1->s_combo[them].s) | |||
186 | return (1); | |||
187 | if (sp->s_combo[them].s != sp1->s_combo[them].s) | |||
188 | return (0); | |||
189 | if (sp->s_level[them] < sp1->s_level[them]) | |||
190 | return (1); | |||
191 | if (sp->s_level[them] != sp1->s_level[them]) | |||
192 | return (0); | |||
193 | if (sp->s_nforce[them] > sp1->s_nforce[them]) | |||
194 | return (1); | |||
195 | if (sp->s_nforce[them] != sp1->s_nforce[them]) | |||
196 | return (0); | |||
197 | ||||
198 | if (sp->s_wval > sp1->s_wval) | |||
199 | return (1); | |||
200 | if (sp->s_wval != sp1->s_wval) | |||
201 | return (0); | |||
202 | ||||
203 | return (arc4random() & 1); | |||
204 | } | |||
205 | ||||
206 | int curcolor; /* implicit parameter to makecombo() */ | |||
207 | int curlevel; /* implicit parameter to makecombo() */ | |||
208 | ||||
209 | /* | |||
210 | * Scan the sorted list of non-empty frames and | |||
211 | * update the minimum combo values for each empty spot. | |||
212 | * Also, try to combine frames to find more complex (chained) moves. | |||
213 | */ | |||
214 | void | |||
215 | scanframes(int color) | |||
216 | { | |||
217 | struct combostr *cbp, *ecbp; | |||
218 | struct spotstr *sp; | |||
219 | union comboval *cp; | |||
220 | struct elist *ep, *nep; | |||
221 | int i, r, d, n; | |||
222 | union comboval cb; | |||
223 | ||||
224 | curcolor = color; | |||
225 | ||||
226 | /* check for empty list of frames */ | |||
227 | cbp = sortframes[color]; | |||
228 | if (cbp == (struct combostr *)0) | |||
229 | return; | |||
230 | ||||
231 | /* quick check for four in a row */ | |||
232 | sp = &board[cbp->c_vertex]; | |||
233 | cb.s = sp->s_fval[color][d = cbp->c_dir].s; | |||
234 | if (cb.s < 0x101) { | |||
235 | d = dd[d]; | |||
236 | for (i = 5 + cb.c.b; --i >= 0; sp += d) { | |||
237 | if (sp->s_occ != EMPTY2) | |||
238 | continue; | |||
239 | sp->s_combo[color].s = cb.s; | |||
240 | sp->s_level[color] = 1; | |||
241 | } | |||
242 | return; | |||
243 | } | |||
244 | ||||
245 | /* | |||
246 | * Update the minimum combo value for each spot in the frame | |||
247 | * and try making all combinations of two frames intersecting at | |||
248 | * an empty spot. | |||
249 | */ | |||
250 | n = combolen; | |||
251 | ecbp = cbp; | |||
252 | do { | |||
253 | sp = &board[cbp->c_vertex]; | |||
254 | cp = &sp->s_fval[color][r = cbp->c_dir]; | |||
255 | d = dd[r]; | |||
256 | if (cp->c.b) { | |||
257 | /* | |||
258 | * Since this is the first spot of an open ended | |||
259 | * frame, we treat it as a closed frame. | |||
260 | */ | |||
261 | cb.c.a = cp->c.a + 1; | |||
262 | cb.c.b = 0; | |||
263 | if (cb.s < sp->s_combo[color].s) { | |||
264 | sp->s_combo[color].s = cb.s; | |||
265 | sp->s_level[color] = 1; | |||
266 | } | |||
267 | /* | |||
268 | * Try combining other frames that intersect | |||
269 | * at this spot. | |||
270 | */ | |||
271 | makecombo2(cbp, sp, 0, cb.s); | |||
272 | if (cp->s != 0x101) | |||
273 | cb.s = cp->s; | |||
274 | else if (color != nextcolor) | |||
275 | memset(tmpmap, 0, sizeof(tmpmap)); | |||
276 | sp += d; | |||
277 | i = 1; | |||
278 | } else { | |||
279 | cb.s = cp->s; | |||
280 | i = 0; | |||
281 | } | |||
282 | for (; i < 5; i++, sp += d) { /* for each spot */ | |||
283 | if (sp->s_occ != EMPTY2) | |||
284 | continue; | |||
285 | if (cp->s < sp->s_combo[color].s) { | |||
286 | sp->s_combo[color].s = cp->s; | |||
287 | sp->s_level[color] = 1; | |||
288 | } | |||
289 | if (cp->s == 0x101) { | |||
290 | sp->s_nforce[color]++; | |||
291 | if (color != nextcolor) { | |||
292 | n = sp - board; | |||
293 | BIT_SET(tmpmap, n)((tmpmap)[(n)/(sizeof(int) * 8)] |= (1 << ((n) % (sizeof (int) * 8)))); | |||
294 | } | |||
295 | } | |||
296 | /* | |||
297 | * Try combining other frames that intersect | |||
298 | * at this spot. | |||
299 | */ | |||
300 | makecombo2(cbp, sp, i, cb.s); | |||
301 | } | |||
302 | if (cp->s == 0x101 && color != nextcolor) { | |||
303 | if (nforce == 0) | |||
304 | memcpy(forcemap, tmpmap, sizeof(tmpmap)); | |||
305 | else { | |||
306 | for (i = 0; i < MAPSZ(((19 +2)*(19 +1)+1) / (sizeof(int) * 8)); i++) | |||
307 | forcemap[i] &= tmpmap[i]; | |||
308 | } | |||
309 | } | |||
310 | /* mark frame as having been processed */ | |||
311 | board[cbp->c_vertex].s_flg |= MFLAG0x001000 << r; | |||
312 | } while ((cbp = cbp->c_next) != ecbp); | |||
313 | ||||
314 | /* | |||
315 | * Try to make new 3rd level combos, 4th level, etc. | |||
316 | * Limit the search depth early in the game. | |||
317 | */ | |||
318 | d = 2; | |||
319 | while (d <= ((unsigned)(movenum + 1) >> 1) && combolen > n) { | |||
320 | if (debug) { | |||
321 | snprintf(fmtbuf, sizeof fmtbuf, | |||
322 | "%cL%d %d %d %d", "BW"[color], | |||
323 | d, combolen - n, combocnt, elistcnt); | |||
324 | dlog(fmtbuf); | |||
325 | refresh()wrefresh(stdscr); | |||
326 | } | |||
327 | n = combolen; | |||
328 | addframes(d); | |||
329 | d++; | |||
330 | } | |||
331 | ||||
332 | /* scan for combos at empty spots */ | |||
333 | for (sp = &board[PT(T,20)((19) + (19 +1) * (20))]; --sp >= &board[PT(A,1)((1) + (19 +1) * (1))]; ) { | |||
334 | for (ep = sp->s_empty; ep; ep = nep) { | |||
335 | cbp = ep->e_combo; | |||
336 | if (cbp->c_combo.s <= sp->s_combo[color].s) { | |||
337 | if (cbp->c_combo.s != sp->s_combo[color].s) { | |||
338 | sp->s_combo[color].s = cbp->c_combo.s; | |||
339 | sp->s_level[color] = cbp->c_nframes; | |||
340 | } else if (cbp->c_nframes < sp->s_level[color]) | |||
341 | sp->s_level[color] = cbp->c_nframes; | |||
342 | } | |||
343 | nep = ep->e_next; | |||
344 | free(ep); | |||
345 | elistcnt--; | |||
346 | } | |||
347 | sp->s_empty = (struct elist *)0; | |||
348 | for (ep = sp->s_nempty; ep; ep = nep) { | |||
349 | cbp = ep->e_combo; | |||
350 | if (cbp->c_combo.s <= sp->s_combo[color].s) { | |||
351 | if (cbp->c_combo.s != sp->s_combo[color].s) { | |||
352 | sp->s_combo[color].s = cbp->c_combo.s; | |||
353 | sp->s_level[color] = cbp->c_nframes; | |||
354 | } else if (cbp->c_nframes < sp->s_level[color]) | |||
355 | sp->s_level[color] = cbp->c_nframes; | |||
356 | } | |||
357 | nep = ep->e_next; | |||
358 | free(ep); | |||
359 | elistcnt--; | |||
360 | } | |||
361 | sp->s_nempty = (struct elist *)0; | |||
362 | } | |||
363 | ||||
364 | /* remove old combos */ | |||
365 | if ((cbp = sortcombos) != (struct combostr *)0) { | |||
366 | struct combostr *ncbp; | |||
367 | ||||
368 | /* scan the list */ | |||
369 | ecbp = cbp; | |||
370 | do { | |||
371 | ncbp = cbp->c_next; | |||
372 | free(cbp); | |||
373 | combocnt--; | |||
374 | } while ((cbp = ncbp) != ecbp); | |||
375 | sortcombos = (struct combostr *)0; | |||
376 | } | |||
377 | combolen = 0; | |||
378 | ||||
379 | #ifdef DEBUG | |||
380 | if (combocnt) { | |||
381 | snprintf(fmtbuf, sizeof fmtbuf, | |||
382 | "scanframes: %c combocnt %d", "BW"[color], | |||
383 | combocnt); | |||
384 | dlog(fmtbuf); | |||
385 | whatsup(0); | |||
386 | } | |||
387 | if (elistcnt) { | |||
388 | snprintf(fmtbuf, sizeof fmtbuf, | |||
389 | "scanframes: %c elistcnt %d", "BW"[color], | |||
390 | elistcnt); | |||
391 | dlog(fmtbuf); | |||
392 | whatsup(0); | |||
393 | } | |||
394 | #endif | |||
395 | } | |||
396 | ||||
397 | /* | |||
398 | * Compute all level 2 combos of frames intersecting spot 'osp' | |||
399 | * within the frame 'ocbp' and combo value 's'. | |||
400 | */ | |||
401 | void | |||
402 | makecombo2(struct combostr *ocbp, struct spotstr *osp, int off, int s) | |||
403 | { | |||
404 | struct spotstr *fsp; | |||
405 | struct combostr *ncbp; | |||
406 | int f, r, d, c; | |||
407 | int baseB, fcnt, emask, bmask, n; | |||
408 | union comboval ocb, fcb; | |||
409 | struct combostr **scbpp, *fcbp; | |||
410 | ||||
411 | /* try to combine a new frame with those found so far */ | |||
412 | ocb.s = s; | |||
413 | baseB = ocb.c.a + ocb.c.b - 1; | |||
414 | fcnt = ocb.c.a - 2; | |||
415 | emask = fcnt ? ((ocb.c.b ? 0x1E : 0x1F) & ~(1 << off)) : 0; | |||
416 | for (r = 4; --r >= 0; ) { /* for each direction */ | |||
417 | /* don't include frames that overlap in the same direction */ | |||
418 | if (r == ocbp->c_dir) | |||
419 | continue; | |||
420 | d = dd[r]; | |||
421 | /* | |||
422 | * Frame A combined with B is the same value as B combined with A | |||
423 | * so skip frames that have already been processed (MFLAG). | |||
424 | * Also skip blocked frames (BFLAG) and frames that are <1,x> | |||
425 | * since combining another frame with it isn't valid. | |||
426 | */ | |||
427 | bmask = (BFLAG0x010000 | FFLAG0x000100 | MFLAG0x001000) << r; | |||
428 | fsp = osp; | |||
429 | for (f = 0; f < 5; f++, fsp -= d) { /* for each frame */ | |||
430 | if (fsp->s_occ == BORDER3) | |||
431 | break; | |||
432 | if (fsp->s_flg & bmask) | |||
433 | continue; | |||
434 | ||||
435 | /* don't include frames of the wrong color */ | |||
436 | fcb.s = fsp->s_fval[curcolor][r].s; | |||
437 | if (fcb.c.a >= MAXA6) | |||
438 | continue; | |||
439 | ||||
440 | /* | |||
441 | * Get the combo value for this frame. | |||
442 | * If this is the end point of the frame, | |||
443 | * use the closed ended value for the frame. | |||
444 | */ | |||
445 | if (f == 0 && (fcb.c.b || fcb.s == 0x101)) { | |||
446 | fcb.c.a++; | |||
447 | fcb.c.b = 0; | |||
448 | } | |||
449 | ||||
450 | /* compute combo value */ | |||
451 | c = fcb.c.a + ocb.c.a - 3; | |||
452 | if (c > 4) | |||
453 | continue; | |||
454 | n = fcb.c.a + fcb.c.b - 1; | |||
455 | if (baseB < n) | |||
456 | n = baseB; | |||
457 | ||||
458 | /* make a new combo! */ | |||
459 | ncbp = reallocarray(NULL((void *)0), 3, sizeof(struct combostr)); | |||
460 | if (ncbp == (struct combostr *)NULL((void *)0)) | |||
461 | qlog("Memory allocation failure."); | |||
462 | scbpp = (struct combostr **)(ncbp + 1); | |||
463 | fcbp = fsp->s_frame[r]; | |||
464 | if (ocbp < fcbp) { | |||
465 | scbpp[0] = ocbp; | |||
466 | scbpp[1] = fcbp; | |||
467 | } else { | |||
468 | scbpp[0] = fcbp; | |||
469 | scbpp[1] = ocbp; | |||
470 | } | |||
471 | ncbp->c_combo.c.a = c; | |||
472 | ncbp->c_combo.c.b = n; | |||
473 | ncbp->c_link[0] = ocbp; | |||
474 | ncbp->c_link[1] = fcbp; | |||
475 | ncbp->c_linkv[0].s = ocb.s; | |||
476 | ncbp->c_linkv[1].s = fcb.s; | |||
477 | ncbp->c_voff[0] = off; | |||
478 | ncbp->c_voff[1] = f; | |||
479 | ncbp->c_vertex = osp - board; | |||
480 | ncbp->c_nframes = 2; | |||
481 | ncbp->c_dir = 0; | |||
482 | ncbp->c_frameindex = 0; | |||
483 | ncbp->c_flg = (ocb.c.b) ? C_OPEN_00x01 : 0; | |||
484 | if (fcb.c.b) | |||
485 | ncbp->c_flg |= C_OPEN_10x02; | |||
486 | ncbp->c_framecnt[0] = fcnt; | |||
487 | ncbp->c_emask[0] = emask; | |||
488 | ncbp->c_framecnt[1] = fcb.c.a - 2; | |||
489 | ncbp->c_emask[1] = ncbp->c_framecnt[1] ? | |||
490 | ((fcb.c.b ? 0x1E : 0x1F) & ~(1 << f)) : 0; | |||
491 | combocnt++; | |||
492 | ||||
493 | if (c == 1 && debug > 1) { | |||
494 | snprintf(fmtbuf, sizeof fmtbuf, | |||
495 | "%c c %d %d m %x %x o %d %d", | |||
496 | "bw"[curcolor], | |||
497 | ncbp->c_framecnt[0], ncbp->c_framecnt[1], | |||
498 | ncbp->c_emask[0], ncbp->c_emask[1], | |||
499 | ncbp->c_voff[0], ncbp->c_voff[1]); | |||
500 | dlog(fmtbuf); | |||
501 | printcombo(ncbp, fmtbuf, sizeof fmtbuf); | |||
502 | dlog(fmtbuf); | |||
503 | } | |||
504 | if (c > 1) { | |||
505 | /* record the empty spots that will complete this combo */ | |||
506 | makeempty(ncbp); | |||
507 | ||||
508 | /* add the new combo to the end of the list */ | |||
509 | appendcombo(ncbp); | |||
510 | } else { | |||
511 | updatecombo(ncbp, curcolor); | |||
512 | free(ncbp); | |||
513 | combocnt--; | |||
514 | } | |||
515 | #ifdef DEBUG | |||
516 | if (c == 1 && debug > 1 || debug > 5) { | |||
517 | markcombo(ncbp); | |||
518 | bdisp(); | |||
519 | whatsup(0); | |||
520 | clearcombo(ncbp, 0); | |||
521 | } | |||
522 | #endif /* DEBUG */ | |||
523 | } | |||
524 | } | |||
525 | } | |||
526 | ||||
527 | /* | |||
528 | * Scan the sorted list of frames and try to add a frame to | |||
529 | * combinations of 'level' number of frames. | |||
530 | */ | |||
531 | void | |||
532 | addframes(int level) | |||
533 | { | |||
534 | struct combostr *cbp, *ecbp; | |||
535 | struct spotstr *sp, *fsp; | |||
536 | struct elist *ep, *nep; | |||
537 | int i, r, d; | |||
538 | struct combostr **cbpp, *pcbp; | |||
539 | union comboval fcb, cb; | |||
540 | ||||
541 | curlevel = level; | |||
542 | ||||
543 | /* scan for combos at empty spots */ | |||
544 | i = curcolor; | |||
545 | for (sp = &board[PT(T,20)((19) + (19 +1) * (20))]; --sp >= &board[PT(A,1)((1) + (19 +1) * (1))]; ) { | |||
546 | for (ep = sp->s_empty; ep; ep = nep) { | |||
547 | cbp = ep->e_combo; | |||
548 | if (cbp->c_combo.s <= sp->s_combo[i].s) { | |||
549 | if (cbp->c_combo.s != sp->s_combo[i].s) { | |||
550 | sp->s_combo[i].s = cbp->c_combo.s; | |||
551 | sp->s_level[i] = cbp->c_nframes; | |||
552 | } else if (cbp->c_nframes < sp->s_level[i]) | |||
553 | sp->s_level[i] = cbp->c_nframes; | |||
554 | } | |||
555 | nep = ep->e_next; | |||
556 | free(ep); | |||
557 | elistcnt--; | |||
558 | } | |||
559 | sp->s_empty = sp->s_nempty; | |||
560 | sp->s_nempty = (struct elist *)0; | |||
561 | } | |||
562 | ||||
563 | /* try to add frames to the uncompleted combos at level curlevel */ | |||
564 | cbp = ecbp = sortframes[curcolor]; | |||
565 | do { | |||
566 | fsp = &board[cbp->c_vertex]; | |||
567 | r = cbp->c_dir; | |||
568 | /* skip frames that are part of a <1,x> combo */ | |||
569 | if (fsp->s_flg & (FFLAG0x000100 << r)) | |||
570 | continue; | |||
571 | ||||
572 | /* | |||
573 | * Don't include <1,x> combo frames, | |||
574 | * treat it as a closed three in a row instead. | |||
575 | */ | |||
576 | fcb.s = fsp->s_fval[curcolor][r].s; | |||
577 | if (fcb.s == 0x101) | |||
578 | fcb.s = 0x200; | |||
579 | ||||
580 | /* | |||
581 | * If this is an open ended frame, use | |||
582 | * the combo value with the end closed. | |||
583 | */ | |||
584 | if (fsp->s_occ == EMPTY2) { | |||
585 | if (fcb.c.b) { | |||
586 | cb.c.a = fcb.c.a + 1; | |||
587 | cb.c.b = 0; | |||
588 | } else | |||
589 | cb.s = fcb.s; | |||
590 | makecombo(cbp, fsp, 0, cb.s); | |||
591 | } | |||
592 | ||||
593 | /* | |||
594 | * The next four spots are handled the same for both | |||
595 | * open and closed ended frames. | |||
596 | */ | |||
597 | d = dd[r]; | |||
598 | sp = fsp + d; | |||
599 | for (i = 1; i < 5; i++, sp += d) { | |||
600 | if (sp->s_occ != EMPTY2) | |||
601 | continue; | |||
602 | makecombo(cbp, sp, i, fcb.s); | |||
603 | } | |||
604 | } while ((cbp = cbp->c_next) != ecbp); | |||
605 | ||||
606 | /* put all the combos in the hash list on the sorted list */ | |||
607 | cbpp = &hashcombos[FAREA(19*(19 -4) + (19 -4)*(19 -4) + 19*(19 -4) + (19 -4)*(19 -4))]; | |||
608 | do { | |||
609 | cbp = *--cbpp; | |||
610 | if (cbp == (struct combostr *)0) | |||
611 | continue; | |||
612 | *cbpp = (struct combostr *)0; | |||
613 | ecbp = sortcombos; | |||
614 | if (ecbp == (struct combostr *)0) | |||
615 | sortcombos = cbp; | |||
616 | else { | |||
617 | /* append to sort list */ | |||
618 | pcbp = ecbp->c_prev; | |||
619 | pcbp->c_next = cbp; | |||
620 | ecbp->c_prev = cbp->c_prev; | |||
621 | cbp->c_prev->c_next = ecbp; | |||
622 | cbp->c_prev = pcbp; | |||
623 | } | |||
624 | } while (cbpp != hashcombos); | |||
625 | } | |||
626 | ||||
627 | /* | |||
628 | * Compute all level N combos of frames intersecting spot 'osp' | |||
629 | * within the frame 'ocbp' and combo value 's'. | |||
630 | */ | |||
631 | void | |||
632 | makecombo(struct combostr *ocbp, struct spotstr *osp, int off, int s) | |||
633 | { | |||
634 | struct combostr *cbp, *ncbp; | |||
635 | struct spotstr *sp; | |||
636 | struct elist *ep; | |||
637 | int n, c; | |||
638 | struct elist *nep; | |||
639 | struct combostr **scbpp; | |||
640 | int baseB, fcnt, emask, verts; | |||
641 | union comboval ocb; | |||
642 | struct ovlp_info vertices[1]; | |||
643 | ||||
644 | ocb.s = s; | |||
645 | baseB = ocb.c.a + ocb.c.b - 1; | |||
646 | fcnt = ocb.c.a - 2; | |||
647 | emask = fcnt ? ((ocb.c.b ? 0x1E : 0x1F) & ~(1 << off)) : 0; | |||
| ||||
648 | for (ep = osp->s_empty; ep; ep = ep->e_next) { | |||
649 | /* check for various kinds of overlap */ | |||
650 | cbp = ep->e_combo; | |||
651 | verts = checkframes(cbp, ocbp, osp, s, vertices); | |||
652 | if (verts
| |||
653 | continue; | |||
654 | ||||
655 | /* check to see if this frame forms a valid loop */ | |||
656 | if (verts
| |||
657 | sp = &board[vertices[0].o_intersect]; | |||
658 | #ifdef DEBUG | |||
659 | if (sp->s_occ != EMPTY2) { | |||
660 | snprintf(fmtbuf, sizeof fmtbuf, | |||
661 | "loop: %c %s", "BW"[curcolor], | |||
662 | stoc(sp - board)); | |||
663 | dlog(fmtbuf); | |||
664 | whatsup(0); | |||
665 | } | |||
666 | #endif | |||
667 | /* | |||
668 | * It is a valid loop if the intersection spot | |||
669 | * of the frame we are trying to attach is one | |||
670 | * of the completion spots of the combostr | |||
671 | * we are trying to attach the frame to. | |||
672 | */ | |||
673 | for (nep = sp->s_empty; nep; nep = nep->e_next) { | |||
674 | if (nep->e_combo == cbp) | |||
675 | goto fnd; | |||
676 | if (nep->e_combo->c_nframes < cbp->c_nframes) | |||
677 | break; | |||
678 | } | |||
679 | /* frame overlaps but not at a valid spot */ | |||
680 | continue; | |||
681 | fnd: | |||
682 | ; | |||
683 | } | |||
684 | ||||
685 | /* compute the first half of the combo value */ | |||
686 | c = cbp->c_combo.c.a + ocb.c.a - verts - 3; | |||
687 | if (c > 4) | |||
688 | continue; | |||
689 | ||||
690 | /* compute the second half of the combo value */ | |||
691 | n = ep->e_fval.c.a + ep->e_fval.c.b - 1; | |||
692 | if (baseB < n) | |||
693 | n = baseB; | |||
694 | ||||
695 | /* make a new combo! */ | |||
696 | ncbp = malloc(sizeof(struct combostr) + | |||
697 | (cbp->c_nframes + 1) * sizeof(struct combostr *)); | |||
698 | if (ncbp == (struct combostr *)NULL((void *)0)) | |||
699 | qlog("Memory allocation failure."); | |||
700 | scbpp = (struct combostr **)(ncbp + 1); | |||
701 | if (sortcombo(scbpp, (struct combostr **)(cbp + 1), ocbp)) { | |||
702 | free(ncbp); | |||
703 | continue; | |||
704 | } | |||
705 | combocnt++; | |||
706 | ||||
707 | ncbp->c_combo.c.a = c; | |||
708 | ncbp->c_combo.c.b = n; | |||
709 | ncbp->c_link[0] = cbp; | |||
710 | ncbp->c_link[1] = ocbp; | |||
711 | ncbp->c_linkv[1].s = ocb.s; | |||
712 | ncbp->c_voff[1] = off; | |||
713 | ncbp->c_vertex = osp - board; | |||
714 | ncbp->c_nframes = cbp->c_nframes + 1; | |||
715 | ncbp->c_flg = ocb.c.b ? C_OPEN_10x02 : 0; | |||
716 | ncbp->c_frameindex = ep->e_frameindex; | |||
717 | /* | |||
718 | * Update the completion spot mask of the frame we | |||
719 | * are attaching 'ocbp' to so the intersection isn't | |||
720 | * listed twice. | |||
721 | */ | |||
722 | ncbp->c_framecnt[0] = ep->e_framecnt; | |||
723 | ncbp->c_emask[0] = ep->e_emask; | |||
724 | if (verts) { | |||
725 | ncbp->c_flg |= C_LOOP0x04; | |||
726 | ncbp->c_dir = vertices[0].o_frameindex; | |||
727 | ncbp->c_framecnt[1] = fcnt - 1; | |||
728 | if (ncbp->c_framecnt[1]) { | |||
729 | n = (vertices[0].o_intersect - ocbp->c_vertex) / | |||
730 | dd[ocbp->c_dir]; | |||
731 | ncbp->c_emask[1] = emask & ~(1 << n); | |||
732 | } else | |||
733 | ncbp->c_emask[1] = 0; | |||
734 | ncbp->c_voff[0] = vertices[0].o_off; | |||
735 | } else { | |||
736 | ncbp->c_dir = 0; | |||
737 | ncbp->c_framecnt[1] = fcnt; | |||
738 | ncbp->c_emask[1] = emask; | |||
739 | ncbp->c_voff[0] = ep->e_off; | |||
740 | } | |||
741 | ||||
742 | if (c == 1 && debug > 1) { | |||
743 | snprintf(fmtbuf, sizeof fmtbuf, | |||
744 | "%c v%d i%d d%d c %d %d m %x %x o %d %d", | |||
745 | "bw"[curcolor], verts, ncbp->c_frameindex, ncbp->c_dir, | |||
746 | ncbp->c_framecnt[0], ncbp->c_framecnt[1], | |||
747 | ncbp->c_emask[0], ncbp->c_emask[1], | |||
748 | ncbp->c_voff[0], ncbp->c_voff[1]); | |||
749 | dlog(fmtbuf); | |||
750 | printcombo(ncbp, fmtbuf, sizeof fmtbuf); | |||
751 | dlog(fmtbuf); | |||
752 | } | |||
753 | if (c > 1) { | |||
754 | /* record the empty spots that will complete this combo */ | |||
755 | makeempty(ncbp); | |||
756 | combolen++; | |||
757 | } else { | |||
758 | /* update board values */ | |||
759 | updatecombo(ncbp, curcolor); | |||
760 | } | |||
761 | #ifdef DEBUG | |||
762 | if (c == 1 && debug > 1 || debug > 4) { | |||
763 | markcombo(ncbp); | |||
764 | bdisp(); | |||
765 | whatsup(0); | |||
766 | clearcombo(ncbp, 0); | |||
767 | } | |||
768 | #endif /* DEBUG */ | |||
769 | } | |||
770 | } | |||
771 | ||||
772 | #define MAXDEPTH100 100 | |||
773 | struct elist einfo[MAXDEPTH100]; | |||
774 | struct combostr *ecombo[MAXDEPTH100]; /* separate from elist to save space */ | |||
775 | ||||
776 | /* | |||
777 | * Add the combostr 'ocbp' to the empty spots list for each empty spot | |||
778 | * in 'ocbp' that will complete the combo. | |||
779 | */ | |||
780 | void | |||
781 | makeempty(struct combostr *ocbp) | |||
782 | { | |||
783 | struct combostr *cbp, **cbpp; | |||
784 | struct elist *ep, *nep; | |||
785 | struct spotstr *sp; | |||
786 | int s, d, m, emask, i; | |||
787 | int nframes; | |||
788 | ||||
789 | if (debug > 2) { | |||
790 | snprintf(fmtbuf, sizeof fmtbuf, "E%c ", "bw"[curcolor]); | |||
791 | printcombo(ocbp, fmtbuf + 3, sizeof fmtbuf - 3); | |||
792 | dlog(fmtbuf); | |||
793 | } | |||
794 | ||||
795 | /* should never happen but check anyway */ | |||
796 | if ((nframes = ocbp->c_nframes) >= MAXDEPTH100) | |||
797 | return; | |||
798 | ||||
799 | /* | |||
800 | * The lower level combo can be pointed to by more than one | |||
801 | * higher level 'struct combostr' so we can't modify the | |||
802 | * lower level. Therefore, higher level combos store the | |||
803 | * real mask of the lower level frame in c_emask[0] and the | |||
804 | * frame number in c_frameindex. | |||
805 | * | |||
806 | * First we traverse the tree from top to bottom and save the | |||
807 | * connection info. Then we traverse the tree from bottom to | |||
808 | * top overwriting lower levels with the newer emask information. | |||
809 | */ | |||
810 | ep = &einfo[nframes]; | |||
811 | cbpp = &ecombo[nframes]; | |||
812 | for (cbp = ocbp; cbp->c_link[1] != NULL((void *)0); cbp = cbp->c_link[0]) { | |||
813 | ep--; | |||
814 | ep->e_combo = cbp; | |||
815 | *--cbpp = cbp->c_link[1]; | |||
816 | ep->e_off = cbp->c_voff[1]; | |||
817 | ep->e_frameindex = cbp->c_frameindex; | |||
818 | ep->e_fval.s = cbp->c_linkv[1].s; | |||
819 | ep->e_framecnt = cbp->c_framecnt[1]; | |||
820 | ep->e_emask = cbp->c_emask[1]; | |||
821 | } | |||
822 | cbp = ep->e_combo; | |||
823 | ep--; | |||
824 | ep->e_combo = cbp; | |||
825 | *--cbpp = cbp->c_link[0]; | |||
826 | ep->e_off = cbp->c_voff[0]; | |||
827 | ep->e_frameindex = 0; | |||
828 | ep->e_fval.s = cbp->c_linkv[0].s; | |||
829 | ep->e_framecnt = cbp->c_framecnt[0]; | |||
830 | ep->e_emask = cbp->c_emask[0]; | |||
831 | ||||
832 | /* now update the emask info */ | |||
833 | s = 0; | |||
834 | for (i = 2, ep += 2; i < nframes; i++, ep++) { | |||
835 | cbp = ep->e_combo; | |||
836 | nep = &einfo[ep->e_frameindex]; | |||
837 | nep->e_framecnt = cbp->c_framecnt[0]; | |||
838 | nep->e_emask = cbp->c_emask[0]; | |||
839 | ||||
840 | if (cbp->c_flg & C_LOOP0x04) { | |||
841 | s++; | |||
842 | /* | |||
843 | * Account for the fact that this frame connects | |||
844 | * to a previous one (thus forming a loop). | |||
845 | */ | |||
846 | nep = &einfo[cbp->c_dir]; | |||
847 | if (--nep->e_framecnt) | |||
848 | nep->e_emask &= ~(1 << cbp->c_voff[0]); | |||
849 | else | |||
850 | nep->e_emask = 0; | |||
851 | } | |||
852 | } | |||
853 | ||||
854 | /* | |||
855 | * We only need to update the emask values of "complete" loops | |||
856 | * to include the intersection spots. | |||
857 | */ | |||
858 | if (s && ocbp->c_combo.c.a == 2) { | |||
859 | /* process loops from the top down */ | |||
860 | ep = &einfo[nframes]; | |||
861 | do { | |||
862 | ep--; | |||
863 | cbp = ep->e_combo; | |||
864 | if (!(cbp->c_flg & C_LOOP0x04)) | |||
865 | continue; | |||
866 | ||||
867 | /* | |||
868 | * Update the emask values to include the | |||
869 | * intersection spots. | |||
870 | */ | |||
871 | nep = &einfo[cbp->c_dir]; | |||
872 | nep->e_framecnt = 1; | |||
873 | nep->e_emask = 1 << cbp->c_voff[0]; | |||
874 | ep->e_framecnt = 1; | |||
875 | ep->e_emask = 1 << ep->e_off; | |||
876 | ep = &einfo[ep->e_frameindex]; | |||
877 | do { | |||
878 | ep->e_framecnt = 1; | |||
879 | ep->e_emask = 1 << ep->e_off; | |||
880 | ep = &einfo[ep->e_frameindex]; | |||
881 | } while (ep > nep); | |||
882 | } while (ep != einfo); | |||
883 | } | |||
884 | ||||
885 | /* check all the frames for completion spots */ | |||
886 | for (i = 0, ep = einfo, cbpp = ecombo; i < nframes; i++, ep++, cbpp++) { | |||
887 | /* skip this frame if there are no incomplete spots in it */ | |||
888 | if ((emask = ep->e_emask) == 0) | |||
889 | continue; | |||
890 | cbp = *cbpp; | |||
891 | sp = &board[cbp->c_vertex]; | |||
892 | d = dd[cbp->c_dir]; | |||
893 | for (s = 0, m = 1; s < 5; s++, sp += d, m <<= 1) { | |||
894 | if (sp->s_occ != EMPTY2 || !(emask & m)) | |||
895 | continue; | |||
896 | ||||
897 | /* add the combo to the list of empty spots */ | |||
898 | nep = malloc(sizeof(struct elist)); | |||
899 | if (nep == (struct elist *)NULL((void *)0)) | |||
900 | qlog("Memory allocation failure."); | |||
901 | nep->e_combo = ocbp; | |||
902 | nep->e_off = s; | |||
903 | nep->e_frameindex = i; | |||
904 | if (ep->e_framecnt > 1) { | |||
905 | nep->e_framecnt = ep->e_framecnt - 1; | |||
906 | nep->e_emask = emask & ~m; | |||
907 | } else { | |||
908 | nep->e_framecnt = 0; | |||
909 | nep->e_emask = 0; | |||
910 | } | |||
911 | nep->e_fval.s = ep->e_fval.s; | |||
912 | if (debug > 2) { | |||
913 | snprintf(fmtbuf, sizeof fmtbuf, | |||
914 | "e %s o%d i%d c%d m%x %x", | |||
915 | stoc(sp - board), | |||
916 | nep->e_off, | |||
917 | nep->e_frameindex, | |||
918 | nep->e_framecnt, | |||
919 | nep->e_emask, | |||
920 | nep->e_fval.s); | |||
921 | dlog(fmtbuf); | |||
922 | } | |||
923 | ||||
924 | /* sort by the number of frames in the combo */ | |||
925 | nep->e_next = sp->s_nempty; | |||
926 | sp->s_nempty = nep; | |||
927 | elistcnt++; | |||
928 | } | |||
929 | } | |||
930 | } | |||
931 | ||||
932 | /* | |||
933 | * Update the board value based on the combostr. | |||
934 | * This is called only if 'cbp' is a <1,x> combo. | |||
935 | * We handle things differently depending on whether the next move | |||
936 | * would be trying to "complete" the combo or trying to block it. | |||
937 | */ | |||
938 | void | |||
939 | updatecombo(struct combostr *cbp, int color) | |||
940 | { | |||
941 | struct spotstr *sp; | |||
942 | struct combostr *tcbp; | |||
943 | int i, d; | |||
944 | int nframes, s, flg = 0; | |||
945 | union comboval cb; | |||
946 | ||||
947 | /* save the top level value for the whole combo */ | |||
948 | cb.c.a = cbp->c_combo.c.a; | |||
949 | nframes = cbp->c_nframes; | |||
950 | ||||
951 | if (color != nextcolor) | |||
952 | memset(tmpmap, 0, sizeof(tmpmap)); | |||
953 | ||||
954 | for (; (tcbp = cbp->c_link[1]) != NULL((void *)0); cbp = cbp->c_link[0]) { | |||
955 | flg = cbp->c_flg; | |||
956 | cb.c.b = cbp->c_combo.c.b; | |||
957 | if (color == nextcolor) { | |||
958 | /* update the board value for the vertex */ | |||
959 | sp = &board[cbp->c_vertex]; | |||
960 | sp->s_nforce[color]++; | |||
961 | if (cb.s <= sp->s_combo[color].s) { | |||
962 | if (cb.s != sp->s_combo[color].s) { | |||
963 | sp->s_combo[color].s = cb.s; | |||
964 | sp->s_level[color] = nframes; | |||
965 | } else if (nframes < sp->s_level[color]) | |||
966 | sp->s_level[color] = nframes; | |||
967 | } | |||
968 | } else { | |||
969 | /* update the board values for each spot in frame */ | |||
970 | sp = &board[s = tcbp->c_vertex]; | |||
971 | d = dd[tcbp->c_dir]; | |||
972 | i = (flg & C_OPEN_10x02) ? 6 : 5; | |||
973 | for (; --i >= 0; sp += d, s += d) { | |||
974 | if (sp->s_occ != EMPTY2) | |||
975 | continue; | |||
976 | sp->s_nforce[color]++; | |||
977 | if (cb.s <= sp->s_combo[color].s) { | |||
978 | if (cb.s != sp->s_combo[color].s) { | |||
979 | sp->s_combo[color].s = cb.s; | |||
980 | sp->s_level[color] = nframes; | |||
981 | } else if (nframes < sp->s_level[color]) | |||
982 | sp->s_level[color] = nframes; | |||
983 | } | |||
984 | BIT_SET(tmpmap, s)((tmpmap)[(s)/(sizeof(int) * 8)] |= (1 << ((s) % (sizeof (int) * 8)))); | |||
985 | } | |||
986 | } | |||
987 | ||||
988 | /* mark the frame as being part of a <1,x> combo */ | |||
989 | board[tcbp->c_vertex].s_flg |= FFLAG0x000100 << tcbp->c_dir; | |||
990 | } | |||
991 | ||||
992 | if (color != nextcolor) { | |||
993 | /* update the board values for each spot in frame */ | |||
994 | sp = &board[s = cbp->c_vertex]; | |||
995 | d = dd[cbp->c_dir]; | |||
996 | i = (flg & C_OPEN_00x01) ? 6 : 5; | |||
997 | for (; --i >= 0; sp += d, s += d) { | |||
998 | if (sp->s_occ != EMPTY2) | |||
999 | continue; | |||
1000 | sp->s_nforce[color]++; | |||
1001 | if (cb.s <= sp->s_combo[color].s) { | |||
1002 | if (cb.s != sp->s_combo[color].s) { | |||
1003 | sp->s_combo[color].s = cb.s; | |||
1004 | sp->s_level[color] = nframes; | |||
1005 | } else if (nframes < sp->s_level[color]) | |||
1006 | sp->s_level[color] = nframes; | |||
1007 | } | |||
1008 | BIT_SET(tmpmap, s)((tmpmap)[(s)/(sizeof(int) * 8)] |= (1 << ((s) % (sizeof (int) * 8)))); | |||
1009 | } | |||
1010 | if (nforce == 0) | |||
1011 | memcpy(forcemap, tmpmap, sizeof(tmpmap)); | |||
1012 | else { | |||
1013 | for (i = 0; i < MAPSZ(((19 +2)*(19 +1)+1) / (sizeof(int) * 8)); i++) | |||
1014 | forcemap[i] &= tmpmap[i]; | |||
1015 | } | |||
1016 | nforce++; | |||
1017 | } | |||
1018 | ||||
1019 | /* mark the frame as being part of a <1,x> combo */ | |||
1020 | board[cbp->c_vertex].s_flg |= FFLAG0x000100 << cbp->c_dir; | |||
1021 | } | |||
1022 | ||||
1023 | /* | |||
1024 | * Add combo to the end of the list. | |||
1025 | */ | |||
1026 | void | |||
1027 | appendcombo(struct combostr *cbp) | |||
1028 | { | |||
1029 | struct combostr *pcbp, *ncbp; | |||
1030 | ||||
1031 | combolen++; | |||
1032 | ncbp = sortcombos; | |||
1033 | if (ncbp == (struct combostr *)0) { | |||
1034 | sortcombos = cbp; | |||
1035 | cbp->c_next = cbp; | |||
1036 | cbp->c_prev = cbp; | |||
1037 | return; | |||
1038 | } | |||
1039 | pcbp = ncbp->c_prev; | |||
1040 | cbp->c_next = ncbp; | |||
1041 | cbp->c_prev = pcbp; | |||
1042 | ncbp->c_prev = cbp; | |||
1043 | pcbp->c_next = cbp; | |||
1044 | } | |||
1045 | ||||
1046 | /* | |||
1047 | * Return zero if it is valid to combine frame 'fcbp' with the frames | |||
1048 | * in 'cbp' and forms a linked chain of frames (i.e., a tree; no loops). | |||
1049 | * Return positive if combining frame 'fcbp' to the frames in 'cbp' | |||
1050 | * would form some kind of valid loop. Also return the intersection spots | |||
1051 | * in 'vertices[]' beside the known intersection at spot 'osp'. | |||
1052 | * Return -1 if 'fcbp' should not be combined with 'cbp'. | |||
1053 | * 's' is the combo value for frame 'fcpb'. | |||
1054 | */ | |||
1055 | int | |||
1056 | checkframes(struct combostr *cbp, struct combostr *fcbp, struct spotstr *osp, | |||
1057 | int s, struct ovlp_info *vertices) | |||
1058 | { | |||
1059 | struct combostr *tcbp, *lcbp = NULL((void *)0); | |||
1060 | int i, n, mask, flg, verts, idx, fcnt; | |||
1061 | union comboval cb; | |||
1062 | u_char *str; | |||
1063 | short *ip; | |||
1064 | ||||
1065 | cb.s = s; | |||
1066 | fcnt = cb.c.a - 2; | |||
1067 | verts = 0; | |||
1068 | flg = 0; | |||
1069 | idx = cbp->c_nframes; | |||
1070 | n = (fcbp - frames) * FAREA(19*(19 -4) + (19 -4)*(19 -4) + 19*(19 -4) + (19 -4)*(19 -4)); | |||
1071 | str = &overlap[n]; | |||
1072 | ip = &intersect[n]; | |||
1073 | /* | |||
1074 | * i == which overlap bit to test based on whether 'fcbp' is | |||
1075 | * an open or closed frame. | |||
1076 | */ | |||
1077 | i = cb.c.b ? 2 : 0; | |||
1078 | for (; (tcbp = cbp->c_link[1]) != NULL((void *)0); lcbp = cbp, cbp = cbp->c_link[0]) { | |||
1079 | if (tcbp == fcbp) | |||
1080 | return (-1); /* fcbp is already included */ | |||
1081 | ||||
1082 | /* check for intersection of 'tcbp' with 'fcbp' */ | |||
1083 | idx--; | |||
1084 | mask = str[tcbp - frames]; | |||
1085 | flg = cbp->c_flg; | |||
1086 | n = i + ((flg & C_OPEN_10x02) != 0); | |||
1087 | if (mask & (1 << n)) { | |||
1088 | /* | |||
1089 | * The two frames are not independent if they | |||
1090 | * both lie in the same line and intersect at | |||
1091 | * more than one point. | |||
1092 | */ | |||
1093 | if (tcbp->c_dir == fcbp->c_dir && (mask & (0x10 << n))) | |||
1094 | return (-1); | |||
1095 | /* | |||
1096 | * If this is not the spot we are attaching | |||
1097 | * 'fcbp' to and it is a reasonable intersection | |||
1098 | * spot, then there might be a loop. | |||
1099 | */ | |||
1100 | n = ip[tcbp - frames]; | |||
1101 | if (osp != &board[n]) { | |||
1102 | /* check to see if this is a valid loop */ | |||
1103 | if (verts) | |||
1104 | return (-1); | |||
1105 | if (fcnt == 0 || cbp->c_framecnt[1] == 0) | |||
1106 | return (-1); | |||
1107 | /* | |||
1108 | * Check to be sure the intersection is not | |||
1109 | * one of the end points if it is an open | |||
1110 | * ended frame. | |||
1111 | */ | |||
1112 | if ((flg & C_OPEN_10x02) && | |||
1113 | (n == tcbp->c_vertex || | |||
1114 | n == tcbp->c_vertex + 5 * dd[tcbp->c_dir])) | |||
1115 | return (-1); /* invalid overlap */ | |||
1116 | if (cb.c.b && | |||
1117 | (n == fcbp->c_vertex || | |||
1118 | n == fcbp->c_vertex + 5 * dd[fcbp->c_dir])) | |||
1119 | return (-1); /* invalid overlap */ | |||
1120 | ||||
1121 | vertices->o_intersect = n; | |||
1122 | vertices->o_fcombo = cbp; | |||
1123 | vertices->o_link = 1; | |||
1124 | vertices->o_off = (n - tcbp->c_vertex) / | |||
1125 | dd[tcbp->c_dir]; | |||
1126 | vertices->o_frameindex = idx; | |||
1127 | verts++; | |||
1128 | } | |||
1129 | } | |||
1130 | n = i + ((flg & C_OPEN_00x01) != 0); | |||
1131 | } | |||
1132 | if (cbp == fcbp) | |||
1133 | return (-1); /* fcbp is already included */ | |||
1134 | ||||
1135 | /* check for intersection of 'cbp' with 'fcbp' */ | |||
1136 | mask = str[cbp - frames]; | |||
1137 | if (mask & (1 << n)) { | |||
1138 | /* | |||
1139 | * The two frames are not independent if they | |||
1140 | * both lie in the same line and intersect at | |||
1141 | * more than one point. | |||
1142 | */ | |||
1143 | if (cbp->c_dir == fcbp->c_dir && (mask & (0x10 << n))) | |||
1144 | return (-1); | |||
1145 | /* | |||
1146 | * If this is not the spot we are attaching | |||
1147 | * 'fcbp' to and it is a reasonable intersection | |||
1148 | * spot, then there might be a loop. | |||
1149 | */ | |||
1150 | n = ip[cbp - frames]; | |||
1151 | if (osp != &board[n]) { | |||
1152 | /* check to see if this is a valid loop */ | |||
1153 | if (verts) | |||
1154 | return (-1); | |||
1155 | if (fcnt == 0 || lcbp->c_framecnt[0] == 0) | |||
1156 | return (-1); | |||
1157 | /* | |||
1158 | * Check to be sure the intersection is not | |||
1159 | * one of the end points if it is an open | |||
1160 | * ended frame. | |||
1161 | */ | |||
1162 | if ((flg & C_OPEN_00x01) && | |||
1163 | (n == cbp->c_vertex || | |||
1164 | n == cbp->c_vertex + 5 * dd[cbp->c_dir])) | |||
1165 | return (-1); /* invalid overlap */ | |||
1166 | if (cb.c.b && | |||
1167 | (n == fcbp->c_vertex || | |||
1168 | n == fcbp->c_vertex + 5 * dd[fcbp->c_dir])) | |||
1169 | return (-1); /* invalid overlap */ | |||
1170 | ||||
1171 | vertices->o_intersect = n; | |||
1172 | vertices->o_fcombo = lcbp; | |||
1173 | vertices->o_link = 0; | |||
1174 | vertices->o_off = (n - cbp->c_vertex) / | |||
1175 | dd[cbp->c_dir]; | |||
1176 | vertices->o_frameindex = 0; | |||
1177 | verts++; | |||
1178 | } | |||
1179 | } | |||
1180 | return (verts); | |||
1181 | } | |||
1182 | ||||
1183 | /* | |||
1184 | * Merge sort the frame 'fcbp' and the sorted list of frames 'cbpp' and | |||
1185 | * store the result in 'scbpp'. 'curlevel' is the size of the 'cbpp' array. | |||
1186 | * Return true if this list of frames is already in the hash list. | |||
1187 | * Otherwise, add the new combo to the hash list. | |||
1188 | */ | |||
1189 | int | |||
1190 | sortcombo(struct combostr **scbpp, struct combostr **cbpp, | |||
1191 | struct combostr *fcbp) | |||
1192 | { | |||
1193 | struct combostr **spp, **cpp; | |||
1194 | struct combostr *cbp, *ecbp; | |||
1195 | int n, inx; | |||
1196 | ||||
1197 | #ifdef DEBUG | |||
1198 | if (debug > 3) { | |||
1199 | char *str; | |||
1200 | ||||
1201 | snprintf(fmtbuf, sizeof fmtbuf, | |||
1202 | "sortc: %s%c l%d", stoc(fcbp->c_vertex), | |||
1203 | pdir[fcbp->c_dir], curlevel); | |||
1204 | dlog(fmtbuf); | |||
1205 | str = fmtbuf; | |||
1206 | for (cpp = cbpp; cpp < cbpp + curlevel; cpp++) { | |||
1207 | snprintf(str, fmtbuf + sizeof fmtbuf - str, | |||
1208 | " %s%c", stoc((*cpp)->c_vertex), | |||
1209 | pdir[(*cpp)->c_dir]); | |||
1210 | str += strlen(str); | |||
1211 | } | |||
1212 | dlog(fmtbuf); | |||
1213 | } | |||
1214 | #endif /* DEBUG */ | |||
1215 | ||||
1216 | /* first build the new sorted list */ | |||
1217 | n = curlevel + 1; | |||
1218 | spp = scbpp + n; | |||
1219 | cpp = cbpp + curlevel; | |||
1220 | do { | |||
1221 | cpp--; | |||
1222 | if (fcbp > *cpp) { | |||
1223 | *--spp = fcbp; | |||
| ||||
1224 | do | |||
1225 | *--spp = *cpp; | |||
1226 | while (cpp-- != cbpp); | |||
1227 | goto inserted; | |||
1228 | } | |||
1229 | *--spp = *cpp; | |||
1230 | } while (cpp != cbpp); | |||
1231 | *--spp = fcbp; | |||
1232 | inserted: | |||
1233 | ||||
1234 | /* now check to see if this list of frames has already been seen */ | |||
1235 | cbp = hashcombos[inx = *scbpp - frames]; | |||
1236 | if (cbp == (struct combostr *)0) { | |||
1237 | /* | |||
1238 | * Easy case, this list hasn't been seen. | |||
1239 | * Add it to the hash list. | |||
1240 | */ | |||
1241 | fcbp = (struct combostr *) | |||
1242 | ((char *)scbpp - sizeof(struct combostr)); | |||
1243 | hashcombos[inx] = fcbp; | |||
1244 | fcbp->c_next = fcbp->c_prev = fcbp; | |||
1245 | return (0); | |||
1246 | } | |||
1247 | ecbp = cbp; | |||
1248 | do { | |||
1249 | cbpp = (struct combostr **)(cbp + 1); | |||
1250 | cpp = cbpp + n; | |||
1251 | spp = scbpp + n; | |||
1252 | cbpp++; /* first frame is always the same */ | |||
1253 | do { | |||
1254 | if (*--spp != *--cpp) | |||
1255 | goto next; | |||
1256 | } while (cpp != cbpp); | |||
1257 | /* we found a match */ | |||
1258 | #ifdef DEBUG | |||
1259 | if (debug > 3) { | |||
1260 | char *str; | |||
1261 | ||||
1262 | snprintf(fmtbuf, sizeof fmtbuf, "sort1: n%d", n); | |||
1263 | dlog(fmtbuf); | |||
1264 | str = fmtbuf; | |||
1265 | for (cpp = scbpp; cpp < scbpp + n; cpp++) { | |||
1266 | snprintf(str, fmtbuf + sizeof fmtbuf - str, | |||
1267 | " %s%c", stoc((*cpp)->c_vertex), | |||
1268 | pdir[(*cpp)->c_dir]); | |||
1269 | str += strlen(str); | |||
1270 | } | |||
1271 | dlog(fmtbuf); | |||
1272 | printcombo(cbp, fmtbuf, sizeof fmtbuf); | |||
1273 | dlog(fmtbuf); | |||
1274 | str = fmtbuf; | |||
1275 | cbpp--; | |||
1276 | for (cpp = cbpp; cpp < cbpp + n; cpp++) { | |||
1277 | snprintf(str, fmtbuf + sizeof fmtbuf - str, | |||
1278 | " %s%c", stoc((*cpp)->c_vertex), | |||
1279 | pdir[(*cpp)->c_dir]); | |||
1280 | str += strlen(str); | |||
1281 | } | |||
1282 | dlog(fmtbuf); | |||
1283 | } | |||
1284 | #endif /* DEBUG */ | |||
1285 | return (1); | |||
1286 | next: | |||
1287 | ; | |||
1288 | } while ((cbp = cbp->c_next) != ecbp); | |||
1289 | /* | |||
1290 | * This list of frames hasn't been seen. | |||
1291 | * Add it to the hash list. | |||
1292 | */ | |||
1293 | ecbp = cbp->c_prev; | |||
1294 | fcbp = (struct combostr *)((char *)scbpp - sizeof(struct combostr)); | |||
1295 | fcbp->c_next = cbp; | |||
1296 | fcbp->c_prev = ecbp; | |||
1297 | cbp->c_prev = fcbp; | |||
1298 | ecbp->c_next = fcbp; | |||
1299 | return (0); | |||
1300 | } | |||
1301 | ||||
1302 | /* | |||
1303 | * Print the combo into string 'str'. | |||
1304 | */ | |||
1305 | void | |||
1306 | printcombo(struct combostr *cbp, char *str, size_t strl) | |||
1307 | { | |||
1308 | char *basestr = str; | |||
1309 | struct combostr *tcbp; | |||
1310 | ||||
1311 | snprintf(str, strl, "%x/%d", cbp->c_combo.s, cbp->c_nframes); | |||
1312 | str += strlen(str); | |||
1313 | for (; (tcbp = cbp->c_link[1]) != NULL((void *)0); cbp = cbp->c_link[0]) { | |||
1314 | snprintf(str, basestr + strl - str, | |||
1315 | " %s%c%x", stoc(tcbp->c_vertex), pdir[tcbp->c_dir], | |||
1316 | cbp->c_flg); | |||
1317 | str += strlen(str); | |||
1318 | } | |||
1319 | snprintf(str, basestr + strl - str, | |||
1320 | " %s%c", stoc(cbp->c_vertex), pdir[cbp->c_dir]); | |||
1321 | } | |||
1322 | ||||
1323 | #ifdef DEBUG | |||
1324 | void | |||
1325 | markcombo(struct combostr *ocbp) | |||
1326 | { | |||
1327 | struct combostr *cbp, *tcbp, **cbpp; | |||
1328 | struct elist *ep, *nep, **epp; | |||
1329 | struct spotstr *sp; | |||
1330 | int s, d, m, i; | |||
1331 | int nframes; | |||
1332 | int r, n, flg, cmask, omask; | |||
1333 | ||||
1334 | /* should never happen but check anyway */ | |||
1335 | if ((nframes = ocbp->c_nframes) >= MAXDEPTH100) | |||
1336 | return; | |||
1337 | ||||
1338 | /* | |||
1339 | * The lower level combo can be pointed to by more than one | |||
1340 | * higher level 'struct combostr' so we can't modify the | |||
1341 | * lower level. Therefore, higher level combos store the | |||
1342 | * real mask of the lower level frame in c_emask[0] and the | |||
1343 | * frame number in c_frameindex. | |||
1344 | * | |||
1345 | * First we traverse the tree from top to bottom and save the | |||
1346 | * connection info. Then we traverse the tree from bottom to | |||
1347 | * top overwriting lower levels with the newer emask information. | |||
1348 | */ | |||
1349 | ep = &einfo[nframes]; | |||
1350 | cbpp = &ecombo[nframes]; | |||
1351 | for (cbp = ocbp; tcbp = cbp->c_link[1]; cbp = cbp->c_link[0]) { | |||
1352 | ep--; | |||
1353 | ep->e_combo = cbp; | |||
1354 | *--cbpp = cbp->c_link[1]; | |||
1355 | ep->e_off = cbp->c_voff[1]; | |||
1356 | ep->e_frameindex = cbp->c_frameindex; | |||
1357 | ep->e_fval.s = cbp->c_linkv[1].s; | |||
1358 | ep->e_framecnt = cbp->c_framecnt[1]; | |||
1359 | ep->e_emask = cbp->c_emask[1]; | |||
1360 | } | |||
1361 | cbp = ep->e_combo; | |||
1362 | ep--; | |||
1363 | ep->e_combo = cbp; | |||
1364 | *--cbpp = cbp->c_link[0]; | |||
1365 | ep->e_off = cbp->c_voff[0]; | |||
1366 | ep->e_frameindex = 0; | |||
1367 | ep->e_fval.s = cbp->c_linkv[0].s; | |||
1368 | ep->e_framecnt = cbp->c_framecnt[0]; | |||
1369 | ep->e_emask = cbp->c_emask[0]; | |||
1370 | ||||
1371 | /* now update the emask info */ | |||
1372 | s = 0; | |||
1373 | for (i = 2, ep += 2; i < nframes; i++, ep++) { | |||
1374 | cbp = ep->e_combo; | |||
1375 | nep = &einfo[ep->e_frameindex]; | |||
1376 | nep->e_framecnt = cbp->c_framecnt[0]; | |||
1377 | nep->e_emask = cbp->c_emask[0]; | |||
1378 | ||||
1379 | if (cbp->c_flg & C_LOOP0x04) { | |||
1380 | s++; | |||
1381 | /* | |||
1382 | * Account for the fact that this frame connects | |||
1383 | * to a previous one (thus forming a loop). | |||
1384 | */ | |||
1385 | nep = &einfo[cbp->c_dir]; | |||
1386 | if (--nep->e_framecnt) | |||
1387 | nep->e_emask &= ~(1 << cbp->c_voff[0]); | |||
1388 | else | |||
1389 | nep->e_emask = 0; | |||
1390 | } | |||
1391 | } | |||
1392 | ||||
1393 | /* | |||
1394 | * We only need to update the emask values of "complete" loops | |||
1395 | * to include the intersection spots. | |||
1396 | */ | |||
1397 | if (s && ocbp->c_combo.c.a == 2) { | |||
1398 | /* process loops from the top down */ | |||
1399 | ep = &einfo[nframes]; | |||
1400 | do { | |||
1401 | ep--; | |||
1402 | cbp = ep->e_combo; | |||
1403 | if (!(cbp->c_flg & C_LOOP0x04)) | |||
1404 | continue; | |||
1405 | ||||
1406 | /* | |||
1407 | * Update the emask values to include the | |||
1408 | * intersection spots. | |||
1409 | */ | |||
1410 | nep = &einfo[cbp->c_dir]; | |||
1411 | nep->e_framecnt = 1; | |||
1412 | nep->e_emask = 1 << cbp->c_voff[0]; | |||
1413 | ep->e_framecnt = 1; | |||
1414 | ep->e_emask = 1 << ep->e_off; | |||
1415 | ep = &einfo[ep->e_frameindex]; | |||
1416 | do { | |||
1417 | ep->e_framecnt = 1; | |||
1418 | ep->e_emask = 1 << ep->e_off; | |||
1419 | ep = &einfo[ep->e_frameindex]; | |||
1420 | } while (ep > nep); | |||
1421 | } while (ep != einfo); | |||
1422 | } | |||
1423 | ||||
1424 | /* mark all the frames with the completion spots */ | |||
1425 | for (i = 0, ep = einfo, cbpp = ecombo; i < nframes; i++, ep++, cbpp++) { | |||
1426 | m = ep->e_emask; | |||
1427 | cbp = *cbpp; | |||
1428 | sp = &board[cbp->c_vertex]; | |||
1429 | d = dd[s = cbp->c_dir]; | |||
1430 | cmask = CFLAG0x000001 << s; | |||
1431 | omask = (IFLAG0x000010 | CFLAG0x000001) << s; | |||
1432 | s = ep->e_fval.c.b ? 6 : 5; | |||
1433 | for (; --s >= 0; sp += d, m >>= 1) | |||
1434 | sp->s_flg |= (m & 1) ? omask : cmask; | |||
1435 | } | |||
1436 | } | |||
1437 | ||||
1438 | void | |||
1439 | clearcombo(struct combostr *cbp, int open) | |||
1440 | { | |||
1441 | struct spotstr *sp; | |||
1442 | struct combostr *tcbp; | |||
1443 | int d, n, mask; | |||
1444 | ||||
1445 | for (; tcbp = cbp->c_link[1]; cbp = cbp->c_link[0]) { | |||
1446 | clearcombo(tcbp, cbp->c_flg & C_OPEN_10x02); | |||
1447 | open = cbp->c_flg & C_OPEN_00x01; | |||
1448 | } | |||
1449 | sp = &board[cbp->c_vertex]; | |||
1450 | d = dd[n = cbp->c_dir]; | |||
1451 | mask = ~((IFLAG0x000010 | CFLAG0x000001) << n); | |||
1452 | n = open ? 6 : 5; | |||
1453 | for (; --n >= 0; sp += d) | |||
1454 | sp->s_flg &= mask; | |||
1455 | } | |||
1456 | ||||
1457 | int | |||
1458 | list_eq(struct combostr **scbpp, struct combostr **cbpp, int n) | |||
1459 | { | |||
1460 | struct combostr **spp, **cpp; | |||
1461 | ||||
1462 | spp = scbpp + n; | |||
1463 | cpp = cbpp + n; | |||
1464 | do { | |||
1465 | if (*--spp != *--cpp) | |||
1466 | return (0); | |||
1467 | } while (cpp != cbpp); | |||
1468 | /* we found a match */ | |||
1469 | return (1); | |||
1470 | } | |||
1471 | #endif /* DEBUG */ |