Author: Vincent Diepeveen
Date: 07:25:42 02/01/01
Go up one level in this thread
On February 01, 2001 at 09:50:50, Carmelo Calzerano wrote: >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? there are zillions of ways to do this! >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? As this 4 connect problem is TOO simple. Why hash something if you can solve the entire game very quick by other means? The advantage of hashing is especially that something which can't be stored within a few bytes can be stored now in only a few bytes, running the risk that you of course get a hashcollission which messes up search, i'm pretty sure that instead of using 32 bits hashing it's smarter to store the entire position as that gives 100% garantuee on not giving a collission, even with 64 bits of Zobrist hashing you don't have a safe theoretic feeling, perhaps you are using a wrong random generator or just have bad luck, whereas you now can simply solve the entire game in a theoretic very correct way! No hash algorithm beats a true storage of the entire position if it's possible in just the same number of bits! Zobrist gives especially a lot of safety there where you don't see all the legal positions. In chess it's *very* unlikely that both all pawns are getting moves to the 6th row and all pieces messed up over the board (just for the pawns on 6th row you already need a fullwidth search depth of 48 ply from openings position). So Zobrist is strong if nearly all positions look like each other with only relative small changes. Here we talk about a game where we see potentially *all* positions, so the chance you get a collission is relatively seen bigger! >Bye, >Carmelo
This page took 0.01 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.