MadChess 3.0 Beta Build 075 (Eval Param Tuning)

I ported my particle swarm tuning code from MadChess 2.x to MadChess 3.0 Beta, then simplified and improved it. My code uses the Texel tuning technique described by Peter Österlund in a TalkChess forum post. I improved my particle swarm algorithm in the following manner.

  • Simplified update of evaluation parameters via EvaluationConfig class.
  • Run the Iterate method of each ParticleSwarm on the .NET Core threadpool instead of using dedicated threads.
  • Locate global best particle (among all particle swarms) and update particle velocities after all Iterate methods have completed. This eliminates need to synchronize reads and writes of global state via a lock (to make code thread-safe). Algorithm performs best if number of particle swarms <= number of physical CPU cores.
  • Randomize location of all particles, except the global best, if 10 iterations fail to improve evaluation error. Retaining the global best causes other particles to be drawn back towards it, though their motions are randomized- they’re also drawn towards their individual best and swarm best with random magnitudes, so they jitter in particle-space. They may encounter a new global best on their path towards the last known global best.

In his post, Peter describes how to calibrate evaluation parameters by examining a large collection of games played by strong Grandmasters or engines. By scoring every position in every game, mapping the score (which represents fractional pawn units) to a winning percentage using a sigmoid function, then summing the square of the difference between the winning percentage and the actual result of the game (0 = player-to-move loses, 1/2 = draw, 1 = win), the chess engine’s strength can be improved by minimizing the evaluation error. Peter does not describe how to minimize the error- that effort is left for the chess engine programmer. The minimization effort is challenging because the parameter space is huge. MadChess 3.0 Beta’s evaluation function considers only material and piece square location, and yet, given reasonable minimum and maximum integer values for all evaluation parameters, 1.75 x 1068 discrete parameter combinations are possible.

Skip Code, Go To Results

Particle.cs

