Finding special magic numbers

[dangi12012]

My god people - someone should just post results!

King is perfectly hashable - meaning you just can pick 256 slots per square and be done with it.
Obviously you could fiddle with the offsets and seeds to compact the table but this is a KISS solution.

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <vector>
#include <set>
#include <iostream>
#include <bitset>
#include <bit>
#include <immintrin.h>


constexpr int bits = 8;

uint64_t _rnd_seed{};
uint64_t rnd()
{
	uint64_t z = (_rnd_seed += UINT64_C(0x9E3779B97F4A7C15));
	z = (z ^ (z >> 30)) * UINT64_C(0xBF58476D1CE4E5B9);
	z = (z ^ (z >> 27)) * UINT64_C(0x94D049BB133111EB);
	return z ^ (z >> 31);
}

struct SquareHash
{
	int sq;
	std::vector<uint64_t> AllAttacks;
};

static constexpr uint64_t fold(uint64_t num, uint64_t seed)
{
	return (num * seed) >> (64 - bits);
}

static constexpr uint64_t KingAttacks[] = {
	0x0000000000000302, 0x0000000000000705, 0x0000000000000E0A, 0x0000000000001C14, 0x0000000000003828, 0x0000000000007050, 0x000000000000E0A0, 0x000000000000C040,
	0x0000000000030203, 0x0000000000070507, 0x00000000000E0A0E, 0x00000000001C141C, 0x0000000000382838, 0x0000000000705070, 0x0000000000E0A0E0, 0x0000000000C040C0,
	0x0000000003020300, 0x0000000007050700, 0x000000000E0A0E00, 0x000000001C141C00, 0x0000000038283800, 0x0000000070507000, 0x00000000E0A0E000, 0x00000000C040C000,
	0x0000000302030000, 0x0000000705070000, 0x0000000E0A0E0000, 0x0000001C141C0000, 0x0000003828380000, 0x0000007050700000, 0x000000E0A0E00000, 0x000000C040C00000,
	0x0000030203000000, 0x0000070507000000, 0x00000E0A0E000000, 0x00001C141C000000, 0x0000382838000000, 0x0000705070000000, 0x0000E0A0E0000000, 0x0000C040C0000000,
	0x0003020300000000, 0x0007050700000000, 0x000E0A0E00000000, 0x001C141C00000000, 0x0038283800000000, 0x0070507000000000, 0x00E0A0E000000000, 0x00C040C000000000,
	0x0302030000000000, 0x0705070000000000, 0x0E0A0E0000000000, 0x1C141C0000000000, 0x3828380000000000, 0x7050700000000000, 0xE0A0E00000000000, 0xC040C00000000000,
	0x0203000000000000, 0x0507000000000000, 0x0A0E000000000000, 0x141C000000000000, 0x2838000000000000, 0x5070000000000000, 0xA0E0000000000000, 0x40C0000000000000,
};

int main(int argc, char* argv[])
{
	printf("Preparing all possible attacks...\n");
	std::vector<SquareHash> sqrs;
	for (int i = 0; i < 64; i++)
	{
		SquareHash sq;
		sq.sq = i;
		int bits = std::popcount(KingAttacks[i]);
		int max = 1 << bits;
		printf("King - %i sees: %i \n", i, max);

		for (uint64_t config = 0; config < max; config++)
		{
			sq.AllAttacks.push_back(_pdep_u64(config, KingAttacks[i]));
		}
		sqrs.push_back(sq);
	}
	
	
	char indexes[1 << bits]{ };
	int max = 0;

	printf("\nSolving hashes...\n");
	for (int r = 0; r < 64; r++)
	{
		uint64_t hash;
		while (true)
		{
			hash = rnd() & rnd();
			auto& data = sqrs[r].AllAttacks;

			int n = 0;
			for (n = 0; n < data.size(); n++) {
				int idx = fold(data[n], hash);

				if (indexes[idx] != 0) break;
				else {
					indexes[idx] = 1;
				}
			}

			if (n == data.size()) {
				break;
			}
			for (int m = 0; m <= n; m++)
			{
				indexes[fold(data[m], hash)] = 0;
			}
		}
		memset(indexes, 0, sizeof(indexes));
		std::cout << "offset: " << r * (1ull << bits) << " hash: " << hash << "ull,\n";
	}

	return 0;
}

Results:
Duration: 0.8s
Time to code: 23 minutes
Time to create this comment: 6 minutes
Good evening: Yes
Not enough time spent with my family: Also yes

Code: Select all

