artificial intelligence - Generate unique identifier for chess board -

i'm looking checksum chess board pieces in specific places. i'm looking see if dynamic programming or memoized solution viable ai chess player. unique identifier used check if 2 boards equal or use indices in arrays. help.

an extensively used checksum board positions zobrist signature.

it's unique index number chess position, requirement 2 similar positions generate entirely different indices. these index numbers used faster , space efficient transposition tables / opening books.

you need set of randomly generated bitstrings:

• one each piece @ each square;
• one indicate side move;
• four castling rights;
• eight file of valid en-passant square (if any).

if want zobrist hash code of position, have xor random numbers linked given feature (details: here , correctly implementing zobrist hashing).

e.g starting position:

[hash white rook on a1] xor [white knight on b1] xor ... ( pieces ) ... xor [white castling long] xor ... ( castling rights ) 

xor allows fast incremental update of hash key during make / unmake of moves.

usually 64bit used standard size in modern chess programs (see the effect of hash signature collisions in chess program).

you can expect encounter collision in 32 bit hash when have evaluated √ 2³² == 2¹⁶. 64 bit hash, can expect collision after 2³² or 4 billion positions (birthday paradox).