In the Chess project, I implemented AI bots that run the Minimax searching algorithm. The minimax algorithm uses recursive backtracking to find the best way to play the next step. At a high level, it simulates every possible result of the game after K moves, and decides to take the move that gives the current player the highest “value” based on some evaluation function, assuming that both players play optimally.
The minimax algorithm is great, but since chess is a rather complicated game, the vast search space makes simple minimax not good enough. To speed up minimax search, I used the ForkJoin framework of Java to parallelize the search. The parallelization is rather simple: instead of going through each branch in a for loop, we start a new thread for each branch and let Java (and the OS) take care of all the threads. This leads to a significant speedup.
Besides speeding up with parallelization, another strategy would be improving the Minimax search algorithm itself. A famous improvement to the Minimax algorithm is known as Alpha-Beta pruning. Basically, it “prunes” the branches that can’t possibly contain the max/min value of a node. The pruning speeds up the search for about 50%, and is really powerful and useful in many scenarios.
In the end, my bot was able to beat myself and my roommate. We were not completely novices, so I am pretty happy with the results. In future work, I would like to try using the AlphaZero algorithm to build an even more powerful chess AI.