Verified null-move pruning

Programming Topics (Computer Chess) and technical aspects as test techniques, book building, program tuning etc

Moderator: Andres Valverde

Verified null-move pruning

Postby Tom King » 09 Mar 2006, 21:21

I stumbled across a paper on this: http://www.cs.biu.ac.il/~davoudo/pubs/vrfd_null.html

What do others think? Is this a useful way to grab a few more ELO points or is it a wash?

I've implemented this, and am trying a few test games. Will report back.

Regards,
Tom
Tom King
 
Posts: 19
Joined: 19 Jul 2005, 09:36

Re: Verified null-move pruning

Postby Uri Blass » 09 Mar 2006, 22:23

I am not sure if it is productive and I use it onlyin the endgame.

Based on my experience when I implemented it everywehere in test suites it could help to solve some positions at smaller depth but it also make the program slower so the total result was that it solved less positions at the same time.

The were cases when it helped in the middle game but the main advantage was in the endgame so I decided to have it only in the endgame(in other words in positions when the total value of pieces of both sides is not more than 24 pawns).

Note that I use null move with R=3 and checks in the qsearch.

Uri
User avatar
Uri Blass
 
Posts: 727
Joined: 09 Oct 2004, 05:59
Location: Tel-Aviv

Re: Verified null-move pruning

Postby smcracraft » 10 Mar 2006, 18:44

Tom King wrote:I stumbled across a paper on this: http://www.cs.biu.ac.il/~davoudo/pubs/vrfd_null.html

What do others think? Is this a useful way to grab a few more ELO points or is it a wash?

I've implemented this, and am trying a few test games. Will report back.

Regards,
Tom


I don't use it but tried/tested it.

I do use adaptive null move however.

Stuart
smcracraft
 
Posts: 65
Joined: 15 Jan 2006, 05:38

Re: Verified null-move pruning

Postby Tom King » 10 Mar 2006, 20:16

smcracraft wrote:
Tom King wrote:I stumbled across a paper on this: http://www.cs.biu.ac.il/~davoudo/pubs/vrfd_null.html

What do others think? Is this a useful way to grab a few more ELO points or is it a wash?

I've implemented this, and am trying a few test games. Will report back.

Regards,
Tom


I don't use it but tried/tested it.

I do use adaptive null move however.

Stuart


So far, so bad. For my program (sans verified null move) vs my program (avec verified null move):

+ 19,= 12,- 11, 59.5 %

Needs more games, of course, and self play is not a reliable indicator, of course. But this doesn't look like a win to me.

Ok, next thing to try, null move R=3 throughout. (Currently I use R=2 near the leaves and R=2 further away). Adaptive null move, like you, Stuart.

Regards,
Tom
Tom King
 
Posts: 19
Joined: 19 Jul 2005, 09:36

Re: Verified null-move pruning

Postby H.G.Muller » 11 Mar 2006, 10:25

Any advantage of verified (vs standard) null-move pruning can only come from the fact that you allow further null-move pruning in the verification search. If you have an advantage so great that you can afford null move, the first real move of the verification search in general will be able to keep that advantage, so two ply later you can still afford null move. So eventualy the reductions add.

So the results of the comparison you are making might be sensitive to how exactly you handle the accumulation of reductions in the two cases.

Accumulation of reductions is a concern in null-move pruning anyway. The fact that you reduce the depth of the null-move search can only be justified by the assumption that you have forcing moves available that can postpone the effects of a possible threat in the real-move branches by the amount of the reduction. One should thus always avoid accumulation of the total reduction to a value larger than what is a plausible number for such delaying moves. (This might depend on the stage of the game.)

Even if you want to limit the total reduction to 4 ply, allowing two consecutive reductions of R=2 in the null-move branch might be a much more reliable way to implement this than a single R=4, because you will then only apply the maximum reduction in situations where you can afford 2 null moves.
User avatar
H.G.Muller
 
Posts: 3184
Joined: 16 Nov 2005, 12:02
Location: Diemen, NL

Re: Verified null-move pruning

Postby Tom King » 11 Mar 2006, 22:41

H.G.Muller wrote:Any advantage of verified (vs standard) null-move pruning can only come from the fact that you allow further null-move pruning in the verification search. If you have an advantage so great that you can afford null move, the first real move of the verification search in general will be able to keep that advantage, so two ply later you can still afford null move. So eventualy the reductions add.

So the results of the comparison you are making might be sensitive to how exactly you handle the accumulation of reductions in the two cases.

Accumulation of reductions is a concern in null-move pruning anyway. The fact that you reduce the depth of the null-move search can only be justified by the assumption that you have forcing moves available that can postpone the effects of a possible threat in the real-move branches by the amount of the reduction. One should thus always avoid accumulation of the total reduction to a value larger than what is a plausible number for such delaying moves. (This might depend on the stage of the game.)

Even if you want to limit the total reduction to 4 ply, allowing two consecutive reductions of R=2 in the null-move branch might be a much more reliable way to implement this than a single R=4, because you will then only apply the maximum reduction in situations where you can afford 2 null moves.


oh.. I'm allowing further null moves in the verification search. But not further verification searches (within the verification search). As per Tabibi and Netanyahu's paper.

Still, their implementation seemed like a backward step to me, so I've ditched this for now.
Tom King
 
Posts: 19
Joined: 19 Jul 2005, 09:36

Re: Verified null-move pruning

Postby Pradu » 13 Mar 2006, 04:21

An interesting alternative to using verified nullmove is doubble nullmove. Anyone here tested their programs with doubble and verified nullmove and find that one method is more advantageous than the other?
User avatar
Pradu
 
Posts: 343
Joined: 12 Jan 2005, 19:17
Location: Chandler, Arizona, USA


Return to Programming and Technical Discussions

Who is online

Users browsing this forum: No registered users and 1 guest

cron