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

[Vincent Diepeveen <diep@xxxxxxxxx>]

Hello David,

Fun to see you here in the mailing list again after meeting you at the ICGA!

Perhaps i should explain what nullmove is for some of the programmers.

Nullmove to start with is legal in go. Illegal in chess.

So it is amazing that this was figured out in chess to be working instead
of go.

Instead of making a normal move, you do nothing. You give the opponent the
move and only use 1 major trick. You reduce the search depth of that tree.

If that gives a cutoff, you use that.

The number of ply reduction is called the Reduction factor, or R.

Initially R=2 was used in chess. Nowadays i guess all pro's are using R=3.

Nullmove is very difficult to define for last few plies. I'm sure other
techniques can be used in combination with it there.

Assuming a depth limited search (i'm not going into details like researches
of pvs or hashtables or whatever) :

global R=3;

int alfabeta(int alfa,int beta,int depthleft,int side) {
  if( (x=transposition(alfa,beta,&bestmove,depthleft)) != MAXSCORE ) 
    return x; // transposition table cutoff

  generatemovelist();
  assignsortingscorestomovelist();
  
  // nullmove
  if( depth <= R+1 ) 
    score = -qsearch(-beta,-alfa,side^1);
  else
    score = -alfabeta(-beta,-alfa,depthleft-R-1,side^1);
  if( score >= beta ) {    
    bestmove = move_nullmove; // try at own risk to keep existing bestmove :)
    storeinhash(..);
    return score;
  }

  bestscore = -infinite; 
  for( all moves ) {
    makemove
    tempscore = -alfabeta(-beta,-alfa,depthleft-1,side^1);
    unmakemove
    if( tempscore > bestscore ) {
      bestscore = tempscore;
      if( tempscore >= beta ) {
        break;
      } 
      if( tempscore > alfa ) 
        alfa = tempscore;
    }
    
  } 

  storeinkillertable();
  storeinhash();
  return bestscore;
}

So the huge saving with nullmove is that a search of n ply gets replaced by
a search of n-4 ply, for R=3.

That trivially means that the branching factor exponent goes down, because
you shorten the search lines.

The better your evaluation function, the better nullmove works in terms of
good play.

At 14:58 7-11-2004 -0800, David Fotland wrote:
>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/
>
>
_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/