MadChess 3.0 Beta Build 093 (Staged Move Generation)

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
Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *