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
Vincent Diepeveen



Joined: 09 Mar 2006
Posts: 1738
Location: The Netherlands
PostPost subject: Re: Zobrist alternative?    Posted: Sat Jun 16, 2012 12:55 pm Reply to topic Reply with quote
Don wrote:
diep wrote:
Daniel Shawul wrote:
Hi Vincent
We can't use a look up table for sq and piece since we are trying to avoid that. Rotation of a magic number was a substitute for that in this case. This will probably be not a good cryptographic hash but for zobrist might work since xor changes the hash key based on adjacent bits. The problem is that there are too many squares 1200 so we need a many majic numbers. But the rotation reduces tables size by 64 times. This is mentioned somewhere in this thread to reduce tables size, but can it be used to completely avoid it? I will see what can be used from RanRot for this purpose.
Thanks


Hi, just try it.


You missed the point. We have already discussed using two small tables and have concluded that adding them together might work just fine. Then it was suggested that might find a way to completely avoid any table lookups and wondered if there was a fast way to do that. Not because we don't think we should, but because we wondered if we could.

Quote:


I'm rotating the sq random number by a small prime lookuped for piece and vice versa. Maybe you missed this detail.

And then we add up this after 2 rotations.

So effectively we're having a bitresult of a multiplication in a field.

HGM wanted to avoid 5MB lookup to generate his Zobrist key and this definitely does with such tiny lookup tables of just a few kilobyte Smile

HGM wanted to avoid lookup of a double array, not single array.

double array is [piece][sq]
this is however single lookups of just [piece] and [sq]
We CAN use looking up piece and sq in a table,
we just can't afford a table sized sq * piece, that's all Smile

Bottomline is that what i posted here is factors faster than the multiplication you proposed.

As the lookups probably can get prefetched what i posted is under 2 clocks and will keep just 3 execution units busy for 1 cycle Smile

So throughput latency is 1 cycle, not counting the prefetch of the L1.

What you posted is maybe 5 cycles throughput or so?


The original question was a caching question to not get outside of the L1. Focus upon that. Changing the discussion is not what wise men would do.

Using multiplication then and smaller tables isn't very clever, as todays cpu's have magnificent caches, so the multiplication will just slow it down too much as it's 5 times slower or so than using small lookup tables.
Back to top
View user's profile Send private message Send e-mail Visit poster's website MSN 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