2 Comments

MadChess 3.0 Beta Build 075 (Eval Param Tuning)

  By

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();
}
view raw Particle.cs hosted with ❤ by GitHub

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();
}
view raw UciStream.cs hosted with ❤ by GitHub

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();
}
}
view raw ParticleSwarms.cs hosted with ❤ by GitHub

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);
}
}
view raw ParticleSwarm.cs hosted with ❤ by GitHub

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, 0, 0, -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));
view raw Particle.cs hosted with ❤ by GitHub

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;
}
}
view raw Evaluation.cs hosted with ❤ by GitHub

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 Rev1 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
  2. Win At Chess position test, 3 seconds per position
  3. Bullet chess, 2 min / game + 1 sec / move
No comments

MadChess 3.0 Beta Build 058 (Baseline)

  By

I’ve reached an important milestone in the development of my new chess engine. MadChess 3.0 Beta can play a timed game of chess.

I copied the search function from MadChess 2.0 but implemented an evaluation function from scratch. The search function is rather sophisticated.

  • Alpha / beta negamax
  • PVS with aspiration windows
  • MVV / LVA move order
  • MultiPV with tracking of all principal variations (in search, not in hash table)
  • Hashtable with score, bounds, and best move
  • Delayed move generation (play best move from hashtable before generating moves)
  • Null move pruning
  • Killer moves
  • Move history with aging (used to sort quiet moves)
  • Late move reductions
  • Futility pruning
  • Time management based on total material and material advantage, with “panic” time loss prevention

The evaluation function is very simple.

  • Material
  • Piece location
  • Draw by repetition, 50 moves without a capture or pawn move, or insufficient material
  • Checkmate (obviously)

Move generation is limited to a single function: all moves are generated. I have not implemented separate move generators for captures-only or check-evasion.

I figure there’s no point for me to repeat the exact process I used to develop MadChess 2.0, where I slowly built up search and evaluation functions in tandem. In MadChess 3.0 Beta, I’ve changed the board representation from mailbox to bitboards. This greatly affects the evaluation logic (no more traversing a piece square table) but not the search logic, so it makes sense to retain the search function as-is. After all, the search code is a product of hundreds of hours of engineering and testing.

It will be interesting to measure the Elo value of evaluation features as I add them to MadChess 3.0 Beta. I am aware through personal experience of the highly non-linear relationship between individual search and evaluation features (with regards to contribution to Elo playing strength), so it’s unlikely I’ll find the same Elo values for evaluation features as I found in MadChess 2.0. Now I’m adding them to an engine with a mature search function. Who knows if they’ll be worth more or less than they were in MadChess 2.0? Stay tuned.

OK, what was the result of all this effort just to make a rather dumb chess engine? To answer this question, I ran a gauntlet tournament, pitting MadChess 3.0 Beta against familiar engines.

45) MadChess 3.0        2096.3 :   2000 (+783,=348,-869),  47.9 %

    vs.                        :  games (   +,   =,   -),   (%) :    Diff,    SD, CFS (%)
    Sungorus 1.4               :    200 (  40,  27, 133),  26.8 :  -213.7,  12.8,    0.0
    Waxman 2017                :    200 (  39,  38, 123),  29.0 :  -158.7,  11.1,    0.0
    Zevra 1.8.4                :    200 (  39,  36, 125),  28.5 :  -138.3,  12.9,    0.0
    Napoleon 1.8               :    200 (  43,  43, 114),  32.3 :  -117.7,  16.9,    0.0
    Galjoen 0.37.2             :    200 (  66,  33, 101),  41.3 :   -73.9,  11.9,    0.0
    BikJump 2.01               :    200 (  69,  44,  87),  45.5 :   -18.0,  14.3,   10.4
    Monarch 1.7                :    200 (  90,  37,  73),  54.3 :   +42.9,  15.1,   99.8
    Gerbil 02                  :    200 ( 122,  27,  51),  67.8 :  +114.0,   6.6,  100.0
    Faile 1.4                  :    200 ( 111,  47,  42),  67.3 :  +115.7,  13.8,  100.0
    TSCP 1.81                  :    200 ( 164,  16,  20),  86.0 :  +334.8,  14.6,  100.0

This establishes a baseline rating.

