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)… Continue Reading

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… Continue Reading

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… Continue Reading

MadChess 2.0 Beta Build 023 (Delay Move Generation)

I added code to delay move generation if a cached position specifies a best move. The best move is played first. If it causes a beta cutoff, the expense of generating moves is avoided. If not, moves are generated and searched, skipping the best move, which has already been searched. Also, I corrected a bug that caused all searches to use an infinite aspiration window.  The corrected code will search the first ply using an infinite aspiration window, then search subsequent plies with a narrow window around the first ply’s score.  If the score of subsequent searches lies on an… Continue Reading