Arimaa Forum - Print Page


    
      
        Arimaa Forum
        (http://arimaa.com/arimaa/forum/cgi/YaBB.cgi)
      

        Arimaa >> Off Topic Discussion >> Cracking Go by Brute Force
        
(Message started by: Fritzlein on Oct 26^th, 2007, 4:37pm)

Title: Cracking Go by Brute Force
Post by Fritzlein on Oct 26^th, 2007, 4:37pm

The man who built Deep Blue is at it again. He claims there can be a brute-force computer Go champion ten years from now. http://www.spectrum.ieee.org/oct07/5552

If branching factor is the only issue, then to search as deeply for Go as Deep Blue did for chess requires "only" a speedup of a million. A million is 10^6 = 2^20, so twenty doublings of processing power. A gap of twenty years between the computers conquering chess and computers conquering Go does not seem outlandish. On that score Hsu can perhaps convince me.

But I remain very skeptical about the evaluation of terminal nodes in a search tree. The static evaluation of chess positions by Deep Blue was reasonably good. Right now the static evaluation of Go positions by computers is terrible. I don't understand how grafting one portion of the search tree onto another place will fix this.

Also, he anticipates alpha-beta pruning plus recursive null-move pruning effectively quadruples search depth. I know that for alpha-beta pruning to work the move-ordering must be good, and I suppose the same is true for recursive null-move pruning. But where does the good move-ordering come from?

I have to say that despite Microsoft potentially funding this research to the tune of millions of dollars, I expect the some developer to win the Arimaa Challenge long before Go falls to computers.

Title: Re: Cracking Go by Brute Force
Post by chessandgo on Oct 27^th, 2007, 3:43am

Hey, thanks for the link. Needless to say, I would gladly bet with Mr Hsu that humans will still be a long shot better than computers in a decade, but it would be great to see computer programs play well at go.

And indeed, this is quite bad news for the safety of the arimaa challenge ... seems like we will have to work hard to make it hold :)