Score Inaccuracy: An Engine Weakening Algorithm

Discussion of chess software programming and technical issues.

Moderators: hgm, Dann Corbit, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
emadsen
Posts: 316
Joined: Wed Apr 25, 2012 11:51 pm
Location: Oak Park, IL, USA
Full name: Erik Madsen
Contact:

Score Inaccuracy: An Engine Weakening Algorithm

Post by emadsen » Wed Oct 31, 2012 5:54 am

I'd like to describe the technique I use to weaken my engine, MadChess, and ask a couple questions:

1) How do you weaken the playing strength of your engine? Do you use a technique similar to "score inaccuracy" or do something totally different?
2) Have you measured the correlation between weakening parameters and playing strength (ELO)? I'd appreciate any information you're willing to share.

So here's "score inaccuracy." I hesitate to call it an algorithm because the code is very simple:

At full strength (ScoreInaccuracy = 0)
  1. Peform an iterative deepening PVS search.
  2. Search first move with an aspiration window.
  3. If score falls outside aspiration boundary, research with infinite window.
  4. On subsequent moves, search with zero window, expanding to infinite window if score fails high.
At weakened strength (ScoreInaccuracy > 0)
  1. First assign an Error to each legal move, from -ScoreInaccuracy to +ScoreInaccuracy.
  2. Perform an iterative deepening PVS search.
  3. Search first move with a window equal to normal aspiration window + ScoreInaccuracy.
  4. If score falls outside aspiration boundary, research with infinite window.
  5. On subsequent moves, search with a window equal to 1 (the normal zero window) + ScoreInaccuracy, expanding to infinite window if score fails high.
  6. Add the move's Error to its minimax score before testing alpha / beta bounds.
I feel the weakened search should have the same form as the full strength search so it does not suffer a huge performance hit, for example, were it to perform an infinite-window search for every root move. The weakness should come from the score Error, not a performance degradation. Also, I wanted the search to look like a real search to the user- manage time, report score, depth, and principal variation. And I wanted to avoid a wildly fluctuating score as the search progressed- hence each move is assigned an Error that applies at every depth.

Note that I add Error to root moves and not to evaluations at the leaf nodes. I did this primarily because it's much easier to reason about the effect it will have on playing strength. I suspected randomization in evaluation would get lost in statistical noise.

I haven't played enough games against a weakened MadChess to get a good sense of how it "feels." But I have measured its playing strength against a common pool of opponents (no self-play), varying the ScoreInaccuracy parameter. I intend to use this data to calibrate the UCI_Elo parameter.

Image

Here's the code:

Code: Select all

// Snip
foreach (Move objMove in this.Search.GetMoveSelector(this.SearchState, objSearchDepth))
{                
    if (this.Board.IsMoveLegal(objMove))
    {
        // Move is legal
        colLegalMoves.Add(objMove);
        ScoredMove objScoredMove = new ScoredMove(objMove);
        // Determine error.
        if (this.ScoreInaccuracy > 0)
        {
            objScoredMove.Error = mobjRandom.Next(-this.ScoreInaccuracy, this.ScoreInaccuracy + 1);
        }
        else
        {
            objScoredMove.Error = 0;
        }
        this.SearchState.ScoredMoves.Add(objScoredMove);
    }
}
// Snip
this.SearchMoves(this.SearchState, objSearchDepth, colLegalMoves);


