summaryrefslogtreecommitdiff
path: root/noncore/games/go/killable.c
Side-by-side diff
Diffstat (limited to 'noncore/games/go/killable.c') (more/less context) (ignore whitespace changes)
-rw-r--r--noncore/games/go/killable.c373
1 files changed, 373 insertions, 0 deletions
diff --git a/noncore/games/go/killable.c b/noncore/games/go/killable.c
new file mode 100644
index 0000000..3ed2d2e
--- a/dev/null
+++ b/noncore/games/go/killable.c
@@ -0,0 +1,373 @@
+/* By Stoney Ballard */
+/* Ported from Pascal to C by Todd R. Johnson */
+
+#include "go.h"
+#include "goplayutils.h"
+#include "amigo.h"
+
+extern intBoard bord, groupIDs;
+extern boolBoard legal;
+extern groupRec gList[maxGroup];
+extern short gMap[maxGroup], adjInAtari, adj2Libs, playMark, treeLibLim,
+ utilPlayLevel, killFlag, depthLimit, dbStop, showTrees;
+extern pointList plist2;
+
+/*
+ returns true if the group (at x, y) is killable.
+ if so, returns the point to play at in killx, killy.
+*/
+
+ short me, him, depth, i, j, tryCount, tl, topMark, tkMark, mark2;
+ char sChar;
+ sPointList lList, dList;
+ point tp;
+ short libList[maxSPoint+1];
+ short esc;
+
+short mtNbrs(x, y)
+short x, y;
+ { /* mtNbrs */
+ short n = 0;
+ if ((x > 0) && (bord[x - 1][y] == 0))
+ n = n + 1;
+ if ((x < maxPoint) && (bord[x + 1][y] == 0))
+ n = n + 1;
+ if ((y > 0) && (bord[x][y - 1] == 0))
+ n = n + 1;
+ if ((y < maxPoint) && (bord[x][y + 1] == 0))
+ n = n + 1;
+ return n;
+ } /* mtNbrs */
+
+short killTree(tx, ty, gx, gy, escape, tkMark)
+short tx, ty, gx, gy, *escape, tkMark;
+ { /* killTree */
+ short curMark, mark2, mark3, i, j, k, tl, dStart, result;
+ sPointList lList1, lList2;
+ short libList[maxSPoint+1];
+ point tp;
+ short esc = FALSE;
+ tryCount = tryCount + 1;
+ if (tryCount > tryLimit)
+ {
+ undoTo(tkMark);
+/* for (i = 1; i <= depth - 1; i++)
+ {
+ sClearChar(sChar, rXor);
+ } */
+ depth = 1;
+ return FALSE;
+ }
+/* write(sChar); */
+ depth = depth + 1;
+ curMark = playMark;
+ tryPlay(tx, ty, me); /* try my move */
+ pause();
+ if (gList[gMap[groupIDs[tx][ty]]].libC == 0) /* I'm dead */
+ {
+ result = FALSE;
+ goto one;
+ }
+ else if (killFlag) /* I killed something of his */
+ {
+ result = TRUE;
+ goto one;
+ }
+ else if (gList[gMap[groupIDs[gx][gy]]].libC > treeLibLim) /* safe */
+ {
+ result = FALSE;
+ goto one;
+ }
+ else
+ {
+ sSpanGroup(gx, gy, &lList1); /* find his liberties */
+ if (gList[gMap[groupIDs[tx][ty]]].libC == 1) /* he can kill me */
+ {
+ if (lList1.indx < maxSPoint) /* add that option to his list */
+ {
+ lList1.indx = lList1.indx + 1;
+ spanGroup(tx, ty, &plist2); /* find my liberty */
+ lList1.p[lList1.indx].px = plist2.p[1].px;
+ lList1.p[lList1.indx].py = plist2.p[1].py;
+ }
+ else
+ {
+ result = FALSE;
+ goto one;
+ }
+ }
+ for (i = 1; i <= maxSPoint; i++) /* init liblist so diags can be marked */
+ libList[i] = -1;
+ if ((utilPlayLevel > 4) &&
+ (lList1.indx > 1) &&
+ (gList[gMap[groupIDs[gx][gy]]].libC > 1)) /* try diags */
+ {
+ listDiags(gx, gy, &dList);
+ j = 0;
+ i = lList1.indx;
+ while ((j < dList.indx) &&
+ (i < maxSPoint))
+ {
+ j = j + 1;
+ i = i + 1;
+ libList[i] = 0; /* mark this as a diag */
+ lList1.p[i].px = dList.p[j].px;
+ lList1.p[i].py = dList.p[j].py;
+ }
+ lList1.indx = i;
+ }
+ if (lList1.indx > 1) /* sort by decreasing lib count */
+ {
+ for (i = 1; i <= lList1.indx; i++)
+ if (libList[i] != 0) /* diags are tried last */
+ {
+ mark2 = playMark;
+ tryPlay(lList1.p[i].px, lList1.p[i].py, him);
+ libList[i] = gList[gMap[groupIDs[gx][gy]]].libC;
+ if ((libList[i] > treeLibLim) ||
+ ((libList[i] > (depthLimit - depth)) &&
+ (libList[i] > 2)))
+ {
+ *escape = TRUE;
+ result = FALSE;
+ goto one;
+ }
+ undoTo(mark2);
+ }
+ for (i = 1; i <= lList1.indx - 1; i++)
+ for (j = i + 1; j <= lList1.indx; j++)
+ if (libList[i] < libList[j])
+ {
+ tl = libList[i];
+ libList[i] = libList[j];
+ libList[j] = tl;
+ tp = lList1.p[i];
+ lList1.p[i] = lList1.p[j];
+ lList1.p[j] = tp;
+ }
+ }
+ for (i = 1; i <= lList1.indx + 1; i++) /* try his responses */
+ {
+ mark2 = playMark;
+ if (i <= lList1.indx) /* try his move */
+ {
+ tryPlay(lList1.p[i].px, lList1.p[i].py, him); /* play his response */
+ pause();
+ if (gList[gMap[groupIDs[lList1.p[i].px]
+ [lList1.p[i].py]]].libC < 2)
+ goto two; /* a bogus move */
+ }
+ else if (gList[gMap[groupIDs[gx][gy]]].libC <= 1)
+ {
+ result = TRUE;
+ goto one;
+ }
+ if (gList[gMap[groupIDs[gx][gy]]].libC > treeLibLim)
+ {
+ *escape = TRUE;
+ result = FALSE;
+ goto one;
+ }
+ if (gList[gMap[groupIDs[gx][gy]]].libC > 1)
+ { /* look at my responses */
+ sSpanGroup(gx, gy, &lList2); /* list his liberties */
+ dStart = lList2.indx + 1;
+ if (adjInAtari) /* he wins */
+ {
+ result = FALSE;
+ goto one;
+ }
+ if ((lList2.indx > 2) && adj2Libs) /* he wins */
+ {
+ result = FALSE;
+ goto one;
+ }
+ for (k = 1; k <= maxSPoint; k++)
+ libList[k] = -1;
+ if (utilPlayLevel > 4) /* account for diagonal moves */
+ {
+ listDiags(gx, gy, &dList);
+ j = 0;
+ k = lList2.indx;
+ while ((j < dList.indx) &&
+ (k < maxSPoint))
+ {
+ j = j + 1;
+ k = k + 1;
+ libList[k] = 100;
+ lList2.p[k].px = dList.p[j].px;
+ lList2.p[k].py = dList.p[j].py;
+ }
+ lList2.indx = k;
+ }
+ if (lList2.indx > 1) /* sort by increasing lib count */
+ {
+ for (k = 1; k <= lList2.indx; k++)
+ if (libList[k] != 100) /* diags go last */
+ {
+ mark3 = playMark;
+ tryPlay(lList2.p[k].px, lList2.p[k].py, me);
+ libList[k] = gList[gMap[groupIDs[gx][gy]]].libC;
+ undoTo(mark3);
+ }
+ for (k = 1; k <= lList2.indx - 1; k++)
+ for (j = k + 1; j <= lList2.indx; j++)
+ if (libList[k] > libList[j])
+ {
+ tl = libList[k];
+ libList[k] = libList[j];
+ libList[j] = tl;
+ tp = lList2.p[k];
+ lList2.p[k] = lList2.p[j];
+ lList2.p[j] = tp;
+ }
+ else if ((libList[k] == libList[j]) &&
+ (libList[k] == 1))
+ if (mtNbrs(lList2.p[k].px, lList2.p[k].py) <
+ mtNbrs(lList2.p[j].px, lList2.p[j].py))
+ {
+ tl = libList[k];
+ libList[k] = libList[j];
+ libList[j] = tl;
+ tp = lList2.p[k];
+ lList2.p[k] = lList2.p[j];
+ lList2.p[j] = tp;
+ }
+ }
+ for (j = 1; j <= lList2.indx; j++)
+ {
+ if (killTree(lList2.p[j].px, lList2.p[j].py, gx,
+ gy, &esc, tkMark))
+ goto two; /* this kills him */
+ if (esc && (j >= dStart))
+ {
+ result = FALSE;
+ goto one; /* don't bother with more diags if escapes */
+ }
+ }
+ result = FALSE; /* none of my responses kills him */
+ goto one;
+ }
+ two:
+ undoTo(mark2);
+ }
+ result = TRUE; /* none of his responses saves him */
+ }
+ one:
+ undoTo(curMark);
+/* sClearChar(sChar, rXor); */
+ depth = depth - 1;
+ return result;
+ } /* killTree */
+
+short tKillTree(tx, ty, gx, gy)
+short tx, ty, gx, gy;
+ { /* tKillTree */
+ short tkMark, escape;
+ tryCount = 0;
+ tkMark = playMark;
+ return killTree(tx, ty, gx, gy, &escape, tkMark);
+ } /* tKillTree */
+
+short killable(gx, gy, killx, killy)
+short gx, gy, *killx, *killy;
+{ /* killable */
+#ifdef DEBUG
+ printf( "killable\n" );
+ showTrees = TRUE;
+#endif
+ dbStop = TRUE;
+ him = bord[gx][gy]; /* find out who I am */
+ me = -him;
+/* if (me == 1)
+ sChar = '>';
+ else
+ sChar = '|'; */
+/* write(sChar); */
+ depth = 1;
+ topMark = playMark;
+ sSpanGroup(gx, gy, &lList); /* find his liberties */
+ if (lList.indx == 1)
+ {
+ *killx = lList.p[1].px;
+ *killy = lList.p[1].py;
+ return TRUE;
+ }
+ else if (lList.indx > treeLibLim)
+ return FALSE;
+ else if (adjInAtari)
+ return FALSE;
+ else if ((lList.indx > 2) && adj2Libs)
+ return FALSE;
+ else
+ {
+ for (i = 1; i <= maxSPoint; i++)
+ libList[i] = -1;
+ if (utilPlayLevel > 4) /* account for diagonal moves */
+ {
+ listDiags(gx, gy, &dList);
+ j = 0;
+ i = lList.indx;
+ while ((j < dList.indx) &&
+ (i < maxSPoint))
+ {
+ j = j + 1;
+ i = i + 1;
+ libList[i] = 100;
+ lList.p[i].px = dList.p[j].px;
+ lList.p[i].py = dList.p[j].py;
+ }
+ lList.indx = i;
+ }
+ if (lList.indx > 1) /* sort by increasing lib count */
+ {
+ for (i = 1; i <= lList.indx; i++)
+ if (libList[i] != 100) /* diags go last */
+ {
+ mark2 = playMark;
+ tryPlay(lList.p[i].px, lList.p[i].py, me);
+ libList[i] = gList[gMap[groupIDs[gx][gy]]].libC;
+ undoTo(mark2);
+ }
+ for (i = 1; i <= lList.indx - 1; i++)
+ for (j = i + 1; j <= lList.indx; j++)
+ if (libList[i] > libList[j])
+ {
+ tl = libList[i];
+ libList[i] = libList[j];
+ libList[j] = tl;
+ tp = lList.p[i];
+ lList.p[i] = lList.p[j];
+ lList.p[j] = tp;
+ }
+ else if ((libList[i] == libList[j]) &&
+ (libList[i] == 1))
+ if (mtNbrs(lList.p[i].px, lList.p[i].py) <
+ mtNbrs(lList.p[j].px, lList.p[j].py))
+ {
+ tl = libList[i];
+ libList[i] = libList[j];
+ libList[j] = tl;
+ tp = lList.p[i];
+ lList.p[i] = lList.p[j];
+ lList.p[j] = tp;
+ }
+ }
+ for (i = 1; i <= lList.indx; i++)
+ {
+ if (legal[lList.p[i].px][lList.p[i].py])
+ {
+ *killx = lList.p[i].px;
+ *killy = lList.p[i].py;
+ if (tKillTree(*killx, *killy, gx, gy))
+ {
+/* sClearChar(sChar, rXor); */
+ return TRUE;
+ }
+ }
+ }
+ return FALSE;
+ }
+/* sClearChar(sChar, rXor); */
+} /* killable */
+