alpha bound in hash table

[xr_a_y]

I may be wrong (as often ...) but it seems to me that TT move with alpha bound has a score but never has an associated move.
Since the only way to insert an alpha bound in TT is if no move raised alpha and thus "best move" was never updated.

In this old post http://talkchess.com/forum3/viewtopic.p ... 10#p762826, I found that in Weini I was never using alpha bound in TT because I was never inserting something in TT without a "valid move". That is why the (bad) solution was to use the first move in list when an alpha bound in inserted inside TT so that alpha bound are in TT and TT scores might be returned more often. In Weini this indeed leads to solve fine70 way faster than before.

This morning I faced more or less the same issue in Minic, but the other way around. I was trying to get ride of the ugly line

Code: Select all

if (bestMove == INVALIDMOVE)  bestMove = moves[0]; // so that B_alpha are stored in TT

and simply accept to add TT entry without valid move ; I had to add some guards at some point to ensure TT move is valid before using it, but was able to use (and return) TT score without valid move in case of alpha bound.

I was expecting absolutely no change in playing strength but see a great -150elo !! and a totally new behavior in solving fine70.

I am quite confused with this ...

Let's take the simplest code

Code: Select all

ScoreType pvs(ScoreType alpha, ScoreType beta, const Position & p, DepthType depth, bool pvnode, unsigned int ply, std::vector<Move> & pv, DepthType & seldepth){
    if ( std::max(1,(int)std::chrono::duration_cast<std::chrono::milliseconds>(Clock::now() - TimeMan::startTime).count()) > currentMoveMs ){
        stopFlag = true;
        return STOPSCORE;
    }

    if ((int)ply > seldepth) seldepth = ply;

    if ( depth <= 0 ) return qsearch(alpha,beta,p,ply,seldepth);

    const bool rootnode = ply == 1;

    if (isDraw(p, pvnode)) return 0;

    float gp = 0;
    if (ply >= MAX_PLY - 1 || depth >= MAX_DEPTH - 1) return eval(p, gp);

    alpha = std::max(alpha, (ScoreType)(-MATE + ply));
    beta  = std::min(beta,  (ScoreType)( MATE - ply - 1));
    if (alpha >= beta) return alpha;

    TT::Entry e;
    if (TT::getEntry(computeHash(p), depth, e)) { 
        if (e.h != 0 && !rootnode && std::abs(e.score) < MATE - MAX_DEPTH && !pvnode &&
                ( (e.b == TT::B_alpha && e.score <= alpha) || (e.b == TT::B_beta  && e.score >= beta) || (e.b == TT::B_exact) ) ) {
            if ( e.m != INVALIDMOVE) pv.push_back(e.m); // here e.m might be INVALIDMOVE if B_alpha
            return e.score;
        }
    }

    const bool isInCheck = isAttacked(p, kingSquare(p));
    ScoreType val;

    // IID
    if ( (e.h == 0 /*|| e.d < depth/3*/) && pvnode && depth >= iidMinDepth){
        std::vector<Move> iidPV;
        pvs(alpha,beta,p,depth/2,pvnode,ply,iidPV,seldepth);
        if ( !stopFlag) TT::getEntry(computeHash(p), depth, e);
        if (stopFlag) return STOPSCORE;
    }

    int validMoveCount = 0;
    bool alphaUpdated = false;
    Move bestMove = INVALIDMOVE;

    std::vector<Move> moves;
    generate(p,moves);
    if ( moves.empty() ) return isInCheck?-MATE + ply : 0;
    sort(*this,moves,p,&e);
    /// ?????       if (bestMove == INVALIDMOVE)  bestMove = moves[0]; // so that B_alpha are stored in TT

    for(auto it = moves.begin() ; it != moves.end() && !stopFlag ; ++it){
        Position p2 = p;
        if ( ! apply(p2,*it) ) continue;
        validMoveCount++;
        val = -pvs(-beta,-alpha,p2,depth-1+extension,pvnode,ply+1,childPV,seldepth);

        if ( !stopFlag && val > alpha ){
            alphaUpdated = true;
            if ( val >= beta ){
                TT::setEntry({*it,val,TT::B_beta,depth,computeHash(p)});
                return val;
            }
            alpha = val;
            bestMove = *it;
        }
    }

    if ( validMoveCount==0 && !stopFlag) return isInCheck?-MATE + ply : 0;
    ///@todo here validMoveCount shall not be present, this does not allow to store alpha bound !!!!
    if ( !stopFlag && /*validMoveCount*/ bestMove != INVALIDMOVE ) TT::setEntry({bestMove,alpha,alphaUpdated?TT::B_exact:TT::B_alpha,depth,computeHash(p)});

    return stopFlag?STOPSCORE:alpha;
 

Is it what shall be done ??

[Sven]

I think that you should better

1) return STOPSCORE immediately if stopFlag is set after returning from recursive pvs() call,
2) otherwise always store something in the TT, with bestmove possibly being INVALIDMOVE, and
3) remove the "/// ????? if (bestMove == INVALIDMOVE) bestMove = moves[0];" line completely since uncommenting it would be wrong.

