path: root/src/dynamic.c

/**

Copyright (c) Scott Gasch

Module Name:

    dynamic.c

Abstract:

    Dynamic move ordering functions/structures.  By "dynamic move
    ordering" I mean killer moves and history heuristic stuff.  

    Note 1: there are two history tables here.  One is used for move
    ordering and the other is used for pruning decisions.  Both only
    contain data about non-capture/promote moves.  The former is
    updated with roughly remaining_depth^2 at a fail high while the
    latter is updated so as to maintain an approximate answer to "what
    percent of the time does this move fail high."

    Note 2: the globals in this module may be accessed by more than
    one searcher thread at the same time; spinlocks used to
    synchronize.

    Note 3: All of these tables must be cleared when a new game is
    started or a new position is loaded onto the board.

Author:

    Scott Gasch ([email protected]) 24 Jun 2004

Revision History:

    $Id: dynamic.c 345 2007-12-02 22:56:42Z scott $

**/

#include "chess.h"

// Declared directly instead of #include <math.h> -- that header
// #defines its own INFINITY, which collides with ours (chess.h:198,
// MAX_SHORT).  Only needed once, at startup, to build g_iLMRQuietReduction.
extern double log(double);

ULONG g_HistoryCounters[14][128];
SCORE g_iLMRQuietReduction[MAX_PLY_PER_SEARCH + 1][LMR_TABLE_MAX_MOVES + 1];

// Keyed by (cFrom, cTo, pMoved) -- the low 20 bits of mv.uMove -- rather
// than MOVE_TO_INDEX's (cFrom, cTo, color) so that e.g. a king shuffle
// and a queen sac to the same square/color aren't folded into the same
// fail-high bucket. pMoved's low bit is already the color, so this
// subsumes MOVE_TO_INDEX's color term for free.
#define MOVE_TO_FH_INDEX(mv) ((mv).uMove & 0xFFFFF)
#define FH_STATS_TABLE_SIZE (0x100000)

typedef struct _FH_STATS
{
    union
    {
        ULONG uWholeThing;
        struct
        {
            USHORT u16FailHighs;
            USHORT u16Attempts;
        };
    };
} FH_STATS;

FH_STATS g_FailHighs[FH_STATS_TABLE_SIZE];

#ifdef MP
volatile static ULONG g_uDynamicLock;
#define DYN_IS_LOCKED (g_uDynamicLock != 0)
#define LOCK_DYN \
    AcquireSpinLock(&g_uDynamicLock); \
    ASSERT(DYN_IS_LOCKED)
#define UNLOCK_DYN \
    ASSERT(DYN_IS_LOCKED); \
    ReleaseSpinLock(&g_uDynamicLock)
#else // no MP
#define DYN_IS_LOCKED (1)
#define LOCK_DYN
#define UNLOCK_DYN
#endif


void
InitLMRTable(void)
/**

Routine description:

    Build the LMR reduction table once at startup -- log(depth) *
    log(moves) formula (Ethereal's constants as a starting point, not
    load-bearing; expect to retune), converted to ONE_PLY-scaled
    integer ply-fractions so the search hot path never does floating
    point.  Quiet moves only; captures/promotions/checks/etc. are
    excluded by GetLMRReduction's own gate before this table is ever
    consulted.

Parameters:

    void

Return value:

    void

**/
{
    ULONG uDepth, uMoves;
    double d;

    for (uDepth = 0; uDepth <= MAX_PLY_PER_SEARCH; uDepth++)
    {
        for (uMoves = 0; uMoves <= LMR_TABLE_MAX_MOVES; uMoves++)
        {
            if ((uDepth < 1) || (uMoves < 1))
            {
                g_iLMRQuietReduction[uDepth][uMoves] = 0;
                continue;
            }
            d = 0.7844 + (log((double)uDepth) * log((double)uMoves)) / 2.4696;
            if (d < 0.0)
            {
                d = 0.0;
            }
            g_iLMRQuietReduction[uDepth][uMoves] = (SCORE)(d * (double)ONE_PLY);
        }
    }
}


FLAG
InitializeDynamicMoveOrdering(void)
/**

Routine description:

    Initialize dynamic move ordering structures.

Parameters:

    void

Return value:

    FLAG

**/
{
#ifdef MP
    g_uDynamicLock = 0;
#endif
    ClearDynamicMoveOrdering();
    return(TRUE);
}

