Implemented Threefold repetition check

[joee-ca]

I just finished implementing Threefold repetition check and its relative test.

Looking a bit on the internet I found out that usually people use Zobrist Hashing to store chess positions in a dictionary and check the repetition, but I decided to use Swift Hasher for simplicity. If you later want to implement it through Zobrist you can still do it, since the hashing is done separately (if you want I can implement it when I find some time). Other than that the function also support FivefoldRepetition. It all depends on the "times" parameter used in the function. I tried to respect your will to delegate the check to the Board, but I'm concerned about the actual possibility of storing positions that are a result of game PGN moves into the gamePositions dictionary inside "Board".

I hope everything is fine. Tell me if there is any error 😊

[joee-ca]

I did every change you requested, but: 1- I had to add conformance function hash to make Position class Hashable 2- Since positionHashCounts is now private, I had to add a function to retrieve that variable for the test

Also I fixed a problem related to the FEN notation. Basically you were adding the enPassant square to it every time a player moved a pawn by 2 squares, but that is not the only condition that allows enPassant. I added sideSquares variable to Piece to check if there were any pawns on the side of the the one that moved by 2 squares, and if so the enPassant would be added to the notation.

Hope everything is clear 😄

[joee-ca]

Thinking about it, the enPassant square should not be written inside the FEN notation also if it leads to a check, so I added another check to avoid it

[pdil]

Thinking about it, the enPassant square should not be written inside the FEN notation also if it leads to a check, so I added another check to avoid it

@joee-ca, in FEN the en passant is notated whenever a pawn has moved two squares, even if there is no piece to capture, see here:

En passant target square: This is a square over which a pawn has just passed while moving two squares; it is given in algebraic notation. If there is no en passant target square, this field uses the character "-". This is recorded regardless of whether there is a pawn in position to capture en passant. An updated version of the spec has since made it so the target square is recorded only if a legal en passant capture is possible, but the old version of the standard is the one most commonly used.

In any case if the change were to be made I would prefer it to be in a separate PR so we can keep this one focused on the repetition checks.

[joee-ca]

I can revert all the changes and make the clock Hashable but there are 2 problems:

Problem number 1

If we keep:

if abs(start.rank.value - end.rank.value) == 2 {
         position.enPassant = EnPassant(pawn: updatedPiece)
   }

in Board like you said we will have problem in checking for threefold repetition, since 2 positions will be considered different even tho the POSSIBILITY TO EXECUTE the enPassant is the same.

Problem number 2

Making the clock Hashable and using the default implementation of .hashValue modifier on Position will return every time a different value.

For point n.1, to implement things like you said, we should change the way FEN string is written or find some kind of workaround, because enPassant rights are written if position.enPassant is not nil:

if let enPassant = position.enPassant {
            fen += "\(enPassant.captureSquare) "
        } else {
            fen += "- "
        }

Basically we should do something like if lastMove == pawnMovedBy2 to write the FEN, because the possibility to execute enPassant is different from having targeted square inside the FEN.

On the other hand, for what regards point n.2, I think it's better to keep things like they are right now (defining hash function), but suggestions are appreciated.

Tell me what you think so that I can start working on it 😄

[pdil]

@joee-ca

Ah ok, regarding the Clock yes I guess we can't include that in the hash or every position will appear different, good point.

As for en passant, I'm having trouble understanding. We reset enPassant to nil if the player does not capture en passant, so on the next iteration of the move it will appear different which is correct because the positions are not considered repeated if the player was able to en passant on one turn and then not able to on another.

Quoting here:

Positions are considered the same if (1) the same player has the move, (2) pieces of the same kind and color occupy the same squares, and (3) the possible moves of all the pieces are the same. Under (3) above, positions are not considered to be the same if: (a) in the first position, a pawn could have been captured en passant (by the en passant rule, in the subsequent positions, the pawn cannot be captured en passant anymore), or (b) either player has lost a right to castle, i.e. either king or one of the rooks has been moved, in between repetitions of the position.

