EndGame is a deterministic chess engine written in C++ that aims to find guaranteed checkmate lines in chess puzzles. It focuses on solving two and three move checkmate puzzles due to RAM limitations for the decision tree.
- Deterministic Algorithm: EndGame uses a deterministic approach to solve chess puzzles, ensuring a correct answer for each problem.
- Large Database of Test Cases: With a database of 550,000 puzzles, including 300,000 two-move puzzles, EndGame has a wide range of test cases to work with.
- FEN Notation Parsing: EndGame parses standardized chess FEN notation to generate the board state for each puzzle.
- Legal Move Generation: The engine generates a vector of legal moves, starting with a list of pseudo-legal moves and then filtering out those that would result in a self-check.
- n-ary Tree of Board States: EndGame utilizes an n-ary tree to map all possible move combinations and board states, allowing for efficient exploration of the decision tree.
- Backward Pathfinding: The algorithm goes backward through the decision tree to identify the guaranteed checkmate path and presents the solution.
EndGame starts by selecting a random mate-in-two puzzle from the test case file. It then parses the FEN string and generates the board, using lowercase letters for black pieces and uppercase letters for white pieces.
Once the board is set up, the engine generates a vector of legal moves by first creating a list of pseudo-legal moves without considering self-checks. The engine then filters out any moves that would result in a self-check.
To explore all possible move combinations, EndGame creates an n-ary tree of board states. The algorithm then traverses the decision tree in reverse to find the guaranteed checkmate path. Finally, the program prints out the correct solution path for the given puzzle.