Removed memory allocations from IsInCheckmate and IsInStalemate

Vag-Soft · Jul 30, 2023 · 3064406 · 3064406
1 parent a6c102b
commit 3064406
Show file tree

Hide file tree

Showing 3 changed files with 153 additions and 37 deletions.
diff --git a/Chess-Challenge/src/API/Board.cs b/Chess-Challenge/src/API/Board.cs
@@ -20,6 +20,8 @@ public sealed class Board
 		bool hasCachedMoves;
 		Move[] cachedLegalCaptureMoves;
 		bool hasCachedCaptureMoves;
+		bool hasCachedMoveCount;
+		int cachedMoveCount;
 		int depth;
 
         /// <summary>
@@ -154,6 +156,8 @@ public Move[] GetLegalMoves(bool capturesOnly = false)
                 moveGen.GenerateMoves(ref moveSpan, board, includeQuietMoves: true);
                 cachedLegalMoves = moveSpan.ToArray();
                 hasCachedMoves = true;
+				hasCachedMoveCount = true;
+				cachedMoveCount = moveSpan.Length;
 			}
 
 			return cachedLegalMoves;
@@ -169,7 +173,9 @@ public void GetLegalMovesNonAlloc(ref Span<Move> moveList, bool capturesOnly = f
 		{
 			bool includeQuietMoves = !capturesOnly;
 			moveGen.GenerateMoves(ref moveList, board, includeQuietMoves);
-		}
+            hasCachedMoveCount = true;
+            cachedMoveCount = moveList.Length;
+        }
 
 
 		Move[] GetLegalCaptureMoves()
@@ -187,12 +193,12 @@ Move[] GetLegalCaptureMoves()
 		/// <summary>
 		/// Test if the player to move is in check in the current position.
 		/// </summary>
-		public bool IsInCheck() => board.IsInCheck();
+		public bool IsInCheck() => moveGen.IsInitialized ? moveGen.InCheck() : board.IsInCheck();
 
 		/// <summary>
 		/// Test if the current position is checkmate
 		/// </summary>
-		public bool IsInCheckmate() => IsInCheck() && GetLegalMoves().Length == 0;
+		public bool IsInCheckmate() => IsInCheck() && HasZeroLegalMoves();
 
         /// <summary>
         /// Test if the current position is a draw due stalemate, repetition, insufficient material, or 50-move rule.
@@ -202,17 +208,24 @@ Move[] GetLegalCaptureMoves()
         public bool IsDraw()
 		{
 			return IsFiftyMoveDraw() || IsInsufficientMaterial() || IsInStalemate() || IsRepeatedPosition();
-
-			bool IsInStalemate() => !IsInCheck() && GetLegalMoves().Length == 0;
-			bool IsFiftyMoveDraw() => board.currentGameState.fiftyMoveCounter >= 100;
 		}
 
-		/// <summary>
-		/// Test if the current position has occurred at least once before on the board.
-		/// This includes both positions in the actual game, and positions reached by
-		/// making moves while the bot is thinking.
-		/// </summary>
-		public bool IsRepeatedPosition() => depth > 0 && repetitionTable.Contains(board.ZobristKey);
+        /// <summary>
+        /// Test if the current position is a draw due to stalemate
+        /// </summary>
+        public bool IsInStalemate() => !IsInCheck() && HasZeroLegalMoves();
+
+        /// <summary>
+        /// Test if the current position is a draw due to the fifty move rule
+        /// </summary>
+        public bool IsFiftyMoveDraw() => board.currentGameState.fiftyMoveCounter >= 100;
+
+        /// <summary>
+        /// Test if the current position has occurred at least once before on the board.
+        /// This includes both positions in the actual game, and positions reached by
+        /// making moves while the bot is thinking.
+        /// </summary>
+        public bool IsRepeatedPosition() => depth > 0 && repetitionTable.Contains(board.ZobristKey);
 
 		/// <summary>
 		/// Test if there are sufficient pieces remaining on the board to potentially deliver checkmate.
@@ -362,7 +375,17 @@ void OnPositionChanged()
             moveGen.NotifyPositionChanged();
             hasCachedMoves = false;
             hasCachedCaptureMoves = false;
+			hasCachedMoveCount = false;
         }
 
+		bool HasZeroLegalMoves()
+		{
+			if (hasCachedMoveCount)
+			{
+				return cachedMoveCount == 0;
+			}
+			return moveGen.NoLegalMovesInPosition(board);
+		}
+
     }
 }
