Newbie Question concerning Transposition Tables

[smatovic]

Thus far my engine works with an AlphaBeta, Qsearch and move ordering.

Transpoistion Tables are the next item on todo-list, but i cant get them working "correct". Maybe someone could help me.

I try to store in AlphaBeta-search the score and the move with flag for fail high and fail low and exact score in a Transposition Table. Zobrist-Hashing seems to work allright (after adding castle rights).

But in which case do i update alpha respectively beta score or use the stored move from TT?

I am even not sure if i store the flag right.

Code: Select all

Score alphabeta_qs_mvvlva_tt(Bitboard *board, Boardindex *bindex, int som, int depth, Move lastmove, Score alpha, Score beta) {

    Move moves[218];
    Move bestmove = 0;
    int i,movecounter = 0;
    int flag = 0;
    Score score = ALPHA;
    U64 hash = compute_hash(board, som);
    struct tt *tt;
    NODECOUNT++;

    score = eval(board, bindex, som);

    tt = &TT[hash>>core_bit];
    if (tt->hash == hash && tt->depth >= max_depth-depth+PLY) {
        if (tt->flag != 0) {
            moves[movecounter] = tt->bestmove;
            movecounter++;
        }
        if (tt->flag == 1) {
            alpha = MAX(alpha, tt->score);
        }
        if (tt->flag ==-1) {
            beta = MIN(beta, tt->score);
        }
    }

    if &#40;depth <= 0 &&  kingincheck&#40;board,som&#41;)
        depth++;

    if &#40;depth <= 0&#41; 
        return alphabeta_qsearch_mvvlva_tt&#40;board, bindex, som, depth, lastmove, alpha, beta&#41;;

    movecounter = genmoves&#40;board, bindex, moves, movecounter, som, lastmove&#41;;

    if &#40;movecounter <= 0&#41;
        return score;

    qsort&#40;moves, movecounter, sizeof&#40;*moves&#41;, mvv_lva&#41;;

    MOVECOUNT+= movecounter;

    for &#40;i=0; i < movecounter; i++) &#123;
        domove&#40;board, bindex, moves&#91;i&#93;, som&#41;;
        score = -alphabeta_qs_mvvlva_tt&#40;board, bindex, !som, depth-1, moves&#91;i&#93;, -beta, -alpha&#41;;
        if &#40;score >= beta&#41; &#123;
            undomove&#40;board, bindex, moves&#91;i&#93;, som&#41;;
            beta_cut++;
            bestmove = moves&#91;i&#93;;
            flag = 1;
            save_to_tt&#40;hash, bestmove, score, flag, max_depth-depth+PLY&#41;;
            return score;
        &#125;
        if &#40;score > alpha&#41; &#123;
            alpha_cut++;
            alpha = score;
            bestmove = moves&#91;i&#93;;
            flag = -1;
        &#125;
        undomove&#40;board, bindex, moves&#91;i&#93;, som&#41;;
    &#125;
    save_to_tt&#40;hash, bestmove, alpha, flag, max_depth-depth+PLY&#41;;
    return alpha;

}

[Desperado]

hi Srdja,

well, i have not looked very intensively at your code, but
there are some eye-catchers... let s go

1:
====

your definitions (if i read correctly):

Code: Select all

FAIL_LO (maximum-score) :  0
FAIL_HI (minimum-score) :  1
EXCAT : -1

your code:

Code: Select all

    tt = &TT[hash>>core_bit]; 
    if (tt->hash == hash && tt->depth >= max_depth-depth+PLY) { 
        if (tt->flag != 0) { 
            moves[movecounter] = tt->bestmove; 
            movecounter++; 
        } 
        if (tt->flag == 1) { 
            alpha = MAX(alpha, tt->score); 
        } 
        if (tt->flag ==-1) { 
            beta = MIN(beta, tt->score); 
        } 
    } 

hint:

Code: Select all