[joee-ca]

Sorry, I'm bad at explaining things 😅. I will try to be as clear as possible. EnPassant is not nil when a player moves a pawn by 2 squares. Now let's do a quick example:

PGN Notation

1. e4 e5 -> classic pawn moves 2. Nf3 Nf6 -> moving knights forward 3. Ng1 Ng8 -> moving knights back

Now after 1 .e4 e5 and 3. Ng1 Ng8 the position will be exactly the same, but since on move 1 the pawn has moved from e7 to e5, the enPassant will not be nil, hence the hashed value will be different even tho it should not.

This is the reason why it brings problem to the threefold repetition check. We should divide the possibility to actually execute the enPassant from the need of writing the target square into the FEN notation. One solution could also be storing all the legal moves inside the Position, so that we don't pass enPassant + legalCastlings but only the legalMoves array.

I hope I explained myself well 😅

P.S: you should change the documentation of enPassant in Position.swift, since the value is not nil if a player moved a pawn by 2 squares, not if there is the possibility to execute the enPassant.

[pdil]

@joee-ca

In Board.move(pieceAt:to:) we do the following:

        if piece.kind == .pawn,
           let enPassant = position.enPassant,
           enPassant.pawn.color == piece.color.opposite,
           end == enPassant.captureSquare {
            position.remove(enPassant.pawn)
            position.move(piece, to: end)
            return process(move: Move(result: .capture(enPassant.pawn), piece: piece, start: start, end: end))
        } else {
            position.enPassant = nil     // prevent en passant on next turn
        }

which resets enPassant on the following move if it's not taken. Come to think of it we should probably call position.enPassant = nil in both cases of the if statement.

I agree the documentation needs to be updated to be more clear.

[joee-ca]

I agree that on next move It will be put to nil, but not for the current one. I mean if I do 1.e4 e5 there should be no enPassant since there is no white pawn that can capture and go on e6

[pdil]

@joee-ca ok yeah now I see what you're saying! Sorry for the misunderstanding.

Yeah this is tricky because we still need EnPassant to be set whenever a pawn moves two squares for writing the FEN.

What we can do is add a property to Position that we modify in the Board.move(pieceAt:to:) function where you added the check as needed when a pawn moves by 2 squares. Something like var enPassantIsPossible: Bool (in Position). Then in the Position.hash(into:) function we check:

if enPassantIsPossible {
    hasher.combine(enPassant)
}

We just have to be very careful and make sure enPassantIsPossible is set correctly each time a move is made. I'm open to other suggestions too but I think this way satisfies the repetition check and the FEN notation requirements.

[joee-ca]

@pdil I have two suggestions:

1- We could add a property to Position that we modify on Board.move called targetSquare. Basically its type is Square? and we can make It equal to EnPassant(updatedPiece).captureSquare after a pawn move by 2 squares. After that we run other checks to see if enPassant is possible and, if it is, we put position.enPassant = EnPassant(updatedPiece). Than inside FENParser we can do if let square = position.targetSquare { fen += "\(square) " } else { fen += "- "}

2- We can add the property enPassantIsPossible to position, but then we don't use it like you said, because it would make no difference

if enPassantIsPossible {
    hasher.combine(enPassant)
    // hashing or not hashing the enPassant would make no difference. The important thing is having it nil or not according to the position
}

We could do something like this in Board.process:

if !enPassantIsPossible {
   positionHashCounts[position.hashValue, default: 0] += 1
}

Basically if the enPassant is possible, we don't put that position inside the positionHashCounts dictionary. Why? Because on next move it won't be available anymore. This means that every position with an enPassant possibility is unique and can appear maximum 1 time per game, so we don't need to count it for three/five-fold repetition.

Among these options, I think the 1st is the best, but for sure there is something better that I'm missing. I will try to find it in the meanwhile. Tell me if you had any other idea 🥲