Go

Posted by William M. Connolley on January 26, 2007
(7)
More »

I used to play Go at university and after, but rather dropped out when I had children. Recently I’ve started playing online again, though its a somewhat inhuman way of playing. One of the themes of those times was that computers were rubbish at Go, in contrast their chess performance (one of the problems is that its pretty hard to evaluate a go position, particularly at the start, by any kind of counting. In chess (I think) you can count pieces and locations pretty quickly). So of course we Go players took that as clear proof that Go was a more interesting game :-)

The Economist has a little article updating this a bit: here asserting that “Monte Carlo” methods enable progams to play well on small boards. It still sounds rather like brute force to me, but (guessing from the story) rather than doing all branches of the tree to a certain depth you randomly prune the tree but follow some branches to the end? Full 19×19 boards should still be safe for a while, though.

(7)
More »

Comments

  1. #1 James Annan
    2007/01/26

    Well MC methods are commonly used for all sorts of approximate counting (estimation) methods. It sounds like the key is that (unlike theory with most 2-player zero sum games) the game is complicated enough that it’s a good enough heuristic to estimate the winning probability with random moves rather than the much more challenging search for the optimal strategy against best play (minimax solution).

    What that indicates about the skill level of even decent go players is left as an exercise for the reader :-)

    [Indeed. I have the impression that human players have reached some kind of level, in that no-one gets much beyond 9-dan. What level is beyond that is unknown. I have a memory of an apocryphal quote from ages back, of a 9-dan (asked to estimate how much better it would conceivably be possible to play) saying he expected to have to give a few stones to God -W]

    I think shogi (Japanese chess) is another game where computers are relatively poor. They can’t translate Japanese either…

  2. #2 Steve Bloom
    2007/01/26

    It’s not apocryphal, although I couldn’t tell you the name after this long. He said five stones, but IMHO he was padding that by a couple of stones (although he did say beat rather than just have an even chance, so maybe that accounts for the difference). IOW, I suppose at five stones a 9-dan could be reasonably confident that the Cosmic Muffin would lose every game.

    Back when I was playing, I was told that as an amateur 4-dan I would need a five stone handicap against a pro 9-dan (although I never actually played one since I never did the pay for play stuff). I was also told that nine stones probably wouldn’t be enough to save me if the 9-dan was drunk and there was a bet on the game. :)

    Shogi has that extra layer of complexity (relative to Western chess) of capture conversions, but maybe the main difference is that the one that’s played internationally has gotten all the programming effort.

  3. #3 coby
    2007/01/26

    The big difference between chess and Go for a computer program is the branching factor, which for chess is something like 64, whereas Go it is around 360! That makes for a lot of possible board configurations at just a few moves ahead.

    While I am sure there are some very clever game state evaluations and pruning algorithms used by Deep Blue, IMO it is definately in the “brute force” category. It uses a parallel array of 1024 custom processors and searches 1 billion positions per second! I don’t expect that is how most of us humans play the game…

  4. #4 Dan Andersson
    2007/01/26

    There is a common misconception that the difference that makes Go harder than Chess is the branching factor or the game search and state space size. While it is true that it does have some impact it in itself doesn’t mean much. Counterexamples are readily available: Amazons and Backgammon have one decimal order of magnitude larger branching for example.
    The problem is arguably a matter of evaluation and recognizing quiet positions. Using MC solves both those problems but suffers from being tactically weak. Along comes the UCT search algorithm that generalizes N armed Bandit strategies over trees and is scalable with time/memory. There has been some similar work done with randomized Minimax search.

  5. #5 Eli Rabett
    2007/01/27

    Brute force Monte Carlo is a losing strategy, you need some sort of weighting to avoid wasting time on improbable starting points. In terms of Go this would involve a rapid way of paring the tree. I suspect the issue with Go is the depth of the tree rather than its width.

  6. #6 Steve Bloom
    2007/01/27

    Just to note that with a 9×9 or even 13×13 board you’re into the tactical stuff almost immediately. All the subtleties of fuseki and to a considerable extent joseki(look those up, non-players) are not present. One of the real problems for programmers might be understanding the principles by which e.g. fuseki play in one corner relates to what’s happening in the opposite corner. The top pros certainly have a feel for that, but my impression is that they don’t understand it in a way that would be helpful for programming.

  7. #7 CapitalistImperialistPig
    2007/01/29

    There used to be an annual tournament for computer go, with the champion computer playing a match with some young (13-14 yr old) 5-dan amateurs. I think they could give the strongest computer 13 or so stones.

    I’m a weak kyu player, play mostly against my old MFG program, but have trouble winning against the computer on 13×13 if I give it 3 stones. They do play elementary life and death pretty well.

    Dan has mentioned newer computer strategies. Any idea of how they stack up against today’s strong amateurs?