Dots-and-Boxes Game

> $iShifts[$iGroup]) & $nGroupMask;
            } else {
                $nGroupPat = ($nPat1 >> $iShifts[$iGroup]) & $nGroupMask;
            }
            $nGroupsPat[$iGroup] = $nGroupPat;
            while($nGroupPat) {
                if($nGroupPat & 1) $mLines--;
                $nGroupPat >>= 1;
            }
            $nGroupsLines[$iGroup] = $mLines;
        }
        /* check if symmetric transformation required */
        if($nLinesOffset[0][$nGroupsPat[0]] < 0) {
            $iSym = -$nLinesOffset[0][$nGroupsPat[0]];
            $nTemp = $nPat1a;
            $nPat1 = 0;
            $iBit = 0;
            while($nTemp) {
                if($nTemp & 1) $nPat1 += $SymMap1[$iSym][$iBit];
                $nTemp = RShift($nTemp,1);
                $iBit++;
            }
            $nTemp = $nPat2a;
            $nPat2 = 0;
            $iBit = 0;
            while($nTemp) {
                if($nTemp & 1) $nPat2 += $SymMap2[$iSym][$iBit];
                $nTemp = RShift($nTemp,1);
                $iBit++;
            }
            goto retry;
        }
        /* check positions with one line added */
        for($iGroup=0;$iGroup<$nGroups;$iGroup++) {
            $nGroupPat = $nGroupsPat[$iGroup];
            $iLineLo = $iShifts[$iGroup];
            $iLineHi = $iLineLo + $nGroupSizes[$iGroup];
            if($nGroupPat) {  /* if there's room for another line */
                /* read in file with extra line in $iGroup */
                $sFilename = $sProblemName.'/'.($nLines+1);;
                $nGroupLines = $nGroupsLines[$iGroup];
                for($jGroup=0;$jGroup<$nGroups-1;$jGroup++) {
                    $mLines = $jGroup == $iGroup ?
                     $nGroupLines+1 : $nGroupsLines[$jGroup];
                    $sFilename .= '/'.$mLines;
                }
                $sFilename .= ".bin";
                $nBytes = 1;
                for($jGroup=$nGroups-1;$jGroup>=0;$jGroup--) {
                    $nGroupsMult[$jGroup] = $nBytes;
                    $mLines = $jGroup == $iGroup ?
                     $nGroupLines+1 : $nGroupsLines[$jGroup];
/* printf("$jGroup=%d $nBytes=%d $mLines=%d\n",$jGroup,$nBytes,$mLines); */
                    $nBytes *= $nLinesCount[$jGroup][$mLines];
                }
if($DBUG) {
                printf("Read %d bytes from %s.\n",$nBytes,$sFilename);
}
                $previous = file_get_contents($sFilename);
                if($previous === FALSE) {
                    /* opening book exhausted--time to use in-memory analysis*/
                    $bFinish = 1;
                    $bShow = 'Y';
                    $sComputerPlay = 'C';
                    return;
                    //printf("Opening book exhausted (%s missing)\n",$sFilename);
                    //abortProgram();
                }
                $nBytes2 = strlen($previous);
                if($nBytes != $nBytes2) {
                    printf(
                     "Read from file %s failed.  Expected %d bytes, got %d.\n",
                     $sFilename,$nBytes,$nBytes2);
                    abortProgram();
                }
                /* calculate the offsets into "previous" for $iGroup with
                   one line added */
                $nPatiGroup = $nLinesIndex2[$iGroup][$nGroupLines+1];
                $nMult = $nGroupsMult[$iGroup];
                do {
                    $nLinesProd[$nPatiGroup] = 
                     $nLinesOffset[$iGroup][$nPatiGroup] * $nMult;
                    $nPatiGroup = $nLinesLink[$iGroup][$nPatiGroup];
                } while($nPatiGroup > 0);
                /* if first group, copy negative symmetry nos. for
                   symmetry covered positions */
                if(!$iGroup) {
                    for($nPatiGroup=$nLinesIndexSym[$nGroupLines+1]; 
                     $nPatiGroup>=0;
                     $nPatiGroup=$nLinesLink[0][$nPatiGroup]) {
                        $nLinesProd[$nPatiGroup] =
                         $nLinesOffset[0][$nPatiGroup];
                    }
                }
                /* calculate offset into previous */
                $ixPrevious = 0;
                for($jGroup=0;$jGroup<$nGroups;$jGroup++) {
                    if($jGroup != $iGroup) {
                        $ixPrevious += $nLinesOffset[$jGroup][$nGroupsPat[$jGroup]] *
                         $nGroupsMult[$jGroup];
                    }
                }
                /* check the move */
                $nPatiGroup = $nGroupsPat[$iGroup];
                if($iClusters[$iGroup]) {
                    for($iLine=$iLineLo; $iLine < $iLineHi; $iLine++) {
                        if($nPat2 & $TestBits[$iLine]) {
                            /* found a possible move--test for new boxes */
                            $nBoxesNew =
                             (($nPat1 & $TestBox2[0][$iLine]) == 0 &&
                              ($nPat2 & $TestBox2[1][$iLine]) == 0) +
                             (($nPat1 & $TestBox2[2][$iLine]) == 0 &&
                              ($nPat2 & $TestBox2[3][$iLine]) == 0);
                            $nProd = $nLinesProd[$nPatiGroup &
                             $MaskBits[$iLine-$iLineLo]];
if($DBUG) {
printf("nPatiGroup=%lx iLine-iLineLo=%d MaskBits=%lx And=%lx nProd=%ld\n",
$nPatiGroup,$iLine-$iLineLo,$MaskBits[$iLine-$iLineLo],$nPatiGroup &
 $MaskBits[$iLine-$iLineLo],$nProd);
}
                            if($nProd >= 0) $nScore =
                             ord($previous{$ixPrevious+$nProd});
                            else symmetry();
if($DBUG){
                            $nScoreSave1 = $nScore;
                            $nBoxesNewSave = $nBoxesNew;
}
                            $nLoony = $nScore & 3;
                            $nScore >>= 2;
                            if($nScore >= 32) $nScore -= 64;
                            $iChain = $ixChain2[$iLine];
                            if($iChain >= 0) {
                                $nScoreBeforeChain[$iChain] = $nScore;
                                chain($iChain);
                            }
if($DBUG) {
printf("nPat2=%04X iLine=%d iGroup=%d nProd=%d %d ",$nPat2,$iLine,$iGroup
,$nProd,$ixPrevious+$nProd);
printf("nScore=%3d nScoreSoFar=%4d nBoxesNew=%d\n",
$nScore,$nScoreSoFar,$nBoxesNew);
                            $nScoreSave2 = $nScore;
}
                            if ($nBoxesNew) {
                                $nScore += $nBoxesNew;
                            } else {
                                $nScore = -$nScore;
                                $nLoony = 4 - $nLoony;
                            }
if($DBUG){
                            printf("Pat1=%06X Line+nHalf1=%2d Grp=%d Prod=%3d %3d ",
                             $nPat1,
                             $iLine+$nHalf1,$iGroup,$nProd,$ixPrevious+$nProd);
                            printf("Score=%3d:%3d:%3d",
                             $nScoreSave1,$nScoreSave2,$nScore);
                            printf("%2d",$nLoony);
                            printf(" Chain=%2d BxNew=%d:%d\n",
                             $iChain,$nBoxesNewSave,$nBoxesNew);
}
                            $nScores2[$iLine+$nHalf1] =
                             $nScoreSoFar + $nPlayer*$nScore;
                            $nLoonys2[$iLine+$nHalf1] = $nPlayer > 0 ?
                             $nLoony : 4 - $nLoony;
                        } else {
                            $nScores2[$iLine+$nHalf1] = -128;
                            $nLoonys2[$iLine+$nHalf1] = 0;
                        }
                    }
                } else {
                    for($iLine=$iLineLo; $iLine < $iLineHi; $iLine++) {
                        if($nPat1 & $TestBits[$iLine]) {
                            /* found a possible move--test for new boxes */
                            $nBoxesNew =
                             (($nPat1 & $TestBox1[0][$iLine]) == 0 &&
                              ($nPat2 & $TestBox1[1][$iLine]) == 0) +
                             (($nPat1 & $TestBox1[2][$iLine]) == 0 &&
                              ($nPat2 & $TestBox1[3][$iLine]) == 0);
                            $nProd = $nLinesProd[$nPatiGroup &
                             $MaskBits[$iLine-$iLineLo]];
if($DBUG) {
printf("nPatiGroup=%lx iLine-iLineLo=%d MaskBits=%lx And=%lx nProd=%ld\n",
$nPatiGroup,$iLine-$iLineLo,$MaskBits[$iLine-$iLineLo],$nPatiGroup &
 $MaskBits[$iLine-$iLineLo],$nProd);
}
                            if($nProd >= 0) $nScore = 
                             ord($previous{$ixPrevious+$nProd});
                            else symmetry();
if($DBUG){
                            $nScoreSave1 = $nScore;
                            $nBoxesNewSave = $nBoxesNew;
}
                            $nLoony = $nScore & 3;
                            $nScore >>= 2;
                            if($nScore >= 32) $nScore -= 64;
                            $iChain = $ixChain1[$iLine];
                            if($iChain >= 0) {
                                $nScoreBeforeChain[$iChain] = $nScore;
                                chain($iChain);
                            }
if($DBUG){
                            $nScoreSave2 = $nScore;
}
                            if ($nBoxesNew) {
                                $nScore += $nBoxesNew;
                            } else {
                                $nScore = -$nScore;
                                $nLoony = 4 - $nLoony;
                            }
if($DBUG){
                            printf("Pat1=%06X Line=%2d Grp=%d Prod=%3d %3d ",
                             $nPat1,
                             $iLine,$iGroup,$nProd,$ixPrevious+$nProd);
                            printf("Score=%3d:%3d:%3d",
                             $nScoreSave1,$nScoreSave2,$nScore);
                            printf("%2d",$nLoony);
                            printf(" Chain=%2d BxNew=%d:%d\n",
                             $iChain,$nBoxesNewSave,$nBoxesNew);
}
                            $nScores2[$iLine] = $nScoreSoFar + $nPlayer*$nScore;
                            $nLoonys2[$iLine] = $nPlayer > 0 ? $nLoony : 4 - $nLoony;
                        } else {
                            $nScores2[$iLine] = -128;
                            $nLoonys2[$iLine] = 0;
                        }
                    }
                }
            } else {
                if($iClusters[$iGroup]) {
                    for($iLine=$iLineLo; $iLine < $iLineHi; $iLine++) {
                        $nScores2[$iLine+$nHalf1] = -128;
                        $nLoonys2[$iLine+$nHalf1] = 0;
                    }
                } else {
                    for($iLine=$iLineLo; $iLine < $iLineHi; $iLine++) {
                        $nScores2[$iLine] = -128;
                        $nLoonys2[$iLine] = 0;
                    }
                }
            }
        }
        /* copy $nScores2 to $nScores compensating for sym. transformation */
        $nLoonyMin = 4;
        $nLoonyMax = 0;
