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

[Vincent Diepeveen <diep@xxxxxxxxx>]

Yes. And better search enhancements then reduce that further.

Chess has on average 40 moves i measured (not counting positions where king
is in check, as those positions get extended anyway).

So Knuths writing that's roughly 6.32
In reality for programs just searching with nullmove (no other pruning),
you  get to 2.8 (= fritz branching factor on average according to Frans
Morsch) in middlegame.

Programs like Shredder and Hydra use more forward pruning and get deeper.

Shredder must be around 2.5 to get 1 ply deeper.

Also in go, in order to beat the pro's in a year or 30, you MUST use brute
force searching algorithms.

If you don't use them, you *always* will keep playing at utmost beginners
level.

Of course with hyper selectivity you take care that seemingly good lines
you see deeper than idiotic lines.

At 19:15 7-11-2004 -0200, Mark Boon wrote:
>Well, I'm not familiar with the computer-chess terminology, and your table
>doesn't clarify much to me. Are you referring to the roughly square-root
>alpha-beta cut-off does to the branching? So 100 moves gives an effective
>branching factor of 10?
>
>> -----Original Message-----
>> From: computer-go-bounces@xxxxxxxxxxxxxxxxx
>> [mailto:computer-go-bounces@xxxxxxxxxxxxxxxxx]On Behalf Of Gian-Carlo
>> Pascutto
>> Sent: Sunday, November 07, 2004 19:06
>> To: computer-go
>> Subject: Re: [computer-go] Modern brute force search in go
>>
>>
>> Mark Boon wrote:
>>
>> > I don't understand this. How does the branching factor get to
>> 10 in go? Are
>> > you referring to another terminology of branch-factor?
>>
>> Effective branching factor.
>>
>> With just a PVS alphabeta search, R=3 nullmove, fairly simple
>> evaluation, and no other move ordering besides hashtables, I get:
>>
>> 19x19
>>
>>   d:  1 s:     3 n:        365 t:     0.4s pv: s18
>>   d:  2 s:     1 n:       1812 t:     0.5s pv: s18 s19
>>   d:  3 s:     4 n:       8743 t:     0.7s pv: r18 s18 o18
>>   d:  4 s:     0 n:     249878 t:     6.6s pv: s18 s3 s7 b18
>>   d:  5 s:     4 n:     638195 t:    18.0s pv: s18 r18 s3 q3 s15
>>   d:  6 s:     0 n:   13871970 t:   377.2s pv: s18 r18 s15 t15 b18 o18
>>   d:  7 s:     4 n:   57710143 t:  2039.0s pv: s18 r18 s15 t15 s3 s7 b18
>>
>> Or an effective branching factor of 7 to 10.
>>
>> 9x9
>>
>>   d:  1 s:     3 n:         85 t:     0.7s pv: h8
>>   d:  2 s:     1 n:        412 t:     0.7s pv: h8 h9
>>   d:  3 s:     4 n:       1993 t:     0.7s pv: g8 h8 d8
>>   d:  4 s:     0 n:      25846 t:     1.0s pv: h8 f9 h5 b8
>>   d:  5 s:     4 n:      69288 t:     1.8s pv: h8 g8 g2 h5 b8
>>   d:  6 s:     0 n:     641869 t:    15.9s pv: h8 g8 b8 b7 b2 b4
>>   d:  7 s:     5 n:    3558016 t:    83.0s pv: g2 h5 h8 b8 e8 g9 b2
>>   d:  8 s:     0 n:   25101795 t:   480.9s pv: h2 g2 b8 c8 h8 h7 b2
>>
>> Or an effective branching factor of 5 to 7.
>>
>> --
>> GCP
>> _______________________________________________
>> 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/
>
>
_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/