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 &#40;alpha < SCORE_INF&#41; &#123;
		if	&#40;alpha >  SCORE_WINNING&#41;	alpha += search_rootDistance&#40;treeinfo&#41;;
		else if &#40;alpha < -SCORE_WINNING&#41;	alpha -= search_rootDistance&#40;treeinfo&#41;;
	&#125;

	if &#40;beta > -SCORE_INF&#41; &#123;
		if	&#40;beta >  SCORE_WINNING&#41;		beta += search_rootDistance&#40;treeinfo&#41;;
		else if &#40;beta < -SCORE_WINNING&#41;		beta -= search_rootDistance&#40;treeinfo&#41;;
	&#125;

	if &#40;b.d.ply > 75&#41; &#123;	// ignore values if 50-move counter becomes to high
		alpha = SCORE_INF;
		beta  = -SCORE_INF;
	&#125;

	sttmain_entry * entry = &ttmain&#91;&#40;b.d.hash ^ b.d.stm&#41; & ttmain_mask&#93;;

	U8 depth = &#40;U8&#41; max&#40;0, treeinfo->depth&#41;;


	if &#40;entry.hash == &#40;b.d.hash >> 32&#41;) &#123;

		if &#40;depth >= entry.depth_move && move&#41; &#123;
			entry.move	 = move;
			entry.depth_move = depth;
		&#125;

		if &#40;depth >= entry.depth_alpha && alpha < SCORE_INF&#41; &#123;
			if &#40;depth > entry.depth_alpha || alpha < entry.alpha&#41; &#123;
				entry.alpha		= &#40;S16&#41; alpha;
				entry.depth_alpha	=	depth;
			&#125;
		&#125;

		if &#40;depth >= entry.depth_beta && beta > -SCORE_INF&#41; &#123;
			if &#40;depth > entry.depth_beta || beta > entry.beta&#41; &#123;
				entry.beta		= &#40;S16&#41; beta;
				entry.depth_beta	=	depth;
			&#125;
		&#125;


		return;
	&#125;

	entry.hash		= &#40;U32&#41; &#40;b.d.hash >> 32&#41;;

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

	entry.alpha		= &#40;S16&#41; alpha;
	entry.depth_alpha	=	depth;

	entry.beta		= &#40;S16&#41; beta;
	entry.depth_beta	=	depth;

	if (!move&#41;		 entry.depth_move  = 0;
	if &#40;alpha ==  SCORE_INF&#41; entry.depth_alpha = 0;
	if &#40;beta  == -SCORE_INF&#41; entry.depth_beta  = 0;

&#125;

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 &#40;treeinfo->depth <= entry.depth_alpha && entry.alpha != SCORE_INF&#41; &#123;
			entry_alpha = entry.alpha;
			if &#40;entry_alpha >  SCORE_WINNING&#41;	entry_alpha -= search_rootDistance&#40;treeinfo&#41;;
			if &#40;entry_alpha < -SCORE_WINNING&#41;	entry_alpha += search_rootDistance&#40;treeinfo&#41;;
		&#125;

		if &#40;treeinfo->depth <= entry.depth_beta  && entry.beta != -SCORE_INF&#41;	&#123;
			entry_beta = entry.beta;
			if &#40;entry_beta  >  SCORE_WINNING&#41;	entry_beta  -= search_rootDistance&#40;treeinfo&#41;;
			if &#40;entry_beta  < -SCORE_WINNING&#41;	entry_beta  += search_rootDistance&#40;treeinfo&#41;;
		&#125;

		if &#40;entry_alpha <= alpha&#41;	return entry_alpha;
		if &#40;entry_beta  >= beta&#41;	return entry_beta;
		if &#40;entry_alpha <= entry_beta&#41;	return entry_beta;

		return INVALID;
	&#125;

	return INVALID;
&#125;

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);