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: 4318
PostPost subject: Re: Zobrist alternative?    Posted: Fri Jun 15, 2012 8:16 pm Reply to topic Reply with quote
Daniel Shawul wrote:
Quote:

hash = any_number;
hash = hash ^ cp;
hash = hash * FNV;
hash = hash ^ square;
hash = hash * FNV;

Well hash = ( any_number * FNV ) ^ sq only changes the lowest bits


Yes, this is how it works. In fact it's supposed to just be 8 bits that change. Multiplying it by the cleverly chosen large constant does the mixing.

Quote:

since it uses the _same_ number to initialize all squares.


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.

Quote:

It is similar to an sequentially executed LCG but poorer because in the latter case any_number is replaced by the previously generated random number. So what this method does is basically using sq as the hashkey. Note that the hash function is called every time the key for the piece on square is required, and it has to return the same key every time. So unless you store different initialization numbers (seeds) for each square (which again means storing it in a table), this can't work.

This is a sound hash - you are probably misunderstanding something. Did you notice that first the color/piece is xored, then multiplied then this is combined with the square number? There is nothing improper about that. I suspect that you did not understand "cp" in my little code example - but what this does will be to create a unique key for any color/piece/square combination. If you want I will compute this for chess and prove it to you. Or I will make up a test with 1000 piece types and 1000 squares and check to see if any match. They won't. Of course to be really sure one would would need to run a test of random numbers on the keys generated. I don't know if it would pass all the tests a true random generator would but that does not necessarily mean it won't be good for this. It's more important that keys are nicely distributed in the domain in which they are used, not that they pass random number tests.

Quote:

Quote:

I'm not explicitly mixing here but this will be pretty fast and avoid a lot of source code clutter with tables of random numbers.

The table could be generated at run time from a given seed so there is no need to store them in the source code. If same random numbers are required as in the case where the keys are used for book too, then the seed can be fixed. Also mixing will add a lot of code that is done twice..

_________________
"Your superior intellect is no match for our puny weapons." -Kang and Kodos
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