Final Report
Summary
In this project, we implemented six terminal-based chess engines using either the simple minimax algorithm or alpha-beta pruning, with serial, OpenMP, and MPI versions for each method. The minimax engines achieved a 50x speedup on 128 cores and a playing strength of just under 2000 ELO at a depth 5 cutoff. Alpha-beta pruning, which significantly optimizes search efficiency, delivered a 300x speedup over the naive minimax serial engine. However, due to the sequential nature of alpha-beta pruning, its parallel versions had less pronounced speedups relative to their serial counterpart. Despite this, all parallel alpha-beta engines achieved over 2200+ ELO at a depth 7 cutoff, demonstrating strong performance and computational efficiency.
Background
Our first three engines use the simple minimax algorithm. Here we set a fixed MAX_DEPTH to be 5 as default. Then, we construct the game tree to this MAX_DEPTH on the stack. That is, we list out all possible moves for the computer from the current position, and recursively generate all moves for the opponent, and so on until we reach the leaf nodes. Then, we run a static evaluation function to score the position (positive for white and negative for black). White plays the role of the maximizer and black plays the role of the minimizer. The minimizer will score the intermediate nodes as the minimum of its children scores and the maximizer will score the intermediate nodes as the maximum of its children scores. Eventually, there will be a score for every choice the computer has and depending on the computer’s color, it will select either the maximum or minimum score. Shown below is a simple example of minimax for a MAX_DEPTH of 3. The bottom scores were computed with a custom static evaluation function by counting material and positional advantages using heatmaps. The intermediate nodes are computed via maximizing or minimizing the children nodes. The top score +1.1 is the maximizer’s evaluation of the position (they are white and winning) and the second layer is the maximizer’s evaluation of the possible choices (+1.1 and -0.2).
The high workload comes from the game tree’s high branching factor. Minimax is highly parallelizable as different subtrees can be computed independently and the synchronization between different branches of the game tree can be evaluated with a reduce (alternating max or min). The evaluation of the board is a data parallel job as it is unrelated to other board positions.
Our next three engines use alpha-beta pruning, an optimization of minimax. The idea behind alpha-beta pruning is that we store two values during our search:
-
Alpha, which is the minimum score that the maximizing player is guaranteed to attain at any moment in the recursive search.
-
Beta, the maximum score the minimizing player is guaranteed to attain at any moment during the recursive search.
We modify the recursive call to minimax with the values of alpha and beta and when it is determined that traversing down a particular branch is no longer optimal for each player based on the values of alpha and beta, we break the search, saving computation time. Below is an example of the algorithm:
Here, we show an example of pruning occurring from the previous example. The maximizer has determined by the time it reaches the right subtree that it can get at least +1.1. Then, when it determines that the minimizer will get a value of at most -0.2 it can prune the rest of the right subchild as the maximizer will pick +1.1, which is better than whatever the minimizer can pick later.
Note that because alpha and beta depend on which nodes a single thread traversing the tree has visited previously, this introduces challenges to parallelization. When we parallelize, the individual threads work on deeper layers of the tree and a smaller fraction of the entire tree gets pruned.
The board state representation and move generation were handled by the triple happy chess library (THC) https://github.com/billforsternz/thc-chess-library. We used this library since we have a huge game tree and so generating nodes was computationally and spatially expensive. Moves are represented with 32 bits and legal moves are stored in a vector. The board is represented with the class ChessRules which is a bitboard with move history and castling rights. Since this board is large, we did not duplicate the board for serial versions with one thread but we did have to copy the board and distribute them to the different threads in the parallel versions.
In the move vector, we implemented move reordering using capturing heuristics to give an approximation of the best to worst moves before the search. The reason for this is twofold. First, move reordering helps with alpha-beta pruning. This makes it more likely that a branch gets pruned earlier. This is especially useful in the parallelized version as there is less benefit from pruning near the deeper layers of the tree. Secondly, it helps more evenly distribute the workload among different threads.
In our main function we have a simple loop which allows the computer and the player to take turns entering moves. The input to the algorithm is an algebraic notation string representing the player’s move. The computer returns the best move. We introduced iterative deepening and time outs in the input. For each engine, we let it search for each fixed depth until we reached the MAX_DEPTH or a timeout. Below, we computed the game tree up to depth 1, and printed out the time it took to compute with the score evaluated, total leaf nodes computed, and rate (1000 nodes per second). We then did this again for depth 2, and so on. Note that because the branching factor for chess is high (~35 per level) the majority of the computation time comes from the computation of the last node and so there is not much overhead by recomputing previously visited layers. Furthermore, temporal locality is helpful as many of the previously computed nodes stay in the cache. However, with this output in addition to the computer’s move we have a lot of data we can use to benchmark our engine’s performance.
Approach
During the initial implementation of the serial version of our engine, we decided to use the THC Chess Library, “a C++ implementation of the rules of standard chess”. We think that this decision was important in order for us to focus on implementing different search algorithms and parallelization techniques rather than focusing on correctly implementing the rules of chess, which can be a complicated and cumbersome process.
Techniques Used:
Given the scope of the final project, we decided to explore two parallel techniques from class: OpenMP and MPI. We decided to use these techniques instead of CUDA since we felt that backtracking would involve divergent code execution, making OpenMP and MPI a better fit for our particular use case. Overall, the MPI implementation was definitely one of the more challenging parts of the project, requiring careful consideration of work assignment and communication.
Mapping to hardware:
At a high level, we represent our problem as a (board_state, current_depth) pair. Each of these pairs is mapped to a core on the machine. In the case of OpenMP, total threads <= total cores on the machine, which means that it is highly likely that each problem gets a dedicated core. In the case of MPI, this translation of problem -> core is more explicit.
We developed our code on our local machines, and performed final benchmarking on the PSC machines.
OpenMP Parallelization:
After implementing the serial version, the OpenMP implementation involved adding parallelization and experimenting with different configurations, such as dynamic scheduling vs static scheduling and coarse-grained locking vs fine-grained locking.
The initial implementation was straightforward, involving an omp for loop. Reviewing the techniques discussed in class, we then decided to try dynamic work allocation, which gave us a noticeable speed improvement. Upon further consideration of the code, we realized that our omp critical section was shared amongst different parallel calls of the recursive function. This was definitely not ideal, and we decided to implement fine-grained locking within each recursive call. This also helped us improve the speedup over the previous version. We also tried a version of the code with parallel reduction, however, this performed worse than the previous version at 128 threads.
Overall, we experimented a lot with different approaches such as reduction vs critical sections, static vs dynamic scheduling and fine-grained vs coarse-grained locking.
MPI Parallelization:
The MPI implementation was significantly more involved compared to the OpenMP implementation for our project. Our initial idea for our MPI implementation involved simply allocated work among processors at the top level of the recursion tree. However, given that the average number of moves in a game of chess is 35, and not all branches have an equal amount of work to be done, this approach would not scale well with an increasing number of processors.
In our final implementation we decided to use a recursive strategy for splitting processors into subsets using MPI communicators to represent sets of processors.
Then, as we recurse down the game tree, we create two branches:
-
If the number of possible moves is greater than the number of the available processors, we treat this as our base case. Each processor gets at least [n_moves/n_proc] moves to recursively calculate.
-
If the number of available processors is greater than the number of possible moves, then we split our processors into n_moves groups, with each move getting at least [n_proc/n_moves] processors. We then traverse down the game tree with this processor allocation until the number of processors is no longer greater than the number of possible moves for that given state.
After recursion, different sets of processors share their results using an MPI reduction. They share 8 bytes of information with other processors: the best score (represented as a 4-byte floating-point number) and the best move (which is represented using a 32 bit thc::Move struct). This data is then returned to the caller of the current recursive call.
Another observation here is that move reordering in our alpha-beta pruning implementation sorts the moves based on an estimation of their viability. This serves as a proxy for how big a particular branch would be. As a result, the allocation of processors to moves should be in an alternating fashion instead of a contiguous manner in order to ensure fair work division.
Our parallel implementation of the alpha-beta pruning algorithm was similar, with the difference that alpha-beta pruning happens within a given processor when the number of processors is less than the number of available moves. This does affect how many branches can be pruned, however, also reduces the amount of required communication between processors. This implementation scales similarly to the OpenMP parallel alpha-beta pruning implementation.
Results
For correctness, we compared the outputs to the serial versions at depth 5 for minimax and depth 7 for alpha beta pruning. We played several games with the depth 5 and depth 7 solutions on chess.com bots and determined that the depth 5 solutions play at slightly under 2000 ELO and the depth 7 solutions play at above 2200 ELO.
For benchmarking, we measure the performance of the two algorithms we use: naive minimax and alpha-beta pruning. For both of these, we use the sequential algorithm as the base performance. We then measure the speedup we obtain by using OpenMP and MPI for both algorithms.
Problem sizes:
In order to get a better idea of the impact of parallelism, we reasoned that we should look at bigger depths. For the naive algorithm, we decided to use a MAX_DEPTH of 5 since this is the maximum depth the algorithm could reach within a minute. For alpha-beta pruning, we used a MAX_DEPTH of 7 for similar reasons.
Targeted Machines:
The parallel techniques we use, OpenMP and MPI, are both suited towards parallelizing with CPUs. We think that this is the correct choice over a GPU given the divergent nature of the code. On further researching this, we found that the application on GPUs to chess engines is more towards applying machine learning approaches. On the other hand, traditional chess algorithms are targeted better by CPUs.
Results:
-
Naive Minimax
As a first step for this project, we implemented a sequential chess engine that uses simple minimax. Simple minimax is a highly parallelizable algorithm since each branch is independent of other branches at a given depth level.
-
MPI
The algorithm scales really well on using MPI. We measure a 54x speedup on using 128 cores.
An interesting trend in this graph is that speedup increases dramatically on changing the number of processors from 32 to 64. This was an extremely surprising trend. Further investigating this trend, we found out that there is a 1.89x speedup going from 32 to 34 threads! After this “bump”, the code scales linearly again.
We hypothesize that this is due to the fact that our code branches into two cases:
-
Number of processors <= Number of available moves
-
Number of processors > number of available moves
On changing the number of cores to 34, the second condition gets triggered, which should allow for better work division. Let’s look at this through an example, considering two cases:
-
20 moves and 19 processors. Here, 1 processor has to take care of 2 moves. This one processor changes the total runtime to 2x.
-
20 moves and 20 processors. Here, each processor only has to take care of 1 move.
This example illustrates a 2x performance speedup on increasing the number of cores by 1. We think that this also explains the performance “bump” we notice.
b. OpenMP
For OpenMP, we find that the algorithm does not scale as well as we expected. Going from static to dynamic scheduling gave us noticeable results. However, coarse-grained vs fine-grained locking did not make a significant difference. We also tried to implement omp parallel reduction instead of the locking/critical sections, which also did not significantly affect the performance.
We observe a similar speedup until processors = 16. However, performance seems to plateau after this. This is true for all the approaches that we explored.
In order to investigate this, we tried exploring the number of cache misses as we scale across multiple processors:
We can see that similar to the performance, the number of cache misses also plateaus as we increase the number of processors. One possible factor for this is the overhead from thread synchronization and thread management. Another possibility is that there is unexpected behavior in how OpenMP is assigning threads for recursive calls.
-
Alpha-beta pruning
Alpha-beta pruning helps us speed up the engine significantly. Comparing the sequential version of alpha-beta pruning vs sequential simple minimax, we see a speedup of 300x! Alpha-beta pruning is incredibly useful for trimming branches in the search tree.
At the same time, this is a very sequential algorithm, and the speedups we can see for this algorithm are limited.
We see that both algorithms scale similarly for alpha-beta pruning. For the OpenMP version, the contention on locks increases given that the alpha and beta values need to be updated by all threads. As a result, the lock contention increases with the number of threads.
For MPI, an interesting observation is that the effect from pruning is diminished on increasing the number of processors since each processor prunes on its assigned branches. This means that while there is no additional cost from lock contention, the number of branches we can prune is also reduced. Overall, our performance increases as the number of cores increases.
Updated Project Schedule
-
Work Completed So Far:
-
Week 1: Researching chess engine algorithms and beginning implementation and design completed by Naman and Vincent (changed original project idea)
-
Week 2: Implementing working sequential version and OpenMP version, completed by Naman and Vincent
-
-
Revised Plan for the Coming Weeks:
-
Week 3.1: OpenMPI version assigned to Naman and Vincent.
-
Week 3.2: Finish OpenMPI engine with debugging assigned to Naman and Vincent.
-
Week 4.1: Testing number of nodes computed and collecting data assigned to Naman and Vincent.
-
Week 4.2: Assembling data and finishing stretch goals assigned to Naman and Vincent.
-
Summary of Work Completed So Far
-
We have completed a sequential version of a chess engine which plays at around 2200 ELO although still difficult to measure. We also have a framework for reporting the number of nodes computed as well as the time it took for the engine to compute the nodes.
Goals and Deliverables
Current Goals and Deliverables:
-
On-Track Deliverables: Sequential version and OpenMP version are done. We also have a good way of reporting data including time spent searching, number of nodes searched etc.
-
At-Risk Deliverables: We haven’t yet fully explored the Message Passing version of the parallel code yet. We aim to start working on this after the milestone report.
-
"Nice-to-Haves": Lazy SMP evaluation, quiescence search, book + syzygy bases. NNUE evaluation.
Poster Session
We will display graphs for the speedup for each of the three engines that we are implementing. We will also show how it scales. We will show max depth computed for each move, ELO, how many nodes computed, as well as how many thousands of nodes are computed per second. It will be available for download for anyone to play the engines. We will also play a few games with the engines against each other to confirm that more nodes computed will lead to greater performance. We hope to show that the performance of the engine scales with more cores.
Preliminary Results
We have the ability to report the total number of nodes computed. We are still debugging the OpenMP output. Above is the terminal output of the engine.
Our serial-engine was able to reach a winning position against a chess engine from chess.com with an ELO of 2000, although it was unable to deliver a checkmate. We played them against each other on the chess.com interface.
Issues and Concerns
Challenges Faced:
-
The chess engine is somewhat hard to debug. We know that it works though there are some cases where the engine may not necessarily pick the best move and we do not know if it is due to a bug or if our hard coded evaluation function is not good. Implementing NNUE is difficult.
-
Remaining Work:
-
We have to implement the OpenMPI version and collect performance data. We also have to complete our stretch goals.
Team Meeting with Course Staff
We met with Professor Skarlatos on 12/2. We updated that we have the serial version of our chess engine working and about to finish the OpenMP version of the parallelization. We discussed with Professor Skarlatos that finishing the MPI version of the engine after the OpenMP version should be sufficient for the scope of our project.
Milestones
Updated Project Schedule
-
Work Completed So Far:
-
Week 1: Researching chess engine algorithms and beginning implementation and design completed by Naman and Vincent (changed original project idea)
-
Week 2: Implementing working sequential version and OpenMP version, completed by Naman and Vincent
-
-
Revised Plan for the Coming Weeks:
-
Week 3.1: OpenMPI version assigned to Naman and Vincent.
-
Week 3.2: Finish OpenMPI engine with debugging assigned to Naman and Vincent.
-
Week 4.1: Testing number of nodes computed and collecting data assigned to Naman and Vincent.
-
Week 4.2: Assembling data and finishing stretch goals assigned to Naman and Vincent.
-
Summary of Work Completed So Far
-
We have completed a sequential version of a chess engine which plays at around 2200 ELO although still difficult to measure. We also have a framework for reporting the number of nodes computed as well as the time it took for the engine to compute the nodes.
Goals and Deliverables
Current Goals and Deliverables:
-
On-Track Deliverables: Sequential version and OpenMP version are done. We also have a good way of reporting data including time spent searching, number of nodes searched etc.
-
At-Risk Deliverables: We haven’t yet fully explored the Message Passing version of the parallel code yet. We aim to start working on this after the milestone report.
-
"Nice-to-Haves": Lazy SMP evaluation, quiescence search, book + syzygy bases. NNUE evaluation.
Poster Session
We will display graphs for the speedup for each of the three engines that we are implementing. We will also show how it scales. We will show max depth computed for each move, ELO, how many nodes computed, as well as how many thousands of nodes are computed per second. It will be available for download for anyone to play the engines. We will also play a few games with the engines against each other to confirm that more nodes computed will lead to greater performance. We hope to show that the performance of the engine scales with more cores.
Preliminary Results
We have the ability to report the total number of nodes computed. We are still debugging the OpenMP output. Above is the terminal output of the engine.
Our serial-engine was able to reach a winning position against a chess engine from chess.com with an ELO of 2000, although it was unable to deliver a checkmate. We played them against each other on the chess.com interface.
Issues and Concerns
Challenges Faced:
-
The chess engine is somewhat hard to debug. We know that it works though there are some cases where the engine may not necessarily pick the best move and we do not know if it is due to a bug or if our hard coded evaluation function is not good. Implementing NNUE is difficult.
-
Remaining Work:
-
We have to implement the OpenMPI version and collect performance data. We also have to complete our stretch goals.
Team Meeting with Course Staff
We met with Professor Skarlatos on 12/2. We updated that we have the serial version of our chess engine working and about to finish the OpenMP version of the parallelization. We discussed with Professor Skarlatos that finishing the MPI version of the engine after the OpenMP version should be sufficient for the scope of our project.
Proposal
Project URL
Summary
We aim to implement three chess engines: a sequential engine, a parallel engine, and a parallel engine with randomization. We will then compare their speed and ELO performance.
Background
There will be three chess engines implemented for this project.
The first engine will be a sequential solver, which traverses down the game tree with the minimax algorithm and optimized using alpha-beta pruning. It evaluates the resulting positions at the child nodes using heat maps for positional evaluation and point counters for material evaluation.
The second engine will parallelize the search steps of the game tree that the sequential engine traverses, and will coordinate the best moves among different threads. Synchronization happens after all of the threads have reached the max depth. Parallelism will also be used to sort move orders.
Finally, the third engine will implement a randomized algorithm for furthering the computations of the game tree past the previous engine's max depth. We will use a randomized algorithm similar to simulated anneal when the bottom of the search tree has been reached, to again additional insight about further moves.
We will be using a chess library that creates efficient data structures for chessboard representation, move generation, and evaluation. However, we will focus on the parallelization search algorithms. Additionally, we will integrate simulated clients that test the engines by querying it for moves under various game conditions, estimate each of the engines' ELOs, and time the performance of each engine to reach depth n.
Challenge
Parallelizing a chess engine is challenging due to the irregular and dynamic nature of the game tree and the dependencies inherent in the alpha-beta pruning algorithm. The game tree’s varying branch factors and depths make it difficult to distribute workloads evenly across threads, while pruning decisions rely on previously explored branches, requiring careful synchronization of shared alpha and beta bounds. Shared resources like transposition tables, essential for caching evaluated positions, must be accessed efficiently to prevent contention, which can become a bottleneck. Additionally, the divergent execution paths in the search tree result in imbalanced workloads and complicate the use of uniform parallelism techniques. These challenges are compounded by a high communication-to-computation ratio, irregular memory access patterns, and the need to minimize synchronization overhead while scaling effectively on multi-core systems. By addressing these issues, we aim to learn how to design scalable search algorithms, optimize memory usage, and implement efficient load balancing to maximize the engine’s throughput and correctness.
Resources
We will be creating the parallelization algorithms with C++ from scratch. We will also be using a chess library to do move generation and board data structures. We will be running the project on the GHC cluster machines as well as PSC.
Goals and Deliverables
Plan to Achieve
Our main goal is to develop a functional parallel chess engine that implements core optimizations like parallel alpha-beta pruning, transposition tables, and move ordering. We aim to achieve at least a 5x speedup on a 16-core system compared to a sequential version and validate correctness through matches against known engines or test games. Speedup graphs will demonstrate scalability, and we will test the engine under simulated client conditions.
Hope to Achieve
If ahead of schedule, we aim to integrate advanced techniques like late move reductions, null move pruning, and an NNUE evaluation model to enhance performance. Our stretch goal is to process 10 million positions per second and achieve a 50x speedup over the sequential baseline.
Demo Plan
We will present speedup graphs, compare sequential vs. parallel performance, and showcase the engine playing chess against simulated clients or interactively against users. The demo will highlight both performance gains and practical functionality. We will also have the chess engines play against other chess bots to determine its ELO.
Platform Choice
We will be running the project on the GHC cluster machines and PSC, as these have enough cores for our project to demonstrate scalability. Furthermore, we will not be using CUDA and will resort to OpenMP or MPI as there is divergent execution.
Schedule
Week 1 - Research chess algorithms and implement sequential engine.
Week 2 - Implement parallel chess engine. Start randomized engine.
Week 3 - Finish implementing engines and add final optimizations.
Week 4 - Testing engines, recording data, modifying engines accordingly.