Author: Uri Blass
Date: 12:59:12 10/03/01
Go up one level in this thread
On October 03, 2001 at 13:36:15, TEERAPONG TOVIRAT wrote: >On October 03, 2001 at 02:54:32, Uri Blass wrote: > >>On October 02, 2001 at 20:52:13, TEERAPONG TOVIRAT wrote: >> >>> >>>Dear Dr.Hyatt, >>> >>>I think the number of total _possible_ positions in chess is beyond >>>the question. However,I'd like to know how they calculate it ? >>> >>>A few months ago,I tried to work out the number in _checkers_ >>>game. My logical assumption is that if the hash signature is too >>>small there would be a high incidence of type 1 collision and if >>>the hash signature is large enough the collision would be 0. >>>So,my experiment started with 32 bit hash table ,after 1 million >>>entries are fully occupied I started counting the incidence of >>>type 1 collision. Each time I got type 1 error,I increase another >>>bit to the hash table.I saw the incidence is lowered by half too. >>>Until one point the incidence is zero ,of course after a few >>>games test. >>> >>>Could I claim that at that point the hash signature is approximately >>>equal to the number of legal(possible) positions? >> > > >Hi, > > >>I do not know what is type 1 collision > >I mean Zobrist type 1 error,2 different positions having the same >hash signature. I read about this from Dennis Breuker's papers. > > >and I also do not understand what hash >>tables can do with the number of legal positions because it is known that the >>search trees of programs contains only a very small part of the number of legal >>positions. > >In checkers,it's said that there are 10^18 possible positions. Simple estimate gives 5^32 as an upper bound because there are 32 relevant squares on the board. It is possible to get a better estimate by using only positions with legal material structure. I think that after doing it the best way to get an estimate is to generate a lot of random positions and to find out how many of them are legal (the monta karlo way) even 5^32<10^23 so you can expect more than 10 legal positions out of 1,000,000 if you consider the fact that most of the random positions have illegal material structure then I guess that you can get even more than 10 out of 100,000 if you choose a random material structure. >For a 64 bit hash table (1.6x10^19) ,if we have a good hash function, >we will never get type 1 error. It seems like you have 10 tennis balls >in 100 baskets,we can expect any position has its own unique signature. > -> Do you agree here? yes > >if we decrease number of bit of hash table one after another. >What would happen? (You start to decrease the number of baskets.) >We would get more risk of type one error,approximately by factor of 2 >for each decreasing bit,because there must be some positions sharing >the same hash signature. ->Do you agree here? yes > >By experiment, we can test the incidence of the error when collision of >position occur. I admit that if the number of test is small it's difficult to >say the incidence is zero or just close to zero .This is the main drawback. > >I started with 32 bit hash table. If the error happened,I gradually >increased the number of bit. Until the incidence is touching zero. >I think at that point the number of positions and hash signature is >roughly equal. The problem is that you used only positions from games and I suspect that there are legal positions that are not from games. I believe that checkers is simple enough to use the monta karlo way. I also expect this game to be solved in the next 20 years and maybe even in the next 10 years. I believe that the best way to solve the game practically is simply searching. People are not going to be sure that the game is solved at the time that it is solved(the only evidence for it is going to be seeing draws in every game between top programs) but after the solution is going to become known it is going to be clear that the programs practically did no mistake. I do not know much about checkers and I wonder if there are positions in that game when the best programs of today cannot find the right move even after 24 hours of search. There are in chess(for example the Bh3 known sacrifice of shirov) Uri
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.