As the core systems of Total War have been established and redefined in the franchise

- a point I have discussed in the first two parts of this series - there is always a need

to strive for better. RTS games continue to be one of the most demanding domains for AI

to operate within and as such we seek new inspiration from outside of game AI practices.

With this in mind, I will be taking a look at 2013's Total War: Rome II - one of the

most important games in the franchise when it comes to the design and development of

AI practices. So let's take a look at what happened behind the scenes and what makes

Rome II such a critical and vital step in Total Wars future progression.

In part 2 of this series we concluded with an overview of the dramatic changes to the

underlying AI systems in Total War with the release of Empire, followed by Napoleon in

2009 and 2010 respectively. What was once a more simple and more manageable state-driven

and reactive AI system had made way for an adoption of the Goal Oriented Action Planning

system. A technique popularised by First Encounter Assault Recon. The GOAP implementation within

Total War was ambitious but struggled on launch with Empire, requiring patching and updating

both post-launch as well as in the following year's Napoleon. The same AI tech was adopted

in 2011's Total War: Shogun 2, with it proving to be a less challenging experience for the

systems involved. Shogun 2 returned to Japan, which provided a much more balanced mix of

ranged combat and melee, with less emphasis on gun-driven combat. Even the campaign AI

didn't struggle with the same problems as Empire and Napoleon, with a smaller and less

chaotic structure. But while it seems Creative Assembly was becoming content with the combat

systems, the campaign AI still needed more work. This resulted in some significant changes

under the hood during the Fall of the Samurai DLC for Shogun 2, which among other things

includes the naval warfare of Empire and Napoleon. One of the new problems this creates for players

is that the army and naval logic were until that point separate, meaning the AI needed

to be rewritten to consider how naval strategy could influence ground troops, such as being

bombarded on the coast line. At that point, the campaign AI's planning approach couldn't

foresee these issues well enough and was often stuck being reactive in its planning process

rather than deliberative and forging ahead on its own ambitions.

To resolve this, a new campaign AI system was prototyped in Shogun 2, which was later

expanded to create some rather seismic changes in Total War: Rome II.

2013's Total War: Rome II was a return to one of the most well-known entries in the

franchise, but with it came a rather seismic change for the campaign AI under the hood.

The drive for a more deliberative system that could consider the overlap between mechanics

resulted in a growing number of sub-systems responsible for individually managing the

budgeting of money, conducting diplomacy, selecting tasks for attacking and defending

- be they attacking enemy forces or laying siege to settlement - deciding what issues

take high priority, figuring out how to navigate an army safely across the map, not to mention

managing construction and taxes.

All of these require the AI to consider the overall suite of resources it has at its disposal

and how best to utilise them. The system is still reliant on the belief, desire and intention

system mentioned in part 2, but now the sheer number of combinations here are staggering.

Even if the system has decided on a smaller subset of tasks it wants to complete in a

given turn, there are still tens of thousands of different possible outcomes for that one

turn. The map for military deployment is quoted to have around 800,000 individual hex points

alone. How can the system hope to approach this sort of task at this scale?

The answer comes in the form of Monte Carlo Tree Search: an AI algorithm that had recently

taken academic research by storm and is making big waves in general intelligence AI research.

MCTS allows for the system to consider all of the different possiblities, explore the

ones that seem the most fruitful but also continue to consider alternatives. In time,

those alternatives might yield some strong outcomes, so this system is able to keep doing

things it knows are good for it, but also consider other opportunities along the way.

Now before we get into the meat of how the campaign AI in Rome II is managed through

MCTS, I need to take a moment to talk about how the algorithm works.

Monte Carlo Tree Search is a type of reinforcement learning algorithm: a branch of machine learning

algorithms that look at a problem and find good decisions by considering all possibilities,

while largely focussing on the ones it finds to be most useful. This is really useful when

you have a problem that is incredibly large and has a large number of possibilities, given

we might find a good decision to make, but we can't say with any certainty it's the best

decision. In order to have a better understanding of whether there are better options to take,

we need to consider alternatives periodically and see if they would be more useful. This

is known in reinforcement learning as the exploration/exploitation trade off. We want

to exploit the actions and strategies we have found to be the best, but must also continue

to explore the local space of alternative decisions and see whether they could replace

the current best. This is a difficult process to resolve, given that sometimes we need to

really explore a series of decisions to discover that an action that might look bad now, might

actually prove to be a really good idea somewhere down the line.

This is what MCTS does best: it explores all potential options for a given decision point,

isolates the best ones and then dictates which one is the best, both considering it's short

and long-term ramifications. The key component of MCTS the ability to run

a playout: where the AI effectively plays the game from a given starting point, all

the way to the end by making random decisions. Now it can't actually play the game to the

end, so MCTS uses what's called a forward-model: an abstract approximation of the game logic

that allows it consider the outcome of playing action X in state Y, resulting in outcome

Z. The algorithm gathers up all the decisions it can make in a given state of the game,

then runs thousands of random playouts across them in a structured and intelligent fashion.

It gathers data from each of these rollouts and concludes the process by selecting the

action that had the best rollout score. It's both incredibly powerful and strangely stupid

in its execution.

