compact score value representation

[Sven]

Indeed, I don't use such tricks where structs/unions will do. The only place for it in chess engines is for representing a MOVE where bitfields may be slower.

Code: Select all

typedef struct tagHASH {
	HASHKEY hash_key;
	union {
		HASHKEY data_key;
		struct {
			UBMP32  move;
			BMP16   score;
			UBMP8   depth;
			UBMP8   flags;
		};
	};
}HASH,*PHASH;

Why do you name it "data_key"? Isn't it simply a (structured) 64 bit value, and wouldn't it be better to call it "data" or "value" instead of "data_key"? I'd assume you won't lookup anything in your hash table using that "data_key".

In order to access the whole 64 bit structure at once (if you really see the need for it) you might as well omit the union and use a name for the struct, as in:

Code: Select all

typedef struct tagHASH {
	HASHKEY hash_key;
	struct {
		UBMP32  move;
		BMP16   score;
		UBMP8   depth;
		UBMP8   flags;
	} data;
}HASH,*PHASH;

It would require to write "xx.data.score" instead of "xx.score" but I think this would be acceptable.

I think that does basically the same as your solution but with even less "trickery", would you agree?

Sven

[hgm]

I don't think you can apply operators like XOR to a struct. Which is what you would have to do for Bob's lockless hashing.

[Daniel Shawul]

I thought it would be obvious why I needed it. Just last week I needed to use a lock-less hash table method where you do (hash_key ^ data_key). So previously my TT entry was as shown as below with no unions/structs, since there was no need for them. Switching to anonymous union gets the job done without breaking a sweat. One can just declare a 64 bit data_key and does all the bit shifting but most compilers will produce the same code with the union as well.

Code: Select all

typedef struct tagHASH {
	HASHKEY hash_key;
	UBMP32  move;
	BMP16   score;
	UBMP8   depth;
	UBMP8   flags;
}HASH,*PHASH;

It would require to write "xx.data.score" instead of "xx.score" but I think this would be acceptable.

Too ugly and would have needed me to make changes to the previous code. Note that annonymous structs are not standard in C++ but I used them anyway since many compilers has support for them. C++11 responded to the cries of many programmers and has support for them now.

Daniel

[elcabesa]

You are not seriously believing that a difference of 1 score point in the opening evaluation can cause 'huge Elo loss', do you? You must have had some other bug.

I don't think +-1 eval would cause Huge elo loss, I probably had some bug.
This time I wanted to be sure I did it the right way so I tested the sum algorithm and i get this strage +-1 bug. I don't think it will probably give me elo loss, but if there are way to do without +-1 error I'd like to use them

[Sven]

You are not seriously believing that a difference of 1 score point in the opening evaluation can cause 'huge Elo loss', do you? You must have had some other bug.

I don't think +-1 eval would cause Huge elo loss, I probably had some bug.
This time I wanted to be sure I did it the right way so I tested the sum algorithm and i get this strage +-1 bug. I don't think it will probably give me elo loss, but if there are way to do without +-1 error I'd like to use them

Which kind of "+- 1 bug" are you talking about, other than what has been explained by Gerd and also in the context of the thread I pointed you to?

Sven

[elcabesa]

the code I initially wrote has a +-1 error in one of the value stored after a sum

[hgm]

There need not be any error. If you want to calculate an interpolation of middle-game eval M and end-game eval E as w*M + (1-w)*E = E + w*(M-E) you can tabulate the PST contributions E + CONST*(M-E), where CONST = (1<<16), and sum them incrementally to a combined eval X. Then

Y = X * (CONST + w) =
(E + (M-E)*CONST)*(CONST + w) =
(M-E)*CONST*CONST + E*CONST + w*(M-E)*CONST + w*E =
E*CONST + w*E + w*(M-E)*CONST

because CONST*CONST = 1<<32 and multiplication with it shifts the first (M-E) term completely out of the 32-bit word without leaving a trace. The sought quantity E+w*(M-E) is now multiplied by CONST (i.e. shifted to the high-order 16 bits), but it is contaminated with w*E, which lives in the low-order 16 bits, and is quite small compared to a single score point multiplied by CONST. So what you do to get rid of it is add a quantity to it larger than a negative 16-bit score is expected to get, to make sure it is positive. Then you get rid of the multipy by CONST through shifting 16 bits to the right, which pushes w*E entirely out of the word, and leaves E+w*(M-E).

Now in these formula w would be a multiplier between 0 and 1. Usually the game phase is something running from 0-32, though (adding total material as N,B=1, R=3, Q=6), so you have to factor in an extra division by 32 (right-shift by 5) to convert it to w. This can be done implicitly

Code: Select all

// in Evaluate()
#define CONST &#40;1<<16&#41;
int X = &#40;difEval * &#40;CONST*32LL + gamePhase&#41; >> 5&#41; + 10000;
X >>= 16;
// X is now the interpolated eval

[sje]

1) I actually meant to write "compactification" which is better Latin-wise.

2) I forgot to mention that an opening book is a good prospect for compactification. The number of book entries may be high and the need for access speed is fairly low. I have used an opening book compactification scheme for my program Myopic. Myopic's book is limited to 32 KB because of the need to fit on an Arduino Mega embeddable system which has only 128 KB ROM total.

[DrRibosome]

just tried this in my engine and seems to have sped up nps by ~5% (measured on 2k sample positions)