/**

Copyright (c) Scott Gasch

Module Name:

    see.c

Abstract:

    Static exchange evaluator and support code.  See also x86.asm.

Author:

    Scott Gasch (scott.gasch@gmail.com) 11 Jun 2004

Revision History:

    $Id: see.c 348 2008-01-05 07:11:36Z scott $

**/

#include "chess.h"

#define ADD_ATTACKER(p, c, v) \
    pList->data[pList->uCount].pPiece = (p); \
    pList->data[pList->uCount].cLoc = (c);   \
    pList->data[pList->uCount].uVal = (v);   \
    pList->uCount++;

void CDECL
SlowGetAttacks(IN OUT SEE_LIST *pList,
               IN POSITION *pos,
               IN COOR cSquare,
               IN ULONG uSide)
/*++

Routine description:

    SlowGetAttacks is the C version of GetAttacks; it should be
    identical to the GetAttacks code in x86.asm.  The job of the
    function is, given a position, square and side, to populate the
    SEE_LIST with the locations and types of enemy pieces attacking
    the square.

Parameters:

    SEE_LIST *pList : list to populate
    POSITION *pos : the board
    COOR cSquare : square in question
    ULONG uSide : side we are looking for attacks from

Return value:

    void

--*/
{
    register ULONG x;
    PIECE p;
    COOR c;
    int iIndex;
    COOR cBlockIndex;
    int iDelta;
    static PIECE pPawn[2] = { BLACK_PAWN, WHITE_PAWN };
    static int iSeeDelta[2] = { -17, +15 };

#ifdef DEBUG
    ASSERT(IS_ON_BOARD(cSquare));
    ASSERT(IS_VALID_COLOR(uSide));
    VerifyPositionConsistency(pos, FALSE);
#endif
    pList->uCount = 0;

    //
    // Check for pawns attacking cSquare
    //
    c = cSquare + (iSeeDelta[uSide]);
    if (IS_ON_BOARD(c))
    {
        p = pos->rgSquare[c].pPiece;
        if (p == pPawn[uSide])
        {
            //
            // N.B. Don't use ADD_ATTACKER here because we know we're
            // at element zero.
            //
            pList->data[0].pPiece = p;
            pList->data[0].cLoc = c;
            pList->data[0].uVal = VALUE_PAWN;
            pList->uCount = 1;
        }
    }

    c += 2;
    if (IS_ON_BOARD(c))
    {
        p = pos->rgSquare[c].pPiece;
        if (p == pPawn[uSide])
        {
            ADD_ATTACKER(p, c, VALUE_PAWN);
        }
    }

    //
    // Check for pieces attacking cSquare
    //
    for (x = pos->uNonPawnCount[uSide][0] - 1;
         x != (ULONG)-1;
         x--)
    {
        c = pos->cNonPawns[uSide][x];
        ASSERT(IS_ON_BOARD(c));

        p = pos->rgSquare[c].pPiece;
        ASSERT(p && !IS_PAWN(p));
        ASSERT(GET_COLOR(p) == uSide);

        iIndex = (int)c - (int)cSquare;
        if (0 == (CHECK_VECTOR_WITH_INDEX(iIndex, GET_COLOR(p)) &
                  (1 << PIECE_TYPE(p))))
        {
            continue;
        }

        if (IS_KNIGHT_OR_KING(p))
        {
            ASSERT(IS_KNIGHT(p) || IS_KING(p));
            ADD_ATTACKER(p, c, PIECE_VALUE(p));
            continue;
        }

        //
        // Check to see if there is a piece in the path from cSquare
        // to c that blocks the attack.
        //
        iDelta = NEG_DELTA_WITH_INDEX(iIndex);
        ASSERT(iDelta == -1 * CHECK_DELTA_WITH_INDEX(iIndex));
        ASSERT(iDelta != 0);
        for (cBlockIndex = cSquare + iDelta;
             cBlockIndex != c;
             cBlockIndex += iDelta)
        {
            if (!IS_EMPTY(pos->rgSquare[cBlockIndex].pPiece))
            {
                goto done;
            }
        }

        //
        // Nothing in the way.
        //
        ADD_ATTACKER(p, c, PIECE_VALUE(p));

 done:
        ;
    }
}


