During the search.
==================
If score never gets to alpha we save the node as FailLow. But no move is saved
If score increases alpha we save the node as exact, and the move that caused this.
If score > beta we save the node as a FailHigh node and the move that caused this.
If during a null move we have a beta cut, we save the node as FailHigh.......what move do we save ?
Before the search.
==================
Lookup the node.
IF its a FailLow node don't do a NullMove search.
IF the TT height >= Depth then the info is good to use
{If it is an Exact node just return the score.
Alpha = Max(Alpha, NodeScore)
If Alpha >= Beta then its a beta cut, return Beta.}
ELSE
Search the stored move since it still may give a cutoff even if the height < Depth.
So if a null move causes a beta cut we don't have a move to save. What do we do here ?
Thanks
Laurie.
Can you please check my Transposition Table logic
Moderators: hgm, Rebel, chrisw
-
- Posts: 199
- Joined: Sun Nov 03, 2013 9:32 am
-
- Posts: 1334
- Joined: Sun Jul 17, 2011 11:14 am
Re: Can you please check my Transposition Table logic
Yes, though fail-soft can still give you a move. The ordering tends to be fairly worthless though.lauriet wrote:During the search.
==================
If score never gets to alpha we save the node as FailLow. But no move is saved
Yes, though I think you mean >= beta.If score increases alpha we save the node as exact, and the move that caused this.
If score > beta we save the node as a FailHigh node and the move that caused this.
You just don't save a move, same as a fail low node. You can still get TT score cutoffs, which don't need a move.If during a null move we have a beta cut, we save the node as FailHigh.......what move do we save ?
Correct, though determining ALL versus CUT nodes is somewhat difficult.Before the search.
==================
Lookup the node.
IF its a FailLow node don't do a NullMove search.
This looks odd to me. If you have the upper bound/lower bound flags set, wouldn't it make more sense to check if stored score is >= beta on an indicated fail high node and check if the score is <= alpha on an indicated fail low node instead of shenanigans with max() that probably won't work on a fail low node?IF the TT height >= Depth then the info is good to use
{If it is an Exact node just return the score.
Alpha = Max(Alpha, NodeScore)
If Alpha >= Beta then its a beta cut, return Beta.}
Yes, since most of the time you will still get a cutoff.ELSE
Search the stored move since it still may give a cutoff even if the height < Depth.
Don't save a move. Alternatively, don't store nullmove scores in the TT. YMMV.So if a null move causes a beta cut we don't have a move to save. What do we do here ?
Thanks
Laurie.
Some believe in the almighty dollar.
I believe in the almighty printf statement.
I believe in the almighty printf statement.
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Can you please check my Transposition Table logic
Some terminology to make sure you avoid mistakes:lauriet wrote:During the search.
==================
If score never gets to alpha we save the node as FailLow. But no move is saved
If score increases alpha we save the node as exact, and the move that caused this.
If score > beta we save the node as a FailHigh node and the move that caused this.
If during a null move we have a beta cut, we save the node as FailHigh.......what move do we save ?
Before the search.
==================
Lookup the node.
IF its a FailLow node don't do a NullMove search.
IF the TT height >= Depth then the info is good to use
{If it is an Exact node just return the score.
Alpha = Max(Alpha, NodeScore)
If Alpha >= Beta then its a beta cut, return Beta.}
ELSE
Search the stored move since it still may give a cutoff even if the height < Depth.
So if a null move causes a beta cut we don't have a move to save. What do we do here ?
Thanks
Laurie.
You store an UPPER flag, indicating that this is a bound, but it is an upper bound. The actual score might be lower. If you think about alpha/beta, when you search all moves, you know that the score can't be > alpha, and that it is probably lower. Hence alpha is an UPPER bound on the score (sounds backward, but this is the terminology everyone uses).
You store a LOWER flag, indicating that this is a lower bound. IE the search returned a value >= beta, so you store beta. But beta is a LOWER bound on the score which is probably higher.
EXACT is pretty obvious.
A couple of mistakes in your comments:
(1) if score is >= beta, you should store LOWER. NOT just > beta.
(2) ditto for score <= alpha, you store UPPER, not just < alpha.
For the null-move question, if it failed high, you don't have a move to save.
For the lookup part, that seems a bit confused. You have three cases, all assume that stored draft >= remaining depth of course.
(1) entry = EXACT. Just return that value instantly.
(2) entry = LOWER. If tt bound is >= beta, then you can return beta instantly.
(3) entry = UPPER. If tt bound is <= alpha, then you can return alpha instantly.
The easy way to think of this is as follows. Whatever you did when you stored the entry, you want to do the SAME thing here, exactly, assuming the draft is sufficient and the bounds satisfy the above tests. If you searched all moves without modifying alpha and then stored that result, then you want to return alpha here just like you did when you stored the entry.
-
- Posts: 193
- Joined: Wed Mar 11, 2015 3:34 am
- Location: United States
Re: Can you please check my Transposition Table logic
Hmmm. I've never stored beta cutoffs from a null move search in the TT. What depth would you use? Can the score really be considered reliable? Perhaps I should give it a try.ZirconiumX wrote:Don't save a move. Alternatively, don't store nullmove scores in the TT. YMMV.So if a null move causes a beta cut we don't have a move to save. What do we do here ?
Of the engine developers out there that do store null move beta cutoffs in the TT, how do you determine the depth to set on the entry? And do you use any special handling for such cases?
-
- Posts: 1334
- Joined: Sun Jul 17, 2011 11:14 am
Re: Can you please check my Transposition Table logic
At a quick glance, Fruit 2.1 seems to treat it as a plain beta cutoff, though it isn't state of the art by any means.zd3nik wrote:Of the engine developers out there that do store null move beta cutoffs in the TT, how do you determine the depth to set on the entry? And do you use any special handling for such cases?
Some believe in the almighty dollar.
I believe in the almighty printf statement.
I believe in the almighty printf statement.
-
- Posts: 199
- Joined: Sun Nov 03, 2013 9:32 am
Re: Can you please check my Transposition Table logic
Hey Bob,
What about the case where it was a fail low node (an UpperBound) in the TT, but the TT score is higher than the current Alpha. Should the current alpha be updated to the TT score......and then if it is >= Beta it is a new cut off....or tighter bounds on the new search ?
Thats what the Alpha = Max(Alpha, TTscore) was about.
Regards
Laurie
What about the case where it was a fail low node (an UpperBound) in the TT, but the TT score is higher than the current Alpha. Should the current alpha be updated to the TT score......and then if it is >= Beta it is a new cut off....or tighter bounds on the new search ?
Thats what the Alpha = Max(Alpha, TTscore) was about.
Regards
Laurie
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Can you please check my Transposition Table logic
Since most use PVS, which means almost all nodes are searched with a null window, updating alpha does nothing if you didn't take the cutoff, as that would force you to cutoff also since increasing alpha would either hit beta or go higher...lauriet wrote:Hey Bob,
What about the case where it was a fail low node (an UpperBound) in the TT, but the TT score is higher than the current Alpha. Should the current alpha be updated to the TT score......and then if it is >= Beta it is a new cut off....or tighter bounds on the new search ?
Thats what the Alpha = Max(Alpha, TTscore) was about.
Regards
Laurie
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Can you please check my Transposition Table logic
You use the normal depth. Why? This is about saving effort. If you reach position P with depth D and null-search fails high, you store P with depth D and "LOWER" flag. Then when you reach P through a different path, you get the instant cutoff and avoid doing even the null-move search, which would obviously also fail high here since it is the same position.zd3nik wrote:Hmmm. I've never stored beta cutoffs from a null move search in the TT. What depth would you use? Can the score really be considered reliable? Perhaps I should give it a try.ZirconiumX wrote:Don't save a move. Alternatively, don't store nullmove scores in the TT. YMMV.So if a null move causes a beta cut we don't have a move to save. What do we do here ?
Of the engine developers out there that do store null move beta cutoffs in the TT, how do you determine the depth to set on the entry? And do you use any special handling for such cases?