Feature Category Date Rev1 WAC2 Elo Rating3 Improvement
Sophisticated Search
Material and Piece Location		 Baseline 2018 Nov 08 58 269 2096 0
  1. Subversion source code revision
  2. Win At Chess position test, 3 seconds per position
  3. Bullet chess, 2 min / game + 1 sec / move

I will add one evaluation (occasionally search) feature at a time and update this table, so I may track the progress of MadChess 3.0 Beta.

No comments

Banks 71st Amateur Series Division 7

  By

MadChess 2.2 participated in Graham Banks’ 71st amateur tournament in division 7.

                                Orio Bets Topp Lozz Jumb Rook MadC Talt Dros Jone Romi Ares  
 1. Orion 0.5 64-bit            #### 11=0 =1== 000= 1011 0=1= 1=11 0==1 ==11 111= =1=1 =11=  65%  28.5 ( 942.0, 594.0)
 2. Betsabe II 1.84             00=1 #### 10=1 1==0 =110 ===1 011= 1=1= 0101 11=1 0111 10==  61%  27.0 ( 948.0, 573.0)
 3. Topple 0.2.1                =0== 01=0 #### 11=1 0=10 =000 ==01 0111 0011 011= 1=11 1111  58%  25.5 ( 954.0, 520.0)
 4. Lozza 1.18 64-bit           111= 0==1 00=0 #### 0=0= ==11 0=1= 0111 1011 11=1 ===0 ==01  57%  25.0 ( 956.0, 542.5)
 5. Jumbo 0.6.51 64-bit         0100 =001 1=01 1=1= #### 101= =0=0 0111 ===1 =00= 0111 =11=  55%  24.0 ( 960.0, 505.5)
 6. RookieMonster 1.6.3 64-bit  1=0= ===0 =111 ==00 010= #### =1=1 10=1 0111 =1=0 =00= 011=  53%  23.5 ( 962.0, 511.3)
 7. MadChess 2.2 64-bit         0=00 100= ==10 1=0= =1=1 =0=0 #### =000 0111 1==1 11=1 =011  51%  22.5 ( 966.0, 464.3)
 8. Taltos rev118 64-bit        1==0 0=0= 1000 1000 1000 01=0 =111 #### 1001 0==1 1001 1111  48%  21.0 ( 972.0, 432.5)
 9. Drosophila 1.5.1 64-bit     ==00 1010 1100 0100 ===0 1000 1000 0110 #### =100 1=01 11=1  43%  19.0 ( 980.0, 396.5)
10. Jonesy 1.0 64-bit           000= 00=0 100= 00=0 =11= =0=1 0==0 1==0 =011 #### 1=0= =111  43%  19.0 ( 980.0, 387.0)
11. RomiChess P3n 64-bit        =0=0 1000 0=00 ===1 1000 =11= 00=0 0110 0=10 0=1= #### 0010  36%  16.0 ( 992.0, 358.0)
12. Ares GB 64-bit              =00= 01== 0000 ==10 =00= 100= =100 0000 00=0 =000 1101 ####  30%  13.0 (1004.0, 292.5)

Games

2 Comments

MadChess 3.0 Beta Build 039 (Bitboards)

  By

For the last month or so, in the evenings and on the weekends, I’ve been writing a new version of MadChess. For this 3.0 version, I’m writing code using bitboards instead of the mailbox board representation I used in MadChess 1.x and 2.x. I considered using C++ and even went as far as purchasing Bjarne Stroustrup’s The C++ Programming Language book and reading the first four chapters. But in the end I decided to stick with C#, the programming language with which I’m most familiar, for a few reasons.

  • Microsoft has been adding high-performance features to C# in recent editions, such as ref locals and ref returns.
  • Microsoft has embraced the open source movement with its .NET Core development platform.
  • C# is fast enough.

Perhaps I’ll consider using C++ for version 4 of MadChess.

OK, back to version 3: At program startup, I pre-calculate moves for sliding pieces using magic hashing. I found paulwal222’s answer to the Sliding Move Generation Using Magic Bitboard topic on Stack Overflow a very clear explanation of the technique. See my code below.

