Problema:

No xadrez, existe uma regra bem conhecida sobre o empate pela repetição. Se a mesma posição for repetida 3 vezes (ou mais), o jogador que pretender fazer a jogada que causará a repetição poderá reivindicar um empate.

Às vezes, essa é uma tarefa fácil para um árbitro detectar, se os últimos movimentos são apenas os jogadores se movendo para trás e para frente. Às vezes é menos trivial, quando as peças se movem significativamente entre posições repetidas.

O problema neste desafio é gerar um valor de verdade se a posição reivindicada for desenhada por repetição (foi vista 3 vezes ou mais) e um valor de falsey se a posição reivindicada não for desenhada por repetição, dada uma lista de movimentos na notação de coordenadas conforme descrito abaixo ou qualquer notação de sua escolha (mas você precisará converter os casos de teste).

O que é uma posição?

Em um cenário do mundo real, a posição seria afetada por coisas como se um jogador pode dominar ou se um passante é possível; você não deve considerá-los na sua solução para o problema. Neste problema, uma posição é definida simplesmente pela configuração das peças no tabuleiro. Portanto, para os propósitos desse problema, duas posições são iguais, se cada quadrado em ambas as placas for ocupado pelo mesmo tipo de peça da mesma cor. Esta não precisa ser a peça exata, por exemplo, os cavaleiros brancos poderiam trocar quadrados e, se todas as outras peças atenderem aos critérios, essa ainda seria a mesma posição.

Como é uma notação válida?

Embora eu continue explicando a notação de coordenadas, você é livre para receber informações do sistema de notação que escolher. Providenciou que:

• Cada item da notação descreve um ou todos: a peça / peças envolvidas; se cheque, xeque-mate, duplo cheque, xeque-mate ou impasse foram entregues; se ocorreu uma captura passante; a posição inicial; a posição final.
• Você pode não ter informações sobre repetição em sua notação.

Portanto, desde que esses critérios sejam atendidos, fico feliz em aceitar, desde que você especifique em sua resposta, seu sistema de anotação. Pode ser, por exemplo, 0 linha indexada, tuplas de coluna ou o que fizer sentido para o seu programa.

Notação de coordenadas

A notação de coordenadas é uma notação que descreve puramente os movimentos como um sistema de coordenadas.

Uma movimentação é descrita como primeiro a coordenada inicial do conjunto {A1-H8}e, em seguida, a coordenada de destino novamente do mesmo conjunto. Assim, o Gambit do rei se pareceria (como uma coleção de cordas)

{"E2-E4","E7-E5","F2-F4"}

Acredito que seja a melhor notação a ser usada para esse problema, pois não está repleta de informações estranhas, como se a verificação ocorreu ou qual é o tipo de peça em movimento. Conforme mencionado anteriormente, a notação pode ser de sua escolha; portanto, você pode usar outra notação, por exemplo, notação algébrica ou adaptar essa notação (por exemplo, remover os traços ou fazer uma lista de tuplas)

Regras:

• Você não deve considerar se uma posição ou movimento é válido, apenas se causa repetição
• Você pode supor que a promoção de castelos e peões não ocorrerá.
• Você deve ter uma lista de strings como entrada e saída de um valor de verdade ou falsey correspondente a se a terceira (ou mais) repetição ocorreu no movimento final
• O jogo sempre começa na posição inicial padrão do xadrez. A posição inicial pode contar para a repetição.
• O empate por repetição não ocorreu se a posição não for repetida pelo movimento final

Regras gerais:

• Isso é código-golfe , então a resposta mais curta em bytes vence.
  Não permita que idiomas com código de golfe o desencorajem a postar respostas com idiomas que não sejam codegolf. Tente encontrar uma resposta o mais curta possível para 'qualquer' linguagem de programação.
• As regras padrão se aplicam à sua resposta com as regras de E / S padrão , para que você possa usar STDIN / STDOUT, funções / método com os parâmetros adequados e programas completos do tipo retorno. Sua chamada.
• As brechas padrão são proibidas.
• Se possível, adicione um link com um teste para o seu código (ou seja, TIO ).
• Além disso, é altamente recomendável adicionar uma explicação para sua resposta.

Casos de teste

Você deve retornar valores de verdade para:

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

E valores de falsey para:

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

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

-4 graças a ngn.

Programa completo. Solicita a lista invertida de pares de coordenadas invertidas:
 por exemplo, {"B1-C3","B8-C6"}é[[[8,2],[6,3]],[[1,2],[3,3]]]

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

Experimente online! (inclui a função de utilitário Coordsque traduz o formato do OP)

Configure uma lista de estados:

s←3 atribuir a três s(para s stados)

Como 3 não é um estado válido do quadro, não afetará nossa contagem de repetições, e precisamos do valor de passagem da tarefa…

Crie uma representação no tabuleiro de xadrez:

5... descarte que para o resultado da aplicação da seguinte função derivada entre 5 e 3:
 ⍥⍳ estender ambos os argumentos aos seus Ɩ ndices;
  [1,2,3,4,5]… [1,2,3]
 ,∘⌽ O lado esquerdo concatenado com o reverso do lado direito
  [1,2,3,4,5,3,2,1]representa os oficiais

⍪ transformar em mesa;
 [[1],
  [2],
  [3],
  [4],
  [5],
  [3],
  [2],
  [1]]

6, prefixar (para cada linha) um seis, representando peões;
 [[6,1],
  [6,2],
  [6,3],
  [6,4],
  [6,5],
  [6,3],
  [6,2],
  [6,1]]

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