diff --git a/Chess-Challenge/src/Framework/Application/Helpers/API Helpers/APIMoveGen.cs b/Chess-Challenge/src/Framework/Application/Helpers/API Helpers/APIMoveGen.cs
@@ -51,7 +51,9 @@ public APIMoveGen()
         {
             board = new Board();
         }
-
+
+        public bool IsInitialized => hasInitializedCurrentPosition;
+
         // Movegen needs to know when position has changed to allow for some caching optims in api
         public void NotifyPositionChanged()
         {
@@ -64,6 +66,27 @@ public ulong GetOpponentAttackMap(Board board)
             return opponentAttackMap;
         }
 
+        public bool NoLegalMovesInPosition(Board board)
+        {
+            Span<API.Move> moves = stackalloc API.Move[128];
+            generateNonCapture = true;
+            Init(board);
+            GenerateKingMoves(moves);
+            if (currMoveIndex > 0) { return false; }
+
+            if (!inDoubleCheck)
+            {
+                GenerateKnightMoves(moves);
+                if (currMoveIndex > 0) { return false; }
+                GeneratePawnMoves(moves);
+                if (currMoveIndex > 0) { return false; }
+                GenerateSlidingMoves(moves, true);
+                if (currMoveIndex > 0) { return false; }
+            }
+
+            return true;
+        }
+
         // Generates list of legal moves in current position.
         // Quiet moves (non captures) can optionally be excluded. This is used in quiescence search.
         public void GenerateMoves(ref Span<API.Move> moves, Board board, bool includeQuietMoves = true)
@@ -96,17 +119,17 @@ public void Init(Board board)
             this.board = board;
             currMoveIndex = 0;
 
-            
+
             if (hasInitializedCurrentPosition)
             {
                 moveTypeMask = generateNonCapture ? ulong.MaxValue : enemyPieces;
                 return;
             }
-            
+
             hasInitializedCurrentPosition = true;
 
             // Reset state
-           
+
             inCheck = false;
             inDoubleCheck = false;
             checkRayBitmask = 0;
@@ -131,7 +154,7 @@ public void Init(Board board)
 
             CalculateAttackData();
 
-           
+
         }
 
         API.Move CreateAPIMove(int startSquare, int targetSquare, int flag)
@@ -187,7 +210,7 @@ void GenerateKingMoves(Span<API.Move> moves)
             }
         }
 
-        void GenerateSlidingMoves(Span<API.Move> moves)
+        void GenerateSlidingMoves(Span<API.Move> moves, bool exitEarly = false)
         {
             // Limit movement to empty or enemy squares, and must block check if king is in check.
             ulong moveMask = emptyOrEnemySquares & checkRayBitmask & moveTypeMask;
@@ -218,6 +241,10 @@ void GenerateSlidingMoves(Span<API.Move> moves)
                 {
                     int targetSquare = BitBoardUtility.PopLSB(ref moveSquares);
                     moves[currMoveIndex++] = CreateAPIMove(startSquare, targetSquare, 0);
+                    if (exitEarly)
+                    {
+                        return;
+                    }
                 }
             }
 
@@ -237,6 +264,10 @@ void GenerateSlidingMoves(Span<API.Move> moves)
                 {
                     int targetSquare = BitBoardUtility.PopLSB(ref moveSquares);
                     moves[currMoveIndex++] = CreateAPIMove(startSquare, targetSquare, 0);
+                    if (exitEarly)
+                    {
+                        return;
+                    }
                 }
             }
         }

