The History of Game AI, from Checkers Programs to AlphaGo and Generative AI
Seventy years of game AI, from Arthur Samuel's checkers program in the 1950s and Pac-Man's ghost personalities to Halo 2's behavior trees, F.E.A.R.'s GOAP, Left 4 Dead's AI Director, Deep Blue, AlphaGo, AlphaStar, OpenAI Five, how janggi and Go apps tune difficulty, and generative AI in game development.
Games and artificial intelligence have been intertwined from the very beginning. To show that a computer could "think," nothing worked better than a game like checkers or chess, where the rules are clear and the outcome is unambiguous. Researchers in the 1950s coined the phrase "machine learning" while building a checkers program, and research labs in the 2010s proved their methods on Go and StarCraft for the same reason.
At the same time, the enemies that face the player inside a game, the companions who move alongside them, and the invisible director who adjusts the mood to the situation are all called "game AI" too. The goal here is not to become the strongest player in the world. It is to be just smart enough, and just sloppy enough, for the player to have fun.
This post follows these two threads, AI that tries to conquer games and AI that makes games fun, side by side. We start with the checkers program of the 1950s, move through Pac-Man's ghosts in 1980, the behavior trees and planning techniques of the 2000s, Deep Blue in 1997 and AlphaGo in 2016, and end with the generative AI now used in game development. Along the way we also look at how the AI opponents in janggi and Go apps choose their moves and adjust their difficulty.
The 1950s: A Computer That Plays Checkers, and the Phrase "Machine Learning"
IBM researcher Arthur Samuel started writing a checkers program on the IBM 701 computer in 1952. The program was demonstrated on television in 1956 and kept improving after that.
Samuel's program matters not simply because it could play checkers. It played game after game against itself and adjusted the weights in its own evaluation function as it went. Samuel described this approach in a 1959 paper and used the phrase "machine learning," which today names an entire field of artificial intelligence. In 1962 the program also won a game against Robert Nealey, a Connecticut state checkers champion.
Around the same time, Claude Shannon's 1950 paper "Programming a Computer for Playing Chess" laid out the basic framework of search: spreading possible moves out like a tree and evaluating them. Looking several moves ahead, assuming the opponent always picks the move worst for you, and choosing the best move on that basis is called minimax, and cutting off branches that do not need examining is alpha-beta pruning. Together they formed the backbone of board game AI for decades.
1980: The Personalities of Pac-Man's Four Ghosts
Arcade games had AI too. The four ghosts in Namco's Pac-Man (1980) are the most frequently cited example in the history of game AI. The four differ not only in color but in the rule each one uses to pick its target.
| Ghost | Color | How it picks its target |
|---|---|---|
| Blinky | Red | Chases Pac-Man's current position directly |
| Pinky | Pink | Aims a few tiles ahead of Pac-Man to cut him off |
| Inky | Cyan | Combines Pac-Man's position and Blinky's position to set its target |
| Clyde | Orange | Chases when far away, but retreats to his own corner when he gets close |
On top of this, the whole group alternates over time between a "chase mode," where every ghost pursues Pac-Man, and a "scatter mode," where each one heads to its own corner. Each rule is extremely simple, but when the four overlap the player feels surrounded. And because the rules are fixed, skilled players can read the ghosts' movement and build "patterns." That balance, an enemy that is predictable yet threatening, is still the standard for good enemy AI today.
From Finite State Machines to Behavior Trees
Most enemies in the 3D shooters of the 1990s ran on finite state machines (FSMs). An enemy is in one of a handful of states, such as "patrolling," "player spotted," "attacking," or "fleeing," and moves to another state when a given condition is met. Pac-Man's chase and scatter modes are an example of such a state machine.
FSMs are easy to understand and easy to build, but once the number of states grows into the dozens, the transitions between them tangle into a web that is hard to touch. The technique that spread widely to solve this problem is the behavior tree.
A behavior tree organizes an enemy's behavior in the shape of a tree. From the top you descend through branches with rules like "try this first, and if it fails try the next" or "do all of these in order," and the leaves at the bottom hold the actual actions, such as "move to cover" or "throw a grenade." Because behaviors are broken into pieces, it is easy to attach a new one or change their order.
The game that made behavior trees famous in the industry was Bungie's Halo 2 (2004). Bungie AI programmer Damian Isla presented at the 2005 Game Developers Conference (GDC) on how the team handled the growing complexity of Halo 2's enemy AI, and after that talk behavior trees became a standard tool in shooters and action games. Today Unreal Engine ships with a behavior tree editor built in.
2005: The Planning Enemies of F.E.A.R.
The enemy soldiers in F.E.A.R., the first-person shooter released by Monolith Productions in 2005, surprised players at the time. They flanked around the side, knocked over desks to create cover, and shouted out when a comrade went down.
The secret was a technique called GOAP (Goal-Oriented Action Planning). Developer Jeff Orkin adapted STRIPS, a classic planning technique from the Stanford Research Institute in 1971, to fit games. Where an FSM or a behavior tree has the designer write down in advance "in this situation, do this," GOAP gives the enemy only a goal ("kill the player") and a set of available actions ("move to cover," "fire," "reload," each with its conditions and effects), and lets the enemy compute for itself the sequence of actions that reaches the goal in the current situation.
Since the designer no longer has to write out every combination of actions, enemies move in sequences the designer never anticipated. Much of the "intelligence" players perceived was really a few simple actions chained differently each time. Add the staging of enemies calling out the situation to each other over the radio, and they appeared to cooperate far more tightly than they actually did.
2008: The AI Director of Left 4 Dead
Some AI controls not individual enemies but the flow of the whole game. The best-known example is the AI Director in Left 4 Dead, the cooperative zombie shooter Valve released in 2008.
The AI Director watches the players constantly. It looks at how much health they have left, how much damage they have recently taken, and how closely they are grouped, and estimates each player's "intensity." If tension stays high, it holds the zombie hordes back for a moment to give the players room to breathe; if things stay quiet for too long, it sends a horde or brings out a special infected. The placement of items and weapons also changes from one playthrough to the next.
The purpose of this design is not to beat the players but to create a rhythm of tension and release, like a film. Because the same map becomes a different experience each time, the replay value of cooperative play rose sharply. Many games since have added an AI in this "director" role.
Deep Blue in 1997, AlphaGo in 2016: Surpassing the Best Humans
Let us return to the "AI that conquers games." In May 1997, IBM's chess computer Deep Blue defeated world champion Garry Kasparov 3.5 to 2.5 in a six-game match. Kasparov had won their first match a year earlier in 1996, so the rematch reversed the result. Deep Blue won through the power of search, using dedicated chess chips to evaluate hundreds of millions of positions per second. It was the road Shannon and Samuel had paved in the 1950s, pushed to its limit.
Go was different. The board is larger than a chessboard and there are far more places to play at each move, so it was long believed that the same approach could not beat a human professional. From around 2006, Monte Carlo tree search (MCTS), which finds promising moves by accumulating the results of random playouts to the end of the game, was adopted in Go programs and raised their strength considerably, but a gap to professional players remained.
Google DeepMind's AlphaGo added deep neural networks to this. It trained one network to predict "the next move" from human game records and another to evaluate "how favorable this position is," strengthened them through self-play, and then used them to narrow the branches MCTS would explore. In October 2015 it beat European champion Fan Hui 5 to 0, and in March 2016 in Seoul it beat Lee Sedol 9-dan 4 to 1. In 2017 came AlphaGo Zero, which learned from self-play alone using only the rules and no human records, and at the end of the same year AlphaZero, which learned chess, shogi, and Go with a single method.
If Deep Blue was "human-designed evaluation plus massive search," AlphaGo was "self-learned evaluation plus narrowed search." That difference changed the direction of game AI research afterwards.
2019: StarCraft II and Dota 2, into Real-Time Games
After board games, the next target was real-time strategy. There are no turns, the opponent's screen is hidden, hundreds of units must be handled at once, and a single match demands thousands of decisions over tens of minutes.
DeepMind's AlphaStar took on StarCraft II. In December 2018 it won a series of closed matches against professional players TLO and MaNa, and the results were made public in January 2019. A paper published in the journal Nature in October 2019 reported that AlphaStar had joined the Battle.net ladder under the same conditions as ordinary players and reached the Grandmaster tier with all three races. It first learned from human game records, then grew stronger as many agents with different strategies competed against each other in a league.
OpenAI's OpenAI Five took on Dota 2, a five-versus-five team game. It lost to professional teams at The International world championship in 2018, but in April 2019 it beat OG, the reigning world champion team, 2 to 0. Five neural networks had learned through an enormous volume of self-play against each other.
Both cases left an important lesson beyond "it beat humans." There was debate that the comparison is not fair unless the AI's reaction speed and number of actions are limited to human levels, and AlphaStar was in fact evaluated with limits on actions per minute and camera switching.
How the AI Opponent in a Janggi or Go App Plays
The AI opponent you meet when playing janggi or Go on a smartphone is a smaller version of the technology above. The principles fall broadly into two kinds.
Search-based. Like the chess engine Stockfish, it spreads out the possible moves from the current position, looks several moves ahead, scores the results with an evaluation function, and picks the best move. This approach fits games like janggi well, where the value of pieces and positions is relatively clear. Since 2020 Stockfish has also used a small neural network (NNUE) in its evaluation function, so the line between search and neural networks is steadily blurring.
Neural network and MCTS-based. There are open-source projects that reimplement the AlphaGo Zero approach publicly, and many Go apps adopt these engines. The network shortlists "places worth playing," and MCTS examines those places in depth.
So how is difficulty adjusted? An AI that only plays the strongest move is no fun for a beginner, so you need mechanisms to weaken it deliberately. Common methods include the following.
- Limiting search depth: reduce how many moves ahead it looks. A shallow search misses moves that lie far ahead.
- Limiting thinking time: in MCTS-style engines, reducing the number of simulations weakens the engine naturally.
- Making deliberate mistakes: pick probabilistically among the top few moves instead of the best one, or mix random noise into the evaluation scores. The UCI protocol used by chess engines includes an option where you specify a target rating and the engine lowers its strength to that level.
- Limiting knowledge: disable the opening book or the endgame database.
The key to good difficulty tuning is "weak, but not stupid." If you only reduce search depth, the AI tends to make absurd blunders like simply handing over a piece right in front of it. So a well-made app mixes several methods so that major mistakes are prevented while only minor judgments waver. The "rubber-band" adjustment in racing games that speeds up a car that has fallen behind, and changing enemy accuracy in a first-person shooter to match the player's skill, are the same idea. As with Pac-Man's ghosts in 1980, the opponent that is loved longest is the one that is just smart enough for the player to beat.
KEKE STUDIO's 3D Action Janggi is also built so you can play against a search-based AI of this kind, letting you play a full game alone alongside the battle scenes that unfold whenever pieces clash.
Today: Generative AI Is Used to Make Games
In the 2020s, the center of gravity in game AI has been shifting from "AI that plays" to "AI that makes." Large language models and image generation models have begun entering the game development process.
- Dialogue generation: at GDC 2023, Ubisoft showed Ghostwriter, an internal tool that drafts the short situational lines NPCs blurt out, for writers to refine.
- Conversational NPCs: in 2023 NVIDIA announced ACE, a technology that bundles speech recognition, a language model, speech synthesis, and facial animation to create characters that converse freely with the player.
- World-generating models: in 2024 Google DeepMind unveiled Genie 2, which produces a controllable 3D environment from a single image or a short description. It is still at the research stage, but it points toward generating game environments themselves.
- Disclosure rules: in January 2024 Valve introduced a policy requiring developers submitting games to Steam to disclose how generative AI was used during development and at runtime.
Alongside these, generative AI is also widely used in less visible places such as writing code, generating textures and sound effects, translation, and test automation. At the same time, debate over creators' rights, the provenance of training data, and the quality of generated output is growing, and the industry is still working out its rules.
Seventy years ago, when a checkers program taught itself and beat a human, the next targets were chess and Go. Today AI has moved beyond winning games to the point of making them. But as Pac-Man's ghosts showed, the real goal of game AI has always been the same: to make the player want "one more game."
