Re: 12 to 8 bit Hashes - application to chess
- From: David Eather <eather@xxxxxxxxxx>
- Date: Sat, 18 Nov 2006 16:01:34 +1000
Mike Amling wrote:
Gian-Carlo Pascutto wrote:riedel wrote:
Hi Gian-Carlo,
you might find this interesting:
http://www.gotw.ca/gotw/072.htm
or study the sources of cbu at
http://www.wotsit.org/download.asp?f=cbu_src
for the old chessbase format cbf
(it used a similar - but broken - algorithm to enumerate legal
moves).
Unfortunately pretty much all the answers ignored the hash questions and
suggested techniques based on enumerating moves - which is at least
several orders of magnitude too slow.
If it's going to take much more than a few adds, shifts, multiplies, or
table lookups, it's just too slow.
I've heard of speed chess, but ...
Is it both the speed of encoding and the speed of decoding that are critical, or only one of them?
What's the input to the encoding? Algebraic notation? PGN?
Is the goal to convert thousands of games in algebraic notation to something more compact?
That's the reason why I'm looking at a hash.
As fast as that might be for encoding, how are you going to decode if there are collisions?
My current thinking is like this: any piece on the field c1
can't possibly move to f8. Not all 64 x 64 combinations are actually
possible. And they won't be equally likely (long moves are less likely
since it's more likely there will be a blocker in the way). But how to
exploit this in the 8 bit hash to minimize the collisions?
I can tabulate the 64 x 64 possibilities and calculate the statistics on
them. How to go from here? Order them from most likely to least likely
and assign them modulo 255? This would decrease the likelyhood of a
collision, wouldn't it? And the "hash" would just be a 4K table lookup.
If you ignore the state of the board, then the From square would on average need 4 or 5 bits, leaving 3 or 4 bits for the To square. Sounds like a lot of collisions.
Anything better possible?
Start with a 64-element array BOARD[0..63] representing the board contents. Each element of BOARD has the man identifier (which becomes the first few bits of output) and what kind of piece it is. The remaining bits of the output are from a 6x64x64 array MOVES[piece type, 0..63, 0..63] whose elements have a bit string and the length of that bit string. After outputting, update BOARD for the move. (Updating the BOARD needs a little special code to handle promotions, castling and en passant.) If it's a capture that brings down the number of opponent's men to a power of two, you may wish to update the man-identifiers to shorter bit strings.
The above can't be several orders of magnitude slower than an alternative because it doesn't take several orders of magnitude of machine instructions.
There's no need to make a list of legal moves on a per-move basis, unless you want to check each move for legality (which would be time consuming even if your output is some kind of hash). MOVES does need to be set up (once) using knowledge of legal moves.
--Mike Amling
MA,
can I ask you a question via e-mail?
David Eather
.
- References:
- 12 to 8 bit Hashes - application to chess
- From: Gian-Carlo Pascutto
- Re: 12 to 8 bit Hashes - application to chess
- From: riedel
- Re: 12 to 8 bit Hashes - application to chess
- From: Gian-Carlo Pascutto
- Re: 12 to 8 bit Hashes - application to chess
- From: Mike Amling
- 12 to 8 bit Hashes - application to chess
- Prev by Date: Re: Quantum computing and Brute Force Attacks
- Next by Date: Re: Strongest encryption algorithm
- Previous by thread: Re: 12 to 8 bit Hashes - application to chess
- Next by thread: Re: 12 to 8 bit Hashes - application to chess
- Index(es):
Relevant Pages
|
