MadChess UCI_LimitStrength Algorithm

[emadsen]

Hi Ferdinand.

I have questions here, when doing multi-pv (when move/blunder error is greater than 0) do you use the full strength personality?

No. The search speed is limited. And positional understanding is weakened (the lower the ELO, the more positional evaluation terms are set to zero).

Perhaps some code will help. First, how to decide the error this move.

Code: Select all

// Determine score error this move.
int intScoreErrorThisMove = 0;
if (BlunderError > 0)
{
    if (_objRandom.Next&#40;0, 101&#41; <= BlunderPercent&#41;
    &#123;
        // Blunder
        intScoreErrorThisMove = BlunderError;
    &#125;
&#125;
intScoreErrorThisMove = Math.Max&#40;intScoreErrorThisMove, MoveError&#41;;
SearchState.HasError = intScoreErrorThisMove > 0;

So an error of at least MoveError (UCI parameter) is guaranteed. However is no suboptimal moves exist in the error range, the best move will be played. The engine will not hang its queen for the sake of playing a second best move. The suboptimal move must be in the error range.

Pass the move error to the Aspiration Window / PVS search.

Code: Select all

// Search moves with aspiration window.
int intScore = SearchMovesWithAspirationWindow(intHorizon, intScoreErrorThisMove);

Next, how to perform an Aspiration Window / PVS / MultiPV search with error. Basically, you have to use the correct alpha beta window to account for move error. Using Aspiration Windows and PVS keeps the time-to-depth fast, which is important for simulating ELO close to the max ELO of the engine. Using an infinite search window immediately loses 300 - 400 ELO.

By default my engine searches with an Aspiration Window of 50, then 200, then 500, then infinite.

Code: Select all

private int SearchMovesWithAspirationWindow(int Horizon, int ScoreErrorThisMove)
{
    if ((Horizon == 1) || (SearchState.BestMoves.Count == 0))
    {
        // Search moves with infinite aspiration window.
        return Search.Recurse(SearchState, 0, Horizon, -PositionalEvaluation.MaxScore, PositionalEvaluation.MaxScore);
    }
    // Found a best move from prior iteration.
    int intAspirationScore = SearchState.BestMoves[0].Score;
    int intAlpha = intAspirationScore - ScoreErrorThisMove;
    int intBeta = intAspirationScore;
    ScorePrecision enuScorePrecision = ScorePrecision.Exact;
    foreach (int intAspirationWindow in Search.AspirationWindows)
    {
        // Reset scored moves.
        foreach (ScoredMove objScoredMove in SearchState.ScoredMoves)
        {
            objScoredMove.Score = -PositionalEvaluation.MaxScore;
            objScoredMove.ScorePrecision = ScorePrecision.LowerBound;
        }
        // Adjust alpha / beta window.
        SearchState.SearchStats.AspirationNodes++;
        switch (enuScorePrecision)
        {
            case ScorePrecision.UpperBound:
                // Fail low
                intAlpha -= intAspirationWindow;
                break;
            case ScorePrecision.LowerBound:
                // Fail high
                intBeta += intAspirationWindow;
                break;
            default:
                // Initial aspiration window
                intAlpha -= intAspirationWindow;
                intBeta += intAspirationWindow;
                break;
        }
        // Search moves with aspiration window.
        int intBestScore = Search.Recurse(SearchState, 0, Horizon, intAlpha, intBeta);
        if (Math.Abs(intBestScore) == PositionalEvaluation.InterruptedSearchScore)
        {
            // Stop searching.
            return intBestScore;
        }
        if (intBestScore >= intBeta)
        {
            // Fail high
            enuScorePrecision = ScorePrecision.LowerBound;
            Search.UpdateInfoScoreFailed(SearchState, Horizon, true, intBestScore, enuScorePrecision);
            continue;
        }
        // Find lowest score.
        int intLowestScore;
        if (Search.MultiPv == 1)
        {
            // One principal variation scored.
            intLowestScore = intBestScore;
        }
        else
        {
            // Multiple principal variations scored.
            _colBestMoves.Clear();
            SearchState.ScoredMoves.AddBestMoves(_colBestMoves, Search.MultiPv);
            intLowestScore = _colBestMoves[_colBestMoves.Count - 1].Score;
        }
        if &#40;intLowestScore <= intAlpha&#41;
        &#123;
            // Fail low
            enuScorePrecision = ScorePrecision.UpperBound;
            Search.UpdateInfoScoreFailed&#40;SearchState, Horizon, true, intBestScore, enuScorePrecision&#41;;
            continue;
        &#125;
        // Score within aspiration window.
        SearchState.SearchStats.AspirationNodesCorrect++;
        return intBestScore;
    &#125;
    // Search moves with infinite aspiration window.
    return Search.Recurse&#40;SearchState, 0, Horizon, -PositionalEvaluation.MaxScore, PositionalEvaluation.MaxScore&#41;;
&#125;

There's a lot jammed into the above code. Notice how Alpha is initially set to intAspirationScore - ScoreErrorThisMove - intAspirationWindow (done on two separate lines, but this is the net effect). Alpha or Beta is adjusted if the search score lies on an aspiration boundary.

Notice how the Aspiration Window bounds are checked. This is not a requirement of Limit ELO but MultiPV. The best score cannot be compared against the high and low bounds. Rather, the best score is compared against the high bound, and the lowest MultiPV score is compared against the low bound.

Code: Select all

// Multiple principal variations scored.
_colBestMoves.Clear();
SearchState.ScoredMoves.AddBestMoves(_colBestMoves, Search.MultiPv);
intLowestScore = _colBestMoves[_colBestMoves.Count - 1].Score;

If MultiPV is 4, ScoredMoves.AddBestMoves returns the 4 best moves, sorted high to low. The next line returns the score of the 4th best move.

The MultiPV code is a bit distracting. To be clear, a Limit ELO search uses MultiPV = 1, uses Aspiration Windows (with initial alpha set low enough to account for move error), and uses PVS. One more piece of code is critical.

Code: Select all

if (intScore > intBestScore)
{
    // New principal variation 
    intBestScore = intScore;
    intPvMoveNumber = intLegalMoveNumber;
    if (intLegalMoveNumber > 1)
    {
        // Principal variation incorrect.
        bolPvCorrect = false;
    }
    // Update best move cache.
    UpdateBestMoveCache(SearchState, Depth, Horizon, objMove, intScore, Alpha, Beta);
    if ((Depth > 0) || ((MultiPv == 1) && !SearchState.HasError))
    {
        // Update alpha.
        Alpha = intScore;
    }
}

In the recursive PVS search, alpha is not updated if Depth == 0 and the search has error. Neither is alpha updated if Depth == 0 and MultiPV > 1. This keeps the search window open for the root moves.

[emadsen]

played a game against a setting with elo 1600

Thanks Ferdinand. I enjoyed playing through your game and reading your comments.

Another thing to consider is time pressure, let the computer get weaker when time is low, I don't know how low is this but it should be factored in, perhaps just increase the blunder percent.

That's a very good idea! The engine shouldn't be cool under pressure. It should get nervous like we humans do

[hgm]

I guess that to make this look natural, there should even be consistency between subsequent searches. We keep track of whether the current search has encountered the move, and what was the lowest ply level at which it was encountered. After the first search of the game, all moves that were not encountered will be disabled. (The search from the initial position does not need to be compromised, as even beginners would know what to do there,)

If later searches hit upon a disabled move at a lower ply level as what it was seen up to now, or when they hit upon it at the same ply level for the first time, the depth will be accordingly adapted, and the move will become enabled with a certain probability. This increases the probability the move will be searched as it gets closer to the root during the game, but even in the root there isn't a 100% probability it will be searched. When a move is still overlooked in the root, but remains possible there, the next game move it gets again a chance to become noticed (when the new search encounters it again at level 0).

Moves that are not visited during the current search will be disabled again after it, and their level will be reset. So they are ready to be overlooked again.