//
// board_representation/MIGRATION.md section 3: bbPieces-backed
// "who attacks square X" primitive, and a GetAttacks PoC built on
// it. Not wired into the GetAttacks macro yet -- see MIGRATION.md
// section 6 for the eventual toggle. Uses chess.h's FastFirstBit/
// FastLastBit (static inline bsf/bsr wrappers) rather than the real
// out-of-line FirstBit/LastBit -- worth avoiding call overhead in a
// per-move-generated, per-node hot path like this one.
//
static BITBOARD
_BuildOccupiedBB(IN POSITION *pos)
/**

Routine description:

    Full-board occupancy (both colors, every piece including pawns
    and kings), built from the incrementally-maintained bbPieces[2][8]
    and bbPawns[2] fields plus the king mailbox array
    (cNonPawns[.][0], a single square per side -- a bitboard for that
    adds nothing). All O(1) ORs now that bbPawns exists; this used to
    loop cPawns[2][8] (up to 16 iterations) to build the pawn portion,
    which ran on every single call regardless of how few pawns were
    actually relevant.

Parameters:

    POSITION *pos

Return value:

    BITBOARD

**/
{
    return (pos->bbPieces[WHITE][KNIGHT] | pos->bbPieces[WHITE][BISHOP] |
            pos->bbPieces[WHITE][ROOK]   | pos->bbPieces[WHITE][QUEEN]  |
            pos->bbPieces[BLACK][KNIGHT] | pos->bbPieces[BLACK][BISHOP] |
            pos->bbPieces[BLACK][ROOK]   | pos->bbPieces[BLACK][QUEEN]  |
            pos->bbPawns[WHITE]          | pos->bbPawns[BLACK]          |
            COOR_TO_BB(pos->cNonPawns[WHITE][0]) |
            COOR_TO_BB(pos->cNonPawns[BLACK][0]));
}

static BITBOARD
_WhoAttacksSquareBB(IN POSITION *pos,
                     IN COOR cSquare,
                     IN ULONG uSide,
                     IN BITBOARD bbOccupied)
/**

Routine description:

    Return a bitboard of every uSide knight/bishop/rook/queen/king
    that attacks cSquare in the current position, blockers included.
    Pawns are deliberately excluded -- see GetAttacksBB, which handles
    them the same 2-square-delta way SlowGetAttacks always has (already
    O(1), nothing to improve).

    Knights and the king are pure O(1) table/delta lookups (no
    blocking possible). Sliders walk outward from cSquare along each
    of the 4 rook/4 bishop directions to the *nearest* blocker
    (g_RookRayToEdge/g_BishopRayToEdge ANDed with bbOccupied, reduced
    via FastFirstBit/FastLastBit), and test only that nearest
    blocker for membership in uSide's rook/bishop/queen bitboard --
    anything beyond the first blocker on a ray cannot be attacking
    cSquare regardless of its type, so only one square per direction
    is ever classified.

    Each 4-direction ray-walk is skipped entirely (bbRookSliders/
    bbBishopSliders both zero) when uSide has no piece that could
    possibly be found by it -- cheap up front, and the case that
    matters most: a benchmark comparing this function's original
    unconditional version against the real (asm) GetAttacks showed a
    consistent ~1.4x slowdown across opening/middlegame/endgame
    positions, because the unconditional 8-ray walk pays a fixed cost
    regardless of how few of uSide's pieces are actually sliders,
    while the mailbox version's cost scales with uSide's live piece
    count. This early-out targets exactly that mismatch -- see
    board_representation/MIGRATION.md section 3 for the writeup.

Parameters:

    POSITION *pos,
    COOR cSquare : target square
    ULONG uSide : side whose attackers on cSquare we want
    BITBOARD bbOccupied : full-board occupancy (see _BuildOccupiedBB)

Return value:

    BITBOARD

**/
{
    BITBOARD bbAttackers;
    BITBOARD bbRookSliders;
    BITBOARD bbBishopSliders;
    BITBOARD bbRay;
    BITBOARD bbBlockers;
    BITBOARD bbBlockerBit;
    ULONG u;

    bbAttackers = g_KnightAttacksBB[cSquare] & pos->bbPieces[uSide][KNIGHT];
    if (DISTANCE(cSquare, pos->cNonPawns[uSide][0]) == 1)
    {
        bbAttackers |= COOR_TO_BB(pos->cNonPawns[uSide][0]);
    }

    // Measured slower: deriving the needed direction(s) directly from
    // the aligned slider bits (via FastFirstBit + rank/file-nibble
    // comparison) instead of the plain 4-direction loop below. The
    // extra bit-scan and branching to *avoid* touching 2-3 empty
    // directions cost more than just touching them via a cheap
    // AND+continue -- reverted; keeping the note so this isn't
    // rediscovered as "obviously better" and retried the same way.
    //
    // g_RookRayAll[cSquare] (all 4 directions' masks pre-ORed at
    // startup) answers "is uSide's rook/queen bitboard aligned with
    // cSquare in *any* rook direction at all" in one lookup+AND,
    // before paying for even the first per-direction check -- pieces
    // that aren't on any rook line from cSquare get rejected right
    // here. For the direction(s) that remain possible, g_RookRayToEdge[
    // u][cSquare] & bbRookSliders is the bitboard equivalent of what
    // CHECK_VECTOR does per-piece in the mailbox version -- "does
    // uSide have a rook/queen on *this* ray specifically."
    bbRookSliders = pos->bbPieces[uSide][ROOK] | pos->bbPieces[uSide][QUEEN];
    if (bbRookSliders & g_RookRayAll[cSquare])
    {
        for (u = 0; u < 4; u++)
        {
            bbRay = g_RookRayToEdge[u][cSquare];
            if (!(bbRay & bbRookSliders))
            {
                continue;
            }
            bbBlockers = bbRay & bbOccupied;
            // Isolate the nearest blocker as a bitboard bit directly,
            // skipping the bit-index/COOR round trip entirely --
            // bbBlockers, bbRookSliders and bbAttackers are all
            // already bitboards, so there's nothing COOR-space adds
            // here. Lowest-bit isolation (positive-direction rays)
            // doesn't even need FastFirstBit's ctz -- bb & -bb is O(1)
            // with no bit-scan instruction at all; the negative
            // direction still needs FastLastBit (no O(1) "isolate
            // highest bit" trick exists without counting leading
            // zeros first).
            bbBlockerBit = g_RookRayPositiveDir[u] ?
                           (bbBlockers & (0ULL - bbBlockers)) :
                           (1ULL << (FastLastBit(bbBlockers) - 1));
            bbAttackers |= (bbRookSliders & bbBlockerBit);
        }
    }

    bbBishopSliders = pos->bbPieces[uSide][BISHOP] | pos->bbPieces[uSide][QUEEN];
    if (bbBishopSliders & g_BishopRayAll[cSquare])
    {
        for (u = 0; u < 4; u++)
        {
            bbRay = g_BishopRayToEdge[u][cSquare];
            if (!(bbRay & bbBishopSliders))
            {
                continue;
            }
            bbBlockers = bbRay & bbOccupied;
            bbBlockerBit = g_BishopRayPositiveDir[u] ?
                           (bbBlockers & (0ULL - bbBlockers)) :
                           (1ULL << (FastLastBit(bbBlockers) - 1));
            bbAttackers |= (bbBishopSliders & bbBlockerBit);
        }
    }

    return bbAttackers;
}

