OBJECTIVES
Our AI components are available for licensing. What you get is a proven AI to drive your game in a short time frame.
The primary objective is to create an advanced non-cheating AI for a premier strategy game, Heroes V, and to develop it to new heights, particularly in respect of replay value and the experience of the player. A secondary objective is to demonstrate to developers worldwide what benefits this truly has for a game, and why it enhances the user experience substantially and adds value to many other game elements.
This part of the project is a full rewrite of the AI inspired by the spirit of H3. It is meant to give the strategic gameplay of H5 a boost by playing against dedicated AI opponents who know the ropes. This AI does not cheat, on higher difficulty levels the only advantage it has is the lower starting resources for the player. During further development many more advanced difficulty levels are planned, and the capability to have the AI adapt dynamically to the skills of a player, to provide newcomers and veteran players alike with a fair challenge. The idea is to give all the chance to win the game with their present skills and to challenge their wits.
Technically, the AI runs in its own dedicated process and consists of many advanced components, for example an ultra-fast hypercube pathfinder, advanced lookahead opposition tracking and multi-pass strategic balancing amongst others. An adaptation of the AI for other games is possible within a short time frame.
MOTIVATION
There are so many examples of strategy games out there that have a promising setting and design. But it's very hard to find a good game that gives you a truly fair challenge. There are all kinds of cheats to increase the difficulty, extra space ships, extra population growth, extra creatures, you name it. As if the companies behind these games couldn't do any better, as if it would be impossible to create a good AI that can match a skillful strategist's wits.
Having gone through this effort with this AI mod for H5, I am fully aware that this type of work is a real challenge for many developers. It's not only about designing artifical intelligence, it's just as much about processing speed. The amount of preprocessing the AI does is insane. It was one of the main challenges to get the preprocessing even on a huge map done within a maximum time frame of 30 seconds. Most of this is done by highly optimized routines that fit all data into the processor cache to gain a factor of 5 - 10.
Another example is the pathfinder in the AI mod that is capable of looking up the shortest path between two points in nearly constant time, thus enabling the evaluation of milllions of alternative paths in a second, which in turn is critical for reaching good lookahead depth. Given all the complex rules for the terrain in H5, monsters blocking paths, not to forget teleporting and ship building/boarding, this is no small feat. Many developers think that the computing requirements for turn-based games are low. Far from it, this pathfinder had to be faster than what is typically required of a real-time strategy game.
That is one, probably the biggest reason, that good examples of turn-based strategy games that get it right are rare. Master of Orion II is my favorite one. The chess computer program Fritz counts as well, even if it is technically a board game. Fritz is an important achievement because it has proven that a computer AI can be a match for world champions.
In the end strategy is about the balance of power and what you can achieve with a given leverage. If the AI cannot hold its own and contest the player's forces, the challenge is a shallow one indeed, not necessarily easy, more like grind work and lacks the elegance of strategic mastery.
On the other hand the formula of the Heroes games had me always coming back again and again after a while of abstinence. As such it was a natural target for me, to have these two elements join, the addictive gameplay of the Heroes franchise with an AI that can give it depth.
That is where we are now. For me, this AI is a first step into the right direction, sort of a prototype that still needs to be developed to its full power.
But I am also aware that it is the content that makes a strategy game live and breathe. Map making is an important part of it. And again the AI can help us in this effort. Advanced tools can interactively provide feedback to the map designer, how the landscape and objects on the map affect the strategic balance of power and its leverage. Maps that are designed around an inherent balance of power where two or more sides contest strategic locations and resources by skill.
Quantomas (AI programmer, scientist, inventor)
AI INNOVATIONS
AI Logic
The AI evaluates all possibilities that can occur on the map for a given number of lookahead days (turns). It begins with the hero start position and examines all actions the hero can do, movement on the terrain, visiting towns and other structures, combat with neutral creatures and enemy heroes etc. All possible positions at the end of the turn are compiled into one list. Each position is then used as a start position for processing all possible actions in the next turn to arrive at all possible positions at the end of this turn. This process is repeated for turn 1, 2, 3 and so forth until the maximum number of lookahead days is reached.
The effort for the computation of all possibilites grows typically exponentially with the number of processed lookahead days. This is further exacerbated by the fact that the gameplay rules allow for new heroes being hired every turn and that many features on the map are updated dynamically. The computation requirements even for a modest number of lookahead days, for example three, is gigantic.
To keep the evaluation of all possibilites manageable the AI uses an intelligent pruning algorithm which eliminates inferior action sequences and limits the number of possible start positions that are carried over from one turn to the next. Even so, the number of possibilities and the computation required is enormous. The AI employs a fair number of innovative optimizations that in combination with preprocessing and reusing as much information as possible, give the AI a lookahead range that is so far unmatched in any advanced strategy title.
The AI is required to do much more than processing the actions the heroes can perform on the map. The real challenge is to balance the actions of all heroes of one player against the possible actions of all opposition players.
The AI performs a four pass strategic balancing. It first evaluates an offensive strategic approach for each player. Second, a defensive approach for each player is evaluated. Third, a balanced strategy based on the needs of each individual player is computed, i. e. offensive and defensive actions are carefulled weighed against each other and the best strategy is selected, which often has the heroes select paths that enable them to fulfil offensive and defensive roles simultaneously as best as they can.
The fourth pass compiles the weighed optimized behaviour for each player to arrive at the most likely prediction of the course of action, and the actions that are most beneficial to take.
The quality of this process of strategic balancing depends largely on how accurate the AI can evaluate the strategic value of actions. Humans have an intuitive understanding of the strategic value of most actions. In contrast a computer has to get down to counting things and numerically evaluating the strength of actions.
The AI uses an algebraic factorization to produce the knowledge needed to assess all actions. In short, each rule and impact is factorized. For example, the AI "knows" that armies are comprised of creatures and that each creature does a specific amount of damage. It also knows that it requires time and resources to hire creatures. It knows about the costs for buildings, the resources required, and how to obtain them. It knows about terrain movement costs, and how much time heroes need to reach a goal.
All in all, this provides the AI with the intelligence how things work. If this is implemented accurately, and combined with the natural strength of a computer to count things, it gives the AI excellent strategic insight.
In general this AI architecture is not limited to turn-based games. It can also be employed in all kinds of real-time settings.
Comparison with H3, H4 & H5
The original H3 design
H3 used a hybrid design that merged the pathfinder and the AI into a single unit. The pathfinder processes the terrain movement cost for each tile the hero moves on the map and associates the sum of the values of the tiles visited with the computed path. The value of a tile is determined by the action that the hero can take there, for example visiting a structure, hiring creatures, combating neutral creatures or heroes etc.
In this way the AI can determine which path has the greatest value. The processing simply employed the pathfinder to check all possible paths over all tiles within reach. The current value of a path is the sum of the values of all tiles visited. Every time the pathfinder moves to an adjacent tile, it computes the updated value of the path. This path value is stored in the tile unless there is already a better path value in it. If the path value is inferior, the newly computed path to this tile could be terminated and discarded.
This is a simple and effective algorithm to determine the best path. The values of actions are numerical values that are the result of an extensive tuning process that applied to resources, skill enhancements, combat boni and scores of different actions the hero can take. The quality of the tuning process 3DO applied to balance the numerical values of actions against each other is unmatched. It is a technological marvel, the path selection for the heroes produced a nearly humanoid intuition.
Layered over the path selection was a threat check, that made heroes aware of stronger opponents nearby. Taking into account the pathfinder computation depth and threat layer, the AI had effectively a lookahead depth of 3 days (turns).
The strength of this approach is a faithful application of the gameplay rules. Because the pathfinder uses an incremental computation, fog of war and exploration into the shroud as well as the actions on the map work naturally without further AI modelling.
One weakness lies in the computation cost. Because the terrain movement rules are complex, extending the lookahead depth of the AI would cause spiraling computation costs. A second weakness is the required tuning. If the gameplay rules are modified, the entire tuning of the action values has to be revisited.
What broke H4 and 3DO
H4 mainly used the same AI as H3. But the gameplay rules had been modified. In particular the AI didn't make sufficient adjustments to adapt to the newly introduced movement range of neutral creatures. The result was that on higher difficulty levels with stronger neutral creatures the AI heroes died too frequently on the map. A player could then visit the supposedly AI controlled regions and find only the tomb stones of died heroes and underdeveloped towns.
It is unlikely that 3DO wasn't aware of this issue after the beta test. It is more likely that 3DO assumed that only a small minority plays the game on high difficulty levels, and gambled that they could get away with releasing the product in this state.
Limitations in H5
H5 essentially returned to the roots of H3. The magic system was revised, the powerful town portal and dimension door spells were better balanced and the Summon Creatures spell was introduced to facilitate faster in-game development. The hero skills and the structures on the map underwent also a number of changes.
While it is true that the H3 AI design does not require AI modelling, the tuning of the numerical values that represent the strategic value of actions on the map would need a revision. Considering how masterful the balancing was done in H3, it would have required a major effort or genius programmer to rebalance the AI values for the modified H5 gameplay rules with the same mastery.
It is evident that the developer decided, that the best course of action was to stick with the H3 balancing. The result was that the AI heroes on the map would behave unpredictable from time to time.
To mitigate these issues the lookahead range of the AI was tentatively increased by having the pathfinder process more tiles for an extended movement range. Because extending the tiles for an extended movement range causes an exponentially spiraling computation cost with the given design, this approach was limited to an additional 0,5 to 1,0 lookahead day (turn).
Even with this limitation, the lookahead extension made the pathfinder and AI very slow once it reached an open area, in which lots of adjacent tiles would need processing of a high number of permutations over potential paths. To counter this, the map generator was revised to produce regions that were typically linked only by narrow passages.
All in all the AI strength was significantly hampered and processing speed could be very slow. To offer the player a challenge, the campaigns made use of spawning armies by a script or prepopulating the map with strong opponents. While this is possible it changes the nature of the game.
Prototype AI features
The prototyped AI is very fast and processing speed does neither degrade on large open areas nor huge map sizes. The currently implemented computing depth is eight lookahead days (turns). The lookahead depth can be adjusted dynamically based on the strategic situation to produce ultrafast response times or allow for a more in-depth analysis and strategy.
The AI can dynamically adapt the challenge rating for the player. The quality of the AI decisions can be degraded gracefully and the lookahead range adjusted. The AI can measure the performance of the player in combat and the strategic leverage of resources and forces, and adapt its own strength if this is desired. This feature allows for a product that challenges players of all strengths to the limit of their wits, newcomers and veterans alike, and giving each the opportunity to complete a mission successfully.
There is no need to tune numerical values for hero actions on the map. Instead the AI uses an algebraic factorization of all gameplay rules. This is less error-prone and considerably easier to maintain.
As an additional advantage the algebraic factorization can also be used reversively. It is possible to analyze the gameplay rules in their entirety and to determine how strongly each gameplay element contributes to strategic success. In this way undue over-accentuation of individual gameplay elements can be identified and the rules rebalanced.
The inherent logic in the algebraic factorization can also be used to analyze the challenge ratings of maps. If implemented correctly, this tool can greatly aid the design of maps and the random map generator. E. g. if a gold mine is placed next to a player's start position, or native creature dwellings are in close proximity, this tool shows the added strategic leverage for a given player. The landscape and structures on the map are taken into account.
All in all this AI allows for a beautiful strategic contest, in which the strategic strengths of each player and the strategic features of the landscape become core elements to explore and conquer.
DEVELOPMENT COMPLETED
Compared to H3 which had merged the AI with the pathfinder, if the AI were to achieve higher lookahead ranges it was necessary to implement an advanced pathfinder and separate AI logic.
The pathfinder implemented in the prototype is highly innovative in its own right and is capable of estimating distances very fast and producing accurate measurements with only minimal additional effort. It has a near constant computation time and is capable of processing millions of paths as an input for the hero turn progression in a second.
The hero turn progression is implemented in full for a lookahead depth of eight days (turns). The full turn progression for all players on the map inclusive the four pass strategic evaluation is also implemented in full.
What is still implemented only rudimentary is the logic for the strategic balancing. Currently, the strategic evaluation at the end of lookahead day 8 is simply a qualified count of the castles, heroes, forces and resources. This will be replaced by a full strategic evaluation based on the algebraic factorization.
The current build also has a number of smaller limitations that are explained in the next section. Once the strategic balancing is implemented in full and the limitations are resolved, the AI will perform fully to the specified features.
The AI is fairly aggressive as was the AI of H3, and capable to stand its ground against veteran players. In the present build it does not use the Summon Creatures spell, but tasks the heroes with reinforcements. There are a number of patterns that emerge naturally in how the heroes collaborate with each other to reinforce themselves and to capture the buildings and resources on the map. For the most part this stage performs beautifully.
The way for a veteran player to defeat the AI is to outmaneuver the opposition and to strengthen the own position gradually by gaining access to castles with the same troop types to build a stronger force in the end. This is a result of the missing strategic end stage, and once the strategic balancing is in place this will no longer be generally possible.
ADDITIONAL INFORMATION
As the AI prototype gets further fleshed out, particulary when the algebraic factorization is implemented in full, more documentation will follow.
In the meantime, if you are interested in studying the details of the AI, check out the log files the debug build produces. These detail a good deal of how the AI partitions its data structures and does turn processing. Try a small map because otherwise the log files can get very big. The debug build also has an enhanced minimap that shows the area states the AI uses to optimize its computation internally.