Diffstat (limited to 'noncore/games/go/goplayutils.c') (more/less context) (ignore whitespace changes)
| -rw-r--r-- | noncore/games/go/goplayutils.c | 1317 |
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 @@ +/* The go player utilities */ +/* Ported from Pascal to C by Todd R. Johnson */ +/* From the original Pascal file: +Copyright (c) 1983 by Three Rivers Computer Corp. + +Written: January 17, 1983 by Stoney Ballard +*/ + +#include "goplayutils.h" +#include "amigo.h" +#include "go.h" + +extern struct bRec goboard[19][19]; + +intBoard claim, extra, bord, ndbord, sGroups, threatBord, + groupIDs, connectMap, protPoints; +boolBoard groupSeen, legal; +short maxGroupID; +pointList pList, pList1, plist2, plist3, pPlist; +intList nlcGroup, aList; +sgRec sList[401]; +groupRec gList[maxGroup]; +short killFlag, + numCapt, + utilPlayLevel, + treeLibLim; +sType mySType; +short showTrees; +short sGlist[maxGroup+1]; +short depthLimit; +intBoard markBoard; +short marker; + +short adjInAtari, adj2Libs, + intersectNum, spanNum, libMark; +playRec playStack[1025]; +short playMark, + newGID, + tryLevel, + grpMark, + gMap[maxGroup]; +short dbStop, inGenState; + + pause() +{ /* pause */ +/* if (dbStop and ! inGenState) + { + while ! tabswitch do; + repeat + if (tabYellow) + dbStop = false; + until ! tabswitch; + } */ +} /* pause */ + +sstone(w, x, y, numb) +short w, x, y, numb; +{ /* sstone */ + if (w == 1) + placestone(mySType, x, y); + else if (mySType == WHITE) + placestone(BLACK, x, y); + else + placestone(WHITE, x, y); +} /* sstone */ + +rstone(x, y) +short x, y; +{ /* rstone */ + removestone(x, y); +} /* rstone */ + +initBoolBoard(bb) +boolBoard bb; +{ /* initBoolBoard */ + short i, j; +#ifdef DEBUG + printf( "initBoolBoard\n" ); +#endif + for (i = 0; i <= maxPoint; i++) + for (j = 0; j <= maxPoint; j++) + bb[i][j] = FALSE; +} /* initBoolBoard */ + +sortLibs() +{ /* sortLibs */ + short i, j, t; +#ifdef DEBUG + printf( "sortLibs\n" ); +#endif + for (i = 1; i <= maxGroupID; i++) + sGlist[i] = i; + for (i = 1; i < maxGroupID; i++) + for (j = i + 1; j <= maxGroupID; j++) + if (gList[sGlist[i]].libC > gList[sGlist[j]].libC) + { + t = sGlist[i]; + sGlist[i] = sGlist[j]; + sGlist[j] = t; + } +} /* sortLibs */ + +spanGroupspan(x, y, libs, lookFor) +short x, y, lookFor; +pointList *libs; + { /* span */ + markBoard[x][y] = marker; + if (bord[x][y] == 0) + { + libs->indx = libs->indx + 1; + libs->p[libs->indx].px = x; + libs->p[libs->indx].py = y; + } + else if (bord[x][y] == lookFor) + { + groupSeen[x][y] = TRUE; + if ((x > 0) && (markBoard[x - 1][y] != marker)) + spanGroupspan(x - 1, y, libs, lookFor); + if ((y > 0) && (markBoard[x][y - 1] != marker)) + spanGroupspan(x, y - 1, libs, lookFor); + if ((x < maxPoint) && (markBoard[x + 1][y] != marker)) + spanGroupspan(x + 1, y, libs, lookFor); + if ((y < maxPoint) && (markBoard[x][y + 1] != marker)) + spanGroupspan(x, y + 1, libs, lookFor); + } + else if (gList[gMap[groupIDs[x][y]]].libC == 1) + adjInAtari = TRUE; + else if ((gList[gMap[groupIDs[x][y]]].libC == 2) && + (! gList[gMap[groupIDs[x][y]]].isLive)) + adj2Libs = TRUE; + } /* span */ + +spanGroup(x, y, libs) +short x, y; +pointList *libs; +{ /* spanGroup */ + short lookFor; +#ifdef DEBUG + printf( "spanGroup\n" ); +#endif + marker = marker + 1; + if (marker == 0) + { + initArray(markBoard); + marker = 1; + } + adjInAtari = FALSE; + adj2Libs = FALSE; + lookFor = bord[x][y]; + libs->indx = 0; + spanGroupspan(x, y, libs, lookFor); +} /* spanGroup */ + +sSpanGroupspan(x, y, libs, lookFor) +short x, y, lookFor; +sPointList *libs; + { /* span */ + markBoard[x][y] = marker; + if (bord[x][y] == 0) + { + libs->indx += 1; + if (libs->indx <= maxSPoint) + { + libs->p[libs->indx].px = x; + libs->p[libs->indx].py = y; + } + } + else if (bord[x][y] == lookFor) + { + groupSeen[x][y] = TRUE; + if ((x > 0) && (markBoard[x - 1][y] != marker)) + sSpanGroupspan(x - 1, y, libs, lookFor); + if ((y > 0) && (markBoard[x][y - 1] != marker)) + sSpanGroupspan(x, y - 1, libs, lookFor); + if ((x < maxPoint) && (markBoard[x + 1][y] != marker)) + sSpanGroupspan(x + 1, y, libs, lookFor); + if ((y < maxPoint) && (markBoard[x][y + 1] != marker)) + sSpanGroupspan(x, y + 1, libs, lookFor); + } + else if (gList[gMap[groupIDs[x][y]]].libC == 1) + adjInAtari = TRUE; + else if ((gList[gMap[groupIDs[x][y]]].libC == 2) && + (! gList[gMap[groupIDs[x][y]]].isLive)) + adj2Libs = TRUE; + } /* span */ + +sSpanGroup(x, y, libs) +short x, y; +sPointList *libs; +{ /* sSpanGroup */ + short lookFor; +#ifdef DEBUG + printf( "sSpanGroup\n" ); +#endif + marker = marker + 1; + if (marker == 0) + { + initArray(markBoard); + marker = 1; + } + adjInAtari = FALSE; + adj2Libs = FALSE; + lookFor = bord[x][y]; + libs->indx = 0; + sSpanGroupspan(x, y, libs, lookFor); +} /* sSpanGroup */ + +LAspan(x, y, me, him, iL) +short x, y, me, him; +intList *iL; + { /* span */ +#ifdef DEBUG + printf( "LAspan\n" ); +#endif + markBoard[x][y] = marker; + if (bord[x][y] == me) + { + if ((x > 0) && (markBoard[x - 1][y] != marker)) + LAspan(x - 1, y, me, him, iL); + if ((x < maxPoint) && (markBoard[x + 1][y] != marker)) + LAspan(x + 1, y, me, him, iL); + if ((y > 0) && (markBoard[x][y - 1] != marker)) + LAspan(x, y - 1, me, him, iL); + if ((y < maxPoint) && (markBoard[x][y + 1] != marker)) + LAspan(x, y + 1, me, him, iL); + } + else if (bord[x][y] == him) + if (gList[gMap[groupIDs[x][y]]].groupMark != grpMark) + { + gList[gMap[groupIDs[x][y]]].groupMark = grpMark; + iL->indx = iL->indx + 1; + iL->v[iL->indx] = gMap[groupIDs[x][y]]; + } + } /* span */ + +listAdjacents(x, y, iL) +short x, y; +intList *iL; +{ /* listAdjacents */ + short me, him; +#ifdef DEBUG + printf( "listAdjacents\n" ); +#endif + grpMark = grpMark + 1; + marker = marker + 1; + if (marker == 0) + { + initArray(markBoard); + marker = 1; + } + iL->indx = 0; + me = bord[x][y]; + him = -me; + LAspan(x, y, me , him, iL); +} /* listAdjacents */ + +LDspan(x, y, me, diags) +short x, y, me; +sPointList *diags; + { /* span */ +#ifdef DEBUG + printf( "LDspan\n" ); +#endif + markBoard[x][y] = marker; + if ((x > 0) && (y > 0) && + (bord[x - 1][y - 1] == 0) && + (bord[x][y - 1] != me) && + (bord[x - 1][y] != me) && + (markBoard[x - 1][y - 1] != marker)) + { + markBoard[x - 1][y - 1] = marker; + diags->indx = diags->indx + 1; + if (diags->indx <= maxSPoint) + { + diags->p[diags->indx].px = x - 1; + diags->p[diags->indx].py = y - 1; + } + } + if ((x < maxPoint) && (y > 0) && + (bord[x + 1][y - 1] == 0) && + (bord[x][y - 1] != me) && + (bord[x + 1][y] != me) && + (markBoard[x + 1][y - 1] != marker)) + { + markBoard[x + 1][y - 1] = marker; + diags->indx = diags->indx + 1; + if (diags->indx <= maxSPoint) + { + diags->p[diags->indx].px = x + 1; + diags->p[diags->indx].py = y - 1; + } + } + if ((x > 0) && (y < maxPoint) && + (bord[x - 1][y + 1] == 0) && + (bord[x][y + 1] != me) && + (bord[x - 1][y] != me) && + (markBoard[x - 1][y + 1] != marker)) + { + markBoard[x - 1][y + 1] = marker; + diags->indx = diags->indx + 1; + if (diags->indx <= maxSPoint) + { + diags->p[diags->indx].px = x - 1; + diags->p[diags->indx].py = y + 1; + } + } + if ((x < maxPoint) && (y < maxPoint) && + (bord[x + 1][y + 1] == 0) && + (bord[x][y + 1] != me) && + (bord[x + 1][y] != me) && + (markBoard[x + 1][y + 1] != marker)) + { + markBoard[x + 1][y + 1] = marker; + diags->indx = diags->indx + 1; + if (diags->indx <= maxSPoint) + { + diags->p[diags->indx].px = x + 1; + diags->p[diags->indx].py = y + 1; + } + } + if ((x > 0) && (bord[x - 1][y] == me) && + (markBoard[x - 1][y] != marker)) + LDspan(x - 1, y, me, diags); + if ((x < maxPoint) && (bord[x + 1][y] == me) && + (markBoard[x + 1][y] != marker)) + LDspan(x + 1, y, me, diags); + if ((y > 0) && (bord[x][y - 1] == me) && + (markBoard[x][y - 1] != marker)) + LDspan(x, y - 1, me, diags); + if ((y < maxPoint) && (bord[x][y + 1] == me) && + (markBoard[x][y + 1] != marker)) + LDspan(x, y + 1, me , diags); +} /* span */ + +listDiags(x, y, diags) +short x, y; +sPointList *diags; +{ /* listDiags */ + short me; +#ifdef DEBUG + printf( "listDiags\n" ); +#endif + me = bord[x][y]; + diags->indx = 0; + marker = marker + 1; + if (marker == 0) + { + initArray(markBoard); + marker = 1; + } + LDspan(x, y, me, diags); +} /* listDiags */ + +intersectPlist(p1, p2, pr) +pointList *p1, *p2, *pr; +{ /* intersectPlist */ + short i, j, k; +#ifdef DEBUG + printf( "intersectPlist\n" ); +#endif + marker = marker + 1; + if (marker == 0) + { + initArray(markBoard); + marker = 1; + } + pr->indx = 0; + for (i = 1; i <= p1->indx; i++) + markBoard[p1->p[i].px][p1->p[i].py] = marker; + j = 0; + for (i = 1; i <= p2->indx; i++) + if (markBoard[p2->p[i].px][p2->p[i].py] == marker) + { + j = j + 1; + pr->p[j] = p2->p[i]; + } + pr->indx = j; +} /* intersectPlist */ + +initArray(ary) +intBoard ary; +{ /* initArray */ + short i, j; + for (i = 0; i <= maxPoint; i++) + for (j = 0; j <= maxPoint; j++) + ary[i][j] = 0; +} /* initArray */ + +initState() +{ /* initState */ + short i, j; + for (i = 0; i <= maxPoint; i++) + for (j = 0; j <= maxPoint; j++) + { + extra[i][j] = 0; + claim[i][j] = 0; + groupIDs[i][j] = 0; + connectMap[i][j] = 0; + protPoints[i][j] = 0; + } +} /* initState */ + +copyArray( dest, src ) +intBoard dest, src; +{ + short x, y; + for (y = 0; y <= maxPoint; y++) + for (x = 0; x <= maxPoint; x++) + dest[x][y] = src[x][y]; +} + +/* + generates a one-point spread in the force field array (claim) + + the spread from a single point after four calls is: + + 1 + 2 2 2 + 2 4 6 4 2 + 2 4 8 10 8 4 2 + 1 2 6 10 62 10 6 2 1 + 2 4 8 10 8 4 2 + 2 4 6 4 2 + 2 2 2 + 1 + +*/ +stake() +{ + short x, y; + initArray( extra ); + for (y = 0; y <= maxPoint; y++) + for (x = 0; x <= maxPoint; x++) + { + extra[x][y] = extra[x][y] + claim[x][y]; + if (claim[x][y] > 0) + { + if (x > 0) extra[x-1][y] += 1; + if (y > 0) extra[x][y-1] += 1; + if (x < maxPoint) extra[x+1][y] += 1; + if (y < maxPoint) extra[x][y+1] += 1; + } + else if (claim[x][y] < 0) + { + if (x > 0) extra[x-1][y] -= 1; + if (y > 0) extra[x][y-1] -= 1; + if (x < maxPoint) extra[x+1][y] -= 1; + if (y < maxPoint) extra[x][y+1] -= 1; + } + } + copyArray( claim, extra ); +} /* stake */ + +/* + sets up claim from the current board position +*/ +spread() +{ + short x, y; + for (y = 0; y <= maxPoint; y++) + for (x = 0; x <= maxPoint; x++) + claim[x][y] = ndbord[x][y] * 50; + stake(); + stake(); + stake(); + stake(); +} /* spread */ + +/* + gList is initialized with the size, loc, and libCount of each group + groupIDs contains the serial numbers of the groups. +*/ +Resspan(x, y, gID, gSize, libCount, who) +short x, y, gID, *gSize, *libCount, who; + { /* span */ + if ((bord[x][y] == 0) && + (markBoard[x][y] != marker)) /* a liberty */ + { + markBoard[x][y] = marker; + *libCount = *libCount + 1; + } + else if ((bord[x][y] == who) && + (groupIDs[x][y] == 0)) + { + groupIDs[x][y] = gID; + *gSize = *gSize + 1; + if (x > 0) + Resspan(x - 1, y, gID, gSize, libCount, who); + if (x < maxPoint) + Resspan(x + 1, y, gID, gSize, libCount, who); + if (y > 0) + Resspan(x, y - 1, gID, gSize, libCount, who); + if (y < maxPoint) + Resspan(x, y + 1, gID, gSize, libCount, who); + } + } /* span */ + +respreicen() +{ /* respreicen */ + short i, j, gID, libCount, gSize, who; + gID = 0; +#ifdef DEBUG + printf( "respreicen\n" ); +#endif + for (i = 0; i <= maxPoint; i++) + for (j = 0; j <= maxPoint; j++) + groupIDs[i][j] = 0; + for (i = 0; i <= maxPoint; i++) + for (j = 0; j <= maxPoint; j++) + if ((bord[i][j] != 0) && /* a stone there */ + (groupIDs[i][j] == 0)) /* not seen yet */ + { + marker = marker + 1; + if (marker == 0) + { + initArray(markBoard); + marker = 1; + } + gID = gID + 1; + libCount = 0; + gSize = 0; + who = bord[i][j]; + Resspan(i, j, gID, &gSize, &libCount, who); /* span the group, collecting info */ + gList[gID].groupMark = 0; + gList[gID].atLevel = 0; + gList[gID].isLive = FALSE; /* we don't know yet */ + gList[gID].isDead = FALSE; + gList[gID].numEyes = -1; + gList[gID].size = gSize; + gList[gID].libC = libCount; + gList[gID].lx = i; + gList[gID].ly = j; + gMap[gID] = gID; /* set up identity map */ + } + maxGroupID = gID; + newGID = gID; + grpMark = 0; +} /* respreicen */ + +/* + play z at [x, y]. + killFlag is set true if anything is killed. +*/ +killGroup(x, y, me, him) +short x, y, me, him; + { /* killGroup */ +#ifdef DEBUG + printf( "killGroup\n" ); +#endif + playMark = playMark + 1; + /* record this kill */ + playStack[playMark].kind = rem; + playStack[playMark].uval.rem.who = him; + playStack[playMark].uval.rem.xl = x; + playStack[playMark].uval.rem.yl = y; + playStack[playMark].gID = groupIDs[x][y]; + playStack[playMark].uval.rem.sNumber = goboard[x][y].mNum; + if (showTrees) + rstone(x, y); + numCapt = numCapt + 1; + bord[x][y] = 0; + groupIDs[x][y] = 0; + if (x > 0) + { + if (bord[x - 1][y] == me) + { + nlcGroup.indx = nlcGroup.indx + 1; + nlcGroup.v[nlcGroup.indx] = gMap[groupIDs[x - 1][y]]; + } + else if (bord[x - 1][y] == him) + killGroup(x - 1, y, me , him); + } + if (x < maxPoint) + { + if (bord[x + 1][y] == me) + { + nlcGroup.indx = nlcGroup.indx + 1; + nlcGroup.v[nlcGroup.indx] = gMap[groupIDs[x + 1][y]]; + } + else if (bord[x + 1][y] == him) + killGroup(x + 1, y, me, him); + } + if (y > 0) + { + if (bord[x][y - 1] == me) + { + nlcGroup.indx = nlcGroup.indx + 1; + nlcGroup.v[nlcGroup.indx] = gMap[groupIDs[x][y - 1]]; + } + else if (bord[x][y - 1] == him) + killGroup(x, y - 1, me, him); + } + if (y < maxPoint) + { + if (bord[x][y + 1] == me) + { + nlcGroup.indx = nlcGroup.indx + 1; + nlcGroup.v[nlcGroup.indx] = gMap[groupIDs[x][y + 1]]; + } + else if (bord[x][y + 1] == him) + killGroup(x, y + 1, me, him); + } + } /* killGroup */ + +mergeGroup(sGID, myGID) +short sGID, myGID; + { /* mergeGroup */ + short i; +#ifdef DEBUG + printf( "mergeGroup\n" ); +#endif + for (i = 1; i <= newGID; i++) + if (gMap[i] == sGID) + { + playMark = playMark + 1; + playStack[playMark].kind = reMap; + playStack[playMark].gID = i; + playStack[playMark].uval.reMap.oldGID = sGID; + gMap[i] = myGID; + } + } /* mergeGroup */ + +tryPlay(x, y, z) +short x, y, z; +{ /* plei */ + short i, me, him, myGID; + short isNew; +#ifdef DEBUG + printf( "tryPlay\n" ); +#endif + me = z; + him = -me; + killFlag = FALSE; /* set true if something is killed */ + numCapt = 0; + tryLevel = tryLevel + 1; + isNew = FALSE; + bord[x][y] = z; /* play the stone */ + if ((x > 0) && (bord[x - 1][y] == me)) /* connect to adjacent group */ + myGID = gMap[groupIDs[x - 1][y]]; + else if ((x < maxPoint) && (bord[x + 1][y] == me)) + myGID = gMap[groupIDs[x + 1][y]]; + else if ((y > 0) && (bord[x][y - 1] == me)) + myGID = gMap[groupIDs[x][y - 1]]; + else if ((y < maxPoint) && (bord[x][y + 1] == me)) + myGID = gMap[groupIDs[x][y + 1]]; + else /* nobody to connect to */ + { + newGID = newGID + 1; + isNew = TRUE; + myGID = newGID; + gList[myGID].groupMark = 0; + gList[myGID].atLevel = tryLevel; + gList[myGID].isLive = FALSE; + gList[myGID].numEyes = -1; + gList[myGID].size = -1; + gList[myGID].lx = x; + gList[myGID].ly = y; + gMap[myGID] = myGID; + } + groupIDs[x][y] = myGID; + playMark = playMark + 1; + /* record this move */ + playStack[playMark].kind = add; + playStack[playMark].uval.add.who = me; + playStack[playMark].uval.add.xl = x; + playStack[playMark].uval.add.yl = y; + playStack[playMark].gID = myGID; + playStack[playMark].uval.add.sNumber = 0; + if (isNew) + playStack[playMark].uval.add.nextGID = newGID - 1; + else + playStack[playMark].uval.add.nextGID = newGID; + if (showTrees) + sstone(me, x, y, 0); + /* merge adjacent groups */ + if ((x > 0) && (bord[x - 1][y] == me) && + (gMap[groupIDs[x - 1][y]] != myGID)) + mergeGroup(gMap[groupIDs[x - 1][y]], myGID); + if ((x < maxPoint) && (bord[x + 1][y] == me) && + (gMap[groupIDs[x + 1][y]] != myGID)) + mergeGroup(gMap[groupIDs[x + 1][y]], myGID); + if ((y > 0) && (bord[x][y - 1] == me) && + (gMap[groupIDs[x][y - 1]] != myGID)) + mergeGroup(gMap[groupIDs[x][y - 1]], myGID); + if ((y < maxPoint) && (bord[x][y + 1] == me) && + (gMap[groupIDs[x][y + 1]] != myGID)) + mergeGroup(gMap[groupIDs[x][y + 1]], myGID); + /* kill opposing groups, listing affected groups */ + nlcGroup.indx = 1; + nlcGroup.v[1] = myGID; /* init list to include me */ + if ((x > 0) && (bord[x - 1][y] == him) && + (gList[gMap[groupIDs[x - 1][y]]].libC == 1)) + { + killFlag = TRUE; + killGroup(x - 1, y, me, him); + } + if ((x < maxPoint) && (bord[x + 1][y] == him) && + (gList[gMap[groupIDs[x + 1][y]]].libC == 1)) + { + killFlag = TRUE; + killGroup(x + 1, y, me, him); + } + if ((y > 0) && (bord[x][y - 1] == him) && + (gList[gMap[groupIDs[x][y - 1]]].libC == 1)) + { + killFlag = TRUE; + killGroup(x, y - 1, me, him); + } + if ((y < maxPoint) && (bord[x][y + 1] == him) && + (gList[gMap[groupIDs[x][y + 1]]].libC == 1)) + { + killFlag = TRUE; + killGroup(x, y + 1, me, him); + } + /* list groups adjacent to me */ + if ((x > 0) && (bord[x - 1][y] == him)) + { + nlcGroup.indx = nlcGroup.indx + 1; + nlcGroup.v[nlcGroup.indx] = gMap[groupIDs[x - 1][y]]; + } + if ((x < maxPoint) && (bord[x + 1][y] == him)) + { + nlcGroup.indx = nlcGroup.indx + 1; + nlcGroup.v[nlcGroup.indx] = gMap[groupIDs[x + 1][y]]; + } + if ((y > 0) && (bord[x][y - 1] == him)) + { + nlcGroup.indx = nlcGroup.indx + 1; + nlcGroup.v[nlcGroup.indx] = gMap[groupIDs[x][y - 1]]; + } + if ((y < maxPoint) && (bord[x][y + 1] == him)) + { + nlcGroup.indx = nlcGroup.indx + 1; + nlcGroup.v[nlcGroup.indx] = gMap[groupIDs[x][y + 1]]; + } + /* fix liberty count for affected groups */ + grpMark = grpMark + 1; + for (i = 1; i <= nlcGroup.indx; i++) + if (gList[nlcGroup.v[i]].groupMark != grpMark) + { + if (gList[nlcGroup.v[i]].atLevel != tryLevel) + { + playMark = playMark + 1; + playStack[playMark].kind = chLib; + playStack[playMark].gID = nlcGroup.v[i]; + playStack[playMark].uval.chLib.oldLevel = + gList[nlcGroup.v[i]].atLevel; + playStack[playMark].uval.chLib.oldLC = + gList[nlcGroup.v[i]].libC; + } + gList[nlcGroup.v[i]].groupMark = grpMark; + gList[nlcGroup.v[i]].atLevel = tryLevel; + spanGroup(gList[nlcGroup.v[i]].lx, gList[nlcGroup.v[i]].ly, &pPlist); + gList[nlcGroup.v[i]].libC = pPlist.indx; + } +} /* plei */ + +saveState() +{ /* saveState */ + playMark = 0; + tryLevel = 0; + newGID = maxGroupID; +} /* saveState */ + +/* + undoes a move sequence back to uMark +*/ +undoTo(uMark) +short uMark; +{ /* undoTo */ + short i, xl, yl; +#ifdef DEBUG + printf( "undoTo\n" ); +#endif + for (i = playMark; i >= uMark + 1; i--) + if (playStack[i].kind == rem) + { + xl = playStack[i].uval.rem.xl; + yl = playStack[i].uval.rem.yl; + bord[xl][yl] = playStack[i].uval.rem.who; + groupIDs[xl][yl] = playStack[i].gID; + if (showTrees) + sstone(playStack[i].uval.rem.who, xl, yl, + playStack[i].uval.rem.sNumber); + } + else if (playStack[i].kind == add) + { + xl = playStack[i].uval.add.xl; + yl = playStack[i].uval.add.yl; + bord[xl][yl] = 0; + groupIDs[xl][yl] = 0; + tryLevel = tryLevel - 1; + newGID = playStack[i].uval.add.nextGID; + if (showTrees) + rstone(xl, yl); + } + else if (playStack[i].kind == reMap) + gMap[playStack[i].gID] = playStack[i].uval.reMap.oldGID; + else /* change libs of group - gID is pre-mapped */ + { + gList[playStack[i].gID].libC = playStack[i].uval.chLib.oldLC; + gList[playStack[i].gID].atLevel = playStack[i].uval.chLib.oldLevel; + } + playMark = uMark; +} /* undoTo */ + +/* + restores the state of the world after trying a move sequence +*/ +restoreState() +{ /* restoreState */ +#ifdef DEBUG + printf( "restoreState\n" ); +#endif + if (playMark > 0) + { + undoTo(0); + playMark = 0; + tryLevel = 0; + } +} /* restoreState */ + +/* exception bpt; */ + + +/* + returns true if (the group (at gx, gy) is saveable. + if so, returns the point to play at in savex, savey +*/ +short saveable(gx, gy, savex, savey) +short gx, gy, *savex, *savey; +{ /* saveable */ + short me, him, gx1, gx2, i, j, smark, mark2, tl, result; + char sChar; + sPointList dList; + point tp; + short libList[maxSPoint+1]; +#ifdef DEBUG + printf( "saveable\n" ); +#endif + dbStop = TRUE; + me = bord[gx][gy]; + him = -me; + if (me == 1) + sChar = '|'; + else + sChar = '>'; +/* write(sChar); */ + spanGroup(gx, gy, &plist3); /* find my liberties */ + if (adjInAtari) /* one of my options is to kill */ + { + listAdjacents(gx, gy, &aList); + for (i = 1; i <= aList.indx; i++) + if (gList[aList.v[i]].libC == 1) + { + spanGroup(gList[aList.v[i]].lx, gList[aList.v[i]].ly, + &pList1); /* find it's liberty */ + plist3.indx = plist3.indx + 1; + plist3.p[plist3.indx].px = pList1.p[1].px; + plist3.p[plist3.indx].py = pList1.p[1].py; + } + } + for (i = 1; i <= maxSPoint; i++) + libList[i] = -1; + if ((utilPlayLevel > 4) && + (gList[gMap[groupIDs[gx][gy]]].libC > 1)) /* account for diags */ + { + listDiags(gx, gy, &dList); + j = 0; + i = plist3.indx; + while ((j < dList.indx) && + (i < maxSPoint)) + { + j = j + 1; + i = i + 1; + libList[i] = 100; + plist3.p[i].px = dList.p[j].px; + plist3.p[i].py = dList.p[j].py; + } + plist3.indx = i; + } + if (plist3.indx > 1) /* sort by decreasing lib count */ + { + for (i = 1; i <= plist3.indx; i++) + if (libList[i] != 100) + { + mark2 = playMark; + tryPlay(plist3.p[i].px, plist3.p[i].py, me); + libList[i] = gList[gMap[groupIDs[gx][gy]]].libC; + if (libList[i] > treeLibLim) /* i'm safe */ + { + *savex = plist3.p[i].px; + *savey = plist3.p[i].py; + result = TRUE; + goto one; + } + undoTo(mark2); + } + for (i = 1; i <= plist3.indx - 1; i++) + for (j = i + 1; j <= plist3.indx; j++) + if (libList[i] < libList[j]) + { + tl = libList[i]; + libList[i] = libList[j]; + libList[j] = tl; + tp = plist3.p[i]; + plist3.p[i] = plist3.p[j]; + plist3.p[j] = tp; + } + } + for (i = 1; i <= plist3.indx; i++) + { + *savex = plist3.p[i].px; + *savey = plist3.p[i].py; + if (legal[*savex][*savey]) + { + smark = playMark; + tryPlay(*savex, *savey, me); + pause(); + if (gList[gMap[groupIDs[*savex][*savey]]].libC > 1) + if (gList[gMap[groupIDs[gx][gy]]].libC > treeLibLim) + { + restoreState(); +/* sClearChar(sChar, rXor); */ + return TRUE; + } + else if (gList[gMap[groupIDs[gx][gy]]].libC > 1) + if (! killable(gx, gy, &gx1, &gx2)) + { + restoreState(); +/* sClearChar(sChar, rXor); */ + return TRUE; + } + undoTo(smark); + } + } + result = FALSE; +one: + restoreState(); +/* sClearChar(sChar, rXor); */ + return result; +} /* saveable */ + +/* + marks unsavable groups as dead +*/ +markDead() +{ /* markDead */ + short i, j, gx, gy, result; +#ifdef DEBUG + printf( "markDead\n" ); +#endif + for (i = 1; i <= maxGroupID; i++) + if (killable(gList[i].lx, gList[i].ly, &gx, &gy)) + result = ! saveable(gList[i].lx, gList[i].ly, &gx, &gy); + else + result = FALSE; + for (i = 0; i <= maxPoint; i++) + for (j = 0; j <= maxPoint; j++) + if (bord[i][j] == 0) + ndbord[i][j] = 0; + else if (gList[groupIDs[i][j]].isDead) + ndbord[i][j] = 0; + else + ndbord[i][j] = bord[i][j]; +} /* markDead */ + +/* + marks groups with two eyes as live +*/ +MLspan(x, y, saw1, sawm1, size, sMark) +short x, y, *saw1, *sawm1, *size, sMark; + { /* span */ + if (ndbord[x][y] == 1) + *saw1 = TRUE; + else if (ndbord[x][y] == -1) + *sawm1 = TRUE; + else if (sGroups[x][y] == 0) + { + sGroups[x][y] = sMark; + *size = *size + 1; + if (x > 0) + MLspan(x - 1, y, saw1, sawm1, size, sMark); + if (x < maxPoint) + MLspan(x + 1, y, saw1, sawm1, size, sMark); + if (y > 0) + MLspan(x, y - 1, saw1, sawm1, size, sMark); + if (y < maxPoint) + MLspan(x, y + 1, saw1, sawm1, size, sMark); + } + } /* span */ + +short CLspan(x, y, numEyes, who) +short x, y, *numEyes, who; + { /* span */ + markBoard[x][y] = marker; + if (ndbord[x][y] == 0) + { + if ((sList[sGroups[x][y]].sm != marker) && + (sList[sGroups[x][y]].w == who)) + { + sList[sGroups[x][y]].sm = marker; + if (sList[sGroups[x][y]].s > 6) + return TRUE; + *numEyes = *numEyes + 1; + if (*numEyes > 1) + return TRUE; + } + } + else if (bord[x][y] == who) + { + if ((x > 0) && + (markBoard[x - 1][y] != marker)) + if (CLspan(x - 1, y, numEyes, who)) return TRUE; + if ((x < maxPoint) && + (markBoard[x + 1][y] != marker)) + if (CLspan(x + 1, y, numEyes, who)) return TRUE; + if ((y > 0) && + (markBoard[x][y - 1] != marker)) + if (CLspan(x, y - 1, numEyes, who)) return TRUE; + if ((y < maxPoint) && + (markBoard[x][y + 1] != marker)) + if (CLspan(x, y + 1, numEyes, who)) return TRUE; + } + return FALSE; + } /* span */ + +short checkLive(x, y) +short x, y; + { /* checkLive */ + short numEyes, who; +#ifdef DEBUG + printf( "checkLive\n" ); +#endif + numEyes = 0; + who = bord[x][y]; + marker = marker + 1; + return CLspan(x, y, &numEyes, who); + } /* checkLive */ + +markLive() +{ /* markLive */ + short i, j, size, sMark = 0; + short saw1, sawm1; +#ifdef DEBUG + printf( "markLive\n" ); +#endif + initArray(sGroups); + for (i = 0; i <= maxPoint; i++) + for (j = 0; j <= maxPoint; j++) + if ((sGroups[i][j] == 0) && + (ndbord[i][j] == 0)) + { + size = 0; + sMark = sMark + 1; + sawm1 = FALSE; + saw1 = FALSE; + MLspan(i, j, &saw1, &sawm1, &size, sMark); + sList[sMark].s = size; + sList[sMark].sm = 0; + if (sawm1) + if (saw1) + sList[sMark].w = 0; + else + sList[sMark].w = -1; + else if (saw1) + sList[sMark].w = 1; + else + sList[sMark].w = 0; + } + for (i = 1; i <= maxGroupID; i++) + if (! gList[i].isDead) + gList[i].isLive = checkLive(gList[i].lx, gList[i].ly); +} /* markLive */ + +/* + generates the connection map and the protected point map. +*/ +genConnects() +{ /* genConnects */ + short x, y, numStones; +#ifdef DEBUG + printf( "genConnects\n" ); +#endif + for (x = 0; x <= maxPoint; x++) + for (y = 0; y <= maxPoint; y++) + { + connectMap[x][y] = 0; + protPoints[x][y] = 0; + } + for (x = 0; x <= maxPoint; x++) + for (y = 0; y <= maxPoint; y++) + if (bord[x][y] == 1) /* map connections to this stone */ + { + if (x > 0) /* direct connection */ + connectMap[x - 1][y] += 1; + if (x < maxPoint) + connectMap[x + 1][y] += 1; + if (y > 0) + connectMap[x][y - 1] += 1; + if (y < maxPoint) + connectMap[x][y + 1] += 1; + if ((x > 0) && (y > 0) && /* diagonal connection */ + (bord[x - 1][y] == 0) && (bord[x][y - 1] == 0)) + connectMap[x - 1][y - 1] += 1; + if ((x < maxPoint) && (y > 0) && + (bord[x + 1][y] == 0) && (bord[x][y - 1] == 0)) + connectMap[x + 1][y - 1] += 1; + if ((x < maxPoint) && (y < maxPoint) && + (bord[x + 1][y] == 0) && (bord[x][y + 1] == 0)) + connectMap[x + 1][y + 1] += 1; + if ((x > 0) && (y < maxPoint) && + (bord[x - 1][y] == 0) && (bord[x][y + 1] == 0)) + connectMap[x - 1][y + 1] += 1; + if ((x > 1) && (claim[x - 1][y] > 3)) /* one point jump */ + connectMap[x - 2][y] += 1; + if ((x < (maxPoint - 1)) && (claim[x + 1][y] > 3)) + connectMap[x + 2][y] += 1; + if ((y > 1) && (claim[x][y - 1] > 3)) + connectMap[x][y - 2] += 1; + if ((y < (maxPoint - 1)) && (claim[x][y + 1] > 3)) + connectMap[x][y + 2] += 1; + if ((x > 1) && (y > 0) && /* knight's move */ + (claim[x - 1][y] > 3) && (claim[x - 1][y - 1] > 3)) + connectMap[x - 2][y - 1] += 1; + if ((x > 0) && (y > 1) && + (claim[x][y - 1] > 3) && (claim[x - 1][y - 1] > 3)) + connectMap[x - 1][y - 2] += 1; + if ((x < (maxPoint - 1)) && (y > 0) && + (claim[x + 1][y] > 3) && (claim[x + 1][y - 1] > 3)) + connectMap[x + 2][y - 1] += 1; + if ((x < maxPoint) && (y > 1) && + (claim[x][y - 1] > 3) && (claim[x + 1][y - 1] > 3)) + connectMap[x + 1][y - 2] += 1; + if ((x > 1) && (y < maxPoint) && + (claim[x - 1][y] > 3) && (claim[x - 1][y + 1] > 3)) + connectMap[x - 2][y + 1] += 1; + if ((x > 0) && (y < (maxPoint - 1)) && + (claim[x][y + 1] > 3) && (claim[x - 1][y + 1] > 3)) + connectMap[x - 1][y + 2] += 1; + if ((x < (maxPoint - 1)) && (y < maxPoint) && + (claim[x + 1][y] > 3) && (claim[x + 1][y + 1] > 3)) + connectMap[x + 2][y + 1] += 1; + if ((x < maxPoint) && (y < (maxPoint - 1)) && + (claim[x][y + 1] > 3) && (claim[x + 1][y + 1] > 3)) + connectMap[x + 1][y + 2] += 1; + } + else if (bord[x][y] == 0) /* see if protected point */ + { + numStones = 0; + if (x == 0) + numStones = numStones + 1; + if (y == 0) + numStones = numStones + 1; + if (x == maxPoint) + numStones = numStones + 1; + if (y == maxPoint) + numStones = numStones + 1; + if ((x > 0) && (bord[x - 1][y] == 1)) + numStones = numStones + 1; + if ((y > 0) && (bord[x][y - 1] == 1)) + numStones = numStones + 1; + if ((x < maxPoint) && (bord[x + 1][y] == 1)) + numStones = numStones + 1; + if ((y < maxPoint) && (bord[x][y + 1] == 1)) + numStones = numStones + 1; + if (numStones == 4) + protPoints[x][y] = 1; + else if (numStones == 3) + { + if ((x > 0) && + ((bord[x - 1][y] == 0) || + ((bord[x - 1][y] == -1) && + (gList[groupIDs[x - 1][y]].libC == 1)))) + protPoints[x][y] = 1; + else if ((x < maxPoint) && + ((bord[x + 1][y] == 0) || + ((bord[x + 1][y] == -1) && + (gList[groupIDs[x + 1][y]].libC == 1)))) + protPoints[x][y] = 1; + else if ((y > 0) && + ((bord[x][y - 1] == 0) || + ((bord[x][y - 1] == -1) && + (gList[groupIDs[x][y - 1]].libC == 1)))) + protPoints[x][y] = 1; + else if ((y < maxPoint) && + ((bord[x][y + 1] == 0) || + ((bord[x][y + 1] == -1) && + (gList[groupIDs[x][y + 1]].libC == 1)))) + protPoints[x][y] = 1; + } + } + for (x = 0; x <= maxPoint; x++) + for (y = 0; y <= maxPoint; y++) + if (bord[x][y] != 0) + { + connectMap[x][y] = 0; + protPoints[x][y] = 0; + } +} /* genConnects */ + +/* + generates the whole state of the game. +*/ +genState() +{ /* genState */ +#ifdef DEBUG + printf( "genState\n" ); +#endif + inGenState = TRUE; + respreicen(); + markDead(); + markLive(); + spread(); + genConnects(); +#ifdef DEBUG +/* printBoard( claim, "claim" ); */ +/* printBoard( bord, "bord" ); */ +/* printBoard( ndbord, "ndbord" ); + printBoard( sGroups, "sGroups" ); + printBoard( groupIDs, "groupIDs" ); + printBoard( connectMap, "connectMap" ); + printBoard( protPoints, "protPoints" ); */ +#endif + inGenState = FALSE; +} /* genState */ + +/* + generates a value for the [x, y] location that appears to get larger + for points that are saddle points in the influence graph (klein) +*/ +short tencen(x, y) +short x, y; +{ /* tencen */ + short a, b, c, d, w, z; +#ifdef DEBUG + printf( "tencen\n" ); +#endif + if (claim[x][y] > -1) /* if (he does not influence this area, return 50 */ + { + return 50; + } + w = claim[x][y]; /* w <= -1 */ + a = iNil; + if (x > 0) + if (claim[x - 1][y] > -1) /* if (neighbor is not influenced by him */ + a = claim[x - 1][y] - w; /* score is sum of his influence on central */ + b = iNil; /* point and my influence on this neighbor */ + if (y > 0) + if (claim[x][y - 1] > -1) + b = claim[x][y - 1] - w; + c = iNil; + if (x < maxPoint) + if (claim[x + 1][y] > -1) + c = claim[x + 1][y] - w; + d = iNil; + if (y < maxPoint) + if (claim[x][y + 1] > -1) + d = claim[x][y + 1] - w; + z = a; /* z = max(a, b, c, d) */ + if (z != iNil) + { + if ((b != iNil) && + (b > z)) + z = b; + } + else + z = b; + if (z != iNil) + { + if ((c != iNil) && + (c > z)) + z = c; + } + else + z = c; + if (z != iNil) + { + if ((d != iNil) && + (d > z)) + z = d; + } + else + z = d; + if ((z != iNil) && + ((x == 0) || + (y == 0) || + (x == maxPoint) || + (y == maxPoint))) + z = z * 2; /* double z if (on the edge of the board ?? */ + if (z != iNil) + return z; + else + return 50; +} /* tencen */ + +initGPUtils() +{ /* initGPUtils */ +#ifdef DEBUG + printf( "initGPUtils\n" ); +#endif + initArray(markBoard); + initState(); + marker = 0; + playMark = 0; + gList[0].isLive = FALSE; + gList[0].isDead = FALSE; + gList[0].libC = 0; + gList[0].size = 0; + gList[0].numEyes = 0; + gList[0].lx = -1; + gList[0].ly = -1; + gMap[0] = 0; + dbStop = FALSE; + inGenState = FALSE; +} /* initGPUtils */ + |