Is there an equivalent of Deep Blue in the Go world?

Question

Deep Blue was a chess-playing computer developed by IBM. On May 11, 1997, the machine won a six-game match by two wins to one with three draws against world champion Garry Kasparov. Kasparov accused IBM of cheating and demanded a rematch, but IBM refused and dismantled Deep Blue. Kasparov had beaten a previous version of Deep Blue in 1996.

Is there an equivalent program that challenged and won the top Go masters (on the standard sized board)?

Is there a specific research project like this in progress?

Answer 1

AlphaGo

Now there is AlphaGo by Deep Mind, a company recently bought by Google playing currently a match against 9p Lee Sedol. It is the Deep Blue of Go.

EDIT: The final result of the match of five games was AlphaGo 4 – Lee Sedol 1. This confirms the former conjecture: AlphaGo is the Deep Blue of Go.

Answer 2

On an 19x19 board there is no computer that evens top level players (9p) as of November 2011. It seems that the strongest programs for the moment use Monte Carlo methods and from time to time matches with pro's are organised, though usually with handicap. The level reached by programs for the last couple of years seems to indicate that they need at least 7 stones handicap against a 9p player.

Amongst computers you can get an idea which programs are strongest by checking this page however that doesn't necessarily tell you very much about the strength vs human players.

Wikipedia has a quite up to date recent results section on computer vs human player go.

On senseis library there is a list of programs and if you check the pages for individual programs you find a summary of their most important matches against both humans and other bots.

Answer 3

No Go-playing program to date has been known to match the strength of professional players.

The Wikipedia article on Computer Go offers an in-depth discussion about the subject.

According to that article, as of 2011, "the best Go programs running on stock hardware are ranked as 2 dan - 5 dan."

One of the problems is the large number of possibilities.

According to the aforementioned Wikipedia article, in 2008, a program called "MoGo" won a game against a professional on a 9x9 board, but the same program lost to the same professional on a 19x19 board, despite receiving 9 handicap stones.

Answer 4

To my knowledge, no. I barely know how to play go, but I can speak to the AI side of things a bit.

Deep Blue basically uses a big ol' search tree to look many, many moves into the future, like it's testing out numerous parallel games. If a series of moves doesn't terminate in a win or loss, a unit called the "static evaluator" applies a bunch of heuristics to figure out who gains an advantage from the board state. These values then percolate up the tree and are used to decide which current move is most likely to win some advantage for the AI player.

There are two main limiting factors prohibiting a Deep-Blue-like approach to an AI for go: game complexity and hardware limitations.

The first is the inherent complexity of the game. For instance, there's "branching factor". Try to visualize a go game in progress and a chess game in progress, like you've just sat down in front of a half-played board and are trying to make your next move. Because the go board is larger you can place a stone anywhere, there are more possible moves you could make on any given turn. The set of an opponent's possible plays in response to that move is also greater, and so on and so on. This means the tree of all possible game states grows much more quickly, making it harder to look many, many moves into the future. (You can work around this somewhat with "pruning" techniques: basically write off any branches that seem like they're quickly heading off into a losing position; there's no evaluative shortcut that works as well as counting material in chess, though.)

The other is actually the rules for AI players. If I recall correctly, the major tournament organizations require AI software to run on off-the-shelf consumer hardware. Deep Blue had a supercomputer's worth of memory and processing power, including custom-built chips for performing static evaluation in hardware.

So, in essence, a go AI in the style of Deep Blue, using deep search supported by massive processing power, is infeasible. However, a go AI in the style of TD-Gammon (which essentially operates based on learned heuristics) may be. The best information I can really offer on the current state of the field is a Wikipedia link, though.

Answer 5

Is there an equivalent program that challenged and won the top Go masters (on the standard sized board)?

No. According to Wikipedia a win at 6 stone of handicap was the best result against a pro. It's quite far from an even match

Is there a specific research project like this in progress?

In fact several scientific does reasearch in computer go theory exist and the most improvement by such researcher is monte carlo tree search which enabled computers to play even against strong amateurs (5 dan) on a 19x19 board. A good overview of top research can be found in Łukasz Lew phD thesis. However maybe due to the difficulty of the task the means given to computer go is not comparable to the ones of computer chess.