Something very strange [Strelka]

[hgm]

Yes, this is a beautiful piece of code. I was not aware of that math.
I also wonder who the inventor of these index mapping is.
Less populated, but more valuable pieces use the less significant bits.

Why do you see this as a desirable feature? In Joker I do this indexing for black and white separately, so that the tables can be so small that they are always cached, and the details of the mapping are unimportant. But If I would have to think how to best do it for a large table, I would be inclined to do it oppositely from what is shown here: put the most abundant pieces in the low bits. If you have the Queens there, and a Queen is captured, you immediately reduce the packing density of the used entries by a factor 2 (reducing cache hits). If there are Pawns there, and one is captured, 8/9 of the entries is still relevant.

[Gerd Isenberg]

Yes, this is a beautiful piece of code. I was not aware of that math.
I also wonder who the inventor of these index mapping is.
Less populated, but more valuable pieces use the less significant bits.

Why do you see this as a desirable feature? In Joker I do this indexing for black and white separately, so that the tables can be so small that they are always cached, and the details of the mapping are unimportant. But If I would have to think how to best do it for a large table, I would be inclined to do it oppositely from what is shown here: put the most abundant pieces in the low bits. If you have the Queens there, and a Queen is captured, you immediately reduce the packing density of the used entries by a factor 2 (reducing cache hits). If there are Pawns there, and one is captured, 8/9 of the entries is still relevant.

Yes, you are right. It is a simple nested enumeration of 236196 material-recombinations which might be done in several ways.

Code: Select all

void traverseMaterial1()
{
	int sum, n = 0;

	for (int bp = 0; bp < 9; bp++)
	for (int wp = 0; wp < 9; wp++)
	for (int bn = 0; bn < 3; bn++)
	for (int wn = 0; wn < 3; wn++)
	for (int bb = 0; bb < 3; bb++)
	for (int wb = 0; wb < 3; wb++)
	for (int br = 0; br < 3; br++)
	for (int wr = 0; wr < 3; wr++)
	for (int bq = 0; bq < 2; bq++)
	for (int wq = 0; wq < 2; wq++)
	{
		sum =		
			wq +
			bq * 2 +
			wr * 2*2 +
			br * 2*2*3 +
			wb * 2*2*3*3 +
			bb * 2*2*3*3*3 +
			wn * 2*2*3*3*3*3 +
			bn * 2*2*3*3*3*3*3 +
			wp * 2*2*3*3*3*3*3*3 +
			bp * 2*2*3*3*3*3*3*3*9;
		assert (n == sum);
		n++;
	}
	printf("%d material-combis, last key = 0x%08X\n", n, sum);
}

void traverseMaterial2()
{
	int sum, n = 0;

	for (int wq = 0; wq < 2; wq++)
	for (int bq = 0; bq < 2; bq++)
	for (int wr = 0; wr < 3; wr++)
	for (int br = 0; br < 3; br++)
	for (int wb = 0; wb < 3; wb++)
	for (int bb = 0; bb < 3; bb++)
	for (int wn = 0; wn < 3; wn++)
	for (int bn = 0; bn < 3; bn++)
	for (int wp = 0; wp < 9; wp++)
	for (int bp = 0; bp < 9; bp++)
	{
		sum =		
			bp +
			wp * 9 +
			bn * 9*9 +
			wn * 9*9*3 +
			bb * 9*9*3*3 +
			wb * 9*9*3*3*3 +
			br * 9*9*3*3*3*3 +
			wr * 9*9*3*3*3*3*3 +
			bq * 9*9*3*3*3*3*3*3 +
			wq * 9*9*3*3*3*3*3*3*2;
		assert (n == sum);
		n++;
	}
	printf("%d material-combis, last key = 0x%08X\n", n, sum);
}

[Gerd Isenberg]