public void ConfigureEvaluation(Evaluation Evaluation)
{
    EvaluationConfig evalConfig = Evaluation.Config;
    // Middlegame
    // Pawns
    evalConfig.MgPawnAdvancement = Parameters[nameof(EvaluationConfig.MgPawnAdvancement)].Value;
    evalConfig.MgPawnCentrality = Parameters[nameof(EvaluationConfig.MgPawnCentrality)].Value;
    // Knights
    evalConfig.MgKnightAdvancement = Parameters[nameof(EvaluationConfig.MgKnightAdvancement)].Value;
    evalConfig.MgKnightCentrality = Parameters[nameof(EvaluationConfig.MgKnightCentrality)].Value;
    evalConfig.MgKnightCorner = Parameters[nameof(EvaluationConfig.MgKnightCorner)].Value;
    evalConfig.MgKnightConstant = Parameters[nameof(EvaluationConfig.MgKnightConstant)].Value;
    // Bishops
    evalConfig.MgBishopAdvancement = Parameters[nameof(EvaluationConfig.MgBishopAdvancement)].Value;
    evalConfig.MgBishopCentrality = Parameters[nameof(EvaluationConfig.MgBishopCentrality)].Value;
    evalConfig.MgBishopCorner = Parameters[nameof(EvaluationConfig.MgBishopCorner)].Value;
    evalConfig.MgBishopConstant = Parameters[nameof(EvaluationConfig.MgBishopConstant)].Value;
    // Rooks
    evalConfig.MgRookAdvancement = Parameters[nameof(EvaluationConfig.MgRookAdvancement)].Value;
    evalConfig.MgRookCentrality = Parameters[nameof(EvaluationConfig.MgRookCentrality)].Value;
    evalConfig.MgRookCorner = Parameters[nameof(EvaluationConfig.MgRookCorner)].Value;
    evalConfig.MgRookConstant = Parameters[nameof(EvaluationConfig.MgRookConstant)].Value;
    // Queens
    evalConfig.MgQueenAdvancement = Parameters[nameof(EvaluationConfig.MgQueenAdvancement)].Value;
    evalConfig.MgQueenCentrality = Parameters[nameof(EvaluationConfig.MgQueenCentrality)].Value;
    evalConfig.MgQueenCorner = Parameters[nameof(EvaluationConfig.MgQueenCorner)].Value;
    evalConfig.MgQueenConstant = Parameters[nameof(EvaluationConfig.MgQueenConstant)].Value;
    // King
    evalConfig.MgKingAdvancement = Parameters[nameof(EvaluationConfig.MgKingAdvancement)].Value;
    evalConfig.MgKingCentrality = Parameters[nameof(EvaluationConfig.MgKingCentrality)].Value;
    evalConfig.MgKingCorner = Parameters[nameof(EvaluationConfig.MgKingCorner)].Value;
    // Endgame
    // Pawns
    evalConfig.EgPawnAdvancement = Parameters[nameof(EvaluationConfig.EgPawnAdvancement)].Value;
    evalConfig.EgPawnCentrality = Parameters[nameof(EvaluationConfig.EgPawnCentrality)].Value;
    // Knights
    evalConfig.EgKnightAdvancement = Parameters[nameof(EvaluationConfig.EgKnightAdvancement)].Value;
    evalConfig.EgKnightCentrality = Parameters[nameof(EvaluationConfig.EgKnightCentrality)].Value;
    evalConfig.EgKnightCorner = Parameters[nameof(EvaluationConfig.EgKnightCorner)].Value;
    evalConfig.EgKnightConstant = Parameters[nameof(EvaluationConfig.EgKnightConstant)].Value;
    // Bishops
    evalConfig.EgBishopAdvancement = Parameters[nameof(EvaluationConfig.EgBishopAdvancement)].Value;
    evalConfig.EgBishopCentrality = Parameters[nameof(EvaluationConfig.EgBishopCentrality)].Value;
    evalConfig.EgBishopCorner = Parameters[nameof(EvaluationConfig.EgBishopCorner)].Value;
    evalConfig.EgBishopConstant = Parameters[nameof(EvaluationConfig.EgBishopConstant)].Value;
    // Rooks
    evalConfig.EgRookAdvancement = Parameters[nameof(EvaluationConfig.EgRookAdvancement)].Value;
    evalConfig.EgRookCentrality = Parameters[nameof(EvaluationConfig.EgRookCentrality)].Value;
    evalConfig.EgRookCorner = Parameters[nameof(EvaluationConfig.EgRookCorner)].Value;
    evalConfig.EgRookConstant = Parameters[nameof(EvaluationConfig.EgRookConstant)].Value;
    // Queens
    evalConfig.EgQueenAdvancement = Parameters[nameof(EvaluationConfig.EgQueenAdvancement)].Value;
    evalConfig.EgQueenCentrality = Parameters[nameof(EvaluationConfig.EgQueenCentrality)].Value;
    evalConfig.EgQueenCorner = Parameters[nameof(EvaluationConfig.EgQueenCorner)].Value;
    evalConfig.EgQueenConstant = Parameters[nameof(EvaluationConfig.EgQueenConstant)].Value;
    // King
    evalConfig.EgKingAdvancement = Parameters[nameof(EvaluationConfig.EgKingAdvancement)].Value;
    evalConfig.EgKingCentrality = Parameters[nameof(EvaluationConfig.EgKingCentrality)].Value;
    evalConfig.EgKingCorner = Parameters[nameof(EvaluationConfig.EgKingCorner)].Value;
    Evaluation.Configure();
}

How large is 1.75 x 1068? I need add only a few more evaluation parameters for the number of discrete parameter combinations to surpass the number of atoms in the universe.

I majored in physics in college, but it’s been a while since I’ve read math-intensive scientific papers, so rather than implement ADAM or other multivariate, derivative-free gradient descent algorithms (or determine how to plug the MadChess 3.0 Beta evaluation error cost function into a third-party optimization library), I decided to trust the particles. They succeeded in finding better evaluation parameters for MadChess 2.x, and they’ve succeeded again for MadChess 3.0 Beta.

While not a complete listing, here’s code that illustrates my implementation of a multi-threaded particle swarm optimizer.

UciStream.cs

