Search

This paper delves into the investigation, analysis, and solution of a specific algorithmic problem: the implementation of a chess engine utilizing the Minimax algorithm. The choice of chess as the focal point is due to it being both a popular game in real-world and popular case study for this type of algorithms. The primary motivation behind this endeavor is to gain a deeper understanding and mastery of search algorithms. The main challenge encountered was the vast number of chess variants and possible states that could be reached during search. Overcoming this obstacle required numerous optimizations and special approaches, reflected in the representation of the chess board and pieces, search optimization, etc... Notably, solving this problem involved preliminary steps such as studying basic recursive algorithms and exploring search trees. The selection of the Minimax algorithm was a logical choice, considering chess is a two-player game with fully visible state and known environment. An alternative could be Monte Carlo Tree Search algorithm, as used in Alpha-zero engine. Alpha-beta pruning was employed to enhance search depth. Simple evaluation function was implemented to count material advantage, with adjustment based on piece positions. The chess board was represented using the mailbox concept, employing 12x12 board which each square and piece represented integer value. Practically, the solution to this problem unified all required steps, starting from analyzing the theory of search algorithms, formulating theoretical solution ideas, and concluding with solution implementation in the chosen programming language (in this case, C++). As the application was designed as a command-line interface, the project also implemented a standard communication protocol. Notably, the entire project was deployed to the lichess server (open-source), utilizing the lichess server's graphical interface. [ABSTRACT FROM AUTHOR]