Computer Go

Computer Go is the project of making a machine play Go well.

6 frameworks, from 1965 to today · Go · Games

still a working view ended · each leads to its entry below

Overview

Computer Go is the project of making a machine play Go well1. It matters out of proportion to the game's modest commercial footprint because Go resisted computation longer than almost any other classic board game. Chess fell to Deep Blue in 1997; Go's best programs were still losing to strong amateurs nearly two decades later. The reason is structural. Go's branching factor — the number of legal moves at a typical position — is around 250, against roughly 35 in chess, and games run to 200–300 moves. Brute-force search, the engine of chess computing, drowns in that1. Worse, Go positions are hard to evaluate: unlike chess material, the value of a Go position is a subtle judgment about territory, influence, and life and death that strong players read intuitively12. Computer Go's history is the history of trying to solve those two problems — search and evaluation — and of the moment when machine learning dissolved the distinction between them.

Early programs and the heuristic era (1960s–1980s)

The first Go programs appeared in the 1960s, written by researchers testing ideas about machine intelligence1. Early efforts played on small boards and were weak, but they established the basic architecture that would dominate for decades: a program that generated candidate moves, evaluated the resulting positions with hand-coded rules, and searched a few moves ahead. The evaluation was the hard part. Programmers encoded Go knowledge as heuristics — rules of thumb such as "extend from a wall," "capture a stone in atari," "prefer moves near the edge in the endgame."1 This is what the field calls knowledge-based Go: the attempt to write down, in code, what human players know1.

The approach had a natural appeal and a natural ceiling. Go knowledge is vast, much of it tacit, and often context-dependent; a heuristic that helps in one position misleads in another. Programs improved through the 1970s and 1980s, and the first computer Go tournaments began — the US Computer Go Championship dates from the late 1970s, and international events followed. But progress was slow, and the gap to human strength remained enormous.

Alpha-beta search and its limits (1980s–1990s)

The standard search method of the era was alpha-beta search, a refinement of minimax that prunes branches of the game tree that cannot affect the result3. In chess it was transformative. In Go it struggled1. Alpha-beta search needs a reliable evaluation function to prune well, and Go evaluation was unreliable; it also needs a manageable branching factor, and Go's was not1. Programs that searched deeply in Go often searched deeply into nonsense. The best programs of the 1990s were still far below dan-level amateur strength, and many researchers concluded that Go would not yield to the methods that had conquered chess1.

A partial exception was the endgame. In the late game, when the board is nearly settled, the position becomes tractable, and programs using combinatorial game theory and alpha-beta methods could play the yose (endgame) at respectable strength. This suggested a pattern that would recur: Go is not uniformly hard, and progress came from attacking its tractable parts.

Monte Carlo methods and the MCTS revolution (2006–2010s)

The turning point came from an unexpected direction. Instead of evaluating positions with hand-coded rules, a program could sample them: play out the position many times with random or lightly guided moves to the end of the game, and average the results1. This is Monte Carlo evaluation, and its great virtue is that it needs no evaluation function at all — the playouts supply the estimate1. Its weakness is variance: random playouts are noisy, and early Monte Carlo Go programs were weak1.

The decisive idea was to combine sampling with search. Monte Carlo tree search (MCTS) builds a search tree incrementally, allocating more playouts to promising branches and balancing exploration against exploitation14. The key algorithm, Upper Confidence Bounds applied to Trees (UCT), was introduced in 2006 by Levente Kocsis and Csaba Szepesvári, and applied to Go almost immediately by Rémi Coulom and others. The effect was dramatic. Within a few years, MCTS programs leapt past the previous generation; by around 2008–2010, programs like MoGo and Crazy Stone were playing at strong amateur level on 9×9 boards and improving rapidly on 19×191. MCTS did not need to know what a good Go move was; it needed only to try many moves and let the statistics sort them out.

MCTS programs still benefited from Go knowledge — better playout policies, patterns learned from game records, and hand-tuned move priors all helped — but the balance had shifted1. The search was doing the work that heuristics had done before.

Neural networks and the AlphaGo breakthrough (2015–2017)

MCTS had a remaining weakness: the playouts were still guided by relatively crude policies, and the evaluation of a position was still a statistical average over noisy simulations1. The next step replaced both with learned functions. Neural-network evaluation and policy learning means training a network to do two jobs: a policy network that predicts which moves a strong player would consider, and a value network that estimates who is winning from a position2. The policy network narrows the search; the value network replaces the noisy playout average with a learned judgment2.