void CDECL
_GetAttacksBB(IN OUT SEE_LIST *pList,
              IN POSITION *pos,
              IN COOR cSquare,
              IN ULONG uSide)
/**

Routine description:

    PROOF OF CONCEPT -- not called from anywhere yet, and not a
    replacement for GetAttacks/SlowGetAttacks until section 4/5/6 of
    board_representation/MIGRATION.md (correctness sweep, benchmark,
    toggle) are done. Reproduces SlowGetAttacks's exact semantics
    (same deliberately-approximate no-pin/no-en-passant contract) via
    _WhoAttacksSquareBB instead of the O(non-pawn-piece-count) mailbox
    walk -- pawns handled identically to SlowGetAttacks (2-square
    delta, unchanged, already O(1)).

    Attacker order is not guaranteed to match SlowGetAttacks -- see()
    sorts/heaps the list immediately after GetAttacks returns, so only
    the *set* of attackers needs to match, not the sequence
    (board_representation/MIGRATION.md section 4).

Parameters:

    SEE_LIST *pList : list to populate
    POSITION *pos : the board
    COOR cSquare : square in question
    ULONG uSide : side we are looking for attacks from

Return value:

    void

**/
{
    BITBOARD bbOccupied;
    BITBOARD bbAttackers;
    ULONG uBitIndex;
    COOR c;
    PIECE p;
    static PIECE pPawn[2] = { BLACK_PAWN, WHITE_PAWN };

#ifdef DEBUG
    ASSERT(IS_ON_BOARD(cSquare));
    ASSERT(IS_VALID_COLOR(uSide));
    VerifyPositionConsistency(pos, FALSE);
#endif
    pList->uCount = 0;

    //
    // g_PawnAttackOriginBB[uSide][cSquare] (precomputed at startup --
    // see data.c) is "the up to 2 squares a uSide pawn would need to
    // stand on to attack cSquare," as a bitboard. One lookup + one AND
    // against bbPawns[uSide] answers the whole question in bit-space --
    // no COOR arithmetic (cSquare + iSeeDelta), no IS_ON_BOARD check,
    // no mailbox load -- entirely replacing what iSeeDelta/pPawn[]
    // used to do at runtime; only the (0-2) actual hits still need a
    // COOR to populate the SEE_LIST.
    {
        BITBOARD bbPawnHits = g_PawnAttackOriginBB[uSide][cSquare] &
                               pos->bbPawns[uSide];
        ULONG uPawnBit;

        while (bbPawnHits)
        {
            uPawnBit = FastFirstBit(bbPawnHits) - 1;
            bbPawnHits &= (bbPawnHits - 1);
            ADD_ATTACKER(pPawn[uSide], BIT_NUMBER_TO_COOR(uPawnBit), VALUE_PAWN);
        }
    }

    //
    // Knights/bishops/rooks/queens/king, via the bitboard primitive.
    //
    bbOccupied = _BuildOccupiedBB(pos);
    bbAttackers = _WhoAttacksSquareBB(pos, cSquare, uSide, bbOccupied);
    while (bbAttackers)
    {
        uBitIndex = FastFirstBit(bbAttackers) - 1;
        bbAttackers &= (bbAttackers - 1); // clear lowest set bit
        c = BIT_NUMBER_TO_COOR(uBitIndex);
        p = pos->rgSquare[c].pPiece;
        ADD_ATTACKER(p, c, PIECE_VALUE(p));
    }
}

