Author: Russell Reagan
Date: 12:52:03 01/05/03
I am looking for an alternative hashing method that will work well given my current limitations. I have been experimenting with using non-rotated bitboards only (no 64-element array), and no bit index extraction routines (like FirstOne() and LastOne() in Crafty). So far it works well, but now I am at the point of implementing a hash table, and zobrist hashing doesn't seem to work well without the use of a bit index extraction routine. Does anyone know of a hashing method that woud work on bitboards (as opposed to working on board indexes)? The main obstacle is that I do not have the 'from' and 'to' indexes to use in a zobrist random mask array, since I am not using a bit index extraction routine (I do know the piece type however). Instead I represent a 'move' as three bitboards which get xor'd with the appropriate bitboard. I can give more details and code if it would help clarify what my limitations are. One method to use a zobrist-like method would be to represent the key for a piece on a particular square as the attacks that piece generates. For example, in classic zobrist key generation, for a white rook on e4 you would xor the current key with 'zobrist[WHITE][ROOK][E4]' which will be some random value. Instead, this value would be the following bitboard: white rook on e4 00001000 00001000 00001000 00001000 11110111 00001000 00001000 00001000 black rook on e4 11110111 11110111 11110111 11110111 00001000 11110111 11110111 11110111 Then you would xor all of the attack bitboards for each piece, and for added changes you could make white be the normal attacks, and a black piece be ~attacks (by complement operator ~). The keys for side to move could be the same as in classic zobrist hashing, so that would add in more randomness to the key, as well as castling rights and en passant square. Also, I could generate the actual attack bitboards instead of psuedo-attacks(since I already have them in my move generation routine) and simply add that as a field in my move structure, and then xor it in for each move. How well would the above method work? Also, I would like to know how to test a hashing method to see if it is effective, so I could test this out on my own and see exactly how effective it is. Another simple method to determine if two positions *might* be the same is to compare the 'all pieces' bitboards of two positions, but to be effective something more would be needed. Maybe you could use each of the 8-bytes comprising the 64-bit value as indexes into arrays, but this would be much less efficient than zobrist. It seems difficult to compare with the effectiveness and efficiency of zobrist hashing. If no other reasonable alternative is available, I will use the bit index extraction routine, but I would like to investigate alternative methods first. If anyone has any ideas I'd appreciate hearing them very much. Thanks, Russell
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.