I’ve reached the first important milestone: legal move generation. I’m happy with the performance of my C# bitboard code. On my PC, MadChess 3.0 Beta generates legal moves at a rate of 41 million per second from the starting position (4.7x faster than MadChess 2.2). This includes generating pseudo-legal moves with the minimal requirements of From Square, To Square, and Pawn Promotion Piece, plus other metadata that eventually will be used by the search function; finding pinned pieces; and testing move legality (does move expose own king to check) for pinned pieces.

// Move bits
// Higher priority moves have higher ulong value.
// 6 6 6 6 5 5 5 5 5 5 5 5 5 5 4 4 4 4 4 4 4 4 4 4 3 3 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0
// 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0
// B|CapV |CapA |Promo |Kil|History |C|K|E|D|P|Q|From |To
// B = Best Move
// CapV = Capture Victim
// CapA = Capture Attacker (inverted)
// Promo = Promoted Piece
// Kil = Killer Move
// C = Castling
// K = King Move
// E = En Passant Capture
// D = Double Pawn Move
// P = Pawn Move
// Q = Quiet (not capture, castling, or pawn promotion)
// From = From (needs one extra bit for illegal square)
// To = To (needs one extra bit for illegal square)
view raw Move.cs hosted with ❤ by GitHub

I’ve successfully passed my suite of test positions– the same positions I used to verify correct legal move generation in MadChess 1.x and 2.x. MadChess 3.0 Beta completes the test suite 4.2x faster than MadChess 2.2.