#ifdef SEE_HEAPS
//
// SEE_HEAPS works great in principle but makes MinLegalPiece
// inaccurate if the top of the heap is not a legal move (i.e. the
// piece is pinned etc...)  When tested the result of this was minimal
// and the use of a heap instead of a sorted list sped up the SEE
// code.
//
#define PARENT(x)      ((x - 1) / 2)
#define LEFT_CHILD(x)  (((x) * 2) + 1)
#define RIGHT_CHILD(x) (((x) * 2) + 2)

#ifdef DEBUG
static FLAG
_IsValidHeap(IN SEE_LIST *p)
/**

Routine description:

    Is the minheap in SEE_LIST p->data[] valid (i.e. does it satisfy
    the minheap property?)

Parameters:

    SEE_LIST *p : SEE_LIST to check

Return value:

    static FLAG : TRUE if valid, FALSE otherwise

**/
{
    ULONG u, l, r;

    for (u = 0; u < p->uCount; u++)
    {
        l = LEFT_CHILD(u);
        if ((l < p->uCount) && (p->data[l].uVal < p->data[u].uVal))
        {
            return(FALSE);
        }

        r = RIGHT_CHILD(u);
        if ((r < p->uCount) && (p->data[r].uVal < p->data[u].uVal))
        {
            return(FALSE);
        }
    }
    return(TRUE);
}
#endif // DEBUG


static void
_PushDown(IN OUT SEE_LIST *p,
          IN ULONG u)
/**

Routine description:

    Take heap node number u and compare its value with the value of
    its children.  Swap smallest value into position u and continue
    the push-down process if warranted.

Parameters:

    SEE_LIST *p : SEE_LIST/minheap
    ULONG u : node number in consideration

Return value:

    static void

**/
{
    ULONG l = LEFT_CHILD(u);
    ULONG r;
    ULONG uSmallest;
    SEE_THREESOME temp;

    //
    // The heap is a complete tree -- if there's no left child of this
    // node then there's no right child either.  If this is a leaf node
    // then our work is done.
    //
    ASSERT(p->uCount > 0);
    if (l >= p->uCount)
    {
        return;
    }
    ASSERT(PARENT(l) == u);

    //
    // Otherwise, find the smallest of u, l and r.
    //
    r = l + 1;
    ASSERT(r == RIGHT_CHILD(u));
    ASSERT(PARENT(r) == u);
    ASSERT((r != u) && (r != l) && (l != u));
    uSmallest = u;
    if (p->data[l].uVal < p->data[u].uVal)
    {
        uSmallest = l;
    }
    if ((r < p->uCount) && (p->data[r].uVal < p->data[uSmallest].uVal))
    {
        uSmallest = r;
    }

    //
    // If it's anything other than u, swap them and continue to push.
    //
    if (uSmallest != u)
    {
        ASSERT((uSmallest == l) || (uSmallest == r));
        temp = p->data[uSmallest];
        p->data[uSmallest] = p->data[u];
        p->data[u] = temp;
        _PushDown(p, uSmallest);
    }
}

