Optimization of the minimax algorithm with alpha-beta pruning for chess artificial intelligence systems

Abstract

The paper considers approaches to training an artificial chess game model. The minimax algorithm with alpha-beta pruning, implemented in the Python programming language with the corresponding chess library, was chosen as the basic search method. Alpha-beta pruning reduces the computational complexity of traversing the game tree by discarding at the early stages those branches that do not affect the final solution. Heuristic extensions were added to the basic algorithm: iterative deepening, transposition tables with Zobrist hashing, ordering of moves according to the principle of priority of capturing the most valuable piece by the least valuable attacker, killer heuristics and historical heuristics, as well as quiescence search to weaken the horizon effect. An adaptive evaluation function was developed that takes into account material balance, positional evaluation tables, king safety, pawn structure, piece mobility, and key square control. The model was trained on a sample of over one hundred thousand games of levels from amateur to grandmaster. According to the experimental results, the combination of alpha-beta pruning with move ordering and transposition tables reduces the number of evaluated nodes by an average of one hundred and twenty times compared to the standard minimax at a depth of five half-moves, and the decision time is reduced from ninety-two point four seconds to zero point forty-three seconds. In simulated matches against a chess engine, the model demonstrates a high percentage of victories at initial levels of complexity (up to ninety-six point five percent at level zero). As a promising direction for further development, an architecture for integrating a neural network estimator based on an efficiently updated artificial neural network into a classical alpha-beta search tree is proposed, which will allow combining the interpretability of the classical method with the adaptability of deep learning. The proposed approach is suitable for decision support systems in deterministic games with complete information and in strategic planning problems.