No TT hits with optimizations

[niel5946]

Hi.

I just tested Loki to make sure that the nodes searched at a certain depth was the same across compilers and architectures, and guess what... It wasn't . I then tried to disable compiler optimizations for the 64-bit executable, and it then searched 189234 nodes @ depth = 10 whereas it searched 246576 at the same depth with optimizations. Then, I tried to disable the TT probing without optimizations and got 246576, which must mean that the transposition table doesn't get probed properly with optimizations. (code for TT: https://github.com/BimmerBass/Loki/blob ... position.h - note: it has been made to be thread safe)

Is this something that happens to other engines or is it just my implementation that has bugs?

Any help is very much appreciated

[hgm]

Are you using the a library function for generating pseudo-random numbers? Different platforms use different PRNG, and if you use them for generating Zobrist keys this will alter the mapping from positions to TT entries, cause different replacements, and eventually a different search tree.

This should not depends on optimizations, thouhg. Unless you do unsafe optimizations that you cannot afford. Dependence on the optimization suggests use of unitialized (local) variables.

Best way is usually not to stare yourself blind on these things, but just check where the difference is coming from, by doing a 'divided search', which reports the number of nodes spent on every move or move sequence, and compare that for the two cases, to zoom in on the branch that causes the difference. Then you will know in a matter of minutes what otherwise might take you days.

[niel5946]

Are you using the a library function for generating pseudo-random numbers? Different platforms use different PRNG, and if you use them for generating Zobrist keys this will alter the mapping from positions to TT entries, cause different replacements, and eventually a different search tree.

This should not depends on optimizations, thouhg. Unless you do unsafe optimizations that you cannot afford. Dependence on the optimization suggests use of unitialized (local) variables.

Best way is usually not to stare yourself blind on these things, but just check where the difference is coming from, by doing a 'divided search', which reports the number of nodes spent on every move or move sequence, and compare that for the two cases, to zoom in on the branch that causes the difference. Then you will know in a matter of minutes what otherwise might take you days.

Yes, I am using the C++ <random> library and the following preprocessor macro:

Code: Select all

#define RAND_64     ((uint64_t)std::rand() | \
					(uint64_t)std::rand() << 15 | \
					(uint64_t)std::rand() << 30 | \
					(uint64_t)std::rand() << 45 | \
					((uint64_t)std::rand() & 0xf) << 60 )

What do you mean with unsafe optimizations?

I will try to implement some sort of divided search to check for discrepancies.

[mar]

Yes, I am using the C++ <random> library and the following preprocessor macro:

Code: Select all

#define RAND_64     ((uint64_t)std::rand() | \
					(uint64_t)std::rand() << 15 | \
					(uint64_t)std::rand() << 30 | \
					(uint64_t)std::rand() << 45 | \
					((uint64_t)std::rand() & 0xf) << 60 )

What do you mean with unsafe optimizations?

I will try to implement some sort of divided search to check for discrepancies.

well, hgm is right, std::rand is actually just a glorified wrapper for rand and doesn't come from <random> but <cstdlib>
and rand implementation differs between microsoft CRT and glibc, this is the source of your non-determinism

[hgm]

'Unsafe optimizations' are optimizations that makes some assumptions about independence of variables, in particular pointers. E.g. when I have the code

for(i=0; i<100000; i++) *p++ = *a + 1;

it would give a speedup to fetch *a from memory only once, and store it in a register and increment it there, before the loop. From which you would then move it to all different memory locations indicated by p. But this fails if a points into the range visited by p. E.g. if a and p would have been equal before the loop, the entire range except the first one should have been filled with *a + 2, instead of *a + 1.

[niel5946]

Yes, I am using the C++ <random> library and the following preprocessor macro:

Code: Select all

#define RAND_64     ((uint64_t)std::rand() | \
					(uint64_t)std::rand() << 15 | \
					(uint64_t)std::rand() << 30 | \
					(uint64_t)std::rand() << 45 | \
					((uint64_t)std::rand() & 0xf) << 60 )

What do you mean with unsafe optimizations?

I will try to implement some sort of divided search to check for discrepancies.

well, hgm is right, std::rand is actually just a glorified wrapper for rand and doesn't come from <random> but <cstdlib>
and rand implementation differs between microsoft CRT and glibc, this is the source of your non-determinism

Alright, I see... How would one go about creating a non-deterministic PRNG? I suppose there aren't any ready-to-use libraries

[mar]

Alright, I see... How would one go about creating a non-deterministic PRNG? I suppose there aren't any ready-to-use libraries

you mean deterministic. well, you already mentioned <random>

so you can do

Code: Select all

#include <random>

void init_zobrist()
{
    // use deterministic seed, any 64-bit constant should do
    std::mt19937_64 rng( 0x1234 );

.
.
.

    // and use it later
    for (...)
        next_zobrist_key = rng();
}

[mar]

I see now that your problem is actually a non-determinism between debug and release build - might be some uninitialized variables?

I've also noticed that you use masking when probing TT, but I don't see where you round numEntries to a power of two; while it still works for your default TT size, it might not for arbitrary TT sizes;
still even this doesn't explain the problems you're facing.

[mvanthoor]

well, hgm is right, std::rand is actually just a glorified wrapper for rand and doesn't come from <random> but <cstdlib>
and rand implementation differs between microsoft CRT and glibc, this is the source of your non-determinism

Hm. I don't understand... even if there are two different lists of Zobrist Keys, the program should still work?

A week or two ago, the "rand" library in Rust got updated, and the PRNG I use had a tiny api-change to seed it differently. I now get different random numbers for my Zobrist hash, but the transposition table for Perft still works. On Linux other OS's the PRNG -can- give different numbers than it does on Windows, but it doesn't seem to affect the engine.

[mar]

Hm. I don't understand... even if there are two different lists of Zobrist Keys, the program should still work?

A week or two ago, the "rand" library in Rust got updated, and the PRNG I use had a tiny api-change to seed it differently. I now get different random numbers for my Zobrist hash, but the transposition table for Perft still works. On Linux other OS's the PRNG -can- give different numbers than it does on Windows, but it doesn't seem to affect the engine.

yes it will, but you certainly want a deterministic seed/generator for your zobrist keys that generate the same keys on all platforms - because you want your singlethreaded search to depth n in position x produce the same tree and node count (perft doesn't suffer from this, of course) - and unless you use say polyglot keys to probe a polyglot book but instead use your own book format with your own keys, then your book probing code would break as well which isn't what you want either.

the problem here is that I didn't read the original post thoroughly, well nevermind - one problem at a time and I'm sure the OP will eventually find and fix the problem