private void Tune(IList<string> Tokens)
{
    string pgnFilename = Tokens[1].Trim();
    int particleSwarmsCount = int.Parse(Tokens[2].Trim());
    int particlesPerSwarm = int.Parse(Tokens[3].Trim());
    int winPercentScale = int.Parse(Tokens[4].Trim()); // Use 661 for Gm2700EloGamesSince2000.pgn.
    int iterations = int.Parse(Tokens[5].Trim());
    _commandStopwatch.Restart();
    ParticleSwarms particleSwarms = new ParticleSwarms(pgnFilename, particleSwarmsCount, particlesPerSwarm, winPercentScale, WriteMessageLine);
    particleSwarms.Optimize(iterations);
    _commandStopwatch.Stop();
}

ParticleSwarms.cs

public void Optimize(int Iterations)
{
    // Determine size of parameter space.
    double parameterSpace = 1d;
    Particle firstParticleInFirstSwarm = this[0].Particles[0];
    for (int index = 0; index < firstParticleInFirstSwarm.Parameters.Count; index++)
    {
        Parameter parameter = firstParticleInFirstSwarm.Parameters[index];
        parameterSpace *= parameter.MaxValue - parameter.MinValue + 1;
    }
    _writeMessageLine($"Optimizing {firstParticleInFirstSwarm.Parameters.Count} parameters in a space of {parameterSpace:e2} discrete parameter combinations.");
    // Create game objects for each particle swarm.
    Board[] boards = new Board[Count];
    Search[] searches = new Search[Count];
    Evaluation[] evaluations = new Evaluation[Count];
    for (int index = 0; index < Count; index++)
    {
        Board board = new Board(_writeMessageLine);
        board.PrecalculatedMoves = new PrecalculatedMoves(board.BishopMoveMasks, board.RookMoveMasks, board.CreateMoveDestinationsMask, _writeMessageLine);
        boards[index] = board;
        Cache cache = new Cache(1, board.ValidateMove);
        KillerMoves killerMoves = new KillerMoves(Search.MaxHorizon);
        MoveHistory moveHistory = new MoveHistory();
        Evaluation evaluation = new Evaluation(new EvaluationConfig(), board.GetPositionCount);
        evaluations[index] = evaluation;
        searches[index] = new Search(cache, killerMoves, moveHistory, evaluation, () => false, _writeMessageLine);
    }
    Task[] tasks = new Task[Count];
    int iterationsWithoutProgress = 0;
    double bestEvaluationError = double.MaxValue;
    for (int iteration = 1; iteration <= Iterations; iteration++)
    {
        // Run iteration tasks on threadpool.
        _iterations = iteration;
        for (int index = 0; index < Count; index++)
        {
            ParticleSwarm particleSwarm = this[index];
            Board board = boards[index];
            Search search = searches[index];
            Evaluation evaluation = evaluations[index];
            tasks[index] = Task.Run(() => particleSwarm.Iterate(board, search, evaluation));
        }
        // Wait for all particle swarms to complete an iteration.
        Task.WaitAll(tasks);
        Particle bestParticle = GetBestParticle();
        if (bestParticle.EvaluationError < bestEvaluationError)
        {
            bestEvaluationError = bestParticle.BestEvaluationError;
            iterationsWithoutProgress = 0;
        }
        else iterationsWithoutProgress++;
        if (iterationsWithoutProgress == _maxIterationsWithoutProgress)
        {
            RandomizeParticles(bestParticle);
            iterationsWithoutProgress = 0;
        }
        else UpdateVelocity();
        UpdateStatus();
    }
}

ParticleSwarm.cs

public void Iterate(Board Board, Search Search, Evaluation Evaluation)
{
    Particle bestParticle = GetBestParticle();
    for (int index = 0; index < Particles.Count; index++)
    {
        Particle particle = Particles[index];
        if (!ReferenceEquals(particle, bestParticle) && (SafeRandom.NextDouble() <= _particleDeathPercent))
        {
            // Recreate particle at random location.
            particle = new Particle(particle.PgnGames, particle.Parameters.DuplicateWithRandomValues());
            Particles[index] = particle;
        }
        particle.Move();
        particle.ConfigureEvaluation(Evaluation);
        particle.CalculateEvaluationError(Board, Search, _winPercentScale);
    }
}

Particle.cs

