Newbie Question concerning Transposition Tables

[smatovic]

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" ?

You are right Michael, the posted code is not the Q-Search. I wanted to get TTs first running in the normal search. I figured out how to use the bestmove first. Now i can play around with prunning and updating the bounds.....your code snippet looks fine, thx.

Code: Select all

  //totally missing now is _exact_ score
  if(tt->flag == -1) {return(tt->score);} 

But what is when alpha was increased (Exact sore)?
Because the actual depth could be deeper (no iterative deepeing) i should compute further?

Code: Select all

    /*  1 => Lower bound, Fail high */
    /*  0 => Exsact Score, alpha was increased */
    /* -1 => Upper bound, Fail low */

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

    }

[bob]

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

Yes, I do that. For the simple reason that it is just a speed optimization. If you have no best move, then you may well try the first move you generated and searched the last time you searched this position. It could be a killer, a good capture, or just a move. But if you searched it first that time, you might get to search it first this time without generating any moves at all...

It is a small speed optimization, but it is essentially a free one...

[Desperado]

Ok, i see there is confusion with using hard coded numbers instead
of definitions/constants.

step 1: kick out the hardcoded numbers

Let s do the following way. update your code with this.

Code: Select all

#define FAIL_LO -1
#define EXACT    0 
#define FAIL_HI  1
#define NOFLAG  choose sth for empty slots

step 2: updating flag

Code: Select all

int search(...)
{ 
  int flag = FAIL_LO;
  
  while(moves)
  {
    value = -search()

    if(value >= beta) { flag = FAIL_HI; ...; return(value or beta);}
    if(value > alpha) { flag = EXACT ; ...}
  }

}

step 3: TT-Check

Code: Select all

tt = &TT[hash>>core_bit]; 
if (tt->hash == hash && tt->depth >= depth /*remaining depth*/) 
{  
 //exact score: value _was_ >alpha_LastTime && <beta_LastTime
 if(tt->flag == EXACT) return(tt->score);

 //fail_hi: value _was_ >= beta_LastTime , 
 //value is a minimum (could be everthing above beta_LastTime) 
 //if(tt->flag == FAIL_HI)
 {
  if(tt->score >= beta) return(tt->score);  //return(beta)
  alpha = MAX(alpha,tt->score);
 }

 //fail_lo: value _was_ <= alpha_LastTime ,
 //value is a maximum (could be everthing below alpha_LastTime)
 
 if (tt->flag == FAIL_LO) // 
  { 
   if(tt->score <= alpha) return(tt->score); //return(alpha)
   beta = MIN(beta, tt->score); 
  } 

 if(tt->bestmove) moves[movecounter++] = tt>bestmove;        
} 

step 4: finally

make sure you really never get other flag numbers when storing
and retrieving than you defined above.


Hopefully this makes it a little bit clearer.

Michael

[smatovic]

Code: Select all

if (tt->hash == hash && tt->depth >= depth /*remaining depth*/) 

Arg,
got an bug in "remaining depth", took also TT ab-values which did not belong to a deeper search.

"Dankeschoen" Michael.

--
srdja

[Mincho Georgiev]

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

Yes, I do that. For the simple reason that it is just a speed optimization. If you have no best move, then you may well try the first move you generated and searched the last time you searched this position. It could be a killer, a good capture, or just a move. But if you searched it first that time, you might get to search it first this time without generating any moves at all...

It is a small speed optimization, but it is essentially a free one...

This is actually something that I intend to try right now. I'll post some results. At first sight it looks good for the pv, which is absolutely reasonable. An idea that makes perfect sense to me, even if the difference in strenght is imperceptible. Still if it doesn't hurt,(which I dont see how could happen) it will help to optimize the search, and in my case it removes unusable (after being applied) check for an empty move (on fail-low). Again - it makes perfect sense and 'not-working' would indicate
a possible bug in my tt handling the least.

[bob]

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

Yes, I do that. For the simple reason that it is just a speed optimization. If you have no best move, then you may well try the first move you generated and searched the last time you searched this position. It could be a killer, a good capture, or just a move. But if you searched it first that time, you might get to search it first this time without generating any moves at all...

It is a small speed optimization, but it is essentially a free one...

This is actually something that I intend to try right now. I'll post some results. At first sight it looks good for the pv, which is absolutely reasonable. An idea that makes perfect sense to me, even if the difference in strenght is imperceptible. Still if it doesn't hurt,(which I dont see how could happen) it will help to optimize the search, and in my case it removes unusable (after being applied) check for an empty move (on fail-low). Again - it makes perfect sense and 'not-working' would indicate
a possible bug in my tt handling the least.

Note... the effect is _very_ small. Positive, but very small...

It will take tens of thousands of games to measure it accurately.