No TT hits with optimizations

Discussion of chess software programming and technical issues.

Moderators: hgm, Dann Corbit, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
niel5946
Posts: 40
Joined: Thu Nov 26, 2020 9:06 am
Full name: Niels Abildskov

No TT hits with optimizations

Post by niel5946 » Tue Feb 23, 2021 9:12 am

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 :D

User avatar
hgm
Posts: 25946
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: No TT hits with optimizations

Post by hgm » Tue Feb 23, 2021 10: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.

niel5946
Posts: 40
Joined: Thu Nov 26, 2020 9:06 am
Full name: Niels Abildskov

Re: No TT hits with optimizations

Post by niel5946 » Tue Feb 23, 2021 11:29 am

hgm wrote:
Tue Feb 23, 2021 10: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.
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
Posts: 2325
Joined: Fri Nov 26, 2010 1:00 pm
Location: Czech Republic
Full name: Martin Sedlak

Re: No TT hits with optimizations

Post by mar » Tue Feb 23, 2021 11:48 am

niel5946 wrote:
Tue Feb 23, 2021 11:29 am
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
Martin Sedlak

User avatar
hgm
Posts: 25946
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: No TT hits with optimizations

Post by hgm » Tue Feb 23, 2021 11:54 am

'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
Posts: 40
Joined: Thu Nov 26, 2020 9:06 am
Full name: Niels Abildskov

Re: No TT hits with optimizations

Post by niel5946 » Tue Feb 23, 2021 12:05 pm

mar wrote:
Tue Feb 23, 2021 11:48 am
niel5946 wrote:
Tue Feb 23, 2021 11:29 am
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
Posts: 2325
Joined: Fri Nov 26, 2010 1:00 pm
Location: Czech Republic
Full name: Martin Sedlak

Re: No TT hits with optimizations

Post by mar » Tue Feb 23, 2021 12:25 pm

niel5946 wrote:
Tue Feb 23, 2021 12:05 pm
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();
}
Martin Sedlak

mar
Posts: 2325
Joined: Fri Nov 26, 2010 1:00 pm
Location: Czech Republic
Full name: Martin Sedlak

Re: No TT hits with optimizations

Post by mar » Tue Feb 23, 2021 12:56 pm

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.
Martin Sedlak

User avatar
mvanthoor
Posts: 824
Joined: Wed Jul 03, 2019 2:42 pm
Full name: Marcel Vanthoor

Re: No TT hits with optimizations

Post by mvanthoor » Tue Feb 23, 2021 1:28 pm

mar wrote:
Tue Feb 23, 2021 11:48 am
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.
Author of Rustic.
Releases | Code | Docs

mar
Posts: 2325
Joined: Fri Nov 26, 2010 1:00 pm
Location: Czech Republic
Full name: Martin Sedlak

Re: No TT hits with optimizations

Post by mar » Tue Feb 23, 2021 1:37 pm

mvanthoor wrote:
Tue Feb 23, 2021 1: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.
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
Martin Sedlak

Post Reply