offset: 0 hash: 7070801120907052452ull,
offset: 256 hash: 3647995412772061314ull,
offset: 512 hash: 9656034352776775979ull,
offset: 768 hash: 9872171867031310341ull,
offset: 1024 hash: 4918318714698474312ull,
offset: 1280 hash: 11695880298579107858ull,
offset: 1536 hash: 3560395457913946117ull,
offset: 1792 hash: 313044180354105376ull,
offset: 2048 hash: 5623184287324246281ull,
offset: 2304 hash: 2594741888837877952ull,
offset: 2560 hash: 17294598824379220418ull,
offset: 2816 hash: 9800976838070141296ull,
offset: 3072 hash: 1441207406165692416ull,
offset: 3328 hash: 9367514987603951681ull,
offset: 3584 hash: 216315787634360332ull,
offset: 3840 hash: 2353359654043880752ull,
offset: 4096 hash: 2595200559335080202ull,
offset: 4352 hash: 7286842089993732096ull,
offset: 4608 hash: 10376857797085367368ull,
offset: 4864 hash: 785880750612807729ull,
offset: 5120 hash: 667659505907274248ull,
offset: 5376 hash: 2974065309374817280ull,
offset: 5632 hash: 9331740041468193330ull,
offset: 5888 hash: 12307286778091439110ull,
offset: 6144 hash: 2325301143867361346ull,
offset: 6400 hash: 3177324791308878336ull,
offset: 6656 hash: 621584744421003848ull,
offset: 6912 hash: 1486541348164864ull,
offset: 7168 hash: 288815325066068993ull,
offset: 7424 hash: 9385785298048319700ull,
offset: 7680 hash: 581845062930923592ull,
offset: 7936 hash: 579763140296994ull,
offset: 8192 hash: 14123715974026854402ull,
offset: 8448 hash: 324295594686546184ull,
offset: 8704 hash: 194220001719354466ull,
offset: 8960 hash: 164386437290067081ull,
offset: 9216 hash: 11110732141628523092ull,
offset: 9472 hash: 2308871347706019853ull,
offset: 9728 hash: 579100271700615204ull,
offset: 9984 hash: 16092224332266211585ull,
offset: 10240 hash: 2595846347999570272ull,
offset: 10496 hash: 2165221246067901448ull,
offset: 10752 hash: 14559011781550285057ull,
offset: 11008 hash: 6917599404035760384ull,
offset: 11264 hash: 1173188819646696448ull,
offset: 11520 hash: 221205522014050368ull,
offset: 11776 hash: 5478218039440708128ull,
offset: 12032 hash: 12909886229102863114ull,
offset: 12288 hash: 1152978683808661764ull,
offset: 12544 hash: 316699489637239172ull,
offset: 12800 hash: 4625198273325433186ull,
offset: 13056 hash: 146688054685859937ull,
offset: 13312 hash: 2314929935946514508ull,
offset: 13568 hash: 11857227922030630ull,
offset: 13824 hash: 4738633492137566227ull,
offset: 14080 hash: 14339483513353539973ull,
offset: 14336 hash: 358552495457544ull,
offset: 14592 hash: 4654784745142514737ull,
offset: 14848 hash: 9369785209685806248ull,
offset: 15104 hash: 4793326623606882872ull,
offset: 15360 hash: 2026646257774117162ull,
offset: 15616 hash: 18158093228589586ull,
offset: 15872 hash: 28217938506989665ull,
offset: 16128 hash: 6921480672498688066ull,

Knight is left as an exercise to the reader. For the more advanced problems I have a mathematics trick that finds good candidates around 100x faster - also above solution can be done on a gpu yielding 3.5 orders of magnitude improvement.
It was interesting and needed to hash all possible slider attacks (14bit per slot) in a table as small as possible.
Hoping above helps in your problem.
I am addicted to chessprogramming again... Taking a 1 week break cya.

[gxchess1]

For a Knight it would be even easier,: the magic multiplier 0x0000080200002020ull would map each bit to the upper byte, without contaminating any of those:

Code: Select all

00000e00 0f0000g0 h0000000 00000000 000000a0 b0000c00 0d000000 00000000 (moves for knight at LSB)
e000f000 0g0h0000 00000000 00000000 0a0b0000 c000d000 00000000 00000000 (<< 5)
0g0h0000 00000000 00000000 0a0b0000 c000d000 00000000 00000000 00000000 (<< 13)
00000a0b 0000c000 d0000000 00000000 00000000 00000000 00000000 00000000 (<< 33)
00c000d0 00000000 00000000 00000000 00000000 00000000 00000000 00000000 (<< 43)
____________________________________________________________________ +
egchfadb ??0hcg? ?0000000 ...

Running some tests, for example, for knight square C3, both generate '0':

Code: Select all

uint8_t map(uint8_t sq, Bitboard bb) {
	Bitboard x = std::rotr(x, sq); 			// rotate right
	return (x * 0x0000080200002020ull) >> 56;	// multiply && shift
}

// now I get:
map(C3, 1ull << A4) == 0
map(C3, 1ull << E4) == 0

Which shouldn't be so because they are supposed to map into a different index.

[dangi12012]

Solution for knight:

Code: Select all

