summaryrefslogtreecommitdiff
path: root/noncore/games/go/goplayutils.c
Unidiff
Diffstat (limited to 'noncore/games/go/goplayutils.c') (more/less context) (ignore whitespace changes)
-rw-r--r--noncore/games/go/goplayutils.c1317
1 files changed, 1317 insertions, 0 deletions
diff --git a/noncore/games/go/goplayutils.c b/noncore/games/go/goplayutils.c
new file mode 100644
index 0000000..9e2ce4c
--- a/dev/null
+++ b/noncore/games/go/goplayutils.c
@@ -0,0 +1,1317 @@
1/* The go player utilities */
2/* Ported from Pascal to C by Todd R. Johnson */
3/* From the original Pascal file:
4Copyright (c) 1983 by Three Rivers Computer Corp.
5
6Written: January 17, 1983 by Stoney Ballard
7*/
8
9#include "goplayutils.h"
10#include "amigo.h"
11#include "go.h"
12
13extern struct bRec goboard[19][19];
14
15intBoard claim, extra, bord, ndbord, sGroups, threatBord,
16 groupIDs, connectMap, protPoints;
17boolBoard groupSeen, legal;
18short maxGroupID;
19pointList pList, pList1, plist2, plist3, pPlist;
20intList nlcGroup, aList;
21sgRec sList[401];
22groupRec gList[maxGroup];
23short killFlag,
24 numCapt,
25 utilPlayLevel,
26 treeLibLim;
27sType mySType;
28short showTrees;
29short sGlist[maxGroup+1];
30short depthLimit;
31intBoard markBoard;
32short marker;
33
34short adjInAtari, adj2Libs,
35 intersectNum, spanNum, libMark;
36playRec playStack[1025];
37short playMark,
38 newGID,
39 tryLevel,
40 grpMark,
41 gMap[maxGroup];
42short dbStop, inGenState;
43
44 pause()
45{ /* pause */
46/* if (dbStop and ! inGenState)
47 {
48 while ! tabswitch do;
49 repeat
50 if (tabYellow)
51 dbStop = false;
52 until ! tabswitch;
53 } */
54} /* pause */
55
56sstone(w, x, y, numb)
57short w, x, y, numb;
58{ /* sstone */
59 if (w == 1)
60 placestone(mySType, x, y);
61 else if (mySType == WHITE)
62 placestone(BLACK, x, y);
63 else
64 placestone(WHITE, x, y);
65} /* sstone */
66
67rstone(x, y)
68short x, y;
69{ /* rstone */
70 removestone(x, y);
71} /* rstone */
72
73initBoolBoard(bb)
74boolBoard bb;
75{ /* initBoolBoard */
76 short i, j;
77#ifdef DEBUG
78 printf( "initBoolBoard\n" );
79#endif
80 for (i = 0; i <= maxPoint; i++)
81 for (j = 0; j <= maxPoint; j++)
82 bb[i][j] = FALSE;
83} /* initBoolBoard */
84
85sortLibs()
86{ /* sortLibs */
87 short i, j, t;
88#ifdef DEBUG
89 printf( "sortLibs\n" );
90#endif
91 for (i = 1; i <= maxGroupID; i++)
92 sGlist[i] = i;
93 for (i = 1; i < maxGroupID; i++)
94 for (j = i + 1; j <= maxGroupID; j++)
95 if (gList[sGlist[i]].libC > gList[sGlist[j]].libC)
96 {
97 t = sGlist[i];
98 sGlist[i] = sGlist[j];
99 sGlist[j] = t;
100 }
101} /* sortLibs */
102
103spanGroupspan(x, y, libs, lookFor)
104short x, y, lookFor;
105pointList *libs;
106 { /* span */
107 markBoard[x][y] = marker;
108 if (bord[x][y] == 0)
109 {
110 libs->indx = libs->indx + 1;
111 libs->p[libs->indx].px = x;
112 libs->p[libs->indx].py = y;
113 }
114 else if (bord[x][y] == lookFor)
115 {
116 groupSeen[x][y] = TRUE;
117 if ((x > 0) && (markBoard[x - 1][y] != marker))
118 spanGroupspan(x - 1, y, libs, lookFor);
119 if ((y > 0) && (markBoard[x][y - 1] != marker))
120 spanGroupspan(x, y - 1, libs, lookFor);
121 if ((x < maxPoint) && (markBoard[x + 1][y] != marker))
122 spanGroupspan(x + 1, y, libs, lookFor);
123 if ((y < maxPoint) && (markBoard[x][y + 1] != marker))
124 spanGroupspan(x, y + 1, libs, lookFor);
125 }
126 else if (gList[gMap[groupIDs[x][y]]].libC == 1)
127 adjInAtari = TRUE;
128 else if ((gList[gMap[groupIDs[x][y]]].libC == 2) &&
129 (! gList[gMap[groupIDs[x][y]]].isLive))
130 adj2Libs = TRUE;
131 } /* span */
132
133spanGroup(x, y, libs)
134short x, y;
135pointList *libs;
136{ /* spanGroup */
137 short lookFor;
138#ifdef DEBUG
139 printf( "spanGroup\n" );
140#endif
141 marker = marker + 1;
142 if (marker == 0)
143 {
144 initArray(markBoard);
145 marker = 1;
146 }
147 adjInAtari = FALSE;
148 adj2Libs = FALSE;
149 lookFor = bord[x][y];
150 libs->indx = 0;
151 spanGroupspan(x, y, libs, lookFor);
152} /* spanGroup */
153
154sSpanGroupspan(x, y, libs, lookFor)
155short x, y, lookFor;
156sPointList *libs;
157 { /* span */
158 markBoard[x][y] = marker;
159 if (bord[x][y] == 0)
160 {
161 libs->indx += 1;
162 if (libs->indx <= maxSPoint)
163 {
164 libs->p[libs->indx].px = x;
165 libs->p[libs->indx].py = y;
166 }
167 }
168 else if (bord[x][y] == lookFor)
169 {
170 groupSeen[x][y] = TRUE;
171 if ((x > 0) && (markBoard[x - 1][y] != marker))
172 sSpanGroupspan(x - 1, y, libs, lookFor);
173 if ((y > 0) && (markBoard[x][y - 1] != marker))
174 sSpanGroupspan(x, y - 1, libs, lookFor);
175 if ((x < maxPoint) && (markBoard[x + 1][y] != marker))
176 sSpanGroupspan(x + 1, y, libs, lookFor);
177 if ((y < maxPoint) && (markBoard[x][y + 1] != marker))
178 sSpanGroupspan(x, y + 1, libs, lookFor);
179 }
180 else if (gList[gMap[groupIDs[x][y]]].libC == 1)
181 adjInAtari = TRUE;
182 else if ((gList[gMap[groupIDs[x][y]]].libC == 2) &&
183 (! gList[gMap[groupIDs[x][y]]].isLive))
184 adj2Libs = TRUE;
185 } /* span */
186
187sSpanGroup(x, y, libs)
188short x, y;
189sPointList *libs;
190{ /* sSpanGroup */
191 short lookFor;
192#ifdef DEBUG
193 printf( "sSpanGroup\n" );
194#endif
195 marker = marker + 1;
196 if (marker == 0)
197 {
198 initArray(markBoard);
199 marker = 1;
200 }
201 adjInAtari = FALSE;
202 adj2Libs = FALSE;
203 lookFor = bord[x][y];
204 libs->indx = 0;
205 sSpanGroupspan(x, y, libs, lookFor);
206} /* sSpanGroup */
207
208LAspan(x, y, me, him, iL)
209short x, y, me, him;
210intList *iL;
211 { /* span */
212#ifdef DEBUG
213 printf( "LAspan\n" );
214#endif
215 markBoard[x][y] = marker;
216 if (bord[x][y] == me)
217 {
218 if ((x > 0) && (markBoard[x - 1][y] != marker))
219 LAspan(x - 1, y, me, him, iL);
220 if ((x < maxPoint) && (markBoard[x + 1][y] != marker))
221 LAspan(x + 1, y, me, him, iL);
222 if ((y > 0) && (markBoard[x][y - 1] != marker))
223 LAspan(x, y - 1, me, him, iL);
224 if ((y < maxPoint) && (markBoard[x][y + 1] != marker))
225 LAspan(x, y + 1, me, him, iL);
226 }
227 else if (bord[x][y] == him)
228 if (gList[gMap[groupIDs[x][y]]].groupMark != grpMark)
229 {
230 gList[gMap[groupIDs[x][y]]].groupMark = grpMark;
231 iL->indx = iL->indx + 1;
232 iL->v[iL->indx] = gMap[groupIDs[x][y]];
233 }
234 } /* span */
235
236listAdjacents(x, y, iL)
237short x, y;
238intList *iL;
239{ /* listAdjacents */
240 short me, him;
241#ifdef DEBUG
242 printf( "listAdjacents\n" );
243#endif
244 grpMark = grpMark + 1;
245 marker = marker + 1;
246 if (marker == 0)
247 {
248 initArray(markBoard);
249 marker = 1;
250 }
251 iL->indx = 0;
252 me = bord[x][y];
253 him = -me;
254 LAspan(x, y, me , him, iL);
255} /* listAdjacents */
256
257LDspan(x, y, me, diags)
258short x, y, me;
259sPointList *diags;
260 { /* span */
261#ifdef DEBUG
262 printf( "LDspan\n" );
263#endif
264 markBoard[x][y] = marker;
265 if ((x > 0) && (y > 0) &&
266 (bord[x - 1][y - 1] == 0) &&
267 (bord[x][y - 1] != me) &&
268 (bord[x - 1][y] != me) &&
269 (markBoard[x - 1][y - 1] != marker))
270 {
271 markBoard[x - 1][y - 1] = marker;
272 diags->indx = diags->indx + 1;
273 if (diags->indx <= maxSPoint)
274 {
275 diags->p[diags->indx].px = x - 1;
276 diags->p[diags->indx].py = y - 1;
277 }
278 }
279 if ((x < maxPoint) && (y > 0) &&
280 (bord[x + 1][y - 1] == 0) &&
281 (bord[x][y - 1] != me) &&
282 (bord[x + 1][y] != me) &&
283 (markBoard[x + 1][y - 1] != marker))
284 {
285 markBoard[x + 1][y - 1] = marker;
286 diags->indx = diags->indx + 1;
287 if (diags->indx <= maxSPoint)
288 {
289 diags->p[diags->indx].px = x + 1;
290 diags->p[diags->indx].py = y - 1;
291 }
292 }
293 if ((x > 0) && (y < maxPoint) &&
294 (bord[x - 1][y + 1] == 0) &&
295 (bord[x][y + 1] != me) &&
296 (bord[x - 1][y] != me) &&
297 (markBoard[x - 1][y + 1] != marker))
298 {
299 markBoard[x - 1][y + 1] = marker;
300 diags->indx = diags->indx + 1;
301 if (diags->indx <= maxSPoint)
302 {
303 diags->p[diags->indx].px = x - 1;
304 diags->p[diags->indx].py = y + 1;
305 }
306 }
307 if ((x < maxPoint) && (y < maxPoint) &&
308 (bord[x + 1][y + 1] == 0) &&
309 (bord[x][y + 1] != me) &&
310 (bord[x + 1][y] != me) &&
311 (markBoard[x + 1][y + 1] != marker))
312 {
313 markBoard[x + 1][y + 1] = marker;
314 diags->indx = diags->indx + 1;
315 if (diags->indx <= maxSPoint)
316 {
317 diags->p[diags->indx].px = x + 1;
318 diags->p[diags->indx].py = y + 1;
319 }
320 }
321 if ((x > 0) && (bord[x - 1][y] == me) &&
322 (markBoard[x - 1][y] != marker))
323 LDspan(x - 1, y, me, diags);
324 if ((x < maxPoint) && (bord[x + 1][y] == me) &&
325 (markBoard[x + 1][y] != marker))
326 LDspan(x + 1, y, me, diags);
327 if ((y > 0) && (bord[x][y - 1] == me) &&
328 (markBoard[x][y - 1] != marker))
329 LDspan(x, y - 1, me, diags);
330 if ((y < maxPoint) && (bord[x][y + 1] == me) &&
331 (markBoard[x][y + 1] != marker))
332 LDspan(x, y + 1, me , diags);
333} /* span */
334
335listDiags(x, y, diags)
336short x, y;
337sPointList *diags;
338{ /* listDiags */
339 short me;
340#ifdef DEBUG
341 printf( "listDiags\n" );
342#endif
343 me = bord[x][y];
344 diags->indx = 0;
345 marker = marker + 1;
346 if (marker == 0)
347 {
348 initArray(markBoard);
349 marker = 1;
350 }
351 LDspan(x, y, me, diags);
352} /* listDiags */
353
354intersectPlist(p1, p2, pr)
355pointList *p1, *p2, *pr;
356{ /* intersectPlist */
357 short i, j, k;
358#ifdef DEBUG
359 printf( "intersectPlist\n" );
360#endif
361 marker = marker + 1;
362 if (marker == 0)
363 {
364 initArray(markBoard);
365 marker = 1;
366 }
367 pr->indx = 0;
368 for (i = 1; i <= p1->indx; i++)
369 markBoard[p1->p[i].px][p1->p[i].py] = marker;
370 j = 0;
371 for (i = 1; i <= p2->indx; i++)
372 if (markBoard[p2->p[i].px][p2->p[i].py] == marker)
373 {
374 j = j + 1;
375 pr->p[j] = p2->p[i];
376 }
377 pr->indx = j;
378} /* intersectPlist */
379
380initArray(ary)
381intBoard ary;
382{ /* initArray */
383 short i, j;
384 for (i = 0; i <= maxPoint; i++)
385 for (j = 0; j <= maxPoint; j++)
386 ary[i][j] = 0;
387} /* initArray */
388
389initState()
390{ /* initState */
391 short i, j;
392 for (i = 0; i <= maxPoint; i++)
393 for (j = 0; j <= maxPoint; j++)
394 {
395 extra[i][j] = 0;
396 claim[i][j] = 0;
397 groupIDs[i][j] = 0;
398 connectMap[i][j] = 0;
399 protPoints[i][j] = 0;
400 }
401} /* initState */
402
403copyArray( dest, src )
404intBoard dest, src;
405{
406 short x, y;
407 for (y = 0; y <= maxPoint; y++)
408 for (x = 0; x <= maxPoint; x++)
409 dest[x][y] = src[x][y];
410}
411
412/*
413 generates a one-point spread in the force field array (claim)
414
415 the spread from a single point after four calls is:
416
417 1
418 2 2 2
419 2 4 6 4 2
420 2 4 8 10 8 4 2
421 1 2 6 10 62 10 6 2 1
422 2 4 8 10 8 4 2
423 2 4 6 4 2
424 2 2 2
425 1
426
427*/
428stake()
429{
430 short x, y;
431 initArray( extra );
432 for (y = 0; y <= maxPoint; y++)
433 for (x = 0; x <= maxPoint; x++)
434 {
435 extra[x][y] = extra[x][y] + claim[x][y];
436 if (claim[x][y] > 0)
437 {
438 if (x > 0) extra[x-1][y] += 1;
439 if (y > 0) extra[x][y-1] += 1;
440 if (x < maxPoint) extra[x+1][y] += 1;
441 if (y < maxPoint) extra[x][y+1] += 1;
442 }
443 else if (claim[x][y] < 0)
444 {
445 if (x > 0) extra[x-1][y] -= 1;
446 if (y > 0) extra[x][y-1] -= 1;
447 if (x < maxPoint) extra[x+1][y] -= 1;
448 if (y < maxPoint) extra[x][y+1] -= 1;
449 }
450 }
451 copyArray( claim, extra );
452} /* stake */
453
454/*
455 sets up claim from the current board position
456*/
457spread()
458{
459 short x, y;
460 for (y = 0; y <= maxPoint; y++)
461 for (x = 0; x <= maxPoint; x++)
462 claim[x][y] = ndbord[x][y] * 50;
463 stake();
464 stake();
465 stake();
466 stake();
467} /* spread */
468
469/*
470 gList is initialized with the size, loc, and libCount of each group
471 groupIDs contains the serial numbers of the groups.
472*/
473Resspan(x, y, gID, gSize, libCount, who)
474short x, y, gID, *gSize, *libCount, who;
475 { /* span */
476 if ((bord[x][y] == 0) &&
477 (markBoard[x][y] != marker)) /* a liberty */
478 {
479 markBoard[x][y] = marker;
480 *libCount = *libCount + 1;
481 }
482 else if ((bord[x][y] == who) &&
483 (groupIDs[x][y] == 0))
484 {
485 groupIDs[x][y] = gID;
486 *gSize = *gSize + 1;
487 if (x > 0)
488 Resspan(x - 1, y, gID, gSize, libCount, who);
489 if (x < maxPoint)
490 Resspan(x + 1, y, gID, gSize, libCount, who);
491 if (y > 0)
492 Resspan(x, y - 1, gID, gSize, libCount, who);
493 if (y < maxPoint)
494 Resspan(x, y + 1, gID, gSize, libCount, who);
495 }
496 } /* span */
497
498respreicen()
499{ /* respreicen */
500 short i, j, gID, libCount, gSize, who;
501 gID = 0;
502#ifdef DEBUG
503 printf( "respreicen\n" );
504#endif
505 for (i = 0; i <= maxPoint; i++)
506 for (j = 0; j <= maxPoint; j++)
507 groupIDs[i][j] = 0;
508 for (i = 0; i <= maxPoint; i++)
509 for (j = 0; j <= maxPoint; j++)
510 if ((bord[i][j] != 0) && /* a stone there */
511 (groupIDs[i][j] == 0)) /* not seen yet */
512 {
513 marker = marker + 1;
514 if (marker == 0)
515 {
516 initArray(markBoard);
517 marker = 1;
518 }
519 gID = gID + 1;
520 libCount = 0;
521 gSize = 0;
522 who = bord[i][j];
523 Resspan(i, j, gID, &gSize, &libCount, who); /* span the group, collecting info */
524 gList[gID].groupMark = 0;
525 gList[gID].atLevel = 0;
526 gList[gID].isLive = FALSE; /* we don't know yet */
527 gList[gID].isDead = FALSE;
528 gList[gID].numEyes = -1;
529 gList[gID].size = gSize;
530 gList[gID].libC = libCount;
531 gList[gID].lx = i;
532 gList[gID].ly = j;
533 gMap[gID] = gID; /* set up identity map */
534 }
535 maxGroupID = gID;
536 newGID = gID;
537 grpMark = 0;
538} /* respreicen */
539
540/*
541 play z at [x, y].
542 killFlag is set true if anything is killed.
543*/
544killGroup(x, y, me, him)
545short x, y, me, him;
546 { /* killGroup */
547#ifdef DEBUG
548 printf( "killGroup\n" );
549#endif
550 playMark = playMark + 1;
551 /* record this kill */
552 playStack[playMark].kind = rem;
553 playStack[playMark].uval.rem.who = him;
554 playStack[playMark].uval.rem.xl = x;
555 playStack[playMark].uval.rem.yl = y;
556 playStack[playMark].gID = groupIDs[x][y];
557 playStack[playMark].uval.rem.sNumber = goboard[x][y].mNum;
558 if (showTrees)
559 rstone(x, y);
560 numCapt = numCapt + 1;
561 bord[x][y] = 0;
562 groupIDs[x][y] = 0;
563 if (x > 0)
564 {
565 if (bord[x - 1][y] == me)
566 {
567 nlcGroup.indx = nlcGroup.indx + 1;
568 nlcGroup.v[nlcGroup.indx] = gMap[groupIDs[x - 1][y]];
569 }
570 else if (bord[x - 1][y] == him)
571 killGroup(x - 1, y, me , him);
572 }
573 if (x < maxPoint)
574 {
575 if (bord[x + 1][y] == me)
576 {
577 nlcGroup.indx = nlcGroup.indx + 1;
578 nlcGroup.v[nlcGroup.indx] = gMap[groupIDs[x + 1][y]];
579 }
580 else if (bord[x + 1][y] == him)
581 killGroup(x + 1, y, me, him);
582 }
583 if (y > 0)
584 {
585 if (bord[x][y - 1] == me)
586 {
587 nlcGroup.indx = nlcGroup.indx + 1;
588 nlcGroup.v[nlcGroup.indx] = gMap[groupIDs[x][y - 1]];
589 }
590 else if (bord[x][y - 1] == him)
591 killGroup(x, y - 1, me, him);
592 }
593 if (y < maxPoint)
594 {
595 if (bord[x][y + 1] == me)
596 {
597 nlcGroup.indx = nlcGroup.indx + 1;
598 nlcGroup.v[nlcGroup.indx] = gMap[groupIDs[x][y + 1]];
599 }
600 else if (bord[x][y + 1] == him)
601 killGroup(x, y + 1, me, him);
602 }
603 } /* killGroup */
604
605mergeGroup(sGID, myGID)
606short sGID, myGID;
607 { /* mergeGroup */
608 short i;
609#ifdef DEBUG
610 printf( "mergeGroup\n" );
611#endif
612 for (i = 1; i <= newGID; i++)
613 if (gMap[i] == sGID)
614 {
615 playMark = playMark + 1;
616 playStack[playMark].kind = reMap;
617 playStack[playMark].gID = i;
618 playStack[playMark].uval.reMap.oldGID = sGID;
619 gMap[i] = myGID;
620 }
621 } /* mergeGroup */
622
623tryPlay(x, y, z)
624short x, y, z;
625{ /* plei */
626 short i, me, him, myGID;
627 short isNew;
628#ifdef DEBUG
629 printf( "tryPlay\n" );
630#endif
631 me = z;
632 him = -me;
633 killFlag = FALSE; /* set true if something is killed */
634 numCapt = 0;
635 tryLevel = tryLevel + 1;
636 isNew = FALSE;
637 bord[x][y] = z; /* play the stone */
638 if ((x > 0) && (bord[x - 1][y] == me)) /* connect to adjacent group */
639 myGID = gMap[groupIDs[x - 1][y]];
640 else if ((x < maxPoint) && (bord[x + 1][y] == me))
641 myGID = gMap[groupIDs[x + 1][y]];
642 else if ((y > 0) && (bord[x][y - 1] == me))
643 myGID = gMap[groupIDs[x][y - 1]];
644 else if ((y < maxPoint) && (bord[x][y + 1] == me))
645 myGID = gMap[groupIDs[x][y + 1]];
646 else /* nobody to connect to */
647 {
648 newGID = newGID + 1;
649 isNew = TRUE;
650 myGID = newGID;
651 gList[myGID].groupMark = 0;
652 gList[myGID].atLevel = tryLevel;
653 gList[myGID].isLive = FALSE;
654 gList[myGID].numEyes = -1;
655 gList[myGID].size = -1;
656 gList[myGID].lx = x;
657 gList[myGID].ly = y;
658 gMap[myGID] = myGID;
659 }
660 groupIDs[x][y] = myGID;
661 playMark = playMark + 1;
662 /* record this move */
663 playStack[playMark].kind = add;
664 playStack[playMark].uval.add.who = me;
665 playStack[playMark].uval.add.xl = x;
666 playStack[playMark].uval.add.yl = y;
667 playStack[playMark].gID = myGID;
668 playStack[playMark].uval.add.sNumber = 0;
669 if (isNew)
670 playStack[playMark].uval.add.nextGID = newGID - 1;
671 else
672 playStack[playMark].uval.add.nextGID = newGID;
673 if (showTrees)
674 sstone(me, x, y, 0);
675 /* merge adjacent groups */
676 if ((x > 0) && (bord[x - 1][y] == me) &&
677 (gMap[groupIDs[x - 1][y]] != myGID))
678 mergeGroup(gMap[groupIDs[x - 1][y]], myGID);
679 if ((x < maxPoint) && (bord[x + 1][y] == me) &&
680 (gMap[groupIDs[x + 1][y]] != myGID))
681 mergeGroup(gMap[groupIDs[x + 1][y]], myGID);
682 if ((y > 0) && (bord[x][y - 1] == me) &&
683 (gMap[groupIDs[x][y - 1]] != myGID))
684 mergeGroup(gMap[groupIDs[x][y - 1]], myGID);
685 if ((y < maxPoint) && (bord[x][y + 1] == me) &&
686 (gMap[groupIDs[x][y + 1]] != myGID))
687 mergeGroup(gMap[groupIDs[x][y + 1]], myGID);
688 /* kill opposing groups, listing affected groups */
689 nlcGroup.indx = 1;
690 nlcGroup.v[1] = myGID; /* init list to include me */
691 if ((x > 0) && (bord[x - 1][y] == him) &&
692 (gList[gMap[groupIDs[x - 1][y]]].libC == 1))
693 {
694 killFlag = TRUE;
695 killGroup(x - 1, y, me, him);
696 }
697 if ((x < maxPoint) && (bord[x + 1][y] == him) &&
698 (gList[gMap[groupIDs[x + 1][y]]].libC == 1))
699 {
700 killFlag = TRUE;
701 killGroup(x + 1, y, me, him);
702 }
703 if ((y > 0) && (bord[x][y - 1] == him) &&
704 (gList[gMap[groupIDs[x][y - 1]]].libC == 1))
705 {
706 killFlag = TRUE;
707 killGroup(x, y - 1, me, him);
708 }
709 if ((y < maxPoint) && (bord[x][y + 1] == him) &&
710 (gList[gMap[groupIDs[x][y + 1]]].libC == 1))
711 {
712 killFlag = TRUE;
713 killGroup(x, y + 1, me, him);
714 }
715 /* list groups adjacent to me */
716 if ((x > 0) && (bord[x - 1][y] == him))
717 {
718 nlcGroup.indx = nlcGroup.indx + 1;
719 nlcGroup.v[nlcGroup.indx] = gMap[groupIDs[x - 1][y]];
720 }
721 if ((x < maxPoint) && (bord[x + 1][y] == him))
722 {
723 nlcGroup.indx = nlcGroup.indx + 1;
724 nlcGroup.v[nlcGroup.indx] = gMap[groupIDs[x + 1][y]];
725 }
726 if ((y > 0) && (bord[x][y - 1] == him))
727 {
728 nlcGroup.indx = nlcGroup.indx + 1;
729 nlcGroup.v[nlcGroup.indx] = gMap[groupIDs[x][y - 1]];
730 }
731 if ((y < maxPoint) && (bord[x][y + 1] == him))
732 {
733 nlcGroup.indx = nlcGroup.indx + 1;
734 nlcGroup.v[nlcGroup.indx] = gMap[groupIDs[x][y + 1]];
735 }
736 /* fix liberty count for affected groups */
737 grpMark = grpMark + 1;
738 for (i = 1; i <= nlcGroup.indx; i++)
739 if (gList[nlcGroup.v[i]].groupMark != grpMark)
740 {
741 if (gList[nlcGroup.v[i]].atLevel != tryLevel)
742 {
743 playMark = playMark + 1;
744 playStack[playMark].kind = chLib;
745 playStack[playMark].gID = nlcGroup.v[i];
746 playStack[playMark].uval.chLib.oldLevel =
747 gList[nlcGroup.v[i]].atLevel;
748 playStack[playMark].uval.chLib.oldLC =
749 gList[nlcGroup.v[i]].libC;
750 }
751 gList[nlcGroup.v[i]].groupMark = grpMark;
752 gList[nlcGroup.v[i]].atLevel = tryLevel;
753 spanGroup(gList[nlcGroup.v[i]].lx, gList[nlcGroup.v[i]].ly, &pPlist);
754 gList[nlcGroup.v[i]].libC = pPlist.indx;
755 }
756} /* plei */
757
758saveState()
759{ /* saveState */
760 playMark = 0;
761 tryLevel = 0;
762 newGID = maxGroupID;
763} /* saveState */
764
765/*
766 undoes a move sequence back to uMark
767*/
768undoTo(uMark)
769short uMark;
770{ /* undoTo */
771 short i, xl, yl;
772#ifdef DEBUG
773 printf( "undoTo\n" );
774#endif
775 for (i = playMark; i >= uMark + 1; i--)
776 if (playStack[i].kind == rem)
777 {
778 xl = playStack[i].uval.rem.xl;
779 yl = playStack[i].uval.rem.yl;
780 bord[xl][yl] = playStack[i].uval.rem.who;
781 groupIDs[xl][yl] = playStack[i].gID;
782 if (showTrees)
783 sstone(playStack[i].uval.rem.who, xl, yl,
784 playStack[i].uval.rem.sNumber);
785 }
786 else if (playStack[i].kind == add)
787 {
788 xl = playStack[i].uval.add.xl;
789 yl = playStack[i].uval.add.yl;
790 bord[xl][yl] = 0;
791 groupIDs[xl][yl] = 0;
792 tryLevel = tryLevel - 1;
793 newGID = playStack[i].uval.add.nextGID;
794 if (showTrees)
795 rstone(xl, yl);
796 }
797 else if (playStack[i].kind == reMap)
798 gMap[playStack[i].gID] = playStack[i].uval.reMap.oldGID;
799 else /* change libs of group - gID is pre-mapped */
800 {
801 gList[playStack[i].gID].libC = playStack[i].uval.chLib.oldLC;
802 gList[playStack[i].gID].atLevel = playStack[i].uval.chLib.oldLevel;
803 }
804 playMark = uMark;
805} /* undoTo */
806
807/*
808 restores the state of the world after trying a move sequence
809*/
810restoreState()
811{ /* restoreState */
812#ifdef DEBUG
813 printf( "restoreState\n" );
814#endif
815 if (playMark > 0)
816 {
817 undoTo(0);
818 playMark = 0;
819 tryLevel = 0;
820 }
821} /* restoreState */
822
823/* exception bpt; */
824
825
826/*
827 returns true if (the group (at gx, gy) is saveable.
828 if so, returns the point to play at in savex, savey
829*/
830short saveable(gx, gy, savex, savey)
831short gx, gy, *savex, *savey;
832{ /* saveable */
833 short me, him, gx1, gx2, i, j, smark, mark2, tl, result;
834 char sChar;
835 sPointList dList;
836 point tp;
837 short libList[maxSPoint+1];
838#ifdef DEBUG
839 printf( "saveable\n" );
840#endif
841 dbStop = TRUE;
842 me = bord[gx][gy];
843 him = -me;
844 if (me == 1)
845 sChar = '|';
846 else
847 sChar = '>';
848/* write(sChar); */
849 spanGroup(gx, gy, &plist3); /* find my liberties */
850 if (adjInAtari) /* one of my options is to kill */
851 {
852 listAdjacents(gx, gy, &aList);
853 for (i = 1; i <= aList.indx; i++)
854 if (gList[aList.v[i]].libC == 1)
855 {
856 spanGroup(gList[aList.v[i]].lx, gList[aList.v[i]].ly,
857 &pList1); /* find it's liberty */
858 plist3.indx = plist3.indx + 1;
859 plist3.p[plist3.indx].px = pList1.p[1].px;
860 plist3.p[plist3.indx].py = pList1.p[1].py;
861 }
862 }
863 for (i = 1; i <= maxSPoint; i++)
864 libList[i] = -1;
865 if ((utilPlayLevel > 4) &&
866 (gList[gMap[groupIDs[gx][gy]]].libC > 1)) /* account for diags */
867 {
868 listDiags(gx, gy, &dList);
869 j = 0;
870 i = plist3.indx;
871 while ((j < dList.indx) &&
872 (i < maxSPoint))
873 {
874 j = j + 1;
875 i = i + 1;
876 libList[i] = 100;
877 plist3.p[i].px = dList.p[j].px;
878 plist3.p[i].py = dList.p[j].py;
879 }
880 plist3.indx = i;
881 }
882 if (plist3.indx > 1) /* sort by decreasing lib count */
883 {
884 for (i = 1; i <= plist3.indx; i++)
885 if (libList[i] != 100)
886 {
887 mark2 = playMark;
888 tryPlay(plist3.p[i].px, plist3.p[i].py, me);
889 libList[i] = gList[gMap[groupIDs[gx][gy]]].libC;
890 if (libList[i] > treeLibLim) /* i'm safe */
891 {
892 *savex = plist3.p[i].px;
893 *savey = plist3.p[i].py;
894 result = TRUE;
895 goto one;
896 }
897 undoTo(mark2);
898 }
899 for (i = 1; i <= plist3.indx - 1; i++)
900 for (j = i + 1; j <= plist3.indx; j++)
901 if (libList[i] < libList[j])
902 {
903 tl = libList[i];
904 libList[i] = libList[j];
905 libList[j] = tl;
906 tp = plist3.p[i];
907 plist3.p[i] = plist3.p[j];
908 plist3.p[j] = tp;
909 }
910 }
911 for (i = 1; i <= plist3.indx; i++)
912 {
913 *savex = plist3.p[i].px;
914 *savey = plist3.p[i].py;
915 if (legal[*savex][*savey])
916 {
917 smark = playMark;
918 tryPlay(*savex, *savey, me);
919 pause();
920 if (gList[gMap[groupIDs[*savex][*savey]]].libC > 1)
921 if (gList[gMap[groupIDs[gx][gy]]].libC > treeLibLim)
922 {
923 restoreState();
924/* sClearChar(sChar, rXor); */
925 return TRUE;
926 }
927 else if (gList[gMap[groupIDs[gx][gy]]].libC > 1)
928 if (! killable(gx, gy, &gx1, &gx2))
929 {
930 restoreState();
931/* sClearChar(sChar, rXor); */
932 return TRUE;
933 }
934 undoTo(smark);
935 }
936 }
937 result = FALSE;
938one:
939 restoreState();
940/* sClearChar(sChar, rXor); */
941 return result;
942} /* saveable */
943
944/*
945 marks unsavable groups as dead
946*/
947markDead()
948{ /* markDead */
949 short i, j, gx, gy, result;
950#ifdef DEBUG
951 printf( "markDead\n" );
952#endif
953 for (i = 1; i <= maxGroupID; i++)
954 if (killable(gList[i].lx, gList[i].ly, &gx, &gy))
955 result = ! saveable(gList[i].lx, gList[i].ly, &gx, &gy);
956 else
957 result = FALSE;
958 for (i = 0; i <= maxPoint; i++)
959 for (j = 0; j <= maxPoint; j++)
960 if (bord[i][j] == 0)
961 ndbord[i][j] = 0;
962 else if (gList[groupIDs[i][j]].isDead)
963 ndbord[i][j] = 0;
964 else
965 ndbord[i][j] = bord[i][j];
966} /* markDead */
967
968/*
969 marks groups with two eyes as live
970*/
971MLspan(x, y, saw1, sawm1, size, sMark)
972short x, y, *saw1, *sawm1, *size, sMark;
973 { /* span */
974 if (ndbord[x][y] == 1)
975 *saw1 = TRUE;
976 else if (ndbord[x][y] == -1)
977 *sawm1 = TRUE;
978 else if (sGroups[x][y] == 0)
979 {
980 sGroups[x][y] = sMark;
981 *size = *size + 1;
982 if (x > 0)
983 MLspan(x - 1, y, saw1, sawm1, size, sMark);
984 if (x < maxPoint)
985 MLspan(x + 1, y, saw1, sawm1, size, sMark);
986 if (y > 0)
987 MLspan(x, y - 1, saw1, sawm1, size, sMark);
988 if (y < maxPoint)
989 MLspan(x, y + 1, saw1, sawm1, size, sMark);
990 }
991 } /* span */
992
993short CLspan(x, y, numEyes, who)
994short x, y, *numEyes, who;
995 { /* span */
996 markBoard[x][y] = marker;
997 if (ndbord[x][y] == 0)
998 {
999 if ((sList[sGroups[x][y]].sm != marker) &&
1000 (sList[sGroups[x][y]].w == who))
1001 {
1002 sList[sGroups[x][y]].sm = marker;
1003 if (sList[sGroups[x][y]].s > 6)
1004 return TRUE;
1005 *numEyes = *numEyes + 1;
1006 if (*numEyes > 1)
1007 return TRUE;
1008 }
1009 }
1010 else if (bord[x][y] == who)
1011 {
1012 if ((x > 0) &&
1013 (markBoard[x - 1][y] != marker))
1014 if (CLspan(x - 1, y, numEyes, who)) return TRUE;
1015 if ((x < maxPoint) &&
1016 (markBoard[x + 1][y] != marker))
1017 if (CLspan(x + 1, y, numEyes, who)) return TRUE;
1018 if ((y > 0) &&
1019 (markBoard[x][y - 1] != marker))
1020 if (CLspan(x, y - 1, numEyes, who)) return TRUE;
1021 if ((y < maxPoint) &&
1022 (markBoard[x][y + 1] != marker))
1023 if (CLspan(x, y + 1, numEyes, who)) return TRUE;
1024 }
1025 return FALSE;
1026 } /* span */
1027
1028short checkLive(x, y)
1029short x, y;
1030 { /* checkLive */
1031 short numEyes, who;
1032#ifdef DEBUG
1033 printf( "checkLive\n" );
1034#endif
1035 numEyes = 0;
1036 who = bord[x][y];
1037 marker = marker + 1;
1038 return CLspan(x, y, &numEyes, who);
1039 } /* checkLive */
1040
1041markLive()
1042{ /* markLive */
1043 short i, j, size, sMark = 0;
1044 short saw1, sawm1;
1045#ifdef DEBUG
1046 printf( "markLive\n" );
1047#endif
1048 initArray(sGroups);
1049 for (i = 0; i <= maxPoint; i++)
1050 for (j = 0; j <= maxPoint; j++)
1051 if ((sGroups[i][j] == 0) &&
1052 (ndbord[i][j] == 0))
1053 {
1054 size = 0;
1055 sMark = sMark + 1;
1056 sawm1 = FALSE;
1057 saw1 = FALSE;
1058 MLspan(i, j, &saw1, &sawm1, &size, sMark);
1059 sList[sMark].s = size;
1060 sList[sMark].sm = 0;
1061 if (sawm1)
1062 if (saw1)
1063 sList[sMark].w = 0;
1064 else
1065 sList[sMark].w = -1;
1066 else if (saw1)
1067 sList[sMark].w = 1;
1068 else
1069 sList[sMark].w = 0;
1070 }
1071 for (i = 1; i <= maxGroupID; i++)
1072 if (! gList[i].isDead)
1073 gList[i].isLive = checkLive(gList[i].lx, gList[i].ly);
1074} /* markLive */
1075
1076/*
1077 generates the connection map and the protected point map.
1078*/
1079genConnects()
1080{ /* genConnects */
1081 short x, y, numStones;
1082#ifdef DEBUG
1083 printf( "genConnects\n" );
1084#endif
1085 for (x = 0; x <= maxPoint; x++)
1086 for (y = 0; y <= maxPoint; y++)
1087 {
1088 connectMap[x][y] = 0;
1089 protPoints[x][y] = 0;
1090 }
1091 for (x = 0; x <= maxPoint; x++)
1092 for (y = 0; y <= maxPoint; y++)
1093 if (bord[x][y] == 1) /* map connections to this stone */
1094 {
1095 if (x > 0) /* direct connection */
1096 connectMap[x - 1][y] += 1;
1097 if (x < maxPoint)
1098 connectMap[x + 1][y] += 1;
1099 if (y > 0)
1100 connectMap[x][y - 1] += 1;
1101 if (y < maxPoint)
1102 connectMap[x][y + 1] += 1;
1103 if ((x > 0) && (y > 0) && /* diagonal connection */
1104 (bord[x - 1][y] == 0) && (bord[x][y - 1] == 0))
1105 connectMap[x - 1][y - 1] += 1;
1106 if ((x < maxPoint) && (y > 0) &&
1107 (bord[x + 1][y] == 0) && (bord[x][y - 1] == 0))
1108 connectMap[x + 1][y - 1] += 1;
1109 if ((x < maxPoint) && (y < maxPoint) &&
1110 (bord[x + 1][y] == 0) && (bord[x][y + 1] == 0))
1111 connectMap[x + 1][y + 1] += 1;
1112 if ((x > 0) && (y < maxPoint) &&
1113 (bord[x - 1][y] == 0) && (bord[x][y + 1] == 0))
1114 connectMap[x - 1][y + 1] += 1;
1115 if ((x > 1) && (claim[x - 1][y] > 3)) /* one point jump */
1116 connectMap[x - 2][y] += 1;
1117 if ((x < (maxPoint - 1)) && (claim[x + 1][y] > 3))
1118 connectMap[x + 2][y] += 1;
1119 if ((y > 1) && (claim[x][y - 1] > 3))
1120 connectMap[x][y - 2] += 1;
1121 if ((y < (maxPoint - 1)) && (claim[x][y + 1] > 3))
1122 connectMap[x][y + 2] += 1;
1123 if ((x > 1) && (y > 0) && /* knight's move */
1124 (claim[x - 1][y] > 3) && (claim[x - 1][y - 1] > 3))
1125 connectMap[x - 2][y - 1] += 1;
1126 if ((x > 0) && (y > 1) &&
1127 (claim[x][y - 1] > 3) && (claim[x - 1][y - 1] > 3))
1128 connectMap[x - 1][y - 2] += 1;
1129 if ((x < (maxPoint - 1)) && (y > 0) &&
1130 (claim[x + 1][y] > 3) && (claim[x + 1][y - 1] > 3))
1131 connectMap[x + 2][y - 1] += 1;
1132 if ((x < maxPoint) && (y > 1) &&
1133 (claim[x][y - 1] > 3) && (claim[x + 1][y - 1] > 3))
1134 connectMap[x + 1][y - 2] += 1;
1135 if ((x > 1) && (y < maxPoint) &&
1136 (claim[x - 1][y] > 3) && (claim[x - 1][y + 1] > 3))
1137 connectMap[x - 2][y + 1] += 1;
1138 if ((x > 0) && (y < (maxPoint - 1)) &&
1139 (claim[x][y + 1] > 3) && (claim[x - 1][y + 1] > 3))
1140 connectMap[x - 1][y + 2] += 1;
1141 if ((x < (maxPoint - 1)) && (y < maxPoint) &&
1142 (claim[x + 1][y] > 3) && (claim[x + 1][y + 1] > 3))
1143 connectMap[x + 2][y + 1] += 1;
1144 if ((x < maxPoint) && (y < (maxPoint - 1)) &&
1145 (claim[x][y + 1] > 3) && (claim[x + 1][y + 1] > 3))
1146 connectMap[x + 1][y + 2] += 1;
1147 }
1148 else if (bord[x][y] == 0) /* see if protected point */
1149 {
1150 numStones = 0;
1151 if (x == 0)
1152 numStones = numStones + 1;
1153 if (y == 0)
1154 numStones = numStones + 1;
1155 if (x == maxPoint)
1156 numStones = numStones + 1;
1157 if (y == maxPoint)
1158 numStones = numStones + 1;
1159 if ((x > 0) && (bord[x - 1][y] == 1))
1160 numStones = numStones + 1;
1161 if ((y > 0) && (bord[x][y - 1] == 1))
1162 numStones = numStones + 1;
1163 if ((x < maxPoint) && (bord[x + 1][y] == 1))
1164 numStones = numStones + 1;
1165 if ((y < maxPoint) && (bord[x][y + 1] == 1))
1166 numStones = numStones + 1;
1167 if (numStones == 4)
1168 protPoints[x][y] = 1;
1169 else if (numStones == 3)
1170 {
1171 if ((x > 0) &&
1172 ((bord[x - 1][y] == 0) ||
1173 ((bord[x - 1][y] == -1) &&
1174 (gList[groupIDs[x - 1][y]].libC == 1))))
1175 protPoints[x][y] = 1;
1176 else if ((x < maxPoint) &&
1177 ((bord[x + 1][y] == 0) ||
1178 ((bord[x + 1][y] == -1) &&
1179 (gList[groupIDs[x + 1][y]].libC == 1))))
1180 protPoints[x][y] = 1;
1181 else if ((y > 0) &&
1182 ((bord[x][y - 1] == 0) ||
1183 ((bord[x][y - 1] == -1) &&
1184 (gList[groupIDs[x][y - 1]].libC == 1))))
1185 protPoints[x][y] = 1;
1186 else if ((y < maxPoint) &&
1187 ((bord[x][y + 1] == 0) ||
1188 ((bord[x][y + 1] == -1) &&
1189 (gList[groupIDs[x][y + 1]].libC == 1))))
1190 protPoints[x][y] = 1;
1191 }
1192 }
1193 for (x = 0; x <= maxPoint; x++)
1194 for (y = 0; y <= maxPoint; y++)
1195 if (bord[x][y] != 0)
1196 {
1197 connectMap[x][y] = 0;
1198 protPoints[x][y] = 0;
1199 }
1200} /* genConnects */
1201
1202/*
1203 generates the whole state of the game.
1204*/
1205genState()
1206{ /* genState */
1207#ifdef DEBUG
1208 printf( "genState\n" );
1209#endif
1210 inGenState = TRUE;
1211 respreicen();
1212 markDead();
1213 markLive();
1214 spread();
1215 genConnects();
1216#ifdef DEBUG
1217/* printBoard( claim, "claim" ); */
1218/* printBoard( bord, "bord" ); */
1219/* printBoard( ndbord, "ndbord" );
1220 printBoard( sGroups, "sGroups" );
1221 printBoard( groupIDs, "groupIDs" );
1222 printBoard( connectMap, "connectMap" );
1223 printBoard( protPoints, "protPoints" ); */
1224#endif
1225 inGenState = FALSE;
1226} /* genState */
1227
1228/*
1229 generates a value for the [x, y] location that appears to get larger
1230 for points that are saddle points in the influence graph (klein)
1231*/
1232short tencen(x, y)
1233short x, y;
1234{ /* tencen */
1235 short a, b, c, d, w, z;
1236#ifdef DEBUG
1237 printf( "tencen\n" );
1238#endif
1239 if (claim[x][y] > -1) /* if (he does not influence this area, return 50 */
1240 {
1241 return 50;
1242 }
1243 w = claim[x][y]; /* w <= -1 */
1244 a = iNil;
1245 if (x > 0)
1246 if (claim[x - 1][y] > -1) /* if (neighbor is not influenced by him */
1247 a = claim[x - 1][y] - w; /* score is sum of his influence on central */
1248 b = iNil; /* point and my influence on this neighbor */
1249 if (y > 0)
1250 if (claim[x][y - 1] > -1)
1251 b = claim[x][y - 1] - w;
1252 c = iNil;
1253 if (x < maxPoint)
1254 if (claim[x + 1][y] > -1)
1255 c = claim[x + 1][y] - w;
1256 d = iNil;
1257 if (y < maxPoint)
1258 if (claim[x][y + 1] > -1)
1259 d = claim[x][y + 1] - w;
1260 z = a; /* z = max(a, b, c, d) */
1261 if (z != iNil)
1262 {
1263 if ((b != iNil) &&
1264 (b > z))
1265 z = b;
1266 }
1267 else
1268 z = b;
1269 if (z != iNil)
1270 {
1271 if ((c != iNil) &&
1272 (c > z))
1273 z = c;
1274 }
1275 else
1276 z = c;
1277 if (z != iNil)
1278 {
1279 if ((d != iNil) &&
1280 (d > z))
1281 z = d;
1282 }
1283 else
1284 z = d;
1285 if ((z != iNil) &&
1286 ((x == 0) ||
1287 (y == 0) ||
1288 (x == maxPoint) ||
1289 (y == maxPoint)))
1290 z = z * 2; /* double z if (on the edge of the board ?? */
1291 if (z != iNil)
1292 return z;
1293 else
1294 return 50;
1295} /* tencen */
1296
1297initGPUtils()
1298{ /* initGPUtils */
1299#ifdef DEBUG
1300 printf( "initGPUtils\n" );
1301#endif
1302 initArray(markBoard);
1303 initState();
1304 marker = 0;
1305 playMark = 0;
1306 gList[0].isLive = FALSE;
1307 gList[0].isDead = FALSE;
1308 gList[0].libC = 0;
1309 gList[0].size = 0;
1310 gList[0].numEyes = 0;
1311 gList[0].lx = -1;
1312 gList[0].ly = -1;
1313 gMap[0] = 0;
1314 dbStop = FALSE;
1315 inGenState = FALSE;
1316} /* initGPUtils */
1317