public void Move()
{
    // Move particle in parameter space.
    for (int index = 0; index < Parameters.Count; index++)
    {
        Parameter parameter = Parameters[index];
        parameter.Value += (int) _velocities[index];
        if (parameter.Value < parameter.MinValue)
        {
            parameter.Value = parameter.MinValue;
            _velocities[index] = 0;
        }
        if (parameter.Value > parameter.MaxValue)
        {
            parameter.Value = parameter.MaxValue;
            _velocities[index] = 0;
        }
    }
}

public void CalculateEvaluationError(Board Board, Search Search, int WinPercentScale)
{
    // Sum the square of evaluation error over all games.
    double evaluationError = 0d;
    for (int gameIndex = 0; gameIndex < PgnGames.Count; gameIndex++)
    {
        PgnGame game = PgnGames[gameIndex];
        Board.SetPosition(Board.StartPositionFen, true);
        for (int moveIndex = 0; moveIndex < game.Moves.Count; moveIndex++)
        {
            ulong move = game.Moves[moveIndex];
            // Play move.
            Board.PlayMove(move);
            // Get quiet score.
            Board.NodesExamineTime = long.MaxValue;
            Search.PvInfoUpdate = false;
            Search.Continue = true;
            int quietScore = Search.GetQuietScore(Board, 00-StaticScore.Max, StaticScore.Max);
            // Convert quiet score to win percent.
            double winPercent = GetWinPercent(quietScore, WinPercentScale);
            // Compare win percent to game result.
            double result;
            // ReSharper disable once SwitchStatementMissingSomeCases
            switch (game.Result)
            {
                case GameResult.WhiteWon:
                    result = Board.CurrentPosition.WhiteMove ? 1d : 0;
                    break;
                case GameResult.Draw:
                    result = 0.5d;
                    break;
                case GameResult.BlackWon:
                    result = Board.CurrentPosition.WhiteMove ? 0 : 1d;
                    break;
                default:
                    throw new InvalidOperationException($"{game.Result} game result not supported.");
            }
            evaluationError += Math.Pow(winPercent - result, 2);
        }
    }
    EvaluationError = evaluationError;
    if (EvaluationError < BestEvaluationError)
    {
        BestEvaluationError = EvaluationError;
        Parameters.CopyValuesTo(BestParameters);
    }
}

public void UpdateVelocity(Particle BestSwarmParticle, Particle GloballyBestParticle)
{
    for (int index = 0; index < Parameters.Count; index++)
    {
        Parameter parameter = Parameters[index];
        Parameter bestParameter = BestParameters[index];
        Parameter bestSwarmParameter = BestSwarmParticle.BestParameters[index];
        Parameter globallyBestParameter = GloballyBestParticle.BestParameters[index];
        double velocity = _inertia * _velocities[index];
        double particleMagnitude = SafeRandom.NextDouble() * _influence;
        velocity += particleMagnitude * (bestParameter.Value - parameter.Value);
        double swarmMagnitude = SafeRandom.NextDouble() * ParticleSwarm.Influence;
        velocity += swarmMagnitude * (bestSwarmParameter.Value - parameter.Value);
        double allSwarmsMagnitude = SafeRandom.NextDouble() * ParticleSwarms.Influence;
        velocity += allSwarmsMagnitude * (globallyBestParameter.Value - parameter.Value);
        _velocities[index] = velocity;
    }
}

private static double GetWinPercent(int Score, int WinPercentScale) => 1d / (1d + Math.Pow(10d-1d * Score / WinPercentScale));

Evaluation.cs