static void
_BuildHeap(IN OUT SEE_LIST *p)
/**

Routine description:

    Convert a random array into a minheap.  Start at the first
    internal node and push it down into place.  Continue to work
    backwards until we get to the root (index 0).

Parameters:

    SEE_LIST *p : list to heapify

Return value:

    static void

**/
{
    int iStart = (p->uCount / 2) - 1;
    int i;

    ASSERT(iStart < (int)p->uCount);
    for (i = iStart; i > -1; i--)
    {
        ASSERT(i >= 0);
        _PushDown(p, (ULONG)i);
    }
    ASSERT(_IsValidHeap(p));
}


static void
_BubbleUp(IN OUT SEE_LIST *p, IN ULONG u)
/**

Routine description:

    Take a node and bubble it up into place to re-create a minheap.

Parameters:

    SEE_LIST *p : heap
    ULONG u : index of node to bubble up

Return value:

    static void

**/
{
    ULONG uParent;
    SEE_THREESOME temp;

    ASSERT(p->uCount > 0);
    if (u == 0) return;

    uParent = PARENT(u);
    ASSERT((LEFT_CHILD(uParent) == u) ||
           (RIGHT_CHILD(uParent) == u));
    ASSERT(uParent < u);
    if (p->data[uParent].uVal > p->data[u].uVal)
    {
        temp = p->data[uParent];
        p->data[uParent] = p->data[u];
        p->data[u] = temp;
        _BubbleUp(p, uParent);
    }
}

#else // !SEE_HEAPS

static void
_SortList(IN OUT SEE_LIST *pList)
/**

Routine description:

    Sort the SEE list by piece value with a selection sort.

Parameters:

    SEE_LIST *pList

Return value:

    static void

**/
{
    ULONG x;
    ULONG y;
    register ULONG uMaxVal;
    register ULONG uMaxLoc;
    SEE_THREESOME sTemp;

    for (x = 0;
         x < pList->uCount;
         x++)
    {
        //
        // Assume index X is the largest value item in the list
        //
        uMaxVal = pList->data[x].uVal;
        uMaxLoc = x;

        //
        // Look for others with a larger value
        //
        for (y = x + 1;
             y < pList->uCount;
             y++)
        {
            if (pList->data[y].uVal > uMaxVal)
            {
                uMaxVal = pList->data[y].uVal;
                uMaxLoc = y;
            }
        }

        sTemp = pList->data[uMaxLoc];
        pList->data[uMaxLoc] = pList->data[x];
        pList->data[x] = sTemp;
    }
}

#endif

static void INLINE
_RemoveItem(IN OUT SEE_LIST *pList,
            IN ULONG x)
/**

Routine description:

    Delete item x from the list.

Parameters:

    SEE_LIST *pList,
    ULONG x

Return value:

    static void INLINE

**/
{
#ifndef SEE_HEAPS
    ULONG y;
#endif

    ASSERT(x < pList->uCount);
    ASSERT(pList->uCount > 0);

#ifdef SEE_HEAPS
    //
    // Swap item x with the last thing on the heap and then push the
    // node back down.
    //
    if (x != (pList->uCount - 1))
    {
        pList->data[x] = pList->data[pList->uCount - 1];
        pList->uCount--;
        _PushDown(pList, 0);
    }
    else
    {
        pList->uCount--;
    }

#else // !SEE_HEAPS

    //
    // If X is not the last thing in the list we will have to ripple
    // shift to close the hole.  This is rare.
    //
    for (y = x + 1;
         y < pList->uCount;
         y++)
    {
        pList->data[y - 1] = pList->data[y];
    }
    pList->uCount--;

#endif // SEE_HEAPS
}


static void
_ClearPieceByLocation(IN OUT SEE_LIST *pList,
                      IN COOR cLoc)
/**

Routine description:

    Find a piece on the SEE list at COOR cLoc and delete it.

Parameters:

    SEE_LIST *pList,
    COOR cLoc

Return value:

    static void

**/
{
    ULONG x = 0;

    while (x < pList->uCount)
    {
        if (pList->data[x].cLoc == cLoc)
        {
            _RemoveItem(pList, x);
            return;
        }
        x++;
    }

    //
    // This can happen if, for example, the SEE move was a passed pawn push
    //
}


#ifdef SEE_HEAPS
static PIECE
_MinLegalPiece(IN POSITION *pos,
               IN ULONG uColor,
               IN SEE_LIST *pList,
               IN SEE_LIST *pOther,
               IN COOR *pc,
               IN COOR cIgnore)
