Is this draw by repetition?

Question

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"}

Answer 1

APL (Dyalog Extended), 55 49 47 45 44 bytes^SBCS

-4 thanks to ngn.

Full program. Prompts for reversed list of reversed coordinate pairs:
 e.g. {"B1-C3","B8-C6"} is [[[8,2],[6,3]],[[1,2],[3,3]]]

2≤≢s∩{0,∘⊃@⍺⊃s,←⊂⍵}/⎕,⊂(⊖⍪-)¯4↑⍉6,⍪5,∘⌽⍥⍳s←3

Try it online! (includes the utility function Coords which translates OP's format)

Set up a list of states:

s←3 assign three to s (for states)

Since 3 is not a valid board state, it will not affect our repetition count, and we need the pass-through value of the assignment…

Build a chess board representation:

5… discard that for the result of applying the following derived function between 5 and 3:
 ⍥⍳ extend both arguments to their ɩndices;
  [1,2,3,4,5]…[1,2,3]
 ,∘⌽ the left side concatenated with the reverse of the right side
  [1,2,3,4,5,3,2,1] this represent the officers

⍪ make into table;
 [[1],
  [2],
  [3],
  [4],
  [5],
  [3],
  [2],
  [1]]

6, prepend (to each row) a six, representing pawns;
 [[6,1],
  [6,2],
  [6,3],
  [6,4],
  [6,5],
  [6,3],
  [6,2],
  [6,1]]

⍉ transpose;
 [[6,6,6,6,6,6,6,6],
  [1,2,3,4,5,3,2,1]]

¯4↑ take negative (i.e. the last) four (rows), padding with zeros, representing empty squares;
 [[0,0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0,0],
  [6,6,6,6,6,6,6,6],
  [1,2,3,4,5,3,2,1]]

(…) apply the following tacit function to that:

 - negate (this represents the opposite colour);
  [[ 0, 0, 0, 0, 0, 0, 0, 0],
   [ 0, 0, 0, 0, 0, 0, 0, 0],
   [-6,-6,-6,-6,-6,-6,-6,-6],
   [-1,-2,-3,-4,-5,-3,-2,-1]]

  ⊖⍪ stack the flipped argument on top of that, giving us the full board;
  [[ 1, 2, 3, 4, 5, 3, 2, 1],
   [ 6, 6, 6, 6, 6, 6, 6, 6],
   [ 0, 0, 0, 0, 0, 0, 0, 0],
   [ 0, 0, 0, 0, 0, 0, 0, 0],
   [ 0, 0, 0, 0, 0, 0, 0, 0],
   [ 0, 0, 0, 0, 0, 0, 0, 0],
   [-6,-6,-6,-6,-6,-6,-6,-6],
   [-1,-2,-3,-4,-5,-3,-2,-1]]

Construct a list of moves followed by the initial state:

⊂ enclose that (to treat it as a single unit)

⎕, prompt for the list of moves, and prepend that to the initial state

Reduce* by a function which appends the current state to the list and makes a move:

{…}/ reduce by the following anonymous lambda:

 ⍵ the right argument (the current state)

 ⊂ enclose it to treat it as a unit

 s,← in-place append it to the list of states

 ⊃ disclose it to use that state

 …@⍺ at the elements with the two coordinates that the left argument represents, put:
  0 a zero
  , followed
  ∘ by
  ⊃ the first value
^{this effectively "moves" the value at the first coordinate to the second coordinate, leaving behind a zero}

Check if we have three or more of the final state:

s∩ the intersection of all states with that final one; the subset of states identical to it

≢ tally them up

2≤ check if there are two or more (i.e. three or more including the final state)

---

* APL is right-associative, so first the function is called with the initial state as right argument and the initial move as left argument, and then its result, the new state, becomes the new right argument with the second move as new left argument, etc. The final result is the

Answer 2

R, 180 177 144 bytes

function(M,`+`=rep,l=c(1:5,3:1,6+8,0+16)){z=rev(Reduce(function(x,y){x[y[2:1]]=x[y]*1:0;x},M,c(l,-rev(l)),,T));sum(sapply(z,identical,el(z)))>2}

Try it online!

-3 bytes thanks to Giuseppe
-29 bytes thanks to Nick Kennedy's use of Reduce and -rev(l)
-4 bytes by reversing z

Takes as input a vector of integers between 1 and 64 denoting the squares. The TIO includes a function to transform into that format. The different pieces are stored as integers between 1 and 6 and between -1 and -6.

Explanation:

function(M,                                # M is the vector of moves 
         `+` = rep,
         l = c(1:5, 3:1, 6 + 8, 0 + 16)) { # initial position of white pieces
  z = rev(Reduce(function(x, y) {
    x[y[2:1]] = x[y] * 1:0                 # a piece moves from y[1] to y[2]; y[1] becomes 0
    x
  }, M, c(l, -rev(l)), , T))
  sum(sapply(z, identical, el(z))) > 2    # find number of past positions identical to the last position
}

Answer 3

Jelly, 41 37 bytes

Ø0;6x8;“Ġ²F’D¤UN;ƊW;µị@⁹Ṫ¤¦0⁹¦$\ċṪ$>1

Try it online!

A monadic link that takes the input as a list of pairs of 1-indexed row-major moves [from, to] and returns a 1 for draws and 0 for not.

Note the footer code on TIO translates the moves as supplied by the OP to the numeric format, but per the discussion below the question, the numeric format would have been a valid input.

Explanation

Ø0                                    | 0,0
  ;6                                  | concatenate to 6 (pawn)
    x8                                | repeat each 8 times (two blank rows and 1 row of pawns)
      ;“Ġ²F’D¤                        | concatenate to 1,2,3,4,5,3,2,1
              UN;Ɗ                    | concatenate a negated flipped version to this one
                  W;                  | wrap as a list and concatenate the input list to the board
                    µ                 | start a new monadic chain
                              $\      | reduce using the two links below
                     ị@⁹Ṫ¤¦           | replace the item pointed to by the second coordinate by the value of the one at the first
                           0⁹¦        | replace the item at first coordinate with zero
                                ċṪ$   | finally count the items equal to the final one (not including it)
                                   >1 | and check of >1

Answer 4

JavaScript (Node.js),  121  111 bytes

Expects the moves in [sq0, sq1] format, where each square is in \$[0..63]\$ with \$\text{a8}=0\$, \$\text{b8}=1\$, ..., \$\text{h1}=63\$.

Returns a Boolean value.

a=>[a,...a].map(([x,y])=>r=b[b[b[y]=b[x],x]=0,b]=-~b[b],b=[...'89ABCA981111111'+10n**32n+0x7e5196ee74377])&&r>2

Try it online!

How?

Pieces

The values used to identify the pieces do not really matter as long as there's one unique value per piece type.

We use:

• 0 for empty squares
• 1 / 8 / 9 / A / B / C for ♟ / ♜ / ♞ / ♝ / ♛ / ♚
• 2 / 3 / 4 / 5 / 6 / 7 for ♙ / ♖ / ♘ / ♗ / ♕ / ♔

Board and initial position

The board is stored in the array \$b\$ which is initialized by splitting the concatenation of the following parts:

• '89ABCA981111111' → the 8 black major pieces, followed by the first 7 black pawns
• 10n**32n → the last black pawn on \$\text{h7}\$ (\$1\$) followed by 32 empty squares (\$0\$)
• 0x7e5196ee74377 → all white pieces (expends to 2222222234567543 in decimal)

which results in:

    a b c d e f g h
  +----------------
8 | 8 9 A B C A 9 8
7 | 1 1 1 1 1 1 1 1
6 | 0 0 0 0 0 0 0 0
5 | 0 0 0 0 0 0 0 0
4 | 0 0 0 0 0 0 0 0
3 | 0 0 0 0 0 0 0 0
2 | 2 2 2 2 2 2 2 2
1 | 3 4 5 6 7 5 4 3

Keeping track of the positions

The variable \$b\$ is also used as an object to keep track of all encountered positions. The key for each position is \$b\$ itself, but this time as an array and implicitly coerced to a string.

This is why we do:

b[b] = -~b[b]

Commented

a =>                    // a[] = input
  [ a,                  // dummy entry to mark the initial position as encountered once
    ...a                // append the actual data
  ].map(([x, y]) =>     // for each pair of squares [x, y] in this array:
    r =                 //   store the last result in r
    b[                  //   update b[b]:
      b[                //     update b[x]:
        b[y] = b[x],    //       set b[y] to b[x]
        x               //       set b[x] ...
      ] = 0,            //     ... to 0
      b                 //     set b[b] ...
    ] = -~b[b],         //   ... to b[b] + 1 (or 1 if b[b] is undefined)
    b = [...(…)]        //   initialize b[] (see above)
  )                     // end of map()
  && r > 2              // return true if the last result is greater than 2

Answer 5

Java 10, 336 330 287 285 282 276 bytes

m->{var V=new java.util.HashMap();int i=64,A[]=new int[i];var t="";for(;i-->0;)t+=A[i]=(i%56<8?i%8*35%41%10%8+2:9>>i/16&1)*(i/32*2-1);V.put(t,1);for(var a:m){for(t="",A[a[1]]=A[a[0]],A[a[0]]=0,i=64;i-->0;)t+=A[i];V.compute(t,(k,v)->v!=null?(int)v+1:1);}return(int)V.get(t)>2;}

-11 bytes thanks to @Arnauld by changing i%56<8?"ABCDECBA".charAt(i%56%7):i%48<16?1:0 to i%56<8?i%8*35%41%10%8+2:9>>i/16&1.

Input as a 2D array of integers where \$a1=0, b1=1, ..., h8=63\$ (i.e. {"E2-E4",... is [[12,28],...).

Try it online.

Explanation:

m->{                   // Method with 3D character array parameter and boolean return-type
  var V=new java.util.HashMap();
                       //  Create a Map to store the occurrences of the board-states
  int i=64,            //  Index integer, starting at 64
      A[]=new int[i];  //  Create the 8 by 8 board
  var t="";            //  Temp-String, starting empty
  for(;i-->0;)         //  Loop `i` in the range (64,0]:
    t+=                //    Append the string `t` with:
      A[i]=            //     Fill the `i`'th cell with:
        i%56<8?        //      If it's either the first or eighth row:
         i%8*35%41%10%8+2
                       //       Fill it with 2,7,3,5,9,3,7,2 based on index `i`
        :9>>i/16&1)    //      Else if it's either the second or seventh row:
                       //       Fill it with 1
                       //      Else (the third, fourth, fifth, or sixth rows):
                       //       Fill it with 0
        *(i/32*2-1);   //      Then multiply it by -1 or 1 depending on whether `i`
                       //      is below 32 or not
  V.put(t,1);          //  Then set string `t` in the map to 1 for the initial state
  for(var a:m){        //  Loop over each of the input's integer-pairs:
    for(t="",          //   Make the String empty again
        A[a[1]]=       //   Set the to-cell of the current integer-pair of the input to:
          A[a[0]],     //    The value in the from-cell of the same integer-pair
        A[a[0]]=0,     //   And then empty this from-cell
        i=65;i-->0;)   //   Inner loop `i` in the range (64,0]:
          t+=A[i];     //    Append the `i`'th value to the String `t`
    V.compute(t,(k,v)->v!=null?(int)v+1:1);}
                       //   Increase the value in the map for String `t` as key by 1
  return(int)V.get(t)  //  Return whether the value in the map for the last String `t`
          >2;}         //  is at least 3

The values of the pieces after filling them with A[i]=(i%56<8?i%8*35%41%10%8+2:9>>i/16&1)*(i/32*2-1) are:

     a  b  c  d  e  f  g  h
  +------------------------
1 | -2 -7 -3 -5 -9 -3 -7 -2
2 | -1 -1 -1 -1 -1 -1 -1 -1
3 |  0  0  0  0  0  0  0  0
4 |  0  0  0  0  0  0  0  0
5 |  0  0  0  0  0  0  0  0
6 |  0  0  0  0  0  0  0  0
7 |  1  1  1  1  1  1  1  1
8 |  2  7  3  5  9  3  7  2

Try it online.

Answer 6

Charcoal, 62 bytes

≔↨²³⁴⁵⁶⁴³²χηＦ⁴⁸⊞η÷⁻⁴⁰ι³²Ｆ…η⁸⊞η±ιＦθ«⊞υ⮌η§≔η⊟ι§η§ι⁰§≔η⊟ι⁰»›№υ⮌η¹

Try it online! Link is to verbose version of code. Takes input as an array of pairs of numbers where the squares are numbered A1, B1, ... H8 (0-indexed) so for instance the first test case would be represented as [[[1, 18], [57, 42], [18, 1], [42, 57], [1, 18], [57, 42], [18, 1], [42, 57]]] and outputs a - if the position is a draw by repetition. Conversion program. All in one. Explanation:

≔↨²³⁴⁵⁶⁴³²χη

Split the number 23456432 into individual digits. These represent the white pieces.

Ｆ⁴⁸⊞η÷⁻⁴⁰ι³²

Add in the pawns and the empty rows. The white pawns have value 1 and the black pawns -1.

Ｆ…η⁸⊞η±ι

Append a negated copy of the white pieces, which represent the black pieces.

Ｆθ«

Loop over the moves.

⊞υ⮌η

Save a copy of the board. (Reversing is the golfiest way to copy the board.)

§≔η⊟ι§η§ι⁰

Update the destination with the source piece.

§≔η⊟ι⁰

Remove the source piece.

»›№υ⮌η¹

Determine whether the current position was seen more than once before.

Answer 7

C# (Visual C# Interactive Compiler), 204 bytes

n=>{var j=new List<char[]>();var d=("ABCDECBATTTTTTTT"+new string('Z',32)+7777777712345321).ToArray();foreach(var(a,b)in n){j.Add(d.ToArray());d[b]=d[a];d[a]='Z';}return j.Count(r=>r.SequenceEqual(d))>1;}

Takes input as a list of tuples of integers, where the first integer is where to move from, and the second is where to move to. 0 represents A1, 1 is A2, and 63 is H8.

Try it online!

n=>{
  var j=new List<char[]>();    //Initialize a list to save states of a board
  var d=("ABCDECBATTTTTTTT" +  //White pieces
  new string('Z',32) +         //Empty spaces
  7777777712345321)            //Black pieces
  .ToArray(); //Initialize the chessboard
  foreach(var(a,b)in n){       //Foreach (source square, destination square) in the input
    j.Add(d.ToArray());        //  Add the current board to the list
    d[b]=d[a];                 //  Set the destination square to the source square's value
    d[a]='Z';                  //  And set the souce square to empty
  }
  return j.Count(         //Return that the amount...
    r=>r.SequenceEqual(d) //  of past positions that are equal to the current position...
  )>1;                    //is at least two
}

Answer 8

Java (JDK), 246 245 244 bytes

import java.util.*;n->{var j=new ArrayList<char[]>();var d=("ABCDECBATTTTTTTT"+"
".repeat(32)+7777777712345321l).toCharArray();for(var k:n){j.add(d.clone());d[k[1]]=d[k[0]];d[k[0]]=1;}return j.stream().filter(x->Arrays.equals(d,x)).count()>1;}

Try it online!

import java.util.*;                   //Import the java.util package

n->{                                  //Function taking in int[][], 
                                      //where each int[] is a a pair of numbers
  var j = new ArrayList<char[]>();    //List to save each position of the chessboard
  var d =                             //The chessboard's starting position
    ("ABCDECBATTTTTTTT" +             //  All the white pieces
    "&#1".repeat(32) +                //  Plus the empty squares
    7777777712345321l)                //  And the black pieces
  .toCharArray();                     //Split to array of chars
  for(var k:n){                       //Foreach [sourceSquare, destinationSquare] in input
    j.add(d.clone());                 //  Add the current position to the list
    d[ k[1] ] = d[ k[0] ];            //  Set the destination square's value
                                      //  to the source squares
    d[ k[0] ] = 1;                    //  And clear the source square 
}                                     //End foreach
return j.stream()                     //Convert list of states to stream
  .filter(x ->                        //Filter each position by
    Arrays.equals(d,x)                //  if the position equals the final position 
  ).count() > 1;                      //And return if there are at least two
                                      //positions that are left
}