Problems with TT, sometimes makes blunder moves

[tttony]

It is best to test the TT on a simple position with very many transpositions. Like the KPK ending or Fine #70. If it doesn't work perfectly, it would almost certainly show up there. E.g. can you find the promotion in

[d]4k3/8/8/8/8/8/4P3/4K3 w

If not, let it print the relevant part of the tree and look where it goes wrong. I always put infra-structure in my engines to print debug info along a selected path, labeled with ply, depth (and possibly IID iteration depth), so that you know which node is printing. Most useful is to print move, score, bestScore immediately after UnMake, and the hash key at the point where you take a hash cutoff. Then you can see which move has the wrong score, add that to the print path, and zoom in on the error. This never fails, although it sometimes is tedious.

BTW, why 32 bits for flags? What flags can you possibly have? I never used more than 3: upper bound, lower bound and in check.

Sounds that I have to work hard with this bug

flag will be uint8, it will just store the bound

@Tony:

The problem is in at least two places in the hash table code.

1) tt_init():

Code: Select all

uint32_t t = 2;
for (; t <= size; t *= 2&#41;
    ;
// Cast to uint64_t because gives = 0
uint64_t ttsize = ((&#40;uint64_t&#41;t / 2&#41; << 20&#41;;

This calculation is wrong. Simply remove the "<< 20" part.

2) index calculation by using bitwise AND (at 3 places):

Code: Select all

uint64_t index = key & hash->size;

After correcting issue 1) above this will work "somehow" but it drops the lowest two bits from the index due to the statement

Code: Select all

hash->size = ttsize - 4;

in tt_init() which seems to increase the probability of hash collisions if I understood it right. Why is that necessary? Why not "hash->size = ttsize - 1" ?

EDIT: 3) Please check the value of MAX_MATE_EVAL. It is used for transforming mate scores from/to TT but then its value should be the biggest possible value that can be returned by the evaluation function (the name MAX_MATE_EVAL could be understood different, though). This would not cause the big problems you were describing but could be another small source of trouble.

The TT it's calculate with MB, so if size = 32, will be 32MB TT, basically I stole the code from Sungorus, I think it's -4 because it uses 4 slots to save the move into the TT, I don't use slots(for now) so I will let -1

I have discovered bugs and I re-activated an old bug that gives the wrong pv move, in the UCI pv string shows the right move but moves a blunder one

In the search:

Code: Select all

			if (score > alpha) {
				if (score >= beta) {
#ifdef USE_HASHTABLE
					tt_save(board->key, board->ply, hash, beta, move, depth, HASH_BETA, 0);
#endif
					return beta;
				}
				alpha = score;
				bestMove = move;
				//UpdatePv&#40;pv, new_pv, move&#41;; // <<-- Here is the problem
			&#125;

Now I save the Best Root Move like this, after the move loop

Code: Select all

if (!board->ply)
   pv[0] = bestMove;

The other bug is with the MATE value, I have it wrong

Kinda hard to choose the correct value for mate, I was tesing these new values:

Code: Select all

#define INF					(32767)
#define MATE_EVAL			(32000)
#define MIN_MATE_EVAL		(MATE_EVAL + MAX_DEPTH)
#define MAX_MATE_EVAL		(MIN_MATE_EVAL - MAX_DEPTH)
#define MAX_EVAL			(29999)

But triggers an ASSERT when saving in the hash:

Code: Select all

if (score >= +MAX_MATE_EVAL) {
		score += ply;
		ASSERT&#40;Abs&#40;score&#41; <= MIN_MATE_EVAL && Abs&#40;score&#41; >= MAX_MATE_EVAL&#41;;
	&#125; else if &#40;score <= -MAX_MATE_EVAL&#41; &#123;
		score -= ply;
		ASSERT&#40;Abs&#40;score&#41; <= MIN_MATE_EVAL && Abs&#40;score&#41; >= MAX_MATE_EVAL&#41;;
	&#125;

The max value is 32064 but with the HGM position in some point reach 32065, pff lot of work to do

Thanks everyone and Sven for spotting the mate value bug, new headache

[Sven]

@Tony:

The problem is in at least two places in the hash table code.
[...]
2) index calculation by using bitwise AND (at 3 places):

Code: Select all

uint64_t index = key & hash->size;

[...] this will work "somehow" but it drops the lowest two bits from the index due to the statement

Code: Select all

hash->size = ttsize - 4;

in tt_init() which seems to increase the probability of hash collisions if I understood it right. Why is that necessary? Why not "hash->size = ttsize - 1" ?

EDIT: 3) Please check the value of MAX_MATE_EVAL. It is used for transforming mate scores from/to TT but then its value should be the biggest possible value that can be returned by the evaluation function (the name MAX_MATE_EVAL could be understood different, though). This would not cause the big problems you were describing but could be another small source of trouble.