private void SearchMoves(SearchState SearchState, SearchDepth SearchDepth, Moves Moves)
{
    int intBestScore = -this.Evaluation.MaxScore;
    bool bolPVCorrect = true;
    int intLegalMove = 0;
    int intPVMove = 1;
    foreach(Move objMove in this.Search.GetMoveSelector(SearchState, SearchDepth, Moves))
    {
        if (!objMove.IsLegal.HasValue)
        {
            // Determine if move is legal.
            objMove.IsLegal = SearchState.Board.IsMoveLegal(objMove);
        }
        if (objMove.IsLegal == true)
        {
            intLegalMove++;
        }
        else
        {
            // Skip illegal move.
            continue;
        }
        ScoredMove objScoredMove = SearchState.ScoredMoves[objMove];
        // Update search state.
        SearchState.RootMove = objMove;
        SearchState.RootMoveNumber = intLegalMove;
        // Play move.
        this.Board.PlayMove(objMove);
        if (intLegalMove == 1)
        {
            // First move
            this.SearchState.SearchStats.PVNodes++;
            if (this.SearchState.BestMove.Move == null)
            {
                // Search with infinite alpha / beta window.
                objScoredMove.Score = -this.Search.Recurse(SearchState, SearchDepth.MoveTowardsHorizon(), -this.Evaluation.MaxScore, this.Evaluation.MaxScore);
            }
            else
            {
                // Search with aspiration window.
                int intAspirationScore = this.SearchState.BestMove.Score;
                int intAspirationWindow;
                if (this.ScoreInaccuracy > 0)
                {
                    intAspirationWindow = this.Search.AspirationWindow + this.ScoreInaccuracy;
                }
                else
                {
                    intAspirationWindow = this.Search.AspirationWindow;
                }
                objScoredMove.Score = this.SearchWithAspirationWindow(SearchState, SearchDepth.MoveTowardsHorizon(), intAspirationScore, intAspirationWindow);
            }
        }
        else
        {
            // Later move     
            int intAlpha = intBestScore - this.ScoreInaccuracy - 1;
            int intBeta = intBestScore + this.ScoreInaccuracy;
            objScoredMove.Score = -this.Search.Recurse(SearchState, SearchDepth.MoveTowardsHorizon(), -intBeta, -intAlpha);
            if ((objScoredMove.Score + objScoredMove.Error) >= intBestScore)
            {
                // Move may be stronger than principal variation.
                // Search with infinite alpha / beta window.
                objScoredMove.Score = -this.Search.Recurse(SearchState, SearchDepth.MoveTowardsHorizon(), -this.Evaluation.MaxScore, this.Evaluation.MaxScore);
            }
        }
        // Undo move.
        this.Board.UndoMove();
        if (objScoredMove.Score == this.Evaluation.InterruptedSearchScore)
        {
            // Stop searching.
            return;
        }
        // Add error to score.
        objScoredMove.Score += objScoredMove.Error; 
        if (objScoredMove.Score > intBestScore)
        {
            // New principal variation.
            intPVMove = intLegalMove;
            if (intLegalMove > 1)
            {
                // Principal variation incorrect.
                bolPVCorrect = false;
            }
            // Update best score.
            intBestScore = objScoredMove.Score;
        }                
        this.SearchState.SearchStats.MovesSearched++;
    }
    this.SearchState.SearchStats.PVMoveNumber += intPVMove;
    if (bolPVCorrect)
    {
        this.SearchState.SearchStats.PVNodesCorrect++;
    }
}


