what is the fastest way to check 3repetition of chess position?

Question

I am wirting chess Ai as a project. if positon repetes 3 times it is a draw I can create array with all previus position then get every updated position iterete over every previus one of them and see if we have 2 same position in array. but this seem like a lot of work for computer and it will make calculating moves for Ai hard. is there any better way to do this?

Answer 1

I would suggest using Zobrist Hashing, which is designed to handle this kind of situation. Simply store a list of hash values for each position as you go along. You could also use a Bloom Filter.

It does not matter so much if you get some false positives if you keep track of the actual board configurations as well, so if you do get a collision, you can then quickly check if you have come across the current position before; this should not happen very often if you use sufficiently large hash values.

Answer 2

As Oliver mentioned in his answer you should use something like Zobrist Hashing, each position then have an (almost) unique number. Zobrist Hashing is hard to implement so you need to make sure your implementation is bug free, which is easier said than done. You then store this value in a list or similar that you loop over backwards to find how many time the same position has occured.

To make the lookup faster you only need to loop each other step since you are checking for a specific colors turn. You can also break the loop immediately if you find a pawn move or a capture since these moves make the position impossible to be repeated again.

You can look at Chessprogrmaming - Repetitions for more inspiration, especially the header "List of Keys".