if($DBUG){
for($i = 0; $i<=2*$nRows; $i++) {
for($j = 0; $j<=2*$nCols; $j++) {
echo ord($position[$i]{$j}).' ';
}
echo "\n";
}
}
        for($iBit=0; $iBit<$nBits; $iBit++) {
            $i = $nBitsRows[$iBit];
            $j = $nBitsCols[$iBit];
            $i2 = ($iSym & 1) ? 2*$nRows - $i : $i;
            $j2 = ($iSym & 2) ? 2*$nCols - $j : $j;
            if($iSym & 4) {
                $iTemp = $i2;
                $i2 = $j2;
                $j2 = $iTemp;
            }
            $iBit2 = ord($position[$i2]{$j2}) - 128;
if($DBUG) {
echo "iBit=$iBit i=$i j=$j iSym=$iSym i2=$i2 j2=$j2 iBit2=$iBit2".
 " nScores2[iBit2]=$nScores2[$iBit2] nLoonys2[iBit2]=$nLoonys2[$iBit2]\n";
}
            $nScores[$iBit] = $nScores2[$iBit2];
            $nLoonys[$iBit] = $nLoonys2[$iBit2];
            if($nScoreMax < $nScores[$iBit] || ($nScoreMax == $nScores[$iBit]
             && $nLoonyMax < $nLoonys[$iBit])) {
                $nScoreMax = $nScores[$iBit];
                $nLoonyMax = $nLoonys[$iBit];
            }
            if($nScores[$iBit] != -128 && ($nScoreMin > $nScores[$iBit] ||
             ($nScoreMin == $nScores[$iBit] && $nLoonyMin > $nLoonys[$iBit]))) {
                $nScoreMin = $nScores[$iBit];
                $nLoonyMin = $nLoonys[$iBit];
            }

/* printf("iSym=%d iBit=%d i=%d j=%d iBit2=%d i2=%d j2=%d nScore=%d\n",
$iSym,$iBit,$i,$j,$iBit2,$i2,$j2,$nScores[$iBit]); */
        }
    }
}

