Our project focuses on the development of a parallel chess AI, leveraging the power of C++ and the OpenMP framework to accelerate the decision-making process in chess. The core objective is to significantly reduce the time required for move selection by distributing computations across multiple threads.
If we want a chess engine to evaluate the best move by looking 3 or 4 moves deeper into the future, the number of possible board states grows exponentially as the depth increases. The heart of our chess AI lies in its ability to explore a vast array of potential moves and their resulting positions, a task managed by the combination of the minimax algorithm and alpha-beta pruning techniques. The minimax algorithm serves as the foundation, guiding the AI in simulating moves and counter-moves to deduce the most advantageous path. Alpha-beta pruning further refines this process, eliminating less promising branches early on, thereby reducing the computational load and focusing resources on more critical analyses.
The main opportunity for parallelism is in the search for the best move. The game tree, representing potential moves and their outcomes, is inherently expansive. Our approach involves dissecting this tree into multiple branches at the root level, each assigned to a separate thread for exploration. This division allows simultaneous traversal of different parts of the game tree, significantly enhancing the breadth and depth of the search within the same computational time frame. By parallelizing the search, we dramatically increase the number of positions analyzed within a given time, directly contributing to more strategic and informed decision-making by the AI. This can significantly reduce the time needed to make an informed decision. It can also allow the chess AI to look farther into the future in the same amount of time compared to a sequential version, allowing it to choose better moves.
Upon reaching leaf nodes or positions requiring evaluation, the computation of heuristic values for these positions presents another opportunity for parallelism. Given that each position's evaluation is independent, we can allocate subsets of these positions to different threads, thereby accelerating the cumulative assessment process.
Parallelizing a chess AI poses several challenges that stem from both the nature of the game and the intricacies of parallel computing.
One challenge is that the minimax algorithm with alpha-beta pruning relies on a tree structure where each node (board position) depends on the evaluation of its child nodes. This inherent dependency complicates parallelization because the value of a parent node cannot be determined until all its children are evaluated, introducing synchronization points that can limit parallel efficiency. Furthermore, different branches of the game tree can have vastly different complexities and depths, leading to divergent execution paths among parallel threads. Some threads might quickly reach a pruning point or a shallow depth, while others might need to explore deeper, more complex branches, resulting in workload imbalance. This leads to challenges with mapping the workload effectively so that threads have similar amounts of work.
Chess AI involves frequent access to the game state, move history, and potentially transposition tables, which is caching of previously evaluated positions. Ensuring memory locality can be challenging but crucial for performance, especially given the potential for a high volume of random memory accesses. The need for threads to synchronize at various points, especially when using alpha-beta pruning, can lead to a high communication-to-computation ratio. Efficiently managing this ratio is critical to ensuring that the overhead of communication does not outweigh the benefits of parallel computation.
We will be building our chess AI system from scratch. We plan on using the ghc cluster machines, using varying numbers of cores to test our system. One resource we will use the wikipedia page about alpha-beta pruning. We may also want to use machines with thread counts higher than 8 like the PSC machines in order to have a better understanding of how well the parallelism works.
If work goes more slowly, we aim to still have a correct parallel chess AI that can achieve at least 2x speedup.
C++ offers high-performance computing capabilities important for the intensive calculations of a chess AI. OpenMP works well for our project since we can use it to distribute branches to different cores.