No comments

MadChess 3.0 Beta Build 103 (Passed Pawns)

  By

I added passed pawn evaluation to MadChess 3.0 Beta. The passed pawn evaluation code scores the following features:

  • Passed Pawns
  • Free Passed Pawns (no pieces blocking promotion path)
  • King Escorted Passed Pawns
  • Unstoppable Passed Pawns (Rule of the Square)

Middlegame Passed Pawns:            000  000  003  008  015  024  034  000
Endgame Passed Pawns:               000  004  018  042  075  118  170  000
Endgame Free Passed Pawns:          000  008  034  077  138  216  311  000
Endgame King Escorted Passed Pawn:  11
Unstoppable Passed Pawn:            775

 

This code improved the engine’s understanding of threats created by pushing passed pawns. It increased the playing strength of MadChess 3.0 Beta by 119 Elo.

 

Feature Category Date Rev1 WAC2 Elo Rating3 Improvement
Passed Pawns Evaluation 2018 Dec 27 103 279 2329 +119
Staged Move Generation Search 2018 Dec 15 93 275 2210 +39
History Heuristics Search 2018 Dec 03 84 275 2171 +28
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 093 (Staged Move Generation)

  By

I increased the speed at which MadChess 3.0 Beta examines nodes by implementing staged move generation. Previously, in the main search, the chess engine would generate all pseudo-legal moves, sort them by move priority, then iterate through them: testing move legality (does move expose own king to check) and playing the legal moves. This is wasteful if a beta cutoff occurs early in the move list. Usually a capture is responsible for a beta cutoff, so time is wasted generating non-captures. Now the chess engine generates moves in stages.

I could have implemented more stages (QueenCaptures, RookCaptures, BishopKnightCaptures, etc) but I wanted to keep the code simple. Implementing a stage for captures of each piece type involves calculating all attacks to a square, not from a square as the engine already does. To test move legality I have already implemented an IsSquareAttacked(int Square) method that returns a boolean value. This does not generate moves though. If I were to implement a GetAttackingMoves(int Square) method I’d need to write debug code that validates the captures generated by calling GetAttackingMoves for all enemy pieces matches the captures generated by calling GenerateMoves(MoveGeneration.OnlyCaptures). Perhaps I’ll investigate this more fine-grained staged move generation later. For now, the code remains simple.

Search.cs

Search.cs GetDynamicScore

Search.cs GetQuietScore

This improved MadChess 3.0 Beta’s move generation speed (Nodes Per Second) while searching and gained 39 Elo points. MadChess 3.0 Beta searches typical middlegame positions at > 5 million NPS. The evaluation function still is limited to material, piece location, draw detection, and checkmate.

 

Feature Category Date Rev1 WAC2 Elo Rating3 Improvement
Staged Move Generation Search 2018 Dec 15 93 275 2210 +39
History Heuristics Search 2018 Dec 03 84 275 2171 +28
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 084 (History Heuristics)

  By

I increased the playing strength of MadChess 3.0 by improving the history heuristics used by Late Move Reductions (LMR).

First, I added a flag that indicates if a move was played during search (indicated below with “!”). This implies the move is legal (doesn’t expose own king to check) and search examined it (as opposed to moves appearing in the move list after a move that causes a beta cutoff). Moves are encoded as ulong primitives like so:

Next, I altered the search function to flag played moves.

Then I modified the search function so it not only increments move history for quiet moves that cause a beta cutoff, but also decrements move history for quiet moves that failed to cause a beta cutoff. The decrement is applied only if a later quiet move actually caused a beta cutoff.

Finally, I modified the Move class to allow negative history values (though stored internally as a positive value to avoid complications with twos complement bit notation used by the .NET Core runtime to represent negative integers).

The listmoves command demonstrates the search function will assign negative history values.

listmoves
Rank   Move  Best  Cap Victim  Cap Attacker  Promo  Killer  History              Priority
====  =====  ====  ==========  ============  =====  ======  =======  ====================
  01   d7d4  True       Queen         Queen              0       -1  12141986070363407779
  02   f6d5                                              2     2857    433752951094266523
  03   h7h5                                              1      -56    433189988923033503
  04   f8e7                                              0    15940    432627106061501068
  05   e8e7                                              0     7705    432627071521931788
  06   a8b8                                              0     2985    432627051724292097
  07   d7d6                                              0      794    432627042534573459
  08   c6c5                                              0       -1    432627039200168218
  09   d7d5                                              0       -6    432627039179130267
  10   a8a7                                              0       -8    432627039170740232
  11   f6g4                                              0       -9    432627039166548646
  12   f6g8                                              0      -10    432627039162354310
  13   f6e4                                              0      -11    432627039158160036
  14   f6h5                                              0      -13    432627039149771423
  15   f8d6                                              0      -13    432627039149769363
  16   d7e7                                              0      -20    432627039120409996
  17   d7c7                                              0      -20    432627039120409994
  18   d7b7                                              0      -21    432627039116215689
  19   f8c5                                              0      -24    432627039103632026
  20   c8b7                                              0      -24    432627039103631625
  21   d7a7                                              0      -34    432627039061689736
  22   d7d8                                              0      -34    432627039061689731
  23   g7g5                                              0      -41    432627039032526622
  24   e6e5                                              0      -44    432627039019813404
  25   g7g6                                              0      -53    432627038982063894
  26   b4b3                                              0      -56    432627038969483433
  27   a6a5                                              0      -56    432627038969481240
  28   h7h6                                              0      -56    432627038969481111
  29   h8g8                                              0      -56    432627038969414534

29 legal moves

This improved MadChess 3.0 Beta’s tactical awareness and gained 28 Elo points. The evaluation function still is limited to material, piece location, draw detection, and checkmate.

I made two other changes that did not greatly affect the strength of MadChess 3.0 Beta. I added detection of drawish pawnless endgames. This may have contributed 5 of the 28 Elo, but I don’t really know because the error margins for 4,000 games are +/- 20 Elo. If a drawish endgame is encountered, MadChess 3.0 Beta assigns a zero score but allows the search to continue (as opposed to dead drawn endgames such as Kk, KBk, or KNk; threefold repetition; 50 moves without a capture or pawn move; or insufficient material to checkmate, where the search is terminated).

  • KQkq
  • KQkrr
  • KRRkrr
  • KRBkrb
  • KRBkrn
  • KRNkrn
  • KRBkr
  • KRNkr
  • KRBNkr
  • KRkr
  • KRkb
  • KRkn
  • KNNkb
  • KNNkn
  • KNNk

Also, I changed the Board.IsMoveLegal function so it plays a null move when determining if a move checks the enemy king. Previously, Board.IsMoveLegal had determined check without actually playing a null move. This caused a subtle bug, though. As a consequence of this change, move legality checking searches an additional node, so the engine reports increased search speed in Nodes Per Second (NPS). This of course is an artificial speed increase, but it does align MadChess 3.0 Beta’s node counting with MadChess 2.x’s. MadChess 3.0 Beta searches the WAC position test at 4.31 million NPS on my PC.

 

Feature Category Date Rev1 WAC2 Elo Rating3 Improvement
History Heuristics Search 2018 Dec 03 84 275 2171 +28
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
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

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

ParticleSwarms.cs

ParticleSwarm.cs

Particle.cs

Evaluation.cs

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.