private int SearchWithAspirationWindow(SearchState SearchState, SearchDepth SearchDepth, int AspirationScore, int AspirationWindow)
{
    int intAspirationAlpha = AspirationScore - AspirationWindow;
    int intAspirationBeta = AspirationScore + AspirationWindow;
    this.SearchState.SearchStats.AspirationNodes++;
    // Search with aspiration window.
    int intScore = -this.Search.Recurse(SearchState, SearchDepth, -intAspirationBeta, -intAspirationAlpha);
    if (Math.Abs(intScore) == this.Evaluation.InterruptedSearchScore)
    {
        // Search was interrupted.
        this.SearchState.SearchStats.AspirationNodes--;
    }
    else if (&#40;intScore <= intAspirationAlpha&#41; || &#40;intScore >= intAspirationBeta&#41;)
    &#123;
        // Score outside aspiration window.
        // Search with infinite alpha / beta window.
        intScore = -this.Search.Recurse&#40;SearchState, SearchDepth, -this.Evaluation.MaxScore, this.Evaluation.MaxScore&#41;;
    &#125;   
    else
    &#123;
        // Score within aspiration window.
        this.SearchState.SearchStats.AspirationNodesCorrect++;
    &#125;        
    return intScore;
&#125;
My C# chess engine: https://www.madchess.net

kinderchocolate
Posts: 454
Joined: Mon Nov 01, 2010 5:55 am
Full name: Ted Wong
Contact:

Re: Score Inaccuracy: An Engine Weakening Algorithm

Post by kinderchocolate » Thu Nov 01, 2012 1:12 am

I think I had asked the same question a while ago. I did briefly tried something like you. While it was a fancy idea, it's practical application was limited. The results were inconsistent and the whole tuning had to be redo for every single major update.

It depends on what you want to do with your engine. It's fine if you intend it only engine vs engine, but certainly not against humans. A better weakened algorithm for playing a human would be something that would crumple against pressure, occasionally lose a pawn etc etc.

I gave up the idea of modifying the search algorithm. Instead, I always have the engine think with it's strongest strength. Say, we're playing 1600, the engine will calculate the best four moves. I then add a deterministic drift and a stochastic diffusion to the scores. I resemble the how an financial option is priced, I model the PV scores as a SDE where the error term is a Geometric Brownian Motion.

So that an non-optimistic move would be more likely to be played if I increase the diffusion and drift coefficients. I also add some effects if the user thinks for a move for too long or too quick. I consider it's a way of saying whether the position is simple or complicated. If it's complicated and the user thinks for a long time, I believe I should give some bonus and increase the probability of an error and a blunder. I also adjust the the probability if I have their FICS results and based on the previous results with the software.

I wrote a script that allows my software to play on FICS against human opponents for hundreds of hundreds of games. The results were very and very accurate on the FICS scale. If I have 20 levels, I would have 20 FICS account. The script automatically adjust the coefficients for each account until to the point I'm satisfied.

User avatar
emadsen
Posts: 316
Joined: Wed Apr 25, 2012 11:51 pm
Location: Oak Park, IL, USA
Full name: Erik Madsen
Contact:

Re: Score Inaccuracy: An Engine Weakening Algorithm

Post by emadsen » Thu Nov 01, 2012 3:16 am

A better weakened algorithm for playing a human would be something that would crumple against pressure, occasionally lose a pawn etc etc.
Agreed. But I'd prefer to start simple and worry about modeling complex behavior later.
the engine will calculate the best four moves
Do you do this with a multi-PV search? Because in a standard PV search all non-PV moves are equally bad. They fail low in a zero-window search and there's no way to distinguish how bad they are.
I then add a deterministic drift and a stochastic diffusion to the scores. I resemble the how an financial option is priced, I model the PV scores as a SDE where the error term is a Geometric Brownian Motion.
Huh? :?
I wrote a script that allows my software to play on FICS against human opponents for hundreds of hundreds of games.
Excellent. That's the ultimate test of whether your ELO parameter is calibrated accurately.
My C# chess engine: https://www.madchess.net

kinderchocolate
Posts: 454
Joined: Mon Nov 01, 2010 5:55 am
Full name: Ted Wong
Contact:

Re: Score Inaccuracy: An Engine Weakening Algorithm

Post by kinderchocolate » Thu Nov 01, 2012 3:42 am

Sorry for making it clean. It was a multi-PV search. How exactly it was conducted was depend on the difficulty. I've found a multi-pv of 3 is enough to trash over 90% of the chess players. Less than 3 would be very difficulty to beat.

My idea is similar to Stockfishand Houdini. They add some random factors once the search is complete. They don't try to stuff the actual search, it's the results that they manipulate. It's a very simple and effective strategy. What I did was I assume the random factors can be modelled by a normal distribution. My job was to calibrate that normal distribution.



emadsen wrote:
A better weakened algorithm for playing a human would be something that would crumple against pressure, occasionally lose a pawn etc etc.
Agreed. But I'd prefer to start simple and worry about modeling complex behavior later.
the engine will calculate the best four moves
Do you do this with a multi-PV search? Because in a standard PV search all non-PV moves are equally bad. They fail low in a zero-window search and there's no way to distinguish how bad they are.
I then add a deterministic drift and a stochastic diffusion to the scores. I resemble the how an financial option is priced, I model the PV scores as a SDE where the error term is a Geometric Brownian Motion.
Huh? :?
I wrote a script that allows my software to play on FICS against human opponents for hundreds of hundreds of games.
Excellent. That's the ultimate test of whether your ELO parameter is calibrated accurately.

syzygy
Posts: 5048
Joined: Tue Feb 28, 2012 10:56 pm

Re: Score Inaccuracy: An Engine Weakening Algorithm

Post by syzygy » Thu Nov 01, 2012 12:10 pm

kinderchocolate wrote:I gave up the idea of modifying the search algorithm. Instead, I always have the engine think with it's strongest strength. Say, we're playing 1600, the engine will calculate the best four moves. I then add a deterministic drift and a stochastic diffusion to the scores. I resemble the how an financial option is priced, I model the PV scores as a SDE where the error term is a Geometric Brownian Motion.
Do the errors terms you add depend on the scores of those best four moves?

If they don't, you could as well add such error terms to all moves before you search, then use Erik's technique for getting the search windows right. This technique is in fact only manipulating the results. (It manipulates the search only in the way multi-pv manipulates the search, but with less overhead. Of course the overhead is not much of an issue when the goal is to weaken the engine.)

I've used the same technique for randomising the first few moves when out of book.

bob
Posts: 20925
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Score Inaccuracy: An Engine Weakening Algorithm

Post by bob » Fri Nov 02, 2012 1:25 pm

emadsen wrote:I'd like to describe the technique I use to weaken my engine, MadChess, and ask a couple questions:

1) How do you weaken the playing strength of your engine? Do you use a technique similar to "score inaccuracy" or do something totally different?
2) Have you measured the correlation between weakening parameters and playing strength (ELO)? I'd appreciate any information you're willing to share.

