Game-playing AI: from chess search to self-play reinforcement learning
Game-playing AI evolved from brute-force search in chess to systems that learn by playing themselves. Deep Blue used parallel search and handcrafted evaluation. AlphaGo combined neural networks with reinforcement learning, while AlphaZero and MuZero removed the need for human knowledge and even game rules.
Early brute force: Deep Blue
IBM's Deep Blue became the first computer system to defeat a reigning world chess champion under standard tournament time controls, beating Garry Kasparov. The system used 32 processors and could evaluate 200 million chess positions per second, as described in IBM's Deep Blue history.
Deep Blue relied on brute force computation and handcrafted evaluation functions. It did not learn from experience. Its success showed that massive parallel search could match human expertise in a specific domain.
The victory was a milestone in computing and AI. It demonstrated that a specialized machine could outperform a human expert in a complex combinatorial game, and it also advanced the ability of supercomputers to handle calculations in fields such as pharmaceuticals and finance.
Deep reinforcement learning at Atari
The paper 'Playing Atari with Deep Reinforcement Learning' described a deep learning model that learned control policies directly from high-dimensional sensory input using reinforcement learning, without relying on handcrafted features the Atari reinforcement learning paper.
The model used a convolutional neural network trained with a variant of Q-learning. Its input was raw pixels and its output was a value function estimating future rewards. The method applied to seven Atari 2600 games without adjusting the architecture or algorithm, outperforming all previous approaches on six of the games and surpassing a human expert on three.
This work showed that deep reinforcement learning could learn from raw sensory data without handcrafted features, opening a path for agents to learn complex tasks directly from experience.
AlphaGo: combining search and learning
Go was a grand challenge for AI because of its complexity. The Google DeepMind research page on AlphaGo notes that the game has roughly 10 to the power of 170 possible board configurations, far more than chess the AlphaGo research page.
AlphaGo combined deep neural networks with advanced search algorithms. One neural network, the policy network, selects the next move. Another, the value network, predicts the winner of the game. Initially, AlphaGo learned from thousands of expert games, then improved through reinforcement learning by playing against itself.
AlphaGo then competed against legendary Go player Lee Sedol, winning 4-1 in a match watched by over 200 million people. During the games, it played inventive moves that upended centuries of traditional wisdom, including one with a 1 in 10,000 chance of being played.
Self-play and learned models: AlphaZero and MuZero
AlphaZero generalized the approach to achieve superhuman performance in chess, shogi, and Go, starting from random play and given no domain knowledge except the game rules. The arXiv paper 'Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm' reports that within 24 hours, AlphaZero reached a superhuman level in all three games and convincingly defeated a world-champion program in each the AlphaZero paper.
Unlike AlphaGo, AlphaZero did not learn from human games. Its neural network received only the rules and then learned by playing itself millions of times using reinforcement learning. The AlphaZero and MuZero research page explains that AlphaZero mastered chess in 9 hours, shogi in 12 hours, and Go in 13 days, and developed a dynamic, unconventional style the AlphaZero and MuZero research page.
MuZero goes one step further. It learns a model of its environment and uses that model to plan, without being told the rules of any game. The arXiv paper 'Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model' describes how MuZero predicts the reward, the action-selection policy, and the value function. When evaluated on 57 Atari games, it achieved a new state of the art, and in Go, chess, and shogi it matched the superhuman performance of AlphaZero the MuZero paper.
These systems show that a single algorithm can learn to discover new knowledge in a range of settings. Their successors have been used to find faster sorting and hashing algorithms and to compress video more efficiently, demonstrating that game-playing AI has practical applications beyond games.
| System | Approach | Prior knowledge | Notable result |
|---|---|---|---|
| Deep Blue | Brute force search | Chess rules and handcrafted evaluation | Defeated world champion Kasparov |
| DQN | Deep Q-learning from raw pixels | None for Atari games | Surpassed human expert on three Atari games |
| AlphaGo | Policy and value networks with search | Learned from expert games then self-play | Defeated Lee Sedol in Go |
| AlphaZero | Self-play from scratch with rules | Game rules only | Superhuman in chess, shogi, and Go within 24 hours |
| MuZero | Learned model for planning | No game rules given | Matched AlphaZero in board games and new state of the art in Atari |
Frequently asked questions
Why is Go harder for AI than chess?
Go has roughly 10 to the power of 170 possible board configurations, far more than chess, making brute force search infeasible.
What is reinforcement learning in games?
Reinforcement learning is a method where an agent learns by trial and error, receiving rewards and adjusting its decisions to improve performance over time.
How did AlphaZero differ from AlphaGo?
AlphaZero learned from scratch using only the game rules and self-play, without training on human expert games.
What does MuZero learn that AlphaZero does not?
MuZero learns a model of the environment to plan, so it does not need to be given the rules of the game.
What real-world uses have come from game-playing AI?
Newer versions of these algorithms have discovered faster sorting and hashing algorithms and improved video compression, showing their potential beyond games.