I'm confused.
If a TT score (with an associated move) at a node is exact I've been returning it without reference to node type or current alpha/beta.
But I notice that that seems to be wrong - and at a PV node one should only return an exact score if it lies within the current alpha/beta window.
I don't follow why. OK, the score is not exact based on the current window, but it has been exact based on a wider window, so surely it's still valid (like mate scores after the move loop are) - it's an exact score for the position but in the context is an alpha/beta cut. Also it seems to me that mate scores will get filtered out by limiting exact score to the current window.
I'm missing something obviously, but what...?
Fail soft context.
Exact TT scores and alpha/beta
Moderators: hgm, Rebel, chrisw
-
- Posts: 490
- Joined: Tue Feb 04, 2014 12:25 pm
- Full name: Colin Jenkins
-
- Posts: 931
- Joined: Tue Mar 09, 2010 3:46 pm
- Location: New York
- Full name: Álvaro Begué (RuyDos)
Re: Exact TT scores and alpha/beta
No, the logic is not quite that. The implication goes only one way: If the minimax score of the node lies within the current alpha/beta window, then the function must return it. Otherwise, it only needs to return something beta or above if the minimax score is beta or above, and something alpha or lower if the minimax score is alpha or lower.op12no2 wrote: But I notice that that seems to be wrong - and at a PV node one should only return an exact score if it lies within the current alpha/beta window.
Returning the exact minimax score is always a valid answer.
-
- Posts: 490
- Joined: Tue Feb 04, 2014 12:25 pm
- Full name: Colin Jenkins
Re: Exact TT scores and alpha/beta
Hi Álvaro,
Ah, OK, thanks, so I'm confusing myself about something I'm not in fact confused about I think I'm not sure where I got the notion now...
Ah, OK, thanks, so I'm confusing myself about something I'm not in fact confused about I think I'm not sure where I got the notion now...
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Exact TT scores and alpha/beta
Whether a score that had been stored in the TT is exact or a lower or upper bound is completely unrelated to the situation at the current node where you consider using it. The score type is determined when storing, i.e. if you store at a beta cutoff then you only know it is a lower bound, and if you store at a fail-low then you only know it is an upper bound. Mate scores are not very special IMO since even for a mate score you can determine the score type when storing it.op12no2 wrote:I'm confused.
If a TT score (with an associated move) at a node is exact I've been returning it without reference to node type or current alpha/beta.
But I notice that that seems to be wrong - and at a PV node one should only return an exact score if it lies within the current alpha/beta window.
I don't follow why. OK, the score is not exact based on the current window, but it has been exact based on a wider window, so surely it's still valid (like mate scores after the move loop are) - it's an exact score for the position but in the context is an alpha/beta cut. Also it seems to me that mate scores will get filtered out by limiting exact score to the current window.
I'm missing something obviously, but what...?
Fail soft context.
When considering to use a TT score for a TT cutoff you can usually always take the cutoff if the score type is "exact" and the stored depth is >= the current remaining depth - provided you are at a node where you consider TT cutoff at all. Upper bound scores greater or equal to beta, as well as lower bound scores lower or equal to alpha, must not be used for a TT cutoff because it is unknown whether the "real" scores are within or outside the current window.
EDIT: Please note the difference between a "beta cutoff" and a "TT cutoff", the latter means taking a shortcut by avoiding to research a subtree when there is reliable information in the TT about it. But you need to be sure whether the resulting score is inside or outside the window, therefore the restriction for upper/lower bound scores but not for exact scores.
-
- Posts: 490
- Joined: Tue Feb 04, 2014 12:25 pm
- Full name: Colin Jenkins
Re: Exact TT scores and alpha/beta
Thanks Sven,
That's what I do I think. For some reason I had got it into my head that exact scores needed to be within the current window but I could not figure out a logical reason why and it was driving me nuts
PS: are alpha and beta swapped (typos) in your middle para?
That's what I do I think. For some reason I had got it into my head that exact scores needed to be within the current window but I could not figure out a logical reason why and it was driving me nuts
Code: Select all
... depth check and get move etc
if (score <= -MINMATE && score >= -MATE)
score += node.ply;
else if (score >= MINMATE && score <= MATE)
score -= node.ply;
if (type == TT_EXACT)
return score;
if (type == TT_ALPHA && score <= alpha)
return score;
if (type == TT_BETA && score >= beta)
return score;
return TTSCORE_UNKNOWN;
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Exact TT scores and alpha/beta
EDIT: Yes, you are right I swapped alpha and beta ...op12no2 wrote:Thanks Sven,
That's what I do I think. For some reason I had got it into my head that exact scores needed to be within the current window but I could not figure out a logical reason why and it was driving me nuts
PS: are alpha and beta swapped (typos) in your middle para?Code: Select all
... depth check and get move etc if (score <= -MINMATE && score >= -MATE) score += node.ply; else if (score >= MINMATE && score <= MATE) score -= node.ply; if (type == TT_EXACT) return score; if (type == TT_ALPHA && score <= alpha) return score; if (type == TT_BETA && score >= beta) return score; return TTSCORE_UNKNOWN;
So I wanted to write:
"Upper bound scores greater than alpha, as well as lower bound scores lower than beta, must not be used for a TT cutoff because it is unknown whether the "real" scores are within or outside the current window."
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Exact TT scores and alpha/beta
My initial version had not been completely wrong but it was also not sufficient to derive correct code from it. We need to prevent "upper-bound-type" TT scores from causing a TT cutoff not only if they fail high to the current window (as I had written initially) but also if they are inside the window. And vice versa for "lower-bound-type" TT scores.
-
- Posts: 490
- Joined: Tue Feb 04, 2014 12:25 pm
- Full name: Colin Jenkins
Re: Exact TT scores and alpha/beta
op12no2 wrote:Thinking about that it seems to be wrong? SHould be > beta?Code: Select all
... if (type == TT_BETA && score >= beta) return score; ...
Ignoring the TT we would not return a score == beta as a beta/low cut, it'd be exact, so the quoted code is keeping us from finding exact moves on occasion...? I'll test it.
-
- Posts: 27790
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Exact TT scores and alpha/beta
The conventional meaning of alpha and beta is such that any score >= beta is a fail high and lower bound, and any score <= alpha is a fail low and upper bound. If alpha < score < beta for a score returned by the search, the score is exact, but that of course makes it BOTH an upper and a lower bound. So in fact any score > alpha is a lower bound, and any score < beta an upper bound.
This becomes quite logical when you realize alpha and beta are nothing but scores you already found in side branches (through the "if(score > alpha) alpha = score"). You are not interested in scores that are the same, only in scores that are better than what you had. So not equal to alpha or beta.
I always do it like this:
While storing:
tt->flags = (bestScore > originalAlpha)*F_LOWER + (bestScore < beta)*F_UPPER;
While probing:
if((tt->flags & F_LOWER || tt->score <= originalAlpha) && (tt->flags & F_UPPER || tt->score >= beta)) ScoreIsUsable();
This becomes quite logical when you realize alpha and beta are nothing but scores you already found in side branches (through the "if(score > alpha) alpha = score"). You are not interested in scores that are the same, only in scores that are better than what you had. So not equal to alpha or beta.
I always do it like this:
While storing:
tt->flags = (bestScore > originalAlpha)*F_LOWER + (bestScore < beta)*F_UPPER;
While probing:
if((tt->flags & F_LOWER || tt->score <= originalAlpha) && (tt->flags & F_UPPER || tt->score >= beta)) ScoreIsUsable();
-
- Posts: 931
- Joined: Tue Mar 09, 2010 3:46 pm
- Location: New York
- Full name: Álvaro Begué (RuyDos)
Re: Exact TT scores and alpha/beta
hgm wrote:
While storing:
tt->flags = (bestScore > originalAlpha)*F_LOWER + (bestScore < beta)*F_UPPER;
An alternative is to use this pseudo-code:
Code: Select all
int negamax(...) {
if (depth <= 0) return blah();
...
bound_type = UpperBound;
for (auto move : moves) {
make_move(move);
int score = -negamax(...);
undo_move(move);
if (score > alpha) {
bound_type = Exact;
alpha = score;
if (score >= beta) {
bound_type = LowerBound;
break;
}
}
}
store_hash(..., bound_type, ...);
return alpha;
}