public void Configure()
{
    // Calculate piece location values.
    for (int square = 0; square < 64; square++)
    {
        int rank = Board.WhiteRanks[square];
        int file = Board.Files[square];
        int squareCentrality = 3 - Board.GetShortestDistance(square, Board.CentralSquares);
        int fileCentrality = 3 - Math.Min(Math.Abs(3 - file), Math.Abs(4 - file));
        int nearCorner = 3 - Board.GetShortestDistance(square, Board.CornerSquares);
        // Middlegame
        _mgPawnLocations[square] = rank * Config.MgPawnAdvancement + squareCentrality * Config.MgPawnCentrality;
        _mgKnightLocations[square] = rank * Config.MgKnightAdvancement + squareCentrality * Config.MgKnightCentrality + nearCorner * Config.MgKnightCorner + Config.MgKnightConstant;
        _mgBishopLocations[square] = rank * Config.MgBishopAdvancement + squareCentrality * Config.MgBishopCentrality + nearCorner * Config.MgBishopCorner + Config.MgBishopConstant;
        _mgRookLocations[square] = rank * Config.MgRookAdvancement + fileCentrality * Config.MgRookCentrality + nearCorner * Config.MgRookCorner + Config.MgRookConstant;
        _mgQueenLocations[square] = rank * Config.MgQueenAdvancement + squareCentrality * Config.MgQueenCentrality + nearCorner * Config.MgQueenCorner + Config.MgQueenConstant;
        _mgKingLocations[square] = rank * Config.MgKingAdvancement + squareCentrality * Config.MgKingCentrality + nearCorner * Config.MgKingCorner;
        // Endgame
        _egPawnLocations[square] = rank * Config.EgPawnAdvancement + squareCentrality * Config.EgPawnCentrality + Config.EgPawnConstant;
        _egKnightLocations[square] = rank * Config.EgKnightAdvancement + squareCentrality * Config.EgKnightCentrality + nearCorner * Config.EgKnightCorner + Config.EgKnightConstant;
        _egBishopLocations[square] = rank * Config.EgBishopAdvancement + squareCentrality * Config.EgBishopCentrality + nearCorner * Config.EgBishopCorner + Config.EgBishopConstant;
        _egRookLocations[square] = rank * Config.EgRookAdvancement + fileCentrality * Config.EgRookCentrality + nearCorner * Config.EgRookCorner + Config.EgRookConstant;
        _egQueenLocations[square] = rank * Config.EgQueenAdvancement + squareCentrality * Config.EgQueenCentrality + nearCorner * Config.EgQueenCorner + Config.EgQueenConstant;
        _egKingLocations[square] = rank * Config.EgKingAdvancement + squareCentrality * Config.EgKingCentrality + nearCorner * Config.EgKingCorner;
    }
}

 

Tuning Results

I used Chessbase to export all games played between two Grandmasters rated >= 2700 ELO since the year 2000. I realize I could tune MadChess’ evaluation function using games played by stronger engines, such as Stockfish or Komodo. However, I wish to avoid biasing my engine’s playing style towards that of other engines. I’d rather have it emulate a more human playing style. I fed my optimization algorithm the games played by 2700+ ELO Grandmasters since the year 2000 and the particles found new evaluation parameters worth 47 ELO in playing strength.

 

Feature Category Date SVN1 WAC2 ELO Rating3 Improvement
Eval Param Tuning Evaluation 2018 Nov 24 75 272 2143 +47
Sophisticated Search
Material and Piece Location
Baseline 2018 Nov 08 58 269 2096 0
  1. Subversion source code revision (for my own use)
  2. Win At Chess position test, 3 seconds per position
  3. Bullet chess, 2 min / game + 1 sec / move
Bookmark the permalink.

2 Comments

  1. Perhaps the best way to calibrate the parameters is to use a high quality database of long time-control over-the-board games. Excluding Rapid, Blitz, Blindfold, Consultation, Internet, Radio, Telegraph, Exhibition and Simultaneous games. Similar to Norman Pollock’s databases.

    I’m not sure but it seems that you used some blitz chess games.

  2. That’s an excellent point, Pablo. I focused on writing the particle swarm algorithm and treated the games database almost as an afterthought. I mean, I made sure to find games played between evenly matched super GMs, but I didn’t make an effort to filter out games played at fast time controls or non-tournament conditions.

    One of the reasons I wrote the tuning code so early in the process of developing MadChess 3.0 is I want to tune the evaluation parameters regularly. Each new evaluation feature unbalances the engine so I intend to tune its evaluation every two or three features.

    Thanks for pointing out the inconsistent quality of the games. I’ll be sure to use a higher quality database next time.

Leave a Reply

Your email address will not be published. Required fields are marked *