Author: martin fierz
Date: 04:43:34 02/01/01
Go up one level in this thread
On February 01, 2001 at 07:01:49, Tony Werten wrote: >On February 01, 2001 at 06:33:05, martin fierz wrote: > >>On February 01, 2001 at 05:57:58, Tony Werten 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) >>>>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? >>> >>>Ideal would be if every number would change half of the number of bits. >>> >>>Currently I'm working on connect 4,5,6 and 7, using hash scheme of 64bits. I >>>have found no problems. The advantage of using zobrist is you can handle >>>mirroring very easy. You just have to keep 16 hash values and store the lowest. >>>It sounds slow, but getting a hashhit saves such a lot of nodes that it's worth >>>it. >>you are probably right. i used symmetries to solve solitaire a long time ago >>with exactly that scheme - i thought in connect4 they would be less important >>since there is only 1 symmetry operation (flip the board left/right), but i >>never tested it. why do you use 16 values? > >Flip horizontally, vertically and on both diagonals. ( 2^4 ) > >> >> >>>Using this hashscheme and some intelligent recognisers (recognizing >>>win-in-5-moves is a big winner), solving 4 in a row shouldn't cost you more than >>>2M nodes (with boards >= 6 by 5, wich is the minimum size for a first player >>>win). >>i'm using the standard 7x6 board. i can't really imagine solving that with >>2Mnodes - what makes you think you can do it with so few nodes? > >I never tried the 7*6 board. If you find the win on 6*5 you can make exactly the >same moves on a 7*6 board, but you have saved a lot of computingtime. > >Tony > >ps Aha erlebnis, you're talking about connect4 with a standing up board (stones >falling down). I'm talking about a flat board. Could make some difference. I >don't think the smaller board trick works, because in you're game zugzwang is >very important. aha-erlebnis indeed - that's exactly the game i was talking about. there you don't have the flip vertical and diagonal symmetry. and you are right that the smaller board trick doesn't work. 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.