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

[Vincent Diepeveen <diep@xxxxxxxxx>]

At 20:37 7-11-2004 +0100, Arend Bayer wrote:
>
>
>> > 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.
>
>It's not pure speculation. Youcan  try to determine god's rankd by looking
>at winning probabilities in even games between players of different
>strength -- at god's level, even a 0.1 rank difference amounts
>to a winning percentage of 100%. I think someone did this with the data
>in the EGF ranks, and concluded it would be about 2-3 stones above
>today's top pros.
>
>> I think for a top pro, 30 moves deep is not unusual. But most moves are
>> played based on a much shallower search.
>
>Even I can read 30 moves occasionally (I am EGF-4d). Some top pro
>claimed he would read ahead 100 moves sometimes, and I find this claim
>entirely credible. 
>
>But I doubt the relevance of this question with regards to go, it seems
>very much a chess programmers point of view (no disrespect intended).

Seeing Chrilly's non stop sollicitations here at the go mailing list and
after we had at in Graz with many chess programmers some general chats,
several can't wait to jump into go, now that hardware gets faster.

For years they have had experience in how to super selectively search real
deep and it is sad for them (and good for me) that nowadays in chess that's
not so relevant for the strength of the program.

I won this years dutch open champs searching 10-12 ply with DIEP. Most
opponents searched 13-16 ply. 

I warned them that writing an evaluation function is a much harder job in
go now already, than it is in chess, and requires a lot more knowledge of
go than writing such selective searches in chess as you must keep the
selection incredible thin and you can't afford missing that line that wins
a group.

Yet i completely disagree with what you write below.

GCP has been doing now a few measurements with R=3 with his simple go
program and already has a branching factor of 7.45

Now i must warn you that for commercial go programs it will be much harder
to get that branching factor than it is for stupid programs. In stupid
programs *everything* gives a cutoff, and not in 85% of the cases, but at
least in 90-96% of the cases the first move already at a cutnode.

When getting that 30 ply in far future, hashtables will play an important
role, so will techniques that can avoid extending too many sidelines.

Additional there is other promising techniques, such as multicut and
similar reduction techniques that will be found coming years (hopefully).

I will therefore assume a branching factor of 6.0 now.

6.0 ^ 30 = 10^23

When will we be able to calculate 10^23 positions in go?

Let's assume we can search at todays hardware single cpu 100k nps.
Now we can trivially already search at 16 processor block 1.6 mln then.

Chrilly will be posting directly he can get at his 60Mhz FPGA even 6
million nodes a second single cpu.

I will use 1 million nps now.
That's 10^6. Important moves where score drops you time extend. Not sure
what time you can time extend. This world champs Shredder searched at 1
important move against me for 60 minutes nearly. Say 10^3. 
10^14 to go.
log(10^14) / log(2) = 46.5
That's 46.5 doublings in hardware needed to get 10^14 faster.
With 18 months for the original Moore law, that's 
46.5 * 18 months = 70 years.

That's a lowerbound of 70 year to go.

It can get better, not worse.

Now that's a very naive way to look at it. 

In computerchess the big progress of the past few years is better
evaluation functions more than cpu speed. 

Of course we can endlessly discuss what happens in 70 years from now.

But do you really believe it takes until then to beat human go players?

Suppose that Mark Boon, after coding for 30 more years, with great tools
has developed an evaluation function and move selection function that's
really human a look like.

What he can do then is simply next.

Exampe of a simple brute force search for go:

At each position in search, make a list of *all* legal moves.
A move that really stinks you give n=4. A move that is real good possible
or might trigger a forced combination, you give n=1. All other moves n=2.

You start for example this iteration at 10 ply depthleft.

For each move made, you reduce the remaining depthleft by n.

If you just take care that the total number of n=1 moves is real small and
the total number of n=2 is not too big, then you really can search deep
with this.

In chess you already can easily search 22 ply with this in middlegame right
*now*. Nullmove doesn't give that a big speedup when using it. 

Note that nullmove is legal in go as you might know and the double nullmove
i invented is illegal in go to use, as the game has ended already by then :)

Then we add some techniques like a fixed multicut (it has transposition
problems currently and doesn't work for me, but the idea is interesting for
go), last few ply pruning, several probes in hashtables, and perhaps some
new techniques are there.

Mark sure will after 30 years of hard work easily get a b.f. of 4.0 then.

Now let's recalculate what you need then.

2^60 = 1.15 * 10^18
minus 10^9 = 10^9  (1 mln nps per second + 1000 seconds for important moves
in a game)

log(9) / log(2) = 30

That's like 45 years to go until your pro players have a better secondant
than themselves.

In 30 years *a lot* can happen.

Go moves are easier to predict than chess moves. Selection functions in
chess are much harder to make than in go.

The advantage in chess is that you don't need selection functions much.

Cutoff rates in go will be better than in chess. DIEP i struggle around
86-90% right now for chance that first move gives a cutoff (knowing that
this node is a cutoff node). Nullmove is not counted in that.

For pruning mechanisms like nullmove, it gives a much better branching
factor when first move is predicted correct.

When you get so many nodes a second in a few years of time, perhaps new
techniques will be found too.

I must really admit that in 1997 i wasn't believing computerchess would go
*that* fast forward in just 7 years. The big dang the improved evaluation
functions have given really is shocking.

>Since a program will never be able to do 30 ply lookahead on a 19x19
>board using standard search techniques, you will need a lot of forward
>pruning, and the strength of the go program will depend much on the
>quality of this pruning (even if you assume an excellent position
>evaluation).

>Further, if a human does 20 ply fullboard lookahead, this is backed up
>with a lot of local reading that is not included in the 20 plies. The
>same will IMO hold true for any strong go program. This reduces the
>relevance of this "20" even more.

Forced moves aren't counted in search depth. You get them for free.

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