square: 0 offset: 0 hash: 7070801120907052452ull
square: 1 offset: 256 hash: 1371778230308577418ull
square: 2 offset: 512 hash: 324279213639344672ull
square: 3 offset: 768 hash: 3647995412772061314ull
square: 4 offset: 1024 hash: 4634807373638212608ull
square: 5 offset: 1280 hash: 9656034352776775979ull
square: 6 offset: 1536 hash: 9514433749938077705ull
square: 7 offset: 1792 hash: 4686279155557470724ull
square: 8 offset: 2048 hash: 4918318714698474312ull
square: 9 offset: 2304 hash: 10474247730220778089ull
square: 10 offset: 2560 hash: 9876465734551537412ull
square: 11 offset: 2816 hash: 13007566534099874822ull
square: 12 offset: 3072 hash: 2384671397466080393ull
square: 13 offset: 3328 hash: 10890058493709166245ull
square: 14 offset: 3584 hash: 10388141885557375017ull
square: 15 offset: 3840 hash: 4900201208440177417ull
square: 16 offset: 4096 hash: 13914012355374994512ull
square: 17 offset: 4352 hash: 2020462568043196472ull
square: 18 offset: 4608 hash: 1153205333242415377ull
square: 19 offset: 4864 hash: 2882867984937038625ull
square: 20 offset: 5120 hash: 3603170170601747816ull
square: 21 offset: 5376 hash: 11011582607937765409ull
square: 22 offset: 5632 hash: 10022787915731435568ull
square: 23 offset: 5888 hash: 4828426208944427027ull
square: 24 offset: 6144 hash: 307372908330692994ull
square: 25 offset: 6400 hash: 36143283969895436ull
square: 26 offset: 6656 hash: 50111482608746560ull
square: 27 offset: 6912 hash: 2902149947070087680ull
square: 28 offset: 7168 hash: 23083150469505348ull
square: 29 offset: 7424 hash: 298082825087750657ull
square: 30 offset: 7680 hash: 939146889428804352ull
square: 31 offset: 7936 hash: 871182920185430018ull
square: 32 offset: 8192 hash: 11646383472427210816ull
square: 33 offset: 8448 hash: 10197016548666247172ull
square: 34 offset: 8704 hash: 211398300468224ull
square: 35 offset: 8960 hash: 9299942028762685574ull
square: 36 offset: 9216 hash: 216245358474068002ull
square: 37 offset: 9472 hash: 22568577836064800ull
square: 38 offset: 9728 hash: 649121704571965568ull
square: 39 offset: 9984 hash: 1174876777223332884ull
square: 40 offset: 10240 hash: 9910318598084100240ull
square: 41 offset: 10496 hash: 45260657452908576ull
square: 42 offset: 10752 hash: 618525769797ull
square: 43 offset: 11008 hash: 16149908609529026600ull
square: 44 offset: 11264 hash: 13837644142081035284ull
square: 45 offset: 11520 hash: 5335113028436238870ull
square: 46 offset: 11776 hash: 11836448488124845295ull
square: 47 offset: 12032 hash: 4770721579832573986ull
square: 48 offset: 12288 hash: 396468615785786369ull
square: 49 offset: 12544 hash: 9236048069158569028ull
square: 50 offset: 12800 hash: 2305845421451313221ull
square: 51 offset: 13056 hash: 9241968099366864909ull
square: 52 offset: 13312 hash: 1207268166507694601ull
square: 53 offset: 13568 hash: 10484670685180864561ull
square: 54 offset: 13824 hash: 333424711504778244ull
square: 55 offset: 14080 hash: 3175055401712624714ull
square: 56 offset: 14336 hash: 5237721903193834112ull
square: 57 offset: 14592 hash: 612489551876866560ull
square: 58 offset: 14848 hash: 9377901812558939301ull
square: 59 offset: 15104 hash: 1226402417790484621ull
square: 60 offset: 15360 hash: 651080209181425537ull
square: 61 offset: 15616 hash: 9223865562973621000ull
square: 62 offset: 15872 hash: 9228696012540872901ull
square: 63 offset: 16128 hash: 3029233734932021504ull

[gxchess1]

Solution for knight:

Code: Select all

square: 0 offset: 0 hash: 7070801120907052452ull
square: 1 offset: 256 hash: 1371778230308577418ull
square: 2 offset: 512 hash: 324279213639344672ull
square: 3 offset: 768 hash: 3647995412772061314ull
square: 4 offset: 1024 hash: 4634807373638212608ull
square: 5 offset: 1280 hash: 9656034352776775979ull
square: 6 offset: 1536 hash: 9514433749938077705ull
square: 7 offset: 1792 hash: 4686279155557470724ull
square: 8 offset: 2048 hash: 4918318714698474312ull
square: 9 offset: 2304 hash: 10474247730220778089ull
square: 10 offset: 2560 hash: 9876465734551537412ull
square: 11 offset: 2816 hash: 13007566534099874822ull
square: 12 offset: 3072 hash: 2384671397466080393ull
square: 13 offset: 3328 hash: 10890058493709166245ull
square: 14 offset: 3584 hash: 10388141885557375017ull
square: 15 offset: 3840 hash: 4900201208440177417ull
square: 16 offset: 4096 hash: 13914012355374994512ull
square: 17 offset: 4352 hash: 2020462568043196472ull
square: 18 offset: 4608 hash: 1153205333242415377ull
square: 19 offset: 4864 hash: 2882867984937038625ull
square: 20 offset: 5120 hash: 3603170170601747816ull
square: 21 offset: 5376 hash: 11011582607937765409ull
square: 22 offset: 5632 hash: 10022787915731435568ull
square: 23 offset: 5888 hash: 4828426208944427027ull
square: 24 offset: 6144 hash: 307372908330692994ull
square: 25 offset: 6400 hash: 36143283969895436ull
square: 26 offset: 6656 hash: 50111482608746560ull
square: 27 offset: 6912 hash: 2902149947070087680ull
square: 28 offset: 7168 hash: 23083150469505348ull
square: 29 offset: 7424 hash: 298082825087750657ull
square: 30 offset: 7680 hash: 939146889428804352ull
square: 31 offset: 7936 hash: 871182920185430018ull
square: 32 offset: 8192 hash: 11646383472427210816ull
square: 33 offset: 8448 hash: 10197016548666247172ull
square: 34 offset: 8704 hash: 211398300468224ull
square: 35 offset: 8960 hash: 9299942028762685574ull
square: 36 offset: 9216 hash: 216245358474068002ull
square: 37 offset: 9472 hash: 22568577836064800ull
square: 38 offset: 9728 hash: 649121704571965568ull
square: 39 offset: 9984 hash: 1174876777223332884ull
square: 40 offset: 10240 hash: 9910318598084100240ull
square: 41 offset: 10496 hash: 45260657452908576ull
square: 42 offset: 10752 hash: 618525769797ull
square: 43 offset: 11008 hash: 16149908609529026600ull
square: 44 offset: 11264 hash: 13837644142081035284ull
square: 45 offset: 11520 hash: 5335113028436238870ull
square: 46 offset: 11776 hash: 11836448488124845295ull
square: 47 offset: 12032 hash: 4770721579832573986ull
square: 48 offset: 12288 hash: 396468615785786369ull
square: 49 offset: 12544 hash: 9236048069158569028ull
square: 50 offset: 12800 hash: 2305845421451313221ull
square: 51 offset: 13056 hash: 9241968099366864909ull
square: 52 offset: 13312 hash: 1207268166507694601ull
square: 53 offset: 13568 hash: 10484670685180864561ull
square: 54 offset: 13824 hash: 333424711504778244ull
square: 55 offset: 14080 hash: 3175055401712624714ull
square: 56 offset: 14336 hash: 5237721903193834112ull
square: 57 offset: 14592 hash: 612489551876866560ull
square: 58 offset: 14848 hash: 9377901812558939301ull
square: 59 offset: 15104 hash: 1226402417790484621ull
square: 60 offset: 15360 hash: 651080209181425537ull
square: 61 offset: 15616 hash: 9223865562973621000ull
square: 62 offset: 15872 hash: 9228696012540872901ull
square: 63 offset: 16128 hash: 3029233734932021504ull

