src/see.c

   1 /**
   2
   3 Copyright (c) Scott Gasch
   4
   5 Module Name:
   6
   7     see.c
   8
   9 Abstract:
  10
  11     Static exchange evaluator and support code.  See also x86.asm.
  12
  13 Author:
  14
  15     Scott Gasch ([email protected]) 11 Jun 2004
  16
  17 Revision History:
  18
  19     $Id: see.c 348 2008-01-05 07:11:36Z scott $
  20
  21 **/
  22
  23 #include "chess.h"
  24
  25 #define ADD_ATTACKER(p, c, v) \
  26     pList->data[pList->uCount].pPiece = (p); \
  27     pList->data[pList->uCount].cLoc = (c);   \
  28     pList->data[pList->uCount].uVal = (v);   \
  29     pList->uCount++;
  30
  31 void CDECL
  32 SlowGetAttacks(IN OUT SEE_LIST *pList,
  33                IN POSITION *pos,
  34                IN COOR cSquare,
  35                IN ULONG uSide)
  36 /*++
  37
  38 Routine description:
  39
  40     SlowGetAttacks is the C version of GetAttacks; it should be
  41     identical to the GetAttacks code in x86.asm.  The job of the
  42     function is, given a position, square and side, to populate the
  43     SEE_LIST with the locations and types of enemy pieces attacking
  44     the square.
  45
  46 Parameters:
  47
  48     SEE_LIST *pList : list to populate
  49     POSITION *pos : the board
  50     COOR cSquare : square in question
  51     ULONG uSide : side we are looking for attacks from
  52
  53 Return value:
  54
  55     void
  56
  57 --*/
  58 {
  59     register ULONG x;
  60     PIECE p;
  61     COOR c;
  62     int iIndex;
  63     COOR cBlockIndex;
  64     int iDelta;
  65     static PIECE pPawn[2] = { BLACK_PAWN, WHITE_PAWN };
  66     static int iSeeDelta[2] = { -17, +15 };
  67
  68 #ifdef DEBUG
  69     ASSERT(IS_ON_BOARD(cSquare));
  70     ASSERT(IS_VALID_COLOR(uSide));
  71     VerifyPositionConsistency(pos, FALSE);
  72 #endif
  73     pList->uCount = 0;
  74
  75     //
  76     // Check for pawns attacking cSquare
  77     //
  78     c = cSquare + (iSeeDelta[uSide]);
  79     if (IS_ON_BOARD(c))
  80     {
  81         p = pos->rgSquare[c].pPiece;
  82         if (p == pPawn[uSide])
  83         {
  84             //
  85             // N.B. Don't use ADD_ATTACKER here because we know we're
  86             // at element zero.
  87             //
  88             pList->data[0].pPiece = p;
  89             pList->data[0].cLoc = c;
  90             pList->data[0].uVal = VALUE_PAWN;
  91             pList->uCount = 1;
  92         }
  93     }
  94
  95     c += 2;
  96     if (IS_ON_BOARD(c))
  97     {
  98         p = pos->rgSquare[c].pPiece;
  99         if (p == pPawn[uSide])
 100         {
 101             ADD_ATTACKER(p, c, VALUE_PAWN);
 102         }
 103     }
 104
 105     //
 106     // Check for pieces attacking cSquare
 107     //
 108     for (x = pos->uNonPawnCount[uSide][0] - 1;
 109          x != (ULONG)-1;
 110          x--)
 111     {
 112         c = pos->cNonPawns[uSide][x];
 113         ASSERT(IS_ON_BOARD(c));
 114
 115         p = pos->rgSquare[c].pPiece;
 116         ASSERT(p && !IS_PAWN(p));
 117         ASSERT(GET_COLOR(p) == uSide);
 118
 119         iIndex = (int)c - (int)cSquare;
 120         if (0 == (CHECK_VECTOR_WITH_INDEX(iIndex, GET_COLOR(p)) &
 121                   (1 << PIECE_TYPE(p))))
 122         {
 123             continue;
 124         }
 125
 126         if (IS_KNIGHT_OR_KING(p))
 127         {
 128             ASSERT(IS_KNIGHT(p) || IS_KING(p));
 129             ADD_ATTACKER(p, c, PIECE_VALUE(p));
 130             continue;
 131         }
 132
 133         //
 134         // Check to see if there is a piece in the path from cSquare
 135         // to c that blocks the attack.
 136         //
 137         iDelta = NEG_DELTA_WITH_INDEX(iIndex);
 138         ASSERT(iDelta == -1 * CHECK_DELTA_WITH_INDEX(iIndex));
 139         ASSERT(iDelta != 0);
 140         for (cBlockIndex = cSquare + iDelta;
 141              cBlockIndex != c;
 142              cBlockIndex += iDelta)
 143         {
 144             if (!IS_EMPTY(pos->rgSquare[cBlockIndex].pPiece))
 145             {
 146                 goto done;
 147             }
 148         }
 149
 150         //
 151         // Nothing in the way.
 152         //
 153         ADD_ATTACKER(p, c, PIECE_VALUE(p));
 154
 155  done:
 156         ;
 157     }
 158 }
 159
 160 #ifdef SEE_HEAPS
 161 //
 162 // SEE_HEAPS works great in principle but makes MinLegalPiece
 163 // inaccurate if the top of the heap is not a legal move (i.e. the
 164 // piece is pinned etc...)  When tested the result of this was minimal
 165 // and the use of a heap instead of a sorted list sped up the SEE
 166 // code.
 167 //
 168 #define PARENT(x)      ((x - 1) / 2)
 169 #define LEFT_CHILD(x)  (((x) * 2) + 1)
 170 #define RIGHT_CHILD(x) (((x) * 2) + 2)
 171
 172 #ifdef DEBUG
 173 static FLAG
 174 _IsValidHeap(IN SEE_LIST *p)
 175 /**
 176
 177 Routine description:
 178
 179     Is the minheap in SEE_LIST p->data[] valid (i.e. does it satisfy
 180     the minheap property?)
 181
 182 Parameters:
 183
 184     SEE_LIST *p : SEE_LIST to check
 185
 186 Return value:
 187
 188     static FLAG : TRUE if valid, FALSE otherwise
 189
 190 **/
 191 {
 192     ULONG u, l, r;
 193
 194     for (u = 0; u < p->uCount; u++)
 195     {
 196         l = LEFT_CHILD(u);
 197         if ((l < p->uCount) && (p->data[l].uVal < p->data[u].uVal))
 198         {
 199             return(FALSE);
 200         }
 201
 202         r = RIGHT_CHILD(u);
 203         if ((r < p->uCount) && (p->data[r].uVal < p->data[u].uVal))
 204         {
 205             return(FALSE);
 206         }
 207     }
 208     return(TRUE);
 209 }
 210 #endif // DEBUG
 211
 212
 213 static void
 214 _PushDown(IN OUT SEE_LIST *p,
 215           IN ULONG u)
 216 /**
 217
 218 Routine description:
 219
 220     Take heap node number u and compare its value with the value of
 221     its children.  Swap smallest value into position u and continue
 222     the push-down process if warranted.
 223
 224 Parameters:
 225
 226     SEE_LIST *p : SEE_LIST/minheap
 227     ULONG u : node number in consideration
 228
 229 Return value:
 230
 231     static void
 232
 233 **/
 234 {
 235     ULONG l = LEFT_CHILD(u);
 236     ULONG r;
 237     ULONG uSmallest;
 238     SEE_THREESOME temp;
 239
 240     //
 241     // The heap is a complete tree -- if there's no left child of this
 242     // node then there's no right child either.  If this is a leaf node
 243     // then our work is done.
 244     //
 245     ASSERT(p->uCount > 0);
 246     if (l >= p->uCount)
 247     {
 248         return;
 249     }
 250     ASSERT(PARENT(l) == u);
 251
 252     //
 253     // Otherwise, find the smallest of u, l and r.
 254     //
 255     r = l + 1;
 256     ASSERT(r == RIGHT_CHILD(u));
 257     ASSERT(PARENT(r) == u);
 258     ASSERT((r != u) && (r != l) && (l != u));
 259     uSmallest = u;
 260     if (p->data[l].uVal < p->data[u].uVal)
 261     {
 262         uSmallest = l;
 263     }
 264     if ((r < p->uCount) && (p->data[r].uVal < p->data[uSmallest].uVal))
 265     {
 266         uSmallest = r;
 267     }
 268
 269     //
 270     // If it's anything other than u, swap them and continue to push.
 271     //
 272     if (uSmallest != u)
 273     {
 274         ASSERT((uSmallest == l) || (uSmallest == r));
 275         temp = p->data[uSmallest];
 276         p->data[uSmallest] = p->data[u];
 277         p->data[u] = temp;
 278         _PushDown(p, uSmallest);
 279     }
 280 }
 281
 282 static void
 283 _BuildHeap(IN OUT SEE_LIST *p)
 284 /**
 285
 286 Routine description:
 287
 288     Convert a random array into a minheap.  Start at the first
 289     internal node and push it down into place.  Continue to work
 290     backwards until we get to the root (index 0).
 291
 292 Parameters:
 293
 294     SEE_LIST *p : list to heapify
 295
 296 Return value:
 297
 298     static void
 299
 300 **/
 301 {
 302     int iStart = (p->uCount / 2) - 1;
 303     int i;
 304
 305     ASSERT(iStart < (int)p->uCount);
 306     for (i = iStart; i > -1; i--)
 307     {
 308         ASSERT(i >= 0);
 309         _PushDown(p, (ULONG)i);
 310     }
 311     ASSERT(_IsValidHeap(p));
 312 }
 313
 314
 315 static void
 316 _BubbleUp(IN OUT SEE_LIST *p, IN ULONG u)
 317 /**
 318
 319 Routine description:
 320
 321     Take a node and bubble it up into place to re-create a minheap.
 322
 323 Parameters:
 324
 325     SEE_LIST *p : heap
 326     ULONG u : index of node to bubble up
 327
 328 Return value:
 329
 330     static void
 331
 332 **/
 333 {
 334     ULONG uParent;
 335     SEE_THREESOME temp;
 336
 337     ASSERT(p->uCount > 0);
 338     if (u == 0) return;
 339
 340     uParent = PARENT(u);
 341     ASSERT((LEFT_CHILD(uParent) == u) ||
 342            (RIGHT_CHILD(uParent) == u));
 343     ASSERT(uParent < u);
 344     if (p->data[uParent].uVal > p->data[u].uVal)
 345     {
 346         temp = p->data[uParent];
 347         p->data[uParent] = p->data[u];
 348         p->data[u] = temp;
 349         _BubbleUp(p, uParent);
 350     }
 351 }
 352
 353 #else // !SEE_HEAPS
 354
 355 static void
 356 _SortList(IN OUT SEE_LIST *pList)
 357 /**
 358
 359 Routine description:
 360
 361     Sort the SEE list by piece value with a selection sort.
 362
 363 Parameters:
 364
 365     SEE_LIST *pList
 366
 367 Return value:
 368
 369     static void
 370
 371 **/
 372 {
 373     ULONG x;
 374     ULONG y;
 375     register ULONG uMaxVal;
 376     register ULONG uMaxLoc;
 377     SEE_THREESOME sTemp;
 378
 379     for (x = 0;
 380          x < pList->uCount;
 381          x++)
 382     {
 383         //
 384         // Assume index X is the largest value item in the list
 385         //
 386         uMaxVal = pList->data[x].uVal;
 387         uMaxLoc = x;
 388
 389         //
 390         // Look for others with a larger value
 391         //
 392         for (y = x + 1;
 393              y < pList->uCount;
 394              y++)
 395         {
 396             if (pList->data[y].uVal > uMaxVal)
 397             {
 398                 uMaxVal = pList->data[y].uVal;
 399                 uMaxLoc = y;
 400             }
 401         }
 402
 403         sTemp = pList->data[uMaxLoc];
 404         pList->data[uMaxLoc] = pList->data[x];
 405         pList->data[x] = sTemp;
 406     }
 407 }
 408
 409 #endif
 410
 411 static void INLINE
 412 _RemoveItem(IN OUT SEE_LIST *pList,
 413             IN ULONG x)
 414 /**
 415
 416 Routine description:
 417
 418     Delete item x from the list.
 419
 420 Parameters:
 421
 422     SEE_LIST *pList,
 423     ULONG x
 424
 425 Return value:
 426
 427     static void INLINE
 428
 429 **/
 430 {
 431 #ifndef SEE_HEAPS
 432     ULONG y;
 433 #endif
 434
 435     ASSERT(x < pList->uCount);
 436     ASSERT(pList->uCount > 0);
 437
 438 #ifdef SEE_HEAPS
 439     //
 440     // Swap item x with the last thing on the heap and then push the
 441     // node back down.
 442     //
 443     if (x != (pList->uCount - 1))
 444     {
 445         pList->data[x] = pList->data[pList->uCount - 1];
 446         pList->uCount--;
 447         _PushDown(pList, 0);
 448     }
 449     else
 450     {
 451         pList->uCount--;
 452     }
 453
 454 #else // !SEE_HEAPS
 455
 456     //
 457     // If X is not the last thing in the list we will have to ripple
 458     // shift to close the hole.  This is rare.
 459     //
 460     for (y = x + 1;
 461          y < pList->uCount;
 462          y++)
 463     {
 464         pList->data[y - 1] = pList->data[y];
 465     }
 466     pList->uCount--;
 467
 468 #endif // SEE_HEAPS
 469 }
 470
 471
 472 static void
 473 _ClearPieceByLocation(IN OUT SEE_LIST *pList,
 474                       IN COOR cLoc)
 475 /**
 476
 477 Routine description:
 478
 479     Find a piece on the SEE list at COOR cLoc and delete it.
 480
 481 Parameters:
 482
 483     SEE_LIST *pList,
 484     COOR cLoc
 485
 486 Return value:
 487
 488     static void
 489
 490 **/
 491 {
 492     ULONG x = 0;
 493
 494     while (x < pList->uCount)
 495     {
 496         if (pList->data[x].cLoc == cLoc)
 497         {
 498             _RemoveItem(pList, x);
 499             return;
 500         }
 501         x++;
 502     }
 503
 504     //
 505     // This can happen if, for example, the SEE move was a passed pawn push
 506     //
 507 }
 508
 509
 510 #ifdef SEE_HEAPS
 511 static PIECE
 512 _MinLegalPiece(IN POSITION *pos,
 513                IN ULONG uColor,
 514                IN SEE_LIST *pList,
 515                IN SEE_LIST *pOther,
 516                IN COOR *pc,
 517                IN COOR cIgnore)
 518 /**
 519
 520 Routine description:
 521
 522     Return the piece from the SEE list with the lowest value that is
 523     not pinned to its own king.  Because we are storing the SEE_LISTS
 524     as heaps, this is only an approximate value in the event that the
 525     real min value piece is indeed pinned to its own king.  I
 526     considered sorting the list in this case but it seems like (in
 527     tests) this inaccuracy really has little or no impact on the
 528     search tree size.  The speedup with heaps instead of sorted lists
 529     seems worth the price.
 530
 531 Parameters:
 532
 533     POSITION *pos : the board
 534     ULONG uColor  : the color on move
 535     SEE_LIST *pList : the list we're selecting from
 536     SEE_LIST *pOther : the other side's list
 537     COOR *pc,
 538     COOR cIgnore
 539
 540 Return value:
 541
 542     static PIECE
 543
 544 **/
 545 {
 546     COOR cKing;
 547     PIECE p;
 548     register ULONG x;
 549     COOR c;
 550
 551     //
 552     // The list is a minheap with the min value piece at index 0.
 553     //
 554     for (x = 0;
 555          x < pList->uCount;
 556          x++)
 557     {
 558         p = pList->data[x].pPiece;
 559
 560         //
 561         // If this piece is the king, then no need to see if the move
 562         // exposes the king to check.. just play the move as long as
 563         // it's legal (i.e. no defenders to the square)
 564         //
 565         if (IS_KING(p))
 566         {
 567             if (pOther->uCount == 0)
 568             {
 569                 *pc = pList->data[0].cLoc;
 570
 571                 //
 572                 // Note: if p is a king and we allow them to play it then
 573                 // by definition the other side has nothing to counter
 574                 // with...  otherwise we'd be moving into check here.  So
 575                 // even if we had other pieces that were pinned to the
 576                 // king, empty out the list because we're done in the next
 577                 // SEE loop.
 578                 //
 579                 pList->uCount = 0;
 580                 return(p);
 581             }
 582         }
 583         else
 584         {
 585             //
 586             // Otherwise... consider pins.  If the least valuable
 587             // defender of the square cannot move because doing so
 588             // would exposes his king to check, skip it and try the
 589             // next least valuable.
 590             //
 591             cKing = pos->cNonPawns[uColor][0];
 592             c = ExposesCheck(pos, pList->data[x].cLoc, cKing);
 593
 594             //
 595             // cIgnore is the coordinate of the last piece the other
 596             // side "moved" in this capture sequence.  This is a hack
 597             // to ignore pins based on a piece that has already moved
 598             // in the computation but is already on the board.  This
 599             // of course does not work for positions where the piece
 600             // you expose check to was "moved" two turns ago but these
 601             // are pretty rare.
 602             //
 603             if (!IS_ON_BOARD(c) || (c == cIgnore))
 604             {
 605                 *pc = pList->data[x].cLoc;
 606                 _RemoveItem(pList, x);
 607                 return(p);
 608             }
 609         }
 610     }
 611
 612     //
 613     // There are no legal pieces to move to square
 614     //
 615     return(0);
 616 }
 617
 618 #else // !SEE_HEAPS
 619
 620 static PIECE
 621 _MinLegalPiece(IN POSITION *pos,
 622                IN ULONG uColor,
 623                IN SEE_LIST *pList,
 624                IN SEE_LIST *pOther,
 625                IN COOR *pc,
 626                IN COOR cIgnore)
 627 /**
 628
 629 Routine description:
 630
 631     Return the piece from the SEE list with the lowest value that is
 632     not pinned to its own king.
 633
 634 Parameters:
 635
 636     POSITION *pos : the board
 637     ULONG uColor  : the color on move
 638     SEE_LIST *pList : the list we're selecting from
 639     SEE_LIST *pOther : the other side's list
 640     COOR *pc,
 641     COOR cIgnore
 642
 643 Return value:
 644
 645     static PIECE
 646
 647 **/
 648 {
 649     COOR cKing;
 650     PIECE p;
 651     register ULONG x;
 652     COOR c;
 653
 654     //
 655     // The list is sorted from most valuable (index 0) to least valuable
 656     // (index N).  Begin at the least valuable and work up.
 657     //
 658     for (x = pList->uCount - 1;
 659          x != (ULONG)-1;
 660          x--)
 661     {
 662         p = pList->data[x].pPiece;
 663         //
 664         // If this piece is the king, then no need to see if the move
 665         // exposes the king to check.. just play the move as long as
 666         // it's legal (i.e. no defenders to the square)
 667         //
 668         if ((IS_KING(p)) && (pOther->uCount == 0))
 669         {
 670             ASSERT(x == 0);
 671             *pc = pList->data[0].cLoc;
 672             pList->uCount = 0;
 673             return(p);
 674         }
 675         else
 676         {
 677             //
 678             // Otherwise... consider pins.  If the least valuable
 679             // defender of the square cannot move because doing so
 680             // would exposes his king to check, skip it and try the
 681             // next least valuable.
 682             //
 683             cKing = pos->cNonPawns[uColor][0];
 684             c = ExposesCheck(pos, pList->data[x].cLoc, cKing);
 685
 686             //
 687             // cIgnore is the coordinate of the last piece the other
 688             // side "moved" in this capture sequence.  This is a hack
 689             // to ignore pins based on a piece that has already moved
 690             // in the computation but is already on the board.  This
 691             // of course does not work for positions where the piece
 692             // you expose check to was "moved" two turns ago but these
 693             // are pretty rare.
 694             //
 695             if (!IS_ON_BOARD(c) || (c == cIgnore))
 696             {
 697                 *pc = pList->data[x].cLoc;
 698                 _RemoveItem(pList, x);
 699                 return(p);
 700             }
 701         }
 702     }
 703
 704     //
 705     // There are no legal pieces to move to square
 706     //
 707     return(0);
 708 }
 709 #endif // SEE_HEAPS
 710
 711 static void _AddXRays(IN POSITION *pos,
 712                       IN INT iAttackerColor,
 713                       IN COOR cTarget,
 714                       IN COOR cObstacle,
 715                       IN OUT SEE_LIST *pAttacks,
 716                       IN OUT SEE_LIST *pDefends)
 717 /**
 718
 719 Routine description:
 720
 721     We just "moved" a piece in the SEE sequence... add any xray
 722     attacks that it exposed to the SEE list to be take part as the
 723     sequence plays out.
 724
 725 Parameters:
 726
 727     POSITION *pos,
 728     INT iAttackerColor,
 729     COOR cTarget,
 730     COOR cObstacle,
 731     SEE_LIST *pAttacks,
 732     SEE_LIST *pDefends
 733
 734 Return value:
 735
 736     static void
 737
 738 **/
 739 {
 740     int iDelta;
 741     COOR cIndex;
 742     PIECE xPiece;
 743     int iIndex;
 744
 745     iIndex = (int)cTarget - (int)cObstacle;
 746
 747     //
 748     // If there is no way for a queen sitting on the target square to
 749     // reach the obsticle square then there is no discovered attack.
 750     // (This could happen, for instance, if a knight captured.  It
 751     // can't uncover a new attack on the square where it took.
 752     //
 753     if (0 == (CHECK_VECTOR_WITH_INDEX(iIndex, BLACK) & (1 << QUEEN)))
 754     {
 755         return;
 756     }
 757
 758     //
 759     // The squares are on the same rank, file or diagonal.  iDelta is
 760     // the way to move from target towards obstacle.
 761     //
 762     iDelta = CHECK_DELTA_WITH_INDEX(iIndex);
 763
 764     //
 765     // Search for a piece that moves the right way to attack the target
 766     // square starting at the obstacle square + delta.
 767     //
 768     for (cIndex = cObstacle + iDelta;
 769          IS_ON_BOARD(cIndex);
 770          cIndex += iDelta)
 771     {
 772         xPiece = pos->rgSquare[cIndex].pPiece;
 773         if (!IS_EMPTY(xPiece))
 774         {
 775             //
 776             // Does it move the right way to hit cTarget?  TODO: can this
 777             // be optimized?  Remember pawns though...
 778             //
 779             if (0 != (CHECK_VECTOR_WITH_INDEX((int)cIndex - (int)cTarget,
 780                                               GET_COLOR(xPiece)) &
 781                       (1 << PIECE_TYPE(xPiece))))
 782             {
 783                 //
 784                 // Add this attacker to the proper SEE_LIST
 785                 //
 786                 if (GET_COLOR(xPiece) == iAttackerColor)
 787                 {
 788                     pAttacks->data[pAttacks->uCount].pPiece = xPiece;
 789                     pAttacks->data[pAttacks->uCount].cLoc = cIndex;
 790                     pAttacks->data[pAttacks->uCount].uVal =
 791                         PIECE_VALUE(xPiece);
 792                     pAttacks->uCount++;
 793                     ASSERT(pAttacks->uCount > 0);
 794 #ifdef SEE_HEAPS
 795                     _BubbleUp(pAttacks, pAttacks->uCount - 1);
 796 #else
 797                     _SortList(pAttacks);
 798 #endif
 799                 }
 800                 else
 801                 {
 802                     pDefends->data[pDefends->uCount].pPiece = xPiece;
 803                     pDefends->data[pDefends->uCount].cLoc = cIndex;
 804                     pDefends->data[pDefends->uCount].uVal =
 805                         PIECE_VALUE(xPiece);
 806                     pDefends->uCount++;
 807                     ASSERT(pDefends->uCount > 0);
 808 #ifdef SEE_HEAPS
 809                     _BubbleUp(pDefends, pDefends->uCount - 1);
 810 #else
 811                     _SortList(pDefends);
 812 #endif
 813                 }
 814             }
 815             return;
 816         }
 817     }
 818 }
 819
 820
 821 SCORE
 822 SEE(IN POSITION *pos,
 823     IN MOVE mv)
 824 /**
 825
 826 Routine description:
 827
 828     Given a board and a move on the board, estimate the value of the
 829     move by considering the friend/enemy pieces that attack the move's
 830     destination square.
 831
 832 Parameters:
 833
 834     POSITION *pos,
 835     MOVE mv
 836
 837 Return value:
 838
 839     SCORE : the estimate of the move's score
 840
 841 **/
 842 {
 843     SEE_LIST rgPieces[2];
 844     PIECE pPiece;
 845     ULONG uInPeril;
 846     SCORE rgiList[32];
 847     ULONG uListIndex;
 848     ULONG uWhoseTurn = GET_COLOR(mv.pMoved);
 849     ULONG uOrig = uWhoseTurn;
 850     int iSign = 1;
 851     ULONG uPromValue;
 852     ULONG uVal;
 853     COOR cFrom = mv.cFrom;
 854     static FLAG _Table[2][3] = {
 855         // a<b    a==b   a>b
 856         {  FALSE, FALSE,  TRUE   },  // uVal==0
 857         {  TRUE,  FALSE,  FALSE  },  // uVal==1
 858     };
 859
 860 #ifdef DEBUG
 861     ASSERT(mv.uMove != 0);
 862     memset(rgiList, 0xFF, sizeof(rgiList));
 863     memset(rgPieces, 0xFF, sizeof(rgPieces));
 864 #endif
 865
 866     //
 867     // Create a sorted list of pieces attacking and defending the
 868     // square.
 869     //
 870     GetAttacks(&(rgPieces[uWhoseTurn]), pos, mv.cTo, uWhoseTurn);
 871     GetAttacks(&(rgPieces[FLIP(uWhoseTurn)]), pos, mv.cTo, FLIP(uWhoseTurn));
 872 #ifdef SEE_HEAPS
 873     _BuildHeap(&(rgPieces[FLIP(uWhoseTurn)]));
 874     _BuildHeap(&(rgPieces[uWhoseTurn]));
 875 #else
 876     _SortList(&(rgPieces[FLIP(uWhoseTurn)]));
 877     _SortList(&(rgPieces[uWhoseTurn]));
 878 #endif
 879
 880     //
 881     // Play the first move -- TODO: the first move may be illegal...
 882     // fix this?
 883     //
 884     rgiList[0] = (PIECE_VALUE(mv.pCaptured) +
 885                   PIECE_VALUE(mv.pPromoted));
 886     uInPeril = (PIECE_VALUE(mv.pMoved) +
 887                 PIECE_VALUE(mv.pPromoted));
 888     uListIndex = 1;
 889
 890     _ClearPieceByLocation(&(rgPieces[uWhoseTurn]), mv.cFrom);
 891     _AddXRays(pos,
 892               uWhoseTurn,
 893               mv.cTo,
 894               mv.cFrom,
 895               &(rgPieces[uWhoseTurn]),
 896               &(rgPieces[FLIP(uWhoseTurn)]));
 897
 898     //
 899     // Play moves 2..n
 900     //
 901     do
 902     {
 903         //
 904         // Other side's turn now...
 905         //
 906         uWhoseTurn = FLIP(uWhoseTurn);
 907         iSign = -iSign;
 908         pPiece = _MinLegalPiece(pos,
 909                                 uWhoseTurn,
 910                                 &(rgPieces[uWhoseTurn]),
 911                                 &(rgPieces[FLIP(uWhoseTurn)]),
 912                                 &cFrom,
 913                                 cFrom);
 914         if (0 == pPiece) break;               // no legal piece
 915         //
 916         // If this is a pawn capturing and it ends on the queening
 917         // rank, set uPromValue appropriately.  Bitwise operators are
 918         // correct here, done for speed and branch removal; this loop
 919         // is pretty heavily used.
 920         //
 921         uPromValue = IS_PAWN(pPiece) & (RANK1(mv.cTo) | RANK8(mv.cTo));
 922         uPromValue *= VALUE_QUEEN;
 923         ASSERT((uPromValue == 0) || (uPromValue == VALUE_QUEEN));
 924
 925         ASSERT(uListIndex != 0);
 926         rgiList[uListIndex] = rgiList[uListIndex - 1] +
 927             iSign * (uInPeril + uPromValue);
 928         uListIndex++;
 929         ASSERT(uListIndex < ARRAY_LENGTH(rgiList));
 930         uInPeril = PIECE_VALUE(pPiece) + uPromValue;
 931
 932         _AddXRays(pos,
 933                   GET_COLOR(mv.pMoved),
 934                   mv.cTo,
 935                   cFrom,
 936                   &(rgPieces[uOrig]),        // These must be rgAttacks and
 937                   &(rgPieces[FLIP(uOrig)])); // rgDefends.  Not based on tomove
 938     }
 939     while(1);
 940
 941     //
 942     // The swaplist is now complete but we still must consider that either
 943     // side has the option of not taking (not continuing the exchange).
 944     //
 945     ASSERT(uListIndex >= 1);
 946     uListIndex--;
 947
 948     while (uListIndex > 0)
 949     {
 950         uVal = (uListIndex & 1);
 951         iSign = ((rgiList[uListIndex] > rgiList[uListIndex - 1]) -
 952                  (rgiList[uListIndex] < rgiList[uListIndex - 1])) + 1;
 953         ASSERT((iSign >= 0) && (iSign <= 2));
 954         if (TRUE == _Table[uVal][iSign])
 955         {
 956             rgiList[uListIndex - 1] = rgiList[uListIndex];
 957         }
 958         uListIndex--;
 959     }
 960
 961 #ifdef TEST_BROKEN
 962     iSign = DebugSEE(pos, mv);
 963
 964     if ((rgiList[0] != iSign) &&
 965         (iSign != INVALID_SCORE))
 966     {
 967         DumpPosition(pos);
 968         DumpMove(mv.uMove);
 969         Trace("Real SEE says: %d\n"
 970               "Test SEE says: %d\n",
 971               rgiList[0], iSign);
 972         UtilPanic(TESTCASE_FAILURE,
 973                   NULL,
 974                   "See mismatch",
 975                   rgiList[0],
 976                   iSign,
 977                   __FILE__, __LINE__);
 978     }
 979 #endif
 980     return(rgiList[0]);
 981 }