[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
RE: [computer-go] Modern brute force search in go
Mark, null move reduces the size of the tree below the sqrt bound you are
thinking of.
Null move searches some lines to less depth than others, typcially going
deeper when
there are threats.
David
> -----Original Message-----
> From: computer-go-bounces@xxxxxxxxxxxxxxxxx
> [mailto:computer-go-bounces@xxxxxxxxxxxxxxxxx] On Behalf Of
> Gian-Carlo Pascutto
> Sent: Sunday, November 07, 2004 1:06 PM
> 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/