TalkChess.com
Hosted by Your Move Chess & Games

Author Message
Vincent Diepeveen

Joined: 09 Mar 2006
Posts: 1738
Location: The Netherlands

Post subject: Re: Zobrist alternative?    Posted: Wed Jun 13, 2012 1:01 pm

 hgm wrote: I have bad experience with shifting keys by only 1 bit. I tried it in a simulator, and it drove up the number of key collisions enormously. When rotating keys by bits I could not detect any difference in collision statistics with truly random keys. I have no explanation for this; it was just an observation.

If you shift it 1 bit, which is a very unlucky amount to shift, there is a multilineair relation between the keys.

If you want to replace the table by a hashfunction, realize the hashfunction will eat several cycles to accomplish the hashing.

Basically we assume you still want to make use of Zobrist and that you can incremental update. As with this self invented form of shogi at 36x36 with 200+ pieces, it'll take a while to play that game for a player.

furthermore 64 bits won't be near enough wth such a huge board size and that many pieces. So you're searching for a bit or 512 to start with anyway.

What you need to design now, which is not so complicated is that given an input piece and a 'to square', you can drop a piece onto that square.

So we have a piece represented in say 8 bits, we have a 'to square' represented in say 11 bits.

From those 2 unique properties you want to generate an unique 512 bits key that doesn't have a multilineair relation. It'll eat a few cycles, but there is many solutions to do so.

Even AES-CBC using 256 bits can generate unique key within 12 cycles a byte overhead, so just to generate a key that's safe enough for Zobrist, assuming 512 bits should be easily possible within a cycle or 10-20.

You can for example precalculate values in some smaller tables.

Say 1 table sized 36*36 entries @ 1024 bits and 1 table of 206+ entries @ 64 bits.

Now using some internal bit rotation from the 1024 bits number to a 512 bits number, using small parts of the 64 bits lookup, you can generate a new number.

Example RNG for this is called RanRot, downloadable from the net obviously.
RanRot works ok for Zobrist.

With some experimentation you can get the number of bits down and limit the amount of rotations you need. It will get down the total number of cycles you 'waste' onto it. It'll work fine.
 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
Re: Zobrist alternative? 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
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