1) would simplify your code at the end of pvs() into:

Code: Select all

    if (validMoveCount == 0) return isInCheck ? -MATE + ply : 0;
    TT::setEntry({bestMove, alpha, alphaUpdated ? TT::B_exact : TT::B_alpha, depth, computeHash(p)});
    return alpha;

[RubiChess]

I may be wrong (as often ...) but it seems to me that TT move with alpha bound has a score but never has an associated move.
Since the only way to insert an alpha bound in TT is if no move raised alpha and thus "best move" was never updated.

Rubi uses a fail soft environment and stores the best move in TT even if it doesn't raise alpha.
But I must admit that I never tested how much ELO this is worth.

Andreas

[xr_a_y]

Good ideas thanks !

[xr_a_y]

Rubi uses a fail soft environment and stores the best move in TT even if it doesn't raise alpha.
But I must admit that I never tested how much ELO this is worth.
Andreas

Are you storing "bestScore" or alpha. I suppose alpha shall be stored because this score will be used if

Code: Select all

e.b == TT::B_alpha && e.score <= alpha

and as alpha is always >= bestScore, I think it is safer in a fail-soft framework.

[RubiChess]

Are you storing "bestScore" or alpha. I suppose alpha shall be stored because this score will be used if

Code: Select all

e.b == TT::B_alpha && e.score <= alpha

and as alpha is always >= bestScore, I think it is safer in a fail-soft framework.

We don't need safe solutions. We need ELO-gaining solutions
Indeed I'm storing bestScore to the TT. Should be more valuable as lower bound than alpha. But again: I don't know/remember if I tested this for ELO.

Andreas

[Joost Buijs]

I may be wrong (as often ...) but it seems to me that TT move with alpha bound has a score but never has an associated move.
Since the only way to insert an alpha bound in TT is if no move raised alpha and thus "best move" was never updated.

Rubi uses a fail soft environment and stores the best move in TT even if it doesn't raise alpha.
But I must admit that I never tested how much ELO this is worth.

Andreas

How on earth can you determine what the best move is if it doesn't raise alpha? My guess is that it is probably the first move you tried, maybe the move from the transposition table or a capture or killer move, but you never know if it is really the best move (from the engines point of view) for that position.

[sovaz1997]

Are you storing "bestScore" or alpha. I suppose alpha shall be stored because this score will be used if

Code: Select all

e.b == TT::B_alpha && e.score <= alpha

and as alpha is always >= bestScore, I think it is safer in a fail-soft framework.

We don't need safe solutions. We need ELO-gaining solutions
Indeed I'm storing bestScore to the TT. Should be more valuable as lower bound than alpha. But again: I don't know/remember if I tested this for ELO.

Andreas

Yes, try don't make save if it's doesn't increase alpha, since this move will most likely not be reinforcing, but it will slow down in sorting. I think you can check it out at a very fast TC.

[xr_a_y]

How on earth can you determine what the best move is if it doesn't raise alpha? My guess is that it is probably the first move you tried, maybe the move from the transposition table or a capture or killer move, but you never know if it is really the best move (from the engines point of view) for that position.

You can still store the move with the highest score in a fail-soft framework I guess ?

Code: Select all

        if ( val > bestScore ){
            bestScore = val;
            bestMove = *it;
            if ( val > alpha ){
                updatePV(pv, *it, childPV);
                alphaUpdated = true;
                alpha = val;
                hashBound = TT::B_exact;
                if ( val >= beta ){
                    hashBound = TT::B_beta;
                    break;
                }
            }
        }

Xiphos is doing this way I think

[Joost Buijs]

You can still store the move with the highest score in a fail-soft framework I guess ?

You can do this by setting best-score at -inf at the start, but there is no way of telling that it is really the best move, if it gives you additional Elo it will be fine of course.

In the past I saw that Stockfish, when they were overwriting an entry with the same key, and there was no best-move available, they kept the old move that was already in the entry, I don't know if they still do it this way.