Re: [computer-go] Pattern matching - example play

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

On Thu, Dec 02, 2004 at 03:33:10PM +0100, Vincent Diepeveen wrote:
> At 09:39 2-12-2004 +0100, Heikki Levanto wrote:
> >On Wed, Dec 01, 2004 at 08:27:20PM +0100, Vincent Diepeveen wrote:
> >> 
> >> 20 ply brute force is no problem either in 9x9. Of course using nullmove
> >> and some later techniques and a good hashtable.
> >> 
> >
> >Searching all those positions is not a hard problem. Evaluating the
> >resulting positions is hard.
> 
> Obviously that will be the problem. However at this moment the go software
> is where chess was, from tactical viewpoint, in 1979. It's missing basic
> tactics thanks to life&death.

I question that date: I will argue that 1965 might be closer to the
mark.

IIRC it was in the early 1980s that some programmer associated with
Cray Blitz said that CB could solve a popular book of tactics problems
before a human player could turn the first page. (The programmer was
probably Hyatt, and the book was probably _Win at Chess_, but I'm
having trouble convincing Google to admit it.) I'd be surprised if
there were many serious Chess programs in 1979 which couldn't solve
the same set of problems within fifteen minutes.

Today in Go, possibly there might be a program which can reliably
solve (as opposed to guessing with 98% accuracy) all the exact-answer
problems (like "black to play and kill," as opposed to "what is the
best move in this opening position") in _Graded Go Problems for
Beginners_ volume III in some achievable amount of time (e.g., a week
of total wall clock time). But I'm not aware of any. My impression is
that closed-tactics-only GoTools is still the state of the art in Go
tactical search; I'd be very interested to hear otherwise.
 
I know that there are classes of harder-for-computers chess problems
(endgame problems, for example) where computers in 1979 were not so
strong. But in Chess, you need to be reasonably good, or very lucky,
to reach such hard-for-computers tactics problems without first being
annihilated by the sorts of middle game tactics that 1979 computers
already understood tolerably well. The situation seems to be reversed
in Go: the hard-for-computers problems dominate the middle game, so
that a computer needs to survive a number of challenges involving
hard-for-computers problems in order to reach situations which
computers might be able to analyze faster than a human. Good luck
doing this against even a below-average club player!

By this argument, then, I think there's a case for saying that
computer Go looks like computer Chess did considerably earlier than
1979.:-| Especially if we try to look at *software* alone, crudely
compensating for improvements in hardware by running old software on
new hardware, which is a little tricky, but less tricky than
recreating old hardware to run old programs on. An early estimate
would be 1957, just before the development of alpha-beta. A late
estimate might be 1966, on the theory that in 1967 MacHack VI beat a
1510 human player, which makes it quite difficult for me to believe
that MacHack VI on 2004 hardware couldn't solve _Win at Chess_ within
a week.

> Look i'm not saying chessprograms were so great at the time, nor that go
> software is primitive or anything like that as i saw Mark Boon interpret
> it. I'm just using it to show what obvious tactics gets missed by software
> right now. A few years later the first pro's were beaten in chess. 
> In Go that will take longer obviously.

I think it already has taken longer. Fortunately, now the chess
programmers are here.:-)
 
> A deeper brute force search is an absolute necessity to make it into the
> dan levels with go software. Without that, the weakest chain is and will be
> just some life&death tactics.

-- 
William Harold Newman <william.newman@xxxxxxxxxxxxxxxxx>
[_8david] ILTWYS"J" as dan_b would say -- <tunes.org/~nef/logs/lisp/04.09.10>
_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/