Are Aspiration Windows Worthless?

[emadsen]

I have not been able to verify any strength gain from aspiration windows.

I have decided to keep aspiration windows in my engine, though. They are useful for two non-competitive modes:

1. MultiPV
2. UCI_LimitStrength

Why? Because unlike in competitive mode, I don't reduce the search horizon of root moves for MultiPV searches or when the engine is weakened. Nor do I use PVS at the root. Nor do I update alpha at the root. This enables me to find in-bound scores for multiple root moves with a single search. For competitive mode (MultiPV = 1, UCI_LimitStrength = false) I reduce the search horizon of late moves at the root (LMR), I use PVS (zero alpha / beta window for legalMoveNumber > 1), and I update alpha when a new principal variation is found (score > bestScore).

My testing has found no strength gain from aspiration windows in competitive mode. However, I have verified improved time-to-depth when in analyze mode (MultiPV) and friendly mode (UCI_LimitStrength).

In my opinion, this technique keeps the code simpler compared to running multiple PVS searches each ply (with excluded moves) in order to find alternative, weaker moves for analysis (MultiPV) or fun (UCI_LimitStrength). I do at most two searches per ply at the root: First, a search with an aspiration window. If that fails high or low, then a second search with an infinite window. Note that a fail low for MultiPV means the nth move (not the best move) was <= alpha.

Code: Select all

private const int _aspirationMinHorizon = 5;
private const int _aspirationWindow = 100;
private bool CompetitivePlay => !LimitStrength && (MultiPv == 1);


public ulong FindBestMove(Board Board)
{
    // Ensure all root moves are legal.
    Board.CurrentPosition.GenerateMoves();
    var legalMoveIndex = 0;
    for (var moveIndex = 0; moveIndex < Board.CurrentPosition.MoveIndex; moveIndex++)
    {
        var move = Board.CurrentPosition.Moves[moveIndex];
        if (Board.IsMoveLegal(ref move))
        {
            // Move is legal.
            Move.SetPlayed(ref move, true); // All root moves will be played so set this in advance.
            Board.CurrentPosition.Moves[legalMoveIndex] = move;
            legalMoveIndex++;
        }
    }
    Board.CurrentPosition.MoveIndex = legalMoveIndex;
    if (legalMoveIndex == 1)
    {
        // Only one legal move found.
        _stopwatch.Stop();
        return Board.CurrentPosition.Moves[0];
    }
    // Copy legal moves to root moves and principal variations.
    for (var moveIndex = 0; moveIndex < legalMoveIndex; moveIndex++)
    {
        var move = Board.CurrentPosition.Moves[moveIndex];
        _rootMoves[moveIndex] = new ScoredMove(move, -StaticScore.Max);
        var principalVariation = new ulong[Position.MaxMoves];
        principalVariation[0] = Move.Null;
        _principalVariations.Add(Move.ToLongAlgebraic(move), principalVariation);
    }
    var principalVariations = Math.Min(MultiPv, legalMoveIndex);
    // Determine score error.
    var scoreError = ((BlunderError > 0) && (SafeRandom.NextInt(0, 100) < BlunderPercent))
        ? BlunderError // Blunder
        : 0;
    scoreError = Math.Max(scoreError, MoveError);
    // Determine move time.
    GetMoveTime(Board.CurrentPosition);
    Board.NodesExamineTime = UciStream.NodesTimeInterval;
    // Iteratively deepen search.
    _originalHorizon = 0;
    var bestMove = new ScoredMove(Move.Null, -StaticScore.Max);
    do
    {
        _originalHorizon++;
        _selectiveHorizon = 0;
        // Clear principal variations and age move history.
        // The Dictionary enumerator allocates memory which is not desirable when searching positions.
        // However, this occurs only once per ply.
        using (var pvEnumerator = _principalVariations.GetEnumerator())
        {
            while (pvEnumerator.MoveNext()) pvEnumerator.Current.Value[0] = Move.Null;
        }
        _moveHistory.Age(Board.CurrentPosition.WhiteMove);
        int alpha;
        int beta;
        if (CompetitivePlay || (_originalHorizon < _aspirationMinHorizon))
        {
            // Search with full alpha / beta window.
            alpha = -StaticScore.Max;
            beta = StaticScore.Max;
        }
        else
        {
            // Search with aspiration window.
            // This speeds up Multi-PV searches (for analysis and UCI_LimitStrength) but slows down Single-PV searches (competitive play).
            if (LimitStrength)
            {
                alpha = _rootMoves[0].Score - scoreError - 1;
                beta = _rootMoves[0].Score + _aspirationWindow;
            }
            else
            {
                alpha = _rootMoves[principalVariations - 1].Score - _aspirationWindow;
                beta = _rootMoves[0].Score + _aspirationWindow;
            }
            alpha = Math.Max(alpha, -StaticScore.Max);
            beta = Math.Min(beta, StaticScore.Max);
        }
        // Reset move scores then search moves.
        for (var moveIndex = 0; moveIndex < Board.CurrentPosition.MoveIndex; moveIndex++) _rootMoves[moveIndex].Score = -StaticScore.Max;
        var score = GetDynamicScore(Board, 0, _originalHorizon, false, alpha, beta);
        if (Math.Abs(score) == StaticScore.Interrupted) break; // Stop searching.
        SortMovesByScore(_rootMoves, Board.CurrentPosition.MoveIndex - 1);
        var failHigh = _rootMoves[0].Score >= beta;
        var failHighScore = score;
        var failLow = !failHigh && (_rootMoves[principalVariations - 1].Score <= alpha);
        var failLowScore = MultiPv > 1 ? _rootMoves[principalVariations - 1].Score : score;
        if (failHigh || failLow)
        {
            if (PvInfoUpdate)
            {
                if (failHigh) UpdateStatusFailHigh(Board.Nodes, failHighScore);
                if (failLow) UpdateStatusFailLow(Board.Nodes, failLowScore);
            }
            // Reset move scores then search moves within infinite alpha / beta window.
            for (var moveIndex = 0; moveIndex < Board.CurrentPosition.MoveIndex; moveIndex++) _rootMoves[moveIndex].Score = -StaticScore.Max;
            score = GetDynamicScore(Board, 0, _originalHorizon, false, -StaticScore.Max, StaticScore.Max);
            if (Math.Abs(score) == StaticScore.Interrupted) break; // Stop searching.
            SortMovesByScore(_rootMoves, Board.CurrentPosition.MoveIndex - 1);
        }
        // Find best move.
        for (var moveIndex = 0; moveIndex < Board.CurrentPosition.MoveIndex; moveIndex++) _bestMoves[moveIndex] = _rootMoves[moveIndex];
        bestMove = _bestMoves[0];
        _bestMovePlies[_originalHorizon] = bestMove;
        if (PvInfoUpdate) UpdateStatus(Board, true);
        if (MateInMoves.HasValue && (Math.Abs(bestMove.Score) >= StaticScore.Checkmate) && (Evaluation.GetMateDistance(bestMove.Score) <= MateInMoves.Value)) break; // Found checkmate in correct number of moves.
        AdjustMoveTime();
        if (!HaveTimeForNextHorizon()) break; // Do not have time to search next ply.
    } while (Continue && (_originalHorizon < HorizonLimit));
    _stopwatch.Stop();
    if (_debug()) _writeMessageLine($"info string Stopping search at {_stopwatch.Elapsed.TotalMilliseconds:0} milliseconds.");
    return scoreError == 0 ? bestMove.Move : GetInferiorMove(Board.CurrentPosition, scoreError);
}