Take the 2-minute tour ×
Board & Card Games Stack Exchange is a question and answer site for people who like playing board games, designing board games or modifying the rules of existing board games. It's 100% free, no registration required.

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?

share|improve this question
1  
Off topic: I found Kasparov's argument for cheating truly compelling when I read about it years ago, but I guess we'll never know the truth! –  dr Hannibal Lecter Nov 12 '11 at 14:30
1  
Perhaps you could make the question a bit more specific by asking what's the highest ranking any bot has ever reached to date –  hasen j Nov 13 '11 at 10:12

4 Answers 4

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.

share|improve this answer
4  
No professional player can give 7 stones to another professional player. A professional 9-dan would most likely lose a game against a professional 1-dan at two stones, assuming the professional 1-dan is reasonably young. The top 7-dan amateurs can utterly annihilate professional 9-dans at 3 stones, for that matter. –  Laval Nov 12 '11 at 21:26
1  
Not sure how you got 1p-2p from being 7 stones below 9p. This would put them in the middle amateur dans, with is consistent with their results on KGS. –  CodesInChaos Nov 13 '11 at 14:20
    
I'll follow up your links, it seems like the answer is No -not for standard board sizes. –  Forkrul Assail Nov 13 '11 at 23:03
    
yes, sorry, my answer talks about 19x19. I am not an expert on the handicap professionals can give each other. In principle one dan of difference means you can have an "even" game with one stone of handicap. Maybe in practice that is not the case. If some definite conclusion about this is given here, I will update the answer. –  ufotds Nov 13 '11 at 23:07
3  
1 handicap stone = 1 rank only applies to amateur ranks. Professional ranks are much closer. Perhaps 2 stones from top pro to weak pro. And pro-dans aren't a direct reflection of strength. I'd see them more as achievements which get awarded for good tournament results. "BillSpight: The traditional pro handicapping made a difference of three ranks per stone. However, with the new (post-WWII) pro rankings, there seems to be a two-stone difference between 9-dans and shodans, which translates to about 1/4 stone per rank." –  CodesInChaos Nov 13 '11 at 23:46

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.

share|improve this answer
    
Thanks, I noted that on the computer go wiki page. Was hoping for more research based answers. Good answer otherwise.Thanks. –  Forkrul Assail Nov 13 '11 at 23:00

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.