AI in video games: a historical evolution, from Search Trees to LLMs. Chapter 2: 1980–2000.
Introduction
Welcome to the second chapter of our ongoing series exploring the evolutionary journey of AI in video games. Our exploration began in 1950, chronicling the emergence of AI up until 1980 in this inaugural chapter.(1️⃣).
There, we delved into the foundational years of video game AI, encompassing the years 1950–1980, and examined the primary approaches of that era: Discrete Logic, Data Trees, Search Algorithms, Selective Search (Minimax, Alpha-Beta, Monte Carlo), Knowledge Bases, AI Patterns, Behaviors, Interaction Meshes, and Text-Based Gaming strategies.
If you missed the first chapter, I highly recommend reviewing it before proceeding. Your support and feedback would be greatly appreciated!
In this second installment, our journey spans from 1980 into the new millennium. This era witnessed the integration of well-established techniques from other domains into video game development, including Pathfinding Algorithms, Finite State Machines, Artificial Neural Networks, and Behaviour Trees. Unfortunately, the pace of AI development (not just limited to video games but across all domains) led to what would later be termed the First and Second AI Winters. This period was marked by setbacks caused by various failures in implementing AI effectively. We’ll also explore some noteworthy failures and missteps within the realm of video game AI, as Cheating AI and Artificial Stupidity.
So, let’s kick things off!
1981. Early Pathfinding in “Tanktics”: a headache.
Pathfinding, also known as pathing, is the computational process used by computer applications to determine the shortest route between two points. It’s a practical method for navigating mazes and complex terrains efficiently.
In our previous discussion in chapter 1️⃣, we explored the simplified approaches to pathfinding, such as those used in games like Pac-Man. In Pac-Man, decision triggers were limited to intersection tiles within the maze, avoiding the need for computationally expensive algorithms of that era.
Tanktics, initially released in 1971 and later by Avalon Hills in 1981, is a two-player tank battle computer wargame. It replicates tank battles on a large hex grid, utilizing maps from Panzer. The early version of the game lacked a Graphical User Interface (GUI), relying solely on a chat interface. Players interacted with the computer, which provided information about their positions, enemy tanks, and ongoing events within the game.
While not revolutionary in terms of graphics, Tanktics is considered a milestone in the application of pathfinding algorithms. Its creator, Chris Crawford, described how he expended a great deal of time trying to solve moving problems with pathfinding
Pathfinding heavily relies on Dijkstra’s algorithm, formulated in 1956, which plays a crucial role in determining the most efficient path on a weighted graph. It’s intricately linked to the shortest path problem in graph theory. This problem delves into the exploration of identifying the optimal route within a complex network, whether it’s the shortest, most cost-effective, or fastest path between two points.
Another remarkable example of Djikstra’s algorithm usage for pathfinding was in the 80s is Robot Odyssey (1984).
Modern iterations of pathfinding algorithms often incorporate variations of Dijkstra’s algorithm, with A* (A star) being a prominent example. A* is widely employed in gaming due to its capacity to approximate the minimum distance between two points using a heuristic, enabling the pruning of paths and optimizing computational costs.
As we discussed in the previous chapter with Search Trees, heuristics help to discard high variability and reduce the computational costs. In A*, it represents the minimum potential distance between a particular node and the endpoint. A* effectively uses this heuristic to refine its search, making informed decisions on the most promising paths and significantly reducing the computational workload.
Diablo and The Elder Scrolls II: Daggerfall (both released in 1996) were among the earliest confirmed adopters of the A* algorithm in video games.
In present times, there are numerous ongoing projects focused on integrating the A* algorithm into game development platforms like Unity and Unreal. This endeavor aims to enhance pathfinding and optimize navigation systems within game development frameworks.
Early 90’s. Finite state machines.
During the late 1980s and early 1990s, notable advancements in AI behaviors emerged, particularly in games like Tony La Russa Baseball. These games implemented AI based on an emulation of the coaching or managerial style of a selected celebrity. They stored patterns resembling a knowledge base of how a celebrity would typically play, which was then utilized to inform and select moves within the game.
Hoever, the most significant advancements in AI behaviors were achieved through the implementation of Finite State Machines, introducing greater complexity to the strategies of AI actors. An FSM, defined as a structure facilitating the creation of intricate behaviors, operates through a finite set of states and transitions to dynamically shift from one state to another based on inputs.
While various methods exist for representing FSMs, one of the most prevalent approaches involves utilizing a directed graph, often referred to as a state diagram.
Now, let’s explore a simple yet illustrative example.
In the directed graph, each node corresponds to a specific state, symbolizing an action or behavior of the actor, such as remaining idle, jumping, attacking, or running. The transition between these states is facilitated by a sequence of inputs, such as pressing keys, analyzing environment input variables, distance to player, etc. enabling the actor to move from one node to another. This transition triggers the adoption of a new behavior associated with that particular node.
FST became very popular with Real-time strategy (RTS) games as Herzog Zwei (1989) considered the first RTS game. Herzog’s system comprised a simple three-state Finite State Machine (FSM). The enemy units demonstrated a awareness of the environment, utilizing multiple listeners to continuously update inputs for the FSM. This real-time input update directly influenced and adjusted the behavior of the units, ensuring dynamic and adaptive responses based on the changing environmental cues.
Herzog Zwei was the predecessor of Dune II (1992), which laid the fundations of posterior popular games as Civilization (1991), Warcraft: Orcs and Humans (1994), Command & Conquer, Age of Empires, StarCraft and whose mechanics we are still seeing in RTS games as the fog of war, technology trees, etc.
Dune II AI had a bit more complex due to its nature as a real-time strategy game with multiple unit types and buildings. These were some of the states of their FSM, depending on the actor type:
1.Harvester Unit. (Idle, Moving to Spice Field, Harvesting, Returning to refinery, Unloading harvest)
2. Combat Unit (e.g., Soldier, Tank). (Idle, Moving to a location or enemy unit, Attacking enemy or structure, Returning to base)
3. Structure (e.g., Construction Yard, Barracks). (Idle, Building, Upgrading to a higher level).
4. Air Unit (e.g., Ornithopter). (Similar to a Combat Unit but with flying features)
The Finite State Machines (FSMs) were internally stored using state-transition tables or adjacency matrices. These tables or matrices facilitated the representation of states, transitions, and the relationships between various states within the system. This storage method streamlined the management of transitions and state changes, optimizing the efficient operation of the Finite State Machines.
If you want to know more about Finite State Machine, there is a comprehensive guide documenting the AI behind Halo 2, available here, which illustrates concepts we have already discussed:
- Actors in the world, target actors;
- A series of Input Variables coming from the Actor’s Perception of the world, used to transverse the graph;
- A series of behaviours triggered depending on those input variables. In Halo 2, they were structured in different layers, due to complexity, and also relied on some memory / persistant storage.
Several of the AI techniques we’ve discussed remain prevalent in modern games. Finite state machines (FSMs) are still widely employed and have become easily designable within Integrated Development Environments (IDEs) such as Unreal Engine and Unity. They are not only utilized for designing behaviors but also play a crucial role in shaping animations, visual effects, and sound effects within game development. The versatility of FSMs has expanded beyond behavior design to influence various facets of game development, enhancing the overall gaming experience.
Artificial Stupidity
Complex behavior trees in AI systems can inadvertently trigger what’s known as Artificial Stupidity leading to repetitive behaviors, reduced player immersion, and abnormal actions in situations unforeseen by developers.
Originally, Artificial Stupidity referred to intentional measures programmed by game designers to adjust to lower difficulty levels. This deliberate adjustment forces the AI to make suboptimal decisions on purpose. However, in modern contexts, the term also encompasses instances where complex behavior trees result in unintended and unfavorable AI behaviors, diverging from the intended gameplay experience. This divergence may lead to repetitive or unusual actions, impacting the overall quality of the gaming experience.
Cheating AI
Just like the concept of AI Stupidity there’s another intriguing idea worth exploring. Among the myriad examples, one particularly fascinating case stands out — not for its exceptional AI, but for its shortcomings. Earlier, we delved into the notion of “Artificial Stupidity,” intentionally constraining AI capabilities to cater to lower difficulty levels. However, there exists an inverse perspective.
In the early versions of various games, especially real-time strategy titles, AI opponents often resorted to cheating. This behavior stemmed from the computational limitations that made long-term decision-making practically unfeasible. Rather than being artificially handicapped, the AI in these games adopted shortcuts and cheats to simulate a greater challenge, compensating for its incapacity to execute intricate, long-term strategic maneuvers.
The phenomenon you’re describing is indeed notable in the Civilization series, particularly evident in Civilization (1991) and Civilization II (1996) . The AI’s actions, sometimes appearing overly smart and bordering on becoming a nuisance or a potential threat, often led to unexpected encounters. For instance, spawning enemy elephants seemingly out of thin air — whether at the map’s boundaries, across oceans, at the poles, in uncharted areas or even in places visible to you which you may had notice — was a vivid demonstration of asserting dominance and authority.
1996–2000. Artificial Neural Networks.
A pivotal milestone in the early 2000s marked the dawn of a new era in AI techniques: the application of Artificial Neural Networks (ANN) in video games. Neural networks had existed since 1958, primarily within research environments, following their inception by the psychologist Frank Rosenblatt of the perceptron, the first implemented artificial neural network.
Artificial neural networks (ANNs), also shortened to neural networks (NNs) or neural nets) are a branch of machine learning models that are built using principles of neuronal organization discovered by connectionism in the biological neural networks constituting animal brains.
An ANN is based on a collection of connected units or nodes called artificial neurons, which loosely model the neurons in a biological brain. Each connection, like the synapses in a biological brain, can transmit a signal to other neurons. The fundamental concept is as follows: an artificial neuron receives signals, processes these signals, and then communicates with connected neurons by utilizing activation functions.
The signal at a connection is a real number, and the output of each neuron is computed by some non-linear function of the sum of its inputs. The connections are called edges. Neurons and edges typically have a weight that adjusts as learning proceeds. The weight increases or decreases the strength of the signal at a connection. Neurons may have a threshold such that a signal is sent only if the aggregate signal crosses that threshold.
The initial layer is termed the input layer, encompassing all the input parameters relevant to the given problem. Meanwhile, the output layer is comprised of nodes representing the various potential solutions or outputs that the model aims to learn.
Typically, neurons are aggregated into layers. Different layers may perform different transformations on their inputs. Signals travel from the first layer (the input layer), to the last layer (the output layer), possibly after traversing the layers multiple times.
During the training process, a neural network adjusts its weights and biases by utilizing real tagged inputs and their corresponding expected outputs. This iterative adjustment enables the network to learn and adapt, allowing it to solve even non-linear problems by capturing complex patterns and relationships within the data. First versions of Neural Networks did not include learning processes of the weights for the input layers, stochastic gradient descent or modern techniques as backpropagation.
AI Winters
The history of Artificial Intelligence has seen cycles of hype, followed by disappointment and reduced interest known as AI winters. These periods were marked by decreased funding and skepticism towards AI research.
The concept was first discussed in 1984 when prominent AI researchers predicted a collapse due to excessive enthusiasm in the field. Major AI winters occurred around 1974–1980 and 1987–2000, with several smaller episodes due to specific project failures and funding cuts.
The main reasons for the first AI Winter to happen in the global AI arena were:
- Failure of machine translation
- Criticism of perceptrons (early, single-layer artificial neural networks)
- Frustration with Speech Understanding;
- Abandonment of certain AI projects, such as expert systems and the Fifth Generation computer project.
In particular, in the field of videogames the scenario looked as follows:
- Overpromising and underdelivering AI: There were high expectations for AI capabilities in games, promising advanced, human-like behaviors from non-player characters (NPCs). However, the actual implementations often fell short, leading to disappointment among players and developers.
- Hardware limitations: AI in games often requires significant computational power. In the past, limitations in hardware capabilities might have restricted the complexity and scale of AI that could be implemented in games.
- Cost and resource implications: Developing sophisticated AI systems can be expensive and time-consuming. Balancing the cost of implementing advanced AI with the potential returns from game sales was a concern for game developers.
- Focus on other game aspects: Sometimes, game development prioritizes other aspects such as graphics, storyline, and gameplay mechanics over AI. This could lead to AI development receiving less attention or resources, resulting in limited advancements in this area.
- Difficulty in achieving human-like AI behaviors: Creating AI that convincingly emulates human behavior, adapts to changing game environments, and remains challenging for developers. Achieving this level of complexity while maintaining game performance and responsiveness can be a significant hurdle.
2001. Neural Networks: first successful application after the second AI Winter.
However, something occurred with the approach exemplified in Creatures (1996, re-launched for PlayStation in 2001), an artificial life simulation where the user hatches small furry animals (Norns) and teaches them how to behave, or leaves them to learn on their own. It was the first successful application of Artificial Neural Networks in video games.
The creatures used this approach to learn and adapt their behavior. This game was considered a groundbreaking achievement in artificial life research, which sought to model the behavior of creatures as they interacted with their environment.
In the game, each Norn has a several layers neural network that represents its brain. This neural network is used to process inputs from the environment and determine the creature’s actions. The inputs included the presence of food, danger, or other creatures.
The connections between these neurons are strengthened or weakened over time based on the creature’s experiences, allowing it to learn and adapt to its environment. This is a form of Machine Learning known as Reinforcement Learning (we will discuss it later on), where an agent learns to make decisions by taking actions that maximize some notion of cumulative reward.
Lastly, this neural network-based approach enables the discovery of emergent behaviors. Emergent Behavior can be defined as:
… a behavior of a system that does not depend on its individual parts, but on their relationships to one another. An emergent behavior cannot be predicted by examination of a system’s individual parts. It can only be predicted, managed, or controlled by understanding the parts and their relationships.
Certainly, neural networks enabled the programming of intricate behavior patterns that aren’t solely reliant on straightforward input-output relationships. This capability empowered Creatures to render each Norn (in-game creature) as a unique entity, capable of surprising players with its behavior. If you’re interested in delving deeper into the history of “real AI” in video games, I recommend watching the following video.
Want to know more?
Stay tunned for the next chapter, where we will be discussing the period after 2000 , a very fruitful period of AI improvements which include the first NLP-based games, Behaviour Collections, Behaviour Trees, Procedural Generation, Reinforcement Learning (a.k.a Adaptative AI), Large Language Models and DLSS (Deep Learning Super Sampling).
About me
My name is Juan Martinez, I’m a Sr. AI engineer who was been working in the field of NLP for about 15 years now. I’m now focused on Video Games Development and specially in the intersection between Video Games and AI. If you are in the video games arena or you just want to say hi, I’m happy to connect in LinkedIn !
