Zobrist alternative?

[Edmund]

why not: key(piece,square) := key(piece, column) ^ key(piece, row)

Bishop on row 0 / file 7 gets the same key as row 7 / file 0. These two positions are only one move apart.

[smrf]

why not: key(piece,square) := key(piece, column) ^ key(piece, row)

Bishop on row 0 / file 7 gets the same key as row 7 / file 0. These two positions are only one move apart.

Be aware that the two sides of XOR obviously use distinct Zobrist keys.

[diep]

I have bad experience with shifting keys by only 1 bit. I tried it in a simulator, and it drove up the number of key collisions enormously. When rotating keys by bits I could not detect any difference in collision statistics with truly random keys.

I have no explanation for this; it was just an observation.

If you shift it 1 bit, which is a very unlucky amount to shift, there is a multilineair relation between the keys.

If you want to replace the table by a hashfunction, realize the hashfunction will eat several cycles to accomplish the hashing.

Basically we assume you still want to make use of Zobrist and that you can incremental update. As with this self invented form of shogi at 36x36 with 200+ pieces, it'll take a while to play that game for a player.

furthermore 64 bits won't be near enough wth such a huge board size and that many pieces. So you're searching for a bit or 512 to start with anyway.

What you need to design now, which is not so complicated is that given an input piece and a 'to square', you can drop a piece onto that square.

So we have a piece represented in say 8 bits, we have a 'to square' represented in say 11 bits.

From those 2 unique properties you want to generate an unique 512 bits key that doesn't have a multilineair relation. It'll eat a few cycles, but there is many solutions to do so.

Even AES-CBC using 256 bits can generate unique key within 12 cycles a byte overhead, so just to generate a key that's safe enough for Zobrist, assuming 512 bits should be easily possible within a cycle or 10-20.

You can for example precalculate values in some smaller tables.

Say 1 table sized 36*36 entries @ 1024 bits and 1 table of 206+ entries @ 64 bits.

Now using some internal bit rotation from the 1024 bits number to a 512 bits number, using small parts of the 64 bits lookup, you can generate a new number.

Example RNG for this is called RanRot, downloadable from the net obviously.
RanRot works ok for Zobrist.

With some experimentation you can get the number of bits down and limit the amount of rotations you need. It will get down the total number of cycles you 'waste' onto it. It'll work fine.

[Edmund]

why not: key(piece,square) := key(piece, column) ^ key(piece, row)

Bishop on row 0 / file 7 gets the same key as row 7 / file 0. These two positions are only one move apart.

Be aware that the two sides of XOR obviously use distinct Zobrist keys.

different keys .. ok

then you still get a problem with multiple pieces of the same type.
e.g. 2 rooks:
rook A on 0/0 and rook B on 7/7
is the same as
rook A on 0/7 and rook B on 7/0

[smrf]

...

then you still get a problem with multiple pieces of the same type.
e.g. 2 rooks:
rook A on 0/0 and rook B on 7/7
is the same as
rook A on 0/7 and rook B on 7/0

Not at all. Four distinct keys will be used to produce both overlaid keys.

[hgm]

Thanks for all suggestions. Some reactions:

To Daniel:
Sorry, but I messed up with the operator priorities, and what I actually meant was to use ~(rand()*rand()) for the pieceKey and squareKey arrays. The reason was that the product of two independent randoms has only 25% probability to be odd, and so its complement is odd in 75% of the cases. Multiplying two of them then has a (0.75)^2 = 9/16 probability to be odd, which is much closer to the desired 50% than when I use pure rand() values for the key factors.

To Reinhard:
It seems safer to use something unrelated to XOR for constructing the keys, like multiplication. With what you propose, two Rooks in the same rank would contribute the same (piece,rank) 'sub-key', which then would cancel each other in the total key. So that the key becomes completely insensitive to which rank the Rook pair is on.
But it seems that using key1[piece][rank]*key2[piece][file] requires bigger table space than key1[piece]*key2[rank][file].

To Vincent:
Would the simple multiplication of pre-computed randoms that I proposed be a sufficiently random mapping of the int8 piece number and int11 square number to implement what you suggest? A single multiply is quite cheap, in terms of cycles. (There is some latency, but you have to do this for from-square, to-square and victim indepently, so it can be nicely pipelined.)

Why do you think a larger key would be needed? That there are more positions possible does not mean my search tree will be any larger. In fact it will be smaller than with Chess, because the nps I can achieve is likely to suck in the extreme, with so many pieces on the board. The key only has to be large enough to reduce the number of misidentified hash hits to an acceptable level. With 32-bit signature I only get a false hit every 4 billion probes.

Note that this game was not 'self invented' (by me, that is), but has existed since the mid 16th century. Whether that was long enough to actually complete a game, I do not know!

[diep]

Thanks for all suggestions. Some reactions:

To Daniel:
Sorry, but I messed up with the operator priorities, and what I actually meant was to use ~(rand()*rand()) for the pieceKey and squareKey arrays. The reason was that the product of two independent randoms has only 25% probability to be odd, and so its complement is odd in 75% of the cases. Multiplying two of them then has a (0.75)^2 = 9/16 probability to be odd, which is much closer to the desired 50% than when I use pure rand() values for the key factors.

To Reinhard:
It seems safer to use something unrelated to XOR for constructing the keys, like multiplication. With what you propose, two Rooks in the same rank would contribute the same (piece,rank) 'sub-key', which then would cancel each other in the total key. So that the key becomes completely insensitive to which rank the Rook pair is on.
But it seems that using key1[piece][rank]*key2[piece][file] requires bigger table space than key1[piece]*key2[rank][file].

