Author: Will Singleton
Date: 09:57:53 03/29/03
Go up one level in this thread
On March 29, 2003 at 03:49:21, Tom Kerrigan wrote: >I just finished a mess of tests, running my engine for 60 seconds/pos on a set >of 7 ECM positions that it solves in 30 to 60 seconds. > >I used the hash table sizes 1, 2, 4, 8, 16, 32, 64, 128, 256. > >The average depth being searched at 60 seconds was: >11.42, 11.71, 11.71, 11.71, 11.71, 11.71, 11.71, 11.71, 11.71 >So increasing hash table size beyond a couple of MB won't make you search >significantly deeper. > >The sum of times to solutions was: >361 (4/7 right), 342 (5/7), 329 (6/7), 321 (6/7), 310, 309, 309, 309, 313 >In other words, increasing the size up to 16MB makes a huge difference, but >there's no benefit to going bigger. > >The nodes/second times were: >1074k, 1074k, 1076k, 1077k, 1083k, 1084k, 1084k, 1079k, 1073k >So the biggest swing is 1%, so hash table size basically doesn't affect NPS. For >some reason speed seems to rise, peak at ~32MB, and fall. I can't explain that; >maybe it's just random. > >I was curious about how full the hash table was getting, so I wrote some code to >count empty entries after the search and also to count the number of overwrites, >i.e., when data for one position is overwritten by data for another position. >For reasons that should be pretty clear, I only calculated these numbers for the >depth-replace hash table and not the always-replace hash table. I only got >statistics for (IMO) the most significant hash table sizes. > >This is the hash table "fullness": >NA, NA, NA, 100%, 100%, NA, NA, NA, 44% > >This is the percentage of writes that were overwrites: >NA, NA, NA, 30%, 27%, NA, NA, NA, 4% > >It's interesting to note that the 16MB table is getting completely filled and 1 >in 4 writes are overwrites, i.e., a lot of information is being lost, but it >performs as well as the 256MB table which gets less than half full and hardly >any information is lost. > >In other words, it doesn't hurt to have a huge hash table, but anything more >than a surprisingly small table (~16MB = ~30% overwrites) likely isn't helping. >Contrary to Hyatt's assertion, it apparently doesn't matter if the hash table >fills up, or if it can hold the entire search tree. > >-Tom I'd just mention two things. According to my tests comparing 16mb vs 128mb tables, gains can be seen to increase with time. So, starting with clear tables, you should see significant benefits with search times going above 60 seconds, depending on the position. A very significant benefit that you don't address is the very large reduction in nodes and search time that occurs when searching with hash tables already full from previous searches. I just ran a quick test, and found the following difference when starting with full tables: 16mb search to depth 11: 135 sec 41238524 nodes 128mb search to depth 11: 60 sec 18579795 nodes The larger the table, the more info you can retain for subsequent searches. The benefits would vary due to hash implementation, pondering, and whether the predicted opponent move is made. Might be nice if someone were to run some tests showing the effects of full tables in various situations. Will
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.