hashing unsigned versus's signed

[bob]

Any special rules for intializing the start hash? like i have a hash board populated with 64 bit numbers of board[64][12], i dont hash empty squares, so a white king on square 4 is like

currenthash=currenthash^board[3][5];

3 for square 4 ( 0-3) and 5 for the white king 0-5 for 6 white pieces.

I do this as i loop through board and find pieces on squares ( again i dont hash empty squares), but one thing i wonder is how to best start the hash. Teh curent method is to set intialhash=getHashNumber();

and hash the first piece on a square into intial hash. so if that king was the first piece it be,

currenthash = intialhash^board[3][5];

i'm only concerned about unqiequness and randomness of this method i suppose.

would it be best to start the hash with intialhash=0?

my old method was to start the hash with currenthash = board[3][5], if that was the first piece and then hash in each additional piece to it.

Mike

The "initial hash signature" should be the XOR sum of all occupied squares on the board. When you move a piece from A to B, you XOR with the random value for square A (which removes that value from the hash) then you XOR the random value for square B which adds that in. Every time you move a piece, you therefore do two XOR operations. This "incrementally updated value" is then available wherever you want with no effort required when using it.

[adams161]

the program computes a start hash when search starts and increments as you outlined from move to move.

if the first move is e2e4 it takes starthash= starthash ^ [p@e2 random hash number] -- to remove it
then starthash = starthash ^ [p@e4 hash numer]. as you outlined.

two additional cases are a capture, requiring that the captured piece be xored out of the board, similar to a from xor without the to step, and hashtoggle value is xored in after each move indicating side to move changed. if one move is made then hashtoggle becomes part of the hash and if two moves are made the effect of xoring it in again takes it out and the board looks like it did on move 1 ( except piece changes).

I probably should compute initial hash once and make move changes cummultive from move to move, then my initial hash would be sum of start postion and cumulitive changes after that.

the answer that its the sum of the pieces xored seems to say that it works like this:
currenthash=firstpiecehash;
currenthash=currenthash^secondpiecehash;
currenthash=currenthash^thirdpiecehash;

additionally castle rights are xored in.

I believe i'm essentially doing it the way you outlined ( or i was with my method before i got creative with an initial hash random number to add the board onto), but essentially i'm thinking mathematically, my method above is the same as:
currenthash=firstpiece^secondpiece^thirdpiece^etc
which is the same as
currenthash=firstpiece^secondpiece;
currenthash=currenthash^thirdpiece;
ect.

were the number for thirdpiece etc is from hashboard[64][12];

Mike

[adams161]

an additional reason i call _computestarthash() before each search and then only cummultivly increment in search itself, is that its a simplifying assumption for cases were the game doesnt move just forward, i.e. takeback in games and undo in analysis mode. Also in analysis mode i swap the pieces ( pulsar is allways at the bottom) so my starthash has to be computed each turn. But once a search commences i do only incrementally adjust hash.

Mike

[sje]

were the number for thirdpiece etc is from hashboard[64][12]

A minor point: almost always, subscript bounds that are a power of two should appear AFTER any subscript bounds that are not a power of two.

To see why, take a look at the instruction stream generated for each case and compare. In the above case, note that a shift by 6 (= log2 64) is much faster than a multiply by 12.

[bob]

were the number for thirdpiece etc is from hashboard[64][12]

A minor point: almost always, subscript bounds that are a power of two should appear AFTER any subscript bounds that are not a power of two.

To see why, take a look at the instruction stream generated for each case and compare. In the above case, note that a shift by 6 (= log2 64) is much faster than a multiply by 12.

The only exception concerns temporal locality. If you access values X and X+1 close together in time, they should be close together in memory. In the case of A[12][64] vs A[64][12] I would use the latter if I more often accessed A[N][M] and then A[N][M+1] since both will be supplied with one cache miss, where if you order the subscripts to make the address calculation slightly faster, you take two cache misses to get both which is _way_ slower.