¯4↑ tomar negativo (ou seja, o último) quatro (linhas), preenchendo com zeros, representando quadrados vazios;
 [[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]]

(… ) Aplique a seguinte função tácita a isso:

 - negar (isso representa a cor oposta);
  [[ 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]]

  ⊖⍪ empilhe o argumento invertido em cima disso, dando-nos a pensão completa;
  [[ 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]]

Construa uma lista de movimentos seguidos pelo estado inicial:

⊂ inclua que (para tratá-lo como uma única unidade)

⎕, solicitar a lista de movimentos e anexá-lo ao estado inicial

Reduza * por uma função que anexa o estado atual à lista e faz uma jogada:

{… }/ Reduza pela seguinte lambda anônima:

 ⍵ o argumento correto (o estado atual)

 ⊂ coloque-o para tratá-lo como uma unidade

 s,← anexá-lo à lista de estados

 ⊃ divulgá-lo para usar esse estado

 … @⍺ Nos elementos com as duas coordenadas que o argumento esquerdo representa, coloque:
  0 um zero
  , seguido
  ∘ pelo
  ⊃ primeiro valor,
^{esse "move" efetivamente o valor na primeira coordenada para a segunda coordenada, deixando para trás um zero}

Verifique se temos três ou mais do estado final:

s∩ a interseção de todos os estados com aquele final; o subconjunto de estados idênticos a ele

≢ conte-os

2≤ verifique se há dois ou mais (ou seja, três ou mais, incluindo o estado final)

* APL é associativo à direita; portanto, primeiro a função é chamada com o estado inicial como argumento da direita e o movimento inicial como argumento da esquerda e, em seguida, seu resultado, o novo estado, torna-se o novo argumento da direita com o segundo movimento como novo argumento à esquerda etc. O resultado final é o

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}

Experimente online!

-3 bytes graças a Giuseppe
-29 bytes graças ao uso de Nick Kennedy Reducee -rev(l)
-4 bytes ao inverterz

Toma como entrada um vetor de números inteiros entre 1 e 64, indicando os quadrados. O TIO inclui uma função para se transformar nesse formato. As diferentes partes são armazenadas como números inteiros entre 1 e 6 e entre -1 e -6.

Explicação:

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
}

Geléia , 41 37 bytes

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

Experimente online!

Um link monádico que recebe a entrada como uma lista de pares de movimentos principais da linha indexados em 1 [from, to]e retorna um 1 para empates e 0 para não.

Observe que o código do rodapé no TIO converte as movimentações fornecidas pelo OP para o formato numérico, mas, conforme a discussão abaixo da pergunta, o formato numérico teria sido uma entrada válida.

Explicação

Ø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

JavaScript (Node.js) ,  121  111 bytes

[sq0, sq1]$[0..63]$$\text{a8}=0$$\text{b8}=1$$\text{h1}=63$

Retorna um valor booleano.

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

Experimente online!

Quão?

Peças

Os valores usados ​​para identificar as peças realmente não importam, desde que haja um valor único por tipo de peça.

Nós usamos:

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

Conselho e posição inicial

$b$

• '89ABCA981111111' → as 8 peças principais pretas, seguidas pelos 7 primeiros peões pretos
• 10n**32n$\text{h7}$$1$$0$
• 0x7e5196ee74377→ todas as peças brancas (gasta 2222222234567543em decimal)

o que resulta em:

    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

Acompanhar as posições

$b$$b$ e implicitamente coagida a uma sequência.

É por isso que fazemos:

b[b] = -~b[b]

Comentado

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

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 graças a @Arnauld , alterando i%56<8?"ABCDECBA".charAt(i%56%7):i%48<16?1:0parai%56<8?i%8*35%41%10%8+2:9>>i/16&1 .

$a1=0, b1=1, ..., h8=63${"E2-E4",...[[12,28],...

Experimente online.

Explicação:

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

Os valores das peças após preenchê-las A[i]=(i%56<8?i%8*35%41%10%8+2:9>>i/16&1)*(i/32*2-1)são:

     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

Experimente online.

Carvão , 62 bytes

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

Experimente online! Link é a versão detalhada do código. Toma entrada como uma matriz de pares de números, onde os quadrados são numerados A1, B1, ... H8(0-indexada), de modo, por exemplo, o primeiro caso de teste seria representado como [[[1, 18], [57, 42], [18, 1], [42, 57], [1, 18], [57, 42], [18, 1], [42, 57]]]e emite um -, se a posição é uma tração por repetição. Programa de conversão. Tudo em um. Explicação:

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

Divida o número 23456432em dígitos individuais. Estes representam as peças brancas.

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

Adicione os peões e as linhas vazias. Os peões brancos têm valor 1e os peões pretos -1.

Ｆ…η⁸⊞η±ι

Anexe uma cópia negada das peças brancas, que representam as peças pretas.

Ｆθ«

Faça um loop sobre os movimentos.

⊞υ⮌η

Salve uma cópia do quadro. (Reversão é a maneira mais divertida de copiar o quadro.)

§≔η⊟ι§η§ι⁰

Atualize o destino com a peça de origem.

§≔η⊟ι⁰

Retire a peça de origem.

»›№υ⮌η¹

Determine se a posição atual foi vista mais de uma vez antes.

C # (compilador interativo do Visual C #) , 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;}

Recebe a entrada como uma lista de tuplas de números inteiros, de onde o primeiro número inteiro é para onde se mover e o segundo é para onde se mover. 0 representa A1, 1 é A2 e 63 é H8.

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

JDK (Java) , 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;}

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