The smart part comes in how each rollout is decided upon and executed, to do this it relies

on four key steps: selection, expansion, simulation and backpropagation.

Selection takes the current state of the game and selects decisions down the tree to a future

state a fixed depth down the tree. Next up comes expansion: provided the state

we reached didn't end the game (either as a win or a loss), we expand it one step down

to and simulate the outcome. Simulation is the random playout phase: it

plays a game of completely random decisions from this point until it reaches either a

terminal state (where it wins or loses) or a simulation cap is reached. It then gives

back a result of how well it performed as a score. This is passed to the backpropagation

phase. In backpropagation: we update the perceived

value of a given state, not just to the state we ran the rollout, but every state that led

to it. So any score - be it positive or negative - works its way back up the tree to the starting

point.

Through those four phases, we can take decisions to a fixed point in the tree, simulate their

outcome and then propagate back the perceived value of it. Now doing this once isn't enough,

you have to do it thousands of times and balance which playouts to make. Different MCTS algorithms

balance it out so they shift focus to different parts of the tree periodically to ensure there

are no better solutions to be found it didn't otherwise spot. But once the playout limit

is reached, it's done and takes the action leading to the best scoring state.

What makes this system even more powerful, is that it's what we call an anytime algorithm:

meaning that it will always give an answer regardless of how many playouts we let it

take. So in a context like a game, where CPU and memory resources are pretty tight, if

it needs to stop evaluating the game at a moments notice, it will still give the best

answer it could within that time. Despite this, giving it a massive amount of CPU resource

won't result in godlike AI, given the knowledge accrued from repeatedly running playouts eventually

levels out.

Alright, with all the science out of the way, how does this all work in Rome II?

First I need to explain how the Rome II campaign AI manages itself. It's broken down into three

chunks: pre-movement, task allocation and post-movement.

- Pre-movement identifies threats and areas of opportunity for the player. It also budgets

resources, conducts diplomacy and selects skills for armies.

- Task allocation is conducted by a highly complex Task Management System - which is

the focus of the MCTS. The task system handles armies, navies, agents and actions related

to diplomacy. - Lastly there is post-movement: once all

units and such are moved and decisions made, the AI will then focus on construction of

buildings, setting taxes and technology research.

MCTS is responsible for managing two critical components of the task allocation systems:

the distribution of resources such that the AI can approach different tasks it wants to

complete and the execution of specific tasks. The tasks themselves are driven by a variety

of different task generation systems with their own focus or perspective. So while there

is a task generator for armies, there is also once for navies, diplomacy actions and much

more. The thing is that there are often way more valid tasks to execute than there are

available resources: the actual units on the map and money to spend. As such, the system

then prioritises which tasks it would complete by selecting the most viable and then allocating

resources to them.

In addition, task viability also carries some filtering to stop it trying to do anything

too stupid, such as removing actions that could cause diplomatic tensions, filtering

actions that could impact long-term strategies and also factoring what it had done recently

so it avoids contradicting itself. Once filtered, the tasks are then assessed using the MCTS

algorithm to grade their effectiveness and priority. With the best and more desirable

looking opportunities graded a higher priority.

After this, the MCTS is called on again in order to run resource coordination: or rather

now that it knows what it wants to do, it still needs to figure out how exactly to do

it. As such, once the system has made some approximations of appropriate targets and

their locations on the map, it will run more MCTS approaches on army movement and army

recruitment. Factoring the makeup of its own forces as well as the opponents in order to

determine where best to move current forces, as well as what types to recruit for future

turns.

In each case, the MCTS is limited such that it doesn't search all the way to the goal,

given that Total War as a game is so large that it would take too long for it to simulate

completing the game. In addition, the game is complex that simulating that far out won't

yield any useful outcome. In fact, it was quoted that the system is only capable of

looking one turn ahead before starting random playouts due to the complexity of the game.

Given the nature of Total War, the MCTS can only exhaustive search the entire state space

for the best action during the opening turns of the game. Over time the number of possible

states grows exponentially, to a point that it is simply beyond the algorithms reach.

Despite this, the anytime property of the algorithm ensures we will still get a useful

and intelligent decision from the system.

Rome II launched in September of 2013 to a largely positive response, but with a few

problems. Most notably, the campaign AI took quite a long time to make its decisions in

the launch build: taking several minutes to conduct campaign movements that most players

conduct in a minute or two, resulting in aggressive patching of the game for several weeks after

launch. In time this led to a noted improvement in campaign decision making that was received

favourably (though not univerally) among fans and critics.

Revolutions aren't easy, nor are they clean and the legacy of Total War: Rome II is no

exception. But it is nonetheless a major milestone for the development of AI systems and practices

in the commercial video games and has led the way for many a successor that is seeking

to adopt MCTS as part of its own AI toolchain. MCTS is a hot topic in contemporary AI research

and has shown many useful applications in fields of expert play and general intelligence.

To learn more about how it all works, be sure to check out the AI 101 on MCTS here on AI

and Games.

Thanks for watching this third entry in the AI of Total War. In part four, I'll be looking

at how the MCTS implementation was improved in Total War: Attila, combined with a deep

dive into just how exactly does the diplomacy AI work in more recent iterations of the game.