Artificial intelligence (video games)
In video games, artificial intelligence is used to generate intelligent behaviors primarily in non-player characters (NPCs), often simulating human-like intelligence. The techniques used typically draw upon existing methods from the field of artificial intelligence (AI). However, the term game AI is often used to refer to a broad set of algorithms that also include techniques from control theory, robotics, computer graphics and computer science in general.
Since game AI for NPCs is centered on appearance of intelligence and good gameplay within environment restrictions, its approach is very different from that of traditional AI; workarounds and cheats are acceptable and, in many cases, the computer abilities must be toned down to give human players a sense of fairness. This, for example, is true in first-person shooter games, where NPCs' otherwise perfect aiming would be beyond human skill.
Game playing was an area of research in AI from its inception. One of the first examples of AI is the computerised game of Nim made in 1951 and published in 1952. Despite being advanced technology in the year it was made, 20 years before Pong, the game took the form of a relatively small box and was able to regularly win games even against highly skilled players of the game. In 1951, using the Ferranti Mark 1 machine of the University of Manchester, Christopher Strachey wrote a checkers program and Dietrich Prinz wrote one for chess. These were among the first computer programs ever written. Arthur Samuel's checkers program, developed in the middle 50s and early 60s, eventually achieved sufficient skill to challenge a respectable amateur. Work on checkers and chess would culminate in the defeat of Garry Kasparov by IBM's Deep Blue computer in 1997. The first video games developed in the 1960s and early 1970s, like Spacewar!, Pong, and Gotcha (1973), were games implemented on discrete logic and strictly based on the competition of two players, without AI.
Games that featured a single player mode with enemies started appearing in the 1970s. The first notable ones for the arcade appeared in 1974: the Taito game Speed Race (racing video game) and the Atari games Qwak (duck hunting light gun shooter) and Pursuit (fighter aircraft dogfighting simulator). Two text-based computer games from 1972, Hunt the Wumpus and Star Trek, also had enemies. Enemy movement was based on stored patterns. The incorporation of microprocessors would allow more computation and random elements overlaid into movement patterns.
It was during the golden age of video arcade games that the idea of AI opponents was largely popularized, due to the success of Space Invaders (1978), which sported an increasing difficulty level, distinct movement patterns, and in-game events dependent on hash functions based on the player's input. Galaxian (1979) added more complex and varied enemy movements, including maneuvers by individual enemies who break out of formation. Pac-Man (1980) introduced AI patterns to maze games, with the added quirk of different personalities for each enemy. Karate Champ (1984) later introduced AI patterns to fighting games, although the poor AI prompted the release of a second version. First Queen (1988) was a tactical action RPG which featured characters that can be controlled by the computer's AI in following the leader. The role-playing video game Dragon Quest IV (1990) introduced a "Tactics" system, where the user can adjust the AI routines of non-player characters during battle, a concept later introduced to the action role-playing game genre by Secret of Mana (1993).
Games like Madden Football, Earl Weaver Baseball and Tony La Russa Baseball all based their AI on an attempt to duplicate on the computer the coaching or managerial style of the selected celebrity. Madden, Weaver and La Russa all did extensive work with these game development teams to maximize the accuracy of the games. Later sports titles allowed users to "tune" variables in the AI to produce a player-defined managerial or coaching strategy.
The emergence of new game genres in the 1990s prompted the use of formal AI tools like finite state machines. Real-time strategy games taxed the AI with many objects, incomplete information, pathfinding problems, real-time decisions and economic planning, among other things. The first games of the genre had notorious problems. Herzog Zwei (1989), for example, had almost broken pathfinding and very basic three-state state machines for unit control, and Dune II (1992) attacked the players' base in a beeline and used numerous cheats. Later games in the genre exhibited more sophisticated AI.
Later games have used bottom-up AI methods, such as the emergent behaviour and evaluation of player actions in games like Creatures or Black & White. Façade (interactive story) was released in 2005 and used interactive multiple way dialogs and AI as the main aspect of game.
Games have provided an environment for developing artificial intelligence with potential applications beyond gameplay. Examples include Watson, a Jeopardy!-playing computer; and the RoboCup tournament, where robots are trained to compete in soccer.
Purists complain that the "AI" in the term "game AI" overstates its worth, as game AI is not about intelligence, and shares few of the objectives of the academic field of AI. Whereas "real" AI addresses fields of machine learning, decision making based on arbitrary data input, and even the ultimate goal of strong AI that can reason, "game AI" often consists of a half-dozen rules of thumb, or heuristics, that are just enough to give a good gameplay experience. Historically, academic game-AI projects have been relatively separate from commercial products because the academic approaches tended to be simple and non-scalable. Commercial game AI has developed its own set of tools, which have been sufficient to give good performance in many cases.
Game developers' increasing awareness of academic AI and a growing interest in computer games by the academic community is causing the definition of what counts as AI in a game to become less idiosyncratic. Nevertheless, significant differences between different application domains of AI mean that game AI can still be viewed as a distinct subfield of AI. In particular, the ability to legitimately solve some AI problems in games by cheating creates an important distinction. For example, inferring the position of an unseen object from past observations can be a difficult problem when AI is applied to robotics, but in a computer game a NPC can simply look up the position in the game's scene graph. Such cheating can lead to unrealistic behavior and so is not always desirable. But its possibility serves to distinguish game AI and leads to new problems to solve, such as when and how to use cheating.
The major limitation to strong AI is the inherent depth of thinking and the extreme complexity of the decision making process. This means that although it would be then theoretically possible to make "smart" AI the problem would take considerable processing power.
In computer simulations of board games
- Computer chess
- Computer Go
- Computer checkers
- Computer poker players
- Computer bridge
- Computer shogi
- Computer Arimaa
- Logistello, which plays Reversi
- Rog-O-Matic, which plays Rogue
- Computer players of Scrabble
- A variety of board games in the Computer Olympiad
- General game playing
- Solved games have a computer strategy which is guaranteed to be optimal, and in some cases force a win or draw.
In modern video games
Game AI/heuristic algorithms are used in a wide variety of quite disparate fields inside a game. The most obvious is in the control of any NPCs in the game, although scripting is currently the most common means of control. Pathfinding is another common use for AI, widely seen in real-time strategy games. Pathfinding is the method for determining how to get a NPC from one point on a map to another, taking into consideration the terrain, obstacles and possibly "fog of war". Beyond pathfinding, navigation is a sub-field of Game AI focusing on giving NPCs the capability to navigate in their environment, finding a path to a target while avoiding collisions with other entities (other NPC, players...) or collaborating with them (group navigation).
The concept of emergent AI has recently been explored in games such as Creatures, Black & White and Nintendogs and toys such as Tamagotchi. The "pets" in these games are able to "learn" from actions taken by the player and their behavior is modified accordingly. While these choices are taken from a limited pool, it does often give the desired illusion of an intelligence on the other side of the screen.
Video game combat AI
The many contemporary video games fall under the category of action, first person shooter, or adventure. In most of these types of games there is some level of combat that takes place. The AI's ability to be efficient in combat is important in these genres. A common goal today is to make the AI more human, or at least appear so.
One of the more positive and efficient features found in modern day video game AI is the ability to hunt. AI originally reacted in a very black and white manner. If the player were in a specific area then the AI would react in either a complete offensive manner or be entirely defensive. In recent years, the idea of "hunting" has been introduced; in this 'hunting' state the AI will look for realistic markers, such as sounds made by the character or footprints they may have left behind. These developments ultimately allow for a more complex form of play. With this feature, the player can actually consider how to approach or avoid an enemy. This is a feature that is particularly prevalent in the stealth genre.
Another development in recent game AI has been the development of "survival instinct". In-game computers can recognize different objects in an environment and determine whether it is beneficial or detrimental to its survival. Like a user, the AI can "look" for cover in a firefight before taking actions that would leave it otherwise vulnerable, such as reloading a weapon or throwing a grenade. There can be set markers that tell it when to react in a certain way. For example, if the AI is given a command to check its health throughout a game then further commands can be set so that it reacts a specific way at a certain percentage of health. If the health is below a certain threshold then the AI can be set to run away from the player and avoid it until another function is triggered. Another example could be if the AI notices it is out of bullets, it will find a cover object and hide behind it until it has reloaded. Actions like these make the AI seem more human. However, there is still a need for improvement in this area. Unlike a human player the AI must be programmed for all the possible scenarios. This severely limits its ability to surprise the player.
Another side-effect of combat AI occurs when two AI-controlled characters encounter each other; first popularized in the id Software game Doom, so-called 'monster infighting' can break out in certain situations. Specifically, AI agents that are programmed to respond to hostile attacks will sometimes attack each other if their cohort's attacks land too close to them. In the case of Doom, published gameplay manuals even suggest taking advantage of monster infighting in order to survive certain levels and difficulty settings.
Uses of AI in games beyond NPCs
Georgios N. Yannakakis suggests that academic AI developments can play roles in game AI beyond the traditional paradigm of AI controlling NPC behavior. He highlights four other potential application areas:
- Player-experience modeling: Discerning the ability and emotional state of the player, so as to tailor the game appropriately. This can include dynamic game difficulty balancing, which consists in adjusting the difficulty in a video game in real-time based on the player's ability. Game AI may also help deduce player intent (such as gesture recognition).
- Procedural-content generation: Creating elements of the game environment like environmental conditions, levels, and even music in an automated way. AI methods can generate new content or interactive stories.
- Data mining on user behavior: This allows game designers to explore how people use the game, what parts they play most, and what causes them to stop playing, allowing developers to tune gameplay or improve monetization.
- Alternate approaches to NPCs: These include changing the game set-up to enhance NPC believability and exploring social rather than individual NPC behavior.
In the context of artificial intelligence in video games, cheating refers to the programmer giving agents access to information that would be unavailable to the player in the same situation. In a simple example, if the agents want to know if the player is nearby they can either be given complex, human-like sensors (seeing, hearing, etc.), or they can cheat by simply asking the game engine for the player's position. The use of cheating in AI shows the limitations of the "intelligence" achievable artificially; generally speaking, in games where strategic creativity is important, humans could easily beat the AI after a minimum of trial and error if it were not for this advantage. Cheating is often implemented for performance reasons where in many cases it may be considered acceptable as long as the effect is not obvious to the player. While cheating refers only to privileges given specifically to the AI—it does not include the inhuman swiftness and precision natural to a computer—a player might call the computer's inherent advantages "cheating" if they result in the agent acting unlike a human player. Sid Meier stated that he omitted multiplayer alliances in Civilization because he found that the computer was almost as good as humans in using them, which caused players to think that the computer was cheating.
- Creatures (1996)
Creatures is an artificial life program where the user "hatches" small furry animals and teaches them how to behave. These "Norns" can talk, feed themselves, and protect themselves against vicious creatures. It's the first popular application of machine learning into an interactive simulation. Neural networks are used by the creatures to learn what to do. The game is regarded as a breakthrough in artificial life research, which aims to model the behavior of creatures interacting with their environment.
- Halo: Combat Evolved (2001)
A first-person shooter where the player assumes the role of the Master Chief, battling various aliens on foot or in vehicles. Enemies use cover very wisely, and employ suppressive fire and grenades. The squad situation affects the individuals, so certain enemies flee when their leader dies. A lot of attention is paid to the little details, with enemies notably throwing back grenades or team-members responding to you bothering them. The underlying "behavior tree" technology has become very popular in the games industry (especially since Halo 2).
- F.E.A.R. (2005)
A first-person shooter where the player helps contain supernatural phenomenon and armies of cloned soldiers. The AI uses a planner to generate context-sensitive behaviors, the first time in a mainstream game. This technology used as a reference for many studios still today. The enemies are capable of using the environment very cleverly, finding cover behind tables, tipping bookshelves, opening doors, crashing through windows, and so on. Squad tactics are used to great effect. The enemies perform flanking maneuvers, use suppression fire, etc.
- S.T.A.L.K.E.R. series (2007-)
A first-person shooter survival horror game where the player must face man-made experiments, military soldiers, and mercenaries known as Stalkers. The various encountered enemies (if the difficulty level is set to its highest) use combat tactics and behaviours such as healing wounded allies, giving orders, out-flanking the player or using weapons with pinpoint accuracy.
- Far Cry 2 (2008)
A first-person shooter where the player fights off numerous mercenaries and assassinates faction leaders. The AI is behavior based and uses action selection, essential if an AI is to multitask or react to a situation. The AI can react in an unpredictable fashion in many situations. The enemies respond to sounds and visual distractions such as fire or nearby explosions and can be subject to investigate the hazard, the player can utilize these distractions to his own advantage. There are also social interfaces with an AI but however not in the form of direct conversation but more reactionary, if the player gets too close or even nudges an AI, the player is subject to getting shoved off or sworn at and by extent getting aimed at. Other social interfaces between AI exist when in combat, or neutral situations, if an enemy AI is injured on the ground, he will shout out for help, release emotional distress, etc.
- Behavior model
- AI effect
- Applications of artificial intelligence
- Action selection
- Computer chess
- Computer game bot
- Computer Go
- Dynamic game difficulty balancing
- General Game Playing
- Simulated reality
- Kynapse - game AI middleware, specializing in path finding and spatial reasoning
- AiLive - A suite of game AI middleware
- xaitment - graphical game AI software
- Grant, Eugene F.; Lardner, Rex (2 August 1952). "The Talk of the Town - It". The New Yorker.
- See "A Brief History of Computing" at AlanTuring.net.
- Schaeffer, Jonathan. One Jump Ahead:: Challenging Human Supremacy in Checkers, 1997,2009, Springer, ISBN 978-0-387-76575-4. Chapter 6.
- McCorduck, Pamela (2004), Machines Who Think (2nd ed.), Natick, MA: A. K. Peters, Ltd., ISBN 1-56881-205-1, p. 480-483
- First Queen at MobyGames
- "Official Site". Kure Software Koubou. Retrieved 19 May 2011. (Translation)
- Schwab, 2004, p. 97-112
- Schwab, 2004, p.107
- Emergent Intelligence in Games17 February 2011.
- Yannakakis, Geogios N (2012). "Game AI revisited" (PDF). Proceedings of the 9th conference on Computing Frontiers: 285–292.
- Schreiner, Tim. "Artificial Intelligence in Game Design." Artificial Intelligence Depot. Web. 19 November 2009. AI-depot.com
- Scott, Bob (2002). "The Illusion of Intelligence". In Rabin, Steve. AI Game Programming Wisdom. Charles River Media. pp. 16–20.
- "The 7th International Computer Game Developers Conference". Computer Gaming World. July 1993. p. 34. Retrieved 12 July 2014.
- AiGameDev - Top 10 Most Influential AI Games
- Bourg; Seemann (2004). AI for Game Developers. O'Reilly & Associates. ISBN 0-596-00555-5.
- Buckland (2002). AI Techniques for Game Programming. Muska & Lipman. ISBN 1-931841-08-X.
- Buckland (2004). Programming Game AI By Example. Wordware Publishing. ISBN 1-55622-078-2.
- Champandard (2003). AI Game Development. New Riders. ISBN 1-59273-004-3.
- Funge (1999). AI for Animation and Games: A Cognitive Modeling Approach. A K Peters. ISBN 1-56881-103-9.
- Funge (2004). Artificial Intelligence for Computer Games: An Introduction. A K Peters. ISBN 1-56881-208-6.
- Millington (2005). Artificial Intelligence for Games. Morgan Kaufmann. ISBN 0-12-497782-0.
- Schwab (2004). AI Game Engine Programming. Charles River Media. ISBN 1-58450-344-0.
- Smed and Hakonen (2006). Algorithms and Networking for Computer Games. John Wiley & Sons. ISBN 0-470-01812-7.