I have several chess transposition table related questions.

I list two implementations of TTables - the first is my current code (based on an incomplete understanding), the second is based on a frequently cited paper ["Parallel Search of Strongly Ordered Game Trees" by T. A. MARSLAND AND M. CAMPBELL, Department of Computing Science, University of Alberta.] Only the relevant portions of code that touch the ttable within the negamax routine are given for simplicity.

First question, is the Marsland listing incorrect in how entries are stored at the end of the listing? Shouldn't the upper and lower flags be swapped?

Second question, why does the first listing handily beat the second listing in head to head competition? All other optimizations are turned off - this is just negamax with alphabeta pruning and transposition table. The remainder of the code is basically identical. The only differences are:

1st listing ttable stores 64 bit integer with bits packed, 2nd listing ttable stores ptr to structure (in preparation for saving best move which first listing does not do.)

1st listing compares only 58 bits of hash (due to cramming everything into 64 bits), 2nd listing compares all 64 bits.

The first code seems somewhat random to me and in places contradicts the second implementation. The second listing makes much more sense.

Third question, what is optimal action to take upon finding a non-exact entry in the table? I have found examples that do variations on A, B and C. Marsland does C. My current code does B.


if(pe!= null && pe->depth >= depth){
if (pe->flag == TTABLE_LOWER) {
// A
if (pe->m_eval >= beta) {
return(beta);
}
// B
if (pe->m_eval <= alpha) {
return(alpha);
}
// C
if (pe->m_eval > alpha) {
alpha = pe->m_eval;
}
}


Fourth question, is there any reason to do ttable store at depth 0 when evaluation is incremental (i.e. code is not calling eval routine to calculate the evaluation, instead the evaluation is simply returned when depth=0).


// My current implementation
hashhval entry;
if (m_pTTable->FindTTableState(m_currHashVal, entry)) {
if (entry.depth >= depth) {
switch (entry.flag) {
case TTABLE_EXACT:
return(entry.value);
case TTABLE_LOWER:
if (entry.value <= alpha) {
return(alpha);
}
break;
case TTABLE_UPPER:
if (entry.value >= beta) {
return(beta);
}
break;
case TTABLE_INVALID:
break;
}
}
}

if (depth <= 0) {
m_pTTable->SaveTTableState(m_currHashVal, iBoard, depth, m_eval, TTABLE_EXACT);
return(m_eval);
}

doMove();
negaMax();
undoMove();

if (v > bestV) {
bestV = v;
}
int ttableType = TTABLE_LOWER;
if (bestV > alpha0) {
ttableType = TTABLE_EXACT;
alpha = bestV;
}
if (bestV >= beta) {
m_pTTable->SaveTTableState(m_currHashVal, iBoard, depth, bestV, TTABLE_UPPER);
return(bestV);
}


m_pTTable->SaveTTableState(m_currHashVal, depth, alpha, ttableType);


// Marsland pseudocode (directly from paper)
CTTEntry* pe;
if ((pe = m_pTTable->FindTTableState(m_currHashVal)) != NULL) {
if (pe->m_depth >= depth) {
switch (pe->m_flag) {
case TTABLE_EXACT:
return(pe->m_eval);
case TTABLE_LOWER:
if (pe->m_eval > alpha) {
alpha = pe->m_eval;
}
break;
case TTABLE_UPPER:
if (pe->m_eval < beta) {
beta = pe->m_eval;
}
break;
case TTABLE_INVALID:
break;
}
if (alpha >= beta) {
return(pe->m_eval);
}
}
}

if (depth <= 0) {
return(m_eval);
}

doMove();
negaMax();
undoMove();

if ((pe == NULL) || (pe->m_depth <= depth)) {
if (bestV <= alpha0) {
m_pTTable->SaveTTableState(m_currHashVal, depth, bestV, TTABLE_UPPER);
}
else if (bestV >= beta) {
m_pTTable->SaveTTableState(m_currHashVal, depth, bestV, TTABLE_LOWER);
}
else {
m_pTTable->SaveTTableState(m_currHashVal, depth, bestV, TTABLE_EXACT);
}
}