Algorithmic Intelligence

One feedback I got lately is that the explanation of Event Sequencing is somewhat on the theoretical side and a practical demonstration would have more value.

Yes and no. It is indeed an explanation on a conceptual level, as I do believe that expressing concepts clearly has value, so that you understand the fundamentals of the algorithms you write. However, Event Sequencing was already successfully incorporated into the 3.1j AI for Heroes of Might & Magic V, the core of which was written in 2008. So this was just my write-up of what exists already in software.

The feedback has merit though, as it points to a valid issue. There are by now a number of presentations, slides, blog posts, code samples and software, including the two versions of AI for Heroes V, so that someone beginning to read one piece has no idea how all these topics are interrelated. This is somewhat compounded by the fact that I haven't solved the issue how to present the AI without giving away too much of the internals, so I mostly stick to writing about proven but dated parts of the tech, like Event Sequencing, Heroes III pathfinding and such, and address newer developments fairly abstractly.

The reason for this is that the plan was all along and still is to present the AI in action, in showcases that ideally are hands-on and can be tried out on a PC. It shouldn't be long now, more about this in a bit, but it makes sense to give a brief overview what kind of documentation is currently available to give visitors an introduction of what tech the AI uses, what issues it solves, what state it has reached and what is currently available for interested parties.

Brief overview

Originally my work on AI started for Ubisoft on Heroes of Might & Magic V in 2007. This AI was intended as an upgrade for the Tribes of the East expansion and completed in summer 2008. As the developer Nival and Ubisoft parted ways at this time unexpectedly, the official support ended and the AI upgrade was released later as a mod with Ubisoft's permission. You can try this AI out by downloading the 3.1j mod and see how it changes the gameplay in Heroes V. It incorporates the original AI design New World Computing developed for Heroes III and turbo-charges it with optimizations that address fundamental AI performance issues, like Event Sequencing which moves from tile-based pathfinding to focusing on the most important interactions faithfully, that is without loosing detail.

In principle this is at the core of progress in AI, to improve its performance by having it focus on what matters, without loosing detail information. It has a lot to do with order of processing, what do you process and when do you process it in order to facilitate decisions what to process next. My post on Advanced C++ Skills has more on quantitative evaluations of the performance gains depending on processing order, these are huge. After the release of the original AI mod I experimented with different techniques, to increase the lookahead depth from seven game days to three game weeks, have the AI handle base upgrades and resource management more smartly, better AI combat performance and most importantly to have the AI more smartly predict their opponents' behaviour and adjust its own strategic planning. This is the 3.1.xx line of mods that you can download and try out too. These are all experimental betas though and fairly old by now.

At one point it became clear that what holds back progress on AI is of fundamental nature. Technically recursive dependencies, if you look at one branch of reality (what one actor can do) you usually make assumptions about how the realities around it unfold, but these realities need their own processing and make their own assumptions about the realities around it, which makes the actions possibly occuring in one reality dependent on what occurs in another reality and vice versa. It is a fundamental problem of predictability.

Now if you want to solve this problem with pure maths you will probably run into the same wall again and again, but in the realm of software we are more flexible and can make assumptions and estimates. It looks almost solvable. But if you work with assumptions, there are tipping points where the decision (what to do) based on one assumption depends on the outcome of another, so that figuring out what has leverage on each other and how the reality unfolds can be computationally complex and expensive. Still, we made an important substantial step here: we sketched out an algorithm with which we can evaluate the actions of competing actors and assess the merit of different actions. How good such an AI is mostly depends on the quality of our assumptions and our algorithms for this.

It dawned upon me that a fully developed AI along this line of thought can almost tackle any challenge, including the long sought goal of abstraction. It is an algorithmic approach to AI as opposed to the self-learning approach to AI and taking such a route holds a lot of formidable technological challenges. I have a certain tenacity when it comes to tackling challenges, so I thought give it a go. I ended up working double the hours regular workers do, mostly because if you tackle the technological unknown you don't know how long it will take you to reach your goal. If this sounds like hardship to you, no, it is a way of life, and I loved to understand more and more of the technological foundation of AI. If you don't have this in you, you won't last the decade such a task can take.