PS C:\Users\Erik\Documents\Visual Studio 2019\Projects\MadChess\Engine\bin\Publish> .\MadChess.Engine.exe
testpositions "C:\Users\Erik\Documents\Chess\Tests\TestPositions.txt"
Number                                                                     Position  Depth     Expected        Moves  Correct    Pct
======  ===========================================================================  =====  ===========  ===========  =======  =====
     1                     rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1      1           20           20     True  100.0
     2                     rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1      2          400          400     True  100.0
     3                     rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1      3        8,902        8,902     True  100.0
     4                     rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1      4      197,281      197,281     True  100.0
     5                     rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1      5    4,865,609    4,865,609     True  100.0
     6                     rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1      6  119,060,324  119,060,324     True  100.0
     7                                           8/8/1k6/8/2pP4/8/5BK1/8 b - d3 0 1      6      824,064      824,064     True  100.0
     8                                          8/8/1k6/2b5/2pP4/8/5K2/8 b - d3 0 1      6    1,440,467    1,440,467     True  100.0
     9                                          8/5k2/8/2Pp4/2B5/1K6/8/8 w - d6 0 1      6    1,440,467    1,440,467     True  100.0
    10                                               5k2/8/8/8/8/8/8/4K2R w K - 0 1      6      661,072      661,072     True  100.0
    11                                               4k2r/8/8/8/8/8/8/5K2 b k - 0 1      6      661,072      661,072     True  100.0
    12                                               3k4/8/8/8/8/8/8/R3K3 w Q - 0 1      6      803,711      803,711     True  100.0
    13                                               r3k3/8/8/8/8/8/8/3K4 b q - 0 1      6      803,711      803,711     True  100.0
    14                                    r3k2r/1b4bq/8/8/8/8/7B/R3K2R w KQkq - 0 1      4    1,274,206    1,274,206     True  100.0
    15                                    r3k2r/7b/8/8/8/8/1B4BQ/R3K2R b KQkq - 0 1      4    1,274,206    1,274,206     True  100.0
    16                                     r3k2r/8/3Q4/8/8/5q2/8/R3K2R b KQkq - 0 1      4    1,720,476    1,720,476     True  100.0
    17                                     r3k2r/8/5Q2/8/8/3q4/8/R3K2R w KQkq - 0 1      4    1,720,476    1,720,476     True  100.0
    18                                            2K2r2/4P3/8/8/8/8/8/3k4 w - - 0 1      6    3,821,001    3,821,001     True  100.0
    19                                            3K4/8/8/8/8/8/4p3/2k2R2 b - - 0 1      6    3,821,001    3,821,001     True  100.0
    20                                          8/8/1P2K3/8/2n5/1q6/8/5k2 b - - 0 1      5    1,004,658    1,004,658     True  100.0
    21                                          5K2/8/1Q6/2N5/8/1p2k3/8/8 w - - 0 1      5    1,004,658    1,004,658     True  100.0
    22                                               4k3/1P6/8/8/8/8/K7/8 w - - 0 1      6      217,342      217,342     True  100.0
    23                                               8/k7/8/8/8/8/1p6/4K3 b - - 0 1      6      217,342      217,342     True  100.0
    24                                                8/P1k5/K7/8/8/8/8/8 w - - 0 1      6       92,683       92,683     True  100.0
    25                                                8/8/8/8/8/k7/p1K5/8 b - - 0 1      6       92,683       92,683     True  100.0
    26                                                K1k5/8/P7/8/8/8/8/8 w - - 0 1      6        2,217        2,217     True  100.0
    27                                                8/8/8/8/8/p7/8/k1K5 b - - 0 1      6        2,217        2,217     True  100.0
    28                                               8/k1P5/8/1K6/8/8/8/8 w - - 0 1      7      567,584      567,584     True  100.0
    29                                               8/8/8/8/1k6/8/K1p5/8 b - - 0 1      7      567,584      567,584     True  100.0
    30                                            8/8/2k5/5q2/5n2/8/5K2/8 b - - 0 1      4       23,527       23,527     True  100.0
    31                                            8/5k2/8/5N2/5Q2/2K5/8/8 w - - 0 1      4       23,527       23,527     True  100.0
    32         r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1      5  193,690,690  193,690,690     True  100.0
    33                                    8/2p5/3p4/KP5r/1R3p1k/8/4P1P1/8 w - - 0 1      6   11,030,083   11,030,083     True  100.0
    34             r3k2r/Pppp1ppp/1b3nbN/nP6/BBP1P3/q4N2/Pp1P2PP/R2Q1RK1 w kq - 0 1      5   15,833,292   15,833,292     True  100.0
    35                rnbqkb1r/pp1p1ppp/2p5/4P3/2B5/8/PPP1NnPP/RNBQK2R w KQkq - 0 1      3       53,392       53,392     True  100.0
    36      r4rk1/1pp1qppp/p1np1n2/2b1p1B1/2B1P1b1/P1NP1N2/1PP1QPPP/R4RK1 w - - 0 1      5  164,075,551  164,075,551     True  100.0
    37                                    8/2p5/3p4/KP5r/1R3p1k/8/4P1P1/8 w - - 0 1      7  178,633,661  178,633,661     True  100.0
    38             r3k2r/Pppp1ppp/1b3nbN/nP6/BBP1P3/q4N2/Pp1P2PP/R2Q1RK1 w kq - 0 1      6  706,045,033  706,045,033     True  100.0
    39                    rnbq1k1r/pp1Pbppp/2p5/8/2B5/8/PPP1NnPP/RNBQK2R w KQ - 1 8      5   89,941,194   89,941,194     True  100.0
    40                                            1k6/1b6/8/8/7R/8/8/4K2R b K - 0 1      5    1,063,513    1,063,513     True  100.0
    41                                            3k4/3p4/8/K1P4r/8/8/8/8 b - - 0 1      6    1,134,888    1,134,888     True  100.0
    42                                           8/8/4k3/8/2p5/8/B2P2K1/8 w - - 0 1      6    1,015,133    1,015,133     True  100.0

Counted 1,846,360,249 nodes (31,154,555 nodes per second).

PrecalculatedMoves.cs:

