As computers and video game consoles advance, players expect the games running on these systems to become ever smarter. Long gone are the days of beating on-screen enemies by timing your attacks based on their predictable patterns of behavior—say, when they throw a fireball. Gamers today want their computerized villains to “think” and act like humans, whether it’s a race car driver who swerves into you at just the right point on the course or an alien who can learn your shooting strategy to take you down.
To make their characters smarter, developers have turned to artificial intelligence (AI), a machine-based way of producing behavior associated with human intelligence. In any of these games, complex algorithms are key. They’re applied to program the characters to react realistically and learn the human player’s behavior. The latest advances in algorithms likely to take gaming to the next level were discussed at the 2009 IEEE Symposium on Computational Intelligence and Games, held in Milan in September.
PROGRESS IN ALGORITHMS
AI has been used in computer games for years and more recently in video games, points out IEEE Senior Member Simon Mark Lucas, an AI expert and professor of computer science at the University of Essex, in Colchester, United Kingdom.
In the beginning, academic research in AI mainly focused on computer versions of classic games such as chess, backgammon, checkers, Othello, and Go, says Lucas, who is editor-in-chief of the IEEE Transactions on Computational Intelligence and AI in Games. Lucas is also cofounder of the symposium.
“In the last decade remarkable advances have been made, with the AI player now dominating the human player in almost all these games,” he says. Go, however, with two players who alternately place black and white stones on empty intersections of a grid so as to surround their opponent’s stones, has long been a difficult challenge for developers because of the high branching factor and lack of a useful position value function, according to Lucas. “Unlike chess, Go cannot be played to a high standard by using conventional game-tree search,” he explains. “The best computer Go player is still weaker than the best human players.”
But, Lucas adds, that may soon change thanks to a new class of algorithms based on the Monte Carlo tree search (MCTS), an approach that uses random sampling to compute results. By using MCTS in an algorithm, programmers can generate realistic and humanlike AI in games because the randomness allows for programming more unique AI behaviors—the way the enemies move, attack, and react to human players and their surroundings.
Developers are making increasingly clever use of AI in video games. A good example is Left 4 Dead, a game developed for the Xbox 360 and PC in which players shoot a horde of rampaging zombies. The AI director controls the way the zombies attack to optimize the player’s experience. Because of the carefully directed randomness, a gamer will never play the exact same scenario twice.
Lucas predicts MCTS and other AI approaches will continue to make even more inroads in games. Gamers will find themselves interacting with tougher opponents, more challenging missions, and more realistic characters. Also, the mode of interaction won’t be limited to game pads, according to Lucas.
“Imagine a Lara Croft [the heroine from the popular Tomb Raider series] having a conversation with you via a headset, such as multiplayer online gamers have among themselves,” he says. To make that possible, AI will have to incorporate speech recognition, which Lucas says is just starting to approach the accuracy needed to be feasible.
Just how smart can engineers make AI? Lucas says there are no boundaries except to make sure an AI approach doesn’t take away from a player’s enjoyment.
“The main challenges are to develop characters that learn in interesting ways as the game progresses and to ensure that smart AI leads to games that are more fun,” he says. “Intelligence for its own sake is an interesting challenge for AI academic studies, but for games, the emphasis is on giving the player a fun experience with high replay value.”