This project was created by Karel Chwistek as semestral project for subject "Programming I" at Charles University in Prague.
The task was specified as:
Create a program, which is able to generate chess puzzles, such as "white mates in 3".
The code was written from scratch, but the ideas used are common throughout the chess programming community.
- Puzzle generation
- Universally used FEN notation to export the puzzles
- Interactive puzzle solving
- Library implementing chess logic (without castling)
Implementation uses both square -> piece and piece -> square lookup data structures for fast move generation.
The logic implements all chess rules (like en-passant, piece promotions) except for castles, as that is not an important feature for chess puzzles.
The implementation has a function to export any position as FEN (but there is no module for exporting games as PGN).
In order to search for valid chess puzzles, it is necessary to implement an engine which is able to search possible continuations and evaluate the position.
The position evaluation function checks whether the position is a mate, stalemate, insufficient material to mate or unclear. If the position is unclear, then the evaluation is material value difference.
The search is implemented as iterated alfa-beta search. The search starts first iteration with depth 0 and goes deeper each iteration. The order of search is defined by evaluation from previous iteration.
Denote "decisive" position as a position, where one side can force a mate in a few (as far as the engine can evaluate) moves.
Puzzles are generated by playing (almost) random moves from starting position, until a decisive position is reached. The moves are chosen based on very shallow evaluation of the engine.
When a decisive position is reached, local search for puzzles is performed by undoing moves. A puzzle with selected difficulty (by number of moves of the solution) is chosen. In case that there is no such puzzle, that would be long enough to match the request, the hardest puzzle is chosen.
The puzzle generator can be seeded to achieve deterministic results.
The program is a console application, its input/output is via console only.
An interactive application generates puzzles, and lets user solve it interactively (user can enter their solution move by move and see, whether it is correct or not).
The application lets user define maximal length of solution for generated puzzles.
The application lets user define a seed. Application runs with the same seed generate the same puzzles (however the results may vary based on compiler, interpreter, etc.).
With default settings, the program runs with up to 10MB of memory.
The application is single threaded. The application should be runnable on any device.
The application was only briefly tested on g++ (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0.