Game AI beyond chess: ghosts, Go, poker and real-time strategy

"Game AI" means two quite different things. To researchers it means programs that try to play a game as well as possible. To game designers it means characters that make a game fun: enemies that feel clever, but not unfair. Chess sits at the point where the two meet, and looking at other games helps explain both.

Designed opponents: the ghosts in Pac-Man

Pac-Man, released in 1980, is a good place to start because its ghosts are not trying to win. Each ghost follows a small set of rules for choosing a target square. The red ghost heads for Pac-Man's current tile. The pink one aims a few tiles ahead of where Pac-Man is facing, which tends to cut him off. The cyan ghost's target depends on both Pac-Man and the red ghost, so it can pincer. The orange ghost chases when far away and wanders off when close. The ghosts also switch between "chase" and "scatter" phases on a timer, which gives the player moments to breathe.

None of that is search or learning. It is design. The rules are simple enough to run on 1980 hardware, but together they produce behaviour that players read as personality and teamwork. That is the lesson designed game AI keeps relearning: an opponent's job is to create interesting decisions for the player, not to be optimal.

A chess bot for a beginner has the same job. A perfect opponent is no fun and teaches little. We come back to that at the end.

Perfect information and search: checkers and chess

Games like checkers and chess have perfect information: both players see everything, there is no dice roll, and moves alternate. These games suit the search approach described in our piece on how chess engines think: build a tree of moves, evaluate the leaves, and back the values up with minimax and alpha-beta.

Checkers fell first. Jonathan Schaeffer's program Chinook won the man-versus-machine world title in the 1990s, and in 2007 his team announced that checkers is solved: with perfect play from both sides, the game is a draw. Chess is far too large to solve that way, but search with a good evaluation was enough for Deep Blue to beat the world champion in 1997.

Backgammon: learning from self-play, early

Backgammon adds dice, so a program cannot simply search every line. In the early 1990s Gerald Tesauro's TD-Gammon learned to evaluate backgammon positions by playing against itself and adjusting a neural network with a method called temporal-difference learning. It reached a level comparable with top human players and even changed how experts thought about some opening moves. It was a preview, decades early, of the self-play approach that would later conquer Go.

Go: when search alone was not enough

Go has perfect information too, but it resisted computers for a long time. The board is 19 by 19, a typical position has a couple of hundred legal moves, and games are long. Worse, it is very hard to write a good evaluation function: whether a group is alive or a wall is valuable depends on subtle whole-board judgement.

The first breakthrough was Monte Carlo tree search, which evaluates a position by playing many quick random or semi-random games from it and seeing who tends to win. That lifted programs to a strong amateur level. The second was deep learning. DeepMind's AlphaGo combined tree search with neural networks trained first on human games and then by self-play, and in March 2016 it beat Lee Sedol, one of the strongest players of the era, four games to one. A year later AlphaGo Zero learned from self-play alone, and AlphaZero applied the same recipe to chess and shogi.

The lesson from Go is that learned judgement can replace handwritten evaluation, and that search guided by good intuition beats search that has to consider everything.

Poker: hidden information and bluffing

Poker breaks a different assumption: you cannot see your opponent's cards. The best move depends on what they might hold, and on what they think you might hold. There is no single "position" to evaluate; there is a spread of possibilities. And a good strategy has to be unpredictable, or opponents will exploit it.

The key idea here is game theory. Methods such as counterfactual regret minimisation let a program improve a mixed strategy (one that chooses between actions with certain probabilities) by playing against itself many times and measuring how much it "regrets" not having taken other actions. Carnegie Mellon's Libratus beat top professionals at heads-up no-limit Texas hold'em in 2017, and its successor Pluribus did well against professionals in six-player games in 2019. Bluffing emerges from the maths rather than from any notion of deception.

Real-time strategy and team games

Games like StarCraft II and Dota 2 combine almost every difficulty at once: hidden information (fog of war), continuous real-time action, huge numbers of possible actions, long time horizons where an early decision matters much later, and in Dota's case teamwork between several agents.

Both were tackled with large-scale reinforcement learning. DeepMind's AlphaStar reached the top league of StarCraft II's public ladder in 2019, playing under constraints meant to keep its speed of action comparable to humans. OpenAI Five, a team of five neural-network agents, beat the reigning world champion Dota 2 team in 2019. Both needed enormous amounts of simulated play, far more than any person could ever experience.

What makes a game hard for AI?

Looking across these examples, a few properties keep coming up:

• Branching factor and length. More options per turn and longer games make exhaustive search hopeless.
• Evaluation difficulty. If it is hard to say who is winning in the middle of a game, you need either very deep search or learned intuition.
• Hidden information. Once you cannot see the whole state, you have to reason about beliefs and mix your strategies.
• Chance. Dice and card draws turn single lines into probability distributions.
• Real time and many actions. Continuous control and fast decisions multiply the space of choices.
• Several agents. Teammates and multiple opponents add coordination and negotiation.

Chess is hard for humans, but by this list it is one of the friendlier games for a computer. That is why it fell early, and why the interesting question in chess AI today is no longer "can a machine win?"

The other question: can a machine help you improve?

This is where the two meanings of game AI join up again. The strongest engine is a poor teacher on its own, for the same reason Pac-Man's ghosts are not optimal: what matters to a learner is a good experience, not a perfect opponent. A useful chess AI plays at a level where you win some and lose some, makes the kind of mistakes players at your level make, and can tell you in plain language what went wrong. We explore that more in playing an AI at your level.