Tactical Minefield in Won Game

I played an interesting blitz game a couple nights ago against MadChess 3.0 Beta. The engine is strong enough for me to release it. Before I do, I’m improving features not related to maximizing engine strength. In fact, quite the opposite: I’m working on UCI_LimitStrength and UCI_Elo options that reduce the engine’s playing strength. This enables us mere mortals to configure MadChess for a more enjoyable game- competitive but with winning chances gifted to us by an engine purposefully playing inaccuracies and blunders.

The game began as follows. Playing white, I develop my pieces. MadChess 3.0 Beta mindlessly pushes a few pawns forward before belatedly developing its pieces. MadChess and I play the opening and middlegame inaccurately- including a significant blunder on my 6th move. (See analysis at end of this blog post.)

1.e4 e5 2.Nf3 h5 3.Be2 f5 4.Nc3 b6 5.Nxe5 a6 6.Ng6 Rh7 7.Nxf8 Kxf8 8.exf5 c5 9.Bxh5 d6 10.Nd5 Rh8 11.Qf3 Qd7 12.Nxb6 Qe7+ 13.Kd1 Bb7 14.Qg4 Nh6 15.Qg6 Be4

rn3k1r/4q1p1/pN1p2Qn/2p2P1B/4b3/8/PPPP1PPP/R1BK3R w - - 7 16

Here the game quickly gets very tactical. Keep in mind I’m playing MadChess 3.0 Beta at reduced strength. I’ve capitalized on its weak moves and have obtained a winning position. That my position is winning is not in doubt: White has won a bishop for a knight, has the bishop pair, and is up four pawns. However, MadChess’ defense complicates my winning position. Despite its moves being suboptimal, MadChess increases the chance a patzer like me spoils the position.

The game continues 16.Re1 Ra7 17.f3 {Another big blunder by me.} Qd8 18.Rxe4 Rf7 19.d3 Re7 20.Bg5 Nc6 21.Kd2 Qe8

4qk1r/4r1p1/pNnp2Qn/2p2PBB/4R3/3P1P2/PPPK2PP/R7 w - - 5 22

Here I miss a mate in two. Can you spot it? It’s easy when given the hint. In the game, with the clock ticking, I thought, “I have a strong attack here. My queen is leading the attack. I don’t want to swap it off.” Instead I play Qxd6, pinning black’s rook on e7. If black takes my bishop on h5, I thought I’d follow by moving my queen to the back rank to check the black king and win black’s other rook. I overlooked black’s knight on c6 covers my queen’s two infiltration squares (b8 and d8). Damn.

The game continues 22.Qxd6 Qxh5 23.Bxe7+ Nxe7 24.Nd7+ Kg8 25.Rxe7 Qg5+ 26.Kc3 Nf7 27.Qb8+ Kh7 28.Qg3

7r/3NRnpk/p7/2p2Pq1/8/2KP1PQ1/PPP3PP/R7 b - - 6 28

Now I’m willing to trade queens. But black isn’t. MadChess takes my rook. I sensed (correctly) it didn’t matter because of the strength of my attack, but I fail to press my advantage maximally.

The game continues 28… Qxe7 29.Qg6+ Kg8

6kr/3Nqnp1/p5Q1/2p2P2/8/2KP1P2/PPP3PP/R7 w - - 2 30

Here, under time pressure, I overlook a crushing move. Afterwards, when reviewing the game I saw it immediately. Nonetheless, I went on to win without making any more significant mistakes:

30.Qe6 Qd8 31.Re1 Rh7 32.Qe8+ Qxe8 33.Rxe8#

A very enjoyable game! I had MadChess 3.0 Beta do post-game analysis. I set it to full strength and asked it to identify moves where I erred by a pawn or more. You may review MadChess’ suggested improvements in the variations it added to the game below.

MadChess 3.0 Beta 4d22dec (Endgame Eval Scaling)

I improved MadChess 3.0 Beta’s detection of drawn endgames. The IsPawnlessDraw method scores the following positions as drawn. Though it continues to search moves for a swindle (opponent mistake that makes a drawn game winnable).

  • 2N vrs <= 1 Minor
  • Q vrs 2B
  • Q vrs 2N
  • Q vrs Q
  • Q vrs R + Minor
  • R vrs R + <= 1 Minor
  • Q vrs 2R
  • 2R vrs R + Minor
  • 2R vrs 2R

Testing revealed considering R vrs <= 2 Minors a draw increased evaluation error and caused the engine to play weaker. I left that endgame in the IsPawnlessDraw function as commented out code (explaining the regression) to thwart any temptation to add it later.

In addition, I added a DetermineEndgameScale method that scales down the score of difficult to win endgames.

  • Winning side has no pawns and is up by a bishop or less.
    • Winning side has a rook or more.
    • Winning side has less than a rook.
  • Sides have opposite colored bishops and no other pieces.
  • All other endgames are scaled by winningPawnCount.

Also, I added a GetTotalScore method that scales down the score as games approach a draw by 50 moves (100 ply) without a capture or pawn move.

Finally The GetStaticScore method brings together the entire evaluation calculation. See the Evaluation.cs source code file for full details. Here’s the code in simplified form.