void 
ClearDynamicMoveOrdering(void)
/**

Routine description:

    Clear the global history table.  Killer moves are per-context
    structures and must be cleared on a per-context basis.

Parameters:

    void

Return value:

    void

**/
{
    ULONG u;

    memset(g_HistoryCounters, 0, sizeof(g_HistoryCounters));
    for (u = 0; u < FH_STATS_TABLE_SIZE; u++) 
    {
        g_FailHighs[u].uWholeThing = 0x00010001;
    }
}


static void 
_RecordMoveFailHigh(MOVE mv)
/**

Routine description:

    Update the "fail high percentage" history table for this move.
    The table is used to make pruning decisions, not to rank moves.

Parameters:

    MOVE mv

Return value:

    static void

**/
{
    ULONG u = MOVE_TO_FH_INDEX(mv);
    ULONG v = g_FailHighs[u].uWholeThing;

    ASSERT(DYN_IS_LOCKED);
    if (((v & 0x0000FFFF) == 0x0000FFFF) || ((v & 0xFFFF0000) == 0xFFFF0000))
    {
        g_FailHighs[u].u16FailHighs >>= 1;
        g_FailHighs[u].u16Attempts >>= 1;
    }
    g_FailHighs[u].u16FailHighs++;
    g_FailHighs[u].u16Attempts++;
    ASSERT(g_FailHighs[u].u16FailHighs != 0);
    ASSERT(g_FailHighs[u].u16Attempts != 0);
    ASSERT(g_FailHighs[u].u16Attempts >= g_FailHighs[u].u16FailHighs);
}


static void 
_RecordMoveFailure(MOVE mv)
/**

Routine description:

    Update the fail high percentage table with the information that a
    move has not produced a fail high cutoff when it was considered.

Parameters:

    MOVE mv

Return value:

    static void

**/
{
    ULONG u = MOVE_TO_FH_INDEX(mv);

    ASSERT(DYN_IS_LOCKED);
    if (g_FailHighs[u].u16Attempts == 0xFFFF)
    {
        g_FailHighs[u].u16FailHighs >>= 1;
        g_FailHighs[u].u16Attempts >>= 1;
    }
    g_FailHighs[u].u16Attempts++;
    ASSERT(g_FailHighs[u].u16Attempts != 0);
    ASSERT(g_FailHighs[u].u16Attempts >= g_FailHighs[u].u16FailHighs);
}


static void 
_NewKillerMove(SEARCHER_THREAD_CONTEXT *ctx, 
               MOVE mv, 
               SCORE iScore)
/**

Routine description:

    Add a new killer move at a ply.

Parameters:

    SEARCHER_THREAD_CONTEXT *ctx,
    MOVE mv,
    SCORE iScore

Return value:

    void

**/
{
    ULONG uPly = ctx->uPly;

    ASSERT(uPly >= 0);
    ASSERT(uPly < MAX_PLY_PER_SEARCH);
    ASSERT(!IS_CAPTURE_OR_PROMOTION(mv));
    ASSERT(mv.uMove);

    if (mv.bvFlags & MOVE_FLAG_ESCAPING_CHECK)
    {
        if (!IS_SAME_MOVE(mv, ctx->mvKillerEscapes[uPly][0]))
        {
            ctx->mvKillerEscapes[uPly][1] = ctx->mvKillerEscapes[uPly][0];
            ctx->mvKillerEscapes[uPly][0] = mv;
            // No mvNullmoveQuietRefutations backfill here, unlike the
            // regular killer table below: TryNullmovePruning asserts
            // !InCheck() before probing, and a null move doesn't move
            // any piece, so the move that refutes it is necessarily
            // played from a position where the opponent was *not* in
            // check either -- it can never legitimately be a check
            // evasion. Backfilling with it here wouldn't be dead code
            // the way the old capture-into-quiet-slot bug was (that
            // was mathematically guaranteed to never match); since
            // IS_SAME_MOVE ignores bvFlags, an ordinary quiet move
            // from some unrelated non-check position could coincide
            // with a real escaping candidate by cFrom/cTo/pMoved/
            // pCaptured/pPromoted alone and pick up an undeserved
            // SECOND_KILLER bonus in evasion ordering. Leave the slot
            // empty instead of risking that.
        }
        ASSERT(!IS_SAME_MOVE(ctx->mvKillerEscapes[uPly][0],
                             ctx->mvKillerEscapes[uPly][1]));
    }
    else
    {
        mv.bvFlags |= ((iScore >= +NMATE) * MOVE_FLAG_KILLERMATE);
        if (!IS_SAME_MOVE(mv, ctx->mvKiller[uPly][0]))
        {
            ctx->mvKiller[uPly][1] = ctx->mvKiller[uPly][0];
            ctx->mvKiller[uPly][0] = mv;
            if (ctx->mvKiller[uPly][1].uMove == 0)
            {
                ctx->mvKiller[uPly][1] = ctx->mvNullmoveQuietRefutations[uPly];
            }
        }
        ASSERT(!IS_SAME_MOVE(ctx->mvKiller[uPly][0], ctx->mvKiller[uPly][1]));
    }
}