Why do you see this as a desirable feature? In Joker I do this indexing for black and white separately, so that the tables can be so small that they are always cached, and the details of the mapping are unimportant. But If I would have to think how to best do it for a large table, I would be inclined to do it oppositely from what is shown here: put the most abundant pieces in the low bits. If you have the Queens there, and a Queen is captured, you immediately reduce the packing density of the used entries by a factor 2 (reducing cache hits). If there are Pawns there, and one is captured, 8/9 of the entries is still relevant.

The point with most significant pawn counts - no overflow occurs after promotion results in unusual material with more than one queen etc. Collision check may be done by game-stage or some "unusual material" flag.

Thus, while make/unmake of captures/promotions you may add/sub the material-delta without affecting possible higher bits.

[hgm]

I don't think you can affort to do this at all. Although such a multiple-Queen position would not overflow the table, it would map into completely wrong piece combinations. If this table were to be used for the material evaluation (rather than for a correction on a separately updated differentialEval for material), the evaluation would be so wrong that a promotion that is really PV would be discarded because it does not notice the new Queen...

In Joker the promotion argument led me to do exactly the opposite, and use the Queen count for the dimension with the largest stride. Then having a super-numerary Queen does not collide with any of the other codes, and I just extended the table to allow upto 3 Queens. Of course in Joker's case that makes the table still only 144 entries, as I do not include Pawns and consider the colors separately.) Joker uses
nB + 2*nB' + 2*2*nN + 2*2*3*nR + 2*2*3*3*nQ

To allow for 3 Queens in stead of 1 (i.e. have 4 Queen states per color, in stead of 2) only makes a full table 4 times larger (1MB in stead of 231KB), and if the Queens determined the highest bits, the extra space would be very rarely probed, if at all. The frequently probed part of the table would consist of cache lines where frequently accessed information is very densely packed (because most lines would have 6 of the 8 pawns still present), and cache lines where you would not need any accesses at all for a long time because close to the root a higher piece was captured. This is ideal for high hit rate and low cache pollution.

At game level you would of course pack the table to squeeze out the combinations that became unreachable because of captures.

[Uri Blass]

I don't think you can affort to do this at all. Although such a multiple-Queen position would not overflow the table, it would map into completely wrong piece combinations. If this table were to be used for the material evaluation (rather than for a correction on a separately updated differentialEval for material), the evaluation would be so wrong that a promotion that is really PV would be discarded because it does not notice the new Queen...

In Joker the promotion argument led me to do exactly the opposite, and use the Queen count for the dimension with the largest stride. Then having a super-numerary Queen does not collide with any of the other codes, and I just extended the table to allow upto 3 Queens. Of course in Joker's case that makes the table still only 144 entries, as I do not include Pawns and consider the colors separately.) Joker uses
nB + 2*nB' + 2*2*nN + 2*2*3*nR + 2*2*3*3*nQ

To allow for 3 Queens in stead of 1 (i.e. have 4 Queen states per color, in stead of 2) only makes a full table 4 times larger (1MB in stead of 231KB), and if the Queens determined the highest bits, the extra space would be very rarely probed, if at all. The frequently probed part of the table would consist of cache lines where frequently accessed information is very densely packed (because most lines would have 6 of the 8 pawns still present), and cache lines where you would not need any accesses at all for a long time because close to the root a higher piece was captured. This is ideal for high hit rate and low cache pollution.

At game level you would of course pack the table to squeeze out the combinations that became unreachable because of captures.

The table is used only for corrections for the material difference
when pawn=1 knight=bishop=3 rook=5 queen=10
so there is no problem if the corrections are not big

There can be a problem with KNN vs K 324*2 that is the same as KN vs Kbbb 324+108*3 but kbbb vs KN win usually for black and overevaluating it for black(that really happens) is not a big problem.

Inspite all of this I do not like this solution and I think that it is better to
have table not for corrections but for real material and detect cases when
you are out of tables to calculate different

I do not like the fact that rybka's evaluation is not symmetric and kbbb vsKN is evaluated in a different way than KBBB vs Kn

Uri

[hgm]

So now we know why Rybka did not support under-promotions?