Where we start
Nearly 15 years ago the computer strategy game Heroes of Might and Magic V was released to the public. For a fan of Heroes of Might and Magic this was an exciting time, because the original developer of the revered Heroes of Might Magic III, New World Computing, had ceased to do business a few years earlier. It was only after Ubisoft acquired the IP that fans could look forward to a new promising game in the series.
Once I started playing Heroes V I realized that its developers had put in a tremendous effort, even to the extent to address known flaws of Heroes III. Everything looked very promising indeed.
But I couldn't help to note that Heroes V introduced its own flaws, particularly notable on maps that replaced strategic gameplay with scripted AI behaviour. Unfortunately, after having played many maps it became clear to me that the AI behaviour was the weakness of Heroes V. It was truly a shame, because the game did so many things right, to see it not reaching the heights it could. So I decided to contact the producer of Heroes V and offer my help to develop a quality AI.
Many years later a lot has happened, including the release of my AI mod in 2011, which was a good improvement but an unfinished prototype. In the years since 2011 I have worked on researching groundbreaking AI techniques, and last year I began to complete what was left unfinished in 2011.
Technically, the AI released most recently, v3123, is a milestone. It incorporates tech that hasn't been used ever in a computer game, with the aim to make Heroes V the #1 strategy game for players who seek to play against strong AI opposition in a rich and varied open strategy game that goes all the way from resource management to base building to army management and winning a game through smart maneuvering and strategic leverage.
While I have pioneered many advanced AI techniques over the years, the most recent universal sequencing improves the AI decision making to a level that wasn't possible before. It gives the AI finer granularity to make decisions that adapt to the context. Conventional techniques used for AI in games typically use predefined or attractor values to get AI opponents to act. It is obvious why this leads to rough behaviours not adapting correctly to the current strategic context. In contrast universal sequencing determines its values dynamically from the lookahead, i.e. what the AI can do and what its opponents can do. In principle this is recursive, because if you track a lookahead path, you have to account for what your opponents can do, and again the opponents paths depend on what you can do and so on. It is similar to complex differential equations. Universal sequencing solves this and gives the AI a profound understanding of the value of its actions, which in turn leads to a highly adaptive and refined behaviour, and to gain leverage without cheats.
Initially this is used by the AI to develop its towns, the bases in Heroes V, much more efficiently. In principle you have to maximize the power of the creatures you recruit in the towns. But the situation can differ dramatically. It can be a scenario with scarce resources, where you need to spend the resources you have wisely. Or where it makes sense to build a tavern first, to gather the creatures from a secondary hero. It could be that you need to build a marketplace, resource silo or town hall fast. And sometimes it simply makes sense to build your dwellings and castle as fast as possible. Sometimes you can afford upgraded dwellings. Sometimes not. And you have to make sure that you have enough gold on hand to recruit creatures, because they don't come for free.
You will be surprised how big the difference is in practical terms, while playing against an AI that KNOWS this. But universal sequencing is a big upgrade for more reasons. Upgrading the way the AI builds up its towns is just one aspect.
Universal sequencing, as the name suggests, is truly universal. We start with the town buildings. The town buildings need resources. The resources, and buildings that produce resources, are acquired by heroes moving on the adventure map. As each faction can have multiple heroes, there needs to be a coordination between all heroes. Finally the heroes have to recruit creatures from the towns and to go out to conquer the territory of the other factions, taking their resource buildings and towns.
So beside accounting for the available resources and income per turn and choosing appropriate buildings for the available budget, we use universal sequencing to generate the values that inform the heroes while they go about their business to acquire the resources needed to build up their faction's towns.
On the next higher level, to coordinate the actions of all heroes of one faction, we use universal sequencing in a different way. While it is clear how to generate a value for acquiring a pile of resources, projecting a path for all the actions a hero can perform over multiple turns is much more complex. The order of the actions matters, the timing can matter, and there are overlaps between the actions different heroes can take. Some actions can only happen once – who will do it? –, others require another action to be performed as a prerequisite. This is where universal sequencing shines, by processing the possible sequences of actions each hero can take, and sorting out the best order of actions for all heroes. It aligns their actions so that they act with one common goal in mind, to improve the power of their faction. Practically all this starts with the creatures you can recruit and that again depends on what you build in your towns, and yes this depends on the resources you can allocate.
You may have guessed it by now, this goes further up. On the next level, we look at the AIs for every faction as a strategy player, who competes for resources, builds smartly and then uses his forces wisely. Universal sequencing is used here as well, to determine possible sequences for what all factions can do, as the actions of all factions are interspersed. Each faction gets their turn in order for each day of the game. The situation is more complex than the alignment of the actions of the heroes of one faction, because each faction also can impede and prevent the actions of its opponents, either by its own actions on the map, or by eliminating opposition in combat. Universal sequencing takes care of this by looking at the threats heroes and their actions pose, in order to determine leverage. It is not only a question who is stronger in a potential combat encounter, leverage can take many forms. If you do that, I can do that. It is a complex give and take. For example you can threaten to approach an important town of an opponent, and he may feel pressured to defend it, but he could also go for one of your towns instead. It becomes more complex, if multiple valuable actions lie along the path of one hero, and if multiple heroes can coordinate their actions. This is the beauty of Heroes of Might and Magic. It is a complete strategy game.
It is also noteworthy that this is a non-cheating AI. It plays according to the same rules as you. In the case that you loose to an AI on a map, turn the tables around by starting the map in reverse positions and observe what the AI does differently than you. You can gather valuable insight from this, what to do in which order, what to build in which order. The timing is equally important. Does the AI capture sawmills and ore pits early? When does it break out from its starting area? What creatures does it have at this point? What kind of losses is it prepared to take?
Regarding the design of the AI, a technique like universal sequencing will not work on its own. It requires a powerful lookahead to arrive at the variants that are evaluated, hence a highly efficient pathfinder is a must. The efficiency of the system results from the intelligence to know which variants to evaluate and to process further.
If you are new to the project you find the AI mod in Downloads. You can try it out and compare it to the vanilla AI. Note that the vanilla AI uses heavy cheating like free resources and double creature recruitment. It is at least questionable to what extent a game is still a strategy game if it doesn't apply its rules equally to all players.
Please note that the current download is work in progress that is continuously upgraded. The AI uses universal sequencing for planning its town buildings since v3123. Work goes on to upgrade the AI further along the route described above. If you like you can observe how it gets stronger step by step and read about the changes and tech here. The next big upgrade is the combat AI.
The current AI is already worth playing against. It is much more formidable than the vanilla, faster and of course works without cheats. It has already crossed a large distance for the genre to make a step forward, because a good AI is of paramount value for a great strategy game.