/**

Routine description:

    Return the piece from the SEE list with the lowest value that is
    not pinned to its own king.  Because we are storing the SEE_LISTS
    as heaps, this is only an approximate value in the event that the
    real min value piece is indeed pinned to its own king.  I
    considered sorting the list in this case but it seems like (in
    tests) this inaccuracy really has little or no impact on the
    search tree size.  The speedup with heaps instead of sorted lists
    seems worth the price.

Parameters:

    POSITION *pos : the board
    ULONG uColor  : the color on move
    SEE_LIST *pList : the list we're selecting from
    SEE_LIST *pOther : the other side's list
    COOR *pc,
    COOR cIgnore

Return value:

    static PIECE

**/
{
    COOR cKing;
    PIECE p;
    register ULONG x;
    COOR c;

    //
    // The list is a minheap with the min value piece at index 0.
    //
    for (x = 0;
         x < pList->uCount;
         x++)
    {
        p = pList->data[x].pPiece;

        //
        // If this piece is the king, then no need to see if the move
        // exposes the king to check.. just play the move as long as
        // it's legal (i.e. no defenders to the square)
        //
        if (IS_KING(p))
        {
            if (pOther->uCount == 0)
            {
                *pc = pList->data[0].cLoc;

                //
                // Note: if p is a king and we allow them to play it then
                // by definition the other side has nothing to counter
                // with...  otherwise we'd be moving into check here.  So
                // even if we had other pieces that were pinned to the
                // king, empty out the list because we're done in the next
                // SEE loop.
                //
                pList->uCount = 0;
                return(p);
            }
        }
        else
        {
            //
            // Otherwise... consider pins.  If the least valuable
            // defender of the square cannot move because doing so
            // would exposes his king to check, skip it and try the
            // next least valuable.
            //
            cKing = pos->cNonPawns[uColor][0];
            c = ExposesCheck(pos, pList->data[x].cLoc, cKing);

            //
            // cIgnore is the coordinate of the last piece the other
            // side "moved" in this capture sequence.  This is a hack
            // to ignore pins based on a piece that has already moved
            // in the computation but is already on the board.  This
            // of course does not work for positions where the piece
            // you expose check to was "moved" two turns ago but these
            // are pretty rare.
            //
            if (!IS_ON_BOARD(c) || (c == cIgnore))
            {
                *pc = pList->data[x].cLoc;
                _RemoveItem(pList, x);
                return(p);
            }
        }
    }

    //
    // There are no legal pieces to move to square
    //
    return(0);
}

#else // !SEE_HEAPS

static PIECE
_MinLegalPiece(IN POSITION *pos,
               IN ULONG uColor,
               IN SEE_LIST *pList,
               IN SEE_LIST *pOther,
               IN COOR *pc,
               IN COOR cIgnore)
/**

Routine description:

    Return the piece from the SEE list with the lowest value that is
    not pinned to its own king.

Parameters:

    POSITION *pos : the board
    ULONG uColor  : the color on move
    SEE_LIST *pList : the list we're selecting from
    SEE_LIST *pOther : the other side's list
    COOR *pc,
    COOR cIgnore

Return value:

    static PIECE

**/
{
    COOR cKing;
    PIECE p;
    register ULONG x;
    COOR c;

    //
    // The list is sorted from most valuable (index 0) to least valuable
    // (index N).  Begin at the least valuable and work up.
    //
    for (x = pList->uCount - 1;
         x != (ULONG)-1;
         x--)
    {
        p = pList->data[x].pPiece;
        //
        // If this piece is the king, then no need to see if the move
        // exposes the king to check.. just play the move as long as 
        // it's legal (i.e. no defenders to the square)
        //
        if ((IS_KING(p)) && (pOther->uCount == 0))
        {
            ASSERT(x == 0);
            *pc = pList->data[0].cLoc;
            pList->uCount = 0;
            return(p);
        }
        else
        {
            //
            // Otherwise... consider pins.  If the least valuable
            // defender of the square cannot move because doing so
            // would exposes his king to check, skip it and try the
            // next least valuable.
            //
            cKing = pos->cNonPawns[uColor][0];
            c = ExposesCheck(pos, pList->data[x].cLoc, cKing);

            //
            // cIgnore is the coordinate of the last piece the other
            // side "moved" in this capture sequence.  This is a hack
            // to ignore pins based on a piece that has already moved
            // in the computation but is already on the board.  This
            // of course does not work for positions where the piece
            // you expose check to was "moved" two turns ago but these
            // are pretty rare.
            //
            if (!IS_ON_BOARD(c) || (c == cIgnore))
            {
                *pc = pList->data[x].cLoc;
                _RemoveItem(pList, x);
                return(p);
            }
        }
    }

    //
    // There are no legal pieces to move to square
    //
    return(0);
}
#endif // SEE_HEAPS

