Extended Transposition Table

[Edmund]

For a long time now we have been using a simple always replace scheme for new TT entries, with the variables: hash, value, flag (all-, cut- or exact-score), bestmove, depth

I now tried to change this to a more complex version, storing for each entry a lower bound, depth for this bound, an upper bound, depth for this bound, bestmove, depth for the bestmove and hash.

This way I hoped to avoid cases where an old entry is overwritten, just because other bounds are passed. Anyway in tests the new version was significantly weaker (about 25%). Am I missing anything obvious?

Saving a TT_entry:

Code: Select all

void ttmain_save(streeinfo * treeinfo, int alpha, int beta, U16 move) {

	if (!ttmain_size || !task) return;

	if (alpha < SCORE_INF) {
		if	(alpha >  SCORE_WINNING)	alpha += search_rootDistance(treeinfo);
		else if (alpha < -SCORE_WINNING)	alpha -= search_rootDistance(treeinfo);
	}

	if (beta > -SCORE_INF) {
		if	(beta >  SCORE_WINNING)		beta += search_rootDistance(treeinfo);
		else if (beta < -SCORE_WINNING)		beta -= search_rootDistance(treeinfo);
	}

	if (b.d.ply > 75) {	// ignore values if 50-move counter becomes to high
		alpha = SCORE_INF;
		beta  = -SCORE_INF;
	}

	sttmain_entry * entry = &ttmain[(b.d.hash ^ b.d.stm) & ttmain_mask];

	U8 depth = (U8) max(0, treeinfo->depth);


	if (entry.hash == (b.d.hash >> 32)) {

		if (depth >= entry.depth_move && move) {
			entry.move	 = move;
			entry.depth_move = depth;
		}

		if (depth >= entry.depth_alpha && alpha < SCORE_INF) {
			if (depth > entry.depth_alpha || alpha < entry.alpha) {
				entry.alpha		= (S16) alpha;
				entry.depth_alpha	=	depth;
			}
		}

		if (depth >= entry.depth_beta && beta > -SCORE_INF) {
			if (depth > entry.depth_beta || beta > entry.beta) {
				entry.beta		= (S16) beta;
				entry.depth_beta	=	depth;
			}
		}


		return;
	}

	entry.hash		= (U32) (b.d.hash >> 32);

	entry.move		=	move;
	entry.depth_move	= 	depth;

	entry.alpha		= (S16) alpha;
	entry.depth_alpha	=	depth;

	entry.beta		= (S16) beta;
	entry.depth_beta	=	depth;

	if (!move)		 entry.depth_move  = 0;
	if (alpha ==  SCORE_INF) entry.depth_alpha = 0;
	if (beta  == -SCORE_INF) entry.depth_beta  = 0;

}

Probing the TT:

Code: Select all

int ttmain_probe(streeinfo * treeinfo, int alpha, int beta, U16 * move) {

	if (!ttmain_size) return INVALID;

	sttmain_entry * entry = &ttmain[(b.d.hash ^ b.d.stm) & ttmain_mask];

	if (entry.hash == (b.d.hash >> 32)) {

		*move = entry.move;

		if (b.d.ply >= 75) return INVALID;

		int entry_alpha =  SCORE_INF + 1;
		int entry_beta	= -SCORE_INF - 1;

		if (treeinfo->depth <= entry.depth_alpha && entry.alpha != SCORE_INF) {
			entry_alpha = entry.alpha;
			if (entry_alpha >  SCORE_WINNING)	entry_alpha -= search_rootDistance(treeinfo);
			if (entry_alpha < -SCORE_WINNING)	entry_alpha += search_rootDistance(treeinfo);
		}

		if (treeinfo->depth <= entry.depth_beta  && entry.beta != -SCORE_INF)	{
			entry_beta = entry.beta;
			if (entry_beta  >  SCORE_WINNING)	entry_beta  -= search_rootDistance(treeinfo);
			if (entry_beta  < -SCORE_WINNING)	entry_beta  += search_rootDistance(treeinfo);
		}

		if (entry_alpha <= alpha)	return entry_alpha;
		if (entry_beta  >= beta)	return entry_beta;
		if (entry_alpha <= entry_beta)	return entry_beta;

		return INVALID;
	}

	return INVALID;
}

Saving in case of a beta-cut/exact score:

Code: Select all

ttmain_save(&treeinfo, SCORE_INF, val, cur_move);

Saving in case of a fail-low:

Code: Select all

ttmain_save(&treeinfo, best_score, -SCORE_INF, *refutation);