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.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| [MethodImpl(MethodImplOptions.AggressiveOptimization)] | |
| public (bool isLegal, bool deliversCheck) PlayMove(ulong move) | |
| { | |
| Debug.Assert(Move.IsValid(move)); | |
| Debug.Assert(AssertMoveIntegrity(move)); | |
| CurrentPosition.PlayedMove = move; | |
| // Advance position index and make move. | |
| NextPosition.Set(CurrentPosition); | |
| _positionIndex++; | |
| var piece = Move.Piece(move); | |
| var fromSquare = Move.From(move); | |
| var toSquare = Move.To(move); | |
| var captureVictim = Move.CaptureVictim(move); | |
| Debug.Assert((captureVictim != Piece.WhiteKing) && (captureVictim != Piece.BlackKing)); | |
| if (Move.IsCastling(move)) Castle(piece, toSquare); | |
| else if (Move.IsEnPassantCapture(move)) EnPassantCapture(piece, captureVictim, fromSquare); | |
| else | |
| { | |
| // Remove capture victim (if any) and move piece. | |
| if (captureVictim != Piece.None) RemovePiece(captureVictim, toSquare); | |
| RemovePiece(piece, fromSquare); | |
| var promotedPiece = Move.PromotedPiece(move); | |
| AddPiece(promotedPiece == Piece.None ? piece : promotedPiece, toSquare); | |
| } | |
| // Change side to move, then determine if move was legal. | |
| CurrentPosition.ColorToMove = CurrentPosition.ColorLastMoved; | |
| if (!PreviousPosition.KingInCheck && !Move.IsKingMove(move) && !Move.IsEnPassantCapture(move)) | |
| { | |
| if ((SquareMasks[(int)fromSquare] & PreviousPosition.PinnedPieces) == 0) | |
| { | |
| // Move could not have exposed king to check. | |
| goto ChecksEnemyKing; | |
| } | |
| } | |
| // Determine if moving piece exposed king to check. | |
| var kingSquare = Bitwise.FirstSetSquare(CurrentPosition.GetKing(CurrentPosition.ColorLastMoved)); | |
| if (IsSquareAttacked(kingSquare)) return (false, false); | |
| if (Move.IsCastling(move) && IsCastlePathAttacked(move)) return (false, false); | |
| ChecksEnemyKing: | |
| // Move is legal. | |
| // Determine if move checks enemy king. | |
| CurrentPosition.ColorToMove = CurrentPosition.ColorLastMoved; | |
| kingSquare = Bitwise.FirstSetSquare(CurrentPosition.GetKing(CurrentPosition.ColorLastMoved)); | |
| var check = IsSquareAttacked(kingSquare); | |
| CurrentPosition.ColorToMove = CurrentPosition.ColorLastMoved; | |
| if (Castling.Permitted(CurrentPosition.Castling)) | |
| { | |
| // Update castling rights. | |
| // ReSharper disable SwitchStatementMissingSomeEnumCasesNoDefault | |
| switch (fromSquare) | |
| { | |
| case Square.A8: | |
| Castling.Set(ref CurrentPosition.Castling, Color.Black, BoardSide.Queen, false); | |
| break; | |
| case Square.E8: | |
| Castling.Set(ref CurrentPosition.Castling, Color.Black, BoardSide.Queen, false); | |
| Castling.Set(ref CurrentPosition.Castling, Color.Black, BoardSide.King, false); | |
| break; | |
| case Square.H8: | |
| Castling.Set(ref CurrentPosition.Castling, Color.Black, BoardSide.King, false); | |
| break; | |
| case Square.A1: | |
| Castling.Set(ref CurrentPosition.Castling, Color.White, BoardSide.Queen, false); | |
| break; | |
| case Square.E1: | |
| Castling.Set(ref CurrentPosition.Castling, Color.White, BoardSide.Queen, false); | |
| Castling.Set(ref CurrentPosition.Castling, Color.White, BoardSide.King, false); | |
| break; | |
| case Square.H1: | |
| Castling.Set(ref CurrentPosition.Castling, Color.White, BoardSide.King, false); | |
| break; | |
| } | |
| switch (toSquare) | |
| { | |
| case Square.A8: | |
| Castling.Set(ref CurrentPosition.Castling, Color.Black, BoardSide.Queen, false); | |
| break; | |
| case Square.H8: | |
| Castling.Set(ref CurrentPosition.Castling, Color.Black, BoardSide.King, false); | |
| break; | |
| case Square.A1: | |
| Castling.Set(ref CurrentPosition.Castling, Color.White, BoardSide.Queen, false); | |
| break; | |
| case Square.H1: | |
| Castling.Set(ref CurrentPosition.Castling, Color.White, BoardSide.King, false); | |
| break; | |
| } | |
| // ReSharper restore SwitchStatementMissingSomeEnumCasesNoDefault | |
| } | |
| // Update current position. | |
| CurrentPosition.EnPassantSquare = Move.IsDoublePawnMove(move) | |
| ? _enPassantTargetSquares[(int)toSquare] | |
| : Square.Illegal; | |
| if ((captureVictim != Piece.None) || Move.IsPawnMove(move)) CurrentPosition.PlySinceCaptureOrPawnMove = 0; | |
| else CurrentPosition.PlySinceCaptureOrPawnMove++; | |
| CurrentPosition.FullMoveNumber += (int)CurrentPosition.ColorToMove; | |
| CurrentPosition.KingInCheck = check; | |
| UpdateFullZobristKey(); | |
| Debug.Assert(AssertIntegrity()); | |
| Nodes++; | |
| return (true, check); | |
| } |
by The calling method (such as Search.GetDynamicScore or Search.GetQuietScore) then either 1) undoes the move (if illegal or futile) and continues to the next pseudo-legal move or 2) searches the resulting position.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| var futileMove = IsMoveFutile(board.CurrentPosition, depth, horizon, move, quietMoveNumber, drawnEndgame, | |
| alpha, beta); | |
| var searchHorizon = GetSearchHorizon(board, depth, horizon, move, cachedPosition, quietMoveNumber, drawnEndgame); | |
| // Play and search move. | |
| var (legalMove, checkingMove) = board.PlayMove(move); | |
| if (!legalMove) | |
| { | |
| // Skip illegal move. | |
| if (Move.IsQuiet(move)) quietMoveNumber--; | |
| board.UndoMove(); | |
| continue; | |
| } | |
| legalMoveNumber++; | |
| if ((legalMoveNumber > 1) && futileMove && !checkingMove) | |
| { | |
| // Skip futile move that doesn't deliver check. | |
| board.UndoMove(); | |
| continue; | |
| } | |
| if (checkingMove) searchHorizon = horizon; // Do not reduce move that delivers check. | |
| Move.SetPlayed(ref move, true); | |
| board.PreviousPosition.Moves[moveIndex] = move; | |
| var moveBeta = (legalMoveNumber == 1) || ((MultiPv > 1) && (depth == 0)) | |
| ? beta // Search with full alpha / beta window. | |
| : bestScore + 1; // Search with zero alpha / beta window. | |
| var score = -GetDynamicScore(board, depth + 1, searchHorizon, true, -moveBeta, -alpha); |
In addition to move legality, I experimented with other performance improvements. None of these experiments succeeded except PR 33: Trust Move Capture Victim, which eliminated redundant calls to Position.GetPiece(Square square) in move generation and when playing moves.
Eliminating redundant double-playing of a move (to test move legality) during search increased the search speed of MadChess 3.1 Beta and produced a 36 Elo gain in playing strength.
| Feature | Category | Date | Commit1 | WAC2 | Elo Rating3 | Improvement |
|---|---|---|---|---|---|---|
| Move Legality Performance Improvement |
Search | 2022 Mar 18 | 533e382 | 289 | 2687 | +36 |
| Pawn Structure | Evaluation | 2022 Jan 11 | d691b32 | 288 | 2651 | +15 |
| Threats | Evaluation | 2021 Oct 24 | 26e5323 | 289 | 2636 | +7 |
| Color-Agnostic Code | Evaluation | 2021 Sep 13 | 2b475bc | 286 | 2629 | +12 |
| Singular Move | Search | 2021 Jun 14 | 0c601ea | 290 | 2617 | +13 |
| 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 |
- GitHub commit (hash) or Subversion source code revision (integer)
- Win At Chess position test, 3 seconds per position
- Bullet chess, 2 min / game + 1 sec / move
I work as a Software Architect at an insurance company. We're building a modern tech stack in the cloud using C#, Azure, ASP.NET Core, Angular, TypeScript, etc.