static void
_NewCounterMove(SEARCHER_THREAD_CONTEXT *ctx, MOVE mv, ULONG uRemainingDepth)
/**

Routine description:

    Remember that mv refuted whatever move the opponent just played to
    reach this node -- keyed by that previous move, not by ply, so it
    generalizes across any branch where the opponent plays the same
    move again, unlike killers.

    Depth-gated: a shallow fail-high (low uRemainingDepth, i.e. close
    to the QSearch handoff) is much lower-confidence evidence than one
    found with many plies still remaining, but unlike killers (which
    are ply-scoped and self-correct locally), this table is global --
    keyed only by move identity, with nothing to stop a later, shallow
    write from clobbering an earlier, deep one just because it's more
    recent.  Only overwrite when the new evidence is at least as deep
    as what's already there.

Parameters:

    SEARCHER_THREAD_CONTEXT *ctx,
    MOVE mv,
    ULONG uRemainingDepth

Return value:

    void

**/
{
    MOVE mvLast;
    ULONG u;
    ULONG uPly;

    ASSERT(!IS_CAPTURE_OR_PROMOTION(mv));
    ASSERT(mv.uMove);

    if (ctx->uPly == 0)
    {
        return;
    }
    mvLast = ctx->sPlyInfo[ctx->uPly - 1].mv;
    if (0 == mvLast.uMove)
    {
        return;
    }
    u = MOVE_TO_INDEX(mvLast);

    //
    // Hit-rate instrumentation: did the counter-move slot for this
    // previous move already predict the move that just won here?
    // Checked before the slot is (maybe) overwritten below.
    //
    if ((ctx->mvCounter[u][0].uMove != 0) ||
        (ctx->mvCounter[u][1].uMove != 0))
    {
        INC(ctx->sCounters.tree.u64CounterMoveTries);
        if (IS_SAME_MOVE(mv, ctx->mvCounter[u][0]) ||
            IS_SAME_MOVE(mv, ctx->mvCounter[u][1]))
        {
            INC(ctx->sCounters.tree.u64CounterMoveHits);
        }
    }

    // A/B test: write-gating by depth (reject shallower overwrites)
    // measured *worse* hit rate with no EBF gain -- this table is
    // global, not ply-scoped, so a frozen "deepest wins" entry can
    // go stale while later, more locally-relevant evidence gets
    // rejected. Always overwrite (recency); track depth instead to
    // scale the read-time bonus.
    uPly = uRemainingDepth / ONE_PLY;
    if (!IS_SAME_MOVE(mv, ctx->mvCounter[u][0]))
    {
        ctx->mvCounter[u][1] = ctx->mvCounter[u][0];
        ctx->mvCounter[u][0] = mv;
    }
    ctx->uCounterDepth[u] = (UCHAR)MINU(uPly, 255);
}


