Author: Robert Hyatt
Date: 20:21:11 12/07/02
Go up one level in this thread
On December 07, 2002 at 11:42:54, David Rasmussen wrote: >On December 07, 2002 at 11:25:44, Robert Hyatt wrote: > >>> >>>I hadn't either until now. But I am pretty sure that Bob sais something about >>>this happening once in 100 games or so. >> >>That was an estimate. Think about the math. You are collapsing some 2^168 >>positions into 2^64 hash space. That is a _huge_ aliasing problem. So the >>probability of getting duplicates is not just a probability, it is an absolute >>certainty... > >I know that. I am not saying that it will not happen. I know it will. But I am >asking about the frequency. When doing math on these beasts people tend to just >assume that everything is random. It isn't. The subspace visited by a 12-ply >search with a 64 MB hashtable is not the same as the whole game tree. As I said: >we don't care if there are signature collisions between two positions that are >"far" from eachother. The probablility for it happening within the history of a >seach with a hash table, is far less (apparently). And it is not simple to >estimate how much. So I was asking about people's experiences of this frequency, >because I didn't believe such naive reasoning anyway. If the theory isn't >corresponding with experience, fix the theory. > >/David The math tells the tale. Searching 1M nodes per second, in a game that goes for (say) four hours (forty moves in 2 hours) means 14400 seconds, which is 14 billion nodes. You are mapping 2^168 positions into a 2^64 hash signature, so it is not surprising that an error occurs here and there. I don't remember the results any longer, but several of us ran some tests years ago in a discussion on r.g.c, and found that 32 bits is useless, and that 64 bits has so few errors they can be ignored. With recent testing I did that suggests that a bad hash collision every 10K nodes has no effect on the final score, we seem to be "ok". :)
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.