|Rolling the Dice: Leveraging Monte-Carlo Tree Search in Game AI
|Nathan Sturtevant, Jeff Rollason, Peter Cowling, David Churchill
|University of Denver, AI Factory, Ltd., University of York, UK, University of Alberta, Canada
|Track / Format:
Did you know free users get access to 30% of content from the last 2 years?
|As the complexity of potential state spaces that AI agents have to explore moves beyond more traditional games like chess, search-based approaches like minimax are no longer feasible to employ. Worse, when imperfect information is involved, the problem becomes largely intractable. What is needed is a way of exploring that multi-layered possibility space and coming up with a "good enough" answer, even if it isn't the "mathematically perfect" one, and still do it in a reasonable amount of time. Using examples from a suite of successful commercial mobile games, as well as the winner of the annual StarCraft AI Competition, this session explains how Monte-Carlo Tree Search (MCTS) works and how it has become a viable tool for AI agents in a wide variety of games.