What score to return from Table lookup

[bob]

Thanks for your help so far.

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]

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]

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]

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(int alpha, int beta, int depth)
{
        // get all capture moves if not in check, else all moves
        MoveList *ptr = board->getMovesList(board->currPlayer(), tactical[depth]? MOVE_ALL : MOVE_CAPTURE);

        // no moves, so position must be quiet enough
        if (!ptr->size) {
                delete ptr;
                return tactical[depth]? CHECKMATE_SCORE : -board->eval();
        }
        int score = -board->eval();

        // does standing pat cause cutoff?
        if (score >= beta) {
                delete ptr;
                return score;
        }
        int best = MIN_SCORE;

        alpha = max(alpha, score);

        sort(ptr->list.begin(), ptr->list.begin() + ptr->size, cmpScore);

        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]

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(int alpha, int beta)
{
    int bestV = evaluate();
    if (bestV >= beta) {
        return bestV;
    }
    generateMoves();
    for (Move * m = nextMove(); m != 0; m = nextMove()) {
        makeMove(m);
        int v = -qSearch(-beta, -Max(alpha, bestV)));
        unmakeMove(m);
        if (v > bestV) {
            bestV = v;
            if (bestV >= beta) {
                break;
            }
        }
    }
    return bestV;
}

Sven