[MethodImpl(MethodImplOptions.AggressiveInlining)]
public ulong GetBishopMovesMask(int Square, ulong Occupancy)
{
ulong occupancy = Occupancy & _bishopRelevantOccupancyMasks[Square];
int index = GetIndex(occupancy, _bishopMagicMultipliers[Square], _bishopShifts[Square]);
return _bishopMoveMasks[Square][index];
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public ulong GetRookMovesMask(int Square, ulong Occupancy)
{
ulong occupancy = Occupancy & _rookRelevantOccupancyMasks[Square];
int index = GetIndex(occupancy, _rookMagicMultipliers[Square], _rookShifts[Square]);
return _rookMoveMasks[Square][index];
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private static int GetIndex(ulong Occupancy, ulong MagicMultiplier, int Shift)
{
return (int) ((Occupancy * MagicMultiplier) >> Shift);
}
public void FindMagicMultipliers(int Piece, bool DisplayStatus)
{
Direction[] directions;
ulong[] unoccupiedMoveMasks;
ulong[] relevantOccupancyMasks;
ulong[] magicMultipliers;
int[] shifts;
ulong[][] moveMasks;
switch (Piece)
{
case Engine.Piece.WhiteBishop:
case Engine.Piece.BlackBishop:
directions = new[] {Direction.NorthEast, Direction.SouthEast, Direction.SouthWest, Direction.NorthWest};
unoccupiedMoveMasks = _unoccupiedBishopMoveMasks;
relevantOccupancyMasks = _bishopRelevantOccupancyMasks;
magicMultipliers = _bishopMagicMultipliers;
shifts = _bishopShifts;
moveMasks = _bishopMoveMasks;
break;
case Engine.Piece.WhiteRook:
case Engine.Piece.BlackRook:
directions = new[] {Direction.North, Direction.East, Direction.South, Direction.West};
unoccupiedMoveMasks = _unoccupiedRookMoveMasks;
relevantOccupancyMasks = _rookRelevantOccupancyMasks;
magicMultipliers = _rookMagicMultipliers;
shifts = _rookShifts;
moveMasks = _rookMoveMasks;
break;
default:
throw new ArgumentException($"Piece {Piece} not supported.");
}
// Generate moves mask on each square.
Dictionary<ulong, ulong> occupancyToMovesMask = new Dictionary<ulong, ulong>();
HashSet<ulong> uniqueMovesMasks = new HashSet<ulong>();
for (int square = 0; square < 64; square++)
{
occupancyToMovesMask.Clear();
uniqueMovesMasks.Clear();
ulong moveDestinations = unoccupiedMoveMasks[square];
ulong relevantMoveDestinations = moveDestinations & relevantOccupancyMasks[square];
int uniqueOccupancies = (int) Math.Pow(2, Bitwise.CountSetBits(relevantMoveDestinations));
occupancyToMovesMask.EnsureCapacity(uniqueOccupancies);
// Generate moves mask for every permutation of relevant occupancy bits.
using (IEnumerator<ulong> occupancyPermutations = Bitwise.GetAllPermutations(relevantMoveDestinations).GetEnumerator())
{
while (occupancyPermutations.MoveNext())
{
ulong occupancy = occupancyPermutations.Current;
if (!occupancyToMovesMask.ContainsKey(occupancy))
{
// Have not yet generated moves for this occupancy mask.
ulong movesMask = _createMoveDestinationsMask(square, occupancy, directions);
occupancyToMovesMask.Add(occupancy, movesMask);
if (!uniqueMovesMasks.Contains(movesMask)) uniqueMovesMasks.Add(movesMask);
}
}
}
// Validate enumerator found all permutations of relevant occupancy bits.
Debug.Assert(occupancyToMovesMask.Count == uniqueOccupancies);
// Determine bit shift that produces number >= unique occupancies.
// A stricter condition is number >= unique moves but this requires more computing time to find magic multipliers.
int shift = 64 - (int) Math.Ceiling(Math.Log(uniqueOccupancies, 2d));
shifts[square] = shift;
ulong magicMultiplier = magicMultipliers[square];
if (magicMultiplier == 0) (magicMultipliers[square], moveMasks[square]) = FindMagicMultiplier(occupancyToMovesMask, shift, null);
else
(magicMultipliers[square], moveMasks[square]) = FindMagicMultiplier(occupancyToMovesMask, shift, magicMultiplier);
if (DisplayStatus)
_writeMessageLine($"{Board.SquareLocations[square].PadLeft(6)} {Engine.Piece.GetName(Piece).PadLeft(6)} {shift.ToString().PadLeft(5)} " +
$"{occupancyToMovesMask.Count.ToString().PadLeft(18)} {uniqueMovesMasks.Count.ToString().PadLeft(12)} {magicMultipliers[square].ToString("X16").PadLeft(16)}");
}
}
private (ulong MagicMultiplier, ulong[] MovesMasks) FindMagicMultiplier(Dictionary<ulong, ulong> OccupancyToMovesMask, int Shift, ulong? KnownMagicMultiplier)
{
int indexBits = 64 - Shift;
int indexLength = (int) Math.Pow(2d, indexBits);
ulong[] movesMasks = new ulong[indexLength];
List<ulong> occupancies = new List<ulong>(OccupancyToMovesMask.Keys);
NextMagicMultiplier:
ulong magicMultiplier = KnownMagicMultiplier ?? ULongRandom.Next();
// Clear moves masks.
for (int maskIndex = 0; maskIndex < movesMasks.Length; maskIndex++) movesMasks[maskIndex] = 0;
for (int occupancyIndex = 0; occupancyIndex < occupancies.Count; occupancyIndex++)
{
ulong occupancy = occupancies[occupancyIndex];
int index = GetIndex(occupancy, magicMultiplier, Shift);
ulong movesMask = movesMasks[index];
if (movesMask == 0)
{
// Moves mask not yet added to unique moves array.
movesMasks[index] = OccupancyToMovesMask[occupancy];
}
else
{
// Moves mask already added to unique moves array.
// Confirm moves mask is correct.
if (movesMask != OccupancyToMovesMask[occupancy]) goto NextMagicMultiplier;
}
}
// Found magic multiplier that maps to correct moves index for all occupancies.
return (magicMultiplier, movesMasks);
}
public static ulong GetRelevantOccupancy(int Square, bool FileRankSlidingPiece)
{
if ((Board.SquareMasks[Square] & Board.EdgeSquareMask) == 0) return ~Board.EdgeSquareMask;
// Square is on edge of board.
if (!FileRankSlidingPiece) return ~Board.EdgeSquareMask;
// Piece can slide along file or rank.
ulong occupancy;
int file = Board.Files[Square];
int rank = Board.WhiteRanks[Square];
switch (file)
{
case 0:
// Piece is on Westernmost edge file.
switch (rank)
{
case 0:
// Piece is on A1 square.
// Occupancy of most distant squares does not affect pseudo-legal moves.
return ~Board.SquareMasks[Engine.Square.a8] & ~Board.SquareMasks[Engine.Square.h1];
case 7:
// Piece is on A8 square.
// Occupancy of most distant squares does not affect pseudo-legal moves.
return ~Board.SquareMasks[Engine.Square.a1] & ~Board.SquareMasks[Engine.Square.h8];
default:
// Piece is not on edge rank.
// Occupancy of edge ranks and opposite edge file does not affect pseudo-legal moves.
return ~Board.RankMasks[0] & ~Board.RankMasks[7] & ~Board.FileMasks[7];
}
case 7:
// Piece is on Easternmost edge file.
switch (rank)
{
case 0:
// Piece is on H1 square.
// Occupancy of most distant squares does not affect pseudo-legal moves.
return ~Board.SquareMasks[Engine.Square.a1] & ~Board.SquareMasks[Engine.Square.h8];
case 7:
// Piece is on H8 square.
// Occupancy of most distant squares does not affect pseudo-legal moves.
return ~Board.SquareMasks[Engine.Square.a8] & ~Board.SquareMasks[Engine.Square.h1];
default:
// Piece is not on edge rank.
// Occupancy of edge ranks and opposite edge file does not affect pseudo-legal moves.
return ~Board.RankMasks[0] & ~Board.RankMasks[7] & ~Board.FileMasks[0];
}
default:
// Piece is not on edge file.
// Occupancy of edge files does not affect pseudo-legal moves.
occupancy = ~Board.FileMasks[0] & ~Board.FileMasks[7];
break;
}
// Piece is not on a corner square (handled in code above).
switch (rank)
{
case 0:
// Piece is on Southernmost edge rank.
// Occupancy of opposite rank does not affect pseudo-legal moves.
return occupancy & ~Board.RankMasks[7];
case 7:
// Piece is on Northernmost edge rank.
// Occupancy of opposite rank does not affect pseudo-legal moves.
return occupancy & ~Board.RankMasks[0];
default:
// Piece is not on edge rank.
// Occupancy of edge ranks does not affect pseudo-legal moves.
return occupancy & ~Board.RankMasks[0] & ~Board.RankMasks[7];
}
}
view raw PrecalculatedMoves.cs hosted with ❤ by GitHub

Bitwise.cs:

public static IEnumerable<ulong> GetAllPermutations(ulong Mask)
{
List<int> setBits = new List<int>();
for (int index = 0; index < 64; index++) if (IsBitSet(Mask, index)) setBits.Add(index);
return GetAllPermutations(setBits, 0, 0);
}
private static IEnumerable<ulong> GetAllPermutations(List<int> SetBits, int Index, ulong Value)
{
SetBit(ref Value, SetBits[Index]);
yield return Value;
int index = Index + 1;
if (index < SetBits.Count)
{
using (IEnumerator<ulong> occupancyPermutations =
GetAllPermutations(SetBits, index, Value).GetEnumerator())
{
while (occupancyPermutations.MoveNext()) yield return occupancyPermutations.Current;
}
}
ClearBit(ref Value, SetBits[Index]);
yield return Value;
if (index < SetBits.Count)
{
using (IEnumerator<ulong> occupancyPermutations =
GetAllPermutations(SetBits, index, Value).GetEnumerator())
{
while (occupancyPermutations.MoveNext()) yield return occupancyPermutations.Current;
}
}
}
public static bool IsBitSet(ulong Value, int Index)
{
Debug.Assert((Index >= 0) && (Index < _longBits));
return (Value & (1ul << Index)) > 0;
}
public static void SetBit(ref ulong Value, int Index)
{
Debug.Assert((Index >= 0) && (Index < _longBits));
Value |= 1ul << Index;
}
public static void ClearBit(ref ulong Value, int Index)
{
Debug.Assert((Index >= 0) && (Index < _longBits));
Value &= ~(1ul << Index);
}
view raw Bitwise.cs hosted with ❤ by GitHub

No comments

Banks 70th Amateur Series Division 7

  By

MadChess 2.2 participated in Graham Banks’ 70th amateur tournament in division 7.

                                 1    2    3    4    5    6    7    8    9    0    1    2    
1   Bagatur 1.5e 64-bit          **** 11½½ 0½½½ ½½11 0½½1 1011 ½1½½ 01½½ ½001 01½1 ½110 1½1½  26.5/44  574.00
2   MadChess 2.2 64-bit          00½½ **** ½½00 1½1½ ½0½1 1011 1½0½ 1½½1 111½ 1½1½ ½½½1 110½  26.5/44  554.25
3   Drosophila 1.5.1 64-bit      1½½½ ½½11 **** 1000 ½100 ½½0½ ½½10 01½½ 111½ 0½11 ½110 ½½11  25.0/44
4   Lozza 1.18 64-bit            ½½00 0½0½ 0111 **** 1011 101½ 10½½ ½0½1 1½½1 00½1 11½½ ½0½1  24.0/44  515.75
5   Shallow r694 64-bit          1½½0 ½1½0 ½011 0100 **** ½½1½ 100½ 01½1 0101 ½½11 11½½ 0011  24.0/44  514.25
6   Jumbo 0.6.45 64-bit          0100 0100 ½½1½ 010½ ½½0½ **** ½100 ½101 1½1½ 11½1 11½½ 101½  23.5/44
7   RomiChess P3n 64-bit         ½0½½ 0½1½ ½½01 01½½ 011½ ½011 **** ½½½1 0½1½ 1010 010½ ½101  23.0/44
8   RookieMonster 1.5.13 64-bit  10½½ 0½½0 10½½ ½1½0 10½0 ½010 ½½½0 **** 1000 1000 1½1½ ½101  19.0/44  418.00
9   Waxman 2017                  ½110 000½ 000½ 0½½0 1010 0½0½ 1½0½ 0111 **** ½100 01½1 1½01  19.0/44  406.25
10  Topple 0.2.1 64-bit          10½0 0½0½ 1½00 11½0 ½½00 00½0 0101 0111 ½011 **** ½1½0 ½000  18.0/44  394.75
11  Nemeton 1.7                  ½001 ½½½0 ½001 00½½ 00½½ 00½½ 101½ 0½0½ 10½0 ½0½1 **** 11½1  18.0/44  390.75
12  Galjoen 0.39.2 64-bit        0½0½ 001½ ½½00 ½1½0 1100 010½ ½010 ½010 0½10 ½111 00½0 ****  17.5/44

Games