So it's possible but will use 128kb for the tables. I wanna see currently if I can use less memory currently.
Thanks a lot friend!

Also, I managed to get 500M nps perft thanks to your article!

[hgm]

You are right, I messed up. The pattern I gave for the Knight on a1 is not correct. A, b, c and d should all have been shifted 8 bits down. That means the left shifts to bring those in view should have been 8 larger (41 instead of 33, 51 instead of 43). So the magic multiplier should have been 0x0008020000002020ull.

[dangi12012]

My friend. Its possible to get much smaller than that.
Let me show how to ALMOST perfectly hash:

This contains 2 additional ideas.
1) Correctnes verification of results (important for any project)
2) Finding the first index where the hashed slots will fit into an array. Just iterating 100k times per single increase of offset yields this.
I mean why would a 8 move hashfunction need 256 full slots? The answer is it does not.

Outcome is the same as before - but much denser. Offset + Hash Seed (commonly known as magic)

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <vector>
#include <set>
#include <iostream>
#include <bitset>
#include <bit>
#include <immintrin.h>


constexpr int bits = 8;

uint64_t _rnd_seed{};
uint64_t rnd()
{
	uint64_t z = (_rnd_seed += UINT64_C(0x9E3779B97F4A7C15));
	z = (z ^ (z >> 30)) * UINT64_C(0xBF58476D1CE4E5B9);
	z = (z ^ (z >> 27)) * UINT64_C(0x94D049BB133111EB);
	return z ^ (z >> 31);
}

struct SquareHash
{
	int sq;
	std::vector<uint64_t> AllAttacks;
};

static constexpr uint64_t fold(uint64_t num, uint64_t seed)
{
	return (num * seed) >> (64 - bits);
}


static constexpr uint64_t KingAttacks[] = {
	0x0000000000000302, 0x0000000000000705, 0x0000000000000E0A, 0x0000000000001C14, 0x0000000000003828, 0x0000000000007050, 0x000000000000E0A0, 0x000000000000C040,
	0x0000000000030203, 0x0000000000070507, 0x00000000000E0A0E, 0x00000000001C141C, 0x0000000000382838, 0x0000000000705070, 0x0000000000E0A0E0, 0x0000000000C040C0,
	0x0000000003020300, 0x0000000007050700, 0x000000000E0A0E00, 0x000000001C141C00, 0x0000000038283800, 0x0000000070507000, 0x00000000E0A0E000, 0x00000000C040C000,
	0x0000000302030000, 0x0000000705070000, 0x0000000E0A0E0000, 0x0000001C141C0000, 0x0000003828380000, 0x0000007050700000, 0x000000E0A0E00000, 0x000000C040C00000,
	0x0000030203000000, 0x0000070507000000, 0x00000E0A0E000000, 0x00001C141C000000, 0x0000382838000000, 0x0000705070000000, 0x0000E0A0E0000000, 0x0000C040C0000000,
	0x0003020300000000, 0x0007050700000000, 0x000E0A0E00000000, 0x001C141C00000000, 0x0038283800000000, 0x0070507000000000, 0x00E0A0E000000000, 0x00C040C000000000,
	0x0302030000000000, 0x0705070000000000, 0x0E0A0E0000000000, 0x1C141C0000000000, 0x3828380000000000, 0x7050700000000000, 0xE0A0E00000000000, 0xC040C00000000000,
	0x0203000000000000, 0x0507000000000000, 0x0A0E000000000000, 0x141C000000000000, 0x2838000000000000, 0x5070000000000000, 0xA0E0000000000000, 0x40C0000000000000,
};

