ChessUSA.com TalkChess.com
Hosted by Your Move Chess & Games
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

Zobrist alternative?
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions Flat
View previous topic :: View next topic  
Author Message
Don Dailey



Joined: 29 Apr 2008
Posts: 4502
PostPost subject: Re: Zobrist alternative?    Posted: Fri Jun 15, 2012 10:59 pm Reply to topic Reply with quote
Daniel Shawul wrote:
Quote:

The same number? Maybe that is why it's called a constant? I don't understand your point, but this is the famous Fowler/Noll/Vo hash which has been found to work very well. Essentially we are applying the FNV hash to the tuple (color, type, square.) There are actually two constants, the first is called the offset basis and is claimed to not be important, just to provide a consistent way to start this off. FNV is called the FNV prime. It is a magic constant that has certain properties that are considered important for this particular hash.

No I clearly understand what you are trying to do. There is the cp (color/piece) and (square) indexes. You had FNV hash xored first then multiplied with FNV but this is not how FNV hash works. It should be reversed which I thought was a typo. But I am not sure anymore since you say now it should be xor first. Anyway you are using the FNV hash twice to get a single key. The fact that the two steps are mixed make it a bit different but basically it will suffer from the problems I mentioned.


The issue with the 2 constants would be optimized away by any compiler and it was just a sloppy translation on my part. There are however 2 constants but one is just used for initialization and is not particularly important.

There are at least two versions of this hash and the one considered superior does the xor first, that is called (I think) FNV-1a if I remember correctly and the one that should be used for this.

Here is my suggested usage:

h = 19282138887198ull;
h = h ^ color_piece;
h = h * FNV_CONSTANT;
h = h ^ square_number;
h = h * FNV_CONSTANT;

This will come out differently for every piece on every square. The only way this varies from proper FNV-1a is that normally you look at 8 bits of key at a time - that is what is xor'd - so to do this the proper FNV way HG might wish to do an extra xor and multiply (if his key is as much as 24 bits.) But I believe this would work just fine.

