Re: computer-go: Complexity & SW

[Heikki Levanto <heikki@xxxxxx>]

Fred Hapgood <hapgood@xxxxxxxxxxxxxxxxx> wrote:


> 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.

I do not know of chess, but you are right, plausible move determination,
position representation, and especially evaluation are what go is all about.


> 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.  

I would say that we do not even begin to understand how humans play go. Your
assumption of pattern matching has obviously something to do with it, but is
not at all the whole story.

> 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.

You seem to imply that this applies to all games. Obviously it does not
apply to purely random games, nor to running. Also, it is far from
sufficient to "have" the better patterns, if one can not use them. Make a
beginner play with a joseki dictionary, and see what a bad opening he is
likely to play anyway.


> This is how both go and chess programming works: finding a better 
> set of patterns than those driving the last rev. 

Or better plauisble move determination, or better position evaluation, 
or better position representation. Or just better implementation of old 
known algorithms. Or something else.

> 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 can see some:
  - It is possible to play chess with a simple evaluation function,
    even down to just counting pieces. Not master-level chess perhaps,
    but a reasonable game. There is no such simplistic evaluation function
    for go. If you do not know the life status of each group, there is
    no way you can get any decent evaluation of the situation.
  - Go has so much larger branching factor that global look-ahead can not be
    done to any serious depth. In many positions there are many plausible
    moves to consider.


> (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.)

Actually, many go programs do not look even one ply ahead. Not globally,
that is. They analyze the position, and in that they do lots of tactical
reading. Then from this analysis they propose a move. And yes, they do beat
rank beginners, and even a bit better than that. 


> 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.  

Has it? Of course many man-years have been invested in computer chess,
especially in the western world. Does anyone have hard facts on how much
effort the Japanese, Chinese, Koreans, and others, have invested in computer
go? At least for human playing, go theory seems to be an old and well
established field with a lot of publications. Most of them unaccessible to
us westerners.


> 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. 

You seem awfully confident of knowing how the ideal go program should work.
If you are so sure, how come your program hasn't beaten the world yet?

- Heikki



-- 
Heikki Levanto     LSD Levanto Software Development   heikki@xxxxxxxxxxxxxxxxx
               "In Murphy we Turst"