tt = &TT[hash>>core_bit]; 
if (tt->hash == hash && tt->depth >= depth /*remaining depth*/) 
{  
 //minimum score stored (was fail hi)
 if(tt->flag == 1) 
 {
  //and now, if minimumScore >= beta ?!,
  //you can of course return the score
  if(tt->score >= beta) return(tt->score);
         
  //now update the bound,which is theoretically
  //absolute ok, some time ago i had bad experience
  //with it. it is not a must to do so. simply take care
  //what will happen and test carefully.
  alpha = MAX(alpha, tt->score);
 }

  //maximum score stored (was fail lo)
  //_0_ is your fail_lo definition right ?!
  if (tt->flag == 0) // 
  { 
   //and now, if maximumScore <= alpha?!,
   //you can of course return the score
   if&#40;tt->score <= alpha&#41; return&#40;tt->score&#41;;
         
   //same hint as above with updates of bounds
   beta = MIN&#40;beta, tt->score&#41;; 
  &#125; 

  //totally missing now is _exact_ score
  if&#40;tt->flag == -1&#41; &#123;return&#40;tt->score&#41;;&#125;

 //now,if you not already returned a value
 //always use the existing move from TT 
 if&#40;tt->bestmove&#41; moves&#91;movecounter++&#93; = tt>bestmove;       
&#125; 

2:
====

it is not clear to me, but it looks like a bug, what is happening when
you update the bounds (dont return,if possible) and enter your _moveLoop_ with an alpha >= beta, or at least the codeblock where
alpha should be updated will not be updated. you may not update bestmove information and so on...

3:
====

if would do the nodecount _after_ the recursive call of "alphabeta_qsearch_mvvlva_tt", and call this before tt-lookup.
Just not to count twice the horizon nodes, which may give wrong impression if you compare your nps with other engines.

Hope i could help...

Michael

[Desperado]

too, late for edit...

so just to be more clear on point 3: just avoid...

Code: Select all

int search(...)
{
 nodecount++;
 if&#40;depth<1&#41; return&#40;searchQS&#40;))

 ...
 value = -search&#40;)
 ...
&#125;

int searchQS&#40;...)
&#123;
 nodecount++; //horizon node ?, counted 2x ?

 ...
 value = -searchQS&#40;)
 ...
&#125;

which can easily double your nps, and is definitely not intended

regards

[bob]

Thus far my engine works with an AlphaBeta, Qsearch and move ordering.

Transpoistion Tables are the next item on todo-list, but i cant get them working "correct". Maybe someone could help me.

I try to store in AlphaBeta-search the score and the move with flag for fail high and fail low and exact score in a Transposition Table. Zobrist-Hashing seems to work allright (after adding castle rights).

But in which case do i update alpha respectively beta score or use the stored move from TT?

I am even not sure if i store the flag right.

First, some terminology so that there is no confusion later. You store 3 types of entries, EXACT, UPPER and LOWER. The latter two are often misused.

UPPER is what you store when you fail low at a node. You search every move, and when you are done, alpha was not changed. This is called UPPER because the current score (alpha) is an upper bound on the score. It could actually be lower...

For LOWER, you find a move that causes a fail high. But all you know is that best (alpha) is >= beta, so this is a LOWER bound on the score and the true score could be even higher.

EXACT is pretty obvious...

To use an entry, you have to (a) match the signature of the entry to the current Zobrist signature and (b) the current depth must be <= the draft (depth) stored in the table. If those are true, you have 3 cases:

(1) EXACT entry. You simply return the score stored, possibly modified if you store checkmate scores since a mate needs to be stored as mate in N from the current position, not mate in N from the root.

(2) LOWER entry. If the stored bound is >= current beta value, then you return something that tells search to "fail high" here as well without doing any further searching.

(3) UPPER entry. If the stored bound is <= alpha, you return something that tells the search to "fail low" here, and also not do any further searching.

The idea of adjusting alpha/beta is pretty much worthless with today's PVS implementations, since almost all nodes are searched with a zero-width window and there is no room for adjustment. If you want to raise the alpha bound, then you should be failing high anyway. If you want to lower beta, you should fail low, since beta is already set to alpha + 1 and any lower will be impossible anyway.

To keep it straight in your head, remember what happened when you stored the entry. And if the sigs match, the draft is sufficient, and the stored bound is compatible with current bound, then you do no searching and just do exactly what you did when you stored the position, which was to return to the previous ply...

Code: Select all

Score alphabeta_qs_mvvlva_tt(Bitboard *board, Boardindex *bindex, int som, int depth, Move lastmove, Score alpha, Score beta) {

    Move moves[218];
    Move bestmove = 0;
    int i,movecounter = 0;
    int flag = 0;
    Score score = ALPHA;
    U64 hash = compute_hash(board, som);
    struct tt *tt;
    NODECOUNT++;

    score = eval(board, bindex, som);

    tt = &TT[hash>>core_bit];
    if (tt->hash == hash && tt->depth >= max_depth-depth+PLY) {
        if (tt->flag != 0) {
            moves[movecounter] = tt->bestmove;
            movecounter++;
        }
        if (tt->flag == 1) {
            alpha = MAX(alpha, tt->score);
        }
        if (tt->flag ==-1) {
            beta = MIN(beta, tt->score);
        }
    }

    if &#40;depth <= 0 &&  kingincheck&#40;board,som&#41;)
        depth++;

    if &#40;depth <= 0&#41; 
        return alphabeta_qsearch_mvvlva_tt&#40;board, bindex, som, depth, lastmove, alpha, beta&#41;;

    movecounter = genmoves&#40;board, bindex, moves, movecounter, som, lastmove&#41;;

    if &#40;movecounter <= 0&#41;
        return score;

    qsort&#40;moves, movecounter, sizeof&#40;*moves&#41;, mvv_lva&#41;;

    MOVECOUNT+= movecounter;

    for &#40;i=0; i < movecounter; i++) &#123;
        domove&#40;board, bindex, moves&#91;i&#93;, som&#41;;
        score = -alphabeta_qs_mvvlva_tt&#40;board, bindex, !som, depth-1, moves&#91;i&#93;, -beta, -alpha&#41;;
        if &#40;score >= beta&#41; &#123;
            undomove&#40;board, bindex, moves&#91;i&#93;, som&#41;;
            beta_cut++;
            bestmove = moves&#91;i&#93;;
            flag = 1;
            save_to_tt&#40;hash, bestmove, score, flag, max_depth-depth+PLY&#41;;
            return score;
        &#125;
        if &#40;score > alpha&#41; &#123;
            alpha_cut++;
            alpha = score;
            bestmove = moves&#91;i&#93;;
            flag = -1;
        &#125;
        undomove&#40;board, bindex, moves&#91;i&#93;, som&#41;;
    &#125;
    save_to_tt&#40;hash, bestmove, alpha, flag, max_depth-depth+PLY&#41;;
    return alpha;

}

[smatovic]

too, late for edit...

so just to be more clear on point 3: just avoid...

thx and yepp, nodecount dropped by almost a half. but nice to see that mvv_lva isnt that bad

I was confused by fail-low. There is no bestmove i could try first...now the engine plays better and faster.

Code: Select all

Score alphabeta_qs_mvvlva_tt(Bitboard *board, Boardindex *bindex, int som, int depth, Move lastmove, Score alpha, Score beta) {

    Move moves[218];
    Move bestmove = 0;
    int i,movecounter = 0;
    int flag = -1;
    /*  1 => Lower bound, Fail high */
    /*  0 => Exsact Score, alpha was increased */
    /* -1 => Upper bound, Fail low */

    Score score = ALPHA;
    U64 hash = compute_hash(board, som);
    struct tt *tt;

    score = eval(board, bindex, som);

    tt = &TT[hash>>core_bit];
    if (tt->hash == hash && tt->depth >= max_depth-depth+PLY) {
        if ( tt->flag >= 0) {
            moves[movecounter] = tt->bestmove;
            movecounter++;

        }
    }


    if &#40;depth <= 0 &&  kingincheck&#40;board,som&#41;)
        depth++;

    if &#40;depth <= 0&#41; 
        return alphabeta_qsearch_mvvlva_tt&#40;board, bindex, som, depth, lastmove, alpha, beta&#41;;

    NODECOUNT++;

    movecounter = genmoves&#40;board, bindex, moves, movecounter, som, lastmove&#41;;

    if &#40;movecounter <= 0&#41;
        return score;

    qsort&#40;moves, movecounter, sizeof&#40;*moves&#41;, mvv_lva&#41;;

    MOVECOUNT+= movecounter;

    for &#40;i=0; i < movecounter; i++) &#123;
        domove&#40;board, bindex, moves&#91;i&#93;, som&#41;;
        score = -alphabeta_qs_mvvlva_tt&#40;board, bindex, !som, depth-1, moves&#91;i&#93;, -beta, -alpha&#41;;
        if &#40;score >= beta&#41; &#123;
            undomove&#40;board, bindex, moves&#91;i&#93;, som&#41;;
            beta_cut++;
            bestmove = moves&#91;i&#93;;
            flag =  1;
            save_to_tt&#40;hash, bestmove, score, flag, max_depth-depth+PLY&#41;;
            return score;
        &#125;
        if &#40;score > alpha&#41; &#123;
            alpha_cut++;
            alpha = score;
            bestmove = moves&#91;i&#93;;
            flag = 0;
        &#125;
        undomove&#40;board, bindex, moves&#91;i&#93;, som&#41;;
    &#125;
    save_to_tt&#40;hash, bestmove, alpha, flag, max_depth-depth+PLY&#41;;
    return alpha;
&#125;

[smatovic]

thanks for your explanations,

I was confused by fail-low. There is no bestmove i could try first from the TT...now the engine plays better and faster.

--
srdja

[bob]

thanks for your explanations,

I was confused by fail-low. There is no bestmove i could try first from the TT...now the engine plays better and faster.

--
srdja

That's a key. Most everyone thinks they can find a way to produce a best move in a fail-low position. They can't. It is the way alpha/beta works. You don't want a bad move as a hash move, as that hurts everywhere...

[Desperado]

Well, if i now look at your last post and its code, i assume
you only retrieve the bestmove from TT instead of prun sth.
That is ok imo when this is a quiescence routine. (i assume it is).

But if so, where is your standpat condition ?
And what is the difference between

"alphabeta_qs_mvvlva_tt" and ?
"alphabeta_qsearch_mvvlva_tt" ?

[Desperado]

Hello Bob,

i remember a thread where this (bestmove stuff) was discussed with
the context of singular extensions.

Instead of storing a _bestMove_, if not such a move exists and the
moveSlot in TT is empty, someone can store the _firstMove_ generated
as "bestMove". So it is possible the next time you visit the node, you
can save movegeneration, and hope so to say, that the "bestMove/firstMove" from
the view of the movepicker will become a real _bestMove_.

didn t you keep this idea ? and if not why ?

regards

[Desperado]

Well, if i now look at your last post and its code, i assume
you only retrieve the bestmove from TT instead of prun sth.
That is ok imo when this is a quiescence routine. (i assume it is).

But if so, where is your standpat condition ?
And what is the difference between

"alphabeta_qs_mvvlva_tt" and ?
"alphabeta_qsearch_mvvlva_tt" ?

and i forget all the time...

not unimportant :
just evaluate (probably expensive) the position _after_ you have checked
the TT.