Draw detection via Zobrist hashes in Position

[nvanderw]

Currently chessIO has no efficient way to detect {three,five}fold repetition draws from a given position, i.e. to tell how many times the position has occurred. The way some modern chess implementations handle this is maintaining a position hash as part of the position data type, and also storing a linked list of hashes of the previous board states (see e.g. Stockfish). Since recomputing the hash of the entire board each move would be expensive, Zobrist hashing is used to quickly update the hashes with only the changed elements of the board.

(Optimization: in order to detect if a given position is a draw by repetition, we only need to know about the prior board states since the last pawn move or capture.)

chessIO already has some Zobrist hashing code in the Polyglot module, but no support for incrementally updating the hashes. So I've moved that hashing logic under Game.Chess.Internal.

After applying a move to a position in unsafeDoPly, I've added a step to XOR the before and after bitboards together -- any 1s indicate changes to the board state. For each detected change to the board state, unsafeDoPly looks up the corresponding hash in the Zobrist tables and XORs it with the position hash.

As of 2022-4-12 I'm still ironing out some bugs in the hashing implementation. And then the next step is to implement the hash history updating/searching. But thought I'd send this out for an early review in the meantime. Also: exposing position hashes to library clients would allow them to use transposition tables.

[oskarpyk]

@nvanderw Glad to see you're working on this; ChessIO is a key library in a project I'm working on. Would you say your threefold-repetition detection is production ready?

[mlang]

Hi. Sorry for the delay, I didnt spent much time on a computer during summeer time.

I am about to merge this PR, however, during review I found anyBits and I am a bit confused why you define it. Either I am not awake yet, or anyBits is equivalent to occupied. ORing the black pieces to all occupied pieces is a no-op.

[nvanderw]

Hi. Sorry for the delay, I didnt spent much time on a computer during summeer time.

I am about to merge this PR, however, during review I found anyBits and I am a bit confused why you define it. Either I am not awake yet, or anyBits is equivalent to occupied. ORing the black pieces to all occupied pieces is a no-op.

Hey Mario, thanks for reviewing. Sorry for delay on my end, hope all is well for you. I think your read is right here and perhaps I was not awake yet when I wrote that piece. I think we can just use occupied. Will give that a try and re-run the tests to be sure.

[nvanderw]

@nvanderw Glad to see you're working on this; ChessIO is a key library in a project I'm working on. Would you say your threefold-repetition detection is production ready?

It is designed to be, and I've added test coverage to ensure the hashing works the way I expect, but I'm loath to claim that there are no bugs etc. I'd be curious to hear you try it out and tell me your experience.