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
No TT hits with optimizations
Moderators: hgm, Rebel, chrisw
-
- Posts: 174
- Joined: Thu Nov 26, 2020 10:06 am
- Full name: Niels Abildskov
-
- Posts: 27817
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: No TT hits with optimizations
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.
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.
-
- Posts: 174
- Joined: Thu Nov 26, 2020 10:06 am
- Full name: Niels Abildskov
Re: No TT hits with optimizations
Yes, I am using the C++ <random> library and the following preprocessor macro:hgm wrote: ↑Tue Feb 23, 2021 11:07 am 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.
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 )
I will try to implement some sort of divided search to check for discrepancies.
-
- Posts: 2559
- Joined: Fri Nov 26, 2010 2:00 pm
- Location: Czech Republic
- Full name: Martin Sedlak
Re: No TT hits with optimizations
well, hgm is right, std::rand is actually just a glorified wrapper for rand and doesn't come from <random> but <cstdlib>niel5946 wrote: ↑Tue Feb 23, 2021 12:29 pm Yes, I am using the C++ <random> library and the following preprocessor macro:What do you mean with unsafe optimizations?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 )
I will try to implement some sort of divided search to check for discrepancies.
and rand implementation differs between microsoft CRT and glibc, this is the source of your non-determinism
Martin Sedlak
-
- Posts: 27817
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: No TT hits with optimizations
'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.
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.
-
- Posts: 174
- Joined: Thu Nov 26, 2020 10:06 am
- Full name: Niels Abildskov
Re: No TT hits with optimizations
Alright, I see... How would one go about creating a non-deterministic PRNG? I suppose there aren't any ready-to-use librariesmar wrote: ↑Tue Feb 23, 2021 12:48 pmwell, hgm is right, std::rand is actually just a glorified wrapper for rand and doesn't come from <random> but <cstdlib>niel5946 wrote: ↑Tue Feb 23, 2021 12:29 pm Yes, I am using the C++ <random> library and the following preprocessor macro:What do you mean with unsafe optimizations?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 )
I will try to implement some sort of divided search to check for discrepancies.
and rand implementation differs between microsoft CRT and glibc, this is the source of your non-determinism
-
- Posts: 2559
- Joined: Fri Nov 26, 2010 2:00 pm
- Location: Czech Republic
- Full name: Martin Sedlak
Re: No TT hits with optimizations
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();
}
Martin Sedlak
-
- Posts: 2559
- Joined: Fri Nov 26, 2010 2:00 pm
- Location: Czech Republic
- Full name: Martin Sedlak
Re: No TT hits with optimizations
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.
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.
Martin Sedlak
-
- Posts: 1784
- Joined: Wed Jul 03, 2019 4:42 pm
- Location: Netherlands
- Full name: Marcel Vanthoor
Re: No TT hits with optimizations
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.
-
- Posts: 2559
- Joined: Fri Nov 26, 2010 2:00 pm
- Location: Czech Republic
- Full name: Martin Sedlak
Re: No TT hits with optimizations
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.mvanthoor wrote: ↑Tue Feb 23, 2021 2:28 pm 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.
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
Martin Sedlak