Author: martin fierz
Date: 11:50:35 01/31/01
Go up one level in this thread
On January 31, 2001 at 13:36:30, Vincent Diepeveen wrote: >On January 31, 2001 at 10:11:23, martin fierz wrote: > >>On January 31, 2001 at 09:39:10, Vincent Diepeveen wrote: >> >>>On January 31, 2001 at 08:13:52, martin fierz wrote: >>> >>>>hi, >>>> >>>>i recently corrected some code in my connect 4 program and now it is able to >>>>solve connect 4 in less than a day on a fast PC with a large hashtable (of >>>>course, connect 4 has been solved long ago). i tried again with a smaller >>>>hashtable and >>>>got some strange results, for very long searches (billions of nodes) i don't get >>>>the same value for >>>>the root position. for not-so-deep searches i get the same values for both >>>>versions. i am wondering, [if this is not just a bug :-)] could this be some >>>>hashcollision-problem? can anybody give me a probability for a hash collision >>>>occuring when using B-byte key & lock, with a hashtable with S entries after >>>>searching N nodes? (i am using 4 byte ints for the key and the lock) >>> >>>You're using 32 bits to hash? >>> >>>I think there are like 7x6 rows or so = 2^42 possibilities which you >>>hash in 32 bits. >>> >>>Easier is to store the entire position. This fits easily in 64 bits >>>as with are 7 rows (?) at most 7 open spots are there. >>> >>>you can do next: white = 0, black = 1. >>>open spots also 0. >>> >>>Now also describe how far each row is open. That's 3 bits for 7 rows = 21 >>>bits. >>> >>>So in 42 + 21 bits you can store the entire position. That's not hashing >>>but a true hash. >>> >>>For solving a game you definitely need to store the entire position! >>> >>>With just 32 bits you ask for trouble! >>> >>>>also, i think i remember somebody mentioning here that one can choose the random >>>>numbers for the XORs in a clever way making hashcollision probabilities >>>>smaller - can somebody tell me how? >>> >>>You don't need XOR. You need a bitmap: >>> #define BITBOARD unsigned _int64 >>> in windows (new ansi-C convention also long long) >>> #define BITBOARD unsigned long long >>> for gcc compiler >>> >>>by making a few tables you can quickly update the true hash. Should >>>update that incremental of course! >>> >>>Not as fast as a 32 bits XOR, but you'll see a lot of problems in your >>>prog are solved! >>> >>>>cheers >>>> martin >> >>hi vincent, >> >>thanks for your tip - you are probably right with your suggestion that i should >>store the whole position if i want to solve connect 4. i remember i used to do >>that earlier, even, but switched to a zobrist scheme later because it was >>faster, and then computers were so slow and my program had lots of bugs in it so >>there was no way to solve connect4 at all. > >Weird. I solved it some years ago already, i guess you talk about the >80s? naah - i had so many bugs in my hashtable that rendered it more or less useless - so i am talking about the 90s :-) >A big speedup is to use more probes for hashing! sure, to solve it i used a 128MB table, that really speeds things up. >My tip is always to use the same random numbers to search with >as this is going to cause determinism in your proggies. i usually use random numbers from a random function but seed the random number generator, i agree, if you always use different numbers, you will always get different results - very bad if you want to debug something :-) >In draughts you can only search fullwidth, all kind of stupid >forward pruning just doesn't work strange - in checkers forward pruning works VERY well - i cut the remaining depth to half if one side is a man up. i wouldn't have expected draughts to be so different. of course, i'm not even sure about the rules of draughts, because there are so many different versions. is this with 10x10 and promoted men moving like kings or like queens in chess? > - mask 9 bits (mask to decide whether to overwrite this position) what do you use the mask for exactly? i use all the other things too, but my overwriting decision is based on the depth of the position as compared to the new position which i might store there. >Are you sure you debugged your hashtable well? no :-) >I found once a bug in hashtable 2 years after i had made that code! i made this connect 4 code in 1994 i think - i can't even remember :-) >But for the chances. Whatever your caclulation, in draughts 52 bits >was not enough for me and 64 bits seems to be ok. the best way to find out is probably to test it with different sizes... cheers martin
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.