AI in strategy games
(first published on indiedb.com)
Strategy games are naturally about contest. You have to do better than your opponent(s). Many great PC strategy games have build upon this formula and gifted us with an incredible range of scenarios from history, science-fiction and fantasy.
The core is always the same though. It requires well-thought-out mechanics and a means to make conquering the opposition challenging. How well this is done determines the long-term appeal of a game for a strategy gamer.
There is a whole range of well-known franchises like Sid Meier's Civilization that simply accept the notion that to offer challenging gameplay to strategy game veterans requires boni, or cheats, for the AI opponents. However, if you come from a background that values fair competition, either from multiplayer games or classic boardgames like chess, you perceive cheating as a lack of persistence. It breaks the game into different parts that adhere to different rules. It is not impossible for a game to get away with this, but for its long-term appeal it matters how seamlessly a game integrates such modifications into the game proper.
Amongst the many strategy games I played, including grand strategy games like Civilization and Age of Wonders, but also real-time games like Homeworld, Distant Worlds and Starcraft, there are only a scant few that I remember for its good AI. Interestingly these games also stand the test of time rather well.
The first one is Master of Orion II. Besides being an engrossing strategy game, it is smart in the way it sets up each game. Its centerpiece is the way you customize the race you are playing with. It uses a point-based system that lets you pick racial traits, which determine how strong your faction is. Here MOO2 shines, it employs this feature to grade the difficulty of games. On higher difficulties the AI factions simply get a few more points to choose traits. While playing it feels natural, like you encountering a race that is a bit more intelligent, or physical tougher, or has a knack for engineering. These traits are random (within reason) and help to make the game feel whole. Combined with a rock-solid turn-based AI that plays by the same rules as you, it offers infinite replay value.
The second one is Heroes of Might and Magic III. It has a wealth of mechanics that all tie logically into each other. Its rules govern how you collect resources, how you build up your towns (which function as bases), how you hire your troops, how you shape your leaders (the eponymous heroes), and ultimately how everything comes together in turn-based battle. What gives it long-term appeal is that the AI uses all these mechanics just the same way you do, based on the same rules.
The interesting question here is whether there is a common core that gives these two revered strategy games its appeal. I believe so, but rather than presenting you with a theoretical discussion, I would like to share with you a grand AI experiment I am conducting for some time.
Some years ago Ubisoft kindly provided me with the opportunity to rework the AI of Heroes of Might and Magic V. It shares a lot of its DNA with Heroes III. Needless to say, this work yielded a lot of lessons.
Lookahead and pathfinding
At the heart of a grand 4X strategy game is naturally the concept of distance to give you space to explore and expand. Real-time strategy games like Homeworld and Starcraft tend to be more tactical, mostly a game about tipping the balance. This plays an important part in 4X games as well, but their strategic features depend to a large degree on the layout and distances of the major objects on the map. Heroes of Might and Magic sits historically on a middle ground, it can do both well.
In terms of AI distance means lookahead and pathfinding. Game design matters a lot here. In MOO2 battles between fleets can only happen in star systems, which means that pathfinding is reduced to tracking the distances between all major objects and the time it needs for fleets of different speeds to arrive there. It gives rise to a beautifully clear AI design that tracks the leverage each faction has on the star systems in its reach. Lookahead is mostly concerned with tracking what you can build and dispatch in any given time. This is not trivial though.
On the other hand Heroes games are on the opposite end of the spectrum. The adventure map is divided into tiles, each of which presents a possible position for adventure map objects and heroes and their armies. It even goes as far as having different types of landscape with different movement constraints, for example swamp vs grassland, that in turn can be traversed at different speeds by different creatures and heroes with different skill sets.
In order to arrive at the leverage that the armies project on the map, you need a powerful pathfinder that tells you exactly how long you need to reach any given spot on the map, either to access an object or to intercept an opponent.
This is were Heroes III shines. The game has technically AI logic for each object on the adventure map and visiting it constitutes an event. The task of the pathfinder is to arrive at logical sequences of events that the heroes can perform on the map. This is no small task. Heroes can typically travel around thirty tiles on the map each turn and the game is designed for a lookahead of roughly three turns, which means it has to look at paths spanning 100 tiles in each direction that each allow a hero to visit between 10 and 20 objects. The order in which these objects are visited can have a huge impact. In short the number of permutations is gigantic.
What made Heroes III successful is a pathfinder design that limits the number of evaluated paths to the more important ones. Its design in the last millenium was far ahead of its time and contemporary games have not come up with a solution of the same quality yet. In a way it is a crucial piece of AI development, but the know-how somehow didn't become mainstream in the way graphics innovations were cultivated. If you are designing an AI for a strategy game, I can only recommend that you look into priority queue based pathfinders that integrate AI logic smartly.
It has to be said that an AI lookahead of 100 tiles, or three turns, for Heroes III is limited in comparison to the lookahead and strategic planning human strategy veterans are used to. But combined with the rich set of rules Heroes has, which require a lot of thinking through, it is enough to keep the game challenging for most players until they reach a very high level of skill.
Experimental upgrades to lookahead and AI
It is a valid question to what extent a lookahead changes the playing experience.
If you reduce it to a low value, for example one turn, to make the AI processing faster, you clearly notice that the behaviour of the heroes becomes more rough, akin to what you typically expect from computer opponents, functional but you can clearly see it is not a human player.
If you have an eye for it, you can also notice the same issue in Heroes III with its default lookahead. The behaviour of the heroes looks much more like actions being performed on purpose, but if you look at the broader picture what matters strategically, you can notice clear deficits.
This is not just an issue that appears in strategy games, for example you can notice it in the tactical combat of the upcoming Solasta: Crown of the Magister or Pillars of Eternity. If you implement a low lookahead, or program it poorly, you clearly notice that the computer opponents act rather inflexibly or erratically. There are many ways for a game to cover this up, but in general I recommend that you at least familiarize yourself with how to implement an at least serviceable lookahead. It greatly enhances the appeal of your game.
Regarding the AI of Heroes V, I examined rather thoroughly what options we have available at our more modern PCs to extend the lookahead significantly. I initially succeeded to increase the lookahead to seven turns by optimizing the pathfinder, and later on developed new techniques to extend the lookahead to 21 turns.
It indeed refines the AI behaviour further, and allows for features like a better building construction in your towns and a more smart reinforcement of armies. But it doesn't improve the AI decision making regarding strategic priorities to the level a skilled human player has. Concepts like diversions and multi-pronged attacks, but also more simple notions like which troop types serve your strategic plan best. It isn't that you cannot implement good heuristics for it, but rather that the behaviour doesn't sufficiently adapt to the evolving strategic context.
The conclusion is there is more required than an outstanding lookahead, even if it can cover the entire map, to arrive at sound strategic decision making.
If you survey the map and make a strategic plan you typically note the distance between important objects, towns for example, what they offer strategically, e.g. generate troops, the location of armies and so on. This gives you an idea of the strategic situation, what you hold safely, what is under threat, where you can make gains, where enemies are located, whether they are stronger or weaker than you. Based on that you develop a strategic plan, what assets you develop, which fronts you defend, where your armies will advance, in short all the actions that you want to take short and long term, adjusted for the counteractions you expect your opponents to take. Essentially you plan an entire campaign to victory, or if this is not possible focus on the actions that have the best chance to strengthen your position. It is worth noting that you have to adapt your strategic plan continuously to reflect current developments.
This is the level where a strategy game becomes worthwhile playing.
If we want a strategy game to hold up to this standard, we need an AI that can develop strategic plans. This is technically an entire additional layer, but it needs to be noted that a strategic plan cannot be developed solely on abstract criteria. It needs to be based on the strategic reality. It has to take into account the whole range of game mechanics, similar to how a sophisticated deep lookahead determines what is possible by looking at each action. Only that the picture is much broader.
From an AI design point of view we are looking at a deep lookahead, possibly as far as the endgame, that only deals with the most critical variants. This is truly the next big leap for AI to gain this level of insight, to take in the situation and game mechanics and arrive at a sound plan to get the best outcome.
This is the work I am currently doing.
Aside from the adventure map logic discussed above, the Heroes AI has to deal with three additional major game elements.
Heroes, the leaders of armies, evolve as they gain experience and the skills they acquire can decide battles. This type of skilling can be done well or poorly and a competent human player needs considerable experience to do it well. Many of the skills heroes can obtain are dependent on the context and the types of troops they lead. Doing this well can make the difference between victory and defeat.
Secondly, heroes can obtain artifacts that provide valuable boni that often empower a hero's skills. Good multiplayer maps are typically designed in such a way that different factions have equal chances to obtain powerful artifacts. Artifacts are often acquired from well guarded adventure map sites, so it becomes an important part of strategic planning.
Most importantly Heroes resolves encounters between opposing armies on a tactical battlefield. Here all the different troop types with their traits, their numbers, as well as the entire range of skills and artifacts their leaders possess, come together in an ultimate test of strength, a battle of might and magic.
Needless to say, the AI has to do well in all these areas.
But more importantly these features make Heroes V a complete strategy game for me. I am interested to see how a competent AI without cheats fares against the best human players in a strategy game so rich in mechanics that you can prevail by creating the better strategic plan, even if the odds on the surface are against you.
As explained, the final stages of the AI are work in progress, but I would like to invite you to take part in the journey towards a unique strategy game, in terms of squaring off against competent AI opponents and in terms of a game rich in mechanics that all serve one common purpose: to prevail. If you are new to Heroes of Might and Magic, I hope my short presentation of its features makes you curious about the strategy game behind it.
You can try out the AI that is available as a free download here.
If you are just curious about the AI, its tech and design, I will post regular updates about the progress in this blog.
Essentially I would like to gather a community of like-minded people who are interested in strategy games and AI.
A lot is possible, developing Heroes V to a pinnacle of contemporary strategy games, as well as creating our own strategy game, possibly a truly worthy successor of Master of Orion II.
But the scope is much bigger. I admire promising ambitious indie games and when I read about them, I always imagine what they could be with an advanced AI. This isn't limited to strategy. Games like the upcoming Vagrus and Baldur's Gate 3 are as well on my radar. AI is versatile.