function display() {
    global $position,$nCols,$nRows,$chBoxes,$remainingMoves;

    /* ----------------------- display result -------------------- */
    printf("\n ");
    for($j=0;$j<=2*$nCols;$j++) {
        printf("  ".chr(ord('a')+$j));
    }
    printf("\n\n");
    for($i=0;$i<=2*$nRows;$i++) {
        if($i&1) {
            fillerRow($i);
            printf(chr(ord('a')+$i));
            for($j=0;$j<=2*$nCols;$j+=2) {
                if($j) {
                    $ch = $position[$i]{$j-1};
                    if(ord($ch) >= 128) $ch = $chBoxes[ord($ch) - 128];
                    printf($ch);
                }
                printf(sScore($i,$j,"  |  "));
            }
            printf("\n");
            fillerRow($i);
        } else {
            printf(chr(ord('a')+$i));
            printf("  ");
            printf($position[$i]{0});
            if($position[$i]{0} == '#' && $remainingMoves)
             $position[$i]{0} = '+';
            for($j=1;$j<2*$nCols;$j+=2) {
                printf(sScore($i,$j,"-----"));
                printf($position[$i]{$j+1});
                if($position[$i]{$j+1} == '#' && $remainingMoves)
                 $position[$i]{$j+1} = '+';
            }
            printf("\n");
        }
    }
    printf("\n");
}


