TalkChess.com
Hosted by Your Move Chess & Games

Author Message
Don Dailey

Joined: 29 Apr 2008
Posts: 4318

Post subject: Re: Zobrist alternative?    Posted: Fri Jun 15, 2012 8:16 pm

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
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
Subject Author Date/Time
H.G.Muller Tue Jun 12, 2012 7:35 pm
Kevin Hearn Tue Jun 12, 2012 7:44 pm
Daniel Shawul Tue Jun 12, 2012 8:19 pm
H.G.Muller Tue Jun 12, 2012 8:54 pm
Daniel Shawul Tue Jun 12, 2012 9:46 pm
Daniel Shawul Wed Jun 13, 2012 3:24 am
Daniel Shawul Wed Jun 13, 2012 4:14 am
Daniel Shawul Wed Jun 13, 2012 4:00 pm
Daniel Shawul Thu Jun 14, 2012 1:30 am
H.G.Muller Thu Jun 14, 2012 5:50 am
Daniel Shawul Thu Jun 14, 2012 12:52 pm
Edmund Moshammer Thu Jun 14, 2012 8:21 am
Edmund Moshammer Thu Jun 14, 2012 9:27 am
Wylie Garvin Tue Jun 12, 2012 8:27 pm
H.G.Muller Tue Jun 12, 2012 8:36 pm
Vincent Diepeveen Wed Jun 13, 2012 1:01 pm
Wylie Garvin Wed Jun 13, 2012 10:57 pm
H.G.Muller Thu Jun 14, 2012 5:42 am
Robert Hyatt Thu Jun 14, 2012 1:17 pm
H.G.Muller Thu Jun 14, 2012 2:17 pm
Wylie Garvin Thu Jun 14, 2012 6:11 pm
Vincent Diepeveen Sat Jun 16, 2012 10:05 am
Reinhard Scharnagl Wed Jun 13, 2012 9:52 am
Edmund Moshammer Wed Jun 13, 2012 9:58 am
Reinhard Scharnagl Wed Jun 13, 2012 12:49 pm
Edmund Moshammer Wed Jun 13, 2012 1:15 pm
Reinhard Scharnagl Wed Jun 13, 2012 1:41 pm
Edmund Moshammer Wed Jun 13, 2012 3:55 pm
Reinhard Scharnagl Wed Jun 13, 2012 4:03 pm
H.G.Muller Wed Jun 13, 2012 2:19 pm
Vincent Diepeveen Wed Jun 13, 2012 2:44 pm
Vincent Diepeveen Wed Jun 13, 2012 2:48 pm
Vincent Diepeveen Wed Jun 13, 2012 3:28 pm
H.G.Muller Wed Jun 13, 2012 4:01 pm
Vincent Diepeveen Wed Jun 13, 2012 5:42 pm
H.G.Muller Wed Jun 13, 2012 5:51 pm
Vincent Diepeveen Wed Jun 13, 2012 6:27 pm
Daniel Shawul Wed Jun 13, 2012 5:29 pm
Karlo Bala Jr. Thu Jun 14, 2012 9:50 am
Reinhard Scharnagl Thu Jun 14, 2012 8:49 am
H.G.Muller Thu Jun 14, 2012 9:09 am
Daniel Shawul Thu Jun 14, 2012 1:11 pm
Vincent Diepeveen Sat Jun 16, 2012 10:12 am
Don Dailey Thu Jun 14, 2012 4:46 pm
Don Dailey Thu Jun 14, 2012 6:38 pm
Daniel Shawul Thu Jun 14, 2012 6:57 pm
Don Dailey Fri Jun 15, 2012 2:39 pm
H.G.Muller Fri Jun 15, 2012 3:46 pm
Daniel Shawul Fri Jun 15, 2012 5:22 pm
H.G.Muller Fri Jun 15, 2012 5:38 pm
Vincent Diepeveen Sat Jun 16, 2012 10:17 am
Daniel Shawul Fri Jun 15, 2012 5:04 pm
Don Dailey Fri Jun 15, 2012 6:00 pm
Daniel Shawul Fri Jun 15, 2012 7:27 pm
Re: Zobrist alternative? Don Dailey Fri Jun 15, 2012 8:16 pm
Daniel Shawul Fri Jun 15, 2012 8:42 pm
Daniel Shawul Fri Jun 15, 2012 9:14 pm
Don Dailey Fri Jun 15, 2012 10:59 pm
Daniel Shawul Sat Jun 16, 2012 12:17 am
Don Dailey Sat Jun 16, 2012 4:28 am
Daniel Shawul Sat Jun 16, 2012 6:30 am
Daniel Shawul Sat Jun 16, 2012 10:09 am
Vincent Diepeveen Sat Jun 16, 2012 10:22 am
Vincent Diepeveen Sat Jun 16, 2012 10:42 am
Vincent Diepeveen Sat Jun 16, 2012 10:54 am
Daniel Shawul Sat Jun 16, 2012 11:03 am
Vincent Diepeveen Sat Jun 16, 2012 11:08 am
Don Dailey Sat Jun 16, 2012 12:03 pm
Vincent Diepeveen Sat Jun 16, 2012 12:55 pm
Vincent Diepeveen Sat Jun 16, 2012 2:21 pm
Daniel Shawul Sat Jun 16, 2012 2:25 pm
Vincent Diepeveen Sat Jun 16, 2012 2:44 pm
Daniel Shawul Sat Jun 16, 2012 12:35 pm
Vincent Diepeveen Sat Jun 16, 2012 1:11 pm
Vincent Diepeveen Sat Jun 16, 2012 1:15 pm
Vincent Diepeveen Sat Jun 16, 2012 1:56 pm
Daniel Shawul Sat Jun 16, 2012 2:05 pm
Vincent Diepeveen Sat Jun 16, 2012 2:10 pm
Daniel Shawul Sat Jun 16, 2012 2:22 pm
Vincent Diepeveen Sat Jun 16, 2012 2:29 pm
Daniel Shawul Sat Jun 16, 2012 2:35 pm
Vincent Diepeveen Sat Jun 16, 2012 2:39 pm
Don Dailey Sat Jun 16, 2012 3:49 pm
Daniel Shawul Sat Jun 16, 2012 4:35 pm
Daniel Shawul Sat Jun 16, 2012 2:11 pm
Vincent Diepeveen Sat Jun 16, 2012 2:13 pm
Vincent Diepeveen Sat Jun 16, 2012 2:19 pm
Daniel Shawul Sat Jun 16, 2012 2:29 pm
Vincent Diepeveen Sat Jun 16, 2012 2:32 pm
Daniel Shawul Sat Jun 16, 2012 4:19 pm
Don Dailey Sat Jun 16, 2012 4:50 pm
Daniel Shawul Sat Jun 16, 2012 4:25 pm
Don Dailey Fri Jun 15, 2012 8:21 pm

 Jump to: Select a forum Computer Chess Club Forums----------------Computer Chess Club: General TopicsComputer Chess Club: Tournaments and MatchesComputer Chess Club: Programming and Technical DiscussionsComputer Chess Club: Engine Origins Other Forums----------------Chess Thinkers ForumForum Help and Suggestions
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