home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_400 / 429_01 / chess12 / chess.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  1994-04-29  |  27.0 KB  |  1,252 lines
  1. #include "misc.hpp"
  2. #include "brdsize.hpp"
  3. #include "chess.hpp"
  4.  
  5. extern void OutOfMemory(void);
  6.  
  7. // piece values.
  8. const int VALUEKING = 0,
  9.       VALUEPAWN = 2,
  10.       VALUEROOK = 10,
  11.       VALUEKNIGHT = 6,
  12.       VALUEBISHOP = 6,
  13.       VALUEQUEEN = 18;
  14.  
  15. class PAWN : public PIECE
  16.   {
  17.   private:
  18.     // pointer to piece to which pawn has been promoted.  null if
  19.     // pawn has not been promoted.
  20.     PIECE *promotePiece;
  21.  
  22.   public:
  23.     PAWN(PIECECOLOR c) : PIECE(c, TYPEPAWN, VALUEPAWN), promotePiece(0) { }
  24.     virtual ~PAWN(void) { if (promotePiece) delete promotePiece; }
  25.  
  26.     void promote(PIECETYPE promoteType);
  27.     void restoreToPawn(void);
  28.  
  29.     virtual PIECETYPE whatType(void) const
  30.       {
  31.     if (promotePiece)
  32.       return(promotePiece->whatType());
  33.     else
  34.       return(PIECE::whatType());
  35.       }
  36.  
  37.     virtual int whatValue(void) const
  38.       {
  39.     if (promotePiece)
  40.       return(promotePiece->whatValue());
  41.     else
  42.       return(PIECE::whatValue());
  43.       }
  44.  
  45.     virtual void legalMoves
  46.       (
  47.     POSITION start,
  48.     const BOARD &board,
  49.         POSITIONLIST &moves
  50.       ) const;
  51.  
  52.   };
  53.  
  54. class ROOK : public PIECE
  55.   {
  56.   public:
  57.     ROOK(PIECECOLOR c) : PIECE(c, TYPEROOK, VALUEROOK)  { }
  58.  
  59.     virtual void legalMoves
  60.       (
  61.     POSITION start,
  62.     const BOARD &board,
  63.         POSITIONLIST &moves
  64.       ) const;
  65.  
  66.   };
  67.  
  68. class KNIGHT : public PIECE
  69.   {
  70.   public:
  71.     KNIGHT(PIECECOLOR c) : PIECE(c, TYPEKNIGHT, VALUEKNIGHT)  { }
  72.  
  73.     virtual void legalMoves
  74.       (
  75.     POSITION start,
  76.     const BOARD &board,
  77.         POSITIONLIST &moves
  78.       ) const;
  79.  
  80.   };
  81.  
  82. class BISHOP : public PIECE
  83.   {
  84.   public:
  85.     BISHOP(PIECECOLOR c) : PIECE(c, TYPEBISHOP, VALUEBISHOP)  { }
  86.  
  87.     virtual void legalMoves
  88.       (
  89.     POSITION start,
  90.     const BOARD &board,
  91.         POSITIONLIST &moves
  92.       ) const;
  93.  
  94.   };
  95.  
  96. class QUEEN : public PIECE
  97.   {
  98.   public:
  99.     QUEEN(PIECECOLOR c) : PIECE(c, TYPEQUEEN, VALUEQUEEN)  { }
  100.  
  101.     virtual void legalMoves
  102.       (
  103.     POSITION start,
  104.     const BOARD &board,
  105.         POSITIONLIST &moves
  106.       ) const;
  107.  
  108.   };
  109.  
  110. class KING : public PIECE
  111.   {
  112.   public:
  113.     KING(PIECECOLOR c) : PIECE(c, TYPEKING, VALUEKING)  { }
  114.  
  115.     virtual void legalMoves
  116.       (
  117.     POSITION start,
  118.     const BOARD &board,
  119.         POSITIONLIST &moves
  120.       ) const;
  121.  
  122.   };
  123.  
  124. // put all the pieces for one color at their starting positions on
  125. // the board
  126. LOCAL void setupPieces
  127.   (
  128.     PIECE *board[][NUMCOLS],
  129.     PIECECOLOR color,
  130.     // column in which the non-pawn pieces go
  131.     int backCol,
  132.     // column in which the pawns go
  133.     int pawnCol
  134.   )
  135.   {
  136.     BOOL f = TRUE;
  137.     int row;
  138.  
  139.     #define NEWPIECE(P, ROWOFFSET, COLOFFSET) \
  140.       f = f && \
  141.           ((board[ROWOFFSET][COLOFFSET] = new P) != (PIECE *) 0);
  142.  
  143.     NEWPIECE(ROOK(color), 0, backCol);
  144.     NEWPIECE(KNIGHT(color), 1, backCol);
  145.     NEWPIECE(BISHOP(color), 2, backCol);
  146.     NEWPIECE(QUEEN(color), 3, backCol);
  147.     NEWPIECE(KING(color), 4, backCol);
  148.     NEWPIECE(BISHOP(color), 5, backCol);
  149.     NEWPIECE(KNIGHT(color), 6, backCol);
  150.     NEWPIECE(ROOK(color), 7, backCol);
  151.  
  152.     for (row = 0; row < NUMROWS; row++)
  153.       NEWPIECE(PAWN(color), row, pawnCol);
  154.  
  155.     if (!f)
  156.       OutOfMemory();
  157.  
  158.     return;
  159.  
  160.     #undef NEWPIECE
  161.   }
  162.  
  163. BOARD::BOARD(void)
  164.   {
  165.     int row, col;
  166.  
  167.     for (row = 0; row < NUMROWS; row++)
  168.       for (col = 0; col < NUMCOLS; col++)
  169.     brd[row][col] = (PIECE *) 0;
  170.  
  171.     setupPieces(brd, WHITE, 0, 1);
  172.     setupPieces(brd, BLACK, 7, 6);
  173.  
  174.     wasLastMoveDoublePawn = FALSE;
  175.  
  176.     return;
  177.   }
  178.  
  179. BOARD::~BOARD(void)
  180.   {
  181.     int r, c;
  182.  
  183.     for (r = 0; r < NUMROWS; r++)
  184.       for (c = 0; c < NUMROWS; c++)
  185.     {
  186.       if (brd[r][c])
  187.         delete brd[r][c];
  188.     }
  189.  
  190.     return;
  191.   }
  192.  
  193. void BOARD::doMove
  194.   (
  195.     POSITION start,
  196.     POSITION end,
  197.     MOVEUNDODATA &undoData
  198.   )
  199.   {
  200.     undoData.capturedPiece = brd[end.row][end.col];
  201.     undoData.enPassantEffect = OTHERMOVE;
  202.  
  203.     brd[end.row][end.col] = brd[start.row][start.col];
  204.   
  205.     brd[start.row][start.col] = (PIECE *) 0;
  206.     brd[end.row][end.col]->moveDone();
  207.  
  208.     if (brd[end.row][end.col]->whatType() == TYPEPAWN)
  209.       {
  210.     if (wasLastMoveDoublePawn)
  211.       if ((doubleMovedPawn.row == end.row) &&
  212.           (doubleMovedPawn.col == start.col) &&
  213.           (start.row != end.row) &&
  214.           !undoData.capturedPiece)
  215.           // these last two tests are necessary to handle situations
  216.           // where the same color is moved twice in a row when
  217.           // looking for check in "canCastle" and looking for
  218.           // stalemate
  219.         {
  220.           // en passant capture
  221.           undoData.capturedPiece =
  222.         brd[doubleMovedPawn.row][doubleMovedPawn.col];
  223.           brd[doubleMovedPawn.row][doubleMovedPawn.col] =
  224.         (PIECE *) 0;
  225.           undoData.saveDoubleMoved = doubleMovedPawn;
  226.           undoData.enPassantEffect = ENPASSANTCAPTURE;
  227.           wasLastMoveDoublePawn = FALSE;
  228.           return;
  229.         }
  230.     {
  231.       int diff = start.col - end.col;
  232.       if (diff < 0)
  233.         diff = -diff;
  234.       if (diff == 2)
  235.         {
  236.           if (wasLastMoveDoublePawn)
  237.         {
  238.           undoData.saveDoubleMoved = doubleMovedPawn;
  239.           undoData.enPassantEffect = AFTERDOUBLEMOVE;
  240.         }
  241.           doubleMovedPawn = end;
  242.           wasLastMoveDoublePawn = TRUE;
  243.           return;
  244.         }
  245.     }
  246.       }
  247.  
  248.     if (wasLastMoveDoublePawn)
  249.       {
  250.     undoData.saveDoubleMoved = doubleMovedPawn;
  251.     undoData.enPassantEffect = AFTERDOUBLEMOVE;
  252.       }
  253.     wasLastMoveDoublePawn = FALSE;
  254.  
  255.     return;
  256.   }
  257.  
  258. void BOARD::undoMove
  259.   (
  260.     POSITION end,
  261.     POSITION orig,
  262.     MOVEUNDODATA undoData
  263.   )
  264.   {
  265.     brd[orig.row][orig.col] = brd[end.row][end.col];
  266.  
  267.     brd[orig.row][orig.col]->moveUndone();
  268.  
  269.     if (undoData.enPassantEffect == ENPASSANTCAPTURE)
  270.       {
  271.     brd[end.row][orig.col] = undoData.capturedPiece;
  272.     brd[end.row][end.col] = (PIECE *) 0;
  273.       }
  274.     else
  275.       brd[end.row][end.col] = undoData.capturedPiece;
  276.  
  277.     if (undoData.enPassantEffect == OTHERMOVE)
  278.       wasLastMoveDoublePawn = FALSE;
  279.     else
  280.       {
  281.     wasLastMoveDoublePawn = TRUE;
  282.     doubleMovedPawn = undoData.saveDoubleMoved;
  283.       }
  284.  
  285.     return;
  286.   }
  287.  
  288. BOOL BOARD::canCastle(MOVETYPE whichCastle, PIECECOLOR color)
  289.   {
  290.     int col = color == WHITE ? 0 : 7;
  291.     int row, rowStep;
  292.     BOARDMETRIC metric;
  293.  
  294.     if (whichCastle == QUEENSIDECASTLE)
  295.       {
  296.     row = 0;
  297.     rowStep = 1;
  298.       }
  299.     else
  300.       {
  301.     row = 7;
  302.     rowStep = -1;
  303.       }
  304.  
  305.     // make sure king & rook in initial positions and have never been
  306.     // moved.
  307.     if (!brd[row][col])
  308.       return(FALSE);
  309.     if (brd[row][col]->hasBeenMoved())
  310.       return(FALSE);
  311.     if (!brd[4][col])
  312.       return(FALSE);
  313.     if (brd[4][col]->hasBeenMoved())
  314.       return(FALSE);
  315.  
  316.     // make sure no pieces in between
  317.     for ( ; ; )
  318.       {
  319.     row += rowStep;
  320.     if (row == 4)
  321.       break;
  322.     if (brd[row][col])
  323.       return(FALSE);
  324.       }
  325.  
  326.     // make sure king is not in check
  327.     findBestMoves(1, OtherColor(color), metric, (BESTMOVES *) 0);
  328.     if (metric.kingSituation[color] == KINGLOST)
  329.       return(FALSE);
  330.  
  331.     // make sure king would not be in check in intermediate position
  332.     brd[4 - rowStep][col] = brd[4][col];
  333.     brd[4][col] = (PIECE *) 0;
  334.     findBestMoves(1, OtherColor(color), metric, (BESTMOVES *) 0);
  335.     brd[4][col] = brd[4 - rowStep][col];
  336.     brd[4 - rowStep][col] = (PIECE *) 0;
  337.  
  338.     return(metric.kingSituation[color] == KINGOK);
  339.   }
  340.  
  341. void BOARD::castle
  342.   (
  343.     MOVETYPE whichCastle,
  344.     PIECECOLOR color,
  345.     MOVEUNDODATA &undoData
  346.   )
  347.   {
  348.     int col = color == WHITE ? 0 : 7;
  349.  
  350.     if (whichCastle == QUEENSIDECASTLE)
  351.       {
  352.     brd[3][col] = brd[0][col];
  353.     brd[2][col] = brd[4][col];
  354.     brd[0][col] = (PIECE *) 0;
  355.     brd[4][col] = (PIECE *) 0;
  356.     brd[3][col]->moveDone();
  357.     brd[2][col]->moveDone();
  358.       }
  359.     else
  360.       {
  361.     brd[5][col] = brd[7][col];
  362.     brd[6][col] = brd[4][col];
  363.     brd[7][col] = (PIECE *) 0;
  364.     brd[4][col] = (PIECE *) 0;
  365.     brd[5][col]->moveDone();
  366.     brd[6][col]->moveDone();
  367.       }
  368.  
  369.     if (wasLastMoveDoublePawn)
  370.       {
  371.     undoData.enPassantEffect = AFTERDOUBLEMOVE;
  372.     undoData.saveDoubleMoved = doubleMovedPawn;
  373.     wasLastMoveDoublePawn = FALSE;
  374.       }
  375.     else
  376.       undoData.enPassantEffect = OTHERMOVE;
  377.  
  378.  
  379.     return;
  380.   }
  381.  
  382. void BOARD::undoCastle
  383.   (
  384.     MOVETYPE whichCastle,
  385.     PIECECOLOR color,
  386.     MOVEUNDODATA &undoData
  387.   )
  388.   {
  389.     int col = color == WHITE ? 0 : 7;
  390.  
  391.     if (whichCastle == QUEENSIDECASTLE)
  392.       {
  393.     brd[0][col] = brd[3][col];
  394.     brd[4][col] = brd[2][col];
  395.     brd[3][col] = (PIECE *) 0;
  396.     brd[2][col] = (PIECE *) 0;
  397.     brd[0][col]->moveUndone();
  398.     brd[4][col]->moveUndone();
  399.       }
  400.     else
  401.       {
  402.     brd[7][col] = brd[5][col];
  403.     brd[4][col] = brd[6][col];
  404.     brd[5][col] = (PIECE *) 0;
  405.     brd[6][col] = (PIECE *) 0;
  406.     brd[7][col]->moveUndone();
  407.     brd[4][col]->moveUndone();
  408.       }
  409.  
  410.     if (undoData.enPassantEffect == AFTERDOUBLEMOVE)
  411.       {
  412.     wasLastMoveDoublePawn = TRUE;
  413.         doubleMovedPawn = undoData.saveDoubleMoved;
  414.       }
  415.     else
  416.       wasLastMoveDoublePawn = FALSE;
  417.  
  418.     return;
  419.   }
  420.  
  421. BOOL BOARD::canPromote(POSITION where)
  422.   {
  423.     PIECE *p = whatPiece(where);
  424.  
  425.     if (!p)
  426.       return(FALSE);
  427.  
  428.     if (where.col != (p->whatColor() == WHITE ? (NUMCOLS - 1) : 0))
  429.       return(FALSE);
  430.  
  431.     return(p->whatType() == TYPEPAWN);
  432.   }
  433.  
  434. void BOARD::promote(POSITION where, PIECETYPE promoteType)
  435.   {
  436.     ((PAWN *) whatPiece(where))->promote(promoteType);
  437.     return;
  438.   }
  439.  
  440. void BOARD::restorePawn(POSITION where)
  441.   {
  442.     ((PAWN *) whatPiece(where))->restoreToPawn();
  443.     return;
  444.   }
  445.  
  446. MOVESTATUS BOARD::doUserMove
  447.   (
  448.     POSITION start,
  449.     POSITION end
  450.   )
  451.   {
  452.     PIECE *p = whatPiece(start.row, start.col), *taken;
  453.     POSITIONLIST moves;
  454.     BOARDMETRIC metric;
  455.     BESTMOVES bestMoves;
  456.     MOVEUNDODATA undoData;
  457.     int m;
  458.  
  459.     if (!p)
  460.       return(MOVESTATUS(ILLEGALMOVE));
  461.  
  462.     p->legalMoves(start, *this, moves);
  463.     for (m = 0; m < moves.nMoves; m++)
  464.       {
  465.     if ((moves.end[m].row == end.row) &&
  466.         (moves.end[m].col == end.col))
  467.       break;
  468.       }
  469.     if (m == moves.nMoves)
  470.       return(MOVESTATUS(ILLEGALMOVE));
  471.  
  472.     doMove(start, end, undoData);
  473.  
  474.     findBestMoves(1, OtherColor(p->whatColor()), metric, &bestMoves);
  475.  
  476.     if (metric.kingSituation[p->whatColor()] == KINGLOST)
  477.       {
  478.         undoMove(end, start, undoData);
  479.     return(MOVESTATUS(WOULDLOSEKING, bestMoves.move[0].start));
  480.       }
  481.  
  482.     if (undoData.capturedPiece)
  483.       delete undoData.capturedPiece;
  484.     if (undoData.enPassantEffect == ENPASSANTCAPTURE)
  485.       return(MOVESTATUS(MOVEENPASSANT));
  486.     else
  487.       return(MOVESTATUS(MOVEDONE));
  488.   }
  489.  
  490. BOOL BOARD::userCanCastle
  491.   (
  492.     MOVETYPE whichCastle,
  493.     PIECECOLOR color
  494.   )
  495.   {
  496.     BOARDMETRIC metric;
  497.     MOVEUNDODATA undoData;
  498.  
  499.     if (!canCastle(whichCastle, color))
  500.       return(FALSE);
  501.  
  502.     castle(whichCastle, color, undoData);
  503.  
  504.     // make sure king is not in check in final position
  505.     findBestMoves(1, OtherColor(color), metric, (BESTMOVES *) 0);
  506.  
  507.     undoCastle(whichCastle, color, undoData);
  508.  
  509.     return(metric.kingSituation[color] == KINGOK);
  510.   }
  511.  
  512.  
  513. // tables that help in comparing the kingSituation portions of two
  514. // board metrics
  515.  
  516. class SITUATIONCOMPARETABLE
  517.   {
  518.   private:
  519.     int t[3][3];
  520.  
  521.   public:
  522.     int * operator [] (int i) { return(t[i]); }
  523.   };
  524.  
  525. class THISSITUATIONCOMPARETABLE : public SITUATIONCOMPARETABLE
  526.   {
  527.   public:
  528.     THISSITUATIONCOMPARETABLE(void)
  529.       {
  530.     (*this)[KINGLOST][KINGLOST] = 0;
  531.     (*this)[KINGLOST][STALEMATE] = -1;
  532.     (*this)[KINGLOST][KINGOK] = -1;
  533.     (*this)[STALEMATE][KINGLOST] = 1;
  534.     (*this)[STALEMATE][STALEMATE] = 0;
  535.     (*this)[STALEMATE][KINGOK] = -1;
  536.     (*this)[KINGOK][KINGLOST] = 1;
  537.     (*this)[KINGOK][STALEMATE] = 1;
  538.     (*this)[KINGOK][KINGOK] = 0;
  539.  
  540.     return;
  541.       }
  542.   };
  543.  
  544. LOCAL THISSITUATIONCOMPARETABLE thisSituationCompareTable;
  545.  
  546. class OTHERSITUATIONCOMPARETABLE : public SITUATIONCOMPARETABLE
  547.   {
  548.   public:
  549.     OTHERSITUATIONCOMPARETABLE(void)
  550.       {
  551.     (*this)[KINGLOST][KINGLOST] = 0;
  552.     (*this)[KINGLOST][STALEMATE] = 1;
  553.     (*this)[KINGLOST][KINGOK] = 1;
  554.     (*this)[STALEMATE][KINGLOST] = -1;
  555.     (*this)[STALEMATE][STALEMATE] = 0;
  556.     (*this)[STALEMATE][KINGOK] = -1;
  557.     (*this)[KINGOK][KINGLOST] = -1;
  558.     (*this)[KINGOK][STALEMATE] = 1;
  559.     (*this)[KINGOK][KINGOK] = 0;
  560.  
  561.     return;
  562.       }
  563.   };
  564.  
  565. LOCAL OTHERSITUATIONCOMPARETABLE otherSituationCompareTable;
  566.  
  567. // compare two board metrics.  if the second metric is invalid,
  568. // the first metric is better.  the color parameter gives the player
  569. // for whom the metric is supposed to be better.
  570. LOCAL int compareMetric
  571.   (
  572.     const BOARDMETRIC &a,
  573.     const BOARDMETRIC &b,
  574.     BOOL bValid,
  575.     PIECECOLOR color
  576.   )
  577.   {
  578.     PIECECOLOR otherColor = OtherColor(color);
  579.     int compare;
  580.  
  581.     if (!bValid)
  582.       return(1);
  583.  
  584.     compare = thisSituationCompareTable[a.kingSituation[color]]
  585.                        [b.kingSituation[color]];
  586.     if (compare != 0)
  587.       return(compare);
  588.  
  589.     compare = otherSituationCompareTable[a.kingSituation[otherColor]]
  590.                         [b.kingSituation[otherColor]];
  591.     if (compare != 0)
  592.       return(compare);
  593.  
  594.     compare = a.materialDiff - b.materialDiff;
  595.  
  596.     if (color == BLACK)
  597.       compare = -compare;
  598.  
  599.     return(compare);
  600.   }
  601.  
  602. void BOARD::helpFindBestMoves
  603.   (
  604.     int lookAhead,
  605.     PIECECOLOR moveColor,
  606.     BOARDMETRIC &metric,
  607.     BESTMOVES *bestMoves
  608.   )
  609.   {
  610.     POSITION where;
  611.     POSITIONLIST moves;
  612.     BOARDMETRIC testMetric;
  613.     BOOL metricSet = FALSE;
  614.     MOVEUNDODATA undoData;
  615.     int m, compareResult;
  616.     int origMaterialDiff = metric.materialDiff;
  617.     MOVETYPE castleType;
  618.  
  619.     testMetric.kingSituation[WHITE] = KINGOK;
  620.     testMetric.kingSituation[BLACK] = KINGOK;
  621.  
  622.     // try all possible moves for the given color
  623.  
  624.     for (where.row = 0; where.row < NUMROWS; where.row++)
  625.       for (where.col = 0; where.col < NUMCOLS; where.col++)
  626.     {
  627.       if (whatPiece(where))
  628.         if (whatPiece(where)->whatColor() == moveColor)
  629.           {
  630.         whatPiece(where)->legalMoves(where, *this, moves);
  631.         for (m = 0; m < moves.nMoves; m++)
  632.           {
  633.             testMetric.materialDiff = origMaterialDiff;
  634.             doMove
  635.               (
  636.             where,
  637.             moves.end[m],
  638.             undoData
  639.               );
  640.  
  641.             if (undoData.capturedPiece)
  642.               {
  643.             if (undoData.capturedPiece->whatType() == TYPEKING)
  644.               {
  645.                 undoMove
  646.                   (
  647.                 moves.end[m],
  648.                 where,
  649.                 undoData
  650.                   );
  651.  
  652.                 metric.kingSituation[OtherColor(moveColor)] =
  653.                   KINGLOST;
  654.  
  655.                 if (bestMoves)
  656.                   {
  657.                 bestMoves->nMoves = 0;
  658.                 bestMoves->move[0] =
  659.                   PIECEMOVE
  660.                     (
  661.                       NORMALMOVE,
  662.                       where,
  663.                       moves.end[m]
  664.                     );
  665.                   }
  666.  
  667.                 return;
  668.               }
  669.             testMetric.materialDiff -=
  670.               undoData.capturedPiece->signedValue();
  671.               }
  672.  
  673.             if (canPromote(moves.end[m]))
  674.               {
  675.             testMetric.materialDiff -=
  676.               whatPiece(moves.end[m])->signedValue();
  677.             promote(moves.end[m], TYPEQUEEN);
  678.             testMetric.materialDiff +=
  679.               whatPiece(moves.end[m])->signedValue();
  680.             if (lookAhead > 1)
  681.               helpFindBestMoves
  682.                 (
  683.                   lookAhead - 1,
  684.                   OtherColor(moveColor),
  685.                   testMetric,
  686.                   (BESTMOVES *) 0
  687.                 );
  688.             compareResult = compareMetric
  689.                       (
  690.                         testMetric,
  691.                         metric,
  692.                             metricSet,
  693.                         moveColor
  694.                       );
  695.                 if (compareResult >= 0)
  696.               {
  697.                 if (compareResult > 0)
  698.                   {
  699.                 metric = testMetric;
  700.                 metricSet = TRUE;
  701.                 if (bestMoves)
  702.                   bestMoves->nMoves = 0;
  703.                   }
  704.                 if (bestMoves)
  705.                   bestMoves->move[bestMoves->nMoves++] =
  706.                 PIECEMOVE
  707.                   (
  708.                     NORMALMOVE,
  709.                     where,
  710.                     moves.end[m],
  711.                     TYPEQUEEN
  712.                   );
  713.               }
  714.             testMetric.materialDiff -=
  715.               whatPiece(moves.end[m])->signedValue();
  716.             restorePawn(moves.end[m]);
  717.  
  718.             promote(moves.end[m], TYPEKNIGHT);
  719.             testMetric.materialDiff +=
  720.               whatPiece(moves.end[m])->signedValue();
  721.             if (lookAhead > 1)
  722.               helpFindBestMoves
  723.                 (
  724.                   lookAhead - 1,
  725.                   OtherColor(moveColor),
  726.                   testMetric,
  727.                   (BESTMOVES *) 0
  728.                 );
  729.             compareResult = compareMetric
  730.                       (
  731.                         testMetric,
  732.                         metric,
  733.                             metricSet,
  734.                         moveColor
  735.                       );
  736.                 if (compareResult >= 0)
  737.               {
  738.                 if (compareResult > 0)
  739.                   {
  740.                 metric = testMetric;
  741.                 metricSet = TRUE;
  742.                 if (bestMoves)
  743.                   bestMoves->nMoves = 0;
  744.                   }
  745.                 if (bestMoves)
  746.                   bestMoves->move[bestMoves->nMoves++] =
  747.                 PIECEMOVE
  748.                   (
  749.                     NORMALMOVE,
  750.                     where,
  751.                     moves.end[m],
  752.                     TYPEKNIGHT
  753.                   );
  754.               }
  755.             restorePawn(moves.end[m]);
  756.               }
  757.             else // no promotion
  758.               {
  759.             if (lookAhead > 1)
  760.               helpFindBestMoves
  761.                 (
  762.                   lookAhead - 1,
  763.                   OtherColor(moveColor),
  764.                   testMetric,
  765.                   (BESTMOVES *) 0
  766.                 );
  767.             compareResult = compareMetric
  768.                       (
  769.                         testMetric,
  770.                         metric,
  771.                             metricSet,
  772.                         moveColor
  773.                        );
  774.                 if (compareResult >= 0)
  775.               {
  776.                 if (compareResult > 0)
  777.                   {
  778.                 metric = testMetric;
  779.                 metricSet = TRUE;
  780.                 if (bestMoves)
  781.                   bestMoves->nMoves = 0;
  782.                   }
  783.                 if (bestMoves)
  784.                   bestMoves->move[bestMoves->nMoves++] =
  785.                 PIECEMOVE
  786.                   (
  787.                     NORMALMOVE,
  788.                     where,
  789.                     moves.end[m]
  790.                   );
  791.               }
  792.               }
  793.  
  794.             undoMove
  795.               (
  796.             moves.end[m],
  797.             where,
  798.             undoData
  799.               );
  800.  
  801.           } // end of for loop over each legal move for piece
  802.  
  803.           }
  804.  
  805.     } // end of double for loop over each board position
  806.  
  807.     // only try castling moves if look ahead move than one, since
  808.     // nothing can be captured by doing a castling move
  809.     if (lookAhead > 1)
  810.       {
  811.     castleType = QUEENSIDECASTLE;
  812.     for ( ; ; )
  813.       {
  814.         if (canCastle(castleType, moveColor))
  815.           {
  816.         testMetric.materialDiff = origMaterialDiff;
  817.         castle(castleType, moveColor, undoData);
  818.         helpFindBestMoves
  819.           (
  820.             lookAhead - 1,
  821.             OtherColor(moveColor),
  822.             testMetric,
  823.             (BESTMOVES *) 0
  824.           );
  825.         compareResult = compareMetric
  826.                   (
  827.                     testMetric,
  828.                     metric,
  829.                     metricSet,
  830.                     moveColor
  831.                   );
  832.         if (compareResult >= 0)
  833.           {
  834.             if (compareResult > 0)
  835.               {
  836.             metric = testMetric;
  837.             metricSet = TRUE;
  838.             if (bestMoves)
  839.               bestMoves->nMoves = 0;
  840.               }
  841.             if (bestMoves)
  842.               bestMoves->move[bestMoves->nMoves++] =
  843.             PIECEMOVE(castleType);
  844.           }
  845.         undoCastle(castleType, moveColor, undoData);
  846.           }
  847.         if (castleType == KINGSIDECASTLE)
  848.           break;
  849.         castleType = KINGSIDECASTLE;
  850.       }
  851.  
  852.         // see if the loss of the king is the result of a stalemate
  853.     // instead of check mate
  854.         if (metric.kingSituation[moveColor] == KINGLOST)
  855.       {
  856.         helpFindBestMoves
  857.           (
  858.         1,
  859.         OtherColor(moveColor),
  860.         testMetric,
  861.         (BESTMOVES *) 0
  862.           );
  863.         if (testMetric.kingSituation[moveColor] != KINGLOST)
  864.           // king will be lost on next move, but is not in check
  865.           metric.kingSituation[moveColor] = STALEMATE;
  866.       }
  867.       }
  868.  
  869.     return;
  870.   }
  871.  
  872. // list all legal horizontal moves in one direction from a given starting
  873. // point
  874. LOCAL void horzMoves
  875.   (
  876.     int row,
  877.     int col,
  878.     int delta,
  879.     const BOARD &board,
  880.     POSITIONLIST &moves
  881.   )
  882.   {
  883.     int limit = delta == 1 ? NUMCOLS : -1;
  884.     PIECECOLOR color = board.whatPiece(row, col)->whatColor();
  885.  
  886.     for ( ; ; )
  887.       {
  888.     col += delta;
  889.     if (col == limit)
  890.       return;
  891.     if (board.whatPiece(row, col))
  892.       if (board.whatPiece(row, col)->whatColor() == color)
  893.         return;
  894.     moves.end[moves.nMoves].row = row;
  895.     moves.end[moves.nMoves++].col = col;
  896.     if (board.whatPiece(row, col))
  897.       return;
  898.       }
  899.   }
  900.  
  901. // list all legal vertical moves in one direction from a given starting
  902. // point
  903. LOCAL void vertMoves
  904.   (
  905.     int row,
  906.     int col,
  907.     int delta,
  908.     const BOARD &board,
  909.     POSITIONLIST &moves
  910.   )
  911.   {
  912.     int limit = delta == 1 ? NUMROWS : -1;
  913.     PIECECOLOR color = board.whatPiece(row, col)->whatColor();
  914.  
  915.     for ( ; ; )
  916.       {
  917.     row += delta;
  918.     if (row == limit)
  919.       return;
  920.     if (board.whatPiece(row, col))
  921.       if (board.whatPiece(row, col)->whatColor() == color)
  922.         return;
  923.     moves.end[moves.nMoves].row = row;
  924.     moves.end[moves.nMoves++].col = col;
  925.     if (board.whatPiece(row, col))
  926.       return;
  927.       }
  928.   }
  929.  
  930. // list all legal rook moves from a given starting point
  931. LOCAL void rookMoves
  932.   (
  933.     int row,
  934.     int col,
  935.     const BOARD &board,
  936.     POSITIONLIST &moves
  937.   )
  938.   {
  939.     horzMoves(row, col, 1, board, moves);
  940.     horzMoves(row, col, -1, board, moves);
  941.     vertMoves(row, col, 1, board, moves);
  942.     vertMoves(row, col, -1, board, moves);
  943.  
  944.     return;
  945.   }
  946.  
  947. // list all legal diagonal moves from a given starting point in a
  948. // single direction
  949. LOCAL void diagMoves
  950.   (
  951.     int row,
  952.     int col,
  953.     int rowDelta,
  954.     int colDelta,
  955.     const BOARD &board,
  956.     POSITIONLIST &moves
  957.   )
  958.   {
  959.     int rowLimit = rowDelta == 1 ? NUMROWS : -1;
  960.     int colLimit = colDelta == 1 ? NUMCOLS : -1;
  961.     PIECECOLOR color = board.whatPiece(row, col)->whatColor();
  962.  
  963.     for ( ; ; )
  964.       {
  965.     row += rowDelta;
  966.     col += colDelta;
  967.     if ((row == rowLimit) || (col == colLimit))
  968.       return;
  969.     if (board.whatPiece(row, col))
  970.       if (board.whatPiece(row, col)->whatColor() == color)
  971.         return;
  972.     moves.end[moves.nMoves].row = row;
  973.     moves.end[moves.nMoves++].col = col;
  974.     if (board.whatPiece(row, col))
  975.       return;
  976.       }
  977.   }
  978.  
  979. // list all legal bishop moves from a given starting point
  980. LOCAL void bishopMoves
  981.   (
  982.     int row,
  983.     int col,
  984.     const BOARD &board,
  985.     POSITIONLIST &moves
  986.   )
  987.   {
  988.     diagMoves(row, col, 1, 1, board, moves);
  989.     diagMoves(row, col, 1, -1, board, moves);
  990.     diagMoves(row, col, -1, 1, board, moves);
  991.     diagMoves(row, col, -1, -1, board, moves);
  992.  
  993.     return;
  994.   }
  995.  
  996. // check if a position is within the board
  997. LOCAL BOOL withinBoard
  998.   (
  999.     int row,
  1000.     int col
  1001.   )
  1002.   {
  1003.     return ((0 <= row) && (row < NUMROWS) &&
  1004.             (0 <= col) && (col < NUMCOLS));
  1005.   }
  1006.  
  1007. // row and colomn offsets from a position
  1008. class POSITIONOFFSET
  1009.   {
  1010.   public:
  1011.     int row, col;
  1012.   };
  1013.  
  1014. // list of moves from a given starting position generated by applying
  1015. // a table of position offsets
  1016. LOCAL void movesFromOffsets
  1017.   (
  1018.     int row,
  1019.     int col,
  1020.     int nOffsets,
  1021.     const POSITIONOFFSET *offset,
  1022.     const BOARD &board,
  1023.     POSITIONLIST &moves
  1024.   )
  1025.   {
  1026.     PIECECOLOR color = board.whatPiece(row, col)->whatColor();
  1027.     int i;
  1028.     PIECE *p;
  1029.  
  1030.     for (i = 0; i < nOffsets; i++)
  1031.       {
  1032.     moves.end[moves.nMoves].row = row + offset[i].row;
  1033.     moves.end[moves.nMoves].col = col + offset[i].col;
  1034.     if (withinBoard(moves.end[moves.nMoves].row,
  1035.                 moves.end[moves.nMoves].col))
  1036.       {
  1037.         p = board.whatPiece
  1038.           (
  1039.             moves.end[moves.nMoves].row = row + offset[i].row,
  1040.             moves.end[moves.nMoves].col = col + offset[i].col
  1041.           );
  1042.  
  1043.         if (!p)
  1044.           moves.nMoves++;
  1045.         else if (p->whatColor() != color)
  1046.           moves.nMoves++;
  1047.       }
  1048.       }
  1049.  
  1050.     return;
  1051.   }
  1052.  
  1053. const POSITIONOFFSET kingOffset[] =
  1054.   { { -1, -1 }, { -1, 0 }, { -1, 1 }, { 0, -1}, { 0, 1 },
  1055.     { 1, -1 }, { 1, 0 }, { 1, 1 } };
  1056. const int nKingOffsets = ARRAY_LENGTH(kingOffset);
  1057.  
  1058. const POSITIONOFFSET knightOffset[] =
  1059.   { { 1, 2 }, { 2, 1}, { -1, 2 }, { 2, -1 }, { 1, -2}, { -2, 1 },
  1060.     { -1, -2 }, { -2, -1 } };
  1061. const int nKnightOffsets = ARRAY_LENGTH(knightOffset);
  1062.  
  1063. void PAWN::promote(PIECETYPE promoteType)
  1064.   {
  1065.     switch (promoteType)
  1066.       {
  1067.       case TYPEQUEEN:
  1068.     promotePiece = new QUEEN(whatColor());
  1069.     break;
  1070.  
  1071.       case TYPEROOK:
  1072.     promotePiece = new ROOK(whatColor());
  1073.     break;
  1074.  
  1075.       case TYPEBISHOP:
  1076.     promotePiece = new BISHOP(whatColor());
  1077.     break;
  1078.  
  1079.       case TYPEKNIGHT:
  1080.     promotePiece = new KNIGHT(whatColor());
  1081.     break;
  1082.       }
  1083.  
  1084.     if (!promotePiece)
  1085.       OutOfMemory();
  1086.  
  1087.     return;
  1088.   }
  1089.  
  1090. void PAWN::restoreToPawn(void)
  1091.   {
  1092.     delete promotePiece;
  1093.     promotePiece = (PIECE *) 0;
  1094.  
  1095.     return;
  1096.   }
  1097.  
  1098. void PAWN::legalMoves
  1099.   (
  1100.     POSITION start,
  1101.     const BOARD &board,
  1102.     POSITIONLIST &moves
  1103.   ) const
  1104.   {
  1105.     int delta, limit;
  1106.     POSITION doubleMovedPawn;
  1107.  
  1108.     if (promotePiece)
  1109.       {
  1110.     promotePiece->legalMoves(start, board, moves);
  1111.     return;
  1112.       }
  1113.     
  1114.     if (whatColor() == WHITE)
  1115.       {
  1116.     delta = 1;
  1117.     limit = NUMCOLS;
  1118.       }
  1119.     else
  1120.       {
  1121.     delta = -1;
  1122.     limit = -1;
  1123.       }
  1124.  
  1125.     moves.nMoves = 0;
  1126.  
  1127.     // check if en passant capture possible
  1128.     if (board.lastMoveDoublePawn(doubleMovedPawn))
  1129.       if ((start.col == doubleMovedPawn.col) &&
  1130.       (whatColor() != board.whatPiece(doubleMovedPawn)->whatColor()))
  1131.     {
  1132.       if ((start.row - 1) == doubleMovedPawn.row)
  1133.         {
  1134.           moves.end[moves.nMoves].row = start.row - 1;
  1135.           moves.end[moves.nMoves++].col = start.col + delta;
  1136.         }
  1137.       else if ((start.row + 1) == doubleMovedPawn.row)
  1138.         {
  1139.           moves.end[moves.nMoves].row = start.row + 1;
  1140.           moves.end[moves.nMoves++].col = start.col + delta;
  1141.         }
  1142.     }
  1143.  
  1144.     start.col += delta;
  1145.  
  1146.     if (start.col == limit)
  1147.       return;
  1148.  
  1149.     // check for moves ahead
  1150.     if (!board.whatPiece(start))
  1151.       {
  1152.     moves.end[moves.nMoves++] = start;
  1153.     // check if initial double move possible
  1154.     if (!hasBeenMoved())
  1155.       if (!board.whatPiece(start.row, start.col + delta))
  1156.         {
  1157.           moves.end[moves.nMoves].row = start.row;
  1158.           moves.end[moves.nMoves++].col = start.col + delta;
  1159.         }
  1160.       }
  1161.  
  1162.     // check for captures
  1163.  
  1164.     if (start.row > 0)
  1165.       if (board.whatPiece(start.row - 1, start.col))
  1166.     if (board.whatPiece(start.row - 1, start.col)->whatColor() !=
  1167.         whatColor())
  1168.       {
  1169.         moves.end[moves.nMoves].row = start.row - 1;
  1170.         moves.end[moves.nMoves++].col = start.col;
  1171.       }
  1172.  
  1173.     if (start.row < (NUMROWS - 1))
  1174.       if (board.whatPiece(start.row + 1, start.col))
  1175.     if (board.whatPiece(start.row + 1, start.col)->whatColor() !=
  1176.         whatColor())
  1177.       {
  1178.         moves.end[moves.nMoves].row = start.row + 1;
  1179.         moves.end[moves.nMoves++].col = start.col;
  1180.       }
  1181.  
  1182.     return;
  1183.   }
  1184.  
  1185. void ROOK::legalMoves
  1186.   (
  1187.     POSITION start,
  1188.     const BOARD &board,
  1189.     POSITIONLIST &moves
  1190.   ) const
  1191.   {
  1192.     moves.nMoves = 0;
  1193.     rookMoves(start.row, start.col, board, moves);
  1194.  
  1195.     return;
  1196.   }
  1197.  
  1198. void KNIGHT::legalMoves
  1199.   (
  1200.     POSITION start,
  1201.     const BOARD &board,
  1202.     POSITIONLIST &moves
  1203.   ) const
  1204.   {
  1205.     moves.nMoves = 0;
  1206.     movesFromOffsets(start.row, start.col, nKnightOffsets, knightOffset,
  1207.                      board, moves);
  1208.  
  1209.     return;
  1210.   }
  1211.  
  1212. void BISHOP::legalMoves
  1213.   (
  1214.     POSITION start,
  1215.     const BOARD &board,
  1216.     POSITIONLIST &moves
  1217.   ) const
  1218.   {
  1219.     moves.nMoves = 0;
  1220.     bishopMoves(start.row, start.col, board, moves);
  1221.  
  1222.     return;
  1223.   }
  1224.  
  1225. void QUEEN::legalMoves
  1226.   (
  1227.     POSITION start,
  1228.     const BOARD &board,
  1229.     POSITIONLIST &moves
  1230.   ) const
  1231.   {
  1232.     moves.nMoves = 0;
  1233.     rookMoves(start.row, start.col, board, moves);
  1234.     bishopMoves(start.row, start.col, board, moves);
  1235.  
  1236.     return;
  1237.   }
  1238.  
  1239. void KING::legalMoves
  1240.   (
  1241.     POSITION start,
  1242.     const BOARD &board,
  1243.     POSITIONLIST &moves
  1244.   ) const
  1245.   {
  1246.     moves.nMoves = 0;
  1247.     movesFromOffsets(start.row, start.col, nKingOffsets, kingOffset,
  1248.                      board, moves);
  1249.  
  1250.     return;
  1251.   }
  1252.