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: 4325
PostPost subject: Re: Zobrist alternative?    Posted: Thu Jun 14, 2012 6:38 pm Reply to topic Reply with quote
Don wrote:
hgm wrote:
Normally we construct a hash key by adding (or XORing) a number of Zobrist keys from a two-dimensional table key[coloredPieceType][square]. Now is the board gets large, and the number of piece types gets large too, this table would becoe intolarably large. For instance, in Taikyoku Shogi the board is 36x36 (1296 squares), and each side has 209 piece types (with somewhat less promoted types). That would make some 700,000 keys, which for a 64-bit key would require 5.6MB! That would not even fit the L2 or L3 cache! (OK, perhaps it can be compressed to 1 byte per key, by overlapping them, but that still nearly fills the L2 cache of the smaller CPUs....)

Do there exist less memory-hungry techniques for producing a hash key? E.g. if I would factorize the individual keys,

key[coloredPieceType][square] = key1[coloredPieceType]*key2[square]

so that I could do that multiplication during key update, would that result in any undesirable effects? I could not think of any obvious disadvantage, provided the key1 and key2 arrays are thoroughly random, with a range much larger than the number of pieces or squares (so that any pair of keys is extremely unlikely to have the same difference).

I'd much rather use a 10.4KB and a 4.8KB table, and do a multiplication in MakeMove, than having to access a 5.6MB table. Multiplications are pretty cheap, nowadays!


Clearly you want something that is incremental even more than you would for smaller boards. So I suggest you still use zobrist, but instead of a table of random numbers you use a simple hash function to produce the individual key elements - assuming you are not willing to eat the memory which is what this thread is about.

So zobrist_table[ colorType ] [ square ]

is replaced by the function zobFunc( colorTyp, square ) which is really a hash function on it's 2 arguments.

There are many fast hash functions that will work - an I don't think they have to be exceptional good hash functions - you just need to pick very fast ones that are good enough. You could have a table of constants, one for each square and multipy them to colorType to produce your key - I don't know how well that would work or whether the constants would have to be carefully picked or not - but for any given move application you would have to call this routine only a couple of times since it's still zobrist hashing at the outer level.

Don


P.S. I see my suggestion is not so different than what you suggest in your initial post. So the only thing I contributed here was a framework for looking at it. I believe that factorizing it like you suggest and multiplying to 2 pieces together is sound but I don't know that for sure. Multiplication is used similar to a hash function in magic bit boards but the constants are chosen carefully. On the other hand that is done to provide a perfect hash so maybe it's not a requirement here.

Maybe this is a way of asking the question:

Given a constant source of truly random number pairs, can the product of them pass any test of randomness? It's assumed of course that we are ignoring the overflows.

Don
_________________
The Optimist thinks this is the best of all possible worlds, the Pessimist fears it is true.
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