src/generate.c

   1 /**
   2
   3 Copyright (c) Scott Gasch
   4
   5 Module Name:
   6
   7     generate.c
   8
   9 Abstract:
  10
  11     This module contains two move generators: a pseudo legal move
  12     generator and a pseudo legal escaping move generator.  The former
  13     is called in positions where side on move is not in check and the
  14     latter is called when the side on move is in check.  Note: both of
  15     these generators produce pseudo-legal moves.  The normal move
  16     generator is pretty bad: it does not bother to see if moves expose
  17     their own king to check or if castles pass through check
  18     etc... Instead it relies on MakeMove to throw out any illegal
  19     moves it generates.  The escape generator is better in that it
  20     produces less illegal moves.  But it is still possible to generate
  21     some with it.  An example: it will generate replies to check that
  22     may include capturing moves that are illegal because the capturing
  23     piece is pinned to the (already in check) king.  Both generators
  24     produce a set of moves that contains the true legal set of moves in
  25     a position as a subset; if a move is legal it will be produced.
  26
  27     This module also contains some code to flag moves as checking
  28     moves and score moves after they are generated.
  29
  30 Author:
  31
  32     Scott Gasch ([email protected]) 11 May 2004
  33
  34 Revision History:
  35
  36     $Id: generate.c 345 2007-12-02 22:56:42Z scott $
  37
  38 **/
  39
  40 #include "chess.h"
  41 #include "psqt.h"
  42
  43 //
  44 // Note: this order is important because of how EvalQueen works
  45 //
  46 const INT g_iQKDeltas[] = {
  47     -17, -16, -15, -1, +1, +17, +15, +16, 0 };
  48
  49 static void
  50 _FindUnblockedSquares(IN MOVE_STACK *pStack,
  51                       IN POSITION *pos)
  52 /**
  53
  54 Routine description:
  55
  56     Given a position, find, count and mark all squares that are
  57     unblocked for the king of the side not on move.  For example:
  58
  59        +---+---+---+---+- - -    The squares marked with *'s in this
  60        |***| K |***|*Q*|         diagram are unblocked for the K.  As
  61        +---+---+---+---+- - -    you can see, there are nine of them.
  62        |*P*|***|***|   |
  63        +---+---+---+---+- - -    Note the piece at the end of an unblocked
  64        |   |***|   |*P*|         ray from the king is on an unblocked
  65        +---+---+---+---+- - -    square (and its color doesn't matter)
  66        |   |*R*|   |   |
  67        +---+---+---+---+- - -    This stuff is used to flag checking moves
  68        |   |   |   |   |         as they are generated.
  69        .   .   .   .   .
  70
  71     Also note: this is one of the most called routines in the engine;
  72     speed is of the essence here.
  73
  74 Parameters:
  75
  76     MOVE_STACK *pStack : move stack pointer
  77     POSITION *pos : position pointer
  78
  79 Return value:
  80
  81     void
  82
  83 **/
  84 {
  85     register ULONG u;
  86     COOR cKing = pos->cNonPawns[FLIP(pos->uToMove)][0];
  87     COOR c;
  88     ULONG uPly = pStack->uPly;
  89 #ifdef DEBUG
  90     PIECE pKing = pos->rgSquare[cKing].pPiece;
  91     ULONG uCount = 0;
  92     COOR cx;
  93
  94     ASSERT(IS_ON_BOARD(cKing));
  95     ASSERT(IS_KING(pKing));
  96     ASSERT(GET_COLOR(pKing) != pos->uToMove);
  97 #endif
  98
  99     //
 100     // Adjust the unblocked key value for this ply...
 101     //
 102     pStack->uUnblockedKeyValue[uPly]++;
 103 #ifdef DEBUG
 104     FOREACH_SQUARE(c)
 105     {
 106         if (!IS_ON_BOARD(c)) continue;
 107         ASSERT(pStack->sUnblocked[uPly][c].uKey !=
 108                pStack->uUnblockedKeyValue[uPly]);
 109     }
 110 #endif
 111
 112     u = 0;
 113     ASSERT(g_iQKDeltas[u] != 0);
 114     do
 115     {
 116         c = cKing + g_iQKDeltas[u];
 117         while(IS_ON_BOARD(c))
 118         {
 119             pStack->sUnblocked[uPly][c].uKey =
 120                 pStack->uUnblockedKeyValue[uPly];
 121             pStack->sUnblocked[uPly][c].iPointer = -1 * g_iQKDeltas[u];
 122 #ifdef DEBUG
 123             ASSERT(-g_iQKDeltas[u] == DIRECTION_BETWEEN_SQUARES(c,cKing));
 124             ASSERT(pStack->sUnblocked[uPly][c].iPointer != 0);
 125             cx = c;
 126             do
 127             {
 128                 cx += pStack->sUnblocked[uPly][c].iPointer;
 129             }
 130             while(IS_ON_BOARD(cx) && (IS_EMPTY(pos->rgSquare[cx].pPiece)));
 131             ASSERT(cx == cKing);
 132             uCount++;
 133 #endif
 134             if (!IS_EMPTY(pos->rgSquare[c].pPiece))
 135             {
 136                 break;
 137             }
 138             c += g_iQKDeltas[u];
 139         }
 140         u++;
 141     }
 142     while(g_iQKDeltas[u] != 0);
 143     ASSERT(uCount > 2);
 144     ASSERT(uCount < 28);
 145 }
 146
 147 #define SQUARE_IS_UNBLOCKED(c) (uUnblocked == kp[(c)].uKey)
 148 #define DIR_FROM_SQ_TO_KING(c) (kp[(c)].iPointer)
 149
 150 FLAG
 151 WouldGiveCheck(IN SEARCHER_THREAD_CONTEXT *ctx,
 152                IN MOVE mv)
 153 /**
 154
 155 Routine description:
 156
 157     Determine whether a move is a checking move or not.  For this
 158     function to work properly _FindUnblockedSquares must have been
 159     called at the start of generation.
 160
 161     Note: this is one of the most called codepaths in the engine,
 162     speed is of the essence here.
 163
 164 Parameters:
 165
 166     MOVE_STACK *pStack : the move stack
 167     POSITION *pos : the board
 168     MOVE mv : the move under consideration
 169
 170 Return value:
 171
 172     FLAG : TRUE if the move is checking, FALSE otherwise
 173
 174 **/
 175 {
 176     //
 177     // TODO: consider adding a hash table to see if sig+mv would
 178     // give check.  Is this worth it?
 179     //
 180     MOVE_STACK *pStack = &(ctx->sMoveStack);
 181     POSITION *pos = &(ctx->sPosition);
 182     COOR cTo = mv.cTo;
 183     COOR cFrom = mv.cFrom;
 184     PIECE pPiece = mv.pMoved;
 185     COOR xKing = pos->cNonPawns[FLIP(GET_COLOR(pPiece))][0];
 186     KEY_POINTER *kp = &(pStack->sUnblocked[ctx->uPly][0]);
 187     ULONG uUnblocked = pStack->uUnblockedKeyValue[ctx->uPly];
 188     COOR cEpSquare;
 189     int iDelta;
 190
 191     ASSERT(ctx->uPly < MAX_PLY_PER_SEARCH);
 192     ASSERT(PositionsAreEquivalent(&(pStack->board[ctx->uPly]), pos));
 193     ASSERT(mv.uMove);
 194     ASSERT(IS_KING(pos->rgSquare[xKing].pPiece));
 195     ASSERT(IS_ON_BOARD(cTo));
 196     ASSERT(IS_ON_BOARD(cFrom));
 197     ASSERT(pPiece);
 198
 199     //
 200     // Phase 1: Does this move directly attack the king?
 201     //
 202
 203     //
 204     // You can't attack one king directly with the other except by
 205     // castling (in which case the rook is doing the attack).
 206     //
 207     if (IS_KING(pPiece))
 208     {
 209         if (!IS_SPECIAL_MOVE(mv))
 210         {
 211             goto exposes;
 212         }
 213
 214         ASSERT((mv.cFrom == E8) || (mv.cFrom == E1));
 215         pPiece &= ~4;
 216         ASSERT(!IS_KING(pPiece));
 217         ASSERT(IS_ROOK(pPiece));
 218         ASSERT(pPiece == (BLACK_ROOK | GET_COLOR(pPiece)));
 219
 220         switch(cTo)
 221         {
 222             case C1:
 223                 cTo = D1;
 224                 if (SQUARE_IS_UNBLOCKED(E1) &&
 225                     (DIR_FROM_SQ_TO_KING(E1) == 1))
 226                 {
 227                     ASSERT(RANK1(xKing));
 228                     return(MOVE_FLAG_CHECKING);
 229                 }
 230                 break;
 231             case G1:
 232                 cTo = F1;
 233                 if (SQUARE_IS_UNBLOCKED(E1) &&
 234                     (DIR_FROM_SQ_TO_KING(E1) == -1))
 235                 {
 236                     ASSERT(RANK1(xKing));
 237                     return(MOVE_FLAG_CHECKING);
 238                 }
 239                 break;
 240             case C8:
 241                 cTo = D8;
 242                 if (SQUARE_IS_UNBLOCKED(E8) &&
 243                     (DIR_FROM_SQ_TO_KING(E8) == 1))
 244                 {
 245                     ASSERT(RANK8(xKing));
 246                     return(MOVE_FLAG_CHECKING);
 247                 }
 248                 break;
 249             case G8:
 250                 cTo = F8;
 251                 if (SQUARE_IS_UNBLOCKED(E8) &&
 252                     (DIR_FROM_SQ_TO_KING(E8) == -1))
 253                 {
 254                     ASSERT(RANK8(xKing));
 255                     return(MOVE_FLAG_CHECKING);
 256                 }
 257                 break;
 258 #ifdef DEBUG
 259             default:
 260                 UtilPanic(SHOULD_NOT_GET_HERE,
 261                           NULL, NULL, NULL, NULL,
 262                           __FILE__, __LINE__);
 263                 break;
 264 #endif
 265         }
 266     }
 267
 268     //
 269     // Ok, either its not a king or its a castle move and we are thinking
 270     // about the rook now.
 271     //
 272
 273     //
 274     // Check the attack vector table
 275     //
 276     ASSERT(!IS_KING(pPiece));
 277     iDelta = 0;
 278     if (mv.pPromoted)
 279     {
 280         ASSERT(IS_PAWN(pPiece));
 281         ASSERT(GET_COLOR(pPiece) == GET_COLOR(mv.pPromoted));
 282         pPiece = mv.pPromoted;
 283         ASSERT(!IS_PAWN(pPiece));
 284         iDelta = cFrom - cTo;
 285         ASSERT(iDelta != 0);
 286     }
 287
 288     //
 289     // Does pPiece attack xKing directly if there are not pieces in
 290     // the way?
 291     //
 292     if (0 != (CHECK_VECTOR_WITH_INDEX((int)cTo - (int)xKing,
 293                                       GET_COLOR(pPiece)) &
 294               (1 << PIECE_TYPE(pPiece))))
 295     {
 296         //
 297         // We don't toggle knight squares as unblocked... so if the sq
 298         // is unblocked then piece must not be a knight.  Note: this
 299         // logical OR replaced with bitwise equivalent for speed.
 300         //
 301         if ((SQUARE_IS_UNBLOCKED(cTo)) | (IS_KNIGHT(pPiece)))
 302         {
 303 #ifdef DEBUG
 304             if (SQUARE_IS_UNBLOCKED(cTo))
 305             {
 306                 ASSERT(!IS_KNIGHT(pPiece));
 307             }
 308             else
 309             {
 310                 ASSERT(IS_KNIGHT(pPiece));
 311             }
 312 #endif
 313             return(MOVE_FLAG_CHECKING);
 314         }
 315         ASSERT(!IS_PAWN(pPiece));
 316
 317         //
 318         // Special case: if this is a pawn that just promoted, and the
 319         // from square was unblocked, this pawn in its new state can
 320         // check the king.
 321         //
 322         if ((DIR_FROM_SQ_TO_KING(cFrom) == iDelta) &&
 323             (SQUARE_IS_UNBLOCKED(cFrom)))
 324         {
 325             return(MOVE_FLAG_CHECKING);
 326         }
 327     }
 328
 329  exposes:
 330     //
 331     // We now know that the move itself does not directly attack the
 332     // enemy king.  We will now see if that move exposes check to the
 333     // enemy king.
 334     //
 335
 336     //
 337     // A move cannot expose check directly if its from square is not
 338     // an unblocked square.  But if it is unblocked, we will have to
 339     // scan behind the piece to see if there is some attacker.
 340     //
 341     if (SQUARE_IS_UNBLOCKED(cFrom))
 342     {
 343         //
 344         // Piece moves towards the king on the same ray?  Cannot be
 345         // check.  Piece moves away from the king on the same ray?
 346         // Cannot be check.
 347         //
 348         if (DIRECTION_BETWEEN_SQUARES(cTo, xKing) !=
 349             DIR_FROM_SQ_TO_KING(cFrom))
 350         {
 351             if (IS_ON_BOARD(FasterExposesCheck(pos, cFrom, xKing)))
 352             {
 353                 ASSERT(IS_ON_BOARD(ExposesCheck(pos, cFrom, xKing)));
 354                 return(MOVE_FLAG_CHECKING);
 355             }
 356         }
 357     }
 358
 359     //
 360     // There is one last special case.  If this move was enpassant
 361     // it's possible that the removal of the enemy pawn has exposed
 362     // the enemy king to check.
 363     //
 364     // rnb2bnr/ppp3pp/4k3/1B1qPpB1/4p1Q1/8/PPP2PPP/RN2K1NR w  - f6 0 0
 365     // rn5r/pp4pp/8/5qk1/1b2pP2/4K3/PPP3PP/RN4NR b  - f3 0 0
 366     //
 367     if (IS_ENPASSANT(mv))
 368     {
 369         ASSERT(IS_PAWN(pPiece));
 370         ASSERT(VALID_EP_SQUARE(cTo));
 371         ASSERT(cTo == pos->cEpSquare);
 372         cEpSquare = cTo + 16 * g_iBehind[(GET_COLOR(pPiece))];
 373 #ifdef DEBUG
 374         if (GET_COLOR(pPiece))
 375         {
 376             ASSERT(cEpSquare == (cTo + 16));
 377         }
 378         else
 379         {
 380             ASSERT(cEpSquare == (cTo - 16));
 381         }
 382 #endif
 383         ASSERT(IS_PAWN(pos->rgSquare[cEpSquare].pPiece));
 384         ASSERT(OPPOSITE_COLORS(pPiece, pos->rgSquare[cEpSquare].pPiece));
 385
 386         //
 387         // Logical OR replaced with bitwise for speed.
 388         //
 389         if (((SQUARE_IS_UNBLOCKED(cEpSquare)) |
 390              (SQUARE_IS_UNBLOCKED(cFrom))) &&
 391             (IS_ON_BOARD(ExposesCheckEp(pos, cEpSquare, cFrom, cTo, xKing))))
 392         {
 393             return(MOVE_FLAG_CHECKING);
 394         }
 395     }
 396
 397     //
 398     // No direct check + no exposed check = no check.
 399     //
 400     return(0);
 401 }
 402
 403
 404 static void FORCEINLINE
 405 _AddNormalMove(IN MOVE_STACK *pStack,
 406                IN POSITION *pos,
 407                IN COOR cFrom,
 408                IN COOR cTo,
 409                IN PIECE pCap)
 410 /**
 411
 412 Routine description:
 413
 414     Adds a move from the generator functions to the stack of generated
 415     moves.
 416
 417 Parameters:
 418
 419     MOVE_STACK *pStack : the move stack
 420     POSITION *pos : the board position
 421     COOR cFrom : the move's from square
 422     COOR cTo : the move's to square
 423     PIECE pCap : what was captured (if anything)
 424
 425 Return value:
 426
 427     static void FORCEINLINE
 428
 429 **/
 430 {
 431     PIECE pMoved = pos->rgSquare[cFrom].pPiece;
 432     ULONG uPly = pStack->uPly;
 433     MOVE_STACK_MOVE_VALUE_FLAGS *pMvf;
 434
 435     ASSERT(pMoved);
 436     ASSERT(GET_COLOR(pMoved) == pos->uToMove);
 437     ASSERT(IS_ON_BOARD(cFrom));
 438     ASSERT(IS_ON_BOARD(cTo));
 439
 440     pMvf = &(pStack->mvf[pStack->uEnd[uPly]]);
 441     pMvf->mv.uMove = MAKE_MOVE_WITH_NO_PROM_OR_FLAGS(cFrom, cTo, pMoved, pCap);
 442     pStack->uEnd[uPly]++;
 443
 444     ASSERT(pMvf->mv.uMove == MAKE_MOVE(cFrom, cTo, pMoved, pCap, 0, 0));
 445     ASSERT(SanityCheckMove(pos, pMvf->mv));
 446 }
 447
 448
 449 static void FORCEINLINE
 450 _AddEnPassant(IN MOVE_STACK *pStack,
 451               IN POSITION *pos,
 452               IN COOR cFrom,
 453               IN COOR cTo)
 454 /**
 455
 456 Routine description:
 457
 458     Add an en passant pawn capture to the move stack.
 459
 460 Parameters:
 461
 462     MOVE_STACK *pStack : the move stack
 463     POSITION *pos : the board position
 464     COOR cFrom : the from square
 465     COOR cTo : the to square (and en passant square)
 466
 467 Return value:
 468
 469     static void
 470
 471 **/
 472 {
 473     PIECE pMoved = BLACK_PAWN | pos->uToMove;
 474     PIECE pCaptured = FLIP(pMoved);
 475     ULONG uPly = pStack->uPly;
 476     MOVE_STACK_MOVE_VALUE_FLAGS *pMvf;
 477
 478     ASSERT(pCaptured == (BLACK_PAWN | (FLIP(pos->uToMove))));
 479     ASSERT(IS_ON_BOARD(cFrom));
 480     ASSERT(IS_ON_BOARD(cTo));
 481     ASSERT(RANK4(cFrom) || RANK5(cFrom));
 482     ASSERT(VALID_EP_SQUARE(cTo));
 483     ASSERT(IS_PAWN(pos->rgSquare[cFrom].pPiece));
 484     ASSERT(GET_COLOR(pos->rgSquare[cFrom].pPiece) == pos->uToMove);
 485
 486     pMvf = &(pStack->mvf[pStack->uEnd[uPly]]);
 487     pMvf->mv.uMove =
 488         MAKE_MOVE(cFrom, cTo, pMoved, pCaptured, 0, MOVE_FLAG_SPECIAL);
 489     pStack->uEnd[uPly]++;
 490
 491     ASSERT(SanityCheckMove(pos, pMvf->mv));
 492 }
 493
 494
 495 static void FORCEINLINE
 496 _AddCastle(IN MOVE_STACK *pStack,
 497            IN POSITION *pos,
 498            IN COOR cFrom,
 499            IN COOR cTo)
 500 /**
 501
 502 Routine description:
 503
 504     Add a castle move to the move stack.
 505
 506 Parameters:
 507
 508     MOVE_STACK *pStack,
 509     POSITION *pos,
 510     COOR cFrom,
 511     COOR cTo
 512
 513 Return value:
 514
 515     static void FORCEINLINE
 516
 517 **/
 518 {
 519     PIECE pMoved = BLACK_KING | pos->uToMove;
 520     ULONG uPly = pStack->uPly;
 521     MOVE_STACK_MOVE_VALUE_FLAGS *pMvf;
 522
 523     ASSERT(IS_ON_BOARD(cFrom));
 524     ASSERT(IS_ON_BOARD(cTo));
 525     ASSERT((E1 == cFrom) || (E8 == cFrom));
 526     ASSERT(IS_KING(pos->rgSquare[cFrom].pPiece));
 527     ASSERT(GET_COLOR(pos->rgSquare[cFrom].pPiece) == pos->uToMove);
 528
 529     pMvf = &(pStack->mvf[pStack->uEnd[uPly]]);
 530     pMvf->mv.uMove = MAKE_MOVE(cFrom, cTo, pMoved, 0, 0, MOVE_FLAG_SPECIAL);
 531     pStack->uEnd[uPly]++;
 532
 533     ASSERT(SanityCheckMove(pos, pMvf->mv));
 534 }
 535
 536
 537 static void FORCEINLINE
 538 _AddPromote(IN MOVE_STACK *pStack,
 539             IN POSITION *pos,
 540             IN COOR cFrom,
 541             IN COOR cTo)
 542 /**
 543
 544 Routine description:
 545
 546     Adds a pawn promotion (set of) moves to the move stack.  This can
 547     be a capture-promotion or non-capture promotion.  This function
 548     pushes several moves onto the move stack, one for each possible
 549     promotion target.
 550
 551 Parameters:
 552
 553     MOVE_STACK *pStack : the move stack
 554     POSITION *pos : the board position
 555     COOR cFrom : the move's from square
 556     COOR cTo : the move's to square
 557
 558 Return value:
 559
 560     static void
 561
 562 **/
 563 {
 564     PIECE pMoved = BLACK_PAWN | pos->uToMove;
 565     PIECE pCaptured = pos->rgSquare[cTo].pPiece;
 566     ULONG uPly = pStack->uPly;
 567     MOVE_STACK_MOVE_VALUE_FLAGS *pMvf;
 568     ULONG u;
 569
 570 #define ARRAY_LENGTH_TARG (4)
 571     const static PIECE pTarg[ARRAY_LENGTH_TARG] = { BLACK_QUEEN,
 572                                                     BLACK_ROOK,
 573                                                     BLACK_BISHOP,
 574                                                     BLACK_KNIGHT };
 575
 576     ASSERT(IS_ON_BOARD(cFrom));
 577     ASSERT(IS_ON_BOARD(cTo));
 578     ASSERT(RANK1(cTo) || RANK8(cTo));
 579     ASSERT(RANK7(cFrom) || RANK2(cFrom));
 580     ASSERT(ARRAY_LENGTH(pTarg) == ARRAY_LENGTH_TARG);
 581     ASSERT(IS_PAWN(pos->rgSquare[cFrom].pPiece));
 582
 583     for (u = 0; u < ARRAY_LENGTH_TARG; u++)
 584     {
 585         pMvf = &(pStack->mvf[pStack->uEnd[uPly]]);
 586         pMvf->mv.uMove = MAKE_MOVE(cFrom, cTo, pMoved, pCaptured,
 587                                    pTarg[u] | pos->uToMove, MOVE_FLAG_SPECIAL);
 588         pStack->uEnd[uPly]++;
 589         ASSERT(SanityCheckMove(pos, pMvf->mv));
 590     }
 591 #undef ARRAY_LENGTH_TARG
 592 }
 593
 594
 595 static void FORCEINLINE
 596 _AddDoubleJump(IN MOVE_STACK *pStack,
 597                IN POSITION *pos,
 598                IN COOR cFrom,
 599                IN COOR cTo)
 600 /**
 601
 602 Routine description:
 603
 604     This function adds a pawn double jump to the move stack.
 605
 606 Parameters:
 607
 608     MOVE_STACK *pStack : the move stack
 609     POSITION *pos : the board position
 610     COOR cFrom : the move's from square
 611     COOR cTo : the move's to square
 612
 613 Return value:
 614
 615     static void
 616
 617 **/
 618 {
 619     PIECE pMoved = BLACK_PAWN | pos->uToMove;
 620     ULONG uPly = pStack->uPly;
 621     MOVE_STACK_MOVE_VALUE_FLAGS *pMvf;
 622
 623     ASSERT(IS_ON_BOARD(cFrom));
 624     ASSERT(IS_ON_BOARD(cTo));
 625     ASSERT(RANK2(cFrom) || RANK7(cFrom));
 626     ASSERT(RANK4(cTo) || RANK5(cTo));
 627     ASSERT(IS_PAWN(pos->rgSquare[cFrom].pPiece));
 628
 629     pMvf = &(pStack->mvf[pStack->uEnd[uPly]]);
 630     pMvf->mv.uMove = MAKE_MOVE(cFrom, cTo, pMoved, 0, 0, MOVE_FLAG_SPECIAL);
 631     pStack->uEnd[uPly]++;
 632
 633     ASSERT(SanityCheckMove(pos, pMvf->mv));
 634 }
 635
 636
 637 const INT g_iNDeltas[] = {
 638     -33, -31,  -18, -14, +14, +18, +31, +33,  0 };
 639
 640 void
 641 GenerateKnight(IN MOVE_STACK *pStack,
 642                IN POSITION *pos,
 643                IN COOR cKnight)
 644 /**
 645
 646 Routine description:
 647
 648     This function is called by GenerateMoves' JumpTable.  Its job
 649     is to generate and push pseudo-legal knight moves for the
 650     knight sitting on square cKnight.
 651
 652 Parameters:
 653
 654     MOVE_STACK *pStack : the move stack
 655     POSITION *pos : the board position
 656     COOR cKnight : the knight's location
 657
 658 Return value:
 659
 660     void
 661
 662 **/
 663 {
 664     COOR c;
 665     ULONG u = 0;
 666     PIECE p;
 667
 668     ASSERT(IS_KNIGHT(pos->rgSquare[cKnight].pPiece));
 669     ASSERT(GET_COLOR(pos->rgSquare[cKnight].pPiece) == pos->uToMove);
 670     ASSERT(g_iNDeltas[u] != 0);
 671
 672     do
 673     {
 674         c = cKnight + g_iNDeltas[u];
 675         u++;
 676         if (IS_ON_BOARD(c))
 677         {
 678             p = pos->rgSquare[c].pPiece;
 679
 680             //
 681             // This logical OR replaced with bitwise OR; the effect is
 682             // the same the the bitwise is marginally faster.
 683             //
 684             if (IS_EMPTY(p) | (OPPOSITE_COLORS(p, pos->uToMove)))
 685             {
 686                 _AddNormalMove(pStack, pos, cKnight, c, p);
 687             }
 688         }
 689     }
 690     while(0 != g_iNDeltas[u]);
 691 }
 692
 693 void
 694 GenerateWhiteKnight(IN MOVE_STACK *pStack,
 695                     IN POSITION *pos,
 696                     IN COOR cKnight)
 697 {
 698     COOR c;
 699     ULONG u = 0;
 700     PIECE p;
 701
 702     ASSERT(IS_KNIGHT(pos->rgSquare[cKnight].pPiece));
 703     ASSERT(GET_COLOR(pos->rgSquare[cKnight].pPiece) == pos->uToMove);
 704     ASSERT(g_iNDeltas[u] != 0);
 705
 706     do
 707     {
 708         c = cKnight + g_iNDeltas[u];
 709         u++;
 710         if (IS_ON_BOARD(c))
 711         {
 712             p = pos->rgSquare[c].pPiece;
 713
 714             //
 715             // Note: this test covers empty squares also -- it is just
 716             // testing that the low order bit (color bit) of p is zero
 717             // which is true for black pieces and empty squares.  This
 718             // is done for speed over readability.
 719             //
 720             if (GET_COLOR(p) == BLACK)
 721             {
 722                 ASSERT(IS_EMPTY(p) || (GET_COLOR(p) == BLACK));
 723                 _AddNormalMove(pStack, pos, cKnight, c, p);
 724             }
 725         }
 726     }
 727     while(0 != g_iNDeltas[u]);
 728 }
 729
 730 //
 731 // These logical AND/ORs replaced with bitwise AND/OR; the effect is
 732 // the same the the bitwise is marginally faster.
 733 //
 734 #define BLOCKS_THE_CHECK(sq) \
 735     ((iAttackDelta != 0) & \
 736      (iAttackDelta == DIRECTION_BETWEEN_SQUARES(cAttacker, (sq))) & \
 737      (((cAttacker > cKing) & ((sq) > cKing)) | \
 738       ((cAttacker < cKing) & ((sq) < cKing))))
 739
 740 void
 741 SaveMeKnight(IN MOVE_STACK *pStack,
 742              IN POSITION *pos,
 743              IN COOR cKnight,
 744              IN COOR cKing,
 745              IN COOR cAttacker)
 746 /**
 747
 748 Routine description:
 749
 750     This routine is called by GenerateEscapes' JumpTable.  Its job is
 751     to generate moves by the knight on square cKnight that alleviate
 752     check to the king on square cKing.  The (lone) piece attacking the
 753     king is on square cAttacker.
 754
 755 Parameters:
 756
 757     MOVE_STACK *pStack : the move stack
 758     POSITION *pos : the board position
 759     COOR cKnight : the location of the knight
 760     COOR cKing : the location of the friendly king
 761     COOR cAttacker : the location of the checking piece
 762
 763 Return value:
 764
 765     void
 766
 767 **/
 768 {
 769     COOR c, cExposed;
 770     int iAttackDelta = DIRECTION_BETWEEN_SQUARES(cAttacker, cKing);
 771     ULONG u = 0;
 772     PIECE p;
 773
 774     ASSERT(InCheck(pos, pos->uToMove));
 775     ASSERT(IS_KNIGHT(pos->rgSquare[cKnight].pPiece));
 776     ASSERT(GET_COLOR(pos->rgSquare[cKnight].pPiece) == pos->uToMove);
 777     ASSERT(GET_COLOR(pos->rgSquare[cKnight].pPiece) ==
 778            GET_COLOR(pos->rgSquare[cKing].pPiece));
 779     ASSERT(OPPOSITE_COLORS(pos->rgSquare[cAttacker].pPiece,
 780                            pos->rgSquare[cKing].pPiece));
 781     ASSERT(g_iNDeltas[u] != 0);
 782
 783     do
 784     {
 785         c = cKnight + g_iNDeltas[u];
 786         u++;
 787         if (IS_ON_BOARD(c))
 788         {
 789             if ((c == cAttacker) || BLOCKS_THE_CHECK(c))
 790             {
 791                 cExposed = ExposesCheck(pos, cKnight, cKing);
 792                 if (!IS_ON_BOARD(cExposed) || (cExposed == c))
 793                 {
 794                     p = pos->rgSquare[c].pPiece;
 795                     ASSERT(!p ||
 796                            OPPOSITE_COLORS(p, pos->rgSquare[cKnight].pPiece));
 797                     ASSERT(!p || (c == cAttacker));
 798                     _AddNormalMove(pStack, pos, cKnight, c, p);
 799                 }
 800             }
 801         }
 802     }
 803     while(0 != g_iNDeltas[u]);
 804 }
 805
 806
 807 const INT g_iBDeltas[] = {
 808     -17, -15, +15, +17, 0 };
 809
 810 void
 811 GenerateBishop(IN MOVE_STACK *pStack,
 812                IN POSITION *pos,
 813                IN COOR cBishop)
 814 /**
 815
 816 Routine description:
 817
 818     This routine is called by GenerateMoves' JumpTable to generate
 819     pseudo-legal bishop moves by the piece at cBishop.
 820
 821 Parameters:
 822
 823     MOVE_STACK *pStack : the move stack
 824     POSITION *pos : the board position
 825     COOR cBishop : the bishop location
 826
 827 Return value:
 828
 829     void
 830
 831 **/
 832 {
 833     COOR c;
 834     PIECE p;
 835
 836     ASSERT(IS_BISHOP(pos->rgSquare[cBishop].pPiece));
 837     ASSERT(GET_COLOR(pos->rgSquare[cBishop].pPiece) == pos->uToMove);
 838
 839     //
 840     // Note: manually unrolled loop
 841     //
 842     c = cBishop - 17;
 843     while(IS_ON_BOARD(c))
 844     {
 845         p = pos->rgSquare[c].pPiece;
 846         if (IS_EMPTY(p))
 847         {
 848             _AddNormalMove(pStack, pos, cBishop, c, 0);
 849         }
 850         else
 851         {
 852             if (OPPOSITE_COLORS(p, pos->uToMove))
 853             {
 854                 _AddNormalMove(pStack, pos, cBishop, c, p);
 855             }
 856             break;
 857         }
 858         c += -17;
 859     }
 860
 861     c = cBishop - 15;
 862     while(IS_ON_BOARD(c))
 863     {
 864         p = pos->rgSquare[c].pPiece;
 865         if (IS_EMPTY(p))
 866         {
 867             _AddNormalMove(pStack, pos, cBishop, c, 0);
 868         }
 869         else
 870         {
 871             if (OPPOSITE_COLORS(p, pos->uToMove))
 872             {
 873                 _AddNormalMove(pStack, pos, cBishop, c, p);
 874             }
 875             break;
 876         }
 877         c += -15;
 878     }
 879
 880     c = cBishop + 15;
 881     while(IS_ON_BOARD(c))
 882     {
 883         p = pos->rgSquare[c].pPiece;
 884         if (IS_EMPTY(p))
 885         {
 886             _AddNormalMove(pStack, pos, cBishop, c, 0);
 887         }
 888         else
 889         {
 890             if (OPPOSITE_COLORS(p, pos->uToMove))
 891             {
 892                 _AddNormalMove(pStack, pos, cBishop, c, p);
 893             }
 894             break;
 895         }
 896         c += 15;
 897     }
 898
 899     c = cBishop + 17;
 900     while(IS_ON_BOARD(c))
 901     {
 902         p = pos->rgSquare[c].pPiece;
 903         if (IS_EMPTY(p))
 904         {
 905             _AddNormalMove(pStack, pos, cBishop, c, 0);
 906         }
 907         else
 908         {
 909             if (OPPOSITE_COLORS(p, pos->uToMove))
 910             {
 911                 _AddNormalMove(pStack, pos, cBishop, c, p);
 912             }
 913             break;
 914         }
 915         c += 17;
 916     }
 917 }
 918
 919
 920 void
 921 SaveMeBishop(IN MOVE_STACK *pStack,
 922              IN POSITION *pos,
 923              IN COOR cBishop,
 924              IN COOR cKing,
 925              IN COOR cAttacker)
 926 /**
 927
 928 Routine description:
 929
 930     This routine is called by GenerateEscapes' JumpTable in order to
 931     generate moves by the bishop at cBishop to alleviate check on its
 932     friendly king (at cKing) which is being checked by a piece at
 933     cAttacker.
 934
 935 Parameters:
 936
 937     MOVE_STACK *pStack : the move stack
 938     POSITION *pos : the board position
 939     COOR cBishop : the bishop's location
 940     COOR cKing : the friendly king's location
 941     COOR cAttacker : the checking piece's location
 942
 943 Return value:
 944
 945     void
 946
 947 **/
 948 {
 949     int iAttackDelta = DIRECTION_BETWEEN_SQUARES(cAttacker, cKing);
 950     COOR c;
 951     COOR cExposed;
 952     ULONG u = 0;
 953     PIECE p;
 954
 955     ASSERT(InCheck(pos, pos->uToMove));
 956     ASSERT(IS_BISHOP(pos->rgSquare[cBishop].pPiece));
 957     ASSERT(GET_COLOR(pos->rgSquare[cBishop].pPiece) == pos->uToMove);
 958     ASSERT(GET_COLOR(pos->rgSquare[cBishop].pPiece) ==
 959            GET_COLOR(pos->rgSquare[cKing].pPiece));
 960     ASSERT(OPPOSITE_COLORS(pos->rgSquare[cAttacker].pPiece,
 961                            pos->rgSquare[cKing].pPiece));
 962     ASSERT(g_iBDeltas[u] != 0);
 963
 964     do
 965     {
 966         c = cBishop + g_iBDeltas[u];
 967         while(IS_ON_BOARD(c))
 968         {
 969             p = pos->rgSquare[c].pPiece;
 970             if ((c == cAttacker) || BLOCKS_THE_CHECK(c))
 971             {
 972                 ASSERT(!p ||
 973                        OPPOSITE_COLORS(p, pos->rgSquare[cBishop].pPiece));
 974                 ASSERT(!p || (c == cAttacker));
 975                 cExposed = ExposesCheck(pos, cBishop, cKing);
 976                 if (!IS_ON_BOARD(cExposed) || (cExposed == c))
 977                 {
 978                     _AddNormalMove(pStack, pos, cBishop, c, p);
 979                     break;
 980                 }
 981             }
 982             else if (!IS_EMPTY(p))
 983             {
 984                 break;
 985             }
 986             c += g_iBDeltas[u];
 987         }
 988         u++;
 989     }
 990     while(0 != g_iBDeltas[u]);
 991 }
 992
 993
 994 const INT g_iRDeltas[] = {
 995     -1, +1, +16, -16, 0 };
 996
 997
 998 void
 999 GenerateRook(IN MOVE_STACK *pStack,
1000              IN POSITION *pos,
1001              IN COOR cRook)
1002 /**
1003
1004 Routine description:
1005
1006     This routine is called by GenerateMoves' JumpTable in order to
1007     generate pseudo-legal moves for the rook at position cRook.
1008
1009 Parameters:
1010
1011     MOVE_STACK *pStack : the move stack
1012     POSITION *pos : the board position
1013     COOR cRook : the rook's location
1014
1015 Return value:
1016
1017     void
1018
1019 **/
1020 {
1021     COOR c;
1022     PIECE p;
1023
1024     ASSERT(IS_ROOK(pos->rgSquare[cRook].pPiece));
1025     ASSERT(GET_COLOR(pos->rgSquare[cRook].pPiece) == pos->uToMove);
1026
1027     //
1028     // Note: manually unrolled loop
1029     //
1030     c = cRook - 1;
1031     while(IS_ON_BOARD(c))
1032     {
1033         p = pos->rgSquare[c].pPiece;
1034         if (IS_EMPTY(p))
1035         {
1036             _AddNormalMove(pStack, pos, cRook, c, 0);
1037         }
1038         else
1039         {
1040             if (OPPOSITE_COLORS(p, pos->uToMove))
1041             {
1042                 _AddNormalMove(pStack, pos, cRook, c, p);
1043             }
1044             break;
1045         }
1046         c += -1;
1047     }
1048
1049     c = cRook + 1;
1050     while(IS_ON_BOARD(c))
1051     {
1052         p = pos->rgSquare[c].pPiece;
1053         if (IS_EMPTY(p))
1054         {
1055             _AddNormalMove(pStack, pos, cRook, c, 0);
1056         }
1057         else
1058         {
1059             if (OPPOSITE_COLORS(p, pos->uToMove))
1060             {
1061                 _AddNormalMove(pStack, pos, cRook, c, p);
1062             }
1063             break;
1064         }
1065         c += 1;
1066     }
1067
1068     c = cRook + 16;
1069     while(IS_ON_BOARD(c))
1070     {
1071         p = pos->rgSquare[c].pPiece;
1072         if (IS_EMPTY(p))
1073         {
1074             _AddNormalMove(pStack, pos, cRook, c, 0);
1075         }
1076         else
1077         {
1078             if (OPPOSITE_COLORS(p, pos->uToMove))
1079             {
1080                 _AddNormalMove(pStack, pos, cRook, c, p);
1081             }
1082             break;
1083         }
1084         c += 16;
1085     }
1086
1087     c = cRook - 16;
1088     while(IS_ON_BOARD(c))
1089     {
1090         p = pos->rgSquare[c].pPiece;
1091         if (IS_EMPTY(p))
1092         {
1093             _AddNormalMove(pStack, pos, cRook, c, 0);
1094         }
1095         else
1096         {
1097             if (OPPOSITE_COLORS(p, pos->uToMove))
1098             {
1099                 _AddNormalMove(pStack, pos, cRook, c, p);
1100             }
1101             break;
1102         }
1103         c += -16;
1104     }
1105 }
1106
1107 void
1108 SaveMeRook(IN MOVE_STACK *pStack,
1109            IN POSITION *pos,
1110            IN COOR cRook,
1111            IN COOR cKing,
1112            IN COOR cAttacker)
1113 /**
1114
1115 Routine description:
1116
1117     This routine is called by GenerateEscapes' JumpTable in order to
1118     generate moves by the rook at location cRook that alleviate check
1119     to the king at cKing.  The lone checking piece is at cAttacker.
1120
1121 Parameters:
1122
1123     MOVE_STACK *pStack : the move stack
1124     POSITION *pos : the board position
1125     COOR cRook : the rook's location
1126     COOR cKing : the king's location
1127     COOR cAttacker : the checker's location
1128
1129 Return value:
1130
1131     void
1132
1133 **/
1134 {
1135     int iAttackDelta = DIRECTION_BETWEEN_SQUARES(cAttacker, cKing);
1136     COOR c;
1137     COOR cExposed;
1138     ULONG u = 0;
1139     PIECE p;
1140
1141     ASSERT(InCheck(pos, pos->uToMove));
1142     ASSERT(IS_ROOK(pos->rgSquare[cRook].pPiece));
1143     ASSERT(GET_COLOR(pos->rgSquare[cRook].pPiece) == pos->uToMove);
1144     ASSERT(GET_COLOR(pos->rgSquare[cRook].pPiece) == pos->uToMove);
1145     ASSERT(GET_COLOR(pos->rgSquare[cRook].pPiece) ==
1146            GET_COLOR(pos->rgSquare[cKing].pPiece));
1147     ASSERT(OPPOSITE_COLORS(pos->rgSquare[cAttacker].pPiece,
1148                            pos->rgSquare[cKing].pPiece));
1149     ASSERT(g_iRDeltas[u] != 0);
1150
1151     do
1152     {
1153         c = cRook + g_iRDeltas[u];
1154         while(IS_ON_BOARD(c))
1155         {
1156             p = pos->rgSquare[c].pPiece;
1157             if ((c == cAttacker) || BLOCKS_THE_CHECK(c))
1158             {
1159                 ASSERT(!p ||
1160                        OPPOSITE_COLORS(p, pos->rgSquare[cRook].pPiece));
1161                 ASSERT(!p || (c == cAttacker));
1162                 cExposed = ExposesCheck(pos, cRook, cKing);
1163                 if (!IS_ON_BOARD(cExposed) || (cExposed == c))
1164                 {
1165                     _AddNormalMove(pStack, pos, cRook, c, p);
1166                     break;
1167                 }
1168             }
1169             else if (!IS_EMPTY(p))
1170             {
1171                 break;
1172             }
1173             c += g_iRDeltas[u];
1174         }
1175         u++;
1176     }
1177     while(0 != g_iRDeltas[u]);
1178 }
1179
1180
1181 void
1182 GenerateQueen(IN MOVE_STACK *pStack,
1183               IN POSITION *pos,
1184               IN COOR cQueen)
1185 /**
1186
1187 Routine description:
1188
1189     This routine is called by GenerateMoves' JumpTable in order to
1190     generate pseudo-legal moves for the queen at position cQueen.
1191
1192 Parameters:
1193
1194     MOVE_STACK *pStack : the move stack
1195     POSITION *pos : the board position
1196     COOR cQueen : the queen's location
1197
1198 Return value:
1199
1200     void
1201
1202 **/
1203 {
1204     COOR c;
1205     ULONG u = 0;
1206     PIECE p;
1207
1208     ASSERT(IS_QUEEN(pos->rgSquare[cQueen].pPiece));
1209     ASSERT(GET_COLOR(pos->rgSquare[cQueen].pPiece) == pos->uToMove);
1210     ASSERT(g_iQKDeltas[u] != 0);
1211
1212     do
1213     {
1214         c = cQueen + g_iQKDeltas[u];
1215         while(IS_ON_BOARD(c))
1216         {
1217             p = pos->rgSquare[c].pPiece;
1218             if (IS_EMPTY(p))
1219             {
1220                 _AddNormalMove(pStack, pos, cQueen, c, 0);
1221             }
1222             else
1223             {
1224                 if (OPPOSITE_COLORS(p, pos->uToMove))
1225                 {
1226                     _AddNormalMove(pStack, pos, cQueen, c, p);
1227                 }
1228                 break;
1229             }
1230             c += g_iQKDeltas[u];
1231         }
1232         u++;
1233     }
1234     while(0 != g_iQKDeltas[u]);
1235 }
1236
1237
1238 void
1239 SaveMeQueen(IN MOVE_STACK *pStack,
1240             IN POSITION *pos,
1241             IN COOR cQueen,
1242             IN COOR cKing,
1243             IN COOR cAttacker)
1244 /**
1245
1246 Routine description:
1247
1248     This routine is called by code in GenerateEscapes in order to
1249     generate moves by the queen at square cQueen that alleviate check
1250     on the friendly king at square cKing.  The lone enemy piece that
1251     is checking the king is sitting on square cAttacker.
1252
1253 Parameters:
1254
1255     MOVE_STACK *pStack : the move stack
1256     POSITION *pos : the board position
1257     COOR cQueen : the queen's location
1258     COOR cKing : the friendly king's location
1259     COOR cAttacker : the attacker's location
1260
1261 Return value:
1262
1263     void
1264
1265 **/
1266 {
1267     COOR c;
1268     COOR cExposed;
1269     int iAttackDelta = DIRECTION_BETWEEN_SQUARES(cAttacker, cKing);
1270     ULONG u = 0;
1271     PIECE p;
1272
1273     ASSERT(InCheck(pos, pos->uToMove));
1274     ASSERT(IS_QUEEN(pos->rgSquare[cQueen].pPiece));
1275     ASSERT(GET_COLOR(pos->rgSquare[cQueen].pPiece) == pos->uToMove);
1276     ASSERT(GET_COLOR(pos->rgSquare[cQueen].pPiece) == pos->uToMove);
1277     ASSERT(GET_COLOR(pos->rgSquare[cQueen].pPiece) ==
1278            GET_COLOR(pos->rgSquare[cKing].pPiece));
1279     ASSERT(OPPOSITE_COLORS(pos->rgSquare[cAttacker].pPiece,
1280                            pos->rgSquare[cKing].pPiece));
1281     ASSERT(g_iQKDeltas[u] != 0);
1282
1283     do
1284     {
1285         c = cQueen + g_iQKDeltas[u];
1286         while(IS_ON_BOARD(c))
1287         {
1288             p = pos->rgSquare[c].pPiece;
1289             if ((c == cAttacker) || BLOCKS_THE_CHECK(c))
1290             {
1291                 ASSERT(!p ||
1292                        OPPOSITE_COLORS(p, pos->rgSquare[cQueen].pPiece));
1293                 ASSERT(!p || (c == cAttacker));
1294                 cExposed = ExposesCheck(pos, cQueen, cKing);
1295                 if (!IS_ON_BOARD(cExposed) || (cExposed == c))
1296                 {
1297                     _AddNormalMove(pStack, pos, cQueen, c, p);
1298                     break;
1299                 }
1300             }
1301             else if (!IS_EMPTY(p))
1302             {
1303                 break;
1304             }
1305             c += g_iQKDeltas[u];
1306         }
1307         u++;
1308     }
1309     while(0 != g_iQKDeltas[u]);
1310 }
1311
1312 void
1313 GenerateBlackKing(IN MOVE_STACK *pStack,
1314                   IN POSITION *pos,
1315                   IN COOR cKing)
1316 /**
1317
1318 Routine description:
1319
1320     This function is called by GenerateMoves in order to generate
1321     pseudo-legal moves for the black king at square cKing.  Note: this
1322     function often generates illegal castling moves and relies on the
1323     MakeMove code to decide about the legality of the castle.
1324
1325 Parameters:
1326
1327     MOVE_STACK *pStack : the move stack
1328     POSITION *pos : the board position
1329     COOR cKing : the king location
1330
1331 Return value:
1332
1333     void
1334
1335 **/
1336 {
1337     COOR c;
1338     ULONG u = 0;
1339     PIECE p;
1340
1341     ASSERT(IS_KING(pos->rgSquare[cKing].pPiece));
1342     ASSERT(GET_COLOR(pos->rgSquare[cKing].pPiece) == pos->uToMove);
1343     ASSERT(g_iQKDeltas[u] != 0);
1344
1345     do
1346     {
1347         c = cKing + g_iQKDeltas[u];
1348         u++;
1349         if (IS_ON_BOARD(c))
1350         {
1351             p = pos->rgSquare[c].pPiece;
1352
1353             //
1354             // This logical OR replaced with bitwise OR; the effect is
1355             // the same the the bitwise is marginally faster.
1356             //
1357             if (IS_EMPTY(p) | (GET_COLOR(p)))
1358             {
1359                 _AddNormalMove(pStack, pos, cKing, c, p);
1360             }
1361         }
1362     }
1363     while(0 != g_iQKDeltas[u]);
1364
1365     if ((pos->bvCastleInfo & BLACK_CAN_CASTLE) == 0) return;
1366 #ifdef DEBUG
1367     p = pos->rgSquare[E8].pPiece;
1368     ASSERT(IS_KING(p));
1369     ASSERT(cKing == E8);
1370 #endif
1371
1372     //
1373     // Note: no castling through check is enforced at the time the
1374     // move is played.  This is a "pseudo-legal" move when generated.
1375     //
1376     if ((pos->bvCastleInfo & CASTLE_BLACK_SHORT) &&
1377         (IS_EMPTY(pos->rgSquare[G8].pPiece)) &&
1378         (IS_EMPTY(pos->rgSquare[F8].pPiece)))
1379     {
1380         ASSERT(pos->rgSquare[H8].pPiece == BLACK_ROOK);
1381         _AddCastle(pStack, pos, E8, G8);
1382     }
1383
1384     if ((pos->bvCastleInfo & CASTLE_BLACK_LONG) &&
1385         (IS_EMPTY(pos->rgSquare[C8].pPiece)) &&
1386         (IS_EMPTY(pos->rgSquare[D8].pPiece)) &&
1387         (IS_EMPTY(pos->rgSquare[B8].pPiece)))
1388     {
1389         ASSERT(pos->rgSquare[A8].pPiece == BLACK_ROOK);
1390         _AddCastle(pStack, pos, E8, C8);
1391     }
1392 }
1393
1394 //
1395 // N.B. There is no SaveYourselfBlackKing or SaveYourselfWhiteKing
1396 // because this functionality is built into phase 1 of
1397 // GenerateEscapes.
1398 //
1399
1400 void
1401 GenerateWhiteKing(IN MOVE_STACK *pStack,
1402                   IN POSITION *pos,
1403                   IN COOR cKing)
1404 /**
1405
1406 Routine description:
1407
1408     This function is called by GenerateMoves in order to generate
1409     pseudo-legal king moves by the white king at square cKing.  Note:
1410     it often generates illegal castling moves and relies on the code
1411     in MakeMove to determine the legality of castles.
1412
1413 Parameters:
1414
1415     MOVE_STACK *pStack : the move stack
1416     POSITION *pos : the board position
1417     COOR cKing : the king location
1418
1419 Return value:
1420
1421     void
1422
1423 **/
1424 {
1425     COOR c;
1426     ULONG u = 0;
1427     PIECE p;
1428
1429     ASSERT(IS_KING(pos->rgSquare[cKing].pPiece));
1430     ASSERT(GET_COLOR(pos->rgSquare[cKing].pPiece) == pos->uToMove);
1431     ASSERT(g_iQKDeltas[u] != 0);
1432
1433     do
1434     {
1435         c = cKing + g_iQKDeltas[u];
1436         u++;
1437         if (IS_ON_BOARD(c))
1438         {
1439             p = pos->rgSquare[c].pPiece;
1440
1441             //
1442             // Note: this test covers empty squares also -- it is just
1443             // testing that the low order bit (color bit) of p is zero
1444             // which is true for black pieces and empty squares.  This
1445             // is done for speed over readability.
1446             //
1447             if (GET_COLOR(p) == BLACK)
1448             {
1449                 ASSERT(IS_EMPTY(p) || (GET_COLOR(p) == BLACK));
1450                 _AddNormalMove(pStack, pos, cKing, c, p);
1451             }
1452         }
1453     }
1454     while(0 != g_iQKDeltas[u]);
1455
1456     if ((pos->bvCastleInfo & WHITE_CAN_CASTLE) == 0) return;
1457 #ifdef DEBUG
1458     p = pos->rgSquare[E1].pPiece;
1459     ASSERT(IS_KING(p));
1460     ASSERT(cKing == E1);
1461 #endif
1462
1463     //
1464     // Note: no castling through check is enforced at the time the
1465     // move is played.  This is a "pseudo-legal" move when generated.
1466     //
1467     if ((pos->bvCastleInfo & CASTLE_WHITE_SHORT) &&
1468         (IS_EMPTY(pos->rgSquare[G1].pPiece)) &&
1469         (IS_EMPTY(pos->rgSquare[F1].pPiece)))
1470     {
1471         ASSERT(pos->rgSquare[H1].pPiece == WHITE_ROOK);
1472         _AddCastle(pStack, pos, E1, G1);
1473     }
1474
1475     if ((pos->bvCastleInfo & CASTLE_WHITE_LONG) &&
1476         (IS_EMPTY(pos->rgSquare[C1].pPiece)) &&
1477         (IS_EMPTY(pos->rgSquare[B1].pPiece)) &&
1478         (IS_EMPTY(pos->rgSquare[D1].pPiece)))
1479     {
1480         ASSERT(pos->rgSquare[A1].pPiece == WHITE_ROOK);
1481         _AddCastle(pStack, pos, E1, C1);
1482     }
1483 }
1484
1485
1486 void
1487 GenerateWhitePawn(IN MOVE_STACK *pStack,
1488                   IN POSITION *pos,
1489                   IN COOR cPawn)
1490 /**
1491
1492 Routine description:
1493
1494     This function is called by GenerateMoves in order to generate
1495     pseudo-legal pawn moves by the pawn at cPawn.  It handles
1496     en passant captures, double jumps, promotions, etc...
1497
1498 Parameters:
1499
1500     MOVE_STACK *pStack : the move stack
1501     POSITION *pos : the board position
1502     COOR cPawn : the pawn's location
1503
1504 Return value:
1505
1506     void
1507
1508 **/
1509 {
1510     ULONG uRank = RANK(cPawn);
1511     PIECE p;
1512     COOR cTo;
1513
1514     ASSERT(IS_PAWN(pos->rgSquare[cPawn].pPiece));
1515     ASSERT(GET_COLOR(pos->rgSquare[cPawn].pPiece) == pos->uToMove);
1516     ASSERT((RANK(cPawn) >= 2) && (RANK(cPawn) <= 7));
1517
1518     if (uRank != 7)
1519     {
1520         cTo = cPawn - 16;
1521         if (IS_EMPTY(pos->rgSquare[cTo].pPiece))
1522         {
1523             _AddNormalMove(pStack, pos, cPawn, cTo, 0);
1524             if (uRank == 2)
1525             {
1526                 cTo = cPawn - 32;
1527                 if (IS_EMPTY(pos->rgSquare[cTo].pPiece))
1528                 {
1529                     _AddDoubleJump(pStack, pos, cPawn, cTo);
1530                 }
1531             }
1532         }
1533         cTo = cPawn - 15;
1534         if (IS_ON_BOARD(cTo))
1535         {
1536             if (cTo == pos->cEpSquare)
1537             {
1538                 _AddEnPassant(pStack, pos, cPawn, cTo);
1539             }
1540             p = pos->rgSquare[cTo].pPiece;
1541
1542             //
1543             // This logical AND replaced with bitwise AND; the effect
1544             // is the same the the bitwise is marginally faster.
1545             //
1546             if (!IS_EMPTY(p) & (GET_COLOR(p) == BLACK))
1547             {
1548                 _AddNormalMove(pStack, pos, cPawn, cTo, p);
1549             }
1550         }
1551         cTo = cPawn - 17;
1552         if (IS_ON_BOARD(cTo))
1553         {
1554             if (cTo == pos->cEpSquare)
1555             {
1556                 _AddEnPassant(pStack, pos, cPawn, cTo);
1557             }
1558             p = pos->rgSquare[cTo].pPiece;
1559
1560             //
1561             // This logical AND replaced with bitwise AND; the effect
1562             // is the same the the bitwise is marginally faster.
1563             //
1564             if (!IS_EMPTY(p) & (GET_COLOR(p) == BLACK))
1565             {
1566                 _AddNormalMove(pStack, pos, cPawn, cTo, p);
1567             }
1568         }
1569     }
1570     else
1571     {
1572         ASSERT(RANK7(cPawn));
1573         cTo = cPawn - 16;
1574         if (IS_EMPTY(pos->rgSquare[cTo].pPiece))
1575         {
1576             _AddPromote(pStack, pos, cPawn, cTo);
1577         }
1578         cTo = cPawn - 15;
1579         if (IS_ON_BOARD(cTo))
1580         {
1581             p = pos->rgSquare[cTo].pPiece;
1582
1583             //
1584             // This logical AND replaced with bitwise AND; the effect
1585             // is the same the the bitwise is marginally faster.
1586             //
1587             if (!IS_EMPTY(p) & (GET_COLOR(p) == BLACK))
1588             {
1589                 _AddPromote(pStack, pos, cPawn, cTo);
1590             }
1591         }
1592         cTo = cPawn - 17;
1593         if (IS_ON_BOARD(cTo))
1594         {
1595             p = pos->rgSquare[cTo].pPiece;
1596
1597             //
1598             // This logical AND replaced with bitwise AND; the effect
1599             // is the same the the bitwise is marginally faster.
1600             //
1601             if (!IS_EMPTY(p) & (GET_COLOR(p) == BLACK))
1602             {
1603                 _AddPromote(pStack, pos, cPawn, cTo);
1604             }
1605         }
1606     }
1607 }
1608
1609
1610 void
1611 SaveMeWhitePawn(IN MOVE_STACK *pStack,
1612                 IN POSITION *pos,
1613                 IN COOR cPawn,
1614                 IN COOR cKing,
1615                 IN COOR cAttacker)
1616 /**
1617
1618 Routine description:
1619
1620     This function is called by the GenerateEscapes code in order to
1621     ask for a pawn's help in alleviating check on the king at square
1622     cKing.  The lone attacker to said king is on square cAttacker.
1623
1624 Parameters:
1625
1626     MOVE_STACK *pStack : the move stack
1627     POSITION *pos : the board position
1628     COOR cPawn : the pawn's location
1629     COOR cKing : the friendly king's location
1630     COOR cAttacker : the location of the lone checker to the king
1631
1632 Return value:
1633
1634     void
1635
1636 **/
1637 {
1638     ULONG uRank = RANK(cPawn);
1639     PIECE p;
1640     COOR cTo;
1641     COOR cExposed;
1642     int iAttackDelta = DIRECTION_BETWEEN_SQUARES(cAttacker, cKing);
1643
1644     ASSERT(InCheck(pos, pos->uToMove));
1645     ASSERT(IS_PAWN(pos->rgSquare[cPawn].pPiece));
1646     ASSERT(GET_COLOR(pos->rgSquare[cPawn].pPiece) == WHITE);
1647     ASSERT(GET_COLOR(pos->rgSquare[cPawn].pPiece) == pos->uToMove);
1648     ASSERT(GET_COLOR(pos->rgSquare[cPawn].pPiece) == pos->uToMove);
1649     ASSERT(GET_COLOR(pos->rgSquare[cPawn].pPiece) ==
1650            GET_COLOR(pos->rgSquare[cKing].pPiece));
1651     ASSERT(OPPOSITE_COLORS(pos->rgSquare[cAttacker].pPiece,
1652                            pos->rgSquare[cKing].pPiece));
1653     ASSERT((RANK(cPawn) >= 2) && (RANK(cPawn) <= 7));
1654
1655     if (uRank != 7)
1656     {
1657         cTo = cPawn - 16;
1658         if (IS_EMPTY(pos->rgSquare[cTo].pPiece))
1659         {
1660             if (BLOCKS_THE_CHECK(cTo) &&
1661                 !IS_ON_BOARD(ExposesCheck(pos, cPawn, cKing)))
1662             {
1663                     _AddNormalMove(pStack, pos, cPawn, cTo, 0);
1664             }
1665
1666             if (uRank == 2)
1667             {
1668                 cTo = cPawn - 32;
1669                 if (IS_EMPTY(pos->rgSquare[cTo].pPiece) &&
1670                     BLOCKS_THE_CHECK(cTo) &&
1671                     !IS_ON_BOARD(ExposesCheck(pos, cPawn, cKing)))
1672                 {
1673                     _AddDoubleJump(pStack, pos, cPawn, cTo);
1674                 }
1675             }
1676         }
1677
1678         cTo = cPawn - 15;
1679         if (cTo == cAttacker)
1680         {
1681             cExposed = ExposesCheck(pos, cPawn, cKing);
1682             if (!IS_ON_BOARD(cExposed) || (cExposed == cAttacker))
1683             {
1684                 p = pos->rgSquare[cTo].pPiece;
1685                 ASSERT(!IS_EMPTY(p));
1686                 ASSERT(GET_COLOR(p) == BLACK);
1687                 ASSERT(IS_ON_BOARD(cTo));
1688                 _AddNormalMove(pStack, pos, cPawn, cTo, p);
1689             }
1690         }
1691
1692         //
1693         // N.B. There is no possible way to block check with an
1694         // en-passant capture because by definition the last move made
1695         // by the other side was the pawn double jump.  So only handle
1696         // if the double jumping enemy pawn is the attacker and we can
1697         // kill it en passant.
1698         //
1699         if ((cTo == pos->cEpSquare) && (cAttacker == cTo + 16))
1700         {
1701             _AddEnPassant(pStack, pos, cPawn, cTo);
1702         }
1703
1704         cTo = cPawn - 17;
1705         if (cTo == cAttacker)
1706         {
1707             cExposed = ExposesCheck(pos, cPawn, cKing);
1708             if (!IS_ON_BOARD(cExposed) || (cExposed == cAttacker))
1709             {
1710                 p = pos->rgSquare[cTo].pPiece;
1711                 ASSERT(!IS_EMPTY(p));
1712                 ASSERT(GET_COLOR(p) == BLACK);
1713                 ASSERT(IS_ON_BOARD(cTo));
1714                 _AddNormalMove(pStack, pos, cPawn, cTo, p);
1715             }
1716         }
1717         if ((cTo == pos->cEpSquare) && (cAttacker == cTo + 16))
1718         {
1719             _AddEnPassant(pStack, pos, cPawn, cTo);
1720         }
1721     }
1722     else
1723     {
1724         ASSERT(RANK7(cPawn));
1725         cTo = cPawn - 16;
1726         if (BLOCKS_THE_CHECK(cTo) && IS_EMPTY(pos->rgSquare[cTo].pPiece))
1727         {
1728             _AddPromote(pStack, pos, cPawn, cTo);
1729         }
1730
1731         cTo = cPawn - 15;
1732         if (cTo == cAttacker)
1733         {
1734             cExposed = ExposesCheck(pos, cPawn, cKing);
1735             if (!IS_ON_BOARD(cExposed) || (cExposed == cAttacker))
1736             {
1737                 p = pos->rgSquare[cTo].pPiece;
1738                 ASSERT(!IS_EMPTY(p));
1739                 ASSERT(GET_COLOR(p) == BLACK);
1740                 ASSERT(IS_ON_BOARD(cTo));
1741                 _AddPromote(pStack, pos, cPawn, cTo);
1742             }
1743         }
1744
1745         cTo = cPawn - 17;
1746         if (cTo == cAttacker)
1747         {
1748             cExposed = ExposesCheck(pos, cPawn, cKing);
1749             if (!IS_ON_BOARD(cExposed) || (cExposed == cAttacker))
1750             {
1751                 p = pos->rgSquare[cTo].pPiece;
1752                 ASSERT(!IS_EMPTY(p));
1753                 ASSERT(GET_COLOR(p) == BLACK);
1754                 ASSERT(IS_ON_BOARD(cTo));
1755                 _AddPromote(pStack, pos, cPawn, cTo);
1756             }
1757         }
1758     }
1759 }
1760
1761
1762 void
1763 GenerateBlackPawn(IN MOVE_STACK *pStack,
1764                   IN POSITION *pos,
1765                   IN COOR cPawn)
1766 /**
1767
1768 Routine description:
1769
1770     This code is called by GenerateMoves in order to handle move
1771     generation for the black pawn on square cPawn.  It handles
1772     en passant captures, double jumps, and promotion.
1773
1774 Parameters:
1775
1776     MOVE_STACK *pStack : the move stack
1777     POSITION *pos : the position
1778     COOR cPawn : the pawn location
1779
1780 Return value:
1781
1782     void
1783
1784 **/
1785 {
1786     ULONG uRank = RANK(cPawn);
1787     PIECE p;
1788     COOR cTo;
1789
1790     ASSERT(IS_PAWN(pos->rgSquare[cPawn].pPiece));
1791     ASSERT(GET_COLOR(pos->rgSquare[cPawn].pPiece) == pos->uToMove);
1792     ASSERT((RANK(cPawn) >= 2) && (RANK(cPawn) <= 7));
1793
1794     if (uRank != 2)
1795     {
1796         cTo = cPawn + 16;
1797         if (IS_EMPTY(pos->rgSquare[cTo].pPiece))
1798         {
1799             _AddNormalMove(pStack, pos, cPawn, cTo, 0);
1800             if (uRank == 7)
1801             {
1802                 cTo = cPawn + 32;
1803                 if (IS_EMPTY(pos->rgSquare[cTo].pPiece))
1804                 {
1805                     _AddDoubleJump(pStack, pos, cPawn, cTo);
1806                 }
1807             }
1808         }
1809         cTo = cPawn + 15;
1810         if (IS_ON_BOARD(cTo))
1811         {
1812             if (cTo == pos->cEpSquare)
1813             {
1814                 _AddEnPassant(pStack, pos, cPawn, cTo);
1815             }
1816             p = pos->rgSquare[cTo].pPiece;
1817
1818             //
1819             // This logical AND replaced with bitwise AND; the effect
1820             // is the same the the bitwise is marginally faster.
1821             //
1822             if (!IS_EMPTY(p) & (GET_COLOR(p)))
1823             {
1824                 _AddNormalMove(pStack, pos, cPawn, cTo, p);
1825             }
1826         }
1827         cTo = cPawn + 17;
1828         if (IS_ON_BOARD(cTo))
1829         {
1830             if (cTo == pos->cEpSquare)
1831             {
1832                 _AddEnPassant(pStack, pos, cPawn, cTo);
1833             }
1834             p = pos->rgSquare[cTo].pPiece;
1835
1836             //
1837             // This logical AND replaced with bitwise AND; the effect
1838             // is the same the the bitwise is marginally faster.
1839             //
1840             if (!IS_EMPTY(p) & (GET_COLOR(p)))
1841             {
1842                 _AddNormalMove(pStack, pos, cPawn, cTo, p);
1843             }
1844         }
1845     }
1846     else
1847     {
1848         ASSERT(RANK2(cPawn));
1849         cTo = cPawn + 16;
1850         if (IS_EMPTY(pos->rgSquare[cTo].pPiece))
1851         {
1852             _AddPromote(pStack, pos, cPawn, cTo);
1853         }
1854         cTo = cPawn + 15;
1855         if (IS_ON_BOARD(cTo))
1856         {
1857             p = pos->rgSquare[cTo].pPiece;
1858
1859             //
1860             // This logical AND replaced with bitwise AND; the effect
1861             // is the same the the bitwise is marginally faster.
1862             //
1863             if (!IS_EMPTY(p) & (GET_COLOR(p)))
1864             {
1865                 _AddPromote(pStack, pos, cPawn, cTo);
1866             }
1867         }
1868         cTo = cPawn + 17;
1869         if (IS_ON_BOARD(cTo))
1870         {
1871             p = pos->rgSquare[cTo].pPiece;
1872
1873             //
1874             // This logical AND replaced with bitwise AND; the effect
1875             // is the same the the bitwise is marginally faster.
1876             //
1877             if (!IS_EMPTY(p) & (GET_COLOR(p)))
1878             {
1879                 _AddPromote(pStack, pos, cPawn, cTo);
1880             }
1881         }
1882     }
1883 }
1884
1885
1886 void
1887 SaveMeBlackPawn(IN MOVE_STACK *pStack,
1888                 IN POSITION *pos,
1889                 IN COOR cPawn,
1890                 IN COOR cKing,
1891                 IN COOR cAttacker)
1892 /**
1893
1894 Routine description:
1895
1896     This code is called to ask for a black pawn's help in alleviating
1897     check to its king.  The pawn is on square cPawn.  The friendly
1898     king is on square cKing.  The lone enemy piece attacking it is on
1899     square cAttacker.
1900
1901 Parameters:
1902
1903     MOVE_STACK *pStack : the move stack
1904     POSITION *pos : the board position
1905     COOR cPawn : the pawn location
1906     COOR cKing : the friendly king location
1907     COOR cAttacker : the lone checker location
1908
1909 Return value:
1910
1911     void
1912
1913 **/
1914 {
1915     ULONG uRank = RANK(cPawn);
1916     PIECE p;
1917     COOR cTo;
1918     COOR cExposed;
1919     int iAttackDelta = DIRECTION_BETWEEN_SQUARES(cAttacker, cKing);
1920
1921     ASSERT(InCheck(pos, pos->uToMove));
1922     ASSERT(IS_PAWN(pos->rgSquare[cPawn].pPiece));
1923     ASSERT(GET_COLOR(pos->rgSquare[cPawn].pPiece) == BLACK);
1924     ASSERT(GET_COLOR(pos->rgSquare[cPawn].pPiece) == pos->uToMove);
1925     ASSERT(GET_COLOR(pos->rgSquare[cPawn].pPiece) == pos->uToMove);
1926     ASSERT(GET_COLOR(pos->rgSquare[cPawn].pPiece) ==
1927            GET_COLOR(pos->rgSquare[cKing].pPiece));
1928     ASSERT(OPPOSITE_COLORS(pos->rgSquare[cAttacker].pPiece,
1929                            pos->rgSquare[cKing].pPiece));
1930     ASSERT((RANK(cPawn) >= 2) && (RANK(cPawn) <= 7));
1931
1932     if (uRank != 2)
1933     {
1934         cTo = cPawn + 16;
1935         if (IS_EMPTY(pos->rgSquare[cTo].pPiece))
1936         {
1937             if (BLOCKS_THE_CHECK(cTo) &&
1938                 !IS_ON_BOARD(ExposesCheck(pos, cPawn, cKing)))
1939             {
1940                 _AddNormalMove(pStack, pos, cPawn, cTo, 0);
1941             }
1942
1943             if (uRank == 7)
1944             {
1945                 cTo = cPawn + 32;
1946                 if (IS_EMPTY(pos->rgSquare[cTo].pPiece) &&
1947                     BLOCKS_THE_CHECK(cTo) &&
1948                     !IS_ON_BOARD(ExposesCheck(pos, cPawn, cKing)))
1949                 {
1950                     _AddDoubleJump(pStack, pos, cPawn, cTo);
1951                 }
1952             }
1953         }
1954
1955         cTo = cPawn + 15;
1956         if (cTo == cAttacker)
1957         {
1958             cExposed = ExposesCheck(pos, cPawn, cKing);
1959             if (!IS_ON_BOARD(cExposed) || (cExposed == cAttacker))
1960             {
1961                 p = pos->rgSquare[cTo].pPiece;
1962                 ASSERT(!IS_EMPTY(p));
1963                 ASSERT(GET_COLOR(p) == WHITE);
1964                 ASSERT(IS_ON_BOARD(cTo));
1965                 _AddNormalMove(pStack, pos, cPawn, cTo, p);
1966             }
1967         }
1968
1969         //
1970         // N.B. There is no possible way to block check with an
1971         // en-passant capture because by definition the last move made
1972         // by the other side was the pawn double jump.  So only handle
1973         // if the double jumping enemy pawn is the attacker and we can
1974         // kill it en passant.
1975         //
1976         if ((cTo == pos->cEpSquare) &&
1977             (cAttacker == cTo - 16))
1978         {
1979             _AddEnPassant(pStack, pos, cPawn, cTo);
1980         }
1981
1982         cTo = cPawn + 17;
1983         if (cTo == cAttacker)
1984         {
1985             cExposed = ExposesCheck(pos, cPawn, cKing);
1986             if (!IS_ON_BOARD(cExposed) || (cExposed == cAttacker))
1987             {
1988                 p = pos->rgSquare[cTo].pPiece;
1989                 ASSERT(!IS_EMPTY(p));
1990                 ASSERT(GET_COLOR(p) == WHITE);
1991                 ASSERT(IS_ON_BOARD(cTo));
1992                 _AddNormalMove(pStack, pos, cPawn, cTo, p);
1993             }
1994         }
1995         if ((cTo == pos->cEpSquare) &&
1996             (cAttacker == cTo - 16))
1997         {
1998             _AddEnPassant(pStack, pos, cPawn, cTo);
1999         }
2000     }
2001     else
2002     {
2003         ASSERT(RANK2(cPawn));
2004         cTo = cPawn + 16;
2005         if (BLOCKS_THE_CHECK(cTo) &&
2006             IS_EMPTY(pos->rgSquare[cTo].pPiece))
2007         {
2008             _AddPromote(pStack, pos, cPawn, cTo);
2009         }
2010
2011         cTo = cPawn + 15;
2012         if (cTo == cAttacker)
2013         {
2014             cExposed = ExposesCheck(pos, cPawn, cKing);
2015             if (!IS_ON_BOARD(cExposed) || (cExposed == cAttacker))
2016             {
2017                 p = pos->rgSquare[cTo].pPiece;
2018                 ASSERT(!IS_EMPTY(p));
2019                 ASSERT(GET_COLOR(p) == WHITE);
2020                 ASSERT(IS_ON_BOARD(cTo));
2021                 _AddPromote(pStack, pos, cPawn, cTo);
2022             }
2023         }
2024
2025         cTo = cPawn + 17;
2026         if (cTo == cAttacker)
2027         {
2028             cExposed = ExposesCheck(pos, cPawn, cKing);
2029             if (!IS_ON_BOARD(cExposed) || (cExposed == cAttacker))
2030             {
2031                 p = pos->rgSquare[cTo].pPiece;
2032                 ASSERT(!IS_EMPTY(p));
2033                 ASSERT(GET_COLOR(p) == WHITE);
2034                 ASSERT(IS_ON_BOARD(cTo));
2035                 _AddPromote(pStack, pos, cPawn, cTo);
2036             }
2037         }
2038     }
2039 }
2040
2041
2042 void
2043 InvalidGenerator(IN UNUSED MOVE_STACK *pStack,
2044                  IN UNUSED POSITION *pos,
2045                  IN UNUSED COOR cPawn)
2046 /**
2047
2048 Routine description:
2049
2050     If you'd like to make a call, please hang up and try your call
2051     again...
2052
2053 Parameters:
2054
2055     IN UNUSED MOVE_STACK *pStack,
2056     IN UNUSED POSITION *pos,
2057     IN UNUSED COOR cPawn
2058
2059 Return value:
2060
2061     void
2062
2063 **/
2064 {
2065     UtilPanic(SHOULD_NOT_GET_HERE,
2066               NULL, NULL, NULL, NULL,
2067               __FILE__, __LINE__);
2068 }
2069
2070
2071 void
2072 InvalidSaveMe(IN UNUSED MOVE_STACK *pStack,
2073               IN UNUSED POSITION *pos,
2074               IN UNUSED COOR cPawn,
2075               IN UNUSED COOR cKing,
2076               IN UNUSED COOR cAttacker)
2077 /**
2078
2079 Routine description:
2080
2081     ...if you need help, please dial the operator.
2082
2083 Parameters:
2084
2085     IN UNUSED MOVE_STACK *pStack,
2086     IN UNUSED POSITION *pos,
2087     IN UNUSED COOR cPawn,
2088     IN UNUSED COOR cKing,
2089     IN UNUSED COOR cAttacker
2090
2091 Return value:
2092
2093     void
2094
2095 **/
2096 {
2097     UtilPanic(SHOULD_NOT_GET_HERE,
2098               NULL, NULL, NULL, NULL,
2099               __FILE__, __LINE__);
2100 }
2101
2102
2103 static void
2104 _GenerateAllMoves(IN MOVE_STACK *pStack,
2105                   IN POSITION *pos)
2106 /**
2107
2108 Routine description:
2109
2110     This code generates all pseudo-legal moves in a position.  Please
2111     see notes at the top of this module for details.
2112
2113 Parameters:
2114
2115     MOVE_STACK *pStack : the move stack
2116     POSITION *pos : the board position
2117
2118 Return value:
2119
2120     static void
2121
2122 **/
2123 {
2124     COOR c;
2125     static void (*JumpTable[])(MOVE_STACK *, POSITION *, COOR) =
2126     {
2127         InvalidGenerator,                     // EMPTY
2128         InvalidGenerator,                     // EMPTY | WHITE
2129         InvalidGenerator,                     // 2  (BLACK_PAWN)
2130         InvalidGenerator,                     // 3  (WHITE_PAWN)
2131         GenerateKnight,                       // 4  (BLACK_KNIGHT)
2132         GenerateWhiteKnight,                  // 5  (WHITE_KNIGHT)
2133         GenerateBishop,                       // 6  (BLACK_BISHOP)
2134         GenerateBishop,                       // 7  (WHITE_BISHOP)
2135         GenerateRook,                         // 8  (BLACK_ROOK)
2136         GenerateRook,                         // 9  (WHITE_ROOK)
2137         GenerateQueen,                        // 10 (BLACK_QUEEN)
2138         GenerateQueen,                        // 11 (WHITE_QUEEN)
2139         GenerateBlackKing,                    // 12 (BLACK_KING)
2140         GenerateWhiteKing                     // 13 (WHITE_KING)
2141     };
2142     ULONG u;
2143 #ifdef DEBUG
2144     PIECE p;
2145 #endif
2146
2147     for(u = pos->uNonPawnCount[pos->uToMove][0] - 1;
2148         u != (ULONG)-1;
2149         u--)
2150     {
2151         c = pos->cNonPawns[pos->uToMove][u];
2152 #ifdef DEBUG
2153         ASSERT(IS_ON_BOARD(c));
2154         p = pos->rgSquare[c].pPiece;
2155         ASSERT(!IS_EMPTY(p));
2156         ASSERT(!IS_PAWN(p));
2157         ASSERT(GET_COLOR(p) == pos->uToMove);
2158 #endif
2159         (JumpTable[pos->rgSquare[c].pPiece])(pStack, pos, c);
2160     }
2161
2162     if (pos->uToMove == BLACK)
2163     {
2164         for(u = 0; u < pos->uPawnCount[BLACK]; u++)
2165         {
2166             c = pos->cPawns[BLACK][u];
2167 #ifdef DEBUG
2168             ASSERT(IS_ON_BOARD(c));
2169             p = pos->rgSquare[c].pPiece;
2170             ASSERT(!IS_EMPTY(p));
2171             ASSERT(IS_PAWN(p));
2172             ASSERT(GET_COLOR(p) == pos->uToMove);
2173 #endif
2174             GenerateBlackPawn(pStack, pos, c);
2175         }
2176     } else {
2177         ASSERT(pos->uToMove == WHITE);
2178         for(u = 0; u < pos->uPawnCount[WHITE]; u++)
2179         {
2180             c = pos->cPawns[WHITE][u];
2181 #ifdef DEBUG
2182             ASSERT(IS_ON_BOARD(c));
2183             p = pos->rgSquare[c].pPiece;
2184             ASSERT(!IS_EMPTY(p));
2185             ASSERT(IS_PAWN(p));
2186             ASSERT(GET_COLOR(p) == pos->uToMove);
2187 #endif
2188             GenerateWhitePawn(pStack, pos, c);
2189         }
2190     }
2191 }
2192
2193
2194
2195 static ULONG
2196 _GenerateEscapes(IN MOVE_STACK *pStack,
2197                  IN POSITION *pos)
2198 /**
2199
2200 Routine description:
2201
2202     This function is called when side to move is in check in order to
2203     generate pseudo-legal escapes from check.  All legal escapes from
2204     check are a subset of the moves returned by this function.  In
2205     general it's pretty good; the only bug I know about is that it
2206     will generate a capture that alleviates check where the capturing
2207     piece is pinned to the king (and thus the capture is illegal).
2208     The purpose of this function is to allow the search to detect when
2209     there is one legal reply to check and possibly extend.
2210
2211 Parameters:
2212
2213     MOVE_STACK *pStack : the move stack
2214     POSITION *pos : the board
2215
2216 Return value:
2217
2218     ULONG : the number of pieces checking the king
2219
2220 **/
2221 {
2222     ULONG u;
2223     ULONG v;
2224     COOR c;
2225     COOR cDefender;
2226     PIECE p;
2227     PIECE pKing;
2228     COOR cKing = pos->cNonPawns[pos->uToMove][0];
2229     int iIndex;
2230     SEE_LIST rgCheckers;
2231     int iDelta;
2232     ULONG uReturn = 0;
2233     static void (*JumpTable[])
2234         (MOVE_STACK *, POSITION *, COOR, COOR, COOR) =
2235     {
2236         InvalidSaveMe,                        // EMPTY
2237         InvalidSaveMe,                        // EMPTY | WHITE
2238         InvalidSaveMe,                        // 2  (BLACK_PAWN)
2239         InvalidSaveMe,                        // 3  (WHITE_PAWN)
2240         SaveMeKnight,                         // 4  (BLACK_KNIGHT)
2241         SaveMeKnight,                         // 5  (WHITE_KNIGHT)
2242         SaveMeBishop,                         // 6  (BLACK_BISHOP)
2243         SaveMeBishop,                         // 7  (WHITE_BISHOP)
2244         SaveMeRook,                           // 8  (BLACK_ROOK)
2245         SaveMeRook,                           // 9  (WHITE_ROOK)
2246         SaveMeQueen,                          // 10 (BLACK_QUEEN)
2247         SaveMeQueen,                          // 11 (WHITE_QUEEN)
2248         InvalidSaveMe,                        // kings already considered
2249         InvalidSaveMe                         // kings already considered
2250     };
2251
2252     ASSERT(IS_KING(pos->rgSquare[cKing].pPiece));
2253     ASSERT(TRUE == InCheck(pos, pos->uToMove));
2254
2255     //
2256     // Use the SEE function GetAttacks to find out how many pieces are
2257     // giving check and from whence.  Note: we don't sort rgCheckers
2258     // here; maybe it would be worth trying.  In any event it
2259     // shouldn't be affected by treating the list as a minheap
2260     // vs. as a sorted list.
2261     //
2262     GetAttacks(&rgCheckers, pos, cKing, FLIP(pos->uToMove));
2263     ASSERT(rgCheckers.uCount > 0);
2264     ASSERT(rgCheckers.uCount < 17);
2265     uReturn = rgCheckers.uCount;
2266
2267     //
2268     // Phase I: See if the king can flee or take the checking piece.
2269     //
2270     pKing = pos->rgSquare[cKing].pPiece;
2271     ASSERT(GET_COLOR(pKing) == pos->uToMove);
2272     ASSERT(IS_KING(pKing));
2273     ASSERT(OPPOSITE_COLORS(pKing, rgCheckers.data[0].pPiece));
2274     u = 0;
2275     while(0 != g_iQKDeltas[u])
2276     {
2277         c = cKing + g_iQKDeltas[u];
2278         u++;
2279         if (IS_ON_BOARD(c))
2280         {
2281             p = pos->rgSquare[c].pPiece;
2282
2283             //
2284             // This logical OR replaced with bitwise OR; the effect is
2285             // the same the the bitwise is marginally faster.
2286             //
2287             if (IS_EMPTY(p) | (OPPOSITE_COLORS(p, pKing)))
2288             {
2289                 if (FALSE == IsAttacked(c, pos, FLIP(pos->uToMove)))
2290                 {
2291                     //
2292                     // So we know the destination square is not under
2293                     // attack right now... but that could be because
2294                     // the present (pre-move) king position "blocks"
2295                     // the attack.  Detect this.
2296                     //
2297                     for (v = 0;
2298                          v < rgCheckers.uCount;
2299                          v++)
2300                     {
2301                         ASSERT(OPPOSITE_COLORS(pKing,
2302                                                rgCheckers.data[v].pPiece));
2303                         if (!IS_PAWN(rgCheckers.data[v].pPiece) &&
2304                             !IS_KNIGHT(rgCheckers.data[v].pPiece))
2305                         {
2306                             iIndex = (int)rgCheckers.data[v].cLoc -
2307                                      (int)cKing;
2308                             iDelta = CHECK_DELTA_WITH_INDEX(iIndex);
2309                             ASSERT(iDelta);
2310
2311                             iIndex = (int)rgCheckers.data[v].cLoc -
2312                                      (int)c;
2313                             if (iDelta == CHECK_DELTA_WITH_INDEX(iIndex))
2314                             {
2315                                 goto loop;
2316                             }
2317                         }
2318                     }
2319                     ASSERT(v == rgCheckers.uCount);
2320
2321                     //
2322                     // If we get here the square is not under attack
2323                     // and it does not contain our own piece.  It's
2324                     // either empty or contains an enemy piece.
2325                     //
2326                     ASSERT(!p || OPPOSITE_COLORS(pKing, p));
2327                     _AddNormalMove(pStack, pos, cKing, c, p);
2328                     uReturn += 0x00010000;
2329                 }
2330             }
2331         }
2332  loop:
2333         ;
2334     }
2335
2336     //
2337     // N.B. If there is more than one piece checking the king then
2338     // there is no way to escape check by blocking check with another
2339     // piece or capturing the offending piece.  The two attackers
2340     // cannot be on the same rank, file or diagonal because this would
2341     // depend on the previous position being illegal.
2342     //
2343     if (rgCheckers.uCount > 1)
2344     {
2345 #ifdef DEBUG
2346         //
2347         // Note: the above comment is correct but this assertion fails
2348         // on positions that we made up to run TestSearch.  Disabled
2349         // for now.
2350         //
2351 #if 0
2352         iDelta = DIRECTION_BETWEEN_SQUARES(rgCheckers.data[0].cLoc, cKing);
2353         for (v = 1; v < rgCheckers.uCount; v++)
2354         {
2355             if (DIRECTION_BETWEEN_SQUARES(rgCheckers.data[v].cLoc, cKing) !=
2356                 iDelta)
2357             {
2358                 break;
2359             }
2360         }
2361         ASSERT(v != rgCheckers.uCount);
2362 #endif
2363 #endif
2364         return(uReturn);
2365     }
2366
2367     //
2368     // Phase 2: If we get here there is a lone attacker causing check.
2369     // See if the other pieces can block the check or take the
2370     // checking piece.
2371     //
2372     c = rgCheckers.data[0].cLoc;
2373     for (u = 1;                               // don't consider the king
2374          u < pos->uNonPawnCount[pos->uToMove][0];
2375          u++)
2376     {
2377         cDefender = pos->cNonPawns[pos->uToMove][u];
2378         ASSERT(IS_ON_BOARD(cDefender));
2379         p = pos->rgSquare[cDefender].pPiece;
2380         ASSERT(p && !IS_PAWN(p));
2381         ASSERT(GET_COLOR(p) == pos->uToMove);
2382
2383         (JumpTable[p])(pStack, pos, cDefender, cKing, c);
2384     }
2385
2386     // Consider all pawns too
2387     if (pos->uToMove == BLACK)
2388     {
2389         for (u = 0; u < pos->uPawnCount[BLACK]; u++)
2390         {
2391             cDefender = pos->cPawns[BLACK][u];
2392 #ifdef DEBUG
2393             ASSERT(IS_ON_BOARD(cDefender));
2394             p = pos->rgSquare[cDefender].pPiece;
2395             ASSERT(p && IS_PAWN(p));
2396             ASSERT(GET_COLOR(p) == pos->uToMove);
2397 #endif
2398             SaveMeBlackPawn(pStack, pos, cDefender, cKing, c);
2399         }
2400     } else {
2401         ASSERT(pos->uToMove == WHITE);
2402         for (u = 0; u < pos->uPawnCount[WHITE]; u++)
2403         {
2404             cDefender = pos->cPawns[WHITE][u];
2405 #ifdef DEBUG
2406             ASSERT(IS_ON_BOARD(cDefender));
2407             p = pos->rgSquare[cDefender].pPiece;
2408             ASSERT(p && IS_PAWN(p));
2409             ASSERT(GET_COLOR(p) == pos->uToMove);
2410 #endif
2411             SaveMeWhitePawn(pStack, pos, cDefender, cKing, c);
2412         }
2413     }
2414     return(uReturn);
2415 }
2416
2417
2418 typedef struct _PRECOMP_KILLERS
2419 {
2420     MOVE mv;
2421     ULONG uBonus;
2422 }
2423 PRECOMP_KILLERS;
2424
2425 static void
2426 _ScoreAllMoves(IN MOVE_STACK *pStack,
2427                IN SEARCHER_THREAD_CONTEXT *ctx,
2428                IN MOVE mvHash)
2429 /**
2430
2431 Routine description:
2432
2433     We have just generated all the moves, now score them.  See comments
2434     inline below about order.
2435
2436 Parameters:
2437
2438     IN MOVE_STACK *pStack,
2439     IN SEARCHER_THREAD_CONTEXT *ctx,
2440     IN MOVE mvHash,
2441
2442 Return value:
2443
2444     static void
2445
2446 **/
2447 {
2448     ULONG uPly = ctx->uPly;
2449     POSITION *pos = &ctx->sPosition;
2450     ULONG u;
2451     MOVE mv;
2452     SCORE s;
2453     MOVE_STACK_MOVE_VALUE_FLAGS mvf;
2454     ULONG uHashMoveLoc = (ULONG)-1;
2455     ULONG uColor = pos->uToMove;
2456     PRECOMP_KILLERS sKillers[4];
2457     COOR cEnprise = GetEnprisePiece(pos, uColor);
2458
2459     //
2460     // We have generated all moves here.  We also know that we are not
2461     // escaping from check.  There can be a hash move -- if there is
2462     // then the search has already tried it and we should not generate
2463     // it again.
2464     //
2465     // White has 218 legal moves in this position:
2466     // 3Q4/1Q4Q1/4Q3/2Q4R/Q4Q2/3Q4/1Q4Rp/1K1BBNNk w - - 0 1
2467     //
2468
2469     //
2470     // Pre-populate killer/bonuses
2471     //
2472     sKillers[0].mv = ctx->mvKiller[uPly][0];
2473     sKillers[0].uBonus = FIRST_KILLER;
2474     sKillers[1].mv.uMove = sKillers[3].mv.uMove = 0;
2475     sKillers[2].mv = ctx->mvKiller[uPly][1];
2476     sKillers[2].uBonus = THIRD_KILLER;
2477     if (uPly > 1)
2478     {
2479         sKillers[1].mv = ctx->mvKiller[uPly - 2][0];
2480         sKillers[1].uBonus = SECOND_KILLER;
2481         sKillers[3].mv = ctx->mvKiller[uPly - 2][1];
2482         sKillers[3].uBonus = FOURTH_KILLER;
2483     }
2484     sKillers[0].uBonus |=
2485         (SORT_THESE_FIRST * (IS_KILLERMATE_MOVE(sKillers[0].mv) != 0));
2486     sKillers[1].uBonus |=
2487         (SORT_THESE_FIRST * (IS_KILLERMATE_MOVE(sKillers[1].mv) != 0));
2488     sKillers[2].uBonus |=
2489         (SORT_THESE_FIRST * (IS_KILLERMATE_MOVE(sKillers[2].mv) != 0));
2490     sKillers[3].uBonus |=
2491         (SORT_THESE_FIRST * (IS_KILLERMATE_MOVE(sKillers[3].mv) != 0));
2492
2493     //
2494     // Score moves
2495     //
2496     ASSERT(MOVE_COUNT(ctx, uPly) <= MAX_MOVES_PER_PLY);
2497     for (u = pStack->uBegin[uPly];
2498          u < pStack->uEnd[uPly];
2499          u++)
2500     {
2501         mv = pStack->mvf[u].mv;
2502         ASSERT(mv.uMove);
2503         ASSERT(GET_COLOR(mv.pMoved) == uColor);
2504         if (!IS_SAME_MOVE(mv, mvHash))
2505         {
2506 #ifdef DEBUG
2507             pStack->mvf[u].iValue = -MAX_INT;
2508             pStack->mvf[u].bvFlags = 0;
2509 #endif
2510             //
2511             // 1. Hash move (already handled by search, all we have to
2512             //               do here is not generate it)
2513             // 2. Killer mate move, if one exists
2514             // 3. Winning captures & promotions (MVV/LVA to tiebreak)
2515             // 4. Even captures & promotions -- >= SORT_THESE_FIRST
2516             // 5. Killer move 1-4
2517             // 6. "good" moves (moves away from danger etc...)
2518             // 7. Other non capture moves (using dynamic move ordering scheme)
2519             // 8. Losing captures -- <0
2520             //
2521
2522             //
2523             // Captures and promotions, use SEE
2524             //
2525             if (IS_CAPTURE_OR_PROMOTION(mv))
2526             {
2527                 ASSERT((mv.pCaptured) || (mv.pPromoted));
2528                 s = PIECE_VALUE(mv.pCaptured) -
2529                     PIECE_VALUE(mv.pMoved);
2530                 if ((s <= 0) || mv.pPromoted)
2531                 {
2532                     s = SEE(pos, mv);
2533                 }
2534
2535                 if (s >= 0)
2536                 {
2537                     s += PIECE_VALUE_OVER_100(mv.pCaptured) + 120;
2538                     s += PIECE_VALUE_OVER_100(mv.pPromoted);
2539                     s -= PIECE_VALUE_OVER_100(mv.pMoved);
2540                     s += SORT_THESE_FIRST;
2541
2542                     //
2543                     // IDEA: bonus for capturing opponent's last moved
2544                     // piece to encourage quicker fail highs?
2545                     //
2546                     ASSERT(s >= SORT_THESE_FIRST);
2547                     ASSERT(s > 0);
2548                     ASSERT((s & STRIP_OFF_FLAGS) < VALUE_KING);
2549                 }
2550 #ifdef DEBUG
2551                 else
2552                 {
2553                     ASSERT((s & STRIP_OFF_FLAGS) > -VALUE_KING);
2554                     s -= VALUE_KING;
2555                     ASSERT(s < 0);
2556                 }
2557 #endif
2558             }
2559
2560             //
2561             // Non-captures/promotes use history/killer
2562             //
2563             else
2564             {
2565                 ASSERT((!mv.pCaptured) && (!mv.pPromoted));
2566                 s = g_iPSQT[mv.pMoved][mv.cTo]; // 0..1000
2567                 s |= (IS_SAME_MOVE(sKillers[0].mv, mv) * sKillers[0].uBonus);
2568                 s |= (IS_SAME_MOVE(sKillers[1].mv, mv) * sKillers[1].uBonus);
2569                 s |= (IS_SAME_MOVE(sKillers[2].mv, mv) * sKillers[2].uBonus);
2570                 s |= (IS_SAME_MOVE(sKillers[3].mv, mv) * sKillers[3].uBonus);
2571                 s |= ((GOOD_MOVE + PIECE_VALUE(mv.pMoved) / 2) *
2572                       (mv.cFrom == cEnprise));
2573                 ASSERT(s >= 0);
2574             }
2575             pStack->mvf[u].iValue = s;
2576             ASSERT(pStack->mvf[u].iValue != -MAX_INT);
2577         }
2578         else
2579         {
2580             ASSERT(uHashMoveLoc == (ULONG)-1);
2581             uHashMoveLoc = u;
2582 #ifdef DEBUG
2583             ASSERT((mv.cFrom == mvHash.cFrom) && (mv.cTo == mvHash.cTo));
2584             pStack->mvf[u].bvFlags |= MVF_MOVE_SEARCHED;
2585 #endif
2586         }
2587
2588     } // next move
2589
2590     //
2591     // If we generated the hash move, stick it at the end and pretend
2592     // we didn't... it was already considered by the search and we
2593     // should not generate it again.
2594     //
2595     if (uHashMoveLoc != (ULONG)-1)
2596     {
2597         ASSERT(MOVE_COUNT(ctx, uPly) >= 1);
2598         ASSERT(uHashMoveLoc >= pStack->uBegin[uPly]);
2599         ASSERT(uHashMoveLoc < pStack->uEnd[uPly]);
2600         mvf = pStack->mvf[uHashMoveLoc];
2601         pStack->mvf[uHashMoveLoc] = pStack->mvf[pStack->uEnd[uPly] - 1];
2602 #ifdef DEBUG
2603         pStack->mvf[pStack->uEnd[uPly] - 1] = mvf;
2604 #endif
2605         pStack->uEnd[uPly]--;
2606     }
2607 }
2608
2609
2610
2611 static void
2612 _ScoreAllEscapes(IN MOVE_STACK *pStack,
2613                  IN SEARCHER_THREAD_CONTEXT *ctx,
2614                  IN MOVE mvHash)
2615 /**
2616
2617 Routine description:
2618
2619     We have just generated all the moves, now score them.  See comments
2620     inline below about order.
2621
2622 Parameters:
2623
2624     IN MOVE_STACK *pStack,
2625     IN SEARCHER_THREAD_CONTEXT *ctx,
2626     IN MOVE mvHash,
2627
2628 Return value:
2629
2630     static void
2631
2632 **/
2633 {
2634     ULONG uPly = ctx->uPly;
2635     POSITION *pos = &ctx->sPosition;
2636     ULONG u;
2637     MOVE mv;
2638     SCORE s;
2639     MOVE_STACK_MOVE_VALUE_FLAGS mvf;
2640     ULONG uHashMoveLoc = (ULONG)-1;
2641     COOR c;
2642     ULONG v;
2643     PIECE p;
2644     static SCORE _bonus[2][7] = {
2645         { 0, 2000, 1250, 1500, 1100, 850,  0 }, // friend
2646         { 0, 1600,  100,  100,   50,  -1, -1 }, // foe
2647     };
2648
2649     //
2650     // We have generated legal escapes from check here.  There can be
2651     // a hash move -- if there is then the search has already tried it
2652     // and we should not generate it again.
2653     //
2654
2655     ASSERT(MOVE_COUNT(ctx, uPly) <= MAX_MOVES_PER_PLY);
2656     for (u = pStack->uBegin[uPly];
2657          u < pStack->uEnd[uPly];
2658          u++)
2659     {
2660         mv = pStack->mvf[u].mv;
2661         ASSERT(mv.uMove);
2662         ASSERT(GET_COLOR(mv.pMoved) == pos->uToMove);
2663         if (!IS_SAME_MOVE(mv, mvHash))
2664         {
2665 #ifdef DEBUG
2666             pStack->mvf[u].iValue = -MAX_INT;
2667             pStack->mvf[u].bvFlags = 0;
2668 #endif
2669             pStack->mvf[u].mv.bvFlags |= MOVE_FLAG_ESCAPING_CHECK;
2670
2671             //
2672             // 1. Hash move (already handled by search, all we have to
2673             //               do here is not generate it)
2674             // 2. Winning captures by pieces other than the checked king
2675             // 3. Winning captures by the king
2676             // 4. Even captures by pieces other than the king
2677             // 5. Killer escapes
2678             // 6. Moves that block the check and are even
2679             // 7. King moves
2680             // 8. Losing captures / blocks
2681             //
2682
2683             //
2684             // Captures and promotions, use SEE
2685             //
2686             if (IS_CAPTURE_OR_PROMOTION(mv))
2687             {
2688                 ASSERT((mv.pCaptured) || (mv.pPromoted));
2689                 s = PIECE_VALUE(mv.pCaptured) -
2690                     PIECE_VALUE(mv.pMoved);
2691                 if ((s <= 0) || mv.pPromoted)
2692                 {
2693                     s = SEE(pos, mv);
2694                 }
2695
2696                 if (s > 0)
2697                 {
2698                     // Winning captures: take with pieces before with king
2699                     s += PIECE_VALUE_OVER_100(mv.pPromoted);
2700                     s -= PIECE_VALUE_OVER_100(mv.pMoved);
2701                     s >>= IS_KING(mv.pMoved);
2702                     s |= SORT_THESE_FIRST;
2703                     ASSERT(s >= SORT_THESE_FIRST);
2704                     ASSERT(s > 0);
2705                     ASSERT((s & STRIP_OFF_FLAGS) < VALUE_KING);
2706                 }
2707                 else if (s == 0)
2708                 {
2709                     // Even capture -- can't be capturing w/ king
2710                     ASSERT(!IS_KING(mv.pMoved));
2711                     s += PIECE_VALUE_OVER_100(mv.pPromoted) + 20;
2712                     s -= PIECE_VALUE_OVER_100(mv.pMoved);
2713                     s |= FIRST_KILLER;
2714                     ASSERT(s > 0);
2715                 }
2716 #ifdef DEBUG
2717                 else
2718                 {
2719                     // Losing capture
2720                     ASSERT(!IS_KING(mv.pMoved));
2721                     ASSERT((s & STRIP_OFF_FLAGS) > -VALUE_KING);
2722                     s -= VALUE_KING;
2723                     ASSERT(s < 0);
2724                 }
2725 #endif
2726             }
2727
2728             //
2729             // Non-captures/promotes
2730             //
2731             else
2732             {
2733                 ASSERT((!mv.pCaptured) && (!mv.pPromoted));
2734                 if (IS_SAME_MOVE(mv, ctx->mvKillerEscapes[uPly][0]) ||
2735                     IS_SAME_MOVE(mv, ctx->mvKillerEscapes[uPly][1]))
2736                 {
2737                     s = SECOND_KILLER;
2738                     ASSERT(s >= 0);
2739                 }
2740                 else
2741                 {
2742                     s = g_iPSQT[mv.pMoved][mv.cTo]; // 0..1000
2743                     if (!IS_KING(mv.pMoved))
2744                     {
2745                         // 0..2400
2746                         s += (VALUE_QUEEN - PIECE_VALUE(mv.pMoved)) * 4;
2747                         if (SEE(pos, mv) >= 0)
2748                         {
2749                             // Non-losing block of check
2750                             ASSERT(SEE(pos, mv) == 0);
2751                             s |= THIRD_KILLER;
2752                             ASSERT(s >= 0);
2753                         }
2754                         else
2755                         {
2756                             // Losing block of check
2757                             s -= VALUE_KING;
2758                             ASSERT(s < 0);
2759                         }
2760                     }
2761                     else
2762                     {
2763                         // If the king is fleeing, encourage a spot next
2764                         // to friendly pieces.
2765                         v = 0;
2766                         do {
2767                             c = mv.cTo + g_iQKDeltas[v++];
2768                             if (IS_ON_BOARD(c))
2769                             {
2770                                 p = pos->rgSquare[c].pPiece;
2771                                 s += _bonus[OPPOSITE_COLORS(pos->uToMove, p)]
2772                                            [PIECE_TYPE(p)];
2773                                 ASSERT(_bonus[OPPOSITE_COLORS(pos->uToMove, p)]
2774                                        [PIECE_TYPE(p)] >= 0);
2775                             }
2776                         }
2777                         while(g_iQKDeltas[v] != 0);
2778                     }
2779                 }
2780             }
2781             pStack->mvf[u].iValue = s;
2782             ASSERT(pStack->mvf[u].iValue != -MAX_INT);
2783         }
2784         else
2785         {
2786             ASSERT(uHashMoveLoc == (ULONG)-1);
2787             uHashMoveLoc = u;
2788 #ifdef DEBUG
2789             ASSERT((mv.cFrom == mvHash.cFrom) && (mv.cTo == mvHash.cTo));
2790             pStack->mvf[u].bvFlags |= MVF_MOVE_SEARCHED;
2791 #endif
2792         }
2793     } // next move
2794
2795     //
2796     // If we generated the hash move, stick it at the end and pretend
2797     // we didn't... it was already considered by the search and we
2798     // should not generate it again.
2799     //
2800     if (uHashMoveLoc != (ULONG)-1)
2801     {
2802         ASSERT(MOVE_COUNT(ctx, uPly) >= 1);
2803         ASSERT(uHashMoveLoc >= pStack->uBegin[uPly]);
2804         ASSERT(uHashMoveLoc < pStack->uEnd[uPly]);
2805         mvf = pStack->mvf[uHashMoveLoc];
2806         pStack->mvf[uHashMoveLoc] = pStack->mvf[pStack->uEnd[uPly] - 1];
2807 #ifdef DEBUG
2808         pStack->mvf[pStack->uEnd[uPly] - 1] = mvf;
2809 #endif
2810         pStack->uEnd[uPly]--;
2811     }
2812 }
2813
2814
2815
2816 static void
2817 _ScoreQSearchMovesInclChecks(IN MOVE_STACK *pStack,
2818                              IN SEARCHER_THREAD_CONTEXT *ctx)
2819 /**
2820
2821 Routine description:
2822
2823     We have just generated all the moves.  We were called from the
2824     Qsearch so:
2825
2826        1. Unlike _ScoreAllMoves we don't have to think about a hash move
2827        2. QSearch only cares about winning/even captures/promotes and
2828           checking moves.
2829
2830     Like _ScoreSearchMoves, this function takes "hints" from the
2831     searcher context about what squares are in danger and tries to
2832     order moves away from those squares sooner.  Unlike
2833     _ScoreSearchMoves this function also attempts to capture enemies
2834     that are in danger sooner.
2835
2836 Parameters:
2837
2838     IN MOVE_STACK *pStack,
2839     IN SEARCHER_THREAD_CONTEXT *ctx
2840
2841 Return value:
2842
2843     static void
2844
2845 **/
2846 {
2847     register POSITION *pos = &ctx->sPosition;
2848     PLY_INFO *pi = &ctx->sPlyInfo[ctx->uPly];
2849     ULONG uPly = ctx->uPly;
2850     ULONG u, uColor = pos->uToMove;
2851     MOVE mv;
2852     MOVE mvLast = (pi-1)->mv;
2853     SCORE s;
2854     COOR cEnprise = GetEnprisePiece(pos, uColor);
2855
2856     //
2857     // We have generate all moves or just legal escapes from check
2858     // here.  There can be a hash move -- if there is then the search
2859     // has already tried it and we should not generate it again.
2860     //
2861     // White has 218 legal moves in this position:
2862     // 3Q4/1Q4Q1/4Q3/2Q4R/Q4Q2/3Q4/1Q4Rp/1K1BBNNk w - - 0 1
2863     //
2864     ASSERT(MOVE_COUNT(ctx, uPly) <= MAX_MOVES_PER_PLY);
2865     ASSERT(uPly >= 1);
2866
2867     for (u = pStack->uBegin[uPly];
2868          u < pStack->uEnd[uPly];
2869          u++)
2870     {
2871         mv = pStack->mvf[u].mv;
2872         ASSERT(GET_COLOR(mv.pMoved) == uColor);
2873 #ifdef DEBUG
2874         pStack->mvf[u].iValue = -MAX_INT;
2875         pStack->mvf[u].bvFlags = 0;
2876 #endif
2877         pStack->mvf[u].mv.bvFlags |= WouldGiveCheck(ctx, mv);
2878
2879         //
2880         // 1. There can't be a hash move so don't worry about it
2881         // 2. Winning captures & promotions
2882         // 3. Even captures & promotions -- >= SORT_THESE_FIRST
2883         // 4. Checking non-capture moves
2884         // 5. Losing captures that check -- > 0
2885         // 6. Everything else is ignored -- <= 0
2886         //
2887
2888         //
2889         // Captures and promotions, use SEE
2890         //
2891         if (IS_CAPTURE_OR_PROMOTION(mv))
2892         {
2893             ASSERT((mv.pCaptured) || (mv.pPromoted));
2894             s = PIECE_VALUE(mv.pCaptured) -
2895                 PIECE_VALUE(mv.pMoved);
2896             if ((s <= 0) || mv.pPromoted)
2897             {
2898                 s = SEE(pos, mv);
2899             }
2900
2901             if (s >= 0)
2902             {
2903                 //
2904                 // Winning / even captures / promotes should be >=
2905                 // SORT_THESE_FIRST.
2906                 //
2907                 s += PIECE_VALUE_OVER_100(mv.pCaptured) + 120;
2908                 s += PIECE_VALUE_OVER_100(mv.pPromoted);
2909                 s -= PIECE_VALUE_OVER_100(mv.pMoved);
2910                 s += SORT_THESE_FIRST;
2911
2912                 //
2913                 // Bonus if it checks too
2914                 //
2915                 s += (pStack->mvf[u].mv.bvFlags & MOVE_FLAG_CHECKING) * 4;
2916
2917                 //
2918                 // Bonus for capturing last moved enemy piece.
2919                 //
2920                 s += (mv.cTo == mvLast.cTo) * 64;
2921                 ASSERT(s >= SORT_THESE_FIRST);
2922                 ASSERT(s > 0);
2923             }
2924             else
2925             {
2926                 //
2927                 // Make losing captures into either zero scores or
2928                 // slightly positive if they check.  Qsearch is going
2929                 // to bail as soon as it sees the first zero so no
2930                 // need to keep real SEE scores on these.
2931                 //
2932                 s = (pStack->mvf[u].mv.bvFlags & MOVE_FLAG_CHECKING);
2933                 ASSERT(s >= 0);
2934             }
2935         }
2936
2937         //
2938         // Non-captures/promotes -- we don't care unless they check
2939         //
2940         else
2941         {
2942             s = (pStack->mvf[u].mv.bvFlags & MOVE_FLAG_CHECKING) * 2;
2943             ASSERT(s >= 0);
2944             ASSERT(s < SORT_THESE_FIRST);
2945         }
2946
2947         //
2948         // If this move moves a piece that was in danger, consider it
2949         // sooner.
2950         //
2951         if (s > 0)
2952         {
2953             ASSERT(IS_CAPTURE_OR_PROMOTION(pStack->mvf[u].mv) ||
2954                    IS_CHECKING_MOVE(pStack->mvf[u].mv));
2955             s += (mv.cFrom == cEnprise) * (PIECE_VALUE(mv.pMoved) / 4);
2956             ASSERT(s > 0);
2957         }
2958         pStack->mvf[u].iValue = s;
2959         ASSERT(pStack->mvf[u].iValue != -MAX_INT);
2960
2961     } // next move
2962 }
2963
2964
2965 static void
2966 _ScoreQSearchMovesNoChecks(IN MOVE_STACK *pStack,
2967                            IN SEARCHER_THREAD_CONTEXT *ctx)
2968 /**
2969
2970 Routine description:
2971
2972     We have just generated all the moves.  We were called from the
2973     Qsearch so:
2974
2975        1. Unlike _ScoreAllMoves we don't have to think about a hash move
2976        2. QSearch only cares about winning/even captures/promotes.  At
2977           this point it is so deep that it doesn't even care about
2978           checks.
2979
2980     Like _ScoreSearchMoves, this function takes "hints" from the
2981     searcher context about what squares are in danger and tries to
2982     order moves away from those squares sooner.  Unlike
2983     _ScoreSearchMoves this function also attempts to capture enemies
2984     that are in danger sooner.
2985
2986 Parameters:
2987
2988     IN MOVE_STACK *pStack,
2989     IN SEARCHER_THREAD_CONTEXT *ctx
2990
2991 Return value:
2992
2993     static void
2994
2995 **/
2996 {
2997     register POSITION *pos = &(ctx->sPosition);
2998     ULONG uPly = ctx->uPly;
2999     ULONG u, uColor;
3000     MOVE mv;
3001     SCORE s;
3002
3003     //
3004     // We have generate all moves or just legal escapes from check
3005     // here.  There can be a hash move -- if there is then the search
3006     // has already tried it and we should not generate it again.
3007     //
3008     // White has 218 legal moves in this position:
3009     // 3Q4/1Q4Q1/4Q3/2Q4R/Q4Q2/3Q4/1Q4Rp/1K1BBNNk w - - 0 1
3010     //
3011     ASSERT(MOVE_COUNT(ctx, uPly) <= MAX_MOVES_PER_PLY);
3012
3013     uColor = pos->uToMove;
3014     for (u = pStack->uBegin[uPly];
3015          u < pStack->uEnd[uPly];
3016          u++)
3017     {
3018         mv = pStack->mvf[u].mv;
3019         ASSERT(GET_COLOR(mv.pMoved) == uColor);
3020 #ifdef DEBUG
3021         pStack->mvf[u].iValue = -MAX_INT;
3022         pStack->mvf[u].bvFlags = 0;
3023 #endif
3024         //
3025         // 1. There can't be a hash move so don't worry about it
3026         // 2. Winning captures & promotions
3027         // 3. Even captures & promotions -- >= SORT_THESE_FIRST
3028         // 4. Everything else is ignored -- <= 0
3029         //
3030
3031         //
3032         // Captures and promotions, use SEE
3033         //
3034         s = 0;
3035         if (IS_CAPTURE_OR_PROMOTION(mv))
3036         {
3037             ASSERT((mv.pCaptured) || (mv.pPromoted));
3038             s = PIECE_VALUE(mv.pCaptured) -
3039                 PIECE_VALUE(mv.pMoved);
3040             //
3041             // TODO: how does this handle positions like K *p *k ?
3042             //
3043             if (s <= 0)
3044             {
3045                 s = SEE(pos, mv);
3046             }
3047
3048             if (s >= 0)
3049             {
3050                 //
3051                 // Winning / even captures / promotes should be >=
3052                 // SORT_THESE_FIRST.
3053                 //
3054                 s += PIECE_VALUE_OVER_100(mv.pCaptured) + 120;
3055                 s += PIECE_VALUE_OVER_100(mv.pPromoted);
3056                 s -= PIECE_VALUE_OVER_100(mv.pMoved);
3057                 s += SORT_THESE_FIRST;
3058
3059                 //
3060                 // IDEA: bonus for capturing an enprise enemy piece?
3061                 //
3062                 ASSERT(s >= SORT_THESE_FIRST);
3063                 ASSERT(s > 0);
3064             }
3065         }
3066         pStack->mvf[u].iValue = s;
3067         ASSERT(pStack->mvf[u].iValue != -MAX_INT);
3068
3069     } // next move
3070 }
3071
3072
3073
3074 void
3075 GenerateMoves(IN SEARCHER_THREAD_CONTEXT *ctx,
3076               IN MOVE mvHash,
3077               IN ULONG uType)
3078 /**
3079
3080 Routine description:
3081
3082     This is the entrypoint to the move generator.  It invokes the
3083     requested generation code which push moves onto the move stack in
3084     ctx.  Once the moves are generated this code optionally will score
3085     the moves.
3086
3087 Parameters:
3088
3089     SEARCHER_THREAD_CONTEXT *ctx : a searcher thread's context
3090
3091         IN: ctx->sPosition.uDangerCount and ctx->sPosition.cDanger
3092             data is used to tweak move scoring.  This data MUST be
3093             consistent with the state of the current board.
3094
3095        OUT: ctx->sMoveStack.uBegin[ctx->uPly] is set,
3096             ctx->sMoveStack.uEnd[ctx->uPly] is set,
3097             ctx->sMoveStack.mvf[begin..end] are populated
3098
3099     MOVE mvHash : the hash move to not generate
3100
3101     ULONG uType : what kind of moves to generate
3102
3103         GENERATE_ALL_MOVES : pseudo-legal generation of all moves;
3104             scored by _ScoreAllMoves.  Return value is count of moves
3105             generated.
3106
3107         GENERATE_ESCAPE: called when stm in check, generate evasions
3108             scored by _ScoreAllMoves.  Return value is special code;
3109             see inline comment below.
3110
3111         GENERATE_CAPTURES_PROMS_CHECKS: caps, promotions, and checks
3112             scored by _ScoreQSearchMoves.  Return value is count of
3113             moves generated.
3114
3115         GENERATE_CAPTURES_PROMS: caps, promotions.  Skip the checks.
3116
3117         GENERATE_DONT_SCORE: pseudo-legal generation of all moves;
3118             not scored to save time.  Return value always zero.
3119
3120 Return value:
3121
3122     void
3123
3124 **/
3125 {
3126     register ULONG uPly = ctx->uPly;
3127     MOVE_STACK *pStack = &ctx->sMoveStack;
3128     POSITION *pos = &ctx->sPosition;
3129     ULONG uReturn;
3130 #ifdef DEBUG
3131     POSITION board;
3132     ULONG u;
3133     MOVE mv;
3134     PIECE p;
3135
3136     ASSERT((uPly >= 0) && (uPly < MAX_PLY_PER_SEARCH));
3137     memcpy(&board, pos, sizeof(POSITION));
3138     memcpy(&(pStack->board[uPly]), pos, sizeof(POSITION));
3139
3140     //
3141     // Make sure the hash move makes sense (if provided)
3142     //
3143     if (mvHash.uMove)
3144     {
3145         p = pos->rgSquare[mvHash.cFrom].pPiece;
3146         ASSERT(p);
3147         ASSERT(GET_COLOR(p) == pos->uToMove);
3148         p = pos->rgSquare[mvHash.cTo].pPiece;
3149         ASSERT(!p || OPPOSITE_COLORS(p, pos->uToMove));
3150     }
3151 #endif
3152     pStack->uPly = uPly;
3153     pStack->uEnd[uPly] = pStack->uBegin[uPly];
3154     pStack->sGenFlags[uPly].uAllGenFlags = 0;
3155
3156     switch(uType)
3157     {
3158         case GENERATE_CAPTURES_PROMS_CHECKS:
3159             ASSERT(!InCheck(pos, pos->uToMove));
3160             ASSERT(mvHash.uMove == 0);
3161             _FindUnblockedSquares(pStack, pos);
3162             _GenerateAllMoves(pStack, pos);
3163             _ScoreQSearchMovesInclChecks(pStack, ctx);
3164             break;
3165         case GENERATE_CAPTURES_PROMS:
3166             ASSERT(!InCheck(pos, pos->uToMove));
3167             ASSERT(mvHash.uMove == 0);
3168             _FindUnblockedSquares(pStack, pos);
3169             _GenerateAllMoves(pStack, pos);
3170             _ScoreQSearchMovesNoChecks(pStack, ctx);
3171             break;
3172         case GENERATE_ALL_MOVES:
3173             ASSERT(!InCheck(pos, pos->uToMove));
3174             _FindUnblockedSquares(pStack, pos);
3175             _GenerateAllMoves(pStack, pos);
3176             _ScoreAllMoves(pStack, ctx, mvHash);
3177             uReturn = MOVE_COUNT(ctx, uPly);
3178             break;
3179         case GENERATE_ESCAPES:
3180             ASSERT(InCheck(pos, pos->uToMove));
3181             _FindUnblockedSquares(pStack, pos);
3182             uReturn = _GenerateEscapes(pStack, pos);
3183             ASSERT(uReturn);
3184             pStack->sGenFlags[uPly].uKingMoveCount = uReturn >> 16;
3185             pStack->sGenFlags[uPly].uCheckingPieces = uReturn & 0xFF;
3186             _ScoreAllEscapes(pStack, ctx, mvHash);
3187             break;
3188
3189         // Note: this is just for plytest / seetest.  Just generate
3190         // moves, do not score them.
3191         case GENERATE_DONT_SCORE:
3192             if (InCheck(pos, pos->uToMove))
3193             {
3194                 (void)_GenerateEscapes(pStack, pos);
3195                 for (uReturn = pStack->uBegin[uPly];
3196                      uReturn < pStack->uEnd[uPly];
3197                      uReturn++)
3198                 {
3199                     pStack->mvf[uReturn].mv.bvFlags |=
3200                         MOVE_FLAG_ESCAPING_CHECK;
3201                 }
3202             }
3203             else
3204             {
3205                 (void)_GenerateAllMoves(pStack, pos);
3206             }
3207             goto end;
3208 #ifdef DEBUG
3209         default:
3210             uReturn = 0;
3211             ASSERT(FALSE);
3212 #endif
3213     }
3214
3215 #ifdef DEBUG
3216     //
3217     // Sanity check the move list we just generated...
3218     //
3219     ASSERT(MOVE_COUNT(ctx, uPly) >= 0);
3220     for (u = pStack->uBegin[uPly];
3221          u < pStack->uEnd[uPly];
3222          u++)
3223     {
3224         mv = pStack->mvf[u].mv;
3225         ASSERT(!IS_SAME_MOVE(mv, mvHash));
3226         SanityCheckMove(pos, mv);
3227
3228         if (WouldGiveCheck(ctx, mv))
3229         {
3230             if (MakeMove(ctx, mv))
3231             {
3232                 ASSERT(ctx->uPly == (uPly + 1));
3233                 ASSERT(InCheck(pos, pos->uToMove));
3234                 UnmakeMove(ctx, mv);
3235
3236                 //
3237                 // Note: this is so that DEBUG and RELEASE builds search
3238                 // the same trees.  Without this the MakeMove/UnmakeMove
3239                 // pair here can affect the order of the pieces in the
3240                 // POSITION piece lists which in turn affects the order
3241                 // in which moves are generated down the road.
3242                 //
3243                 memcpy(&ctx->sPosition, &board, sizeof(POSITION));
3244             }
3245         }
3246         else
3247         {
3248             if (MakeMove(ctx, mv))
3249             {
3250                 ASSERT(ctx->uPly == (uPly + 1));
3251                 ASSERT(!InCheck(pos, pos->uToMove));
3252                 UnmakeMove(ctx, mv);
3253
3254                 //
3255                 // Note: this is so that DEBUG and RELEASE builds search
3256                 // the same trees.  Without this the MakeMove/UnmakeMove
3257                 // pair here can affect the order of the pieces in the
3258                 // POSITION piece lists which in turn affects the order
3259                 // in which moves are generated down the road.
3260                 //
3261                 memcpy(&ctx->sPosition, &board, sizeof(POSITION));
3262             }
3263         }
3264     }
3265     ASSERT(PositionsAreEquivalent(&board, pos));
3266 #endif
3267  end:
3268     pStack->sGenFlags[uPly].uMoveCount = MOVE_COUNT(ctx, uPly);
3269     pStack->uBegin[uPly + 1] = pStack->uEnd[uPly];
3270 }