An extensible framework for programming search algorithms (minimax with cutting, killer moves, transposition tables, etc) and end-tables for board games such as two-player, full info board games such as chess, MNK (generalized TicTacToe), Connect4, checkers etc. Heavy use of teamplates and newer C++ features such as variadic templates, constexpr, consteval, concepts, std::experimental::generator and heavy use of C macros around chess moves.
To get local enlistment:
git clone https://github.com/oggy22/BoardGames- Open
BoardGames.sln
The main algorithm for finding best moves, regardless of the game played, is the minmax algorithm. It is implemented in a highly templatized manner where you can provide any game as long as it satisfies the requirements specified by the C++ concept BoardPosition. The following heuristics are implemented:
- Alhpa-beta prunning
- Killer move
- Transposition tables
Unlike the minimax algorithm, which recursively evaluates positions to determine the best move during play, endgame tables (or tablebases) are precomputed databases that store the best move for every possible position within a specific endgame configuration in advance. Endgames are currently in development for chess.