void
RecordEnprisePieceAtPly(SEARCHER_THREAD_CONTEXT *ctx, ULONG uPly, COOR cSquare)
/**

Routine description:

    Remember (at uPly, not necessarily the current ply) that the
    piece sitting on cSquare in the *current* position -- which must
    belong to whoever is to move at uPly -- looked en prise.
    Ply-indexed and overwrite-in-place, exactly like killer moves:
    this is a nice-to-have ordering/pruning hint, not a fact about the
    current position, and readers must re-validate the recorded piece
    is still on the recorded square before trusting it.

    Invariant: the recorded piece's color always matches the mover's
    color at uPly -- same as a killer move's moved piece always does.
    This only ever records *self* danger (the side to move at uPly
    has a piece hanging), never "I can capture the opponent's piece"
    -- that's a different fact, one no current reader wants, and
    conflating the two would let noisy opponent-danger writes evict
    the self-danger hints readers actually consume.

    uPly need not equal ctx->uPly: a fail-high capture is discovered
    back at the capturing side's own ply (after UnmakeMove restores
    the victim to cSquare), but the victim's color is the *other*
    side's -- exactly the mover at ctx->uPly - 1 (ply parity
    alternates), which is where "despite the move you're about to
    make, this piece is still in trouble" actually belongs. Expected
    mover is derived from the live ctx->uPly/ctx->sPosition.uToMove
    (always in sync) via that parity offset, not from uPly directly.

Parameters:

    SEARCHER_THREAD_CONTEXT *ctx,
    ULONG uPly,
    COOR cSquare

Return value:

    void

**/
{
    PIECE p = ctx->sPosition.rgSquare[cSquare].pPiece;
    ULONG uExpectedMover = (((ctx->uPly - uPly) & 1) ?
                            FLIP(ctx->sPosition.uToMove) :
                            ctx->sPosition.uToMove);

    ASSERT(uPly < MAX_PLY_PER_SEARCH);
    ASSERT(p && IS_VALID_PIECE(p) && !IS_PAWN(p));
    ASSERT(GET_COLOR(p) == uExpectedMover);

    if ((ctx->cEnprise[uPly][0] != cSquare) ||
        (ctx->pEnprise[uPly][0] != p))
    {
        ctx->cEnprise[uPly][1] = ctx->cEnprise[uPly][0];
        ctx->pEnprise[uPly][1] = ctx->pEnprise[uPly][0];
        ctx->cEnprise[uPly][0] = cSquare;
        ctx->pEnprise[uPly][0] = p;
    }
}


void
RecordEnprisePiece(SEARCHER_THREAD_CONTEXT *ctx, COOR cSquare)
/**

Routine description:

    RecordEnprisePieceAtPly at the current ply -- the common case
    (self-danger found by a full Eval() at this exact node).

**/
{
    RecordEnprisePieceAtPly(ctx, ctx->uPly, cSquare);
}


void
RecordTrappedPiece(SEARCHER_THREAD_CONTEXT *ctx, COOR cSquare)
/**

Routine description:

    Remember (at the current ply) that the piece sitting on cSquare --
    belonging to the side to move at this ply -- looked trapped.
    Single slot -- trapped pieces are rarer than en prise ones. Same
    freshness caveat and self-danger-only invariant as
    RecordEnprisePiece.

Parameters:

    SEARCHER_THREAD_CONTEXT *ctx,
    COOR cSquare

Return value:

    void

**/
{
    ULONG uPly = ctx->uPly;
    PIECE p = ctx->sPosition.rgSquare[cSquare].pPiece;

    ASSERT(uPly < MAX_PLY_PER_SEARCH);
    ASSERT(p && IS_VALID_PIECE(p) && !IS_PAWN(p));
    ASSERT(GET_COLOR(p) == ctx->sPosition.uToMove);

    ctx->cTrapped[uPly] = cSquare;
    ctx->pTrapped[uPly] = p;
}


static FLAG INLINE
_EnpriseSlotValid(SEARCHER_THREAD_CONTEXT *ctx, ULONG uSlot, ULONG uSide)
{
    ULONG uPly = ctx->uPly;
    COOR c = ctx->cEnprise[uPly][uSlot];

    return(IS_ON_BOARD(c) &&
           (ctx->sPosition.rgSquare[c].pPiece == ctx->pEnprise[uPly][uSlot]) &&
           (GET_COLOR(ctx->pEnprise[uPly][uSlot]) == uSide));
}


static FLAG INLINE
_TrappedSlotValid(SEARCHER_THREAD_CONTEXT *ctx, ULONG uSide)
{
    ULONG uPly = ctx->uPly;
    COOR c = ctx->cTrapped[uPly];

    return(IS_ON_BOARD(c) &&
           (ctx->sPosition.rgSquare[c].pPiece == ctx->pTrapped[uPly]) &&
           (GET_COLOR(ctx->pTrapped[uPly]) == uSide));
}


COOR
FindEnprisePiece(SEARCHER_THREAD_CONTEXT *ctx, ULONG uSide)
/**

Routine description:

    Look up an en prise piece of color uSide at the current ply,
    re-validated against the live board (see RecordEnprisePiece).
    Used by move ordering to boost moves that rescue the piece.

Parameters:

    SEARCHER_THREAD_CONTEXT *ctx,
    ULONG uSide

Return value:

    COOR : the square, or ILLEGAL_COOR if no valid hint

**/
{
    if (_EnpriseSlotValid(ctx, 0, uSide))
    {
        return ctx->cEnprise[ctx->uPly][0];
    }
    if (_EnpriseSlotValid(ctx, 1, uSide))
    {
        return ctx->cEnprise[ctx->uPly][1];
    }
    return ILLEGAL_COOR;
}


