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.

1. Subversion source code revision
2. Win At Chess position test, 3 seconds per position
3. Bullet chess, 2 min / game + 1 sec / move