$letters = "abcdefghijklmnopqrstuvwxyz";
$remainingMoves = $moves;
while(1) {
    main();
    if($bFinish) {
        $position = $savePosition;
        $nScores = $nSaveScores;
        $nPlayer = $nPlayerSave;
        $i2 = strpos($letters,substr($moves,-2,1));
        $j2 = strpos($letters,substr($moves,-1,1));
        break;
    }
//    display();
    $savePosition = $position;
    $nSaveScores = $nScores;
    $nPlayerSave = $nPlayer;
    if($remainingMoves == "") break;
    $ch0 = $remainingMoves{0};
    $i = ord($remainingMoves{0}) - ord('a');
    $j = ord($remainingMoves{1}) - ord('a');
    $remainingMoves = substr($remainingMoves,2);
    domove($i,$j);
}

function sMoveScore($i,$j,$sRawScore) {
    global $scores,$nMin,$nMax,$i2,$j2,$bShow,$opt,$letters,$game,$moves;
    global $bFinish,$final;

    $ch = $sRawScore{2};
    if($ch >= '0' && $ch <= '9') {
        sscanf(substr($sRawScore,0,3),"%d",$score);
        $nMin = min($nMin,$score);
        $nMax = max($nMax,$score);
        $scores[$i][$j] = $score;
        if(!$bFinish)
         $sRawScore = " ".($bShow?substr($sRawScore,1,3):" ? ")." ";
         elseif($i == $i2 && $j == $j2) {
             $final = $score;
             $sRawScore = "".$sRawScore."";
         }
    } else {
        $scores[$i][$j] = 99;
    }
    return $sRawScore;
}

    while($sComputerPlay == ($nPlayer > 0 ? 'A' : 'B') && !$bFinish) {
        // it's our turn to move
        $nMin = 99;
        $nMax = -99;
        $scores = array();
        for($i=0;$i<=2*$nRows;$i++) {
            if($i&1) {
                for($j=0;$j<=2*$nCols;$j+=2) {
                    sMoveScore($i,$j,sScore($i,$j,"  |  "));
                }
            } else {
                for($j=1;$j<2*$nCols;$j+=2) {
                    sMoveScore($i,$j,sScore($i,$j,"-----"));
                }
            }
        }
        if($nMax == -99) break;
        $nTarget = $sComputerPlay == 'A' ? $nMax : $nMin;
        $nChoices = 0;
        $ii = array();
        $jj = array();
        for($i=0;$i<=2*$nRows;$i++) {
            if($i&1) {
                for($j=0;$j<=2*$nCols;$j+=2) {
                    if($scores[$i][$j] == $nTarget) {
                         $ii[$nChoices] = $i;
                         $jj[$nChoices] = $j;
                         $nChoices++;
                    }
                }
            } else {
                for($j=1;$j<2*$nCols;$j+=2) {
                    if($scores[$i][$j] == $nTarget) {
                         $ii[$nChoices] = $i;
                         $jj[$nChoices] = $j;
                         $nChoices++;
                    }
                }
            }
        }
        if($nChoices) {
            $nChoice = rand(0,$nChoices-1);
            $i = $ii[$nChoice];
            $j = $jj[$nChoice];
            $remainingMoves = substr($letters,$i,1).substr($letters,$j,1);
            $moves .= $remainingMoves;
            $savePosition = $position;
            $nSaveScores = $nScores;
            $nPlayerSave = $nPlayer;
            domove($i,$j);
            $remainingMoves = "";
            main();
            if($bFinish) {
                $position = $savePosition;
                $nScores = $nSaveScores;
                $nPlayer = $nPlayerSave;
                $i2 = strpos($letters,substr($moves,-2,1));
                $j2 = strpos($letters,substr($moves,-1,1));
                break;
            }
        }
    }

    if($moves) {
        if($i & 1) $position[$i-1]{$j} = $position[$i+1]{$j} = '#';
        else $position[$i]{$j-1} = $position[$i]{$j+1} = '#';
    }

    $nMin = 99;
    $nMax = -99;