ULONG
ValueOfMaterialInTroubleDespiteMove(SEARCHER_THREAD_CONTEXT *ctx, ULONG uSide)
/**

Routine description:

    Extended-futility safety net: how much material does uSide stand
    to lose despite the move just made, per the en prise/trapped
    hints at the current ply? Requires *both* en prise slots to be
    valid for uSide (mirrors the old "more than one piece en prise"
    threshold) before trusting the en prise value; the trapped hint
    has no such threshold.

Parameters:

    SEARCHER_THREAD_CONTEXT *ctx,
    ULONG uSide

Return value:

    ULONG : material value in trouble, or 0

**/
{
    ULONG uPly = ctx->uPly;
    ULONG u = 0;
    FLAG fHaveValue = FALSE;
    COOR c, c1;

    if (_EnpriseSlotValid(ctx, 0, uSide) && _EnpriseSlotValid(ctx, 1, uSide))
    {
        c = ctx->cEnprise[uPly][0];
        c1 = ctx->cEnprise[uPly][1];
        ASSERT(c != c1);
        u = MINU(PIECE_VALUE(ctx->sPosition.rgSquare[c].pPiece),
                 PIECE_VALUE(ctx->sPosition.rgSquare[c1].pPiece));
        fHaveValue = TRUE;
    }
    if (_TrappedSlotValid(ctx, uSide))
    {
        c = ctx->cTrapped[uPly];
        u = (fHaveValue ?
             MINU(u, PIECE_VALUE(ctx->sPosition.rgSquare[c].pPiece)) :
             PIECE_VALUE(ctx->sPosition.rgSquare[c].pPiece));
    }
    return u;
}


ULONG
ValueOfMaterialInTroubleAfterNull(SEARCHER_THREAD_CONTEXT *ctx, ULONG uSide)
/**

Routine description:

    Nullmove-pruning safety net: same as ValueOfMaterialInTroubleDespiteMove
    but with a looser threshold (any valid en prise hint counts, not
    just two) since this is guarding a cheaper, more speculative prune.

Parameters:

    SEARCHER_THREAD_CONTEXT *ctx,
    ULONG uSide

Return value:

    ULONG : material value in trouble, or 0

**/
{
    ULONG uPly = ctx->uPly;
    ULONG u = 0;
    COOR c;

    if (_EnpriseSlotValid(ctx, 0, uSide))
    {
        c = ctx->cEnprise[uPly][0];
        u = PIECE_VALUE(ctx->sPosition.rgSquare[c].pPiece);
    }
    if (_TrappedSlotValid(ctx, uSide))
    {
        c = ctx->cTrapped[uPly];
        u = MAXU(u, PIECE_VALUE(ctx->sPosition.rgSquare[c].pPiece));
    }
    return u;
}


static void
_IncrementMoveHistoryCounter(MOVE mv,
                             ULONG uDepth)
/**
  
Routine description:

    Increase a move's history counter in the global history table.
    Also affect the history pruning counters in prune.c.

Parameters:

    MOVE mv,
    ULONG uDepth

Return value:

    void

**/
{
    ULONG x, y;
    ULONG uVal;
    ULONG *pu;

    ASSERT(!IS_CAPTURE_OR_PROMOTION(mv));
    uVal = uDepth / ONE_PLY;
    ASSERT(uVal >= 0);
    ASSERT(uVal <= MAX_PLY_PER_SEARCH);
    uVal += 1;
    uVal *= uVal;
    ASSERT(uVal > 0);

    pu = &(g_HistoryCounters[mv.pMoved][mv.cTo]);
    LOCK_DYN;
    *pu += uVal;

    //
    // Make sure that the history weight doesn't get large enough to
    // affect the move flags or else our move ordering algorithm is
    // screwed.
    //
    while (*pu & ~STRIP_OFF_FLAGS)
    {
        for (x = 0; x <= WHITE_KING; x++)
        {
            FOREACH_SQUARE(y)
            {
                g_HistoryCounters[x][y] >>= 4;
            }
        }
    }

#ifdef MP
    //
    // The purpose of this restriction is to ease contention for the
    // memory bandwidth of the machine on dual-core / dual proc
    // systems.  The net result is positive.
    //
    if (uDepth > THREE_PLY)
    {
        _RecordMoveFailHigh(mv);
    }
#else
    _RecordMoveFailHigh(mv);
#endif
    UNLOCK_DYN;
}

