Author: Vincent Diepeveen
Date: 06:21:36 02/01/01
Go up one level in this thread
On January 31, 2001 at 14:50:35, martin fierz wrote: >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? i'm talking about the most popular form of draughts like is played on high level and professional levels, the polish rules version differences with checkers: draughts has 10x10 board capturing longest string is forced capturing backwards is legal (why isn't is possible to capture backwards in checkers?, i mean a queen is getting just too valuable then!) capturing a long string over promotion field in draughts doesn't automatically capture further as a queen but you get only a queen at the end of your move if you end up at the promotion field. whether you passed it during your capturing is not important. In short a queen is worth hell less in draughts as it is in checkers. Also a feature of 10x10 board is that 3 queens versus 1 queen is in general a draw. I search like 40 ply fullwidth in endgame. How could forward pruning *ever* work for me? A piece in draughts is way less important as it is in checkers i bet. Just the fact that you have more pieces already is an indication for that. In closed position giving away a pieces is very common, as nearly any endgame is a draw if both sides get a queen. So giving away a piece is very smart in order to try a kamikaze effort to promote. last plies pruning is bad for branching factor, no difference in chess or draughts there. Of course if you prune at any level of the tree things get different. However if you do depth reduction you are going to suffer from the FHR problem. Somewhere in hashtable you store for depth = n a score which is in fact n-i where i was the reduction depth you used. I don't need to mention that nullmove is worthless in draughts as doing nothing is usually the best move... Important feature from draughts is that any national player after a bit of practice can beat *any* draughtsprogram, as long as those national players don't tactical blunder (some people who are positionally/strategically brilliant have the habit in any sport to blunder bigtime). Several years i had a version that last ply pruned based upon material, also i tried smart selective searches, but in the end all tactical tricks you see in a flash of a second anyway. No way to find a trick! The only interesting thing is to see lines which you might evaluate wrong. Usually that are the stupid lines where you have long term compensation for a piece down as your majority or whatever is going to get a queen in the end. Humans are far superb in seeing this of course. Things change when you search at a level that the entire game is nearly solved. Getting a ply deeper might be more interesting then as everything gets from your EGTBs then i bet. I bet you already solve entire lines in checkers from openingspositions? Just 32 squares and 12 pieces, *any* non capturing line you are already in EGTB, and you can't move back with a piece, not even capture back!!! I mean in a 10x10 game with 50 squares and 20 pieces i already hit egtb right from the first move! >> - 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. A position which you searched in the openingsposition is of course less important as the position you just searched a move ago. Depth is completely irrelevant compared to that. >>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... Start with 64 bits :) >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.