Artificial intelligence in computer games - X-RAY #25 Part 1

Games too smart for you -- how about not enough? John Simpson delves into the story behind the AI that drives games forward -- the same AI that drives Marines into minefields.

ABOVE: 'Tread marks', a new title from Tantalus Interactive, features intelligent tanks that behave in accordance with the environment. Each has its own personality, and promises to pose a real challenge by using Neutral net AI.

It's been eighteen months since we had to sit through the movie AI: Artificial Intelligence. The film starts out quite well, with William Hurt explaining the difficulties of designing a thinking machine, while a good looking android-ess takes off her clothes and does a neat trick with her face. Then it all goes pear-shaped, as the film hits its second hour and we're wondering what the hell's going on. Blue lady? Critics unanimously agreed it was like watching Disney do Close Encounters, without the mystery and mashed potato.

The real life science of artificial intelligence is not so different -- lots of hype and not a lot to show for it. Getting R2-D2 from the screen to our lounge rooms has been a real struggle -- the best effort to date is a silver dog that runs out of batteries in two hours (then isn't smart enough to recharge itself). Let's face it -- the Matrix is looking a long way off.

There is however one bright star in the AI sky -- computer games. If you thought the enemies in the latest first person shooters are getting smarter, you're right. There have been significant advances in the past couple of years in game AI, with a lot of the work being developed in Australia by companies such as Tantalus and Blue Tongue. It may not be long before games can watch, learn and improve on our best moves. . . then turn them against us.

A brief history of AI

There's a true story about an 18th century Baron -- Wolfgang von Kempelen -– who invented a chess-playing machine for the amusement of Austrian Queen Maria Theresia. The clockwork machine, named 'The Turk', was shaped like a mechanical man positioned over a chessboard. At performances, Kempelen would open the doors in the platform underneath the chessboard, revealing a latticework of gears and machinery, then challenge audience members to play. Almost all were defeated by the machine, which even staged a humiliating defeat against Napoléon the First.

In 1826 The Turk passed into the hands of inventor Johann Maelzel, who took it on its infamous American tour, playing names such as Benjamin Franklin and Edgar Allan Poe. It wasn't until 1857 -- three years after the Turk had been destroyed in a fire and nineteen years after Maelzel died -- that Maelzel's son final owner revealed its secret: an expert chess player hiding inside.

Mankind's fascination with intelligent machines has been around for ages: from the ancient Greeks and their mechanical models, to Pascal's invention of the world's first mechanical calculator in 1642 -- 'thinking' machinery has always pulled crowds. But it was in the twentieth century that the field really began to take a front row. The word 'robot' first appeared in 1950, in a play by Karel Capek (from the Czech word robota meaning serf or 'forced labour' -- the word was reportedly snapped at Karel by his brother in a hissy fit). 'Cybernetics' and 'artificial intelligence' came soon after, riding on the wave of interest from Alan Turing's article Computing Machinery and Intelligence (in it, Turing showed how to test intelligent behaviour in machines (see note) -- it's still a legitimate test today).

That same year, Isaac Asimov wrote the Three Laws of Robotics in his book I,Robot:

1. A robot may not harm a human being, or, through inaction, allow a human being to come to harm.
2. A robot must obey the orders given to it by the human beings, except where such orders would conflict with the First Law.
3. A robot must protect its own existence, as long as such protection does not conflict the First or Second Law.

These Laws are regarded as fundamental to the future of AI, although some scientists question how they would hold for robots working in dangerous areas, or military 'bots. Games obviously don't have to follow these rules, allowing more flexibility -- although as virtual reality advances the Laws may become increasingly important.

History of AI in games

Remember Pac-man, the annoying yellow blob that ate pixel blocks and spawned a new generation of gamers? One of the reasons it was so popular was that the ghosts seemed intelligent. Players had to evade capture, turning the tables after eating a power-up. Despite the simplicity, Pacman formed the basis of the games we play today.

Things moved up a notch with the advent of first person shooters. Like jumping into the Pac-man maze, games like Castle Wolfenstein and Doom introduced enemies that would attack on sight -- but they were often so stupid they'd walk straight into gunfire. It took a number of years before Valve released a game that changed it all: Half-Life. Half-Life had bad guys that would do different things when shot; they'd react to thrown grenades; and they'd even demonstrate a realistic awareness of the player. Half-Life produced an interesting shift in games: from better graphics to more intelligent enemies.

The AI in FPS games today has evolved to remarkable levels. Enemies will hide behind cover if approached; they'll react realistically if outnumbered or outgunned; and they'll even try and throw a grenade back at the player. These combat AIs are very close to the real thing -- although they still can't beat a seasoned player. Why?

The reason is that human opponents have four basic behaviours that -- to date -- AIs can only try and simulate. Let's look at each a little more closely…

1. Environment Utilisation
A combat AI can be programmed to hide behind a box if under fire. But only a human player will make use of that box in other ways – eg. using it as a weapon, or perhaps a floatation device. Unless specifically instructed, the game AI will always behave predictably.
Because of this, combat AIs can't use terrain as effectively as a human player. Humans tend to be much better at ambushing or concealment, whereas AIs can only use the environment in ways they've been instructed.

2.Teamwork Strategies
Teamwork shines when clans play a game like Counter-Strike. Each player makes use of their best skills together with other players, sometimes sacrificing themselves for the benefit of the team. Combat AIs are more solitary in their behaviour, and appear (from the outside) to behave almost selfishly.

Getting AIs to interact as an effective team is extremely difficult. Let's face it: it's hard enough teaming real people together. For now we have to be satisfied with individual opponent AIs flocking together -- a pseudo-team.

3. Hunting
The ghosts in Pac-man were programmed to seek out the player using the shortest possible route. Interestingly, FPSs seem to have taken a step back: now the player takes the predatory role -- the enemies are invariably left to guard. If attacked, AI opponents must decide a course of limited actions as quickly as possible. This makes life a lot easier for the game developers, but not so satisfying for the human players.

Turn the tables: what if the AIs are the predators and the humans are the guards? Currently, this sc