MadChess 3.1 Beta 533e382 (Move Legality Performance Improvement)

I improved the performance of code that determines the legality of pseudo-legal moves. Previously, move legality was tested prior to playing a move. This consisted of playing a move (to test whether it exposed its own king to check and whether it delivered check on the enemy king), undoing the move, updating the “check” move property, then re-playing the move. Now a move is played, move legality and check is tested, and the Board.PlayMove method returns a (bool isLegal, bool deliversCheck) tuple.

The calling method (such as Search.GetDynamicScore or Search.GetQuietScore) then either 1) undoes the move (if illegal or futile) and continues to the next pseudo-legal move or 2) searches the resulting position.

In addition to move legality, I experimented with other performance improvements. None of these experiments succeeded except PR 33: Trust Move Capture Victim, which eliminated redundant calls to Position.GetPiece(Square square) in move generation and when playing moves.

Eliminating redundant double-playing of a move (to test move legality) during search increased the search speed of MadChess 3.1 Beta and produced a 36 Elo gain in playing strength.

 

Feature Category Date Commit1 WAC2 Elo Rating3 Improvement
Move Legality
Performance Improvement
Search 2022 Mar 18 533e382 289 2687 +36
Pawn Structure Evaluation 2022 Jan 11 d691b32 288 2651 +15
Threats Evaluation 2021 Oct 24 26e5323 289 2636 +7
Color-Agnostic Code Evaluation 2021 Sep 13 2b475bc 286 2629 +12
Singular Move Search 2021 Jun 14 0c601ea 290 2617 +13
Endgame Eval Scaling Evaluation 2021 Apr 08 4d22dec 286 2604 +12
Bishop Pair Evaluation 2021 Mar 14 2960ec9 285 2592 +22
Position Cache Optimization Search 2021 Feb 23 42d7702 286 2570 +8
Move Generation Optimization Search 2021 Feb 17 22002dc 287 2562 +12
PVS and Null Move Search 2021 Feb 09 f231dac 285 2550 +20
Remove Aspiration Windows Search 2020 Dec 20 4b7963b 290 2530 +9
Time Management Search 2020 Dec 19 d143bb5 286 2521 +8
Crash Bug Search 2020 Aug 29 2d855ec 288 2513 +0
King Safety Evaluation 2020 Aug 16 6794c89 288 2513 +63
Eval Param Tuning Evaluation 2020 Jul 23 bef88d5 283 2450 +30
Late Move Pruning Search 2020 Feb 08 6f3d17a 288 2420 +29
Piece Mobility Evaluation 2020 Feb 01 5c5d4fc 282 2391 +62
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. GitHub commit (hash) or Subversion source code revision (integer)
  2. Win At Chess position test, 3 seconds per position
  3. Bullet chess, 2 min / game + 1 sec / move

MadChess 3.1 Beta d691b32 (Pawn Structure)

I added evaluation of two pawn structure features to MadChess 3.1 Beta.

  • Isolated Pawns
  • Doubled Pawns

In addition to pawn structure evaluation, I made other code quality improvements in a series of Pull Requests.

Evaluating pawn structure increased the playing strength of MadChess 3.1 Beta by 15 Elo.

 

Feature Category Date Commit1 WAC2 Elo Rating3 Improvement
Pawn Structure Evaluation 2022 Jan 11 d691b32 288 2651 +15
Threats Evaluation 2021 Oct 24 26e5323 289 2636 +7
Color-Agnostic Code Evaluation 2021 Sep 13 2b475bc 286 2629 +12
Singular Move Search 2021 Jun 14 0c601ea 290 2617 +13
Endgame Eval Scaling Evaluation 2021 Apr 08 4d22dec 286 2604 +12
Bishop Pair Evaluation 2021 Mar 14 2960ec9 285 2592 +22
Position Cache Optimization Search 2021 Feb 23 42d7702 286 2570 +8
Move Generation Optimization Search 2021 Feb 17 22002dc 287 2562 +12
PVS and Null Move Search 2021 Feb 09 f231dac 285 2550 +20
Remove Aspiration Windows Search 2020 Dec 20 4b7963b 290 2530 +9
Time Management Search 2020 Dec 19 d143bb5 286 2521 +8
Crash Bug Search 2020 Aug 29 2d855ec 288 2513 +0
King Safety Evaluation 2020 Aug 16 6794c89 288 2513 +63
Eval Param Tuning Evaluation 2020 Jul 23 bef88d5 283 2450 +30
Late Move Pruning Search 2020 Feb 08 6f3d17a 288 2420 +29
Piece Mobility Evaluation 2020 Feb 01 5c5d4fc 282 2391 +62
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. GitHub commit (hash) or Subversion source code revision (integer)
  2. Win At Chess position test, 3 seconds per position
  3. Bullet chess, 2 min / game + 1 sec / move

MadChess 3.1 Beta 26e5323 (Threats)

I added evaluation of threats in the middlegame to MadChess 3.1 Beta. A bonus is given if a pawn or minor piece threatens to capture a more valuable piece on its next move.