So here's "score inaccuracy." I hesitate to call it an algorithm because the code is very simple:

At full strength (ScoreInaccuracy = 0)
  1. Peform an iterative deepening PVS search.
  2. Search first move with an aspiration window.
  3. If score falls outside aspiration boundary, research with infinite window.
  4. On subsequent moves, search with zero window, expanding to infinite window if score fails high.
At weakened strength (ScoreInaccuracy > 0)
  1. First assign an Error to each legal move, from -ScoreInaccuracy to +ScoreInaccuracy.
  2. Perform an iterative deepening PVS search.
  3. Search first move with a window equal to normal aspiration window + ScoreInaccuracy.
  4. If score falls outside aspiration boundary, research with infinite window.
  5. On subsequent moves, search with a window equal to 1 (the normal zero window) + ScoreInaccuracy, expanding to infinite window if score fails high.
  6. Add the move's Error to its minimax score before testing alpha / beta bounds.
I feel the weakened search should have the same form as the full strength search so it does not suffer a huge performance hit, for example, were it to perform an infinite-window search for every root move. The weakness should come from the score Error, not a performance degradation. Also, I wanted the search to look like a real search to the user- manage time, report score, depth, and principal variation. And I wanted to avoid a wildly fluctuating score as the search progressed- hence each move is assigned an Error that applies at every depth.

Note that I add Error to root moves and not to evaluations at the leaf nodes. I did this primarily because it's much easier to reason about the effect it will have on playing strength. I suspected randomization in evaluation would get lost in statistical noise.

I haven't played enough games against a weakened MadChess to get a good sense of how it "feels." But I have measured its playing strength against a common pool of opponents (no self-play), varying the ScoreInaccuracy parameter. I intend to use this data to calibrate the UCI_Elo parameter.

Image

Here's the code:

Code: Select all

// Snip
foreach &#40;Move objMove in this.Search.GetMoveSelector&#40;this.SearchState, objSearchDepth&#41;)
&#123;                
    if &#40;this.Board.IsMoveLegal&#40;objMove&#41;)
    &#123;
        // Move is legal
        colLegalMoves.Add&#40;objMove&#41;;
        ScoredMove objScoredMove = new ScoredMove&#40;objMove&#41;;
        // Determine error.
        if &#40;this.ScoreInaccuracy > 0&#41;
        &#123;
            objScoredMove.Error = mobjRandom.Next&#40;-this.ScoreInaccuracy, this.ScoreInaccuracy + 1&#41;;
        &#125;
        else
        &#123;
            objScoredMove.Error = 0;
        &#125;
        this.SearchState.ScoredMoves.Add&#40;objScoredMove&#41;;
    &#125;
&#125;
// Snip
this.SearchMoves&#40;this.SearchState, objSearchDepth, colLegalMoves&#41;;