void verify(std::vector<std::tuple<uint64_t, uint64_t>>& sols) {
	printf("Verify...");
	char index[64 << bits]{};
	for (int i = 0; i < 64; i++)
	{
		uint64_t offset = std::get<0>(sols[i]);
		uint64_t seed = std::get<1>(sols[i]);
		char* lookup = index + offset;

		int bits = std::popcount(KingAttacks[i]);
		int max = 1 << bits;

		for (uint64_t config = 0; config < max; config++)
		{
			uint64_t SEE = _pdep_u64(config, KingAttacks[i]);
			int index = fold(SEE, seed);

			if (lookup[index] != 0) {
				printf("Verify failed!\n");
				return;
			}
			else lookup[index] = 1;
		}
	}
	printf("OK");
}

int main(int argc, char* argv[])
{
	printf("Preparing all possible attacks...\n");
	std::vector<SquareHash> sqrs;
	int total_see = 0;
	for (int i = 0; i < 64; i++)
	{
		SquareHash sq;
		sq.sq = i;
		int bits = std::popcount(KingAttacks[i]);
		int max = 1 << bits;
		printf("King - %i sees: %i \n", i, max);
		total_see+= max;

		for (uint64_t config = 0; config < max; config++)
		{
			sq.AllAttacks.push_back(_pdep_u64(config, KingAttacks[i]));
		}
		sqrs.push_back(sq);
	}
	printf("Total slots to be hashed: %i \n", total_see);
	
	
	char superindexes[64 << bits]{};
	int max = 0;

	printf("\nSolving hashes...\n");
	std::vector<std::tuple<uint64_t, uint64_t>> sols;
	for (int r = 0; r < 64; r++)
	{
		uint64_t hash;
		auto& data = sqrs[r].AllAttacks;
		for (int index_offset = 0; index_offset < (64 * (1 << bits)); index_offset++)
		{
			char* indexes = superindexes + index_offset;
			int n = 0;
			for (int tries = 0; tries < 1E5; tries++)
			{
				hash = rnd() & rnd();

				for (n = 0; n < data.size(); n++) {
					int idx = fold(data[n], hash);

					if (indexes[idx] != 0) break;
					else {
						indexes[idx] = 1;
					}
				}

				if (n == data.size()) {
					break;
				}
				for (int m = 0; m < n; m++)
				{
					indexes[fold(data[m], hash)] = 0;
				}
			}
			if (n == data.size()) {
				std::cout << "square: " << r << " offset: " << (indexes - superindexes) << " hash: " << hash << "ull\n";
				sols.push_back({ (indexes - superindexes) , hash });
				break;
			}
		}
	}
	verify(sols);


	return 0;
}

If you sum up all the king configuration squares you get:
"Total slots to be hashed: 10016"

You apply the code above to the problem you get:
"Final Array size is 10658"

So this is very - very dense and only a few empty slots remain.

Code: Select all

Solving hashes...
square: 0 offset: 0 hash: 7070801120907052452ull
square: 1 offset: 1 hash: 12541973424027075849ull
square: 2 offset: 2 hash: 292171327547380736ull
square: 3 offset: 4 hash: 1226668091073926280ull
square: 4 offset: 7 hash: 5260697495734059192ull
square: 5 offset: 73 hash: 2319117550636503041ull
square: 6 offset: 143 hash: 8640061366847160848ull
square: 7 offset: 6 hash: 39725355127415200ull
square: 8 offset: 197 hash: 8165238894957447168ull
square: 9 offset: 443 hash: 11533791230643347968ull
square: 10 offset: 699 hash: 3461052597538917376ull
square: 11 offset: 955 hash: 936915848349878656ull
square: 12 offset: 1211 hash: 288283703807967233ull
square: 13 offset: 1467 hash: 1297107646415640576ull
square: 14 offset: 1723 hash: 360312296886501632ull
square: 15 offset: 1979 hash: 6345687465702261841ull
square: 16 offset: 1980 hash: 9593379964858867747ull
square: 17 offset: 2235 hash: 5827673603071610371ull
square: 18 offset: 2491 hash: 6021313569379074065ull
square: 19 offset: 2747 hash: 14197598933955658760ull
square: 20 offset: 3003 hash: 4689375072654499904ull
square: 21 offset: 3259 hash: 10098759322873046018ull
square: 22 offset: 3515 hash: 6929070266728317062ull
square: 23 offset: 368 hash: 10669080843641758721ull
square: 24 offset: 1981 hash: 746832367708686369ull
square: 25 offset: 3771 hash: 1774453464467243032ull
square: 26 offset: 4027 hash: 2306212475755877376ull
square: 27 offset: 4283 hash: 294144651747655690ull
square: 28 offset: 4539 hash: 47081088715128864ull
square: 29 offset: 4795 hash: 288520922736890024ull
square: 30 offset: 5051 hash: 10700553815521757193ull
square: 31 offset: 1984 hash: 90164490187833728ull
square: 32 offset: 5307 hash: 13516433948131353090ull
square: 33 offset: 5560 hash: 18349887032918273ull
square: 34 offset: 5816 hash: 5800847769929384296ull
square: 35 offset: 6072 hash: 6989644105531195393ull
square: 36 offset: 6328 hash: 4629877440461406256ull
square: 37 offset: 6584 hash: 290523484968730742ull
square: 38 offset: 6840 hash: 14854193751518281744ull
square: 39 offset: 5308 hash: 9382593455502401588ull
square: 40 offset: 5309 hash: 523123484243595334ull
square: 41 offset: 7096 hash: 3517737389596443648ull
square: 42 offset: 7352 hash: 1351164640532414976ull
square: 43 offset: 7608 hash: 578713256894664834ull
square: 44 offset: 7864 hash: 599406541061238912ull
square: 45 offset: 8120 hash: 953964740684555776ull
square: 46 offset: 8376 hash: 3172808480341889792ull
square: 47 offset: 5313 hash: 12115527508726782016ull
square: 48 offset: 8632 hash: 8071722678086533436ull
square: 49 offset: 8867 hash: 10682830110100292484ull
square: 50 offset: 9123 hash: 14700876092761180193ull
square: 51 offset: 9379 hash: 81280902223036568ull
square: 52 offset: 9635 hash: 16195191651452354636ull
square: 53 offset: 9891 hash: 1188953671039762470ull
square: 54 offset: 10147 hash: 7061645592522956819ull
square: 55 offset: 8633 hash: 12540274308705951769ull
square: 56 offset: 8 hash: 486549297112035330ull
square: 57 offset: 8635 hash: 5990531208056844290ull
square: 58 offset: 8638 hash: 3026423700365772293ull
square: 59 offset: 10403 hash: 5188762549331560662ull
square: 60 offset: 10404 hash: 1164637941101306180ull
square: 61 offset: 10405 hash: 1954566645604229409ull
square: 62 offset: 10408 hash: 38360040037488801ull
square: 63 offset: 47 hash: 580619450195523ull

