alpha bound in hash table

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
xr_a_y
Posts: 266
Joined: Sat Nov 25, 2017 1:28 pm
Location: France

alpha bound in hash table

Post by xr_a_y » Sun Nov 25, 2018 12:53 pm

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
Posts: 3704
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: alpha bound in hash table

Post by Sven » Sun Nov 25, 2018 1:39 pm

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;
Sven Schüle (engine author: Jumbo, KnockOut, Surprise)

RubiChess
Posts: 39
Joined: Fri Mar 30, 2018 5:20 am

Re: alpha bound in hash table

Post by RubiChess » Sun Nov 25, 2018 2:51 pm

xr_a_y wrote:
Sun Nov 25, 2018 12:53 pm
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

User avatar
xr_a_y
Posts: 266
Joined: Sat Nov 25, 2017 1:28 pm
Location: France

Re: alpha bound in hash table

Post by xr_a_y » Sun Nov 25, 2018 3:14 pm

Good ideas thanks !

User avatar
xr_a_y
Posts: 266
Joined: Sat Nov 25, 2017 1:28 pm
Location: France

Re: alpha bound in hash table

Post by xr_a_y » Sun Nov 25, 2018 3:55 pm

RubiChess wrote:
Sun Nov 25, 2018 2:51 pm
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
Posts: 39
Joined: Fri Mar 30, 2018 5:20 am

Re: alpha bound in hash table

Post by RubiChess » Sun Nov 25, 2018 4:38 pm

xr_a_y wrote:
Sun Nov 25, 2018 3:55 pm
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
Posts: 772
Joined: Thu Jul 16, 2009 8:47 am
Location: Almere, The Netherlands

Re: alpha bound in hash table

Post by Joost Buijs » Sun Nov 25, 2018 5:41 pm

RubiChess wrote:
Sun Nov 25, 2018 2:51 pm
xr_a_y wrote:
Sun Nov 25, 2018 12:53 pm
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
Posts: 166
Joined: Sun Nov 13, 2016 9:37 am

Re: alpha bound in hash table

Post by sovaz1997 » Sun Nov 25, 2018 6:15 pm

RubiChess wrote:
Sun Nov 25, 2018 4:38 pm
xr_a_y wrote:
Sun Nov 25, 2018 3:55 pm
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.
Zevra chess engine
Binary, source and description here: https://gitlab.com/sovaz1997/zevra2/tags

User avatar
xr_a_y
Posts: 266
Joined: Sat Nov 25, 2017 1:28 pm
Location: France

Re: alpha bound in hash table

Post by xr_a_y » Sun Nov 25, 2018 6:23 pm

Joost Buijs wrote:
Sun Nov 25, 2018 5:41 pm
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
Posts: 772
Joined: Thu Jul 16, 2009 8:47 am
Location: Almere, The Netherlands

Re: alpha bound in hash table

Post by Joost Buijs » Mon Nov 26, 2018 7:35 am

xr_a_y wrote:
Sun Nov 25, 2018 6:23 pm
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.

Post Reply