i'm working on a chess app for android (no AI--i'm just wanting to do a really good ChessWithFriends since the ones currently out there get bad reviews) and am ironing out some final aspects of the game logic.
I'm finding it a bit tricky to implement the rules for draw by repetition (the 50-move rule, by contrast, is easy, although it doesn't happen in practice nearly as often). according to wikipedia, the rule is that on your move you can declare a draw if one of the following conditions hold:
1) the current position has occurred 3 times (including the current instance)
2) you can make a move such that the position after your move will have occurred 3 times altogether.
Additional nuances: identity of position includes:
a) whose move it is (same pieces on same squares with black to move != same pieces on same squares with white to move)
b) the right to take something en passant
c) the right to castle
Dealing with the nuances will add a little run-time, but that's not the bad part really. It's keeping the number of times that you exhaustively check all 64 squares as low as possible--in actuality, even that MIGHT not be horrible, but i'd like to keep the speed and resource usage as low as i can within reason.
Here's what I have stored in a Position class, which stores the position, checks moves against the rules, and provides public methods as necessary for the android GUI to use: an int array that stores the current position (each piece has a code), and an ArrayList<Move> where a move object is a source square, a target square, and a piece code (int).
In practice, I'm thinking that it's probably better just to narrow down the positions that need to be checked rather than to try thinking of some fancy way to get a fast hash on positions and look for identical hash codes.
So, what I was thinking was to make an initial loop in which I run through the move list looking for the following actions:
1) moving a pawn
2) taking an opponent's piece
My claim is that you only have to start comparing positions on the first position after such a move.
Then I guess just start at that position, compare it to current, terminate the comparison and move to next position if any square is non-identical.
Then do the same thing for each position that arises out of a non-taking, non-pawn, non-castling move in the current position to test for threefold repetition of a move that CAN be made.
Anyone have a better way of doing this?