static void 
_DecrementMoveHistoryCounter(MOVE mv, 
                             ULONG uDepth)
/**
  
Routine description:

    Decrease a move's history counter in the global history table.

Parameters:

    MOVE mv,
    ULONG uDepth

Return value:

    void

**/
{
    ULONG uVal;
    ULONG *pu;

    ASSERT(!IS_CAPTURE_OR_PROMOTION(mv));
    uVal = uDepth / ONE_PLY;
    ASSERT(uVal >= 0);
    ASSERT(uVal <= MAX_PLY_PER_SEARCH);
    uVal /= 4;
    uVal += 1;
    ASSERT(uVal > 0);

    pu = &(g_HistoryCounters[mv.pMoved][mv.cTo]);
    LOCK_DYN;
    if (*pu >= uVal)
    {
        *pu -= uVal;
    }
    else
    {
        *pu = 0;
    }
    _RecordMoveFailure(mv);
    UNLOCK_DYN;
}


void 
UpdateDynamicMoveOrdering(IN SEARCHER_THREAD_CONTEXT *ctx,
                          IN ULONG uRemainingDepth,
                          IN MOVE mvBest,
                          IN SCORE iScore,
                          IN ULONG uCurrent)
/**

Routine description:

    Update dynamic move ordering structs for a particular move (and,
    possibly, the other moves that were considered prior to this move
    in the move ordering).  This is called when a move beats alpha at
    the root or in Search (but not in QSearch).

Parameters:

    SEARCHER_THREAD_CONTEXT *ctx,
    ULONG uRemainingDepth,
    MOVE mvBest,
    SCORE iScore,
    ULONG uCurrent

Return value:

    void

**/
{
    ULONG u;
    MOVE mv;

    //
    // Add this move to the killer list and increment its history count
    //
    if (!IS_CAPTURE_OR_PROMOTION(mvBest))
    {
        _NewKillerMove(ctx, mvBest, iScore);
        _NewCounterMove(ctx, mvBest, uRemainingDepth);
        _IncrementMoveHistoryCounter(mvBest, uRemainingDepth);
    }

    //
    // If this move was not the first we considered at this node,
    // decrement the history counters of moves we considered before
    // it.
    //
    uCurrent -= (uCurrent != 0);
    for (u = ctx->sMoveStack.uBegin[ctx->uPly];
         u < uCurrent;
         u++)
    {
        ASSERT(IS_SAME_MOVE(ctx->sMoveStack.mvf[uCurrent].mv, mvBest));
        mv = ctx->sMoveStack.mvf[u].mv;
        ASSERT(!IS_SAME_MOVE(mv, mvBest));
        if (!IS_CAPTURE_OR_PROMOTION(mv))
        {
            _DecrementMoveHistoryCounter(mv, uRemainingDepth);
        }
    }
}




ULONG
GetMoveFailHighPercentage(IN MOVE mv, OUT ULONG *puAttempts)
/**

Routine description:

    Lookup a move in the fail high percentage history table and return
    its approximate fail high percentage.

Parameters:

    MOVE mv
    ULONG *puAttempts : optional (may be NULL) -- receives the number of
        observations the percentage is based on, so callers can weight
        by sample confidence instead of trusting a percentage computed
        from as few as one attempt.

Return value:

    ULONG

**/
{
    ULONG u = MOVE_TO_FH_INDEX(mv);
    ULONG n, d;

    n = g_FailHighs[u].u16FailHighs;
    d = g_FailHighs[u].u16Attempts;
    if (puAttempts) *puAttempts = d;
    if (d == 0)
    {
        return(0);
    }
    n *= 100;
    return(n / d);
}


void 
CleanupDynamicMoveOrdering(void)
/**

Routine description:
   
    Cleanup dynamic move ordering structs -- basically a noop for now.

Parameters:

    void

Return value:

    void

**/
{
    NOTHING;
}


void 
MaintainDynamicMoveOrdering(void)
/**

Routine description:

    Perform routine maintenance on dynamic move ordering data by
    reducing the magnitude of the history counters.

Parameters:

Return value:

    void

**/
{
    ULONG x, y;
    
    LOCK_DYN;
    for (x = 0; x <= WHITE_KING; x++)
    {
        FOREACH_SQUARE(y)
        {
            g_HistoryCounters[x][y] >>= 1;
        }
    }
    UNLOCK_DYN;
}