September 2022
This project implements Connect 4 game using a recursive Minimax algorithm enhanced with full alpha-beta pruning, transposition tables, and a custom heuristic evaluation function, it has been ported to the web using WebAssembly (WASM). The algorithm efficiently simulates possible moves and selects the optimal play in order to win or force a draw.
The algorithm recursively explores future game states. By maintaining and updating alpha and beta parameters during the recursive search, it prunes branches that cannot improve the outcome. This significantly reduces the number of nodes evaluated in the search tree.
A transposition table is used to cache previously evaluated board states, avoiding redundant calculations. The heuristic evaluation function assesses board positions by counting set bits, considering positional weight via a distribution array, and measuring potential threats. This helps the it to decide on the best move quickly.
The implementation tracks performance metrics such as total nodes explored, transposition table hits, and elapsed time. Although the algorithm leverages alpha-beta pruning and caching for efficiency, its performance still depends on the board state and depth limits. Further optimizations—such as iterative deepening or parallel search—could enhance performance.