In 2006, an algorithm called Monte-Carlo Tree Search (MCTS) was discovered independently by researchers in artificial intelligence. It combines the exhaustiveness of breadth-first search and the benefits of random sampling together into one search technique that's well suited to making tradeoffs of how it uses computation time to find optimal solutions. Over the years, users have found great success with various board games such as Go, outperforming all other approaches.
This year, MCTS finally hit the AAA games industry, specifically thanks to Creative Assembly's TOTAL WAR: ROME II. At the Game/AI Conference 2014, which took place a month ago in Vienna, Tim Gosling and Piotr Andruszkiewicz explained in more detail how the algorithm was implemented and integrated into the high-level campaign AI for the Roman-themed strategy game.
While the MCTS algorithm is interesting in itself, it's not a good enough excuse to give to you producer when you want to apply it to a AAA game! Why did the AI team at the Creative Assembly attempt to use this randomized search-based technique?
- Random By Design — Unpredictability is sometimes welcome from a game design perspective for replayability. The player doesn't always want to face the same army compositions.
- Avoid Bad Decisions — The brute-force stochastic searches allows the AI to avoid mistakes more effectively since many different options are tried and statistics don't lie. :-)
- Computation Budget — MCTS is capable of making great use of computation to find a balance between "exploring" new solutions and "exploiting" its known best solutions. The algorithm can stop at any stage.
In TOTAL WAR: ROME II, the implementation of Monte-Carlo Tree Search was rolled out incrementally, starting with one well suited problem and expanded out once it proved successful. But how does this fit into the big picture of the AI and the game engine?
Architecture: Divide and Conquer
The Campaign AI of TOTAL WAR: ROME II is built around the observation that the problem is unsolvable if all inter-dependencies are considered. It involves hundreds of regions, units, dozens of buildings and coordinating the diplomacy, technologies, skills, legacies, edicts of each faction...
The solution is therefore built as independent decision making modules that communicate together:
- Task Generation — High-level goals, each with require resources, are created as the collective result of multiple simple "generators" (not MCTS).
- Resource Allocation — Matching resources (few) to tasks (many) taking into account diplomacy, strategy and the previous allocation (using MCTS).
- Resource Coordination — An MCTS-based planner determines the best set of actions given resources and their actions.
To support these modules, there's another system that provides strategic context by querying the state of the game and preparing relevant information. Also, other systems are built to complement MCTS, such as a budgeting algorithm that helps prevent conflicts.
On the implementation level, the code itself was written in C++. Data-structures are carefully crafted for better caching (tree structured), and a stack allocator is used for nodes to reduce dynamic memory allocation costs. These are best practices for implementing planners or path-finders, and applying them to MCTS is particularly critical as tens of thousands of search steps may be performed each invocation (hard limits are imposed on the search.)
Unlike previous iterations of the Total War franchise, ROME II has a clearer separation between the AI and the game through interfaces. This provides good opportunities for preparing and caching data as necessary. Additionally, MCTS typically operates in its own simplified copy of the game state rather than the fully fledged data-structures.
MCTS is applied in multiple places within TOTAL WAR: ROME II, and the implementation provides data-driven controls. This is obviously necessary to make it possible for designers to balance the game and make sure the AI still works! However, the AI still requires some expert insights to make it run efficiently enough...
While MCTS works relatively well (compared to other search-based AI algorithms) without domain knowledge, it performs much better given additional guidance. TOTAL WAR: ROME II does this in multiple ways:
- Aggressive Pruning — Search algorithms can be told to ignore entire branches of the game tree. In this case, rules specific to the campaign AI were hard-coded to prevent wasted searches.
- Eliminate Duplication —Simply discarding duplicate or similar options in the game tree can also provide more advanced forms of pruning. (Results from previous searches could also be reused.)
- Soft Restrictions — Since MCTS also relies on so-called "policies" to guide its expansion of the tree and the random simulation, it can also be influenced by adjusting floating point scores too — biasing the search in certain directions.
Of course, the entire architecture for MCTS in TOTAL WAR: ROME II is designed with domain knowledge, so the concept of divide and conquer is by far the most important for getting performance and results out of the system.
For those of you interested in watching the original presentation by Tim and Piotr from The Creative Assembly at the Game/AI Conference, head over to The AI Sandbox™. The video recording is available (free) as part of the launch next week, so be sure to check it out!