Author: Geoff
Date: 03:49:43 07/05/03
Hello
Questions on the topic of hash tables again.
I recently downloaded from the Italian group website an example of a TSCP clone
that had implemented Hash tables into the original TSCP. I thought this would be
really helpful as I was about to try the same thing.
Looking at their code for the quiescent search I am suspicious of whether it is
correct, I would appreciate the experts comments please.
Code snippet at end of message (bit long sorry)
My question is, Is it correct to do the Hash Insertion of all three conditions
at the bottom of the qsearch.
Surely, these quiescent depths haven't been searched fully so aren't the evals
and bestmoves unsound to save in the hash table ? (it says it saves a best move
only for a fail high or an exact score)
If it is ok to store in the hash table, can anyone explain why please ?
Even if it is sound as coded, the fact that it stores depth=0 doesn't that make
it almost useless for later hash probling anyways ?
Regards Geoff
PS Could you all agree with you comments please, as I am already confused by
this and cant make my mind up :-)
int quiesce(int alpha,int beta)
{
int i, j, x;
int orig_alpha = alpha;
long hashmove = 0, bestmove = 0;
pHash_Entry pHash;
++nodes;
/* do some housekeeping every 1024 nodes */
if ((nodes & 1023) == 0)
checkup();
pv_length[ply] = ply;
/**************************************************************/
/////////////////////////////////////////////////////
////// //////
////// CODE ADDED TO HANDLE HASH TABLE //////
////// =============================== //////
////// //////
/////////////////////////////////////////////////////
pHash = HashFind(hashcode);
if (pHash) { // The position was found in the hash table, and
switch (pHash->flags) { // there is no need to check the depth: any depth
// is ok since we are in qsearch
case EXACT_FLAG: // Real Score = Hash score:
// no need to search further. Just update
// the pv and return the retrieved score
pv[ply][ply].u = pHash->move;
for (j = ply + 1; j < pv_length[ply + 1]; ++j)
pv[ply][j] = pv[ply + 1][j];
pv_length[ply] = pv_length[ply + 1];
return pHash->score;
case LOBOUND_FLAG: // Real Score >= Hash score:
if (pHash->score>=beta) // If we know it's >= beta, there is
return pHash->score; // no need to search further
break;
case HIBOUND_FLAG: // Real Score <= Hash score:
if (pHash->score<=alpha) // If we know it's <= alpha, there is
return pHash->score; // no need to search further
break;
}
hashmove = pHash->move; // If we have a "best move" from hash table,
} // let's remember it so it will be searched
// first (provided that it is a capture move).
/**************************************************************/
/* are we too deep? */
if (ply >= HIST_STACK - 1)
return eval();
/* check with the evaluation function */
x = eval();
if (x > alpha)
alpha = x;
if (x >= beta) goto EndQSearch;
gen_caps();
if (follow_pv) /* are we following the PV? */
sort_pv();
/* loop through the moves */
for (i = gen_begin[ply]; i < gen_end[ply]; ++i) {
//
// When ordering the moves, we have to take into account the
// best move eventually retrieved from the hash table, which
// must be always searched first to maximize search efficiency.
// If we have no best move from hash table, then hashmove is 0.
//
sort(i, hashmove);
if (!makemove(gen_dat[i].m.b))
continue;
x = -quiesce(-beta, -alpha);
takeback();
if (x > alpha)
{
bestmove = gen_dat[i].m.u;
alpha = x;
if (x >= beta)
goto EndQSearch;
/* update the PV */
pv[ply][ply] = gen_dat[i].m;
for (j = ply + 1; j < pv_length[ply + 1]; ++j)
pv[ply][j] = pv[ply + 1][j];
pv_length[ply] = pv_length[ply + 1];
}
}
EndQSearch:
//
// Now store the search results in the hash table, with the correct
// flags. Note that bestmove is 0 (invalid move) in case of fail low,
// and that the depth is set to 0 since we are in qsearch (ie, no
// depth left)
//
if (alpha>=beta)
HashInsert(hashcode, alpha, bestmove, 0, LOBOUND_FLAG);
else if (alpha<=orig_alpha)
HashInsert(hashcode, alpha, bestmove, 0, HIBOUND_FLAG);
else
HashInsert(hashcode, alpha, bestmove, 0, EXACT_FLAG);
return alpha;
}
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.