RE: [computer-go] Modern brute force search in go

[Vincent Diepeveen <diep@xxxxxxxxx>]

At 17:15 7-11-2004 -0200, Mark Boon wrote:
>> -----Original Message-----
>> From: computer-go-bounces@xxxxxxxxxxxxxxxxx
>> [mailto:computer-go-bounces@xxxxxxxxxxxxxxxxx]On Behalf Of Vincent
>> Diepeveen
>> Sent: Sunday, November 07, 2004 17:02
>> To: drd@xxxxxxxxxxxxxxxxx; computer-go; chrilly@xxxxxxxxxxxxxxxxx
>> Cc: computer-go@xxxxxxxxxxxxxxxxx
>> Subject: Re: [computer-go] Modern brute force search in go
>>
>>
>> At 13:51 7-11-2004 -0500, Don Dailey wrote:
>> >
>> >
>> >Just my thoughts.  All of this  is even more true of Go.  There exists
>> >(in  principle) a  future GO  player than  can make  the very  best Go
>> >player (of today or yesterday) look like a baby.
>> >
>> >- Don
>
>To be honest, I consider all of this pure speculation again. Top pro's
>estimate 'god's level' to be anywhere between 3 and 5 stones stronger than a
>top pro. I do think top pro's are biased in this respect, but they're not
>totally ignorant. And they're definitely not stupid either, so I'd say they
>are better qualified to make such estimates than anyone else. Until we have
>some hard data or good theories that say otherwise, why make such claims?
>Unless 5 stones qualifies as 'making look like a baby', which in a pro's eye
>it very well might do.
>
>>
>> In chess there was soon an indication what the average 'non forced' search
>> depth is of combinations played at GM level. That was already estimated to
>> be around 12 ply some tens of years ago.
>>
>> It is very interesting to see that this is a very true number.
>>
>> For go programs it will be very interesting to know what the tactical
>> barrier depth in go is.
>>
>> As i'm a layman there perhaps others can put a light on this?
>
>Sakata once said he could read 30 moves ahead in a snap. Takagawa, one of
>his main rivals at the time responded that his reading was 'pretty
>accurate'.
>
>I think for a top pro, 30 moves deep is not unusual. But most moves are
>played based on a much shallower search.
>
>>
>> That depth is very important for conclusions with respect to what strength
>> software can have when compared to human playing strength.
>>
>> If the barrier depth is far above what professional players see now, it
>> will be trivial that programs will get a lot stronger than mankind.
>>
>> Additionally we can also calculate the cpu power required,
>> knowing that the
>> branching factor in GO starts at empty board at around 10.0 (using
>> nullmove) and slowly climbs down. Hardware gets 2 times faster
>> each 2 years
>> (no longer each 18 months), so it's easy to do math with that.
>>
>
>I don't understand this. How does the branching factor get to 10 in go? Are
>you referring to another terminology of branch-factor?

My simple go program has a branching factor of 10.0 the first 10 plies or so.

It uses the influence function as you have described it many years ago and
it keeps incremental the groups (so if 2 groups gets connected the
incremental code will add it to the right group).

Basically a very simple go program, but enough to get a bound back from the
branching factor.

Note this was done some eyars ago with R=2. 
Nowadays in chess everyone uses R=3 in the main search and near leafs R=2.

It seems i was the first to post on the internet around 1996-1997 to
combine this and to use R=3 instead of R=2.

If 30 ply is what you need (not counting forced moves) for an average
combination, then go software has a major problem.

We know from some games from Kasparov that he has calculated in his best
days an unforced combination of 40 ply (20 moves). Had kasparov not seen
the last move in that sequence, the line would not have been playable.

That's unforced of course. There is forced sequences of over 520 ply in chess.

My chessprogram DIEP has a nominal depth of around 10-12 ply currently, and
extended sequences of up to 96 ply deep. Not more, because i limited its
stack depth to 64+32 ply :)

Important is therefore in go the average unforced depth of combinations,
not how deep one of your best players can calculate.

Humans can of course play moves way deeper than computers in any complex
game than a computer can look deep. That's called strategic moves, played
with a plan :)

So in short we are looking for the search depth needed to not fall into
tricks where the weakest professional players do not fall in quickly. I
don't mean old professional players by that. 

I also lost from Bronstein and Korchnoi games (both #2 of the world once),
without them seeing more than a few ply deep for sure. They just every move
played a better one than i did :)

However when i lost earlier this year from reigning (FIDE) world champ
Kasimzdhanov he didn't only play much better moves, i'm also sure he saw
deeper than i did.

It's not important how deep *these* guys search. It's important to avoid to
fall for tactics that happens each game and which strong amateur players
also see.

>
>
>_______________________________________________
>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/