What we have now is a solution for AI that is far removed from other approaches. There is a short presentation that gives you an idea how algorithmic AI fits in the general progress towards AI today. Simplified algorithmic AI is comprised of crafted algorithms, written by us, that mimic the principles underlying our reality, such as causality, effect propagation and leverage. In practice, if you have the definitions of the actors, goals, entities, interactions and their initial state, algorithmic AI can figure out on its own how such a system behaves. For example in a complex strategy game like Heroes of Might & Magic, the algorithms determine step by step in which way the heroes can go over the map, conquer castles and guards and how their factions can gain leverage and win.

The key here is leverage, the AI must be capable to figure out which course of action yields the best results, which usually involves matching actions against opponents' actions. Algorithmically this was the toughest part of the work, to develop generic algorithms that determine how leverage manifests itself in complex scenarios consisting of hundreds and thousands of entities that can interact in countless ways spread out over different realities. Needless to say these algorithms have to be as efficient as possible and deliver results close to the theoretical optimum, that is competent decisions under consideration of all important facts and potential outcomes made in a minimum of time.

A second longer presentation provides you with an insight how algorithmic AI can work with contemporary video games, in particular how reactivity and productivity benefit from it. The AI tech itself integrates well with concurrent development tools and methods. It cannot be stressed enough that the product is highly practical. All entities in your project, or any desirable subset therof, can be connected to the algorithmic AI. This connection can be lean, a pointer from the entity to the AI to provide the necessary state and context on demand, or vice versa the AI tracking references to the entities to retrieve state and context as needed.

If the AI has sufficient information, everything else happens automatically: threats and opportunities are detected and behaviour emerges naturally. As the AI incorporates algorithms that determine leverage, which basically amounts to which interactions occur in which order, when and where, a good deal of gameplay code becomes redundant. For example the AI would figure out automatically when it makes sense to pick up a weapon, switch ammo, duck behind cover and so on. Its main strength is to connect the dots, i.e. how different entities interact with each other, how their environment affects them, and what to do in a given scenario. This is a lot of gameplay code that otherwise needs to be created manually, and gone with it is a large potential for human errors from extensive work that tracks all the cases how interactions can occur. I expect algorithmic AI to raise the bar for reactivity (think BG3+) and productivity substantially. Initially, given that algorithmic AI is still experimental, it makes sense to apply it first to a subset of entities, for instance the behaviour of squad members. This allows for an incremental development process to create the necessary tools step by step.

Aside from these two presentations and available on request is my co-dev offer to develop a full algorithmic AI engine jointly with an ambitious studio, either as part of a major game or as an engine with accompanying tools for licensing to third parties. Also available on request is a more detailed description of the roadmap for the further development of the AI for business angels interested in financing the technology.

Prototyping

Verification of such a complex technology, and by definition software, is key. While I have no longer any doubt that this technology pushes the edge of what you can do with AI in games, there are still a number of important milestones ahead to establish how powerful this tech truly is.

Currently there are three showcases planned. One is a large 20 vs 20 squad combat in which the team members demonstrate how to cooperate, including cover, suppression fire, and making intelligent use of the environment, height, attacking from different directions, capturing and using heavy weapons, utilizing supply points and smart distribution of the available means. The focus will be on the behaviour with simplified visuals so that the AI's complete tracking of the possible interaction spaces becomes evident and numerous behaviours that so far require their own Behaviour Trees all emerge naturally.

The showcase that will be released first is a reasonably complete military simulation, including logistics, castle building, recruitment, resource management, different types of arms, armies being affected by different types of terrain, and highly interesting strategic gameplay: the algorithmic AI will be released first as a finally complete AI mod for Heroes V. I hope to have this work done in a month, but as it is new cutting-edge technology, there remains some uncertainty, so please take this ETA as what it is, an estimate.

I also plan to attend NG23 in Helsinki, so this an opportunity to meet if you are interested in first-hand information. I am a hands-on programmer, so I could almost immediately give you an idea of the roadmap for implementing highly advanced AI features, if you say you need this and that. While it might give the impression that the algorithmic AI is work-in-progress, the core mechanics are in place and many of the algorithms can be adapted rapidly to be deployed in a project of your choice.