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

[Vincent Diepeveen <diep@xxxxxxxxx>]

At 11:45 2-12-2004 -0600, William Harold Newman wrote:
>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.

Actually it's here where you hit the problem right at its head. The main
problem might be that machack probably would search at todays hardware 8
ply or so, thanks to the many improvements in algorithms there are nowadays
and its evaluation function of course will need plies more to see an 11 ply
tactic where todays software just needs 11 ply.

Win at chess is 300 positions utmost beginners tactics with just a few bit
harder positions. MacHack probably would score around 285 positions when
given 3 minutes a position at modern hardware.

Where older versions of my software scored 300 out of 300, todays version
probably will get 299 out of 300 correct, because 1 endgame has been proven
incorrect (Rb4 sacrafice). Even where from human viewpoint it's best move,
it's objectively not the best one. Some versions of diep play it, others do
not. Objectively it doesn't matter whether it plays it or not. Of course
also programs don't see the 60 ply line or so that's needed to realize it's
a draw anyway. I'll forgive Diep that if it doesn't play it :)

So it'll get 299 or 300 at 1 minute a move or so. What time you give to
machack is not so interesting. It's the branching factor. The software is
not branching factor optimized, it will just not get above 9 or 10 ply *ever*.

It's especially this what i try to write down here in the go programming
mailing list. They are having evaluation functions which are not in
comparision to the search being used in the program. The search is the weak
part IMHO. You can never *ever* beat a professional player if your search
isn't going to find basic tactics.

Claims that things like nullmove do not work we had in the 90s in
computerchess too. It were always university researchers doing such claims.

Cray Blitz ran at a 16 processor machine by the way. 

That's another easy optimization to get another 2 ply in go.

>> 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/
>
>
_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/