Re: computer-go: Complexity & SW

["Fred Hapgood" <hapgood@xxxxxxxxx>]

> 
> > I suspect that if the number of man-years and master involvement
> > invested in go as opposed to chess had been reversed, today we would
> > be seeing computer go programs playing at 3 or 4 dan and computer
> > chess software struggling along with USCF ratings of around 1750.
> 
> I suspect this would not at all be the case. As far as I can see
> (which is not very far), the key to "solving" chess has been that it
> can be solved with brute force (or relatively brute quite-much-force).
> It is of course tempting to speculate that something as powerful would
> have been found for go. But so far we don't even know where to look
> for such a solution...

The fraction of total processing power devoted to full-width 
searching (brute force) in chess software has been falling for 
nearly 25 years. While I would not bet the house on this,
I am 80% sure that most cycles in high-level programs (commercial, 
as opposes to student) go to stuff like plausible move determination, 
position evaluation, and position representation. All this is exactly 
what go programming is about.

The intrinsic complexity of a game -- the number of possible moves,
the number of positions -- has zip to do with the difficulty of making 
a reasonably strong program. Humans play games by learning some 
number of patterns and then using those patterns to probe the 
nature of real positions. When two people play, the one with best set 
of patterns wins, usually.  This is true regardless of how complex the 
game is. If a game has a complexity rating of X, the guy with the 
better patterns wins.  If the game has a complexity rating of x^100, 
the guy with the better patterns wins.  How hard God would find the 
games is not to the point.

This is how both go and chess programming works: finding a better 
set of patterns than those driving the last rev. I see nothing about 
chess to lead me to think that the task of building a machine good 
enough to beat a chess master is any easier than building one to 
beat a 1 dan amateur.  (I would agree that a chess program could 
conceivably win a game or two against a rank beginner using only 1 
or 2 ply searches, which a go program could not, but that isn't
relevant to anything.) 

Possibly slightly more processing power should be allocated to full-
width searching in the case of chess, but the distinction would be on 
the order of 10% (go) versus 25% (chess) or something like that.  
An inconsequential difference. 

What matters is that chess has attracted hundreds of man-years 
more development time than go, and that advantage has proved 
overwhelming, as one would expect it would.  

  
.








> 
> > If someone was to offer a a million dollar prize for a program that
> > could play 1 dan (amateur) I'm sure it would be delivered in two or
> > three years, regardless of how complex GO is in any ultimate sense.
> 
> I think the Ing price was a considerable amount of money (something in
> that neighbourhod), and it was available for several years. Its
> requirement was to beat a junior champion (or Taiwan?), corresponding
> to (say) 4 dan amateur. The prize expired this year, but it had been
> up for quite some time. I don't think anyone seriously believed it
> coule be claimed.  (Someone with all the facts, please fill in and
> correct my mistakes!)
> 
> No, I believe that go is fundamentally more difficult to program than
> chess. At least on today's computers and todays computer science...
> That is why it is such a challenge!
> 
> 
> Regards
>  Heikki
> 
> 
> 
> 
> 
> -- 
> Heikki Levanto     LSD Levanto Software Development   heikki@xxxxxxxxxxxxxxxxx
>                "In Murphy we Turst"
> 
> 


www.pobox.com/~fhapgood