The evaluation code does not determine if the threatening piece is defended. That is left to the Search.GetQuietScore method to resolve. In other words, Search.GetQuietScore may determine the opponent can capture the threatening piece, eliminating the threat and rendering the evaluation bonus moot (because loss of a piece greatly outweighs the threat bonus).

Evaluating threats increased the playing strength of MadChess 3.1 Beta by 7 Elo.

 

Feature Category Date Commit1 WAC2 Elo Rating3 Improvement
Threats Evaluation 2021 Oct 24 26e5323 289 2636 +7
Color-Agnostic Code Evaluation 2021 Sep 13 2b475bc 286 2629 +12
Singular Move Search 2021 Jun 14 0c601ea 290 2617 +13
Endgame Eval Scaling Evaluation 2021 Apr 08 4d22dec 286 2604 +12
Bishop Pair Evaluation 2021 Mar 14 2960ec9 285 2592 +22
Position Cache Optimization Search 2021 Feb 23 42d7702 286 2570 +8
Move Generation Optimization Search 2021 Feb 17 22002dc 287 2562 +12
PVS and Null Move Search 2021 Feb 09 f231dac 285 2550 +20
Remove Aspiration Windows Search 2020 Dec 20 4b7963b 290 2530 +9
Time Management Search 2020 Dec 19 d143bb5 286 2521 +8
Crash Bug Search 2020 Aug 29 2d855ec 288 2513 +0
King Safety Evaluation 2020 Aug 16 6794c89 288 2513 +63
Eval Param Tuning Evaluation 2020 Jul 23 bef88d5 283 2450 +30
Late Move Pruning Search 2020 Feb 08 6f3d17a 288 2420 +29
Piece Mobility Evaluation 2020 Feb 01 5c5d4fc 282 2391 +62
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. GitHub commit (hash) or Subversion source code revision (integer)
  2. Win At Chess position test, 3 seconds per position
  3. Bullet chess, 2 min / game + 1 sec / move

Missed Clever Tactical Shot

Recently I reviewed some blitz games I’ve played on Chess.com over the past few months. I found an enjoyable game where I played very well but missed a clever tactical shot near the end of the game.

When reviewing the game, I recognized this position. I remember wishing, during the game, that I had more time on my clock to think and work out the tactics. On second observation, I found the killer move. MadChess, along with world-class chess engines Stockfish and Komodo Dragon, confirmed it’s the best move. Can you find it?

Very nice! Here’s the full game, with improvements suggested by MadChess.

MadChess 3.1 Beta 2b475bc (Color-Agnostic Code)

I removed 350 lines of code from MadChess and increased its playing strength by 12 Elo. I’m happy with the ratio.

The bulk of changes since my last blog post involve replacing redundant, color-specific code with color-agnostic code, mostly in the Eval class. I replaced code such as this…

… with code that’s generalized for multiple pieces and colors.

The above is just one example of refactored code. There are many others in PR 22 that adds 2,641 lines of code and removes 3,336 lines of code (net -695 lines of code). This refactoring took a lot of time. I was careful to test often to ensure my (partial) changes did not weaken the engine due a mistake when translating color-specific code to color-agnostic code via array lookups indexed by colorless piece.

The Board.GetSquareFromWhitePerspective method violates the spirit of my refactoring. However, an exception is warranted because I don’t bother storing white and black piece location values in separate tables. For black, I simply lookup the corresponding square from white’s side of the board.

In addition to color-agnostic refactoring, I made other code quality improvements in a series of Pull Requests.

Combined, the five PRs removed 350 lines of code. This increased the playing strength of MadChess 3.1 Beta by 12 Elo.

 

Feature Category Date Commit1 WAC2 Elo Rating3 Improvement
Color-Agnostic Code Evaluation 2021 Sep 13 2b475bc 286 2629 +12
Singular Move Search 2021 Jun 14 0c601ea 290 2617 +13
Endgame Eval Scaling Evaluation 2021 Apr 08 4d22dec 286 2604 +12
Bishop Pair Evaluation 2021 Mar 14 2960ec9 285 2592 +22
Position Cache Optimization Search 2021 Feb 23 42d7702 286 2570 +8
Move Generation Optimization Search 2021 Feb 17 22002dc 287 2562 +12
PVS and Null Move Search 2021 Feb 09 f231dac 285 2550 +20
Remove Aspiration Windows Search 2020 Dec 20 4b7963b 290 2530 +9
Time Management Search 2020 Dec 19 d143bb5 286 2521 +8
Crash Bug Search 2020 Aug 29 2d855ec 288 2513 +0
King Safety Evaluation 2020 Aug 16 6794c89 288 2513 +63
Eval Param Tuning Evaluation 2020 Jul 23 bef88d5 283 2450 +30
Late Move Pruning Search 2020 Feb 08 6f3d17a 288 2420 +29
Piece Mobility Evaluation 2020 Feb 01 5c5d4fc 282 2391 +62
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. GitHub commit (hash) or Subversion source code revision (integer)
  2. Win At Chess position test, 3 seconds per position
  3. Bullet chess, 2 min / game + 1 sec / move