Computing hash "on the fly"

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
AndrewGrant
Posts: 583
Joined: Tue Apr 19, 2016 4:08 am
Location: U.S.A
Full name: Andrew Grant
Contact:

Re: Computing hash "on the fly"

Post by AndrewGrant » Fri Jun 03, 2016 1:02 am

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
Posts: 11160
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: Computing hash "on the fly"

Post by Dann Corbit » Fri Jun 03, 2016 1:47 am

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?
Taking ideas is not a vice, it is a virtue. We have another word for this. It is called learning.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.

User avatar
stegemma
Posts: 859
Joined: Mon Aug 10, 2009 8:05 pm
Location: Italy
Full name: Stefano Gemma
Contact:

Re: Computing hash "on the fly"

Post by stegemma » Fri Jun 03, 2016 6:38 am

AndrewGrant wrote: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... ;)
Author of Drago, Raffaela, Freccia, Satana, Sabrina.
http://www.linformatica.com

AndrewGrant
Posts: 583
Joined: Tue Apr 19, 2016 4:08 am
Location: U.S.A
Full name: Andrew Grant
Contact:

Re: Computing hash "on the fly"

Post by AndrewGrant » Fri Jun 03, 2016 6:41 am

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

User avatar
stegemma
Posts: 859
Joined: Mon Aug 10, 2009 8:05 pm
Location: Italy
Full name: Stefano Gemma
Contact:

Re: Computing hash "on the fly"

Post by stegemma » Fri Jun 03, 2016 6:49 am

Dann Corbit wrote: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.
Author of Drago, Raffaela, Freccia, Satana, Sabrina.
http://www.linformatica.com

User avatar
stegemma
Posts: 859
Joined: Mon Aug 10, 2009 8:05 pm
Location: Italy
Full name: Stefano Gemma
Contact:

Re: Computing hash "on the fly"

Post by stegemma » Fri Jun 03, 2016 9:32 am

AndrewGrant wrote: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...
Author of Drago, Raffaela, Freccia, Satana, Sabrina.
http://www.linformatica.com

jwes
Posts: 778
Joined: Sat Jul 01, 2006 5:11 am

Re: Computing hash "on the fly"

Post by jwes » Fri Jun 03, 2016 1:59 pm

stegemma wrote: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
Posts: 925
Joined: Tue Mar 09, 2010 2:46 pm
Location: New York
Full name: Álvaro Begué (RuyDos)

Re: Computing hash "on the fly"

Post by AlvaroBegue » Fri Jun 03, 2016 6:53 pm

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.

User avatar
stegemma
Posts: 859
Joined: Mon Aug 10, 2009 8:05 pm
Location: Italy
Full name: Stefano Gemma
Contact:

Re: Computing hash "on the fly"

Post by stegemma » Fri Jun 03, 2016 7:28 pm

AlvaroBegue wrote:

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.
Author of Drago, Raffaela, Freccia, Satana, Sabrina.
http://www.linformatica.com

User avatar
stegemma
Posts: 859
Joined: Mon Aug 10, 2009 8:05 pm
Location: Italy
Full name: Stefano Gemma
Contact:

Re: Computing hash "on the fly"

Post by stegemma » Fri Jun 03, 2016 7:33 pm

jwes wrote:
stegemma wrote: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.
Author of Drago, Raffaela, Freccia, Satana, Sabrina.
http://www.linformatica.com

Post Reply