Author: Sune Fischer
Date: 08:20:47 09/25/01
Go up one level in this thread
On September 25, 2001 at 10:12:31, Robert Hyatt wrote: >>I understood the question as: "is larger _always_ better". >>The answer would be no. >>Because a hash table of size 2^64 and a computer that could do 2^64 nodes per >>move would fill this in no time and the rest of the game after ply ~30 would be >>_all_ collisions! > > >No it wouldn't. Remember that there are roughly 2^160 different unique >chess positions. We can store up to 2^64 of those. Leaving 2^96 possible >collisions for every possible entry in the 2^64 table. It doesn't matter >whether you store 2^32 entries or 2^64 entries. The potential collisions >are both so large it doesn't matter. Using my example with 2^64 unique nodes calculated per move and a 2^64 size table, you will fill this table on the first move (assuming no collisions). If you have an average branch factor of 6, then this is less than 30 plies deep. So when you get to positions deeper than 30 plies, you will be seeing only new positions, and since your table is full with outdated nodes, they will all collide in the hash. If you "only" use a 2^32 size table, you will have a 50% chance for each of the 2^64 nodes to collide, so that's 2^32 collisions per move. This continues all the way down to 1, where there will be only 1 collision on average per move. >And the only undetected collisions are >going to be the cases where you search two of those 2^96 different positions >that map to the same table entry. And it won't matter whether you have just >one table entry or 2^64. All depends on the amount of nodes searched, if you only search around 2^22 nodes per move, then you would never fill the huge table anyway. And when computers someday actually become that fast, then we'll just use larger keys. >going from 2^20 entries to 2^21 entries does not change this enough to even >think about. It changes by a factor of 2, I'm not saying that it is a problem, I'm merely saying that it is a mathematical fact. (I have made the assumtion that you fill the table quickly, because these probabilities are incorrect while there are still avalible space in the hash.) >We would just be depending on a bit of luck to cause the first >of the two positions to be overwritten before we probe and false-match on the >second. That is yet another degree of freedom. And it gets dwarfed by that >huge collision predictor (2^96 positions for every single table entry) >anyway... I'm not disagreeing with that at all. -S.
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.