Author: Carmelo Calzerano
Date: 06:50:50 02/01/01
Go up one level in this thread
On February 01, 2001 at 09:26:06, Vincent Diepeveen wrote: >On January 31, 2001 at 14:11:56, Carmelo Calzerano wrote: > >>On January 31, 2001 at 12:29:38, Vincent Diepeveen wrote: >> >>>On January 31, 2001 at 10:53:11, Carmelo Calzerano wrote: >>> >>>>On January 31, 2001 at 10:43:41, martin fierz wrote: >>>> >>>>>On January 31, 2001 at 10:29:51, Carmelo Calzerano wrote: >>>>> >>>>>>>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 f >>>or trouble! >>>>>> >>>>>>Vincent, >>>>>>which kind of indexing scheme would be suitable for such a table?! >>>>>>Whichever you use, you are mapping similar positions in the same entry: >>>>>>you'll get killed by conflicts, unless you plan to use a 2^64 entries table >>>>>>of course... >>>>>> >>>>>nobody dies here... you can use any normal indexing scheme, as long as you save >>>>>a unique hashlock-code in the table you are safe. you can still get two >>>>>positions indexed the same way, but you will detect it. >>>> >>>>But it's not a matter of safety, it's a matter of performance: lots of >>>>positions in big subtrees will map in just a bunch of hash entries. >>>>You will be able to easily detect all these conflicts, just comparing the >>>>full hash keys; but the hash table will be almost useless... >>> >>>Sorry you see problems which i don't see. >>> >>>Which problem do you see. >>> >>>You need 2 bytes extra an entry as he's needing now or something. >>> >>>If you put those 21 bits at the most significant bits >>>and the other bits below then you can use the least significant >>>bits even to index into your hashtable! >>> >>>So you only need a few bits more for each entry. I don't understand >>>the dying issue at all! >> >> >>Right, of course. But you forgot to specify this in your previous >>post... Instead, you said: >> >>> You don't need XOR. You need a bitmap >> >>so I assumed you didn't want to use any Zobrist-like algorithm >>for indexing, and that was my point. >>Sorry for misunderstanding :-) > >yes for connect4 one should not use zobrist hashing. as you can easier >get a whole position without zobrist in a single BITBOARD. So what algorithm do you suggest for indexing the table? I mean, it's possible to store the full position representation in (at most) 64 bits, as you described; but given an hash table size << 2^64 entries, how to compute the index where any given position has to be stored? You agreed that a few extra bits (say two bytes at least) are needed, so why don't you like to simply compute them with Zobrist algorithm or something similar? Bye, Carmelo
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.