diff --git a/Chess-Challenge/src/Framework/Application/Helpers/Tester.cs b/Chess-Challenge/src/Framework/Application/Helpers/Tester.cs
@@ -17,21 +17,20 @@ public static class Tester
         public static void Run(bool runPerft)
         {
             anyFailed = false;
-
+
+            new SearchTest().Run(false);
+            new SearchTest().Run(true);
             new SearchTest2().Run();
-
+            new SearchTest3().Run();
+
             RepetitionTest();
-
             DrawTest();
             MoveGenTest();
             PieceListTest();
             CheckTest();
             MiscTest();
             TestBitboards();
             TestMoveCreate();
-            new SearchTest().Run(false);
-            new SearchTest().Run(true);
-
 
             if (runPerft)
             {
@@ -654,6 +653,69 @@ static void WriteWithCol(string msg, ConsoleColor col = ConsoleColor.Red)
             Console.ResetColor();
         }
 
+        public class SearchTest3
+        {
+
+
+            API.Board board;
+            int numCaptures;
+            int numChecks;
+            int numMates;
+            int nodes;
+
+            public void Run()
+            {
+                Console.WriteLine("Running misc search test");
+                Chess.Board b = new();
+                b.LoadPosition("r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - ");
+                board = new API.Board(b);
+                var sw = System.Diagnostics.Stopwatch.StartNew();
+                Search(4, API.Move.NullMove);
+                sw.Stop();
+                Console.WriteLine("Test3 time: " + sw.ElapsedMilliseconds + " ms");
+                bool passed = nodes == 4085603 && numCaptures == 757163 && numChecks == 25523 && numMates == 43;
+                Assert(passed, "Test3 failed");
+
+
+            }
+
+            void Search(int depth, API.Move prevMove)
+            {
+
+                Span<API.Move> moveSpan = stackalloc API.Move[256];
+                board.GetLegalMovesNonAlloc(ref moveSpan);
+
+                if (depth == 0)
+                {
+                    if (prevMove.IsCapture)
+                    {
+                        numCaptures++;
+                    }
+                    if (board.IsInCheck())
+                    {
+                        numChecks++;
+                    }
+                    if (board.IsInCheckmate())
+                    {
+                        numMates++;
+                    }
+
+                    nodes += 1;
+                    return;
+                }
+
+
+                foreach (var move in moveSpan)
+                {
+                    board.MakeMove(move);
+                    Search(depth - 1, move);
+                    board.UndoMove(move);
+                }
+
+            }
+        }
+
+
         public class SearchTest2
         {
             API.Board board;
@@ -778,7 +840,7 @@ public void Run(bool useStackalloc)
                 this.useStackalloc = useStackalloc;
                 Console.WriteLine("Running misc search test | stackalloc = " + useStackalloc);
                 Chess.Board b = new();
-                b.LoadPosition("1r4k1/2P1r1pp/3p4/4n1Q1/1p6/2PB3P/P3pPP1/2B3K1 w - - 7 16");
+                b.LoadPosition("2rqk2r/5p1p/p2p1n2/1pPPn3/8/3B1QP1/PR1K1P1p/2B1R3 w k b6 0 28");
                 board = new API.Board(b);
                 Search(4);
 
@@ -791,19 +853,19 @@ void Search(int plyRemaining)
 
                 numCalls++;
                 var square = new Square(numCalls % 64);
-                miscSumTest += (int)boardAPI.GetPiece(square).PieceType;
-                miscSumTest += boardAPI.GetAllPieceLists()[numCalls % 12].Count;
-                miscSumTest += (long)(boardAPI.ZobristKey % 100);
-                miscSumTest += boardAPI.IsInCheckmate() ? 1 : 0;
+                miscSumTest += (int)board.GetPiece(square).PieceType;
+                miscSumTest += board.GetAllPieceLists()[numCalls % 12].Count;
+                miscSumTest += (long)(board.ZobristKey % 100);
+                miscSumTest += board.IsInCheckmate() ? 1 : 0;
 
                 if (numCalls % 6 == 0)
                 {
-                    miscSumTest += boardAPI.IsInCheck() ? 1 : 0;
+                    miscSumTest += board.IsInCheck() ? 1 : 0;
                 }
 
                 if (numCalls % 18 == 0)
                 {
-                    miscSumTest += boardAPI.SquareIsAttackedByOpponent(square) ? 1 : 0;
+                    miscSumTest += board.SquareIsAttackedByOpponent(square) ? 1 : 0;
                 }
 
                 if (plyRemaining == 0)
@@ -814,10 +876,10 @@ void Search(int plyRemaining)
 
                 if (numCalls % 3 == 0 && plyRemaining > 2)
                 {
-                    if (boardAPI.TrySkipTurn())
+                    if (board.TrySkipTurn())
                     {
                         Search(plyRemaining - 2);
-                        boardAPI.UndoSkipTurn();
+                        board.UndoSkipTurn();
                     }
                 }
 
@@ -826,19 +888,19 @@ void Search(int plyRemaining)
                 if (useStackalloc)
                 {
                     Span<API.Move> moveSpan = stackalloc API.Move[256];
-                    boardAPI.GetLegalMovesNonAlloc(ref moveSpan);
+                    board.GetLegalMovesNonAlloc(ref moveSpan);
                     moves = moveSpan.ToArray(); // (don't actually care about allocations here, just testing the func)
                 }
                 else
                 {
-                    moves = boardAPI.GetLegalMoves();
+                    moves = board.GetLegalMoves();
                 }
 
                 foreach (var move in moves)
                 {
-                    boardAPI.MakeMove(move);
+                    board.MakeMove(move);
                     Search(plyRemaining - 1);
-                    boardAPI.UndoMove(move);
+                    board.UndoMove(move);
                 }