Please notice how square 63 fits back into offset 47, or 56 at the very beginning. Filling holes where others left some space.
Now this whole thing can be improved another 1000 fold in terms of performance - it is an np hard problem and quite fun to get into.
You can also render above array into a bitmap giving you graphical intuition about what is going on.

This whole problem space of dense or perfect hashing is actually creating bitmaps from valid non self intersecting hash seeds - and trying to find an offset where the bitmaps wont intersect with each other. A bitmap is just all the "pixels" where the seed takes up a slot.

If you want ultimate performance in chessprogramming this whole concept can generally be used to replace loops with single lookups. Making an O(n) algorithm O(1).

[gxchess1]

You are right, I messed up. The pattern I gave for the Knight on a1 is not correct. A, b, c and d should all have been shifted 8 bits down. That means the left shifts to bring those in view should have been 8 larger (41 instead of 33, 51 instead of 43). So the magic multiplier should have been 0x0008020000002020ull.

Wow! works now! thanks )
Although the king magic doesn't work too. The thing is I kinda understand how did you get the magic but how did you resolve addition overflows? those are annoying to deal with when creating multiplicands.

[hgm]

I am not completely sure what you mean by 'addition overflows'. Sometimes it is not possible to get all bits uncontaminated to the upper byte, because the move patterns on the various ranks cannot be nicely interleaved. Then some bits for different squares will be added. And this potentially produces a carry, which would also contaminate the bits above it.

But this doesn't have to be a problem, as long as one of the bits that collide is also visible without contamination. Then it would alway be possible to reconstruct the other, as well as the carry that was generated by the addition. It just means that the mapping of move patterns to hash keys is altered, but it will still remain a 1-to-1 mapping.

For the King magic I gave:

Code: Select all

e00000fg h0000000 .... 000000ab c00000d0 (<< 0)
000fgh00 00000000 .... 000abc00 000d0000 (<< 3)
00abc000 00d00000 .... 00000000 00000000 (<< 52)
0d000000 00000000 .... 00000000 00000000 (<< 61)
___________________________________________ +
ed???hfg h0d00000 ...

the addition of the 0, 52 an 61-bit shift (i.e. multiplying by 0x2010000000000001ull) was completely collision free, and would result in

edabc0fg h0d00000 ...

in the upper two bytes. But it only leaves a hole of a single bit, and h is not yet contributing. The 3-shift brings h there, but contaminates the upper 5 bits by adding fg to those. Because of carry propagation this could also alter the upper three bits, so that they would not be equal to eda. But we know what f and g are; these were in the lower two bits of the upper byte, and were not contaminated by any carry. So you can undo the contamination by subtracting fg (i.e. key -= (key & 3) << 3) to get a key edabchfg. Now there isn't any reason to do that; it would just permute the elements of the hash table. (But in a different way for different values of fg. For a given fg you would be adding a constant to the index, which cyclically permutes that quarter of the table. Or not at all when fg=00.) Instead of adjusting the index at run time you might as well have permuted the values in the table to precompensate the contamination during initialization. The important thing is that it can be done; that proves the hashing is perfect.

I don't see any errors in this case. Are you sure the given magic does not work?

[dangi12012]

Better Table for king:

Code: Select all