The TT it's calculate with MB, so if size = 32, will be 32MB TT, basically I stole the code from Sungorus, I think it's -4 because it uses 4 slots to save the move into the TT, I don't use slots(for now) so I will let -1

For me the topic of slots is fully unrelated to the problem I mentioned. You are using the expression hash->size for masking the TT key in order to obtain the TT index from the key. For that purpose you certainly want to use *all* lower bits of the key, not just all except bits 0 and 1. But that is what subtracting 4 from a number which is a power of 2 does: it results in a bit mask like 11111...1111100. With that bitmask you would use only a quarter of the whole hash table, i.e. all TT entries at an index that has at least one of the lowest two bits non-zero would never be used.

Apart from that, I would not understand why using 4 slots per TT index should lead to *subtracting* 4 from the size, for me it would be *dividing* by 4.

The other bug is with the MATE value, I have it wrong

Kinda hard to choose the correct value for mate, I was tesing these new values:

Code: Select all

#define INF					(32767)
#define MATE_EVAL			(32000)
#define MIN_MATE_EVAL		(MATE_EVAL + MAX_DEPTH)
#define MAX_MATE_EVAL		(MIN_MATE_EVAL - MAX_DEPTH)
#define MAX_EVAL			(29999)

But triggers an ASSERT when saving in the hash:

Code: Select all

