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 

Hash table division
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: Hash table division    Posted: Thu Apr 05, 2012 11:15 pm Reply to topic Reply with quote
Rebel wrote:
When implementing hash tables in the days that memory was limited (1 Mb if you were rich) I set-up my hash table data structure as follows:

- One hash table for odd plies
- One hash table for even plies

And where ever possible make the odd ply HT twice as big as the even ply HT because that one is accessed the most due to the AB behaviour. And it also worked great in case of a full HT. Anno 2012 I wonder if that's still the case.

Anyone using a somewhat similar system ?


hi Ed, if that's what you're doing, indeed this century there is better systems, though what most don't realize is that the hashtable, total unmissable for todays software, or they get total crushed, is a lot less relevant for Rebel, thanks to its very unique search.

What started to work far superior for programs start this century is the system as i posted it end 90s, and repeated so start 21th century.

You have 1 big hashtable which you clean at startup or when receiving the openingsposition (or newgame) and then calculate using Zobrist the position in the hashtable. There you try 4 entries in a row and overwrite always the position with the lowest storevalue. The storevalue simply is a few bits, say a bit or 8, though you can risk less, which is the search depth added with the movenumber in the game.

Note i describe 4 entries in a row here. Back then i did do 8 and might go back to trying 8 once again. We call that in that case 8 probes. So default i'm doing 4 probes.

Most effective is moving from 1 to 2 probes.

The effect from 2 to 4 is still significant improving the search quality.
From 4 to 8 obviously only is interesting when the loading factor is over 0.5 or even far above that.

Loading factor you can of course calculate in 2 manners; just chaining will slightly influence the real loading factor to be slightly lower than the theoretic guessed loading factor, which is not a big deal.

Note that Diep also stores qsearch into hashtable, not all engine might have enough system time to do that, so the above probe numbers and decision taking values might be different from program to program there.

AFAIK i was the first one really using 4 sequential or more probes. Bob described in 90s doing 8 random probes (to avoid chaining), but of course at modern memory systems using more than 1 table is pretty slow and/or gives some overhead.

The hashtable though it works simple at cpu's, is so total crucial for todays elorating, without maybe even some world top players win blindfolded from what are top engines now.

Note that it is possible to always keep improving the working of the hashtable, it's such a crucial table now, even reduction decisions get taken based upon whether you have the hash entry or not. Also for cutnodes it's total crucial to have that best move in hashtable, otherwise you might reduce the best move in this position with some increased chance, directly losing elorating statistically for about every engine.

I'm sure that the hashtable codes in 20 years from now are doing a lot more than today. It just keeps getting more complex, not simpler.
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
Hash table division Ed Schroder Thu Apr 05, 2012 8:30 am
      Re: Hash table division H.G.Muller Thu Apr 05, 2012 9:47 am
      Re: Hash table division Steven Edwards Thu Apr 05, 2012 6:11 pm
            Re: Hash table division Robert Hyatt Thu Apr 05, 2012 6:58 pm
                  Re: Hash table division Vincent Diepeveen Thu Apr 05, 2012 11:36 pm
                        Re: Hash table division Robert Hyatt Fri Apr 06, 2012 6:58 pm
                              Re: Hash table division Vincent Diepeveen Fri Apr 06, 2012 8:37 pm
                                    Re: Hash table division Robert Hyatt Sat Apr 07, 2012 4:16 pm
                                          Re: Hash table division Vincent Diepeveen Sat Apr 07, 2012 4:27 pm
      Re: Hash table division Robert Hyatt Thu Apr 05, 2012 7:00 pm
            Re: Hash table division Sam Hamilton Thu Apr 05, 2012 8:39 pm
                  Re: Hash table division Robert Hyatt Fri Apr 06, 2012 7:01 pm
            Re: Hash table division Ed Schroder Fri Apr 06, 2012 1:29 pm
                  Re: Hash table division Vincent Diepeveen Fri Apr 06, 2012 1:33 pm
                        Re: Hash table division Ed Schroder Fri Apr 06, 2012 2:22 pm
                              Re: Hash table division Vincent Diepeveen Fri Apr 06, 2012 2:29 pm
                  Re: Hash table division H.G.Muller Fri Apr 06, 2012 1:35 pm
                        Re: Hash table division Vincent Diepeveen Fri Apr 06, 2012 1:37 pm
                        Re: Hash table division Ed Schroder Fri Apr 06, 2012 2:06 pm
                              Re: Hash table division Vincent Diepeveen Fri Apr 06, 2012 2:15 pm
                              Re: Hash table division Robert Houdart Fri Apr 06, 2012 2:24 pm
                                    Re: Hash table division Vincent Diepeveen Fri Apr 06, 2012 2:47 pm
                                    Re: Hash table division Ed Schroder Fri Apr 06, 2012 4:53 pm
                                          Re: Hash table division Robert Houdart Fri Apr 06, 2012 5:24 pm
                                                Re: Hash table division Sam Hamilton Fri Apr 06, 2012 5:29 pm
                                                      Re: Hash table division Vincent Diepeveen Fri Apr 06, 2012 8:33 pm
                                                            Re: Hash table division Sam Hamilton Sat Apr 07, 2012 1:39 am
                                                                  Re: Hash table division Vincent Diepeveen Sat Apr 07, 2012 8:42 am
                                                                        Re: Hash table division Sam Hamilton Sat Apr 07, 2012 3:11 pm
                                                Re: Hash table division Ed Schroder Fri Apr 06, 2012 9:55 pm
                                                      Re: Hash table division Vincent Diepeveen Fri Apr 06, 2012 10:25 pm
                                                      Re: Hash table division Robert Houdart Fri Apr 06, 2012 10:27 pm
                                                            Re: Hash table division Ed Schroder Sat Apr 07, 2012 3:27 pm
                              Re: Hash table division H.G.Muller Fri Apr 06, 2012 4:24 pm
                                    Re: Hash table division Ed Schroder Fri Apr 06, 2012 5:05 pm
                                          Re: Hash table division H.G.Muller Sat Apr 07, 2012 12:43 pm
                                    Re: Hash table division Vincent Diepeveen Fri Apr 06, 2012 5:14 pm
                  Re: Hash table division Robert Hyatt Fri Apr 06, 2012 8:44 pm
      Re: Hash table division Vincent Diepeveen Thu Apr 05, 2012 11:15 pm
            Re: Hash table division Ed Schroder Fri Apr 06, 2012 1:53 pm
                  Re: Hash table division Vincent Diepeveen Fri Apr 06, 2012 1:58 pm
                        Re: Hash table division Ed Schroder Fri Apr 06, 2012 2:10 pm
                              Re: Hash table division Vincent Diepeveen Fri Apr 06, 2012 2:23 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