square: 0 offset: 0 hash: 1155604348681060488ull - 0.0021171s
square: 1 offset: 1 hash: 78813614370193920ull - 0.0102721s
square: 2 offset: 3 hash: 40536799264636976ull - 0.0259498s
square: 3 offset: 10 hash: 21392992656954880ull - 0.0772784s
square: 4 offset: 21 hash: 613333974856597504ull - 0.22263s
square: 5 offset: 34 hash: 1626644032153190433ull - 0.452307s
square: 6 offset: 52 hash: 128071148797297664ull - 0.770248s
square: 7 offset: 12 hash: 2560318380540444676ull - 0.831728s
square: 8 offset: 115 hash: 17294378943730155905ull - 1.48143s
square: 9 offset: 369 hash: 6918166745744156674ull - 1.48301s
square: 10 offset: 625 hash: 1153489140914864144ull - 1.48521s
square: 11 offset: 881 hash: 1730526298759233536ull - 1.48799s
square: 12 offset: 1137 hash: 1441723901716729859ull - 1.49133s
square: 13 offset: 1393 hash: 3314675988910047872ull - 1.49538s
square: 14 offset: 1649 hash: 9028089975703552ull - 1.49986s
square: 15 offset: 1905 hash: 5999641344790773760ull - 4.69659s
square: 16 offset: 1906 hash: 4504716654578688ull - 7.8667s
square: 17 offset: 2151 hash: 9014122750673024ull - 7.87248s
square: 18 offset: 2407 hash: 4504845177028608ull - 7.87905s
square: 19 offset: 2663 hash: 299492682881827329ull - 7.88678s
square: 20 offset: 2919 hash: 1126454234518816ull - 7.89447s
square: 21 offset: 3175 hash: 2306406236331442208ull - 7.90342s
square: 22 offset: 3431 hash: 20547888585113600ull - 7.91233s
square: 23 offset: 1909 hash: 282093586227464ull - 10.923s
square: 24 offset: 1927 hash: 36064668619382880ull - 13.9777s
square: 25 offset: 3687 hash: 2749623500879691778ull - 13.9876s
square: 26 offset: 3943 hash: 4613990599664599040ull - 13.9977s
square: 27 offset: 4199 hash: 8797720426560ull - 14.0091s
square: 28 offset: 4455 hash: 2341928982053651720ull - 14.0203s
square: 29 offset: 4711 hash: 9223374511393472512ull - 14.0321s
square: 30 offset: 4967 hash: 4612813018387186696ull - 14.0446s
square: 31 offset: 2040 hash: 590261857493094656ull - 17.8058s
square: 32 offset: 5223 hash: 2378182122256990208ull - 22.9107s
square: 33 offset: 5474 hash: 687467528752ull - 22.9242s
square: 34 offset: 5730 hash: 36628924262645777ull - 22.9384s
square: 35 offset: 5986 hash: 5225301776900620304ull - 22.9533s
square: 36 offset: 6242 hash: 5767422289989668884ull - 22.9688s
square: 37 offset: 6498 hash: 938019827730481168ull - 22.9848s
square: 38 offset: 6754 hash: 306245612181266432ull - 23.0014s
square: 39 offset: 5224 hash: 281681672601600ull - 28.0786s
square: 40 offset: 5225 hash: 112592191889625090ull - 33.111s
square: 41 offset: 7010 hash: 4503606607365120ull - 33.1288s
square: 42 offset: 7266 hash: 31529664426093056ull - 33.1469s
square: 43 offset: 7522 hash: 2253451631354112ull - 33.166s
square: 44 offset: 7778 hash: 81364422511616ull - 33.1857s
square: 45 offset: 8034 hash: 162411061595669600ull - 33.2058s
square: 46 offset: 8290 hash: 9306697504521210912ull - 33.2264s
square: 47 offset: 5228 hash: 6055091915213252992ull - 38.2427s
square: 48 offset: 8546 hash: 144124018529223940ull - 45.8075s
square: 49 offset: 8724 hash: 72066546010161860ull - 45.8291s
square: 50 offset: 8980 hash: 9223449363656737986ull - 45.851s
square: 51 offset: 9236 hash: 54465425341677665ull - 45.8737s
square: 52 offset: 9492 hash: 1442696698822732ull - 45.8968s
square: 53 offset: 9748 hash: 4471061495846ull - 45.9205s
square: 54 offset: 10004 hash: 9511602692179402771ull - 45.9449s
square: 55 offset: 10260 hash: 144115892991559713ull - 56.0414s
square: 56 offset: 13 hash: 4611690553998836708ull - 56.109s
square: 57 offset: 8547 hash: 297800628452198666ull - 63.5383s
square: 58 offset: 8553 hash: 108093125834048673ull - 70.938s
square: 59 offset: 10261 hash: 1155604348681060488ull - 80.0972s
square: 60 offset: 10276 hash: 1154047405671448612ull - 89.2642s
square: 61 offset: 10284 hash: 1126037363130386ull - 98.3621s
square: 62 offset: 10325 hash: 2888038814167646225ull - 107.615s
square: 63 offset: 65 hash: 1152921505832141258ull - 107.978s
Verify...OK. Final Array size is 10500

10.5k slots in total. Thats as good as it will get as long as we dont allow self intersection. (For raw bits - yes, for movelist indexing - no)

[gxchess1]

Better Table for king:

Code: Select all

