What score to return from Table lookup

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
jdm64
Posts: 41
Joined: Thu May 27, 2010 9:32 pm

What score to return from Table lookup

Post by jdm64 » Sat Nov 27, 2010 8:53 am

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))

bob
Posts: 20566
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: What score to return from Table lookup

Post by bob » Sun Nov 28, 2010 5:28 pm

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.

jdm64
Posts: 41
Joined: Thu May 27, 2010 9:32 pm

Re: What score to return from Table lookup

Post by jdm64 » Sun Nov 28, 2010 11:17 pm

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&#40;int alpha, int beta, int inDepth, int &outScore&#41;
&#123;
        if (&#40;type & HAS_SCORE&#41; && depth >= inDepth&#41; &#123;
                switch &#40;type&#41; &#123;
                case PV_NODE&#58;
                        outScore = score;
                        return true;
                case CUT_NODE&#58;
                        if &#40;score >= beta&#41;
                                outScore = score; // or beta?
                                return true;
                        &#125;
                        break;
                case ALL_NODE&#58;
                        if &#40;score <= alpha&#41; &#123;
                                outScore = score; // or alpha?
                                return true;
                        &#125;
                        break;
                &#125;
        &#125;
        return false;
&#125;

bob
Posts: 20566
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: What score to return from Table lookup

Post by bob » Mon Nov 29, 2010 3:16 am

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&#40;int alpha, int beta, int inDepth, int &outScore&#41;
&#123;
        if (&#40;type & HAS_SCORE&#41; && depth >= inDepth&#41; &#123;
                switch &#40;type&#41; &#123;
                case PV_NODE&#58;
                        outScore = score;
                        return true;
                case CUT_NODE&#58;
                        if &#40;score >= beta&#41;
                                outScore = score; // or beta?
                                return true;
                        &#125;
                        break;
                case ALL_NODE&#58;
                        if &#40;score <= alpha&#41; &#123;
                                outScore = score; // or alpha?
                                return true;
                        &#125;
                        break;
                &#125;
        &#125;
        return false;
&#125;
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".

jdm64
Posts: 41
Joined: Thu May 27, 2010 9:32 pm

Re: What score to return from Table lookup

Post by jdm64 » Mon Nov 29, 2010 3:47 am

Thanks for your help so far. :D
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, ...)

jwes
Posts: 778
Joined: Sat Jul 01, 2006 5:11 am

Re: What score to return from Table lookup

Post by jwes » Mon Nov 29, 2010 4:20 am

No, if you want to use failsoft, you need to use it everywhere in your search and hash table.

jdm64
Posts: 41
Joined: Thu May 27, 2010 9:32 pm

Re: What score to return from Table lookup

Post by jdm64 » Mon Nov 29, 2010 5:40 am

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?

Michel
Posts: 2050
Joined: Sun Sep 28, 2008 11:50 pm

Re: What score to return from Table lookup

Post by Michel » Mon Nov 29, 2010 9:37 am

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.

vladstamate
Posts: 161
Joined: Thu Jan 08, 2009 8:06 pm
Location: San Francisco, USA
Contact:

Re: What score to return from Table lookup

Post by vladstamate » Mon Nov 29, 2010 2:53 pm

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.

jdm64
Posts: 41
Joined: Thu May 27, 2010 9:32 pm

Re: What score to return from Table lookup

Post by jdm64 » Mon Nov 29, 2010 6:45 pm

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."

Post Reply