To Vincent:
Would the simple multiplication of pre-computed randoms that I proposed be a sufficiently random mapping of the int8 piece number and int11 square number to implement what you suggest? A single multiply is quite cheap, in terms of cycles. (There is some latency, but you have to do this for from-square, to-square and victim indepently, so it can be nicely pipelined.)
Why do you think a larger key would be needed? That there are more positions possible does not mean my search tree will be any larger. In fact it will be smaller than with Chess, because the nps I can achieve is likely to suck in the extreme, with so many pieces on the board. The key only has to be large enough to reduce the number of misidentified hash hits to an acceptable level. With 32-bit signature I only get a false hit every 4 billion probes.

I did not checkout your idea, i will explain why.

In itself seen it would be possible to design hashing functions using multiplication instructions, as a multiplication instruction is mixing the bits in a very effective manner if you choose the number well and shift right a tad (the least significant bits you probably want to get rid of, just like the top bits). There is however hardware technical limitations.

Where at the old K8 it wasn't too bad, it stil lwas blocking other execution units. Still throughput latency of a single multiplication of 2.25 cycles there
meaning effectively you could also execute in that time around 8 other instructions.

At intel things are a lot worse. The throughput is 3.75 cycle for a single multiplication instruction and in SIMD you only can do 32 bits multiplications as SIMD doesn't have anything larger than that for integers.

Total latency is a lot slower of course than 3.75 cycles, this is the *throughput* latency.

Newer processors from AMD, the bulldozer range, multiplication has become 2x slower. Throughput at latest intel cpu, if you can afford it (maybe 10 years from now) is supposed to be better, but i'mm sure that cheaper models it sucks again at and there is so many conditions to fulfill there.

On the other hand if you design things well with rotate instructions and a small lookup table, then i'm sure you can do it faster and also optimize it for SIMD very well.

Realize there isn't a 64 x 64 multiplication instruction in SIMD, only 32x32 is there vectorized and we can prove of c ourse that in case you can't fit your tables in the L2, that you also will be needing a lot more bits for your Zobrist function. Probably it'll be sooner above 512 bits than below what you need.

[diep]

p.s. nice photo - this game started in the year 500 after death of Christ and they're still busy with the same game, each generation of 36x36 Shogi enthusiasts is allowed to play a few moves during life then the next generation plays another few moves?

designing a hashfunction for this isn't what you need - a robot playing the moves for you is more interesting, as i bet each game takes forever

[diep]

On keysize.

the classical approaches on how many bits of Zobrist you need for which application are all pretty flawed.

In Diep i'm using internal 128 bits Zobrist keys from which i store, together with the lookup bits, say around a 80 bits or so.

One key i use as a lookup, the other for storing bits from.

Sometimes if i change the hashtable lookup/store functions then this changes then i store a few bits more then a few less.

Now most will get away with 64 bits in chess, the real question you have to ask your self is not: "how big is the game", but "how big is the search space that a search could potentially hit while playing a game".

In the hashtable replacement system as i posted already around 1999-2000 on the forums, you can see that i'm using 8 probes and overwriting the entry with the count, where count = searchdepthleft + searchdoneingame

At start of game i reset the 'searchdoneingame' counter and each time its searching it gets incremented by 1. So in a normal game this is similar to number of moves from the openingsposition.

In short it's very likely if we play a few moves that we still have entries left from many moves ago.

That means that the effective searchspace you can reach is quite a lot larger than the simple minded '1 bit approach' from Ernst A Heinz.

To start with after 2 searches we get an overwrite 'collission' so to speak if we just use 1 bit and it's not likely that we did overwrite all entries of previous search already. Furthemore, it wouldn't be the first time that we pondered on the wrong move, a move that got us in a total different SEARCH SPACE.

As that's the crucial word. The size of the search space we can potentially reach is determining the size of the key we need. furthermore i'm of the opinion that i want 0 collissions let alone 0 errors.

Many chessprogrammers are fine with a bunch of collissions and a few errors in fact. If you assume that a few errors isn't a problem, then suddenly you can stick to 64 bits for any game for the coming 100 years

And o boy you'll lose some games in those years because of that as Murphy's law always applies in games.

Yet if we assume we want 0 collissions then suddenly the only relevant thing is the total search space we can reach within a single search.

Now the boardsize might seem impressive, it just means we got more legal moves. More legal moves means we can search at high sub dozen million nps figures, letting deep blue seem like a slow beancounter in fact. Parallellizing with so many legal moves possible is going to be easy, even for beginning software engineers.

Also in the displayed games, we have deep forced mating sequences dropping a bunch of pieces around the king in order to mate him.

So there is no discussion about the huge search space that you will be able to reach. Calculating how many bits you actually need for this game is yet another discussion. I just dropped '512' bits as an example.

If we compare chess: Using around a 70+ bits seems pretty safe right now.
The game has in theory a tad more than 10^40 possibilities, yet if we go

In itself 10^38 is 2^128 already.

With a 36x36 board and 200 pieces, knowing in shogi if you capture a piece you can drop it yourself again at the board, you will have a lot more possibilities i bet than that.

For sure this is a game that will take forever to play

[Edmund]

...

then you still get a problem with multiple pieces of the same type.
e.g. 2 rooks:
rook A on 0/0 and rook B on 7/7
is the same as
rook A on 0/7 and rook B on 7/0

Not at all. Four distinct keys will be used to produce both overlaid keys.

Let there be two arrays of zobrist keys
key_col[piece][column] and key_row[piece][row]

now the first position
rook A on 0/0 and rook B on 7/7
key1 = key_col[rook][0] ^ key_row[rook][0] ^ key_col[rook][7] ^ key_row[rook][7]

the second position
rook A on 0/7 and rook B on 7/0
key2 = key_col[rook][0] ^ key_row[rook][7] ^ key_col[rook][7] ^ key_row[rook][0]

key1 = key2