square: 0 offset: 0 hash: 1155604348681060488ull - 0.0021171s
square: 1 offset: 1 hash: 78813614370193920ull - 0.0102721s
square: 2 offset: 3 hash: 40536799264636976ull - 0.0259498s
square: 3 offset: 10 hash: 21392992656954880ull - 0.0772784s
square: 4 offset: 21 hash: 613333974856597504ull - 0.22263s
square: 5 offset: 34 hash: 1626644032153190433ull - 0.452307s
square: 6 offset: 52 hash: 128071148797297664ull - 0.770248s
square: 7 offset: 12 hash: 2560318380540444676ull - 0.831728s
square: 8 offset: 115 hash: 17294378943730155905ull - 1.48143s
square: 9 offset: 369 hash: 6918166745744156674ull - 1.48301s
square: 10 offset: 625 hash: 1153489140914864144ull - 1.48521s
square: 11 offset: 881 hash: 1730526298759233536ull - 1.48799s
square: 12 offset: 1137 hash: 1441723901716729859ull - 1.49133s
square: 13 offset: 1393 hash: 3314675988910047872ull - 1.49538s
square: 14 offset: 1649 hash: 9028089975703552ull - 1.49986s
square: 15 offset: 1905 hash: 5999641344790773760ull - 4.69659s
square: 16 offset: 1906 hash: 4504716654578688ull - 7.8667s
square: 17 offset: 2151 hash: 9014122750673024ull - 7.87248s
square: 18 offset: 2407 hash: 4504845177028608ull - 7.87905s
square: 19 offset: 2663 hash: 299492682881827329ull - 7.88678s
square: 20 offset: 2919 hash: 1126454234518816ull - 7.89447s
square: 21 offset: 3175 hash: 2306406236331442208ull - 7.90342s
square: 22 offset: 3431 hash: 20547888585113600ull - 7.91233s
square: 23 offset: 1909 hash: 282093586227464ull - 10.923s
square: 24 offset: 1927 hash: 36064668619382880ull - 13.9777s
square: 25 offset: 3687 hash: 2749623500879691778ull - 13.9876s
square: 26 offset: 3943 hash: 4613990599664599040ull - 13.9977s
square: 27 offset: 4199 hash: 8797720426560ull - 14.0091s
square: 28 offset: 4455 hash: 2341928982053651720ull - 14.0203s
square: 29 offset: 4711 hash: 9223374511393472512ull - 14.0321s
square: 30 offset: 4967 hash: 4612813018387186696ull - 14.0446s
square: 31 offset: 2040 hash: 590261857493094656ull - 17.8058s
square: 32 offset: 5223 hash: 2378182122256990208ull - 22.9107s
square: 33 offset: 5474 hash: 687467528752ull - 22.9242s
square: 34 offset: 5730 hash: 36628924262645777ull - 22.9384s
square: 35 offset: 5986 hash: 5225301776900620304ull - 22.9533s
square: 36 offset: 6242 hash: 5767422289989668884ull - 22.9688s
square: 37 offset: 6498 hash: 938019827730481168ull - 22.9848s
square: 38 offset: 6754 hash: 306245612181266432ull - 23.0014s
square: 39 offset: 5224 hash: 281681672601600ull - 28.0786s
square: 40 offset: 5225 hash: 112592191889625090ull - 33.111s
square: 41 offset: 7010 hash: 4503606607365120ull - 33.1288s
square: 42 offset: 7266 hash: 31529664426093056ull - 33.1469s
square: 43 offset: 7522 hash: 2253451631354112ull - 33.166s
square: 44 offset: 7778 hash: 81364422511616ull - 33.1857s
square: 45 offset: 8034 hash: 162411061595669600ull - 33.2058s
square: 46 offset: 8290 hash: 9306697504521210912ull - 33.2264s
square: 47 offset: 5228 hash: 6055091915213252992ull - 38.2427s
square: 48 offset: 8546 hash: 144124018529223940ull - 45.8075s
square: 49 offset: 8724 hash: 72066546010161860ull - 45.8291s
square: 50 offset: 8980 hash: 9223449363656737986ull - 45.851s
square: 51 offset: 9236 hash: 54465425341677665ull - 45.8737s
square: 52 offset: 9492 hash: 1442696698822732ull - 45.8968s
square: 53 offset: 9748 hash: 4471061495846ull - 45.9205s
square: 54 offset: 10004 hash: 9511602692179402771ull - 45.9449s
square: 55 offset: 10260 hash: 144115892991559713ull - 56.0414s
square: 56 offset: 13 hash: 4611690553998836708ull - 56.109s
square: 57 offset: 8547 hash: 297800628452198666ull - 63.5383s
square: 58 offset: 8553 hash: 108093125834048673ull - 70.938s
square: 59 offset: 10261 hash: 1155604348681060488ull - 80.0972s
square: 60 offset: 10276 hash: 1154047405671448612ull - 89.2642s
square: 61 offset: 10284 hash: 1126037363130386ull - 98.3621s
square: 62 offset: 10325 hash: 2888038814167646225ull - 107.615s
square: 63 offset: 65 hash: 1152921505832141258ull - 107.978s
Verify...OK. Final Array size is 10500

10.5k slots in total. Thats as good as it will get as long as we dont allow self intersection. (For raw bits - yes, for movelist indexing - no)

I have a solution with a 4K table (for knights but same idea) (and also without array of magic multipliers and no pext) so it's probably not what I need yet. This also probably doesn't scale to sliders because a way bigger array size right?