The side to move is different.Don wrote:How is this any different from just doing the null move search but having it terminate immediately due to a hash table cutoff? If the depth in the table is adequate for the reduced depth search and the bound is right, the search will immediately return with no effort. Am I missing something?bob wrote:Simple explanation.ZirconiumX wrote:I was looking through the source code of Smash, a while ago. Since I decided against using Smash after all, I deleted the source code.
I seem to recall it had a flag in the TT to avoid nullmove. I quickly checked in Crafty and it was there too, but I could not find how it knew to avoid nullmove, other than probe_tt() (or whatever) returning a value of AVOID_NULLMOVE.
Could someone tell me how this is supposed to work?
Something in the back of my head says to check if the TT score fails low.
Matthew:out
First, you expect to do a null-move search, reducing by N plies, and you want it to fail high. That lets you avoid the effort of searching real moves to a deeper depth. But what if the null-move search fails low? Wasted effort.
When you do a hash probe, and get a hit, often the draft (remaining depth stored in the entry is too shallow to let you use the score. But suppose this "hit" says "fail low happened here last time" and the draft is deeper than the draft would be after the null-move reduction. Since you know the same position would fail low searching real moves to a reduced depth, you can safely conclude that the same position would fail low on a reduced-depth null-move search, and you can return a flag saying "don't try it here, it is a wasted effort..."
TT avoid nullmove flag
Moderators: hgm, Rebel, chrisw
-
- Posts: 778
- Joined: Sat Jul 01, 2006 7:11 am
Re: TT avoid nullmove flag
-
- Posts: 42
- Joined: Sat Aug 08, 2009 2:18 pm
- Location: Almere
Re: TT avoid nullmove flag
Indeed, otherwise you could set this "avoid null move" flag as well for BETA and EXACT found transpositions with a draft >= draft - Rjwes wrote:The side to move is different.Don wrote:How is this any different from just doing the null move search but having it terminate immediately due to a hash table cutoff? If the depth in the table is adequate for the reduced depth search and the bound is right, the search will immediately return with no effort. Am I missing something?bob wrote:Simple explanation.ZirconiumX wrote:I was looking through the source code of Smash, a while ago. Since I decided against using Smash after all, I deleted the source code.
I seem to recall it had a flag in the TT to avoid nullmove. I quickly checked in Crafty and it was there too, but I could not find how it knew to avoid nullmove, other than probe_tt() (or whatever) returning a value of AVOID_NULLMOVE.
Could someone tell me how this is supposed to work?
Something in the back of my head says to check if the TT score fails low.
Matthew:out
First, you expect to do a null-move search, reducing by N plies, and you want it to fail high. That lets you avoid the effort of searching real moves to a deeper depth. But what if the null-move search fails low? Wasted effort.
When you do a hash probe, and get a hit, often the draft (remaining depth stored in the entry is too shallow to let you use the score. But suppose this "hit" says "fail low happened here last time" and the draft is deeper than the draft would be after the null-move reduction. Since you know the same position would fail low searching real moves to a reduced depth, you can safely conclude that the same position would fail low on a reduced-depth null-move search, and you can return a flag saying "don't try it here, it is a wasted effort..."
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: TT avoid nullmove flag
I've run some position tests and I am no longer convinced this is a good idea. We have replaced the primary cluster I used for testing, which means I need to slightly modify my test platform since these nodes have way more CPUS (12 per node now rather than the old 2 per node). But position tests suggest that not using this test is better overall. Only explanation I can guess is that the TT entry often has MORE draft than the NM search would use, and a deeper search would not fail high while a shallower one would. I am going to test it on 30K actual games to see if this is actually true in games as well...Don wrote:How is this any different from just doing the null move search but having it terminate immediately due to a hash table cutoff? If the depth in the table is adequate for the reduced depth search and the bound is right, the search will immediately return with no effort. Am I missing something?bob wrote:Simple explanation.ZirconiumX wrote:I was looking through the source code of Smash, a while ago. Since I decided against using Smash after all, I deleted the source code.
I seem to recall it had a flag in the TT to avoid nullmove. I quickly checked in Crafty and it was there too, but I could not find how it knew to avoid nullmove, other than probe_tt() (or whatever) returning a value of AVOID_NULLMOVE.
Could someone tell me how this is supposed to work?
Something in the back of my head says to check if the TT score fails low.
Matthew:out
First, you expect to do a null-move search, reducing by N plies, and you want it to fail high. That lets you avoid the effort of searching real moves to a deeper depth. But what if the null-move search fails low? Wasted effort.
When you do a hash probe, and get a hit, often the draft (remaining depth stored in the entry is too shallow to let you use the score. But suppose this "hit" says "fail low happened here last time" and the draft is deeper than the draft would be after the null-move reduction. Since you know the same position would fail low searching real moves to a reduced depth, you can safely conclude that the same position would fail low on a reduced-depth null-move search, and you can return a flag saying "don't try it here, it is a wasted effort..."
-
- Posts: 454
- Joined: Sat Apr 04, 2009 6:44 pm
- Location: Bulgaria
Re: TT avoid nullmove flag
Strangely enough, I'm not convinced anymore either, regardless of my previous post. After reading this topic I got back to my old sources and discovered a bug in the tt entry. After I've fixed it, this "add-on" was no longer working . No I have to test again while is removed, too bad.
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: TT avoid nullmove flag
Just goes to show it is always best to test, even if you are sure about the outcome.Mincho Georgiev wrote:Strangely enough, I'm not convinced anymore either, regardless of my previous post. After reading this topic I got back to my old sources and discovered a bug in the tt entry. After I've fixed it, this "add-on" was no longer working . No I have to test again while is removed, too bad.
-
- Posts: 454
- Joined: Sat Apr 04, 2009 6:44 pm
- Location: Bulgaria
Re: TT avoid nullmove flag
Yes, I always do, just the last test optimistic results are now obviously false due to that bug. I hate when a bug produces ELO, it always means more bugs
-
- Posts: 1822
- Joined: Thu Mar 09, 2006 11:54 pm
- Location: The Netherlands
Re: TT avoid nullmove flag
You aren't missing anything. It's safer to allow nullmove and sit and wait for that hashtable cutoff, as an upperbound node stored for this position is pretty meaningless.Don wrote:How is this any different from just doing the null move search but having it terminate immediately due to a hash table cutoff? If the depth in the table is adequate for the reduced depth search and the bound is right, the search will immediately return with no effort. Am I missing something?bob wrote:Simple explanation.ZirconiumX wrote:I was looking through the source code of Smash, a while ago. Since I decided against using Smash after all, I deleted the source code.
I seem to recall it had a flag in the TT to avoid nullmove. I quickly checked in Crafty and it was there too, but I could not find how it knew to avoid nullmove, other than probe_tt() (or whatever) returning a value of AVOID_NULLMOVE.
Could someone tell me how this is supposed to work?
Something in the back of my head says to check if the TT score fails low.
Matthew:out
First, you expect to do a null-move search, reducing by N plies, and you want it to fail high. That lets you avoid the effort of searching real moves to a deeper depth. But what if the null-move search fails low? Wasted effort.
When you do a hash probe, and get a hit, often the draft (remaining depth stored in the entry is too shallow to let you use the score. But suppose this "hit" says "fail low happened here last time" and the draft is deeper than the draft would be after the null-move reduction. Since you know the same position would fail low searching real moves to a reduced depth, you can safely conclude that the same position would fail low on a reduced-depth null-move search, and you can return a flag saying "don't try it here, it is a wasted effort..."
-
- Posts: 1822
- Joined: Thu Mar 09, 2006 11:54 pm
- Location: The Netherlands
Re: TT avoid nullmove flag
Why not just try what Don posted and measure elo?hgm wrote:1) It takes an extra hash probeDon wrote:How is this any different from just doing the null move search but having it terminate immediately due to a hash table cutoff? If the depth in the table is adequate for the reduced depth search and the bound is right, the search will immediately return with no effort. Am I missing something?
2) You might not get the hash cutoff. If the node you are probing now failed low with less depth than you need, even if it ordered a null-move search and it survived in the hash table (it has a lot lower depth!), it will also not have enough depth to satisfy the null-move search you are ordering now. (Unless you already saturated to QS level.) There is no guarantee that another path reached the position after null move with more remaining depth.
the 'avoid null flag' is a pretty dangerous flag to use.
-
- Posts: 5566
- Joined: Tue Feb 28, 2012 11:56 pm
Re: TT avoid nullmove flag
No, it is really different. The short explanation has already been given: the side to move is different.diep wrote:You aren't missing anything. It's safer to allow nullmove and sit and wait for that hashtable cutoff, as an upperbound node stored for this position is pretty meaningless.Don wrote:How is this any different from just doing the null move search but having it terminate immediately due to a hash table cutoff? If the depth in the table is adequate for the reduced depth search and the bound is right, the search will immediately return with no effort. Am I missing something?bob wrote:Simple explanation.ZirconiumX wrote:I was looking through the source code of Smash, a while ago. Since I decided against using Smash after all, I deleted the source code.
I seem to recall it had a flag in the TT to avoid nullmove. I quickly checked in Crafty and it was there too, but I could not find how it knew to avoid nullmove, other than probe_tt() (or whatever) returning a value of AVOID_NULLMOVE.
Could someone tell me how this is supposed to work?
Something in the back of my head says to check if the TT score fails low.
Matthew:out
First, you expect to do a null-move search, reducing by N plies, and you want it to fail high. That lets you avoid the effort of searching real moves to a deeper depth. But what if the null-move search fails low? Wasted effort.
When you do a hash probe, and get a hit, often the draft (remaining depth stored in the entry is too shallow to let you use the score. But suppose this "hit" says "fail low happened here last time" and the draft is deeper than the draft would be after the null-move reduction. Since you know the same position would fail low searching real moves to a reduced depth, you can safely conclude that the same position would fail low on a reduced-depth null-move search, and you can return a flag saying "don't try it here, it is a wasted effort..."
The TT trick avoids nullmove if the current position is in the hashtable, but not with enough depth for a cutoff, but with enough depth to compare against a (reduced) nullmove search (and if the stored score indicates that nullmove would/should be useless).
If you don't use this trick but just do the nullmove, the position does not stay the same because the side to move switches. If you now look in the hashtable, you are looking at a different positon, so you are not going to find the score that helped you if you had done the TT trick. So it is really different.
I would add that if the parent position was not in the hashtable with sufficient depth for a cutoff, it seems likely that the position after the nullmove won't be in the hashtable with sufficient reduced depth. If you are now at depth d for the parent position, but its TT entry has depth d-1, then doing a nullmove and probing the hashtable would more likely find an entry with depth (d-1) - R -1 than one with depth d - R -1, simply because the reason it is in the hashtable at all is that it was searched when a nullmove was tried for the parent positon at depth d-1.
I don't know if the TT trick helps elowise compared to not doing the trick, but it certainly makes a difference.
Since you're saying "it is safer to allow nullmove" we might in fact already mostly agree on this. My point is only that it is not the same as Don suggested.
-
- Posts: 5566
- Joined: Tue Feb 28, 2012 11:56 pm
Re: TT avoid nullmove flag
But... if you skip the trick but allow two nullmoves in a row, then you would return to the current position and the 2nd nullmove would immediately return and show that the first nullmove is useless.syzygy wrote:If you don't use this trick but just do the nullmove, the position does not stay the same because the side to move switches. If you now look in the hashtable, you are looking at a different positon, so you are not going to find the score that helped you if you had done the TT trick. So it is really different.
If I'm not mistaken you (Vincent) are a proponent of double nullmove. In that case I think I have to agree that the TT trick is redundant (although it might save some clock cycli).
Am I correct? I haven't though very long about this so maybe I'm missing something.