Artificial intelligence in video games
In video games, artificial intelligence (AI) is used to generate responsive, adaptive or intelligent behaviors primarily in non-player characters (NPCs) similar to human-like intelligence. Artificial intelligence has been an integral part of video games since their inception in the 1950s. AI in video games is a distinct subfield and differs from academic AI. It serves to improve the game-player experience rather than machine learning or decision making. During the golden age of arcade video games the idea of AI opponents was largely popularized in the form of graduated difficulty levels, distinct movement patterns, and in-game events dependent on the player's input. Modern games often implement existing techniques such as pathfinding and decision trees to guide the actions of NPCs. AI is often used in mechanisms which are not immediately visible to the user, such as data mining and procedural-content generation.
However, "game AI" does not, in general, as might be thought and sometimes is depicted to be the case, mean a realization of an artificial person corresponding to an NPC, in the manner of say, the Turing test or an artificial general intelligence.
The term "game AI" is used to refer to a broad set of algorithms that also include techniques from control theory, robotics, computer graphics and computer science in general, and so video game AI may often not constitute "true AI" in that such techniques do not necessarily facilitate computer learning or other standard criteria, only constituting "automated computation" or a predetermined and limited set of responses to a predetermined and limited set of inputs.
Many industries and corporate voices [failed verification] claim that so-called video game AI has come a long way in the sense that it has revolutionized the way humans interact with all forms of technology, although many[who?] expert researchers are skeptical of such claims, and particularly of the notion that such technologies fit the definition of "intelligence" standardly used in the cognitive sciences. Industry voices [failed verification] make the argument that AI has become more versatile in the way we use all technological devices for more than their intended purpose because the AI allows the technology to operate in multiple ways, allegedly developing their own personalities and carrying out complex instructions of the user.
However, many [failed verification] in the field of AI have argued that video game AI is not true intelligence, but an advertising buzzword used to describe computer programs that use simple sorting and matching algorithms to create the illusion of intelligent behavior while bestowing software with a misleading aura of scientific or technological complexity and advancement. 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.
Game playing was an area of research in AI from its inception. One of the first examples of AI is the computerized 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 in 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.
Many experts 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 cheat.
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 shogi
- Computer Go
- Computer checkers
- Computer Othello
- Computer poker players
- 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" (decision tree) is currently the most common means of control. These handwritten decision trees often result in "artificial stupidity" such as repetitive behavior, loss of immersion, or abnormal behavior in situations the developers did not plan for.
Pathfinding, another common use for AI, is 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". Commercial videogames often use fast and simple "grid-based pathfinding", wherein the terrain is mapped onto a rigid grid of uniform squares and a pathfinding algorithm such as A* or IDA* is applied to the grid. Instead of just a rigid grid, some games use irregular polygons and assemble a navigation mesh out of the areas of the map that NPCs can walk to. As a third method, it is sometimes convenient for developers to manually select "waypoints" that NPCs should use to navigate; the cost is that such waypoints can create unnatural-looking movement. In addition, waypoints tend to perform worse than navigation meshes in complex environments. Beyond static pathfinding, navigation is a sub-field of Game AI focusing on giving NPCs the capability to navigate in a dynamic environment, finding a path to a target while avoiding collisions with other entities (other NPC, players...) or collaborating with them (group navigation). Navigation in dynamic strategy games with large numbers of units, such as Age of Empires (1997) or Civilization V (2010), often performs poorly; units often get in the way of other units.
Rather than improve the Game AI to properly solve a difficult problem in the virtual environment, it is often more cost-effective to just modify the scenario to be more tractable. If pathfinding gets bogged down over a specific obstacle, a developer may just end up moving or deleting the obstacle. In Half-Life (1998), the pathfinding algorithm sometimes failed to find a reasonable way for all the NPCs to evade a thrown grenade; rather than allow the NPCs to attempt to bumble out of the way and risk appearing stupid, the developers instead scripted the NPCs to crouch down and cover in place in that situation.
Video game combat AI
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.
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.
Monte Carlo Tree Search Method
Game AI often amounts to pathfinding and finite state machines. Pathfinding gets the AI from point A to point B, usually in the most direct way possible. State machines permit transitioning between different behaviors. The Monte Carlo Tree Search method provides a more engaging game experience by creating additional obstacles for the player to overcome. The MCTS consists of a tree diagram in which the AI essentially plays tic-tac-toe. Depending on the outcome, it selects a pathway yielding the next obstacle for the player. In complex video games, these trees may have more branches, provided that the player can come up with several strategies to surpass the obstacle.
Uses in games beyond NPCs
- 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.
Rather than procedural generation, some researchers have used generative adversarial networks (GANs) to create new content. In 2018 researchers at Cornwall University trained a GAN on a thousand human-created levels for DOOM (1993); following training, the neural net prototype was able to design new playable levels on its own. Similarly, researchers at the University of California prototyped a GAN to generate levels for Super Mario. In 2020 Nvidia displayed a GAN-created clone of Pac-Man; the GAN learned how to recreate the game by watching 50,000 (mostly bot-generated) playthroughs.
Gamers always ask if the AI cheats (presumably so they can complain if they lose)— Terry Lee Coleman of Computer Gaming World, 1994
In the context of artificial intelligence in video games, cheating refers to the programmer giving agents actions and access to information that would be unavailable to the player in the same situation. Believing that the Atari 8-bit could not compete against a human player, Chris Crawford did not fix a bug in Eastern Front (1941) that benefited the computer-controlled Russian side. Computer Gaming World in 1994 reported that "It is a well-known fact that many AIs 'cheat' (or, at least, 'fudge') in order to be able to keep up with human players".
For 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. Common variations include giving AIs higher speeds in racing games to catch up to the player or spawning them in advantageous positions in first-person shooters. 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. Developers say that most are honest but they dislike players erroneously complaining about "cheating" AI. In addition, humans use tactics against computers that they would not against other people.
- 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 was the first popular application of machine learning in 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.
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 suppressing 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 psychological horror first-person shooter in which the player characters engages a battalion of cloned super-soldiers, robots and paranormal creatures. The AI uses a planner to generate context-sensitive behaviors, the first time in a mainstream game. This technology is still used as a reference for many studios. The Replicas are capable of utilizing the game environment to their advantage, such as overturning tables and shelves to create cover, opening doors, crashing through windows, or even noticing (and alerting the rest of their comrades to) the player's flashlight. In addition,the AI is also capable of performing flanking maneuvers, using suppressing fire, throwing grenades to flush the player out of cover, and even playing dead. Most of the aforementioned actions (in particular the flanking) is the result of emergent behavior.
- 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 behaviors such as healing wounded allies, giving orders, out-flanking the player or using weapons with pinpoint accuracy.
- StarCraft II (2010)
A real-time strategy game where a player takes control of one of three factions in a 1v1, 2v2, or 3v3 battle arena. The player must defeat their opponents by destroying all their units and bases. This is accomplished by creating units that are effective at countering your opponents' units. Players can play against multiple different levels of AI difficulty ranging from very easy to Cheater 3 (insane). The AI is able to cheat at the difficulty Cheater 1 (vision), where it can see units and bases when a player in the same situation could not. Cheater 2 gives the AI extra resources, while Cheater 3 gives an extensive advantage over its opponent.
- Applications of artificial intelligence
- Behavior model
- Machine learning in video games
- Video game bot
- 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.
- Yannakakis, Geogios N (2012). "Game AI revisited" (PDF). Proceedings of the 9th Conference on Computing Frontiers: 285–292. Archived (PDF) from the original on 8 August 2014.
- Bogost, Ian (March 2017). ""Artificial Intelligence" Has Become Meaningless". Retrieved 22 July 2017.
- Kaplan, Jerry (March 2017). "AI's PR Problem". MIT Technology Review.
- Eaton, Eric; Dietterich, Tom; Gini, Maria (December 2015). "Who Speaks for AI?". AI Matters. 2 (2): 4–14. doi:10.1145/2847557.2847559. S2CID 207233310.
- Eastwood, Gary. "How video game AI is changing the world". CIO. Archived from the original on 28 February 2017. Retrieved 28 February 2017.
- 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 Games Archived 19 February 2011 at the Wayback Machine17 February 2011.
- Good, Owen S. (5 August 2017). "Skyrim mod makes NPC interactions less scripted, more Sims-like". Polygon. Retrieved 16 April 2018.
- Lara-Cabrera, R., Nogueira-Collazo, M., Cotta, C., & Fernández-Leiva, A. J. (2015). Game artificial intelligence: challenges for the scientific community.
- Yannakakis, G. N. (2012, May). Game AI revisited. In Proceedings of the 9th conference on Computing Frontiers (pp. 285–292). ACM.
- Hagelback, Johan, and Stefan J. Johansson. "Dealing with fog of war in a real-time strategy game environment." In Computational Intelligence and Games, 2008. CIG'08. IEEE Symposium On, pp. 55-62. IEEE, 2008.
- Abd Algfoor, Zeyad; Sunar, Mohd Shahrizal; Kolivand, Hoshang (2015). "A Comprehensive Study on Pathfinding Techniques for Robotics and Video Games". International Journal of Computer Games Technology. 2015: 1–11. doi:10.1155/2015/736138.
- Yap, Peter. "Grid-based path-finding." In Conference of the Canadian Society for Computational Studies of Intelligence, pp. 44-55. Springer, Berlin, Heidelberg, 2002.
- Sturtevant, N. R. (June 2012). "Benchmarks for Grid-Based Pathfinding". IEEE Transactions on Computational Intelligence and AI in Games. 4 (2): 144–148. doi:10.1109/TCIAIG.2012.2197681.
- Goodwin, S. D., Menon, S., & Price, R. G. (2006). Pathfinding in open terrain. In Proceedings of International Academic Conference on the Future of Game Design and Technology.
- Nareyek, A. (2004). AI in computer games. Queue, 1(10).
- Cui, X., & Shi, H. (2011). A*-based pathfinding in modern computer games. International Journal of Computer Science and Network Security, 11(1), 125-130.
- "Design Techniques and Ideals for Video Games". Byte Magazine. 7 (12). 1982. p. 100.
- Lidén, L. (2003). Artificial stupidity: The art of intentional mistakes. AI game programming wisdom, 2, 41-48.
- Schreiner, Tim. "Artificial Intelligence in Game Design." Artificial Intelligence Depot. Web. 19 November 2009. AI-depot.com Archived 10 August 2011 at the Wayback Machine
- Statt, Nick (9 March 2019). "HOW ARTIFICIAL INTELLIGENCE WILL REVOLUTIONIZE THE WAY VIDEO GAMES ARE DEVELOPED AND PLAYED". Retrieved 23 February 2020.
- "AI creates new levels for Doom". BBC News. 8 May 2018. Retrieved 17 May 2018.
- Vincent, James (22 May 2020). "Nvidia's AI recreates Pac-Man from scratch just by watching it being played". The Verge. Retrieved 28 May 2020.
- Coleman, Terry Lee (July 1994). "He Ain't Heavy, He's My Sovereign". Computer Gaming World. pp. 110–111.
- Scott, Bob (2002). "The Illusion of Intelligence". In Rabin, Steve (ed.). AI Game Programming Wisdom. Charles River Media. pp. 16–20.
- Wilson, Johnny L.; Brown, Ken; Lombardi, Chris; Weksler, Mike; Coleman, Terry (July 1994). "The Designer's Dilemma: The Eighth Computer Game Developers Conference". Computer Gaming World. pp. 26–31.
- Wilson, Johnny L. (February 1994). "Mea Culpas And Culpability". Editorial. Computer Gaming World. p. 8.
- "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
- Horti, Samuel (3 April 2017). "Why F.E.A.R.'s AI is still the best in first-person shooters". Rock, Paper, Shotgun. Retrieved 29 December 2020.
- "Building the AI of F.E.A.R. with Goal Oriented Action Planning". www.gamasutra.com. Retrieved 29 December 2020.
- "StarCraft II". StarCraft II. Retrieved 28 February 2017.
- Bogost, Ian (2017). "'Artificial Intelligence' Has Become Meaningless." 
- 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.
- Eaton, Eric et al. (2015). "Who speaks for AI?" 
- 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.
- Kaplan, Jerry (2017). "AI's PR Problem." 
- Millington (2005). Artificial Intelligence for Games Archived 4 September 2012 at the Wayback Machine. 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.