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

MadChess 3.0 Beta f231dac (PVS and Null Move Improvements)

I improved MadChess 3.0 Beta’s Principal Variation Search (PVS) by consolidating two separate re-searches into one. In addition, I changed the null move implementation so it reduces the search horizon more aggressively if the current position’s static score far exceeds beta.

Previously, if a PVS search failed high, the engine would confirm the fail high first by restoring beta from bestScore + 1 to its original value and re-searching. If that also failed high, it restored the search horizon from a reduced value to its original value and re-searched. If that failed high the engine took a beta cutoff.

I simplified the code to a single re-search.

Null move now reduces more aggressively if the current position’s static score far exceeds beta.

This increased the playing strength of MadChess 3.0 Beta by 20 ELO.

 

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

Play Rather Than Code

Watching The Queen’s Gambit on Netflix nudged me to play chess online. I’ve spent time on chess over the last few years… programming an engine, not actually playing. I’m very rusty. Though my puzzle rating is decent. It’s much higher than my game rating, suggesting I need to work on time management. Thinking fast is not my strength, but everyone online plays blitz or bullet so here goes nothing…

Last night I joined a bullet tournament with a 2+1 clock. Each player has 2 minutes to make all their moves in the game, plus 1 second added to their clock after each move. Many of the games I played were blunder fests. But I managed to play solidly in a few. Here’s a well played game considering I’m making most of my moves in like 2 or 3 seconds. I play white (DamageInkk). Afterwards I had MadChess analyze the game. Converting a “won” game is not inevitable for a patzer like me, especially with the time pressure, so I was glad to do it and glad to see MadChess confirm I played accurately from move 16 on.

I like the checkmate configuration at the end of the game: My opponent chases my pawn, walking right into a discovered check / pawn promotion mate.

Knight Outpost

A knight positioned on an outpost controls opponent territory, restricting movement of the opponent’s pieces on the opponent’s side of the board. An outpost is defined as a square on the fifth or sixth rank, occupied by a minor piece (usually a knight), supported by its own pawn, and positioned such that it cannot ever be attacked by an opposing pawn. In other words, the opponent has no pawns on the neighboring files, or if the opponent has pawns on the neighboring files, they’ve advanced even with or beyond the outpost square.

r4rk1/1qb2ppp/1pN2n2/pP2p3/P3P3/4BP2/3RQ1PP/3R2K1 b - - 0 1

Red highlights in the above position indicate squares in black territory attacked by the white knight on c6. Yellow highlights indicate squares in white territory attacked by the same knight.

Controlling Space

Controlling board space- especially central squares- provides room to maneuver pieces. It cramps the opponent’s position, who will have difficulty bringing pieces out from behind their pawns. And it enables a quick redeployment of pieces from one zone of action (queenside, for example) to another zone of action (kingside) to initiate an attack or muster a defense around the king.

Be careful not to overextend when grabbing space. In the following position, white appears to control more space than black. Black’s counterplay demonstrates, however, that white merely occupies space but does not control it.

r1bq1rk1/ppp1ppbp/n2p1np1/4P3/2PP1P2/2N2N2/PP4PP/R1BQKB1R b KQ - 0 1

Black moves his knight to safety (and attacks the e5 central square) then takes advantage of white’s greediness.

Fortunes have changed. Now black controls more territory.