[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [computer-go] Re: Sharing Secrets
Nicol N. Schraudolph wrote:
Let's say you have 1,048,576 blocks of 8 64-bit hashes. Every block's
address is a 20-bit value. Any Zobrist hash' 20 LSB's form the address
of the block in which it will be stored. Which means that now the
block's address (a number from 0 to 1,048,576) is equal to the 20 LSB
of the Zobrist hash. Which means that you can simply take the 20 LSB
of any hash stored and put whatever you like in it. You can put the New
Testament in those 5 nibbles x 1 MB.
I hate to fall so neatly into this pattern of incredulity-then-ridicule
that you perceive here, but I don't think I've ever implemented a hash
table where I stored the address part of hash keys, except when I didn't
care about memory footprint. It didn't occur to me that something that
obvious could be your "big secret".
This is very similar to the way you can save 17 bits when storing connect4
positions in a hashtable, as used by my publicly available connect4 solver.
A position in 7x6 connect 4 can be encoded in exactly 49 bits (using one
extra bit per column to indicate height). Now suppose you take this 49 bit
number N modulo a large prime P to get the index I = N mod P into your hashtable.
To detect collisions, you could store all 49 bits at this entry. But that
is redundant, since only positions N' that are also I mod P can end up there.
So it suffices to store only the most significant 32 bits. Any 2 positions
N and N' with identical top 32 bits differ by less than 2^{49-32}=2^17,
so the only requirement is for your hashtable size P to exceed 128K entries.
To some people this idea is entirely obvious, others might consider it clever.
What I consider clever is a way to represent the board in connect-4 so that
the 49 encoding can be computed incrementally with only 3 additions.
Anyone interested (doubt it though:-) can find out at
http://www.cwi.nl/~tromp/c4/Connect4.java
regards,
-John
_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/