Move Ranking and Evaluation in the Game of Arimaa
David Jian Wu · 2011
In the last two decades, thanks to dramatic advances in artificial intelligence, computers have approached or reached world-champion levels in a wide variety of strategic games, including Checkers, Backgammon, and Chess. Such games have provided fertile ground for developing and testing new algorithms in adversarial search, machine learning, and game theory. Many games, such as Go and Poker, continue to challenge and drive a great deal of research. In this thesis, we focus on the game of Arimaa. Arimaa was invented in 2002 by the computer engineer Omar Syed, with the goal of being both difficult for computers and fun and easy for humans to play. So far, it has succeeded, and every year, human players have defeated the top computer players in the annual “Arimaa Challenge” competition. With a branching factor of 16000 possible moves per turn and many deep strategies that require long-term foresight and judgment, Arimaa provides a challenging new domain in which to test new algorithms and ideas. The work presented here is the first major attempt to apply the tools of machine learning to Arimaa, and makes two main contributions to the state-of-the-art in artificial intelligence for this game. The first contribution is the development of a highly accurate expert move predictor. Such a predictor can be used to prune moves from consideration, reducing the effective branching factor and increasing the efficiency of search. The final system is capable of predicting almost 90 percent of expert moves within only the top 5 percent of its choices, and enables an improvement of more than 100 Elo rating points. The second contribution is a comparison of several algorithms in reinforcement learning for learning a function to evaluate the long-term value of a position. Using these algorithms, it is possible to automatically learn an evaluation function that comes close to the performance of a strong hand-coded function, and the evidence presented shows that significant further improvement is possible. In total, the work presented here demonstrates that machine learning can be successful in Arimaa and lays a foundation for future innovation and research.