Page 1 of 2
What score to return from Table lookup
Posted: Sat Nov 27, 2010 9:53 am
by jdm64
I'm a bit confused as to what score I should return from a transposition table lookup. Say I have something similar to the following search and score retrieval from the table. Also, I'm saving the exact score into the table in the first place.
Code: Select all
int NegaScout(int alpha, int beta, int depth)
{
. . .
. . .
TransItem *tt_item;
if (tt->getItem(board->hash(), tt_item)) {
if (tt_item->getScore(alpha, beta, depth, score))
return score;
. . .
. . .
}
. . .
. . .
}
bool getScore(int alpha, int beta, int inDepth, int &inScore)
{
if ((type & HAS_SCORE) && depth >= inDepth) {
switch (type) {
case PV_NODE:
inScore = ????;
break;
case CUT_NODE:
inScore = ????;
break;
case ALL_NODE:
inScore = ????;
break;
}
return true;
} else {
return false;
}
}
What score should I be returning? I've thought of a few possibilities.
ALL_NODE: score
CUT_NODE: score
PV_NODE: score
ALL_NODE: alpha
CUT_NODE: beta
PV_NODE: score
ALL_NODE: min(score, alpha)
CUT_NODE: max(beta, score)
PV_NODE: max(alpha, min(score, beta))
Re: What score to return from Table lookup
Posted: Sun Nov 28, 2010 6:28 pm
by bob
jdm64 wrote:I'm a bit confused as to what score I should return from a transposition table lookup. Say I have something similar to the following search and score retrieval from the table. Also, I'm saving the exact score into the table in the first place.
Code: Select all
int NegaScout(int alpha, int beta, int depth)
{
. . .
. . .
TransItem *tt_item;
if (tt->getItem(board->hash(), tt_item)) {
if (tt_item->getScore(alpha, beta, depth, score))
return score;
. . .
. . .
}
. . .
. . .
}
bool getScore(int alpha, int beta, int inDepth, int &inScore)
{
if ((type & HAS_SCORE) && depth >= inDepth) {
switch (type) {
case PV_NODE:
inScore = ????;
break;
case CUT_NODE:
inScore = ????;
break;
case ALL_NODE:
inScore = ????;
break;
}
return true;
} else {
return false;
}
}
What score should I be returning? I've thought of a few possibilities.
ALL_NODE: score
CUT_NODE: score
PV_NODE: score
ALL_NODE: alpha
CUT_NODE: beta
PV_NODE: score
ALL_NODE: min(score, alpha)
CUT_NODE: max(beta, score)
PV_NODE: max(alpha, min(score, beta))
There are three cases...
(1) EXACT. you simply return "value" and stop the search at that node.
(2) LOWER. This is a fail-high node where you stored beta. But beta is a "lower bound" as the actual score could be even higher, so all you know is that the score is >= beta making beta a "lower bound.":
(3) UPPER. This is a fail-low node where you stored alpha. But alpha is an upper bound as the actual score could be even lower, so all you know is that the score is <= alpha making alpha an "upper bound".
The trick is in what you do with the results. For EXACT, if value >= beta, you fail high, if value <= alpha, you fail low, else you back up this score as "the result."
For LOWER, if value >= beta, you fail high, else you continue searching.
For UPPER, if value <= alpha, you fail low, else you continue searching.
All of the above assumes draft >= depth, of course.
Re: What score to return from Table lookup
Posted: Mon Nov 29, 2010 12:17 am
by jdm64
Am I also right in assuming that:
(PV_NODE == EXACT) && (CUT_NODE == LOWER) && (ALL_NODE == UPPER)
Because that's what I named the flags in the table.
A few more related questions:
1) when I save the value, do I save alpha/beta or best?
2) when retrieving lower/upper bound scores, do I return alpha/beta or the saved score?
So, the updated score retrieval would look like this?
Code: Select all
bool getScore(int alpha, int beta, int inDepth, int &outScore)
{
if ((type & HAS_SCORE) && depth >= inDepth) {
switch (type) {
case PV_NODE:
outScore = score;
return true;
case CUT_NODE:
if (score >= beta)
outScore = score; // or beta?
return true;
}
break;
case ALL_NODE:
if (score <= alpha) {
outScore = score; // or alpha?
return true;
}
break;
}
}
return false;
}
Re: What score to return from Table lookup
Posted: Mon Nov 29, 2010 4:16 am
by bob
jdm64 wrote:Am I also right in assuming that:
(PV_NODE == EXACT) && (CUT_NODE == LOWER) && (ALL_NODE == UPPER)
Because that's what I named the flags in the table.
Correct.
A few more related questions:
1) when I save the value, do I save alpha/beta or best?
At PV node, you save alpha which is normally the best score you found.
At an ALL node you save alpha since all scores are <= alpha.
At a CUT node, you save beta since score >= beta...
2) when retrieving lower/upper bound scores, do I return alpha/beta or the saved score?
Depends on how you implement it. You can pass current alpha/beta/depth values to HashProbe() and let it return something that says "return this score" or "score >= beta" or "score <= alpha". What you return and what you do with it depends on how you implement the hash code. In the case of Crafty, I do all the comparisons in HashProbe() and simply return HASH_HIT or HASH_MISS. I set alpha to the correct value inside HashProbe(). I can not imagine wanting to alter beta since alpha is the value you test everywhere inside the search since it is traditionally "best score found so far" unless this is an ALL node.
So, the updated score retrieval would look like this?
Code: Select all
bool getScore(int alpha, int beta, int inDepth, int &outScore)
{
if ((type & HAS_SCORE) && depth >= inDepth) {
switch (type) {
case PV_NODE:
outScore = score;
return true;
case CUT_NODE:
if (score >= beta)
outScore = score; // or beta?
return true;
}
break;
case ALL_NODE:
if (score <= alpha) {
outScore = score; // or alpha?
return true;
}
break;
}
}
return false;
}
Doesn't matter whether you return "score" or "beta" if score >= beta (and this is a LOWER hash entry). The former is called fail-soft, the latter (return beta if score > beta) is called "fail-hard".
Re: What score to return from Table lookup
Posted: Mon Nov 29, 2010 4:47 am
by jdm64
Thanks for your help so far.
bob wrote:A few more related questions:
1) when I save the value, do I save alpha/beta or best?
At PV node, you save alpha which is normally the best score you found.
At an ALL node you save alpha since all scores are <= alpha.
At a CUT node, you save beta since score >= beta...
So, values stored in the table are always "fail-hard"? But values returned can be either "fail-hard" or "fail-soft"?
For instance:
on a CUT node (score >= beta) I should do:
tt->save(beta, ...)
instead of
tt->save(score, ...)
on an ALL node (best <= alpha) I should do:
tt->save(alpha, ...)
instead of
tt->save(best, ...)
Re: What score to return from Table lookup
Posted: Mon Nov 29, 2010 5:20 am
by jwes
No, if you want to use failsoft, you need to use it everywhere in your search and hash table.
Re: What score to return from Table lookup
Posted: Mon Nov 29, 2010 6:40 am
by jdm64
jwes wrote:No, if you want to use failsoft, you need to use it everywhere in your search and hash table.
Except for Quiescence search which is fail-hard still -- right?
Re: What score to return from Table lookup
Posted: Mon Nov 29, 2010 10:37 am
by Michel
No, if you want to use failsoft, you need to use it everywhere in your search and hash table.
I think that is incorrect. For alpha-beta to work the search should return upper/lower bounds when the score is outside ]alpha,beta[. So it is allowed to fail hard in some places and soft in others.
Re: What score to return from Table lookup
Posted: Mon Nov 29, 2010 3:53 pm
by vladstamate
jdm64 wrote:jwes wrote:No, if you want to use failsoft, you need to use it everywhere in your search and hash table.
Except for Quiescence search which is fail-hard still -- right?
No. Since the iScore that you compare against alpha and beta is really obtained from evaluation in quiescence only (disregarding hash tables for a moment here) it means that if you have fail hard in QS then even if you have failsoft everywhere else in your engine it does not matter since the scores will already be clamped to alpha, beta from QS.
If you want to use failsoft then you should use it everywhere.
Regards,
Vlad.
Re: What score to return from Table lookup
Posted: Mon Nov 29, 2010 7:45 pm
by jdm64
vladstamate wrote:If you want to use failsoft then you should use it everywhere.
That might explain the bad playing I'm seeing when I enable QS (fail-hard) when the rest of my engine is fail-soft. I'll change the QS to fail-soft and see if that helps.
I'll remember: "Use fail-soft once, use it everywhere."