Re: computer-go: Complexity & SW

[William Harold Newman <william.newman@xxxxxxxxxxx>]

On Sun, Sep 10, 2000 at 05:48:08PM -0400, Fred Hapgood wrote:

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

I mostly agree with this. In particular, it's easy to construct
soluble games (e.g. Nim) which have arbitrarily large numbers of moves
or positions. However, a game does need to have a large number of moves
and positions in order to avoid solution by brute force. Even some
games which are interesting to humans can now be solved by brute force 
-- Nine-Men-Morris, if I remember the name correctly, is one.

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

IMHO, there is more to it than that. Humans do well at games which fit
with our built-in accelerated hardware support for spatial
relationships, visual pattern recognition, temporal planning, and
perhaps other things we don't understand yet. Some games aren't a
particularly good fit, although most of them don't have names because
people don't enjoy them. However, people do enjoy Othello, and
computers reached world champion level in Othello well before Chess.
(Also, people also enjoy blindfold Chess, and sometimes even try
blindfold Go; computers can beat most people at blindfold Chess, and
can beat almost anyone at blindfold Go.:-)

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

You seem to be saying that it's impossible that Go is intrinsically
harder for computers than Chess, because you have demonstrated by
argument that all games are comparably difficult for computers and
humans; and therefore, it must be the lack of Go programming work
which has caused Go to lag behind Chess.

I don't believe that your argument that all games have comparable
difficulty for humans and computers is correct. Consider that Othello,
Nine-Men-Morris (?), and Checkers have attracted enormously fewer
man-years of development than either Chess or Go, yet computers excel
at them. If your argument were correct, how could this be so?

(I suspect that the comparison of programming effort is also flawed.
By now, I estimate that at least as much effort has been put into Go
as had been put into Chess by the early 1980s. If the games are
comparably difficult, why are we still so far from being able to make
a program which runs on a Z80 and gives a club player a challenge?)

-- 
William Harold Newman <william.newman@xxxxxxxxxxxxxxxxx>
software consultant
PGP key fingerprint 85 CE 1C BA 79 8D 51 8C  B9 25 FB EE E0 C3 E5 7C