TalkChess.com
Hosted by Your Move Chess & Games

Author Message
Daniel Shawul

Joined: 14 Mar 2006
Posts: 2187
Location: Ethiopia

Post subject: Re: transposition tables    Posted: Sat Jun 30, 2012 12:40 am

syzygy wrote:
 Daniel Shawul wrote: Give N small hash tables of the same size with K entries, how do you hash a position with zobrist hash hash_key ? Assume the small hash tables are physically separate (on different processor if you will).

If I understand you correctly, the N small hash tables form one large hash table. Each position maps to exactly one entry (or bucket) in this large hash table.

If N = 2^n and K = 2^k, then the large hash table has 2^(n+k) entries (or buckets), so you use n+k bits of the hash key to find this entry of the (fictitious) large hash table. n of those bits determine which of the N small hash tables you use for this position, the other k bits determine the entry within this small hash table.

If N is not a power of two, you could e.g. use the lower k bits to determine the entry (or bucket) within the small hashtable, and take ((hash_key >> k) % N) to find the small hash table.

If K is not a power of two either, you can take (hash_key % K) and ((hash_key / K) % N).

I thought about that but the number of processors is usually not a power of 2. It turns out distributed hash tables have much more important use in web caching and has been researched well. The key elements are decentralization, fault tolerance, and scalability. So I can not make assumptions on the total size of the hash table entries being a power of 2. A client could disconnect at any time and the hash table should keep on working with the remaing tables. When you take these facts into consideration , the method with division and modulo is OK. So each small hash table of equal size with 2^k entries and all N clients total = N * 2^k.
 Code: processor = hash_key % N hash_key = hash_key / N   /* I think a shift to the right could replace the division here but N is dynamic */ entry = hash_key & (2^k - 1)

_________________
https://github.com/dshawul
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
Subject Author Date/Time
Daniel Shawul Sat Jun 23, 2012 2:05 pm
Daniel Shawul Sun Jun 24, 2012 10:20 am
Robert Hyatt Sun Jun 24, 2012 5:01 pm
Daniel Shawul Sun Jun 24, 2012 5:41 pm
Robert Hyatt Mon Jun 25, 2012 12:37 am
Daniel Shawul Mon Jun 25, 2012 1:23 am
Robert Hyatt Mon Jun 25, 2012 10:05 am
Daniel Shawul Mon Jun 25, 2012 4:00 pm
Daniel Shawul Mon Jun 25, 2012 5:21 pm
Daniel Shawul Mon Jun 25, 2012 8:09 pm
Robert Hyatt Mon Jun 25, 2012 8:38 pm
Daniel Shawul Mon Jun 25, 2012 8:53 pm
Robert Hyatt Mon Jun 25, 2012 9:17 pm
Daniel Shawul Mon Jun 25, 2012 9:46 pm
Robert Hyatt Tue Jun 26, 2012 3:34 am
Daniel Shawul Tue Jun 26, 2012 11:06 am
Daniel Shawul Tue Jun 26, 2012 12:55 am
Daniel Shawul Sun Jun 24, 2012 5:53 pm
Daniel Shawul Wed Jun 27, 2012 11:17 pm
Ronald de Man Fri Jun 29, 2012 11:47 pm
Re: transposition tables Daniel Shawul Sat Jun 30, 2012 12:40 am
Vincent Diepeveen Fri Jun 29, 2012 11:07 pm
Daniel Shawul Sat Jun 30, 2012 12:32 am
Daniel Shawul Sat Jun 30, 2012 10:50 am

 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