There is a chance it wouldn't so it would need to be checked out but the hash itself is consider to be reasonable sound for general hashing.
_________________
The Optimist thinks this is the best of all possible worlds, the Pessimist fears it is true.
Back to top
View user's profile Send private message Send e-mail
Display posts from previous:   
Subject Author Date/Time
Zobrist alternative? H.G.Muller Tue Jun 12, 2012 7:35 pm
      Re: Zobrist alternative? Kevin Hearn Tue Jun 12, 2012 7:44 pm
      Re: Zobrist alternative? Daniel Shawul Tue Jun 12, 2012 8:19 pm
            Re: Zobrist alternative? H.G.Muller Tue Jun 12, 2012 8:54 pm
                  Re: Zobrist alternative? Daniel Shawul Tue Jun 12, 2012 9:46 pm
                        Re: Zobrist alternative? Daniel Shawul Wed Jun 13, 2012 3:24 am
                        Re: Zobrist alternative? Daniel Shawul Wed Jun 13, 2012 4:14 am
                              ignored idea here Daniel Shawul Wed Jun 13, 2012 4:00 pm
                                    Re: ignored idea here Daniel Shawul Thu Jun 14, 2012 1:30 am
                                          Re: ignored idea here H.G.Muller Thu Jun 14, 2012 5:50 am
                                                Re: ignored idea here Daniel Shawul Thu Jun 14, 2012 12:52 pm
                                          Re: ignored idea here Edmund Moshammer Thu Jun 14, 2012 8:21 am
                                                Re: ignored idea here Edmund Moshammer Thu Jun 14, 2012 9:27 am
      Re: Zobrist alternative? Wylie Garvin Tue Jun 12, 2012 8:27 pm
            Re: Zobrist alternative? H.G.Muller Tue Jun 12, 2012 8:36 pm
                  Re: Zobrist alternative? Vincent Diepeveen Wed Jun 13, 2012 1:01 pm
                  Re: Zobrist alternative? Wylie Garvin Wed Jun 13, 2012 10:57 pm
                        Re: Zobrist alternative? H.G.Muller Thu Jun 14, 2012 5:42 am
                              Re: Zobrist alternative? Robert Hyatt Thu Jun 14, 2012 1:17 pm
                                    Re: Zobrist alternative? H.G.Muller Thu Jun 14, 2012 2:17 pm
                                          Re: Zobrist alternative? Wylie Garvin Thu Jun 14, 2012 6:11 pm
                        Re: Zobrist alternative? Vincent Diepeveen Sat Jun 16, 2012 10:05 am
      Re: Zobrist alternative? Reinhard Scharnagl Wed Jun 13, 2012 9:52 am
            Re: Zobrist alternative? Edmund Moshammer Wed Jun 13, 2012 9:58 am
                  Re: Zobrist alternative? Reinhard Scharnagl Wed Jun 13, 2012 12:49 pm
                        Re: Zobrist alternative? Edmund Moshammer Wed Jun 13, 2012 1:15 pm
                              Re: Zobrist alternative? Reinhard Scharnagl Wed Jun 13, 2012 1:41 pm
                                    Re: Zobrist alternative? Edmund Moshammer Wed Jun 13, 2012 3:55 pm
                                          Re: Zobrist alternative? Reinhard Scharnagl Wed Jun 13, 2012 4:03 pm
      Re: Zobrist alternative? H.G.Muller Wed Jun 13, 2012 2:19 pm
            Re: Zobrist alternative? Vincent Diepeveen Wed Jun 13, 2012 2:44 pm
            Re: Zobrist alternative? Vincent Diepeveen Wed Jun 13, 2012 2:48 pm
                  Re: Zobrist alternative? Vincent Diepeveen Wed Jun 13, 2012 3:28 pm
                  Re: Zobrist alternative? H.G.Muller Wed Jun 13, 2012 4:01 pm
                        Re: Zobrist alternative? Vincent Diepeveen Wed Jun 13, 2012 5:42 pm
                              Re: Zobrist alternative? H.G.Muller Wed Jun 13, 2012 5:51 pm
                        Re: Zobrist alternative? Vincent Diepeveen Wed Jun 13, 2012 6:27 pm
            Re: Zobrist alternative? Daniel Shawul Wed Jun 13, 2012 5:29 pm
            Re: Zobrist alternative? Karlo Bala Jr. Thu Jun 14, 2012 9:50 am
      Re: Zobrist alternative? Reinhard Scharnagl Thu Jun 14, 2012 8:49 am
            Re: Zobrist alternative? H.G.Muller Thu Jun 14, 2012 9:09 am
            Re: Zobrist alternative? Daniel Shawul Thu Jun 14, 2012 1:11 pm
                  Re: Zobrist alternative? Vincent Diepeveen Sat Jun 16, 2012 10:12 am
      Re: Zobrist alternative? Don Dailey Thu Jun 14, 2012 4:46 pm
            Re: Zobrist alternative? Don Dailey Thu Jun 14, 2012 6:38 pm
                  Re: Zobrist alternative? Daniel Shawul Thu Jun 14, 2012 6:57 pm
                        Re: Zobrist alternative? Don Dailey Fri Jun 15, 2012 2:39 pm
                              Re: Zobrist alternative? H.G.Muller Fri Jun 15, 2012 3:46 pm
                                    Re: Zobrist alternative? Daniel Shawul Fri Jun 15, 2012 5:22 pm
                                          Re: Zobrist alternative? H.G.Muller Fri Jun 15, 2012 5:38 pm
                                                Re: Zobrist alternative? Vincent Diepeveen Sat Jun 16, 2012 10:17 am
                              Re: Zobrist alternative? Daniel Shawul Fri Jun 15, 2012 5:04 pm
                                    Re: Zobrist alternative? Don Dailey Fri Jun 15, 2012 6:00 pm
                                          Re: Zobrist alternative? Daniel Shawul Fri Jun 15, 2012 7:27 pm
                                                Re: Zobrist alternative? Don Dailey Fri Jun 15, 2012 8:16 pm
                                                      Re: Zobrist alternative? Daniel Shawul Fri Jun 15, 2012 8:42 pm
                                                      Re: Zobrist alternative? Daniel Shawul Fri Jun 15, 2012 9:14 pm
                                                            Re: Zobrist alternative? Don Dailey Fri Jun 15, 2012 10:59 pm
                                                                  Re: Zobrist alternative? Daniel Shawul Sat Jun 16, 2012 12:17 am
                                                                        Re: Zobrist alternative? Don Dailey Sat Jun 16, 2012 4:28 am
                                                                              Re: Zobrist alternative? Daniel Shawul Sat Jun 16, 2012 6:30 am
                                                                                    Re: Zobrist alternative? Daniel Shawul Sat Jun 16, 2012 10:09 am
                                                                                          Re: Zobrist alternative? Vincent Diepeveen Sat Jun 16, 2012 10:22 am
                                                                                          Re: Zobrist alternative? Vincent Diepeveen Sat Jun 16, 2012 10:42 am
                                                                                          Re: Zobrist alternative? Vincent Diepeveen Sat Jun 16, 2012 10:54 am
                                                                                          Re: Zobrist alternative? Daniel Shawul Sat Jun 16, 2012 11:03 am
                                                                                          Re: Zobrist alternative? Vincent Diepeveen Sat Jun 16, 2012 11:08 am
                                                                                          Re: Zobrist alternative? Don Dailey Sat Jun 16, 2012 12:03 pm
                                                                                          Re: Zobrist alternative? Vincent Diepeveen Sat Jun 16, 2012 12:55 pm
                                                                                          Re: Zobrist alternative? Vincent Diepeveen Sat Jun 16, 2012 2:21 pm
                                                                                          Re: Zobrist alternative? Daniel Shawul Sat Jun 16, 2012 2:25 pm
                                                                                          Re: Zobrist alternative? Vincent Diepeveen Sat Jun 16, 2012 2:44 pm
                                                                                          Re: Zobrist alternative? Daniel Shawul Sat Jun 16, 2012 12:35 pm
                                                                                          Re: Zobrist alternative? Vincent Diepeveen Sat Jun 16, 2012 1:11 pm
                                                                                          Re: Zobrist alternative? Vincent Diepeveen Sat Jun 16, 2012 1:15 pm
                                                                                          Re: Zobrist alternative? Vincent Diepeveen Sat Jun 16, 2012 1:56 pm
                                                                                          Re: Zobrist alternative? Daniel Shawul Sat Jun 16, 2012 2:05 pm
                                                                                          Re: Zobrist alternative? Vincent Diepeveen Sat Jun 16, 2012 2:10 pm
                                                                                          Re: Zobrist alternative? Daniel Shawul Sat Jun 16, 2012 2:22 pm
                                                                                          Re: Zobrist alternative? Vincent Diepeveen Sat Jun 16, 2012 2:29 pm
                                                                                          Re: Zobrist alternative? Daniel Shawul Sat Jun 16, 2012 2:35 pm
                                                                                          Re: Zobrist alternative? Vincent Diepeveen Sat Jun 16, 2012 2:39 pm
                                                                                          Re: Zobrist alternative? Don Dailey Sat Jun 16, 2012 3:49 pm
                                                                                          Re: Zobrist alternative? Daniel Shawul Sat Jun 16, 2012 4:35 pm
                                                                                          Re: Zobrist alternative? Daniel Shawul Sat Jun 16, 2012 2:11 pm
                                                                                          Re: Zobrist alternative? Vincent Diepeveen Sat Jun 16, 2012 2:13 pm
                                                                                          Re: Zobrist alternative? Vincent Diepeveen Sat Jun 16, 2012 2:19 pm
                                                                                          Re: Zobrist alternative? Daniel Shawul Sat Jun 16, 2012 2:29 pm
                                                                                          Re: Zobrist alternative? Vincent Diepeveen Sat Jun 16, 2012 2:32 pm
                                                                                          Re: Zobrist alternative? Daniel Shawul Sat Jun 16, 2012 4:19 pm
                                                                                          Re: Zobrist alternative? Don Dailey Sat Jun 16, 2012 4:50 pm
                                                                                          Re: Zobrist alternative? Daniel Shawul Sat Jun 16, 2012 4:25 pm
                                                Re: Zobrist alternative? Don Dailey Fri Jun 15, 2012 8:21 pm
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum




Powered by phpBB © 2001, 2005 phpBB Group
Enhanced with Moby Threads