jgaunt.com

Artificial Intelligence. The Holy Grail of computer science and to some extent popular culture in general. Artificial Intelligence (AI) as a discipline started as early as the 1920s before computers had even hit the scene. Alan Turing, who some consider the father of AI, did some of the initial work in those days. At that time the work was focused on logic and calculus and reasoning; constructing a formal language for defining how problems could be solved. A lot of theoretical work (there were no computers yet) was done just to prove it was possible and to define what AI would mean. Turing developed the Turing Test (originally called the Imitation Game) in his 1950 Article "Computing Machinery and Intelligence" (available online here): (loosely paraphrased)

This test is seen as the ultimate test of AI. There is even an annual contest (probably several of them really), called the Loebner Prize ( website ) to see who can create the most "human-like" computer.

For my part, I'm not so concerned with the goal of creating the ultimate intelligent machine. Instead I'm interested in a few of the myriad of branches of AI that have arisen out of the research and development of the past 80 plus years.

The computer gaming industry has been a large factor in the advancement of hardware over roughly the last 10 years. The desire for higher image resolutions, pixel counts, vertex counts etc. without dragging the gameplay down has driven development efforts in video display, architecture, memory and many other areas. Hardware is in good shape. Now game developers are focusing more on the behavior of the computer as an opponent in games like chess to war games to the latest fantasy role playing game. They are attempting to make computers act smarter, as it applies to human thought processes, more competitive without just coding in a bunch of cheats. It is easy enough to let the computer know what the player is doing so it can have precognition and anticipate a player's moves. The difficulty lies in making the computer think and learn from a player's actions, find patterns and then make adjustments in its own gameplay to adapt to the particular skills and strategies of the player. Which is how the best human players game.

To this end game developers are researching and implementing in the fields of Machine Learning, Neural Networks, Genetic Algorithms, Flocking and Artificial Life among others. These are some of the most interesting branches of AI to me. Alone they don't hope to solve the Turing Test, but they can teach us about many different things, sometimes things we wouldn't expect. Some of the simplest concepts turn out to be powerful when studied closer. The Artificial Life game "Conway's Game of Life" (online here) was shown to be a Turing Machine, that is a computer capable of any computation any other computer in the world can solve(definition here).

Where is the gaming industry now?

Up until just a few years ago there was almost no AI in games at all. Not what most people would consider AI. The bulk of the intelligence of computer games is state driven. In a game like Quake3 the computer players (bots) have a number of states they cycle through and given a state (running) and a change in the environment (a player rounds a corner) the bot does a certain thing (charges at the player shooting its gun). In recent years a shift has started that gives the computer players more intelligence.

One of the first major games to show serious changes was a game called HalfLife. As happens to most games it didn't deliver on all the promises it made pre-shipment. But it still blew away the games on the market. It used flocking to compute paths of animals to make them more realistic. Enemies attacked in groups and would retreat and get reinforcements rather than just running forward and dying en masse. The authors of the game actually call their AI system a "schedule driven state machine" [1]. So we aren't talking full machine learning, neural networks and genetic algorithms, but it shows a shift in focus away from just making things fast and pretty to making games compelling and complex and realistic.

Looking at the AI techniques that are popular today and where the gaming industry is, I think the next push will be to get neural networks into games. Right now flocking is making its way in, from the way enemies collaborate to flights of birds in the background. Machine learning is starting to break in. There have been a few games: Black & White, the Creatures series and the Petz series; have all introduced some kind of learning ability in their games. The games however tend to be less stimulating in the long run, having been called "digital ant farms" [1]. That will be the next hurdle, to integrate AI that adds to the game and doesn't turn the game into a 5th grade school project.

Neural Networks seem like the next obvious step to me. Their flexibility means game companies will be able to reuse large portions of them between games. All that would be needed is the generation of new training programs to teach the networks how to deal with the specifics of the new game. Gentic Algorithms are promising too, possibly in conjunction with neural nets, but the long life cycle of getting to an ideal solution makes them a little unwiedly in gaming. I could see them maybe being applied to a game that included lots of cycles. For instance I read an article [2] about a viking game where part of the goal was to die in a blaze of glory and pass on your honor to your heirs. Genetic algorithms could work well in that situation as they would make your opponents get better as the game went on to match the experience the player themself was gaining. And every run of the game would be new and different.

Other things of interest

Most of the first person shooter (fps) games (HalfLife, Unreal, Quake etc) have extensible AI engines. This allows players to update the logic for bots and even create entirely new bots for their games. There are also some strategy games that have extensible AI (Red Alert, Galactic Civilizations). It's widely held that the best way to learn how to program AI for games is to grab one of the fps games that allows scripting and dig in there.

Expanding on that idea there is now a new genre of games: programming games. Not games that help you understand what a for loop is, but rather games where programmers compete with other programmers through AI scripts. These games have no actual players in them, they are just bots against bots. They are fps games generally and provide the ability to code the AI for a team and then upload the script to a website to compete with other programmers. Some games allow the downloading of scripts so you can test out your scripts against others locally. [2]

Most of the programming games provide a special scripting language (I have yet to see one that lets you write in C/C++) that requires some learing. And they mostly deal with state machine type of logic. Nothing is touting actual machine learning yet. But it is only a matter of time before a scripting language is designed, or enough thought is put into a game to enable machine learning in these types of games.

References

[1] GameAI page about the state of AI in games on the market.
[2] Gamasutra article about new ideas for games.
[3] GameAI page about extensible AI games and programming games.
[4] Alan Turing's Computing Machinery and Intelligence paper
[5] Loebner Prize website
[6] Conway's Game of Life
[7] Generation5 - Turing Machine discussion