These code changes increased the playing strength of MadChess 3.0 Beta by 12 ELO. MadChess has crossed the 2600 ELO threshold, at least at bullet chess (2 min / game + 1 sec / move). To date, I have tested MadChess 3.0 Beta exclusively at bullet time control. I was curious how MadChess would perform given more time per game. Of course I’d give its opponents equal additional time. Wouldn’t this benefit both engines equally? Well, chess engines do not scale equally with time. Would MadChess 3.0 Beta or its opponents benefit more from the additional time? Or would it be a wash? That is, they’d scale equally and MadChess 3.0 Beta would achieve the same blitz rating as bullet rating?

MadChess has crossed the 2600 ELO threshold at bullet time control.

It turns out, similar to previous versions, MadChess scales better per time than its opponents. Its blitz chess rating is 2638 ELO. I have started a tournament with rapid time controls (14 min / game + 7 sec / move), however, I won’t know the results for a month or so. Unlike bullet and blitz, I do not have a database of chess engine games at rapid time control. Therefore I cannot run a gauntlet tournament pitting MadChess 3.0 Beta against ten other engines with established ratings. I must run an all-play-all round robin tournament of 48 engines, including MadChess 3.0 Beta, to establish ratings.

MadChess scales better per time than its opponents. Its blitz chess rating is 2638 ELO.

My priority now is to ensure MadChess 3.0 Beta has feature parity (UCI_LimitStrength, MultiPV, etc) with the last release of MadChess, 2.2. Once that’s complete, I’ll release MadChess 3.0.

 

Feature Category Date Commit1 WAC2 ELO Rating3 Improvement
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.0 Beta 2960ec9 (Bishop Pair)

I improved MadChess 3.0 Beta’s evaluation function by adding middlegame and endgame evaluation parameters for bishop pair.

Tuning code indicated the bishop pair parameters immediately reduced evaluation error when examining a database consisting of approximately 54,000 Grandmaster games (both players 2600 ELO or stronger). I ran the Particle Swarm Optimization tuner on all evaluation parameters and it further reduced evaluation error.

This improved evaluation function increased the playing strength of MadChess 3.0 Beta by 22 ELO.

 

Feature Category Date Commit1 WAC2 ELO Rating3 Improvement
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.0 Beta 42d7702 (Position Cache Optimization)

Quoting from my Pull Request #12:

Converted Cache class’ _positions field from a jagged array to a flat array. The flat array is more memory efficient than a jagged array. Jagged arrays have a .NET object header for each sub-array (for garbage collection tracking of reachable-from-root). This enables more positions to be stored per megabyte of memory. The code in this PR stores 65,536 positions per MB = 8,388,608 positions for a typically sized 128 MB cache.

Added stats to track cache hit %, best move found in cached position %, and count of invalid best moves. Stats are displayed when the debug on command is sent.

Experimented condensing CachedPosition struct from two ulongs to a single ulong. Only 15 bits were available for a partial key. Testing showed the partial key caused too many invalid best moves to be extracted from cached positions. Performed weaker than leaving CachedPosition as a struct with a full key.

Here’s my implementation of the Cache class.

Here’s my implementation of the associated CachedPosition struct and CachedPositionData static class.

This improved cache code increased the playing strength of MadChess 3.0 Beta by 8 ELO.

 

Feature Category Date Commit1 WAC2 ELO Rating3 Improvement
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.0 Beta 22002dc (Move Generation Optimization)

Rather than repeat myself, I’ll explain my recent code update by copying the text of my Pull Request #10 here:

Improved detection of pieces pinned to own king by sliding attackers. Previous implementation only found potentially pinned pieces (because the pieces were on the same file, rank, or diagonal as the sliding attacker). The new implementation finds all actually pinned pieces.

This speeds up resolution of pseudo-legal moves to legal moves by eliminating unnecessary calls to Board.IsSquareAttacked(kingSquare) in Board.IsMoveLegal method. Its benefit is limited though because many pseudo-legal moves never are examined for legality because a beta cutoff occurs before the move is searched.

Eliminated unnecessary call to Board.PlayNullMove and Board.UndoMove in Board.IsMoveLegal method. Instead of actually making a null move, the code flips side-to-move, sets a few other properties of the position, calls IsSquareAttacked(kingSquare), then restores original property values.

I experimented with eliminating the remaining call to Board.PlayMove and Board.UndoMove in Board.IsMoveLegal method to determine if this speeds up resolution of pseudo-legal moves to legal moves. I did this by intersecting pre-calculated moves from the destination (To) square to the opponent king. And by detecting pieces pinned to the opponent king by own sliding attackers. Moving such pieces in a direction other than the attacking ray creates a discovered check. Unfortunately, this code was slower than simply moving the piece and calling Board.IsSquareAttacked. Board.IsSquareAttacked uses pre-calculated moves (magic bitboards) to determine if own king is attacked after moving the piece, constituting an illegal move. Did not include in this PR.

Also, I experimented combining legality checking with playing a move in a Board.PlayMoveIfLegal method. Unfortunately this causes numerous complications with futility-pruned moves. MadChess never prunes moves that deliver check, moves aren’t known to deliver check until they’re played, so this must be detected after the fact (which complicates undoing the move and restoring board state) or detected prior to playing the move (which already has been proven slower). Ugly and prone to bugs. Did not include in this PR.

Also adjusted how nodes are counted- affecting Node Per Second (NPS) metric- to a more honest measurement. A node is counted only in…

  1. Board.PlayMove method
  2. Board.PlayNullMove method (because this changes side-to-move plus a few other properties and advances position index)

2562 +/- 16 ELO at bullet chess.

 

Feature Category Date Commit1 WAC2 ELO Rating3 Improvement
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