[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [computer-go] Modern brute force search in go
in diep in fact i'm using PVS and initial window = [-inf;inf], so i don't
try nullmove when beta == infinite.
Note that I made a mistake in my example.
The window at which nullmove searches is [beta-1;beta]
Do not forget that nullmove is a refuting technique with a reduced search
depth. It will not miss anything, but the reduced search depth is very
tricky when searching near the leafs and combining it with last few ply
pruning.
That's why last few plies the programs forward pruning last few plies
agressively use nullmove with R=2.
In DIEP i'm doing R=2 at depthleft <= 4 and R=3 at depthleft <= 5.
You WANT to only try a few moves at depthleft == 1 ply.
I am sure you realize clearly that in Go, most programs thanks to
extensions won't search even 5 ply nominal search depth.
What we do in chess then to nullmove is use the -qsearch, which in case of
go is in many ways to define. For example what i did is putting a stone in
everything with 1 liberty left. All immediate 'tactical threats'. Perhaps
you want to extend it to all moves that let a group directly get hung in
evaluation. In a selective search you keep searching then with this method.
How well or bad this nullmove last few plies works in go, is not clear with
such small search depths to me.
Even more than in chess, in go writing an efficient go move selection
algorithm for quiescencesearch is going to be a difficult job.
It can very easily explode. Perhaps it is better now to just see direct
captures capturing a group which otherwise isn't hung anyway. And only see
in selective search a few plies of threatening moves after which 1 liberty
is left.
In any way here is how quiescencesearch probably should search i guess in a
simplified form:
int qsearch(int alpha,int beta,int side) {
int bestscore,eval,temp,bestmove=0;
if( (temp=hashlookup(alfa,beta,side,0,&eval,&bestmove)) != 0 )
return temp;
if( eval=eval() >= beta ) return eval;
bestscore = eval;
GenerateGroupCapturingMoves();
move = firstmove;
while( move < lastmove ) {
makemove(side,*move);
temp = -qsearch(-beta,-alfa,1-side);
unmakemove(side,*move);
if( temp > bestscore ) {
bestscore = temp;
bestmove = *move;
if( temp >= beta )
break;
if( temp > eval ) alfa = temp;
}
move++;
}
storehash(alfa,beta,bestscore,eval,bestmove,side);
return bestscore;
}
So qsearch does not detect ladders then, which it shouldn't IMHO. Just
groups with 1 liberty which can get connected otherwise, dang capture them.
Before qsearch you might have want to have a selective search, and it is
this selective search which perhaps is a good idea to call when nullmoving,
it should see more than qsearch and it is harder to write and will be the
basis for programs to find tactics.
I hope you see how much tactical moves that give a directly winning threat
or lift the evaluation function several pawns get missed by quiescencesearch.
Also in the game of chess.
A few checks usually get also tried by professional chess programs. There
is also many amateurs which do not do them. Selecting the right checks is
very hard to write code.
Because the nature of nullmove, using qsearch to nullmove which picks up
directly capturing groups/stones, in chess they have awarded nullmove a
threat detecting pruning technique.
That is of course plain wrong. At bigger depths it tries also a lot of
moves with a reduced search depth and doesn't miss any positional move there.
It is *then* that nullmove will work very well when evaluation function is
good.
Vincent
At 09:19 8-11-2004 +0100, Erik van der Werf wrote:
>Hi Vincent,
>
>It seems you are trying nullmove in PV nodes too. Why is that? How does
>the performance compare to only trying nullmove in non-PV nodes?
>
>Best,
>Erik
>
>
>Vincent Diepeveen wrote:
>
>>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/
>>
>>
>
>_______________________________________________
>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/