Transposition Table - Replacement and PV

[hgm]

Always-replace is better than protecting deep entries with worthless bounds, poisoning your hash table. But the standard solution is to use the entries in pairs, and overwrite the least deep entry of the pair when you want to store a key that matches neither. Then you always keep the most recent entry (which was the most important thing), yet you protect deep entries from being overwritten, and reserved half the table for them.

[Cheney]

I think you have upper and lower bounds mixed up. If you have a score that is 'at least' beta wouldn't that be a lower bound?

You are probably right. In my real code, however, I use alphabound and betabound. I went that way because after reading various documents and reviewing various samples, I had the same question because I saw them go both ways.

Sorry if my on-the-fly code sample might be misleading at that point, it really was meant to support the proper placement of where the TT is actually indexed.

BTW, I did test out the proper placement of the TT entry and :

1. The search was faster
2. I can extract the PV from the TT

Thanks for the help

[diep]

I think you have upper and lower bounds mixed up. If you have a score that is 'at least' beta wouldn't that be a lower bound?

You are probably right. In my real code, however, I use alphabound and betabound. I went that way because after reading various documents and reviewing various samples, I had the same question because I saw them go both ways.

Sorry if my on-the-fly code sample might be misleading at that point, it really was meant to support the proper placement of where the TT is actually indexed.

BTW, I did test out the proper placement of the TT entry and :

1. The search was faster
2. I can extract the PV from the TT

Thanks for the help

That translates to:

alphabound = upperbound
betabound = lowerbound

But feel free to use alphabound and betabound as in general that's easier for most people. That's why not seldom i post about betabounds and alfabounds as well, as i see even experienced guys mess up the terminology.

[Lasse Hansen]

I use an always replace startegy, but split the hash table in 8 parts, as in
HashTable[wtm][depth]. This way deep entries are kept much longer than when
using a flat table. A drawback is that I have to probe up to 4 times for an
entry. A plus is that the hash table dont need to be a power of 2, only each
part does.
Fine 70 is solved in 0.01s (Kb1), and score +10.99 after 6.3s d41.

Code: Select all

