Adaptation of Alpha-Beta Search Algorithm for Real-Time Strategy Game

摘要

Real-time strategy (RTS) game is known for its large action space, rapid response speed, and subtle game scenarios, and it has proven to be a very challenging application area in artificial intelligence research. In the RTS game, the search time increases exponentially as the number of units increases. So it is not possible to achieve a complete search for the game tree in the strict circumstances of time constraints. In this paper, we propose a new tree model, and named τ-AlphaBeta search algorithm. It can reduce the interval of Alpha and Beta appropriately by use the dynamic τ value in the AlphaBeta algorithm. It can return to the better results at the same time of fast search, so that there is a balance between search depth and search time. We use SparCraft as our test platform, which shows that our approach can achieve better results.