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)
- Peform an iterative deepening PVS search.
- Search first move with an aspiration window.
- If score falls outside aspiration boundary, research with infinite window.
- On subsequent moves, search with zero window, expanding to infinite window if score fails high.
- First assign an Error to each legal move, from -ScoreInaccuracy to +ScoreInaccuracy.
- Perform an iterative deepening PVS search.
- Search first move with a window equal to normal aspiration window + ScoreInaccuracy.
- If score falls outside aspiration boundary, research with infinite window.
- On subsequent moves, search with a window equal to 1 (the normal zero window) + ScoreInaccuracy, expanding to infinite window if score fails high.
- Add the move's Error to its minimax score before testing alpha / beta bounds.
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.
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 ((intScore <= intAspirationAlpha) || (intScore >= intAspirationBeta))
{
// Score outside aspiration window.
// Search with infinite alpha / beta window.
intScore = -this.Search.Recurse(SearchState, SearchDepth, -this.Evaluation.MaxScore, this.Evaluation.MaxScore);
}
else
{
// Score within aspiration window.
this.SearchState.SearchStats.AspirationNodesCorrect++;
}
return intScore;
}