$nScoreA = $nScoreB = 0;

$scores = array();

    $final = -999;
    printf("\n\n");
    for($i=0;$i<=2*$nRows;$i++) {
        if($i&1) {
            fillerRow($i);
            printf(' ');
            for($j=0;$j<=2*$nCols;$j+=2) {
                if($j) {
                    $ch = $position[$i]{$j-1};
                    if(ord($ch) >= 128) $ch = $chBoxes[ord($ch) - 128];
                    printf($ch);
                    if($ch == 'A') $nScoreA++;
                    elseif($ch == 'B') $nScoreB++;
                }
                printf(sMoveScore($i,$j,sScore($i,$j,"  |  ")));
            }
            printf("\n");
            fillerRow($i);
        } else {
            printf("   ");
            printf($position[$i]{0});
            if($position[$i]{0} == '#') $position[$i]{0} = '+';
            for($j=1;$j<2*$nCols;$j+=2) {
                printf(sMoveScore($i,$j,sScore($i,$j,"-----")));
                printf($position[$i]{$j+1});
                if($position[$i]{$j+1} == '#') $position[$i]{$j+1} = '+';
            }
            printf("\n");
        }
    }
    printf("\n");


echo "
"; echo "Player A has $nScoreA boxes."; if($game=="3x3") echo " Player A (first player) needs 4 boxes to win."; echo "
\n"; echo "Player B has $nScoreB boxes."; if($game=="3x3") echo " Player B (second player) needs 6 boxes to win.\n"; echo "
\n"; if($game=="3x3") echo "See ". "Analysis Results for why player B ". "needs 6 rather than 5 boxes to win.
\n"; echo "
\n"; if($nMin < 99 && !$bFinish) { printf("\nClick on a move for player %s or choose one of the following.

\n", $nPlayer > 0 ? 'A' : 'B'); echo " ".($sComputerPlay == 'B' ? 'X' : ' '). " Make me player A.
\n"; echo " ".($sComputerPlay == 'A' ? 'X' : ' '). " Make me player B.
\n"; echo " ".($sComputerPlay == 'C' ? 'X' : ' '). " Let me move for both players.

\n"; ?> &moves=".($bShow?"Hide":"Show"); ?> Analysis

Opening book is exhausted

\n"; if($final == -999) $final = $nPlayer > 0 ? $nMax : $nMin; echo "With best play, "; if(!$final) echo "the game is tied."; elseif($final > 0) echo "player A wins by $final boxes."; else echo "player B wins by ".(-$final)." boxes."; echo "

\n"; } ?> Dots-and-Boxes Index

Start a new game

\n"; echo "Use your browser's back button to back up a move.

\n"; } if($bShow && $nMin < 99) { ?> In the analysis, the scores are the number of boxes player A will get minus the number of boxes player B will get with best play if the player on the move selects the corresponding line. A suffix of v on a score means player A must make the next loony move; ^ means player B must.