private void SearchMoves&#40;SearchState SearchState, SearchDepth SearchDepth, Moves Moves&#41;
&#123;
    int intBestScore = -this.Evaluation.MaxScore;
    bool bolPVCorrect = true;
    int intLegalMove = 0;
    int intPVMove = 1;
    foreach&#40;Move objMove in this.Search.GetMoveSelector&#40;SearchState, SearchDepth, Moves&#41;)
    &#123;
        if (!objMove.IsLegal.HasValue&#41;
        &#123;
            // Determine if move is legal.
            objMove.IsLegal = SearchState.Board.IsMoveLegal&#40;objMove&#41;;
        &#125;
        if &#40;objMove.IsLegal == true&#41;
        &#123;
            intLegalMove++;
        &#125;
        else
        &#123;
            // Skip illegal move.
            continue;
        &#125;
        ScoredMove objScoredMove = SearchState.ScoredMoves&#91;objMove&#93;;
        // Update search state.
        SearchState.RootMove = objMove;
        SearchState.RootMoveNumber = intLegalMove;
        // Play move.
        this.Board.PlayMove&#40;objMove&#41;;
        if &#40;intLegalMove == 1&#41;
        &#123;
            // First move
            this.SearchState.SearchStats.PVNodes++;
            if &#40;this.SearchState.BestMove.Move == null&#41;
            &#123;
                // Search with infinite alpha / beta window.
                objScoredMove.Score = -this.Search.Recurse&#40;SearchState, SearchDepth.MoveTowardsHorizon&#40;), -this.Evaluation.MaxScore, this.Evaluation.MaxScore&#41;;
            &#125;
            else
            &#123;
                // Search with aspiration window.
                int intAspirationScore = this.SearchState.BestMove.Score;
                int intAspirationWindow;
                if &#40;this.ScoreInaccuracy > 0&#41;
                &#123;
                    intAspirationWindow = this.Search.AspirationWindow + this.ScoreInaccuracy;
                &#125;
                else
                &#123;
                    intAspirationWindow = this.Search.AspirationWindow;
                &#125;
                objScoredMove.Score = this.SearchWithAspirationWindow&#40;SearchState, SearchDepth.MoveTowardsHorizon&#40;), intAspirationScore, intAspirationWindow&#41;;
            &#125;
        &#125;
        else
        &#123;
            // Later move     
            int intAlpha = intBestScore - this.ScoreInaccuracy - 1;
            int intBeta = intBestScore + this.ScoreInaccuracy;
            objScoredMove.Score = -this.Search.Recurse&#40;SearchState, SearchDepth.MoveTowardsHorizon&#40;), -intBeta, -intAlpha&#41;;
            if (&#40;objScoredMove.Score + objScoredMove.Error&#41; >= intBestScore&#41;
            &#123;
                // Move may be stronger than principal variation.
                // Search with infinite alpha / beta window.
                objScoredMove.Score = -this.Search.Recurse&#40;SearchState, SearchDepth.MoveTowardsHorizon&#40;), -this.Evaluation.MaxScore, this.Evaluation.MaxScore&#41;;
            &#125;
        &#125;
        // Undo move.
        this.Board.UndoMove&#40;);
        if &#40;objScoredMove.Score == this.Evaluation.InterruptedSearchScore&#41;
        &#123;
            // Stop searching.
            return;
        &#125;
        // Add error to score.
        objScoredMove.Score += objScoredMove.Error; 
        if &#40;objScoredMove.Score > intBestScore&#41;
        &#123;
            // New principal variation.
            intPVMove = intLegalMove;
            if &#40;intLegalMove > 1&#41;
            &#123;
                // Principal variation incorrect.
                bolPVCorrect = false;
            &#125;
            // Update best score.
            intBestScore = objScoredMove.Score;
        &#125;                
        this.SearchState.SearchStats.MovesSearched++;
    &#125;
    this.SearchState.SearchStats.PVMoveNumber += intPVMove;
    if &#40;bolPVCorrect&#41;
    &#123;
        this.SearchState.SearchStats.PVNodesCorrect++;
    &#125;
&#125;


private int SearchWithAspirationWindow&#40;SearchState SearchState, SearchDepth SearchDepth, int AspirationScore, int AspirationWindow&#41;
&#123;
    int intAspirationAlpha = AspirationScore - AspirationWindow;
    int intAspirationBeta = AspirationScore + AspirationWindow;
    this.SearchState.SearchStats.AspirationNodes++;
    // Search with aspiration window.
    int intScore = -this.Search.Recurse&#40;SearchState, SearchDepth, -intAspirationBeta, -intAspirationAlpha&#41;;
    if &#40;Math.Abs&#40;intScore&#41; == this.Evaluation.InterruptedSearchScore&#41;
    &#123;
        // Search was interrupted.
        this.SearchState.SearchStats.AspirationNodes--;
    &#125;
    else if (&#40;intScore <= intAspirationAlpha&#41; || &#40;intScore >= intAspirationBeta&#41;)
    &#123;
        // Score outside aspiration window.
        // Search with infinite alpha / beta window.
        intScore = -this.Search.Recurse&#40;SearchState, SearchDepth, -this.Evaluation.MaxScore, this.Evaluation.MaxScore&#41;;
    &#125;   
    else
    &#123;
        // Score within aspiration window.
        this.SearchState.SearchStats.AspirationNodesCorrect++;
    &#125;        
    return intScore;
&#125;
If all you do is add some sort of random bias to your scores, and don't change anything else, you will have a "floor" on your performance that is much higher than you might imagine. Don Beal tested a program with a purely random eval and found it did not play foolishly at all. In fact, it played amazingly strong chess. I started out with the "skill" level command in Crafty by doing the same thing, and several testers complained that it was way too strong, even at skill 0, which is purely random.

To make this work, I had to hurt the program on two separate points. Add random noise to the eval AND slow the search speed down so that the "Beal effect" was minimized and random eval would not produce an 1800+ skill level...

Uri Blass
Posts: 9129
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

Re: Score Inaccuracy: An Engine Weakening Algorithm

Post by Uri Blass » Fri Nov 02, 2012 2:41 pm

bob wrote:
emadsen wrote:I'd like to describe the technique I use to weaken my engine, MadChess, and ask a couple questions:

1) How do you weaken the playing strength of your engine? Do you use a technique similar to "score inaccuracy" or do something totally different?
2) Have you measured the correlation between weakening parameters and playing strength (ELO)? I'd appreciate any information you're willing to share.

So here's "score inaccuracy." I hesitate to call it an algorithm because the code is very simple:

At full strength (ScoreInaccuracy = 0)
  1. Peform an iterative deepening PVS search.
  2. Search first move with an aspiration window.
  3. If score falls outside aspiration boundary, research with infinite window.
  4. On subsequent moves, search with zero window, expanding to infinite window if score fails high.
At weakened strength (ScoreInaccuracy > 0)
  1. First assign an Error to each legal move, from -ScoreInaccuracy to +ScoreInaccuracy.
  2. Perform an iterative deepening PVS search.
  3. Search first move with a window equal to normal aspiration window + ScoreInaccuracy.
  4. If score falls outside aspiration boundary, research with infinite window.
  5. On subsequent moves, search with a window equal to 1 (the normal zero window) + ScoreInaccuracy, expanding to infinite window if score fails high.
  6. Add the move's Error to its minimax score before testing alpha / beta bounds.
I feel the weakened search should have the same form as the full strength search so it does not suffer a huge performance hit, for example, were it to perform an infinite-window search for every root move. The weakness should come from the score Error, not a performance degradation. Also, I wanted the search to look like a real search to the user- manage time, report score, depth, and principal variation. And I wanted to avoid a wildly fluctuating score as the search progressed- hence each move is assigned an Error that applies at every depth.

Note that I add Error to root moves and not to evaluations at the leaf nodes. I did this primarily because it's much easier to reason about the effect it will have on playing strength. I suspected randomization in evaluation would get lost in statistical noise.

I haven't played enough games against a weakened MadChess to get a good sense of how it "feels." But I have measured its playing strength against a common pool of opponents (no self-play), varying the ScoreInaccuracy parameter. I intend to use this data to calibrate the UCI_Elo parameter.

Image

Here's the code:

Code: Select all

// Snip
foreach &#40;Move objMove in this.Search.GetMoveSelector&#40;this.SearchState, objSearchDepth&#41;)
&#123;                
    if &#40;this.Board.IsMoveLegal&#40;objMove&#41;)
    &#123;
        // Move is legal
        colLegalMoves.Add&#40;objMove&#41;;
        ScoredMove objScoredMove = new ScoredMove&#40;objMove&#41;;
        // Determine error.
        if &#40;this.ScoreInaccuracy > 0&#41;
        &#123;
            objScoredMove.Error = mobjRandom.Next&#40;-this.ScoreInaccuracy, this.ScoreInaccuracy + 1&#41;;
        &#125;
        else
        &#123;
            objScoredMove.Error = 0;
        &#125;
        this.SearchState.ScoredMoves.Add&#40;objScoredMove&#41;;
    &#125;
&#125;
// Snip
this.SearchMoves&#40;this.SearchState, objSearchDepth, colLegalMoves&#41;;


private void SearchMoves&#40;SearchState SearchState, SearchDepth SearchDepth, Moves Moves&#41;
&#123;
    int intBestScore = -this.Evaluation.MaxScore;
    bool bolPVCorrect = true;
    int intLegalMove = 0;
    int intPVMove = 1;
    foreach&#40;Move objMove in this.Search.GetMoveSelector&#40;SearchState, SearchDepth, Moves&#41;)
    &#123;
        if (!objMove.IsLegal.HasValue&#41;
        &#123;
            // Determine if move is legal.
            objMove.IsLegal = SearchState.Board.IsMoveLegal&#40;objMove&#41;;
        &#125;
        if &#40;objMove.IsLegal == true&#41;
        &#123;
            intLegalMove++;
        &#125;
        else
        &#123;
            // Skip illegal move.
            continue;
        &#125;
        ScoredMove objScoredMove = SearchState.ScoredMoves&#91;objMove&#93;;
        // Update search state.
        SearchState.RootMove = objMove;
        SearchState.RootMoveNumber = intLegalMove;
        // Play move.
        this.Board.PlayMove&#40;objMove&#41;;
        if &#40;intLegalMove == 1&#41;
        &#123;
            // First move
            this.SearchState.SearchStats.PVNodes++;
            if &#40;this.SearchState.BestMove.Move == null&#41;
            &#123;
                // Search with infinite alpha / beta window.
                objScoredMove.Score = -this.Search.Recurse&#40;SearchState, SearchDepth.MoveTowardsHorizon&#40;), -this.Evaluation.MaxScore, this.Evaluation.MaxScore&#41;;
            &#125;
            else
            &#123;
                // Search with aspiration window.
                int intAspirationScore = this.SearchState.BestMove.Score;
                int intAspirationWindow;
                if &#40;this.ScoreInaccuracy > 0&#41;
                &#123;
                    intAspirationWindow = this.Search.AspirationWindow + this.ScoreInaccuracy;
                &#125;
                else
                &#123;
                    intAspirationWindow = this.Search.AspirationWindow;
                &#125;
                objScoredMove.Score = this.SearchWithAspirationWindow&#40;SearchState, SearchDepth.MoveTowardsHorizon&#40;), intAspirationScore, intAspirationWindow&#41;;
            &#125;
        &#125;
        else
        &#123;
            // Later move     
            int intAlpha = intBestScore - this.ScoreInaccuracy - 1;
            int intBeta = intBestScore + this.ScoreInaccuracy;
            objScoredMove.Score = -this.Search.Recurse&#40;SearchState, SearchDepth.MoveTowardsHorizon&#40;), -intBeta, -intAlpha&#41;;
            if (&#40;objScoredMove.Score + objScoredMove.Error&#41; >= intBestScore&#41;
            &#123;
                // Move may be stronger than principal variation.
                // Search with infinite alpha / beta window.
                objScoredMove.Score = -this.Search.Recurse&#40;SearchState, SearchDepth.MoveTowardsHorizon&#40;), -this.Evaluation.MaxScore, this.Evaluation.MaxScore&#41;;
            &#125;
        &#125;
        // Undo move.
        this.Board.UndoMove&#40;);
        if &#40;objScoredMove.Score == this.Evaluation.InterruptedSearchScore&#41;
        &#123;
            // Stop searching.
            return;
        &#125;
        // Add error to score.
        objScoredMove.Score += objScoredMove.Error; 
        if &#40;objScoredMove.Score > intBestScore&#41;
        &#123;
            // New principal variation.
            intPVMove = intLegalMove;
            if &#40;intLegalMove > 1&#41;
            &#123;
                // Principal variation incorrect.
                bolPVCorrect = false;
            &#125;
            // Update best score.
            intBestScore = objScoredMove.Score;
        &#125;                
        this.SearchState.SearchStats.MovesSearched++;
    &#125;
    this.SearchState.SearchStats.PVMoveNumber += intPVMove;
    if &#40;bolPVCorrect&#41;
    &#123;
        this.SearchState.SearchStats.PVNodesCorrect++;
    &#125;
&#125;


private int SearchWithAspirationWindow&#40;SearchState SearchState, SearchDepth SearchDepth, int AspirationScore, int AspirationWindow&#41;
&#123;
    int intAspirationAlpha = AspirationScore - AspirationWindow;
    int intAspirationBeta = AspirationScore + AspirationWindow;
    this.SearchState.SearchStats.AspirationNodes++;
    // Search with aspiration window.
    int intScore = -this.Search.Recurse&#40;SearchState, SearchDepth, -intAspirationBeta, -intAspirationAlpha&#41;;
    if &#40;Math.Abs&#40;intScore&#41; == this.Evaluation.InterruptedSearchScore&#41;
    &#123;
        // Search was interrupted.
        this.SearchState.SearchStats.AspirationNodes--;
    &#125;
    else if (&#40;intScore <= intAspirationAlpha&#41; || &#40;intScore >= intAspirationBeta&#41;)
    &#123;
        // Score outside aspiration window.
        // Search with infinite alpha / beta window.
        intScore = -this.Search.Recurse&#40;SearchState, SearchDepth, -this.Evaluation.MaxScore, this.Evaluation.MaxScore&#41;;
    &#125;   
    else
    &#123;
        // Score within aspiration window.
        this.SearchState.SearchStats.AspirationNodesCorrect++;
    &#125;        
    return intScore;
&#125;
If all you do is add some sort of random bias to your scores, and don't change anything else, you will have a "floor" on your performance that is much higher than you might imagine. Don Beal tested a program with a purely random eval and found it did not play foolishly at all. In fact, it played amazingly strong chess. I started out with the "skill" level command in Crafty by doing the same thing, and several testers complained that it was way too strong, even at skill 0, which is purely random.

To make this work, I had to hurt the program on two separate points. Add random noise to the eval AND slow the search speed down so that the "Beal effect" was minimized and random eval would not produce an 1800+ skill level...
I think that the way that Erik describe is different than what you do.

Erik did not change the evaluation but simply defined error for every legal move(in other words the score is different than the score by normal search only because of the root move and not because of different evaluation in the leaves)

In this case weak moves may easily become the best so I expect the program to play at beginner level with a big error margin(let say of 20 pawns) even without limiting the search because it is often going to lose pieces unless it see that losing the piece leads to mate(it often may not make a simple capture because the capturing move has an error of 10 pawns against it and the capturing move is not better than other moves by 10 pawns0 .

It is not the same as what you do of doing random evaluation in every node that I expect to play relatively stronger even when the evaluation is really random.

jdart
Posts: 4162
Joined: Fri Mar 10, 2006 4:23 am
Location: http://www.arasanchess.org

Re: Score Inaccuracy: An Engine Weakening Algorithm

Post by jdart » Fri Nov 02, 2012 3:20 pm

I preferred changing the leaf evals because the root search logic then does not need alteration.

And I also limit speed as Bob does: because at normal search speed you will get very high depths and if your score inaccuracy is not very large then the program will still find deep tactical shots that win material.

It is still a challenge to get the program to play reasonable-looking moves at low strength. You don't actually want it to just move randomly because even weak human players do not do that. IMO it would be better to let some eval terms like center control still guide the search while still introducing some move randomness, but I have not yet found a good way to do that.

--Jon

Uri Blass
Posts: 9129
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

Re: Score Inaccuracy: An Engine Weakening Algorithm

Post by Uri Blass » Sat Nov 03, 2012 10:09 am

I do not see the point of trying to emulate weak humans.
If I want to play against something that play the same as humans then the best thing is simply to play against humans and it is easy to find opponents in the internet.

If I want to play against a weak computer then I want something different.

I see no problem with weak level that simply play bad positional moves or even blunder pieces at weak level but not blunder to allow mate that the search can see.

A possible option that I think that is even better than having a random number for every legal move is not to attach a random number to every root every move but simply start with a random move and
change your mind only if you see something that is at least x pawns better than the move that you found.

I guess that even when x=0.5 pawn the program is not going to play well enough to get a level of fide rating above 2000 because in many cases it is going to make significant positional blunders because the random move is only 0.3 pawns worse than the best move.

My guess is that
usually with x=0.5 the human is going to get a positional advantage in the games when the only problem is going to be to translate it to a win but not doing tactical mistakes with a big positional advantage is relatively easy so humans may often be succesful at least in getting a draw.

bob
Posts: 20925
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Score Inaccuracy: An Engine Weakening Algorithm

Post by bob » Sat Nov 03, 2012 11:05 pm

jdart wrote:I preferred changing the leaf evals because the root search logic then does not need alteration.

And I also limit speed as Bob does: because at normal search speed you will get very high depths and if your score inaccuracy is not very large then the program will still find deep tactical shots that win material.

It is still a challenge to get the program to play reasonable-looking moves at low strength. You don't actually want it to just move randomly because even weak human players do not do that. IMO it would be better to let some eval terms like center control still guide the search while still introducing some move randomness, but I have not yet found a good way to do that.

--Jon
I don't like just adding a fixed bonus for each root move. If you make the bonus too large, play becomes random...

Post Reply