Thursday, August 15, 2013

Cheesy Tactics - How AI is critical to single-player gaming

One of the areas of gaming that has always fascinated me is artificial intelligence. Whether the goal is to produce a perfect player, accurately mimic humans, or providing an escalating training aid, solid AI is integral to a satisfying offline experience. In this post, I briefly outline what makes for a successful AI and provide some examples of both good and bad implementation.



The types of AI

Whether an AI can be deemed ‘good’ is entirely dependent on its intended goal. The most basic AI is one that is designed to be the most optimal player of a game. The goal of this brand of AI is to win at all costs. In a FPS. this generally entails perfect aim, in a RTS this implies an ability to fully micro-manage an empire. For these genres, a perfect AI can be nigh impossible to defeat in that it is capable of reacting much more quickly and efficiently then a human can. Where the challenge in creating a perfect AI comes in is in handling high strategy. While giving a computer controlled entity super-human reflexes is fairly easy, providing them with the ability to react and adapt to changes in the game and to develop a sound strategy based on how the game is unfolding is much more difficult.

Another approach to AI design is to mimic human behaviour. This intelligence is not intended to win all the time but rather to provide a convincing human-like challenge. The quintessential metric for this type of AI is successful is whether or not it passes the Turing test. While the test exists in many forms, it essentially boils down to whether the computer can act convincingly human enough that it is mistaken for one. Obviously, the longer the AI can pass itself off as human, the better it is. This type of AI can be extremely difficult to design because human behaviour can be extremely difficult to predict. A player may have a default strategy but this is constantly in flux as they react to game conditions. The difference with the perfect AI is that a human player does not always react rationally. If you are killed repeatedly by the same player in an FPS, you may end up ignoring everything else in a quest for revenge. Alternatively, sometimes players just go on tear, racking up kills while in a zen like trance. Both of these examples are unpredictable and it is not difficult to understand why designed AI to mimic them is extremely difficult.

The final approach to AI design I will discuss is a hybrid of the previous two. This AI is generally designed to serve as a learning tool; adapting to a players skill level and adjusting difficulty to provide a solid challenge. For a new player, the AI dumbs itself down providing an opportunity to learn mechanics. For experts, the AI may approach super-human levels to provide a difficult challenge to hone skills against. The difficulty for this AI, is that it needs to make a judgement of human skill which is a factor of many attributes. For example, a really good player may underperform if they are put into a map they are unfamiliar with while a subpar player may artificially inflate their score by exploiting imbalances in game mechanics or relying on a single set of marginal tactics (ie spawn camping). The challenge for the AI is to recognize when a superior player is not playing their best and when a subpar player is overreaching.

 Now that I have elaborated a bit on the different goals of AI programming, I thought I would provide some examples of success and failure in achieving these goals.

The Perfect AI
Good: Deep Blue
A chess playing AI that was beat world champion Kasparov twice. Deep Blue is probably one of the most famous examples of an AI designed to be as difficult as possible. While Deep Blue is certainly powerful, it is also incredibly dull; success for this AI was entirely by rote, calculating millions of possible moves a second and projecting for the best possible board position. As such, Deep Blue would win its matches through stern application of probability rather then through creativity (the hallmark of a great human chess player). Then again, Deep Blue was never designed to be human.

Bad: Civilization 5 (on maximum difficulty)
The AI in Civilization is simply awful. On maximum difficulties, the AI routinely fails to maximize its empire and handles combat like a five year old hitting its toys together and making smashing sounds. The problem with this AI is that it succeeds only by breaking the game rules (ignoring key aspects like income and happiness). I pick Civilization because it is one of the most blatant examples, but when the AI needs to cheat to win, it is not smart.

The Turing AI
Good: Warlight
Warlight is a browser based game that plays like Risk on steroids (http://www.warlight.net) and features one of the best AIs I have ever seen. Routinely I will see the AI baiting traps, checking aggression, and mixing up tactics. It does this all while not being omnicient and seemingly confined by the game rules (often respecting the fog of war and behaving appropriately to the discovery of surprise armies). The only flaw I have found is that it fails to ally up with other AIs when circumstances are dire. If you enjoy Risk, then I highly recommend giving Warlight a try and marveling at just how human-like the AI can be.

Bad: Starcraft 2 (on medium difficulties)
I was sort of on the fence if the AI in Starcraft should be put in the perfect section or here. In the end I decided that moderate AI difficulty settings are intended to replicate a human experience (Blizzard has explicitly stated that the offline mode should serve as a staging ground for online battle). The problem is that the AI routinely falls for specific strategies and rarely seems to adapt to the battlefield. If I am swooping in with only air units, I would expect my opponent to counter by heavily investing in countermeasures (not just building a few token anti-air units for me to chew through). Making matters worse is that, if you have a game stretch on long enough, the AI sort of gives up and basically gets stuck in a loop (making only the same units, attacking in predictable patterns, and never ceasing to expand).


The Hybrid AI
Good: Unreal Tournament
Depending on what difficulty level you set a bot to in Unreal Tournament, you can get everything from a stationary target to a god. While not truly adaptive (you have to specify a difficulty) it is still amazing to see just how each step up on the AI difficulty rung is nuanced. Medium levels have actually won Turing prizes for convincingly mimicking human behavior while lower level difficulties have functioned as the gold-standard training difficulty (and in many cases ported directly to other games).

Bad: Street Fighter 4
Again, not a true instance of dynamic AI, but with a gamut of difficulty levels one should be able to pick a reasonable mix. The problem is that lower difficulties function fine as a punching bag but the difficulty scales in an unrealistic fashion. The AI in Street Fighter doesn't train you to get better but rather trains you to rely on ineffective tactics (lots of jump-ins, blind-firing ultras, crowding the opponent on wake-up). While each of these tactics may have uses in very specific instances, the AI just seems to fall for them all from mid to top difficulties. The final nail in the coffin is that the maximum difficulty AI isn't even all that hard to exploit for for easy victory (I have seen numerous people simply spam Zangief's spinning lariat to victory in single player and trying to transition this to online to horrendous effect).

Final Thoughts

Hopefully, this discussion on AI has highlighted just how important a solid AI can be to contribute to an enjoyable single-player experience. Hopefully, it has also illuminated how strong AI need not always be a victory machine, mimicking human behaviour and serving as a training tool are just as important.