static void _AddXRays(IN POSITION *pos,
                      IN INT iAttackerColor,
                      IN COOR cTarget,
                      IN COOR cObstacle,
                      IN OUT SEE_LIST *pAttacks,
                      IN OUT SEE_LIST *pDefends)
/**

Routine description:

    We just "moved" a piece in the SEE sequence... add any xray
    attacks that it exposed to the SEE list to be take part as the
    sequence plays out.

Parameters:

    POSITION *pos,
    INT iAttackerColor,
    COOR cTarget,
    COOR cObstacle,
    SEE_LIST *pAttacks,
    SEE_LIST *pDefends

Return value:

    static void

**/
{
    int iDelta;
    COOR cIndex;
    PIECE xPiece;
    int iIndex;

    iIndex = (int)cTarget - (int)cObstacle;

    //
    // If there is no way for a queen sitting on the target square to
    // reach the obsticle square then there is no discovered attack.
    // (This could happen, for instance, if a knight captured.  It
    // can't uncover a new attack on the square where it took.
    //
    if (0 == (CHECK_VECTOR_WITH_INDEX(iIndex, BLACK) & (1 << QUEEN)))
    {
        return;
    }

    //
    // The squares are on the same rank, file or diagonal.  iDelta is
    // the way to move from target towards obstacle.
    //
    iDelta = CHECK_DELTA_WITH_INDEX(iIndex);

    //
    // Search for a piece that moves the right way to attack the target
    // square starting at the obstacle square + delta.
    //
    for (cIndex = cObstacle + iDelta;
         IS_ON_BOARD(cIndex);
         cIndex += iDelta)
    {
        xPiece = pos->rgSquare[cIndex].pPiece;
        if (!IS_EMPTY(xPiece))
        {
            //
            // Does it move the right way to hit cTarget?  TODO: can this
            // be optimized?  Remember pawns though...
            //
            if (0 != (CHECK_VECTOR_WITH_INDEX((int)cIndex - (int)cTarget,
                                              GET_COLOR(xPiece)) &
                      (1 << PIECE_TYPE(xPiece))))
            {
                //
                // Add this attacker to the proper SEE_LIST
                //
                if (GET_COLOR(xPiece) == iAttackerColor)
                {
                    pAttacks->data[pAttacks->uCount].pPiece = xPiece;
                    pAttacks->data[pAttacks->uCount].cLoc = cIndex;
                    pAttacks->data[pAttacks->uCount].uVal =
                        PIECE_VALUE(xPiece);
                    pAttacks->uCount++;
                    ASSERT(pAttacks->uCount > 0);
#ifdef SEE_HEAPS
                    _BubbleUp(pAttacks, pAttacks->uCount - 1);
#else
                    _SortList(pAttacks);
#endif
                }
                else
                {
                    pDefends->data[pDefends->uCount].pPiece = xPiece;
                    pDefends->data[pDefends->uCount].cLoc = cIndex;
                    pDefends->data[pDefends->uCount].uVal =
                        PIECE_VALUE(xPiece);
                    pDefends->uCount++;
                    ASSERT(pDefends->uCount > 0);
#ifdef SEE_HEAPS
                    _BubbleUp(pDefends, pDefends->uCount - 1);
#else
                    _SortList(pDefends);
#endif
                }
            }
            return;
        }
    }
}


SCORE
SEE(IN POSITION *pos,
    IN MOVE mv)
