Computing hash "on the fly"

[AndrewGrant]

I HIGHLY doubt that you are out performing Zorbist. Meaning one of a couple things...

1) Your Zorbist implementation is poor
2) Your testing scheme is bad. Changing the hash signatures changes how your table affects your search. To measure the performance of your Hashing method you need to disable to table


IF we assume your test scheme is valid (it's not)
...based on your KNPS 'results'. If we assume your on-the-fly method takes ZERO time, then we could determine your normal hashing takes 8% of your running time. 8% seems way too high. A profile of my run time for apply move (which updates the hash) is less than 4% of run time. The component for updating the hash is probably ~1% of run time.

[Dann Corbit]

Is your zobrist hash updated incrementally?
IOW, if you move a single chessman do you only update the hash elements that are directly affected by the move?

[stegemma]

I HIGHLY doubt that you are out performing Zorbist. Meaning one of a couple things...

1) Your Zorbist implementation is poor
2) Your testing scheme is bad. Changing the hash signatures changes how your table affects your search. To measure the performance of your Hashing method you need to disable to table


IF we assume your test scheme is valid (it's not)
...based on your KNPS 'results'. If we assume your on-the-fly method takes ZERO time, then we could determine your normal hashing takes 8% of your running time. 8% seems way too high. A profile of my run time for apply move (which updates the hash) is less than 4% of run time. The component for updating the hash is probably ~1% of run time.

This method has the same nps as the standard Zobrist key in my engine. This could be do to the good optimizations done by the compiler; if you look at the assembly generated, you can see that there are a series of simple instructions that can be pipelined by the CPU. As you say, the whole hashing algorithm takes a little % of the time, so the overall speed would not be affected even if you use a poor (but valid) hashing computation.

In all of my engines I always search for original method to do almost anything and I share my ideas even when strange or worse. Hyatt say that this method never works but it seems that this way it is a valid method, it seems to works but it should be verified with more test. If it works, it saves me from using a Zobrist keys array. I've done the same for KBN vs K final: I don't use tablebases but a variant in the Evaluate.

Maybe avoiding large arrays is derived from my first computer experience with the 1K ZX 81...

[AndrewGrant]

Your original post claimed to make nps gains. If that is not the case, was is your objective in using a different hashing method?

[stegemma]

Is your zobrist hash updated incrementally?
IOW, if you move a single chessman do you only update the hash elements that are directly affected by the move?

Yes. I have a "#define DEBUG_TT 1" to verify the hash, saving the FEN in any TT entry and comparing with the matched new positions, so I already know that my standard Zobrist hashing implementation doesn't generates false positive (no more than expected). The new one does the same.

Of course my problem is in the TT algorithm, not in the hashing method itself.

This new method (if tested and proved ok) could be used to simplify hashing of books, for sample, not just in searching. Starting from a FEN (instead of a whole game) , this method could be simpler and faster than extracting any single piece bit from a bitboard to obtain an index or iterating through an array of pieces.

[stegemma]

Your original post claimed to make nps gains. If that is not the case, was is your objective in using a different hashing method?

Yes, the first attempt was faster but the method used was not valid (it generates a lot of false hits). The method with modified Marsaglia random generator is almost equal to standard Zobrist, if I compare nps only.

Why to use old or new method if I get the same nps? Why not?

In systems with limited memory or with no fast multiplication, the new method could be better. Using less memory could be better even in modern CPUs, because you have lesser memory pressure on cache.

Another possible use would be (if it can apply) when you have to use a TT for some limited parameters in evaluation function. For sample, if you want a TT for pawns and kings, for kings safety. Updating the hash any move until the last ply when you need it only at leaves could give you a reason to use this new method or some derivation from it.

Of course I'm still experimenting...

[jwes]

Maybe avoiding large arrays is derived from my first computer experience with the 1K ZX 81...

You could try this:

Code: Select all

unsigned __int64 zobp[13];
zhash[ply + 1] = zhash[ply].zhash
^ _rotl64(zobp[piece + 6], from) ^ _rotl64(zobp[piece + 6], to);

[AlvaroBegue]

Code: Select all

            HH(boKings);
            HH(boQueens);
            HH(boRooks);
            HH(boBishops);
            HH(boKnights);
            HH(boPawns);

That can probably just be substituted with something like this:

Code: Select all

            HH(boKings|boRooks|boKnights);
            HH(boQueens|boRooks);
            HH(boBishops|boKnights);

This should be faster. It is making use of the fact that a square will only contain one type of piece, so you can assign each piece a 3-bit code and compute a hash of that more compact representation.

[stegemma]

Code: Select all

            HH(boKings);
            HH(boQueens);
            HH(boRooks);
            HH(boBishops);
            HH(boKnights);
            HH(boPawns);

That can probably just be substituted with something like this:

Code: Select all

            HH(boKings|boRooks|boKnights);
            HH(boQueens|boRooks);
            HH(boBishops|boKnights);

This should be faster. It is making use of the fact that a square will only contain one type of piece, so you can assign each piece a 3-bit code and compute a hash of that more compact representation.

I've try something similar but it lose correctness of the hash (some wrong hits appears). You idea is interesting, I'll try and let you know.

[stegemma]

Maybe avoiding large arrays is derived from my first computer experience with the 1K ZX 81...

You could try this:

Code: Select all

unsigned __int64 zobp[13];
zhash[ply + 1] = zhash[ply].zhash
^ _rotl64(zobp[piece + 6], from) ^ _rotl64(zobp[piece + 6], to);

This idea is an evolution of this old thread:

http://www.talkchess.com/forum/viewtopic.php?t=30008

Modern CPU can do rotates of 64 bit values faster than in the past, so old ideas can come to live.