Magic number generation taking 17 seconds or more

[krismchess]

Hi,
I am writing my own chess engine named Permabrain using magic bitboards technique (fancy). I am able to generate magics, but that is taking a bit longer than usual. I have experienced that the stockfishchess engine is pretty quick in generating the magics. I am given to understand that the stockfishchess random number generator (PRNG) & the seed it uses make the generation much faster. However I am using merssene twister engine from the standard C++ 11 library as shown below:

class Random {
private:
std::mt19937_64 mtEngine;
std::uniform_int_distribution<uint64_t> randomEngine;
public:
Random() : mtEngine(),randomEngine() {
mtEngine = std::mt19937_64(random());
}

Random(uint64_t seed) : mtEngine(),randomEngine() {
mtEngine = std::mt19937_64(seed);
}

uint64_t next() {
return randomEngine(mtEngine);
}
};

And this is how I use it (without any seeds):
Random random;

do {
magic = random.next() & random.next() & random.next();
} while (popCount((mask * magic) >> 56 ) < 6);

This while loop is taking a longer time to finish & on an average it takes 17 seconds to finish the complete magic bitboard tables for rooks & Bishops.

I'd appreciate if someone can help me understand what's going on here.

Many thanks.

Kalyan

[matthewlai]

C++ provides the std::random_device class for seeding RNGs.

I would do something like this -

Code: Select all

std::random_device rd;
std::mt19937_64 mt(rd());
std&#58;&#58;uniform_int_distribution<uint64_t> dist;

auto drawFunc = std&#58;&#58;bind&#40;dist, mt&#41;;

Then you can just call drawFunc() to get a number;

Other than that, I don't see anything strange.

Have you tried profiling to see what's taking the time?

[mcostalba]

I'd appreciate if someone can help me understand what's going on here.

Someone has tried all the possible seeds (well, not all but many) until it found a seed that creates a pseudo-random sequence that is optimal to find the magics in the minimum time.

I'd suggest to re-read SF sources becuase you are missing a key point: seed is not just a casual seed.

[krismchess]

Thanks Matthew Lai.

I did this change and added the compiler switch -O3 which brought down the running time to less than 2 seconds:

std::mersenne_twister_engine<uint64_t,64, 312, 156,
31, 0xb5026f5aa96619e9ULL,
29, 0x5555555555555555ULL,
17, 0x71d67fffeda60000ULL,
37, 0xfff7eee000000000ULL,
43, 6364136223846793005ULL> mtEngine;

With std:mt19937_64 & with -O3 switch it's significantly slower (7 seconds on an average is what I got).

Without -O3 it slows down significantly.

[krismchess]

Hi Matthew Lai,

Your solution also works. Even without -O3 compiler switch I am getting faster magic moves generation. It now consistently takes 3 seconds.

I am sticking with your solution for now.

[mar]

Just one remark: you don't need uniform distribution, because if you generate numbers in the range of 0..2^n-1 (inclusive), they're always uniform.
For example, if you want to generate 0..65535, just and with 65535 and you're done (providing the PRNG has output >=16-bit)
You could also try some fast KISS PRNGs, but I doubt it would make much of a difference, MT is good but it needs extra work each 624 samples;
but you'd have to profile & measure, this is just my guess

[matthewlai]

Just one remark: you don't need uniform distribution, because if you generate numbers in the range of 0..2^n-1 (inclusive), they're always uniform.
For example, if you want to generate 0..65535, just and with 65535 and you're done (providing the PRNG has output >=16-bit)
You could also try some fast KISS PRNGs, but I doubt it would make much of a difference, MT is good but it needs extra work each 624 samples;
but you'd have to profile & measure, this is just my guess

My guess is there is no performance difference in practice, because function inlining and other optimizations will take out the extra code anyways.

[Gerd Isenberg]

The precondition for a good "sparse random" magic factor seems that the upper byte of the 64-bit product with the relevant occupancy mask has at least 6 bits set, so that the index distribution for all subset masks promises a good collision property. I guess the trick largely depends on properties of the used PRNG and seed. I'll suggest to profile how long it takes for every rook and bishop square, how often it loops per square in the first do while popcount loop, and how many trials are used at all per square and piece to find a destructive collision free magic.

[mar]

My guess is there is no performance difference in practice, because function inlining and other optimizations will take out the extra code anyways.

I just did a quick test (generating 1 billion numbers) using my KISS PRNG and 64-bit std:: MT
The result: KISS is 5x faster (msc, 64-bit compile).

[matthewlai]

My guess is there is no performance difference in practice, because function inlining and other optimizations will take out the extra code anyways.

I just did a quick test (generating 1 billion numbers) using my KISS PRNG and 64-bit std:: MT
The result: KISS is 5x faster (msc, 64-bit compile).

I meant using uniform_int_distribution on top of the RNG vs RNG directly.