/**

Routine description:

    Given a board and a move on the board, estimate the value of the
    move by considering the friend/enemy pieces that attack the move's
    destination square.

Parameters:

    POSITION *pos,
    MOVE mv

Return value:

    SCORE : the estimate of the move's score

**/
{
    SEE_LIST rgPieces[2];
    PIECE pPiece;
    ULONG uInPeril;
    SCORE rgiList[32];
    ULONG uListIndex;
    ULONG uWhoseTurn = GET_COLOR(mv.pMoved);
    ULONG uOrig = uWhoseTurn;
    int iSign = 1;
    ULONG uPromValue;
    ULONG uVal;
    COOR cFrom = mv.cFrom;
    static FLAG _Table[2][3] = {
        // a<b    a==b   a>b
        {  FALSE, FALSE,  TRUE   },  // uVal==0
        {  TRUE,  FALSE,  FALSE  },  // uVal==1
    };

#ifdef DEBUG
    ASSERT(mv.uMove != 0);
    memset(rgiList, 0xFF, sizeof(rgiList));
    memset(rgPieces, 0xFF, sizeof(rgPieces));
#endif

    //
    // Create a sorted list of pieces attacking and defending the
    // square.
    //
    GetAttacks(&(rgPieces[uWhoseTurn]), pos, mv.cTo, uWhoseTurn);
    GetAttacks(&(rgPieces[FLIP(uWhoseTurn)]), pos, mv.cTo, FLIP(uWhoseTurn));
#ifdef SEE_HEAPS
    _BuildHeap(&(rgPieces[FLIP(uWhoseTurn)]));
    _BuildHeap(&(rgPieces[uWhoseTurn]));
#else
    _SortList(&(rgPieces[FLIP(uWhoseTurn)]));
    _SortList(&(rgPieces[uWhoseTurn]));
#endif

    //
    // Play the first move -- TODO: the first move may be illegal...
    // fix this?
    //
    rgiList[0] = (PIECE_VALUE(mv.pCaptured) +
                  PIECE_VALUE(mv.pPromoted));
    uInPeril = (PIECE_VALUE(mv.pMoved) +
                PIECE_VALUE(mv.pPromoted));
    uListIndex = 1;

    _ClearPieceByLocation(&(rgPieces[uWhoseTurn]), mv.cFrom);
    _AddXRays(pos,
              uWhoseTurn,
              mv.cTo,
              mv.cFrom,
              &(rgPieces[uWhoseTurn]),
              &(rgPieces[FLIP(uWhoseTurn)]));

    //
    // Play moves 2..n
    //
    do
    {
        //
        // Other side's turn now...
        //
        uWhoseTurn = FLIP(uWhoseTurn);
        iSign = -iSign;
        pPiece = _MinLegalPiece(pos,
                                uWhoseTurn,
                                &(rgPieces[uWhoseTurn]),
                                &(rgPieces[FLIP(uWhoseTurn)]),
                                &cFrom,
                                cFrom);
        if (0 == pPiece) break;               // no legal piece
        //
        // If this is a pawn capturing and it ends on the queening
        // rank, set uPromValue appropriately.  Bitwise operators are
        // correct here, done for speed and branch removal; this loop
        // is pretty heavily used.
        //
        uPromValue = IS_PAWN(pPiece) & (RANK1(mv.cTo) | RANK8(mv.cTo));
        uPromValue *= VALUE_QUEEN;
        ASSERT((uPromValue == 0) || (uPromValue == VALUE_QUEEN));

        ASSERT(uListIndex != 0);
        rgiList[uListIndex] = rgiList[uListIndex - 1] +
            iSign * (uInPeril + uPromValue);
        uListIndex++;
        ASSERT(uListIndex < ARRAY_LENGTH(rgiList));
        uInPeril = PIECE_VALUE(pPiece) + uPromValue;

        _AddXRays(pos,
                  GET_COLOR(mv.pMoved),
                  mv.cTo,
                  cFrom,
                  &(rgPieces[uOrig]),        // These must be rgAttacks and
                  &(rgPieces[FLIP(uOrig)])); // rgDefends.  Not based on tomove
    }
    while(1);

    //
    // The swaplist is now complete but we still must consider that either
    // side has the option of not taking (not continuing the exchange).
    //
    ASSERT(uListIndex >= 1);
    uListIndex--;

    while (uListIndex > 0)
    {
        uVal = (uListIndex & 1);
        iSign = ((rgiList[uListIndex] > rgiList[uListIndex - 1]) -
                 (rgiList[uListIndex] < rgiList[uListIndex - 1])) + 1;
        ASSERT((iSign >= 0) && (iSign <= 2));
        if (TRUE == _Table[uVal][iSign])
        {
            rgiList[uListIndex - 1] = rgiList[uListIndex];
        }
        uListIndex--;
    }

#ifdef TEST_BROKEN
    iSign = DebugSEE(pos, mv);

    if ((rgiList[0] != iSign) &&
        (iSign != INVALID_SCORE))
    {
        DumpPosition(pos);
        DumpMove(mv.uMove);
        Trace("Real SEE says: %d\n"
              "Test SEE says: %d\n",
              rgiList[0], iSign);
        UtilPanic(TESTCASE_FAILURE,
                  NULL,
                  "See mismatch",
                  rgiList[0],
                  iSign,
                  __FILE__, __LINE__);
    }
#endif
    return(rgiList[0]);
}