#define TTE_Size (&#40;HTSize<<17&#41;/sizeof&#40;THTEntry&#41;)
void TTStore&#40;TTree *tr, U32 Move, int Value, int Type, U32 ply, U32 maxply&#41;
// Transposition table split in &#91;wtm&#93;&#91;depth&#93; = &#91;2&#93;&#91;4&#93;
&#123;
	THTEntry *HTAddress;
	U64 Offset;
	U32 Depth = maxply-ply;

	if &#40;Value >  MATESCORE&#41; Value += ply;
	if &#40;Value < -MATESCORE&#41; Value -= ply;
	
	U64 word1 = Move;
	word1 |= (&#40;U64&#41;Depth&63&#41;<<26;
	word1 |= (&#40;U64&#41;Type&7&#41;<<32;
	word1 |= (&#40;U64&#41;&#40;Value+32768&#41;)<<35;

	switch &#40;Depth&#41; &#123;
	case  0 &#58; Offset = 0*TTE_Size; break;
	case  1 &#58; Offset = 0*TTE_Size; break;
	case  2 &#58; Offset = 1*TTE_Size; break;
	case  3 &#58; Offset = 1*TTE_Size; break;
	case  4 &#58; Offset = 2*TTE_Size; break;
	case  5 &#58; Offset = 2*TTE_Size; break;
	default &#58; Offset = 3*TTE_Size; break;
	&#125;
	Offset += 4*TTE_Size * tr->wtm;

	HTAddress = HT + Offset + &#40;tr->HashKey & &#40;TTE_Size-1&#41;);
	
	U64 word2 = tr->HashKey;
	word2 ^= word1; 

	HTAddress->Data = word1;
	HTAddress->HKey = word2;
&#125;

int TTProbe&#40;TTree *tr, U32 *Move, int *Value, U32 ply, U32 maxply, int alpha, int beta&#41;
&#123;
	U64 Type,Depth;
	THTEntry *HTAddress;
	U64 Offset;
	int n;
	
    for &#40;n=3; n>=0; n--) &#123;// Look in all parts of TT
		Offset = n*TTE_Size;
		Offset += 4*TTE_Size * tr->wtm;

		HTAddress = HT + Offset + &#40;tr->HashKey & &#40;TTE_Size-1&#41;);
		U64 word1 = HTAddress->Data;
		U64 word2 = HTAddress->HKey;
		word2 ^= word1;
		if &#40;tr->HashKey != word2&#41; continue;
		
		Type=&#40;word1>>32&#41;&7;
		*Move=word1&(&#40;1<<26&#41;-1&#41;;
		*Value=(&#40;word1>>35&#41;&65535&#41;-32768;
		Depth=&#40;word1>>26&#41;&63;

		if &#40;Depth < maxply-ply&#41; return TT_NOTHING;
		if (&#40;Type == TT_EXACT&#41;&&((*Value < alpha&#41;||(*Value >= beta&#41;)) 
			return TT_NOTHING;
		if (*Value >  MATESCORE&#41; *Value -= ply;
		if (*Value < -MATESCORE&#41; *Value += ply;

		tr->HTHits++; 
		tr->Nt++;

		switch &#40;Type&#41; &#123;
			case TT_EXACT &#58; return TT_EXACT;			
			case TT_LOWER &#58; if (*Value>=beta&#41;  return TT_LOWER; break;
			case TT_UPPER &#58; if (*Value<=alpha&#41; return TT_UPPER; break;
			default &#58; Print&#40;3, "Error&#58;TTProbe&#58;wrong type\n");
		&#125;
	&#125;
	return TT_NOTHING;		
&#125;

Cheers, Lasse

[diep]

What works the best for me is:

Always overwrite entrys of an older table genereration.

And if the table generation is the same then:

Lowerbound and exact will always overwrite an existing entry if the depth >= existing depth or the existing entry is an upperbound.

Upperbounds will only overwrite upperbounds with lesser or equal depth.

So upperbounds wil never overwrite lowerbound or exact entrys from the same table generation.

I don't think this works very well. One needs to ALWAYS store an entry, period. The only question is, what gets overwritten, not IF something gets overwritten. Otherwise you can "outsearch" the TT and reach a point where it doesn't help at all because you refuse to overwrite, and the stuff you are trying to store is important for future efficiency.

I make multiple tests but in every case that HashStore() is called, I store that entry, period...

Bob, the way how i read Joost's posting is that this isn't a brainwave type HGM, yet that this is something that actually works for him.

Also it basically says that in some huge amount of cases, which will be some percentage close to 99% i'd guess, he's overwriting.

So you're disagreeing here now about that 1%?

[tpetzke]

Hi Lucas,

with 5 seconds you are lucky indeed with that strategy. With always replace you would of course be much faster.

Mine old laptop tells me

info depth 26 seldepth 28 time 16 nodes 26094 pv a1b1 a7b7 b1c1 b7c8 c1d2 c8d7 d2c3 d7c7 nps 1630874 score cp 183 hashfull 0 tbhits 0
bestmove a1b1 ponder a7b7
info time 329 nodes 106666 nps 324212

I use a bucket system with 4 buckets. If I want to store a position and already find it in one of the buckets it is replaced (always).

If not I look for a bucket with an old entry (not from current or previous search). If I found one it goes in there.

Otherwise I store it in the bucket that seems to contain the least useful data (depending on age, depth and node type).

To keep an even distribution over the buckets I XOR 2 upper bits from the hash key when I loop over the buckets. This ensures also that a position has a good chance to be found in the first bucket I look into.

Seems to work Ok for me.

Thomas...

[Don]

I also use set associated hashing. I have rules which determine which of the 4 entries to replace but one way or the other one of them always gets replaced.

I use a scoring system because the rules are fairly complicated. If I find an empty or matching entry it is always used, otherwise I consider the "age" of the entry, the depth and the bounds.

I experiment with this periodically but I have yet to improve on the basic scheme.

Hi Lucas,

with 5 seconds you are lucky indeed with that strategy. With always replace you would of course be much faster.

Mine old laptop tells me

info depth 26 seldepth 28 time 16 nodes 26094 pv a1b1 a7b7 b1c1 b7c8 c1d2 c8d7 d2c3 d7c7 nps 1630874 score cp 183 hashfull 0 tbhits 0
bestmove a1b1 ponder a7b7
info time 329 nodes 106666 nps 324212

I use a bucket system with 4 buckets. If I want to store a position and already find it in one of the buckets it is replaced (always).

If not I look for a bucket with an old entry (not from current or previous search). If I found one it goes in there.

Otherwise I store it in the bucket that seems to contain the least useful data (depending on age, depth and node type).

To keep an even distribution over the buckets I XOR 2 upper bits from the hash key when I loop over the buckets. This ensures also that a position has a good chance to be found in the first bucket I look into.

Seems to work Ok for me.

Thomas...

[lucasart]

I also use set associated hashing. I have rules which determine which of the 4 entries to replace but one way or the other one of them always gets replaced.

I use a scoring system because the rules are fairly complicated. If I find an empty or matching entry it is always used, otherwise I consider the "age" of the entry, the depth and the bounds.

I experiment with this periodically but I have yet to improve on the basic scheme.

OK, so pretty much like Stockfish then. I'm going to experiment with that. But first of all, I need to implement an eval cache, so I can remove the eval from the TT entries, and keep the TT entries compact and efficient.

[Don]

I also use set associated hashing. I have rules which determine which of the 4 entries to replace but one way or the other one of them always gets replaced.

I use a scoring system because the rules are fairly complicated. If I find an empty or matching entry it is always used, otherwise I consider the "age" of the entry, the depth and the bounds.

I experiment with this periodically but I have yet to improve on the basic scheme.

OK, so pretty much like Stockfish then. I'm going to experiment with that. But first of all, I need to implement an eval cache, so I can remove the eval from the TT entries, and keep the TT entries compact and efficient.

In fact I got the idea for using set associate hashing from looking at the code of Stockfish. It was a sensible scheme and their overwrite rules are identical anyway to what I had doing for decades before - except now you have a choice of 4 entries to choose from.

I do not know if this is an original idea from SF or not. There are numerous hash table schemes I have seen but I think this is about as good as it gets for something simple.

[bob]

What works the best for me is:

Always overwrite entrys of an older table genereration.

And if the table generation is the same then:

Lowerbound and exact will always overwrite an existing entry if the depth >= existing depth or the existing entry is an upperbound.

Upperbounds will only overwrite upperbounds with lesser or equal depth.

So upperbounds wil never overwrite lowerbound or exact entrys from the same table generation.

I don't think this works very well. One needs to ALWAYS store an entry, period. The only question is, what gets overwritten, not IF something gets overwritten. Otherwise you can "outsearch" the TT and reach a point where it doesn't help at all because you refuse to overwrite, and the stuff you are trying to store is important for future efficiency.

I make multiple tests but in every case that HashStore() is called, I store that entry, period...

Bob, the way how i read Joost's posting is that this isn't a brainwave type HGM, yet that this is something that actually works for him.

Also it basically says that in some huge amount of cases, which will be some percentage close to 99% i'd guess, he's overwriting.

So you're disagreeing here now about that 1%?

I don't know that it is just 1%. If I complete a search and fail low, storing that is certainly useful information, and storing fail low positions happens at every other ply along a path.

I think you have to always store the current position, and simply try to choose intelligently what you are going to replace.