if (score >= +MAX_MATE_EVAL) {
		score += ply;
		ASSERT&#40;Abs&#40;score&#41; <= MIN_MATE_EVAL && Abs&#40;score&#41; >= MAX_MATE_EVAL&#41;;
	&#125; else if &#40;score <= -MAX_MATE_EVAL&#41; &#123;
		score -= ply;
		ASSERT&#40;Abs&#40;score&#41; <= MIN_MATE_EVAL && Abs&#40;score&#41; >= MAX_MATE_EVAL&#41;;
	&#125;

The max value is 32064 but with the HGM position in some point reach 32065, pff lot of work to do

I don't understand why your MIN_MATE_EVAL is greater than MAX_MATE_EVAL, that is confusing. Also MAX_MATE_EVAL is the same as MATE_EVAL. What I do is that I subtract the number of plies from something like MATE_EVAL so that a mate in one ply is +31999 and being mated in 6 plies is -31994, etc. So my MIN_MATE_EVAL is (MATE_EVAL - MAX_DEPTH). You are using MIN and MAX with different semantics compared to what most people are used to ...

Is it right that you add the plies until mate to MATE_EVAL? If so, how do you back up scores during search, then (since a shorter mate now no longer has a higher score than a longer mate from the winning side's viewpoint)?

My point was also slightly different, not about the MATE value but that you used the MAX_MATE_EVAL constant in the code for transforming a mate score from and to a TT score. (My problem with that may be related to the unusual MAX_ in that name, of course.) There you need to determine whether a score is in the range of mate scores or not. With the new code above you seem to detect it correctly but it seems the transformation itself may be wrong. If my assumption is right that (MATE_EVAL + ply) is your representation of a mate in "ply" plies then you need to *subtract* the ply when storing a positive mate score in TT, etc.

[kbhearn]

For me the topic of slots is fully unrelated to the problem I mentioned. You are using the expression hash->size for masking the TT key in order to obtain the TT index from the key. For that purpose you certainly want to use *all* lower bits of the key, not just all except bits 0 and 1. But that is what subtracting 4 from a number which is a power of 2 does: it results in a bit mask like 11111...1111100. With that bitmask you would use only a quarter of the whole hash table, i.e. all TT entries at an index that has at least one of the lowest two bits non-zero would never be used.

Apart from that, I would not understand why using 4 slots per TT index should lead to *subtracting* 4 from the size, for me it would be *dividing* by 4.

That could make sense for the mask - the idea is that entry xxxxx..xxxxx00 - xxxxx..xxxxx11 are 1 cluster of 4 entries instead of making a seperate cluster object and creating an array of clusters.

[Sven]

For me the topic of slots is fully unrelated to the problem I mentioned. You are using the expression hash->size for masking the TT key in order to obtain the TT index from the key. For that purpose you certainly want to use *all* lower bits of the key, not just all except bits 0 and 1. But that is what subtracting 4 from a number which is a power of 2 does: it results in a bit mask like 11111...1111100. With that bitmask you would use only a quarter of the whole hash table, i.e. all TT entries at an index that has at least one of the lowest two bits non-zero would never be used.

Apart from that, I would not understand why using 4 slots per TT index should lead to *subtracting* 4 from the size, for me it would be *dividing* by 4.

That could make sense for the mask - the idea is that entry xxxxx..xxxxx00 - xxxxx..xxxxx11 are 1 cluster of 4 entries instead of making a seperate cluster object and creating an array of clusters.

Thanks for the hint, seems plausible. But that makes it harder to understand the code (e.g. to see easily whether an index is the index of a cluster or of a single entry), and it does not allow to simply change the program such that a cluster contains a number of entries that is not a power of two (e.g. SF8 = 3 entries with 10 bytes each plus 2 padding bytes = 32 bytes per cluster). But of course it is a possible and correct implementation which I did not recognize on my first attempt.

[hgm]

But why would you want to change it? Best is usual to design things as they must be, and then leave them alone forever. Designing code with the purpose to change it seems a very roundabout way of doing things. If you decide you want buckets of 4, e.g. because an entry is 16 bytes and you want to store them in sync withe a cache line of 64 byte, this seems as simple as it can get, codewise.

Code: Select all

// hash probe
int slot=0;
HashEntry *entry = hashTable + (key & hashMask);
if(entry[slot].lock == key || entry[slot^=1].lock == key ||
   entry[slot^=2].lock == key || entry[slot^=1].lock == key) { // hit
  entry += slot;
  ...
} else { // miss
  slot = -1;
}

...

// hash store
if&#40;slot < 0&#41; &#123; // invoke replacement scheme
  entry = ...
&#125;
entry->lock = key;
...

You don't have to bother with any intermediate level of organization of the hash table.

[Sven]

But why would you want to change it? Best is usual to design things as they must be, and then leave them alone forever. Designing code with the purpose to change it seems a very roundabout way of doing things.

You are programming. I am developing software. You write code to make it work. I write code to make it work but also to be able to read it, see why it works or does not work, and be able to change it whenever I want. That is the simple difference. I have seen enough code that works even though nobody understands why. I guess you don't understand that, so we'd better not discuss it ...

[hgm]

You mean you are unable to see why the code I shown above would work?

That indeed seems like a problem...

[tttony]

Sungorus does not use slots as array

Code: Select all

void AllocTrans(int mbsize)
{
  for &#40;tt_size = 2; tt_size <= mbsize; tt_size *= 2&#41;
    ;
  tt_size = (&#40;tt_size / 2&#41; << 20&#41; / sizeof&#40;ENTRY&#41;;
  tt_mask = tt_size - 4;
  free&#40;tt&#41;;
  tt = &#40;ENTRY *) malloc&#40;tt_size * sizeof&#40;ENTRY&#41;);
  ClearTrans&#40;);
&#125;

Code: Select all

int TransRetrieve(U64 key, int *move, int *score, int alpha, int beta, int depth, int ply)
{
  int i;
  entry = tt + (key & tt_mask);
  for &#40;i = 0; i < 4; i++) &#123;
    if &#40;entry->key == key&#41; &#123;
      entry->date = tt_date;
      *move = entry->move;
      if &#40;entry->depth >= depth&#41; &#123;
        *score = entry->score;
        if (*score < -MAX_EVAL&#41;
          *score += ply;
        else if (*score > MAX_EVAL&#41;
          *score -= ply;
        if (&#40;entry->flags & UPPER && *score <= alpha&#41; ||
            &#40;entry->flags & LOWER && *score >= beta&#41;)
          return 1;
      &#125;
      break;
    &#125;
    entry++;
  &#125;
  return 0;
&#125;

You right, the var names are a mess, the MIN_MATE_VALUE it's the mated value mate in 0, MAX_MATE_EVAL is the max mate in, it is 64, for example:

Code: Select all

-32064 + 4  = -32060
-32064 + 64 = -32000

The value it's between 32000 and 32064, I don't want to exceed that value, just for making sure that it's a mate value

The ASSERT now it's only in tt_probe() in tt_save() the score can be higher, later will be adjusted

Now back to the TT bug it's getting worse in this position the engine gives +M4

[d] 8/3kP3/8/3K4/8/8/8/8 w - - 0 11

Code: Select all

FEN: 8/3kP3/8/3K4/8/8/8/8 w - - 0 11 

Skiull 0.2 x64 popcnt:
   1	00:00	          20	20	+0,60	e7-e8Q+
   2	00:00	          40	40	+5,60	e7-e8R
   3	00:00	         137	137	+0,60	e7-e8R
   4	00:00	         240	240	+0,60	e7-e8R
   5	00:00	         756	756	+1,84	Kd5-e5
   6	00:00	       1.441	1.441	+0,50	e7-e8Q+
   7	00:00	      10.893	10.893	+5,70	Kd5-e5
   8	00:00	      39.158	39.158	+10,05	Kd5-c5
   9	00:00	     535.220	11.387.660	+M4	e7-e8Q+
  10	00:00	   1.420.680	10.075.745	+M4	e7-e8Q+
  11	00:01	  12.123.198	11.601.146	+M5	e7-e8Q+
  12	00:03	  33.239.698	10.393.902	+M4	e7-e8Q+
  13	00:25	 296.230.237	11.728.639	+M4	e7-e8Q+

Skiull 0.1 x64 popcnt:
   1	00:00	          20	20	+0,40	e7-e8Q+
   2	00:00	          40	40	+0,40	e7-e8Q+
   3	00:00	         129	129	+0,40	e7-e8Q+
   4	00:00	         300	300	+0,30	e7-e8Q+
   5	00:00	         943	943	+0,40	e7-e8Q+
   6	00:00	       2.251	2.251	+0,30	e7-e8Q+
   7	00:00	       7.047	7.047	+0,40	e7-e8Q+
   8	00:00	      16.080	16.080	+0,30	e7-e8Q+
   9	00:00	      52.722	52.722	+0,40	e7-e8Q+
  10	00:00	     124.174	124.174	+0,30	e7-e8Q+
  11	00:00	     409.254	13.201.742	+0,40	e7-e8Q+
  12	00:00	     953.893	15.141.159	+0,30	e7-e8Q+
  13	00:00	   3.375.590	13.502.360	+0,40	e7-e8Q+
  14	00:00	   8.165.116	13.085.122	+0,30	e7-e8Q+
  15	00:02	  33.329.862	13.870.105	+0,40	e7-e8Q+
  16	00:05	  79.527.796	13.379.507	+0,30	e7-e8Q+
  17	00:23	 322.281.880	13.883.681	+0,40	e7-e8Q+
  18	00:57	 765.954.197	13.429.782	+0,30	e7-e8Q+

The 0.1 version with no TT has no problem

[hgm]

Well, first it would help if you would print a complete PV, rather than just the first move. Then you can see in which position it makes the wrong move that allows pomotion. Or is that because the PV is cut by a TT hit?

If so, you should print the key of the hit at the end of the PV. Then you can test in the program where you store with that key, and print the position there. It seems the engine is mixing up positions. Are you sure your hash keys are OK (and not zero for a large part)?

[Sven]

You mean you are unable to see why the code I shown above would work?

That indeed seems like a problem...

I am certainly able to understand C code, even if it looks like that:

Code: Select all

int slot=0;
HashEntry *entry = hashTable + (key & hashMask);
if(entry[slot].lock == key || entry[slot^=1].lock == key ||
   entry[slot^=2].lock == key || entry[slot^=1].lock == key) { // hit
  entry += slot;
  ...
} else { // miss
  slot = -1;
}

I simply don't like it that way. A simple loop does the same since the compiler will unroll it due to the number of slots being a compile time constant. Updating the slot variable with some XORs may be a nice hacker trick but why invest energy if an obvious solution is available?

Code: Select all

inline HashEntry * ttProbe(uint64_t key) {
    HashEntry * entry = hashTable + (key & hashMask);
    for &#40;int slot = 0; slot < 4; slot++) &#123;
        if &#40;entry&#91;slot&#93;.lock == key&#41; &#123;
            return &&#40;entry&#91;slot&#93;);
        &#125;
    &#125;
    return 0;
&#125;