The landmark was AlphaGo, developed by DeepMind and announced in 2015. Its first version combined MCTS with policy and value networks trained on human game records, and in October 2015 it defeated Fan Hui, the European professional champion — the first time a computer beat a professional Go player without handicap12. In March 2016, AlphaGo defeated Lee Sedol, one of the strongest players in the world, four games to one. The match was a global event, and Lee's single win in game four — a brilliant, unexpected move — became one of the most discussed games in Go history.

AlphaGo's successor, AlphaGo Zero (2017), removed the human game records entirely15. It learned from self-play reinforcement learning: starting from random play, it played against itself, and the results of those games were used to improve the policy and value networks, which in turn generated better self-play. This is the idea that a system can bootstrap its own skill without human examples, using only the rules of the game and the outcome of wins and losses65. AlphaGo Zero surpassed the version trained on human data, and its successor AlphaZero extended the method to chess and shogi15. The lesson was that in Go, human knowledge, however deep, was not the ceiling — it was a starting point that could be surpassed.

The engine era and the present

Since 2017, the strongest Go players in the world have been programs. Open-source engines such as Leela Zero, built on the AlphaGo Zero approach and trained by distributed volunteer computing, and KataGo, which added efficient search and support for variable rules and komi, became widely available. Professional players now study engine games and engine evaluations; the joseki (corner sequences) and opening patterns of the pre-engine era have been revised, and some have been abandoned. The engine's judgment — its win-rate estimates and its preferred moves — has become a reference point in professional study, much as chess engines became for chess.

The field's open questions are no longer about whether machines can play Go well. They concern efficiency (how little computation is needed to reach strong play), generalization (how the methods transfer to other games and to real-world problems), interpretability (what the networks have learned and why they choose the moves they do), and the human side: how professional Go culture absorbs and adapts to a game whose strongest authorities are now machines. The history of Computer Go is, in that sense, still being played out.

References

  1. Computer Go (introduction, Minimax tree search, Challenges for strategy and performance for classic AIs, Early decades, Knowledge-based systems, System design, Overview and history, Monte-Carlo methods, 2007–2014: Monte Carlo tree search, 2015 onwards: The deep learning era), Wikipedia
  2. AlphaGo (History, introduction), Wikipedia
  3. Alpha–beta pruning, Wikipedia
  4. Monte Carlo tree search, Wikipedia
  5. AlphaGo Zero, Wikipedia
  6. Self-play, Wikipedia

The frameworks of Computer Go

Each framework is a way of working the field has used: when it held, and the question it answers.

  1. 1965-2005

    Knowledge-based Go

    How can human Go knowledge be encoded as rules?

    Fly to its tower in Nousfarer

  2. 1980-2000

    Alpha–beta pruning

    How can game trees be searched efficiently?

    Fly to its tower in Nousfarer

  3. 2015-Present

    Neural-network policy and value learning

    How can neural networks learn to evaluate and select moves?

    Fly to its tower in Nousfarer

  4. 2017-Present

    Open-source engine ecosystem

    How can strong Go engines be built and shared openly?

    Fly to its tower in Nousfarer

  5. 2017-Present

    Self-play reinforcement learning

    Can a system learn complex skills without human examples?

    Fly to its tower in Nousfarer

How the ideas connect

Each arrow runs from an earlier idea to the later one it shaped. The list below says what passed between them.

Knowledge-based GoAlpha–beta pruningMonte Carlo tree searchNeural-network policy and value learn…Open-source engine ecosystemSelf-play reinforcement learning

Beyond the field

Where Computer Go's ideas came from in other fields, and what they led to there: the strongest 12 of 17 links.

A city in Nousfarer: a red-carpeted stair climbing terraces to a crowned tower on an acropolis, more towers round it, forest and snowy mountains beyond.
A city in Nousfarer, the game played in the browser.

Computer Go is a planet in Nousfarer

Its city has a tower for each of these 6 frameworks. Land, walk in, and climb one concept at a time.

Land on Computer Go

Related fields

Fields its ideas are linked to

More in Go

See where Computer Go sits on the Map of Human Knowledge