New heuristic algorithm to improve the Minimax for Gomoku artificial intelligence

Abstract

<p>Back in the 1990s, after IBM developed Deep Blue to defeat human chess players, people tried to solve all kinds of board game problems using computers. Gomoku is one of the popular board games in Asia and Europe, people also try to simulate and solve it through computer algorithms. The traditional and effective strategy for Gomoku AI is the tree search algorithm. The minimax algorithm is one of the most common game trees used in AI strategy. But obviously, the biggest problem with this is that as the number of stones on the board and the number of search depth increases, even computers have to spend a lot of time calculating each step. The number of nodes with exponential increment is really difficult to achieve in practical terms. In the paper, we will discuss in detail how to improve the most basic minimax algorithm. The direction of the research is on how to improve the efficiency of the algorithm and maximize the search depth. The most common means used now is to cut out the clutter in the search tree through Alpha-Beta pruning. Moreover, we offer a new heuristic algorithm which can boost the depth search processing a lot. The core idea is how to sort and reduce the potential candidates for each depth and nodes, and how to return the best path in a recursive way. We finally will compare and compete with the traditional minimax algorithm and New Heuristic minimax algorithm in the experimental testing session. Based on the API developed individually, this paper will explain back-end algorithms and the program user interfaces itself in detail.</p>