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
Daniel Shawul



Joined: 14 Mar 2006
Posts: 2283
Location: Ethiopia
PostPost subject: Re: Zobrist alternative?    Posted: Sat Jun 16, 2012 12:17 am Reply to topic Reply with quote
Well the sample code you gave does the multiply first i.e FNV-1 not FNV-1a.
Code:

for (i=0; i<size; i++) {
    hash = hash * FNV;
    hash = hash ^ dta[i];
  }

And since 'cp' and 'square' take only few bits they fit into a character, avoiding the aboveloop. Anyway FNV is a string hashing algorithm so its main strength comes from hashing multiple characters. We have only two here. For instance, if you just needed a hash key for the square alone then it would be a disaster as I showed in my previous post. The fact that two characters (cp & square) are merged make it workable but I have serious doubts about the number of collision with this method... When you use an LCG to generate hash keys, there is no correlation between (sq,cp) and the resulting hashkey. If we have doubts about a hashkey generated using rand() through that process, then the FNV one is very questionable in that regard.

Edit: I just did a _quick_ test with both FNV-1 and FNV-1a and I was right about the possible number of collisions. FNV-1 is completely horrendous while FNV-1a is a little better but you can imagine what how many collisions you can have zobrist hashing with this. First column FNV-1 and second one FNV-1a. Here is the result.

14 pieces placed at square 4
Code:

0x06409b6c1e4ab2ca      0x06409f6c1e4ab99a
0x06409c6c1e4ab485      0x0643fd6c1e4d8f2b
0x0640996c1e4aaf6c      0x0639cb6c1e44e5b0
0x06409a6c1e4ab11f      0x063d316c1e47c8d9
0x06409f6c1e4ab99e      0x0632ff6c1e3f1f5e
0x0640a06c1e4abb49      0x06366d6c1e42101f
0x06409d6c1e4ab630      0x062c3b6c1e3966a4
0x06409e6c1e4ab7e3      0x062fa16c1e3c49cd
0x0640936c1e4aa532      0x06256f6c1e33a052
0x0640946c1e4aa6ed      0x0628cd6c1e3675e3
0x0640916c1e4aa1d4      0x061e9b6c1e2dcc68
0x0640926c1e4aa387      0x0622016c1e30af91
0x0640976c1e4aac06      0x0617cf6c1e280616
0x0640986c1e4aadb1      0x061b3d6c1e2af6d7

Same piece placed at 64 squares. This is absolutely terrible. An xor would nullify most bits. Note that using a different piece here produces similar result.
Code:

0x06409f6c1e4ab99a      0x0633036c1e3f262a
0x06409f6c1e4ab99b      0x0633046c1e3f27dd
0x06409f6c1e4ab998      0x0633016c1e3f22c4
0x06409f6c1e4ab999      0x0633026c1e3f2477
0x06409f6c1e4ab99e      0x0632ff6c1e3f1f5e
0x06409f6c1e4ab99f      0x0633006c1e3f2111
0x06409f6c1e4ab99c      0x0632fd6c1e3f1bf8
0x06409f6c1e4ab99d      0x0632fe6c1e3f1dab
0x06409f6c1e4ab992      0x0632fb6c1e3f1892
0x06409f6c1e4ab993      0x0632fc6c1e3f1a45
0x06409f6c1e4ab990      0x0632f96c1e3f152c
0x06409f6c1e4ab991      0x0632fa6c1e3f16df
0x06409f6c1e4ab996      0x0632f76c1e3f11c6
0x06409f6c1e4ab997      0x0632f86c1e3f1379
0x06409f6c1e4ab994      0x0632f56c1e3f0e60
0x06409f6c1e4ab995      0x0632f66c1e3f1013
0x06409f6c1e4ab98a      0x0633136c1e3f415a
0x06409f6c1e4ab98b      0x0633146c1e3f430d
0x06409f6c1e4ab988      0x0633116c1e3f3df4
0x06409f6c1e4ab989      0x0633126c1e3f3fa7
0x06409f6c1e4ab98e      0x06330f6c1e3f3a8e
0x06409f6c1e4ab98f      0x0633106c1e3f3c41
0x06409f6c1e4ab98c      0x06330d6c1e3f3728
0x06409f6c1e4ab98d      0x06330e6c1e3f38db
0x06409f6c1e4ab982      0x06330b6c1e3f33c2
0x06409f6c1e4ab983      0x06330c6c1e3f3575
0x06409f6c1e4ab980      0x0633096c1e3f305c
0x06409f6c1e4ab981      0x06330a6c1e3f320f
0x06409f6c1e4ab986      0x0633076c1e3f2cf6
0x06409f6c1e4ab987      0x0633086c1e3f2ea9
0x06409f6c1e4ab984      0x0633056c1e3f2990
0x06409f6c1e4ab985      0x0633066c1e3f2b43
0x06409f6c1e4ab9ba      0x0632e36c1e3eefca
0x06409f6c1e4ab9bb      0x0632e46c1e3ef17d
0x06409f6c1e4ab9b8      0x0632e16c1e3eec64
0x06409f6c1e4ab9b9      0x0632e26c1e3eee17
0x06409f6c1e4ab9be      0x0632df6c1e3ee8fe
0x06409f6c1e4ab9bf      0x0632e06c1e3eeab1
0x06409f6c1e4ab9bc      0x0632dd6c1e3ee598
0x06409f6c1e4ab9bd      0x0632de6c1e3ee74b
0x06409f6c1e4ab9b2      0x0632db6c1e3ee232
0x06409f6c1e4ab9b3      0x0632dc6c1e3ee3e5
0x06409f6c1e4ab9b0      0x0632d96c1e3edecc
0x06409f6c1e4ab9b1      0x0632da6c1e3ee07f
0x06409f6c1e4ab9b6      0x0632d76c1e3edb66
0x06409f6c1e4ab9b7      0x0632d86c1e3edd19
0x06409f6c1e4ab9b4      0x0632d56c1e3ed800
0x06409f6c1e4ab9b5      0x0632d66c1e3ed9b3
0x06409f6c1e4ab9aa      0x0632f36c1e3f0afa
0x06409f6c1e4ab9ab      0x0632f46c1e3f0cad
0x06409f6c1e4ab9a8      0x0632f16c1e3f0794
0x06409f6c1e4ab9a9      0x0632f26c1e3f0947
0x06409f6c1e4ab9ae      0x0632ef6c1e3f042e
0x06409f6c1e4ab9af      0x0632f06c1e3f05e1
0x06409f6c1e4ab9ac      0x0632ed6c1e3f00c8
0x06409f6c1e4ab9ad      0x0632ee6c1e3f027b
0x06409f6c1e4ab9a2      0x0632eb6c1e3efd62
0x06409f6c1e4ab9a3      0x0632ec6c1e3eff15
0x06409f6c1e4ab9a0      0x0632e96c1e3ef9fc
0x06409f6c1e4ab9a1      0x0632ea6c1e3efbaf
0x06409f6c1e4ab9a6      0x0632e76c1e3ef696
0x06409f6c1e4ab9a7      0x0632e86c1e3ef849
0x06409f6c1e4ab9a4      0x0632e56c1e3ef330
0x06409f6c1e4ab9a5      0x0632e66c1e3ef4e3

_________________
https://sites.google.com/site/dshawul/
https://github.com/dshawul
Back to top
View user's profile Send private message Visit poster's website Yahoo Messenger
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