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.
bob
Posts: 20478
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: What score to return from Table lookup

Post by bob » Tue Nov 30, 2010 3:11 am

jdm64 wrote: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"?
No. Whenever you get a score outside the alpha/beta window, you can always store that. Depends on what you are trying to do. The common goal is to narrow the window as much as possible, since the narrower the window the smaller the tree. In Negamax, you would not want to lower alpha, since that increases the size of the tree and is also bad for you. But you would want to raise beta if possible since that is good for you.

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

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

Re: What score to return from Table lookup

Post by bob » Tue Nov 30, 2010 3:13 am

Michel wrote:
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.
Correct. Getting sloppy just makes the tree a bit larger, but whether you return beta or beta+3, the answer is correct, since saying score > beta or score > beta+3 is accurate, but score > beta+3 has a little more information.

Sven
Posts: 3822
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: What score to return from Table lookup

Post by Sven » Tue Nov 30, 2010 1:40 pm

jdm64 wrote:
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."
However, a "fail-soft" QS implementation will not be the same as "fail-soft" in full-width search due to "stand pat". While in full search you initialize some "bestValue" to -INFINITY (which is essential for fail-soft in order to be able to return a bestValue < alpha), in QS you initialize bestValue to the stand pat value at least which _could_ be inside the alpha-beta window already.

If you don't use "fail-soft" in QS then in my opinion you effectively disable any "fail-soft" implementation in your full-width search since when failing high you always return exactly beta and when failing low you always return exactly alpha.

Sven

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

Re: What score to return from Table lookup

Post by jdm64 » Tue Nov 30, 2010 8:07 pm

Sven Schüle wrote:However, a "fail-soft" QS implementation will not be the same as "fail-soft" in full-width search due to "stand pat". While in full search you initialize some "bestValue" to -INFINITY (which is essential for fail-soft in order to be able to return a bestValue < alpha), in QS you initialize bestValue to the stand pat value at least which _could_ be inside the alpha-beta window already.
I do return if "stand pat" causes beta-cutoff. But if it doesn't, I set Best to -INFINITY and continue searching -- forgetting "stand pat". So, Best only gets updated with real values from deeper QS searches.

Code: Select all

quiescence&#40;int alpha, int beta, int depth&#41;
&#123;
        // get all capture moves if not in check, else all moves
        MoveList *ptr = board->getMovesList&#40;board->currPlayer&#40;), tactical&#91;depth&#93;? MOVE_ALL &#58; MOVE_CAPTURE&#41;;

        // no moves, so position must be quiet enough
        if (!ptr->size&#41; &#123;
                delete ptr;
                return tactical&#91;depth&#93;? CHECKMATE_SCORE &#58; -board->eval&#40;);
        &#125;
        int score = -board->eval&#40;);

        // does standing pat cause cutoff?
        if &#40;score >= beta&#41; &#123;
                delete ptr;
                return score;
        &#125;
        int best = MIN_SCORE;

        alpha = max&#40;alpha, score&#41;;

        sort&#40;ptr->list.begin&#40;), ptr->list.begin&#40;) + ptr->size, cmpScore&#41;;

        for &#40;int n = 0; n < ptr->size; n++) &#123;
                // set check for opponent                                             
                tactical&#91;depth + 1&#93; = ptr->list&#91;n&#93;.check;

                board->make&#40;ptr->list&#91;n&#93;.move&#41;;
                score = -Quiescence&#40;-beta, -alpha, depth + 1&#41;;
                board->unmake&#40;ptr->list&#91;n&#93;.move&#41;;

                if &#40;score >= beta&#41; &#123;
                        delete ptr;
                        return score;
                &#125;
                best = max&#40;best, score&#41;;
                alpha = max&#40;alpha, score&#41;;
        &#125;
        // fail low
        delete ptr;
        return best;
&#125;

Sven
Posts: 3822
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: What score to return from Table lookup

Post by Sven » Sat Dec 04, 2010 9:14 pm

jdm64 wrote:
Sven Schüle wrote:However, a "fail-soft" QS implementation will not be the same as "fail-soft" in full-width search due to "stand pat". While in full search you initialize some "bestValue" to -INFINITY (which is essential for fail-soft in order to be able to return a bestValue < alpha), in QS you initialize bestValue to the stand pat value at least which _could_ be inside the alpha-beta window already.
I do return if "stand pat" causes beta-cutoff. But if it doesn't, I set Best to -INFINITY and continue searching -- forgetting "stand pat". So, Best only gets updated with real values from deeper QS searches.
The basic idea of QS is to find out if the moving side can win material, and if it can't, to return the static evaluation. I can't see how your implementation does that.
Also I can't see the reason why you use -eval() instead of eval().
This is one possible way of a "standard" QS implementation using "fail-soft".

Code: Select all

int qSearch&#40;int alpha, int beta&#41;
&#123;
    int bestV = evaluate&#40;);
    if &#40;bestV >= beta&#41; &#123;
        return bestV;
    &#125;
    generateMoves&#40;);
    for &#40;Move * m = nextMove&#40;); m != 0; m = nextMove&#40;)) &#123;
        makeMove&#40;m&#41;;
        int v = -qSearch&#40;-beta, -Max&#40;alpha, bestV&#41;));
        unmakeMove&#40;m&#41;;
        if &#40;v > bestV&#41; &#123;
            bestV = v;
            if &#40;bestV >= beta&#41; &#123;
                break;
            &#125;
        &#125;
    &#125;
    return bestV;
&#125;
Sven

Post Reply