src/movesup.c

   1 /**
   2
   3 Copyright (c) Scott Gasch
   4
   5 Module Name:
   6
   7     movesup.c
   8
   9 Abstract:
  10
  11     Functions to support MakeMove and UnmakeMove along with some other
  12     miscellanious move support functions.
  13
  14 Author:
  15
  16     Scott Gasch ([email protected]) 13 May 2004
  17
  18 Revision History:
  19
  20     $Id: movesup.c 345 2007-12-02 22:56:42Z scott $
  21
  22 **/
  23
  24 #include "chess.h"
  25
  26 COOR
  27 FasterExposesCheck(POSITION *pos,
  28                    COOR cRemove,
  29                    COOR cLocation)
  30 /**
  31
  32 Routine description:
  33
  34     This is just like ExposesCheck (see below) but it does not bother
  35     checking whether its possible to expose check with the piece at
  36     cRemove because we already know it is.
  37
  38 Parameters:
  39
  40     POSITION *pos,
  41     COOR cRemove,
  42     COOR cLocation
  43
  44 Return value:
  45
  46     COOR
  47
  48 **/
  49 {
  50     register int iDelta;
  51     register COOR cBlockIndex;
  52     int iIndex;
  53     PIECE xPiece;
  54     ULONG uColor = GET_COLOR(pos->rgSquare[cLocation].pPiece);
  55
  56     ASSERT(IS_KING(pos->rgSquare[cLocation].pPiece));
  57     iIndex = (int)cLocation - (int)cRemove;
  58
  59     ASSERT(IS_ON_BOARD(cRemove));
  60     ASSERT(IS_ON_BOARD(cLocation));
  61     ASSERT(!IS_EMPTY(pos->rgSquare[cLocation].pPiece));
  62     ASSERT(0 != (CHECK_VECTOR_WITH_INDEX(iIndex, BLACK) & (1 << QUEEN)));
  63
  64     iDelta = CHECK_DELTA_WITH_INDEX(iIndex);
  65     ASSERT(iDelta != 0);
  66
  67     for (cBlockIndex = cRemove + iDelta;
  68          IS_ON_BOARD(cBlockIndex);
  69          cBlockIndex += iDelta)
  70     {
  71         ASSERT(cBlockIndex != cRemove);
  72         ASSERT(cBlockIndex != cLocation);
  73         xPiece = pos->rgSquare[cBlockIndex].pPiece;
  74         if (!IS_EMPTY(xPiece))
  75         {
  76             //
  77             // Is it an enemy?
  78             //
  79             if (OPPOSITE_COLORS(xPiece, uColor))
  80             {
  81                 //
  82                 // Does it move the right way to attack?
  83                 //
  84                 iIndex = (int)cBlockIndex - (int)cLocation;
  85                 if (0 != (CHECK_VECTOR_WITH_INDEX(iIndex, WHITE) &
  86                           (1 << (PIECE_TYPE(xPiece)))))
  87                 {
  88                     return(cBlockIndex);
  89                 }
  90             }
  91
  92             //
  93             // Either we found another friendly piece or an enemy piece
  94             // that was unable to reach us.  Either way we are safe.
  95             //
  96             return(ILLEGAL_COOR);
  97         }
  98     }
  99
 100     //
 101     // We fell off the board without seeing another piece.
 102     //
 103     return(ILLEGAL_COOR);
 104 }
 105
 106
 107
 108 COOR
 109 ExposesCheck(POSITION *pos,
 110              COOR cRemove,
 111              COOR cLocation)
 112 /**
 113
 114 Routine description:
 115
 116     Test if removing the piece at cRemove exposes the piece at
 117     cLocation to attack by the other side.  Note: there must be a
 118     piece at cLocation because the color of that piece is used to
 119     determine what side is "checking" and what side is "being
 120     checked".
 121
 122 Parameters:
 123
 124     POSITION *pos : the board
 125     COOR cRemove : the square where a piece hypothetically removed from
 126     COOR cLocation : the square where the attackee is sitting
 127
 128 Return value:
 129
 130     COOR : the location of an attacker piece or 0x88 (!IS_ON_BOARD) if
 131            the removal of cRemove does not expose check.
 132
 133 **/
 134 {
 135     register int iDelta;
 136     register COOR cBlockIndex;
 137     int iIndex;
 138     PIECE xPiece;
 139
 140     ASSERT(IS_ON_BOARD(cRemove));
 141     ASSERT(IS_ON_BOARD(cLocation));
 142     ASSERT(!IS_EMPTY(pos->rgSquare[cLocation].pPiece));
 143
 144     iIndex = (int)cLocation - (int)cRemove;
 145
 146     //
 147     // If there is no way for a queen sitting at the square removed to
 148     // reach the square we are testing (i.e. the two squares are not
 149     // on the same rank, file, or diagonal) then there is no way
 150     // removing it can expose cLocation to check.
 151     //
 152     if (0 == (CHECK_VECTOR_WITH_INDEX(iIndex, BLACK) & (1 << QUEEN)))
 153     {
 154         return(ILLEGAL_COOR);
 155     }
 156     iDelta = CHECK_DELTA_WITH_INDEX(iIndex);
 157     for (cBlockIndex = cLocation + iDelta;
 158          IS_ON_BOARD(cBlockIndex);
 159          cBlockIndex += iDelta)
 160     {
 161         if (cBlockIndex == cRemove)
 162         {
 163             continue;
 164         }
 165         xPiece = pos->rgSquare[cBlockIndex].pPiece;
 166         if (!IS_EMPTY(xPiece))
 167         {
 168             //
 169             // Is it an enemy?
 170             //
 171             if (OPPOSITE_COLORS(xPiece, pos->rgSquare[cLocation].pPiece))
 172             {
 173                 //
 174                 // Does it move the right way to attack?
 175                 //
 176                 iIndex = (int)cBlockIndex - (int)cLocation;
 177                 if (0 != (CHECK_VECTOR_WITH_INDEX(iIndex, GET_COLOR(xPiece)) &
 178                           (1 << (PIECE_TYPE(xPiece)))))
 179                 {
 180                     return(cBlockIndex);
 181                 }
 182             }
 183
 184             //
 185             // Either we found another friendly piece or an enemy piece
 186             // that was unable to reach us.  Either way we are safe.
 187             //
 188             return(ILLEGAL_COOR);
 189         }
 190     }
 191
 192     //
 193     // We fell off the board without seeing another piece.
 194     //
 195     return(ILLEGAL_COOR);
 196 }
 197
 198
 199 COOR
 200 ExposesCheckEp(POSITION *pos,
 201                COOR cTest,
 202                COOR cIgnore,
 203                COOR cBlock,
 204                COOR cKing)
 205 /**
 206
 207 Routine description:
 208
 209 Parameters:
 210
 211     POSITION *pos,
 212     COOR cTest : The square from whence the attack comes
 213     COOR cIgnore : Ignore this square, the pawn moved
 214     COOR cBlock : This square is where the pawn moved to and now blocks
 215     COOR cKing : The square under attack
 216
 217 Return value:
 218
 219     COOR
 220
 221 **/
 222 {
 223     register int iDelta;
 224     register COOR cBlockIndex;
 225     int iIndex;
 226     PIECE xPiece;
 227
 228     ASSERT(IS_ON_BOARD(cTest));
 229     ASSERT(IS_ON_BOARD(cIgnore));
 230     ASSERT(IS_ON_BOARD(cBlock));
 231     ASSERT(IS_ON_BOARD(cKing));
 232
 233     iIndex = (int)cKing - (int)cTest;
 234
 235     //
 236     // If there is no way for a queen sitting at the square removed to
 237     // reach the square we are testing (i.e. the two squares are not
 238     // on the same rank, file, or diagonal) then no problemo.
 239     //
 240     if (0 == (CHECK_VECTOR_WITH_INDEX(iIndex, BLACK) & (1 << QUEEN)))
 241     {
 242         return(ILLEGAL_COOR);
 243     }
 244
 245     iDelta = CHECK_DELTA_WITH_INDEX(iIndex);
 246     for (cBlockIndex = cKing + iDelta;
 247          IS_ON_BOARD(cBlockIndex);
 248          cBlockIndex += iDelta)
 249     {
 250         if (cBlockIndex == cTest) continue;
 251         if (cBlockIndex == cIgnore) continue;
 252         if (cBlockIndex == cBlock) return(ILLEGAL_COOR);
 253
 254         xPiece = pos->rgSquare[cBlockIndex].pPiece;
 255         if (!IS_EMPTY(xPiece))
 256         {
 257             if (OPPOSITE_COLORS(xPiece, pos->rgSquare[cKing].pPiece))
 258             {
 259                 //
 260                 // Does it move the right way to attack?
 261                 //
 262                 iIndex = (int)cBlockIndex - (int)cKing;
 263                 if (0 != (CHECK_VECTOR_WITH_INDEX(iIndex, GET_COLOR(xPiece)) &
 264                           (1 << (PIECE_TYPE(xPiece)))))
 265                 {
 266                     return(cBlockIndex);
 267                 }
 268             }
 269
 270             //
 271             // Either we found another friendly piece or an enemy piece
 272             // that was unable to reach us.  Either way we are safe.
 273             //
 274             return(ILLEGAL_COOR);
 275         }
 276     }
 277
 278     //
 279     // We fell off the board without seeing another piece.
 280     //
 281     return(ILLEGAL_COOR);
 282 }
 283
 284
 285 FLAG
 286 IsAttacked(COOR cTest, POSITION *pos, ULONG uSide)
 287 /**
 288
 289 Routine description:
 290
 291     Determine whether the square cTest is attacked by the side uSide.
 292
 293 Parameters:
 294
 295     COOR cTest : the square we want to determine if is under attack
 296     POSITION *pos : the board
 297     ULONG uSide : the side we want to see if is attacking cTest
 298
 299 Return value:
 300
 301     FLAG : TRUE if uSide attacks cTest, FALSE otherwise
 302
 303 **/
 304 {
 305     ULONG u;
 306     PIECE pPiece;
 307     COOR cLocation;
 308     COOR cBlockIndex;
 309     int iIndex;
 310     int iDelta;
 311     static int iPawnLoc[2] = { -17, +15 };
 312     static PIECE pPawn[2] = { BLACK_PAWN, WHITE_PAWN };
 313
 314     ASSERT(IS_ON_BOARD(cTest));
 315     ASSERT(IS_VALID_COLOR(uSide));
 316     ASSERT((pos->uNonPawnCount[uSide][0] - 1) < 16);
 317
 318     //
 319     // Begin at the end because the king is the 0th item in the list and
 320     // we want to consider king moves last.
 321     //
 322     for (u = pos->uNonPawnCount[uSide][0] - 1;
 323          u != (ULONG)-1;
 324          u--)
 325     {
 326         cLocation = pos->cNonPawns[uSide][u];
 327         ASSERT(IS_ON_BOARD(cLocation));
 328         pPiece = pos->rgSquare[cLocation].pPiece;
 329         ASSERT(!IS_EMPTY(pPiece));
 330         ASSERT(!IS_PAWN(pPiece));
 331         ASSERT(GET_COLOR(pPiece) == uSide);
 332         iIndex = (int)cLocation - (int)cTest;
 333
 334         if (!(CHECK_VECTOR_WITH_INDEX(iIndex, uSide) &
 335               (1 << (PIECE_TYPE(pPiece)))))
 336         {
 337             continue;
 338         }
 339
 340         //
 341         // These pieces do not slide, we don't need to look for
 342         // blockers.  If they can get there then there is nothing
 343         // we can do to stop them.
 344         //
 345         if (IS_KNIGHT(pPiece) || IS_KING(pPiece))
 346         {
 347             return(TRUE);
 348         }
 349
 350         //
 351         // Well, here we have a sliding piece (bishop, rook or queen)
 352         // that is on the same line (file, rank or diagonal) as the
 353         // cTest.  We now have to see if the attacker (pPiece) is
 354         // blocked or is free to attack cTest.
 355         //
 356         iDelta = NEG_DELTA_WITH_INDEX(iIndex);
 357         for (cBlockIndex = cTest + iDelta;
 358              cBlockIndex != cLocation;
 359              cBlockIndex += iDelta)
 360         {
 361             if (!IS_EMPTY(pos->rgSquare[cBlockIndex].pPiece))
 362             {
 363                 break;
 364             }
 365         }
 366         if (cBlockIndex == cLocation)
 367         {
 368             return(TRUE);
 369         }
 370     }
 371
 372     //
 373     // Check the locations a pawn could attack cTest from.
 374     //
 375     cLocation = cTest + iPawnLoc[uSide];
 376     if (IS_ON_BOARD(cLocation) &&
 377         (pos->rgSquare[cLocation].pPiece == pPawn[uSide]))
 378     {
 379         return(TRUE);
 380     }
 381
 382     cLocation += 2;
 383     if (IS_ON_BOARD(cLocation) &&
 384         (pos->rgSquare[cLocation].pPiece == pPawn[uSide]))
 385     {
 386         return(TRUE);
 387     }
 388     return(FALSE);
 389 }
 390
 391
 392 FLAG
 393 InCheck(POSITION *pos, ULONG uSide)
 394 /**
 395
 396 Routine description:
 397
 398     Determine if a side is in check or not.
 399
 400 Parameters:
 401
 402     POSITION *pos : the board
 403     ULONG uSide : the side we want to determine if is in check
 404
 405 Return value:
 406
 407     FLAG : TRUE if side is in check, FALSE otherwise.
 408
 409 **/
 410 {
 411     COOR cKingLoc;
 412 #ifdef DEBUG
 413     PIECE pKing;
 414 #endif
 415
 416     ASSERT(IS_VALID_COLOR(uSide));
 417
 418     cKingLoc = pos->cNonPawns[uSide][0];
 419 #ifdef DEBUG
 420     pKing = pos->rgSquare[cKingLoc].pPiece;
 421     ASSERT(IS_KING(pKing));
 422     ASSERT(IS_VALID_COLOR(uSide));
 423     ASSERT(GET_COLOR(pKing) == uSide);
 424 #endif
 425     return(IsAttacked(cKingLoc, pos, FLIP(uSide)));
 426 }
 427
 428
 429 static FLAG
 430 _SanityCheckPawnMove(POSITION *pos, MOVE mv)
 431 /**
 432
 433 Routine description:
 434
 435 Parameters:
 436
 437     POSITION *pos,
 438     MOVE mv
 439
 440 Return value:
 441
 442     FLAG
 443
 444 **/
 445 {
 446     PIECE p = mv.pMoved;
 447     COOR cFrom = mv.cFrom;
 448     COOR cTo = mv.cTo;
 449
 450     ASSERT(mv.uMove);
 451     ASSERT(IS_PAWN(p));
 452
 453     //
 454     // General sanity checking...
 455     //
 456     if (!IS_ON_BOARD(cFrom) || !IS_ON_BOARD(cTo))
 457     {
 458         return(FALSE);
 459     }
 460
 461     //
 462     // Sanity check promotions.
 463     //
 464     if (mv.pPromoted)
 465     {
 466         if (GET_COLOR(p) == WHITE)
 467         {
 468             if ((RANK(cTo) != 8) && (RANK(cFrom) != 7)) return(FALSE);
 469         }
 470         else
 471         {
 472             if ((RANK(cTo) != 1) && (RANK(cFrom) != 2)) return(FALSE);
 473         }
 474
 475         if (!IS_KNIGHT(mv.pPromoted) &&
 476             !IS_BISHOP(mv.pPromoted) &&
 477             !IS_ROOK(mv.pPromoted) &&
 478             !IS_QUEEN(mv.pPromoted))
 479         {
 480             return(FALSE);
 481         }
 482     }
 483
 484     //
 485     // Handle capture moves.
 486     //
 487     if (mv.pCaptured)
 488     {
 489         //
 490         // Must be capturing something
 491         //
 492         if (IS_SPECIAL_MOVE(mv) && (!mv.pPromoted))
 493         {
 494             //
 495             // en passant
 496             //
 497             if (!IS_EMPTY(pos->rgSquare[cTo].pPiece)) return(FALSE);
 498         }
 499         else
 500         {
 501             //
 502             // normal capture
 503             //
 504             if (IS_EMPTY(pos->rgSquare[cTo].pPiece)) return(FALSE);
 505             if (!OPPOSITE_COLORS(mv.pMoved, mv.pCaptured)) return(FALSE);
 506         }
 507
 508         //
 509         // Must be in the capturing position.
 510         //
 511         if (WHITE == GET_COLOR(p))
 512         {
 513             if (((cFrom - 17) != cTo) && ((cFrom - 15) != cTo)) return(FALSE);
 514         }
 515         else
 516         {
 517             if (((cFrom + 17) != cTo) && ((cFrom + 15) != cTo)) return(FALSE);
 518         }
 519
 520         if ((IS_SPECIAL_MOVE(mv)) &&
 521             (!mv.pPromoted) &&
 522             (pos->cEpSquare != cTo)) return(FALSE);
 523         return(TRUE);
 524     }
 525     else
 526     {
 527         //
 528         // If the pawn is not capturing, the TO square better be empty.
 529         //
 530         if (!IS_EMPTY(pos->rgSquare[cTo].pPiece)) return(FALSE);
 531
 532         //
 533         // A non-capturing pawn can only push forward.  One or two squares
 534         // based on whether or not its the initial move.
 535         //
 536         if (WHITE == GET_COLOR(p))
 537         {
 538             if (cTo == cFrom - 16) return(TRUE);
 539             if ((cTo == cFrom - 32) &&
 540                 (RANK2(cFrom)) &&
 541                 (IS_EMPTY(pos->rgSquare[cFrom - 16].pPiece))) return(TRUE);
 542         }
 543         else
 544         {
 545             if (cTo == cFrom + 16) return(TRUE);
 546             if ((cTo == cFrom + 32) &&
 547                 (RANK7(cFrom)) &&
 548                 (IS_EMPTY(pos->rgSquare[cFrom + 16].pPiece))) return(TRUE);
 549         }
 550     }
 551     return(FALSE);
 552 }
 553
 554
 555 static FLAG
 556 _SanityCheckPieceMove(POSITION *pos, MOVE mv)
 557 /**
 558
 559 Routine description:
 560
 561 Parameters:
 562
 563     POSITION *pos,
 564     MOVE mv
 565
 566 Return value:
 567
 568     static
 569
 570 **/
 571 {
 572     PIECE p = mv.pMoved;
 573     PIECE pPieceType = p >> 1;
 574     int iIndex;
 575     COOR cFrom = mv.cFrom;
 576     COOR cTo = mv.cTo;
 577     COOR cBlock;
 578     COOR cAttack;
 579     COOR cKing;
 580     int iDelta;
 581
 582     ASSERT(!IS_PAWN(p));
 583
 584     //
 585     // Handle castling
 586     //
 587     if (IS_CASTLE(mv))
 588     {
 589         ASSERT(IS_KING(mv.pMoved));
 590         ASSERT(IS_SPECIAL_MOVE(mv));
 591         return(TRUE);
 592     }
 593
 594     //
 595     // Make sure the piece moves in the way the move describes.
 596     //
 597     iIndex = (int)cFrom - (int)cTo;
 598     if (0 == (CHECK_VECTOR_WITH_INDEX(iIndex, BLACK) &
 599               (1 << pPieceType)))
 600     {
 601         return(FALSE);
 602     }
 603
 604     //
 605     // If we get here the piece can move in the way described by the
 606     // move but we still have to check to see if there are any other
 607     // pieces in the way if the piece moved is not a king or knight
 608     // (pawns handled in their own routine, see above).
 609     //
 610     if ((pPieceType == QUEEN) ||
 611         (pPieceType == ROOK) ||
 612         (pPieceType == BISHOP))
 613     {
 614         iDelta = CHECK_DELTA_WITH_INDEX(iIndex);
 615         for (cBlock = cFrom + iDelta;
 616              cBlock != cTo;
 617              cBlock += iDelta)
 618         {
 619             if (!IS_EMPTY(pos->rgSquare[cBlock].pPiece))
 620             {
 621                 break;
 622             }
 623         }
 624         if (cBlock != cTo) return(FALSE);
 625     }
 626
 627     //
 628     // Ok the piece can move the way they asked and there are no other
 629     // pieces in the way... but it cannot expose its own king to check
 630     // by doing so!
 631     //
 632     cKing = pos->cNonPawns[pos->uToMove][0];
 633     cAttack = ExposesCheck(pos,
 634                            cFrom,
 635                            cKing);
 636     if ((ILLEGAL_COOR != cAttack) && (cTo != cAttack))
 637     {
 638         //
 639         // Ok if we are here then removing this piece from the from square
 640         // does expose the king to check and the move does not capture the
 641         // checking piece.  But it's still ok as long as the TO location
 642         // still blocks the checking piece.
 643         //
 644         iIndex = cAttack - cKing;
 645         iDelta = CHECK_DELTA_WITH_INDEX(iIndex);
 646         for (cBlock = cAttack + iDelta;
 647              cBlock != cKing;
 648              cBlock += iDelta)
 649         {
 650             if ((cBlock == cTo) ||
 651                 !IS_EMPTY(pos->rgSquare[cBlock].pPiece)) break;
 652         }
 653         if (cBlock == cKing) return(FALSE);
 654     }
 655
 656     //
 657     // Legal!
 658     //
 659     return(TRUE);
 660 }
 661
 662
 663 FLAG
 664 SanityCheckMove(POSITION *pos, MOVE mv)
 665 /**
 666
 667 Routine description:
 668
 669     Sanity check a move -- Note: Not a strict chess legality checker!
 670
 671 Parameters:
 672
 673     POSITION *pos,
 674     MOVE mv
 675
 676 Return value:
 677
 678     FLAG
 679
 680 **/
 681 {
 682     register PIECE p = mv.pMoved;
 683
 684     if (0 == mv.uMove)
 685     {
 686         return(FALSE);
 687     }
 688     else if (mv.cTo == mv.cFrom)
 689     {
 690         return(FALSE);
 691     }
 692     else if (IS_EMPTY(pos->rgSquare[mv.cFrom].pPiece))
 693     {
 694         return(FALSE);
 695     }
 696     else if (GET_COLOR(mv.pMoved) != pos->uToMove)
 697     {
 698         return(FALSE);
 699     }
 700     else if ((!IS_EMPTY(pos->rgSquare[mv.cTo].pPiece)) &&
 701              (0 == mv.pCaptured))
 702     {
 703         return(FALSE);
 704     }
 705
 706     if (!IS_SPECIAL_MOVE(mv))
 707     {
 708         if (mv.pCaptured)
 709         {
 710             if (IS_EMPTY(pos->rgSquare[mv.cTo].pPiece))
 711             {
 712                 return(FALSE);
 713             }
 714
 715             if (((pos->rgSquare[mv.cTo].pPiece) != mv.pCaptured) ||
 716                 (!OPPOSITE_COLORS(mv.pCaptured, mv.pMoved)))
 717             {
 718                 return(FALSE);
 719             }
 720         }
 721
 722         if (!IS_EMPTY(pos->rgSquare[mv.cTo].pPiece) &&
 723             !mv.pCaptured)
 724         {
 725             return(FALSE);
 726         }
 727     }
 728     else
 729     {
 730         if (!IS_PAWN(p) && !IS_KING(p))
 731         {
 732             return(FALSE);
 733         }
 734     }
 735
 736     if (IS_PAWN(p))
 737     {
 738         return(_SanityCheckPawnMove(pos, mv));
 739     }
 740     else
 741     {
 742         return(_SanityCheckPieceMove(pos, mv));
 743     }
 744 }
 745
 746
 747 FLAG
 748 LooksLikeFile(CHAR c)
 749 /**
 750
 751 Routine description:
 752
 753     Does some char look like a file (i.e. 'a' <= char <= 'h')
 754
 755 Parameters:
 756
 757     CHAR c
 758
 759 Return value:
 760
 761     FLAG
 762
 763 **/
 764 {
 765     if ((toupper(c) >= 'A') &&
 766         (toupper(c) <= 'H'))
 767     {
 768         return(TRUE);
 769     }
 770     return(FALSE);
 771 }
 772
 773 FLAG LooksLikeRank(CHAR c)
 774 /**
 775
 776 Routine description:
 777
 778     Does char look like a coor rank (i.e. '1' <= char <= '8')
 779
 780 Parameters:
 781
 782     CHAR c
 783
 784 Return value:
 785
 786     FLAG
 787
 788 **/
 789 {
 790     if (((c - '0') >= 1) &&
 791         ((c - '0') <= 8))
 792     {
 793         return(TRUE);
 794     }
 795     return(FALSE);
 796 }
 797
 798
 799 FLAG
 800 LooksLikeCoor(char *szData)
 801 /**
 802
 803 Routine description:
 804
 805     Do the first two chars in szData look like a file/rank?
 806
 807 Parameters:
 808
 809     char *szData
 810
 811 Return value:
 812
 813     FLAG
 814
 815 **/
 816 {
 817     char f = szData[0];
 818     char r = szData[1];
 819
 820     if (LooksLikeFile(f) &&
 821         LooksLikeRank(r))
 822     {
 823         return(TRUE);
 824     }
 825     return(FALSE);
 826 }
 827
 828
 829 CHAR *
 830 StripMove(CHAR *szMove)
 831 /**
 832
 833 Routine description:
 834
 835     Strip decoration punctuation marks out of a move.
 836
 837 Parameters:
 838
 839     CHAR *szMove
 840
 841 Return value:
 842
 843     CHAR
 844
 845 **/
 846 {
 847     CHAR cIgnore[] = "?!x+#-=\r\n";            // chars stripped from szMove
 848     static CHAR szStripped[10];
 849     ULONG y;
 850     CHAR *p;
 851
 852     memset(szStripped, 0, sizeof(szStripped));
 853     p = szMove;
 854     y = 0;
 855     while (*p != '\0')
 856     {
 857         if (NULL == strchr(cIgnore, *p))
 858         {
 859             szStripped[y++] = *p;
 860             if (y >= 8) break;
 861         }
 862         p++;
 863     }
 864     return(szStripped);
 865 }
 866
 867 ULONG LooksLikeMove(char *szData)
 868 /**
 869
 870 Routine description:
 871
 872     Does some char pointer point at some text that looks like a move?
 873     If so, does the move look like SAN or ICS style?
 874
 875 Parameters:
 876
 877     char *szData
 878
 879 Return value:
 880
 881     ULONG
 882
 883 **/
 884 {
 885     CHAR *szStripped = StripMove(szData);
 886     ULONG u;
 887     static CHAR cPieces[] = { 'P', 'N', 'B', 'R', 'Q', 'K', '\0' };
 888
 889     //
 890     // A (stripped) move must be at least two characters long even in
 891     // SAN.
 892     //
 893     if ((strlen(szStripped) < 2) || (strlen(szStripped) > 7))
 894     {
 895         return(NOT_MOVE);
 896     }
 897
 898     //
 899     // O-O, O-O-O
 900     //
 901     if (!STRNCMPI(szStripped, "OOO", 3) ||
 902         !STRNCMPI(szStripped, "OO", 2) ||
 903         !STRNCMPI(szStripped, "00", 2) ||      // duh
 904         !STRNCMPI(szStripped, "000", 3))
 905     {
 906         return(MOVE_SAN);
 907     }
 908
 909     //
 910     // COOR COOR (d2d4)
 911     //
 912     if (LooksLikeCoor(szStripped) &&
 913         LooksLikeCoor(szStripped + 2))
 914     {
 915         return(MOVE_ICS);
 916     }
 917
 918     //
 919     // COOR (d4)
 920     //
 921     if (LooksLikeCoor(szStripped) &&
 922         strlen(szStripped) == 2)
 923     {
 924         return(MOVE_SAN);
 925     }
 926
 927     //
 928     // RANK COOR
 929     //
 930     if ((LooksLikeRank(szStripped[0]) ||
 931          LooksLikeFile(szStripped[0])) &&
 932         LooksLikeCoor(&szStripped[1]))
 933     {
 934         return(MOVE_SAN);
 935     }
 936
 937     //
 938     // PIECE COOR COOR
 939     // PIECE COOR
 940     // PIECE FILE COOR
 941     // PIECE RANK COOR
 942     //
 943     for (u = 0; u < ARRAY_LENGTH(cPieces); u++)
 944     {
 945         if (szStripped[0] == cPieces[u])    // must be uppercase!
 946         {
 947             if (LooksLikeCoor(&szStripped[1]))
 948             {
 949                 return(MOVE_SAN);
 950             }
 951             if (LooksLikeFile(szStripped[1]) &&
 952                 LooksLikeCoor(&szStripped[2]))
 953             {
 954                 return(MOVE_SAN);
 955             }
 956             if (LooksLikeRank(szStripped[1]) &&
 957                 LooksLikeCoor(&szStripped[2]))
 958             {
 959                 return(MOVE_SAN);
 960             }
 961         }
 962     }
 963
 964     //
 965     // (COORD)=(PIECE)
 966     //
 967     if ((strlen(szStripped) == 4) &&
 968         LooksLikeCoor(szStripped) &&
 969         szStripped[2] == '=')
 970     {
 971         if (NULL != strchr(cPieces, szStripped[3]))
 972         {
 973             return(MOVE_SAN);
 974         }
 975     }
 976
 977     //
 978     // (COOR)(PIECE)
 979     //
 980     if ((strlen(szStripped) == 3) &&
 981         LooksLikeCoor(szStripped) &&
 982         (NULL != strchr(cPieces, szStripped[2])))
 983     {
 984         return(MOVE_SAN);
 985     }
 986
 987     return(NOT_MOVE);
 988 }
 989
 990
 991 void FASTCALL
 992 SelectBestWithHistory(SEARCHER_THREAD_CONTEXT *ctx,
 993                       ULONG u)
 994 /**
 995
 996 Routine description:
 997
 998     Pick the best (i.e. move with the highest "score" assigned to it
 999     at generation time) that has not been played yet this ply and move
1000     it to the front of the move list to be played next.
1001
1002 Parameters:
1003
1004     SEARCHER_THREAD_CONTEXT *ctx,
1005     ULONG u
1006
1007 Return value:
1008
1009     void FASTCALL
1010
1011 **/
1012 {
1013     register ULONG v;
1014     register ULONG uEnd = ctx->sMoveStack.uEnd[ctx->uPly];
1015     register SCORE iBestVal;
1016     ULONG uLoc;
1017     SCORE iVal;
1018     MOVE mv;
1019     MOVE_STACK_MOVE_VALUE_FLAGS mvfTemp;
1020
1021     ASSERT(ctx->sMoveStack.uBegin[ctx->uPly] <= uEnd);
1022     ASSERT(u >= ctx->sMoveStack.uBegin[ctx->uPly]);
1023     ASSERT(u < uEnd);
1024
1025     //
1026     // Linear search from u..ctx->sMoveStack.uEnd[ctx->uPly] for the
1027     // move with the best value.
1028     //
1029     iBestVal = ctx->sMoveStack.mvf[u].iValue;
1030     mv = ctx->sMoveStack.mvf[u].mv;
1031     if (!IS_CAPTURE_OR_PROMOTION(mv))
1032     {
1033         iBestVal += g_HistoryCounters[mv.pMoved][mv.cTo];
1034     }
1035     uLoc = u;
1036
1037     for (v = u + 1; v < uEnd; v++)
1038     {
1039         iVal = ctx->sMoveStack.mvf[v].iValue;
1040         mv = ctx->sMoveStack.mvf[v].mv;
1041         if (!IS_CAPTURE_OR_PROMOTION(mv))
1042         {
1043             iVal += g_HistoryCounters[mv.pMoved][mv.cTo];
1044         }
1045         if (iVal > iBestVal)
1046         {
1047             iBestVal = iVal;
1048             uLoc = v;
1049         }
1050     }
1051
1052     //
1053     // Note: the if here slows down the code, just swap em.
1054     //
1055     mvfTemp = ctx->sMoveStack.mvf[u];
1056     ctx->sMoveStack.mvf[u] = ctx->sMoveStack.mvf[uLoc];
1057     ctx->sMoveStack.mvf[uLoc] = mvfTemp;
1058 }
1059
1060
1061 void FASTCALL
1062 SelectBestNoHistory(SEARCHER_THREAD_CONTEXT *ctx,
1063                     ULONG u)
1064 /**
1065
1066 Routine description:
1067
1068     Pick the best (i.e. move with the highest "score" assigned to it
1069     at generation time) that has not been played yet this ply and move
1070     it to the front of the move list to be played next.
1071
1072 Parameters:
1073
1074     SEARCHER_THREAD_CONTEXT *ctx,
1075     ULONG u
1076
1077 Return value:
1078
1079     void FASTCALL
1080
1081 **/
1082 {
1083     register ULONG v;
1084     register ULONG uEnd = ctx->sMoveStack.uEnd[ctx->uPly];
1085     register SCORE iBestVal;
1086     ULONG uLoc;
1087     SCORE iVal;
1088     MOVE_STACK_MOVE_VALUE_FLAGS mvfTemp;
1089
1090     ASSERT(ctx->sMoveStack.uBegin[ctx->uPly] <= uEnd);
1091     ASSERT(u >= ctx->sMoveStack.uBegin[ctx->uPly]);
1092     ASSERT(u < uEnd);
1093
1094     //
1095     // Linear search from u..ctx->sMoveStack.uEnd[ctx->uPly] for the
1096     // move with the best value.
1097     //
1098     iBestVal = ctx->sMoveStack.mvf[u].iValue;
1099     uLoc = u;
1100     for (v = u + 1; v < uEnd; v++)
1101     {
1102         iVal = ctx->sMoveStack.mvf[v].iValue;
1103         if (iVal > iBestVal)
1104         {
1105             iBestVal = iVal;
1106             uLoc = v;
1107         }
1108     }
1109
1110     //
1111     // Note: the if here slows down the code, just swap em.
1112     //
1113     mvfTemp = ctx->sMoveStack.mvf[u];
1114     ctx->sMoveStack.mvf[u] = ctx->sMoveStack.mvf[uLoc];
1115     ctx->sMoveStack.mvf[uLoc] = mvfTemp;
1116 }
1117
1118 void FASTCALL
1119 SelectMoveAtRoot(SEARCHER_THREAD_CONTEXT *ctx,
1120                  ULONG u)
1121 /**
1122
1123 Routine description:
1124
1125 Parameters:
1126
1127     SEARCHER_THREAD_CONTEXT *ctx,
1128     ULONG u
1129
1130 Return value:
1131
1132     void FASTCALL
1133
1134 **/
1135 {
1136     ULONG v = u;
1137     ULONG uEnd = ctx->sMoveStack.uEnd[ctx->uPly];
1138     SCORE iBestVal = -INFINITY;
1139     ULONG uLoc = v;
1140     SCORE iVal;
1141     MOVE_STACK_MOVE_VALUE_FLAGS mvfTemp;
1142
1143     ASSERT(ctx->sMoveStack.uBegin[ctx->uPly] <= uEnd);
1144     ASSERT(u >= ctx->sMoveStack.uBegin[ctx->uPly]);
1145     ASSERT(u < uEnd);
1146     ASSERT(MOVE_COUNT(ctx, ctx->uPly) >= 1);
1147
1148     //
1149     // Find the first move that we have not already searched.  It will
1150     // provide our initial iBestVal.
1151     //
1152     do
1153     {
1154         if (!(ctx->sMoveStack.mvf[v].bvFlags & MVF_MOVE_SEARCHED))
1155         {
1156             iBestVal = ctx->sMoveStack.mvf[v].iValue;
1157             uLoc = v;
1158             break;
1159         }
1160         v++;
1161     }
1162     while(v < uEnd);
1163     if (v >= uEnd) return;
1164
1165     //
1166     // Search the rest of the moves that have not yet been tried by
1167     // RootSearch and find the one with the best value.
1168     //
1169     for (v = uLoc + 1; v < uEnd; v++)
1170     {
1171         if (!(ctx->sMoveStack.mvf[v].bvFlags & MVF_MOVE_SEARCHED))
1172         {
1173             iVal = ctx->sMoveStack.mvf[v].iValue;
1174             if (iVal > iBestVal)
1175             {
1176                 iBestVal = iVal;
1177                 uLoc = v;
1178             }
1179         }
1180     }
1181
1182     //
1183     // Move the best move we found into position u.
1184     //
1185     mvfTemp = ctx->sMoveStack.mvf[u];
1186     ctx->sMoveStack.mvf[u] = ctx->sMoveStack.mvf[uLoc];
1187     ctx->sMoveStack.mvf[uLoc] = mvfTemp;
1188 }
1189
1190
1191 static UINT64 g_uPerftNodeCount;
1192 static UINT64 g_uPerftTotalNodes;
1193 static UINT64 g_uPerftGenerates;
1194
1195 void
1196 Perft(SEARCHER_THREAD_CONTEXT *ctx,
1197       ULONG uDepth)
1198 {
1199     MOVE mv;
1200     ULONG u;
1201     ULONG uPly;
1202
1203     g_uPerftTotalNodes += 1;
1204     ASSERT(uDepth < MAX_PLY_PER_SEARCH);
1205     if (uDepth == 0)
1206     {
1207         g_uPerftNodeCount += 1;
1208         return;
1209     }
1210
1211     mv.uMove = 0;
1212     g_uPerftGenerates += 1;
1213     GenerateMoves(ctx, mv, GENERATE_DONT_SCORE);
1214
1215     uPly = ctx->uPly;
1216     for (u = ctx->sMoveStack.uBegin[uPly];
1217          u < ctx->sMoveStack.uEnd[uPly];
1218          u++)
1219     {
1220         mv = ctx->sMoveStack.mvf[u].mv;
1221         if (MakeMove(ctx, mv))
1222         {
1223             Perft(ctx, uDepth - 1);
1224             UnmakeMove(ctx, mv);
1225         }
1226     }
1227 }
1228
1229 COMMAND(PerftCommand)
1230 /**
1231
1232 Routine description:
1233
1234     This function implements the 'perft' engine command.  I have no
1235     idea what 'perft' means but some people use this command to
1236     benchmark the speed of the move generator code.  Note: the way
1237     this is implemented here does nothing whatsoever with the move
1238     scoring code (i.e. the SEE)
1239
1240     Usage:
1241
1242         perft <depth>
1243
1244 Parameters:
1245
1246     The COMMAND macro hides four arguments from the input parser:
1247
1248         CHAR *szInput : the full line of input
1249         ULONG argc    : number of argument chunks
1250         CHAR *argv[]  : array of ptrs to each argument chunk
1251         POSITION *pos : a POSITION pointer to operate on
1252
1253 Return value:
1254
1255     void
1256
1257 **/
1258 {
1259     LIGHTWEIGHT_SEARCHER_CONTEXT ctx;
1260     ULONG u;
1261     ULONG uDepth;
1262     double dBegin, dTime;
1263     double dNps;
1264
1265     if (argc < 2)
1266     {
1267         Trace("Usage: perft <required_depth>\n");
1268         return;
1269     }
1270     uDepth = atoi(argv[1]);
1271     if (uDepth >= MAX_DEPTH_PER_SEARCH)
1272     {
1273         Trace("Error: invalid depth.\n");
1274         return;
1275     }
1276
1277     InitializeLightweightSearcherContext(pos, &ctx);
1278
1279     g_uPerftTotalNodes = g_uPerftGenerates = 0ULL;
1280     dBegin = SystemTimeStamp();
1281     for (u = 1; u <= uDepth; u++)
1282     {
1283         g_uPerftNodeCount = 0ULL;
1284         Perft((SEARCHER_THREAD_CONTEXT *)&ctx, u);
1285         Trace("%u. %" COMPILER_LONGLONG_UNSIGNED_FORMAT " node%s, "
1286                   "%" COMPILER_LONGLONG_UNSIGNED_FORMAT " generate%s.\n",
1287               u,
1288               g_uPerftNodeCount,
1289               (g_uPerftNodeCount > 1) ? "s" : "",
1290               g_uPerftGenerates,
1291               (g_uPerftGenerates > 1) ? "s" : "");
1292     }
1293     dTime = SystemTimeStamp() - dBegin;
1294     dNps = (double)g_uPerftTotalNodes;
1295     dNps /= dTime;
1296     Trace("%" COMPILER_LONGLONG_UNSIGNED_FORMAT " total nodes, "
1297           "%" COMPILER_LONGLONG_UNSIGNED_FORMAT " total generates "
1298           "in %6.2f seconds.\n",
1299           g_uPerftTotalNodes,
1300           g_uPerftGenerates,
1301           dTime);
1302     Trace("That's approx %.0f moves/sec\n", dNps);
1303 }