13
2
Problem:
In chess, there is a somewhat well known rule about draw by repetition. If the same position is repeated 3 times (or more) then the player intending to make the move which will cause the this repetition can claim a draw.
Sometimes this is an easy task for an arbiter to spot, if the last few moves are just the players moving backwards and forwards. Sometimes it is less trivial, when pieces have moved significantly between repeated positions.
The problem in this challenge is to output a truthy value if the claimed position is draw by repetition (has been seen 3 times or more) and a falsey value if the claimed position is not draw by repetition, given a list of moves in coordinate notation as described below, or any notation of your choosing (but you'll have to convert the test cases).
What is a position?
In a real world scenario, the position would be affected by things such as whether a player can castle or whether en-passant is possible; you should not consider these in your solution to the problem. In this problem a position is defined simply by the configuration of the pieces on the board. So, for the purposes of this problem, two positions are seen to be the same if each square on both boards is occupied by the same type of piece of the same colour. This does not have to be the exact piece for example white's knights could swap squares and if all other pieces fulfill the criteria this would still be the same position.
What does a valid notation look like?
Although I will go on to explain coordinate notation, you are free to take input by a notation system you choose. Provided that:
- Each item in the notation describes any or all of: the piece/pieces involved; whether check, checkmate, double check, checkmate or stalemate have been delivered; if en-passant capture has occurred; the initial position; the final position.
- You may not have information about repetition in your notation.
So as long as these criteria are met I am happy to accept, as long as you specify in your answer, your notation system. This could be e.g. 0 indexed row,column tuples or whatever makes sense for your program.
Coordinate Notation
Coordinate notation is a notation which describes purely the moves as a system of coordinates.
A move is described as first the initial coordinate from the set {A1-H8}
and then the destination coordinate again from the same set. So the King's Gambit would look like (as a collection of strings)
{"E2-E4","E7-E5","F2-F4"}
I believe it's the best notation to use for this problem because it is not littered with extraneous information like whether check has occurred or what the type of piece moving is. As mentioned before the notation can be of your choice, so you could use another notation e.g. algebraic notation or you could adapt this notation (e.g. remove the dashes, or take as a list of tuples)
Rules:
- You should not consider whether a position or move is valid, only whether it causes repetition
- You can assume that castling and pawn promotion will not occur.
- You should take a list of strings as input and output a truthy or falsey value corresponding to whether the third (or more) repetition has occurred on the final move
- The game always starts at the standard starting position for chess. The initial position can count towards repetition.
- Draw by repetition has not occurred if the position is not repeated by the final move
General rules:
- This is code-golf, so shortest answer in bytes wins.
Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language. - Standard rules apply for your answer with default I/O rules, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters and return-type, full programs. Your call.
- Default Loopholes are forbidden.
- If possible, please add a link with a test for your code (i.e. TIO).
- Also, adding an explanation for your answer is highly recommended.
Test Cases
You should return truthy values for:
{"B1-C3","B8-C6","C3-B1","C6-B8","B1-C3","B8-C6","C3-B1","C6-B8"}
{"B1-C3","B8-C6","C3-B1","C6-B8","B1-C3","B8-C6","C3-B1","C6-B8","B1-C3","B8-C6","C3-B1","C6-B8"}
{"B1-C3","B8-C6","D2-D4","D7-D5","D1-D3","D8-D6","C3-B1","C6-B8","B1-C3","B8-C6","D3-D1","D6-D8","D1-D3","D8-D6"}
{"D2-D4","B8-C6","E2-E4","C6-D4","D1-E2","D4-E6","E2-F3","E6-D4","F3-D1","D4-C6","D1-E2","C6-D4","E1-D1","D4-C6","D1-E1","C6-D4"}
{"B1-C3","B8-C6","C3-B1","C6-B8","B1-C3","B8-C6","C3-B1","C6-B8","B1-C3","B8-C6","C3-B1","C6-B8","B1-C3"}
And falsey values for:
{}
{"E2-E4","E7-E5","F2-F4"}
{"B1-C3","B8-C6","C3-B1","C6-B8","B1-C3","B8-C6","C3-B1","C6-B8","F2-F4","F7-F5"}
{"E2-E4","E7-E5","G1-F3","B8-C6","F1-C4","G8-F6","F3-G5","D7-D5","E4-D5","F6-D5","G5-F7"}
{"D2-D4","B8-C6","E2-E4","C6-D4","D1-E2","D4-C6","E2-D1","C6-D4","D1-E2","D4-C6","E2-D1"}
{"B1-C3","B8-C6","C3-B5","C6-B4","B5-D4","B4-D5","D4-C6","D5-C3","C6-B8","C3-B1","B8-C6","B1-C3","C6-B8","C3-B1"}
{"E2-E4","E7-E5","D1-E2","E8-E7","E1-D1","D8-E8","E2-E1","E7-D8","E1-E2","E8-E7","E2-E1","E7-E8"}
Can we take input as, say, a list of pairs of squares numbered in a row-major order, getting rid of chess entirely? How about a list of pairs of pairs of coordinates? – my pronoun is monicareinstate – 2019-04-02T12:57:22.677
You won't be able to get rid of chess entirely, since the pieces themselves and capturing pieces are both still important. You can define your coordinate system however you like though. I'll clarify in the question what properties a valid set of inputs will have. – Expired Data – 2019-04-02T13:00:15.443
Are you sure the last two test cases are indeed falsey? There could be an error in my implementation of course, in which case I'll look for an error, but I come across a state 3 times in both last two falsey test cases. PS: You might want to explicitly mention that the initial state before beginning the match doesn't count towards the 3 times? EDIT: Ah wait, I think I completely miss-implemented the challenge.. The piece type in the occupied cells are important for a state as well I guess? I now have all cells as a toggle whether a piece is on it or not, instead of which piece is on it.. >.> – Kevin Cruijssen – 2019-04-02T13:21:51.757
Can we assume pawn promotion has not occurred? And what is the input format for the initial position? – my pronoun is monicareinstate – 2019-04-02T13:22:45.743
@someone yes I meant to put that in about no pawn promotion. Initial position is not inputted, you will have to store it – Expired Data – 2019-04-02T13:29:37.477
1@KevinCruijssen I'll explicitly add that the initial state DOES count. I think you spotted that the pieces matter, so do the colour of the piece. The second last test case is where black and white's knights swap over. In the last one the queen and king swap around for both players – Expired Data – 2019-04-02T13:31:39.917
1@ExpiredData Can you explain why the 3rd falsey case is falsey? After the last
C6-B8
the initial position has occurred thrice. – Adám – 2019-04-02T13:35:09.4372Ah, it has to be the final position that appeared at least twice before. – Adám – 2019-04-02T13:37:16.287
@Adám from the Fide Laws of chess 9.2.1 The game is drawn, upon a correct claim by a player having the move, when the same position for at least the third time (not necessarily by a repetition of moves): 9.2.1.1 is about to appear, if he first writes his move, which cannot be changed, on his scoresheet and declares to the arbiter his intention to make this move, or 9.2.1.2 has just appeared, and the player claiming the draw has the move. So it's when it's the last move on the scoresheet given to the arbiter...
– Expired Data – 2019-04-02T13:42:35.050