Não é estritamente uma pergunta, é mais um quebra-cabeça ...

Ao longo dos anos, estive envolvido em algumas entrevistas técnicas de novos funcionários. Além de fazer as perguntas padrão "você conhece a tecnologia X", também tentei sentir como eles abordam os problemas. Normalmente, eu enviaria a eles a pergunta por e-mail um dia antes da entrevista e espero que eles encontrem uma solução no dia seguinte.

Freqüentemente, os resultados seriam muito interessantes - errados, mas interessantes - e a pessoa ainda receberia minha recomendação se pudesse explicar por que escolheu uma abordagem específica.

Então pensei em lançar uma das minhas perguntas para o público do Stack Overflow.

Pergunta: Qual é a maneira mais eficiente em termos de espaço que você pode imaginar para codificar o estado de um jogo de xadrez (ou subconjunto dele)? Isto é, dado um tabuleiro de xadrez com as peças dispostas legalmente, codifica tanto esse estado inicial quanto todos os movimentos legais subseqüentes realizados pelos jogadores no jogo.

Nenhum código é necessário para a resposta, apenas uma descrição do algoritmo que você usaria.

EDIT: Como um dos cartazes apontou, eu não considerei o intervalo de tempo entre os movimentos. Sinta-se à vontade para contabilizar isso também como um extra opcional :)

EDIT2: Apenas para esclarecimentos adicionais ... Lembre-se de que o codificador / decodificador reconhece as regras. As únicas coisas que realmente precisam ser armazenadas são as escolhas do jogador - qualquer outra coisa pode ser assumida como conhecida pelo codificador / decodificador.

EDIT3: Vai ser difícil escolher um vencedor aqui :) Muitas respostas boas!

Atualização: Eu gostei tanto deste tópico que escrevi Puzzles de Programação, Posições de Xadrez e Codificação de Huffman . Se você ler isso, concluí que a única maneira de armazenar um estado de jogo completo é armazenando uma lista completa de movimentos. Continue lendo para saber o porquê. Portanto, uso uma versão ligeiramente simplificada do problema para o layout das peças.

O problema

Esta imagem ilustra a posição inicial do xadrez. O xadrez ocorre em um tabuleiro de 8x8 com cada jogador começando com um conjunto idêntico de 16 peças consistindo em 8 peões, 2 torres, 2 cavalos, 2 bispos, 1 rainha e 1 rei conforme ilustrado aqui:

As posições são geralmente registradas como uma letra para a coluna seguida pelo número para a linha, então a rainha das brancas está em d1. Os movimentos são mais frequentemente armazenados em notação algébrica , que não é ambígua e geralmente especifica apenas as informações mínimas necessárias. Considere esta abertura:

1. e4 e5
2. Nf3 Nc6
3. …

que se traduz em:

1. O branco move o peão do rei de e2 para e4 (é a única peça que pode chegar a e4, portanto, “e4”);
2. As pretas movem o peão do rei de e7 para e5;
3. O branco move o cavalo (N) para f3;
4. As pretas movem o cavalo para c6.
5. …

O quadro é parecido com este:

Uma habilidade importante para qualquer programador é ser capaz de especificar o problema de forma correta e inequívoca .

Então, o que está faltando ou é ambíguo? Muito ao que parece.

Estado do tabuleiro vs estado do jogo

A primeira coisa que você precisa determinar é se você está armazenando o estado de um jogo ou a posição das peças no tabuleiro. Codificar simplesmente as posições das peças é uma coisa, mas o problema diz “todos os movimentos legais subsequentes”. O problema também não diz nada sobre saber os movimentos até este ponto. Na verdade, esse é um problema, como vou explicar.

Castling

O jogo decorreu da seguinte forma:

1. e4 e5
2. Nf3 Nc6
3. Bb5 a6
4. Ba4 Bc5

O quadro é o seguinte:

O branco tem a opção de roque . Parte dos requisitos para isso é que o rei e a torre relevante nunca podem ter se movido, portanto, se o rei ou qualquer uma das torres de cada lado se moveu, precisará ser armazenado. Obviamente, se eles não estiverem em suas posições iniciais, eles se moveram, caso contrário, isso precisa ser especificado.

Existem várias estratégias que podem ser usadas para lidar com esse problema.

Em primeiro lugar, poderíamos armazenar 6 bits extras de informação (1 para cada torre e rei) para indicar se aquela peça havia se movido. Poderíamos simplificar isso armazenando apenas um pouco para um desses seis quadrados se a peça certa estiver nele. Alternativamente, poderíamos tratar cada peça imóvel como outro tipo de peça, portanto, em vez de 6 tipos de peça em cada lado (peão, torre, cavalo, bispo, rainha e rei), haja 8 (adicionando torre imóvel e rei imóvel).

En Passant

Outra regra peculiar e frequentemente negligenciada no xadrez é En Passant .

O jogo progrediu.

1. e4 e5
2. Nf3 Nc6
3. Bb5 a6
4. Ba4 Bc5
5. OO b5
6. Bb3 b4
7. c4

O peão preto em b4 agora tem a opção de mover seu peão em b4 para c3 pegando o peão branco em c4. Isso só acontece na primeira oportunidade, o que significa que se as pretas passarem a opção agora, ele não poderá fazer o próximo movimento. Portanto, precisamos armazenar isso.

Se conhecermos o movimento anterior, podemos definitivamente responder se En Passant é possível. Alternativamente, podemos armazenar se cada peão em sua 4ª fileira acabou de se mover para lá com um movimento duplo para frente. Ou podemos olhar para cada posição possível do En Passant no tabuleiro e ter uma bandeira para indicar se é possível ou não.

Promoção

É a jogada das brancas. Se as brancas moverem seu peão em h7 para h8, ele pode ser promovido a qualquer outra peça (mas não ao rei). 99% das vezes é promovida a Rainha, mas às vezes não é, normalmente porque isso pode forçar um impasse quando, de outra forma, você ganharia. Isso é escrito como:

56. h8 = Q

Isso é importante em nosso problema porque significa que não podemos contar com um número fixo de peças em cada lado. É totalmente possível (mas incrivelmente improvável) que um lado termine com 9 rainhas, 10 torres, 10 bispos ou 10 cavalos se todos os 8 peões forem promovidos.

Impasse

Quando está em uma posição da qual você não pode vencer, sua melhor tática é tentar um impasse . A variante mais provável é quando você não pode fazer uma jogada legal (geralmente porque qualquer jogada coloca seu rei em xeque). Neste caso, você pode reivindicar um empate. Este é fácil de atender.

A segunda variante é por repetição tripla . Se a mesma posição do tabuleiro ocorrer três vezes em um jogo (ou ocorrerá uma terceira vez no próximo lance), um empate pode ser reivindicado. As posições não precisam ocorrer em nenhuma ordem particular (o que significa que não precisa da mesma sequência de movimentos repetidos três vezes). Este complica muito o problema porque você tem que se lembrar de todas as posições anteriores do tabuleiro. Se este for um requisito do problema, a única solução possível para o problema é armazenar todos os movimentos anteriores.

Por último, existe a regra dos cinquenta movimentos . Um jogador pode reivindicar um empate se nenhum peão se moveu e nenhuma peça foi tirada nos cinquenta movimentos consecutivos anteriores, então precisaríamos armazenar quantos movimentos desde que um peão foi movido ou uma peça retirada (o mais recente dos dois. Isso requer 6 bits (0-63).

Quem é a vez?

Claro que também precisamos saber de quem é a vez e esta é uma única informação.

Dois problemas

Por causa do caso de impasse, a única maneira viável ou sensata de armazenar o estado do jogo é armazenar todos os movimentos que levaram a essa posição. Vou resolver esse problema. O problema do estado do tabuleiro será simplificado para isto: armazene a posição atual de todas as peças no tabuleiro ignorando as condições de roque, en passant, impasse e de quem é a vez .

O layout das peças pode ser amplamente tratado de duas maneiras: armazenando o conteúdo de cada quadrado ou armazenando a posição de cada peça.

Conteúdo Simples

Existem seis tipos de peças (peão, torre, cavalo, bispo, rainha e rei). Cada peça pode ser branca ou preta, portanto, um quadrado pode conter uma das 12 peças possíveis ou pode estar vazio, com 13 possibilidades. 13 pode ser armazenado em 4 bits (0-15). Portanto, a solução mais simples é armazenar 4 bits para cada quadrado vezes 64 quadrados ou 256 bits de informação.

A vantagem desse método é que a manipulação é incrivelmente fácil e rápida. Isso poderia até ser estendido adicionando mais 3 possibilidades sem aumentar os requisitos de armazenamento: um peão que se moveu 2 casas no último turno, um rei que não se moveu e uma torre que não se moveu, que cuidará de muito das questões mencionadas anteriormente.

Mas nós podemos fazer melhor.

Codificação Base 13

Muitas vezes é útil pensar na posição do conselho como um número muito grande. Isso geralmente é feito na ciência da computação. Por exemplo, o problema da parada trata um programa de computador (com razão) como um grande número.

A primeira solução trata a posição como um número de base 16 de 64 dígitos, mas como demonstrado, há redundância nesta informação (sendo as 3 possibilidades não utilizadas por “dígito”), portanto, podemos reduzir o espaço de número para 64 dígitos de base 13. É claro que isso não pode ser feito de forma tão eficiente quanto a base 16, mas economizará nos requisitos de armazenamento (e minimizar o espaço de armazenamento é nosso objetivo).

Na base 10, o número 234 é equivalente a 2 x 10 ² + 3 x 10 ¹ + 4 x 10 ⁰ .

Na base 16, o número 0xA50 é equivalente a 10 x 16 ² + 5 x 16 ¹ + 0 x 16 ⁰ = 2640 (decimal).

Portanto, podemos codificar nossa posição como p ₀ x 13 ⁶³ + p ₁ x 13 ⁶² + ... + p ₆₃ x 13 ⁰ onde p _i representa o conteúdo do quadrado i .

2 ²⁵⁶ é igual a aproximadamente 1,16e77. 13 ⁶⁴ é igual a aproximadamente 1,96e71, o que requer 237 bits de espaço de armazenamento. Essa economia de apenas 7,5% tem um custo de custos de manipulação significativamente maiores.

Codificação de base variável

Em tabuleiros legais, certas peças não podem aparecer em certas casas. Por exemplo, os peões não podem ocorrer na primeira ou na oitava fileiras, reduzindo as possibilidades dessas casas para 11. Isso reduz as cartas possíveis para 11 ¹⁶ x 13 ⁴⁸ = 1,35e70 (aproximadamente), exigindo 233 bits de espaço de armazenamento.

Na verdade, codificar e decodificar esses valores de e para decimal (ou binário) é um pouco mais complicado, mas pode ser feito de forma confiável e é deixado como um exercício para o leitor.

Alfabetos de largura variável

Os dois métodos anteriores podem ser descritos como codificação alfabética de largura fixa . Cada um dos 11, 13 ou 16 membros do alfabeto é substituído por outro valor. Cada “caractere” tem a mesma largura, mas a eficiência pode ser melhorada quando você considera que cada caractere não é igualmente provável.

Considere o código Morse (foto acima). Os caracteres em uma mensagem são codificados como uma sequência de traços e pontos. Esses traços e pontos são transferidos por rádio (normalmente) com uma pausa entre eles para delimitá-los.

Observe como a letra E ( a letra mais comum em inglês ) é um único ponto, a sequência mais curta possível, enquanto Z (a menos frequente) tem dois travessões e dois bipes.

Esse esquema pode reduzir significativamente o tamanho de uma mensagem esperada, mas tem o custo de aumentar o tamanho de uma sequência de caracteres aleatória.

Deve-se notar que o código Morse tem outro recurso embutido: os traços são tão longos quanto três pontos, então o código acima é criado com isso em mente para minimizar o uso de traços. Como os 1s e 0s (nossos blocos de construção) não têm esse problema, não é um recurso que precisamos replicar.

Por último, existem dois tipos de pausas no código Morse. Um pequeno descanso (o comprimento de um ponto) é usado para distinguir entre pontos e traços. Um intervalo mais longo (o comprimento de um traço) é usado para delimitar os caracteres.

Então, como isso se aplica ao nosso problema?

Codificação Huffman

Existe um algoritmo para lidar com códigos de comprimento variável denominado codificação de Huffman . A codificação de Huffman cria uma substituição de código de comprimento variável, normalmente usa a frequência esperada dos símbolos para atribuir valores mais curtos aos símbolos mais comuns.

Na árvore acima, a letra E é codificada como 000 (ou esquerda-esquerda-esquerda) e S é 1011. Deve ficar claro que esse esquema de codificação não é ambíguo .

Esta é uma distinção importante do código Morse. O código Morse tem o separador de caracteres para que ele possa fazer substituições ambíguas (por exemplo, 4 pontos podem ser H ou 2 Is), mas temos apenas 1s e 0s, então escolhemos uma substituição inequívoca.

Abaixo está uma implementação simples:

private static class Node {
  private final Node left;
  private final Node right;
  private final String label;
  private final int weight;

  private Node(String label, int weight) {
    this.left = null;
    this.right = null;
    this.label = label;
    this.weight = weight;
  }

  public Node(Node left, Node right) {
    this.left = left;
    this.right = right;
    label = "";
    weight = left.weight + right.weight;
  }

  public boolean isLeaf() { return left == null && right == null; }

  public Node getLeft() { return left; }

  public Node getRight() { return right; }

  public String getLabel() { return label; }

  public int getWeight() { return weight; }
}

com dados estáticos:

private final static List<string> COLOURS;
private final static Map<string, integer> WEIGHTS;

static {
  List<string> list = new ArrayList<string>();
  list.add("White");
  list.add("Black");
  COLOURS = Collections.unmodifiableList(list);
  Map<string, integer> map = new HashMap<string, integer>();
  for (String colour : COLOURS) {
    map.put(colour + " " + "King", 1);
    map.put(colour + " " + "Queen";, 1);
    map.put(colour + " " + "Rook", 2);
    map.put(colour + " " + "Knight", 2);
    map.put(colour + " " + "Bishop";, 2);
    map.put(colour + " " + "Pawn", 8);
  }
  map.put("Empty", 32);
  WEIGHTS = Collections.unmodifiableMap(map);
}

e:

private static class WeightComparator implements Comparator<node> {
  @Override
  public int compare(Node o1, Node o2) {
    if (o1.getWeight() == o2.getWeight()) {
      return 0;
    } else {
      return o1.getWeight() < o2.getWeight() ? -1 : 1;
    }
  }
}

private static class PathComparator implements Comparator<string> {
  @Override
  public int compare(String o1, String o2) {
    if (o1 == null) {
      return o2 == null ? 0 : -1;
    } else if (o2 == null) {
      return 1;
    } else {
      int length1 = o1.length();
      int length2 = o2.length();
      if (length1 == length2) {
        return o1.compareTo(o2);
      } else {
        return length1 < length2 ? -1 : 1;
      }
    }
  }
}

public static void main(String args[]) {
  PriorityQueue<node> queue = new PriorityQueue<node>(WEIGHTS.size(),
      new WeightComparator());
  for (Map.Entry<string, integer> entry : WEIGHTS.entrySet()) {
    queue.add(new Node(entry.getKey(), entry.getValue()));
  }
  while (queue.size() > 1) {
    Node first = queue.poll();
    Node second = queue.poll();
    queue.add(new Node(first, second));
  }
  Map<string, node> nodes = new TreeMap<string, node>(new PathComparator());
  addLeaves(nodes, queue.peek(), &quot;&quot;);
  for (Map.Entry<string, node> entry : nodes.entrySet()) {
    System.out.printf("%s %s%n", entry.getKey(), entry.getValue().getLabel());
  }
}

public static void addLeaves(Map<string, node> nodes, Node node, String prefix) {
  if (node != null) {
    addLeaves(nodes, node.getLeft(), prefix + "0");
    addLeaves(nodes, node.getRight(), prefix + "1");
    if (node.isLeaf()) {
      nodes.put(prefix, node);
    }
  }
}

Uma saída possível é:

         White    Black
Empty          0 
Pawn       110      100
Rook     11111    11110
Knight   10110    10101
Bishop   10100    11100
Queen   111010   111011
King    101110   101111

Para uma posição inicial, isso equivale a 32 x 1 + 16 x 3 + 12 x 5 + 4 x 6 = 164 bits.

Diferença de estado

Outra abordagem possível é combinar a primeira abordagem com a codificação de Huffman. Isso é baseado na suposição de que a maioria dos tabuleiros de xadrez esperados (em vez dos gerados aleatoriamente) têm mais probabilidade de, pelo menos em parte, se parecer com uma posição inicial.

Portanto, o que você faz é aplicar um XOR à posição atual da placa de 256 bits com uma posição inicial de 256 bits e, em seguida, codificá-la (usando a codificação Huffman ou, digamos, algum método de codificação de comprimento de execução ). Obviamente, isso será muito eficiente para começar (64 0s provavelmente correspondendo a 64 bits), mas aumenta o armazenamento necessário à medida que o jogo avança.

Posição da peça

Como mencionado, outra forma de atacar esse problema é, em vez disso, armazenar a posição de cada peça que o jogador possui. Isso funciona particularmente bem com posições finais em que a maioria dos quadrados estará vazia (mas na abordagem de codificação de Huffman, quadrados vazios usam apenas 1 bit de qualquer maneira).

Cada lado terá um rei e 0-15 outras peças. Por causa da promoção, a composição exata dessas peças pode variar o suficiente para que você não possa assumir que os números baseados nas posições iniciais são máximos.

A maneira lógica de dividir isso é armazenar uma posição que consiste em dois lados (branco e preto). Cada lado tem:

• Um rei: 6 bits pela localização;
• Tem peões: 1 (sim), 0 (não);
• Se sim, número de peões: 3 bits (0-7 + 1 = 1-8);
• Se sim, a localização de cada peão é codificada: 45 bits (veja abaixo);
• Número de não peões: 4 bits (0-15);
• Para cada peça: tipo (2 bits para rainha, torre, cavalo, bispo) e localização (6 bits)

Quanto à localização do peão, os peões só podem estar em 48 casas possíveis (não em 64 como as outras). Como tal, é melhor não desperdiçar os 16 valores extras que usaria com 6 bits por peão. Portanto, se você tiver 8 peões, existem 48 ⁸ possibilidades, igualando 28.179.280.429.056. Você precisa de 45 bits para codificar tantos valores.

Isso é 105 bits por lado ou 210 bits no total. A posição inicial é o pior caso para este método e ficará substancialmente melhor à medida que você remove peças.

Deve-se ressaltar que existem menos de 48 ⁸ possibilidades porque os peões não podem estar todos na mesma casa. O primeiro tem 48 possibilidades, o segundo 47 e assim por diante. 48 x 47 x… x 41 = 1,52e13 = armazenamento de 44 bits.

Você pode melhorar ainda mais eliminando as casas que estão ocupadas por outras peças (incluindo o outro lado) para que você possa colocar primeiro os não peões brancos, depois os não peões pretos, depois os peões brancos e por último os peões pretos. Em uma posição inicial, isso reduz os requisitos de armazenamento para 44 bits para branco e 42 bits para preto.

Abordagens Combinadas

Outra otimização possível é que cada uma dessas abordagens tem seus pontos fortes e fracos. Você poderia, digamos, escolher os 4 melhores e codificar um seletor de esquema nos primeiros dois bits e, em seguida, o armazenamento específico do esquema.

Com uma sobrecarga tão pequena, essa será de longe a melhor abordagem.

Estado do jogo

Volto ao problema de armazenar um jogo em vez de uma posição . Por causa da repetição tripla, temos que armazenar a lista de movimentos que ocorreram até este ponto.

Anotações

Uma coisa que você precisa determinar é se você está simplesmente armazenando uma lista de movimentos ou está anotando o jogo? Os jogos de xadrez são frequentemente anotados, por exemplo:

17. Bb5 !! Nc4?

O movimento das brancas é marcado por dois pontos de exclamação como brilhantes, ao passo que o das pretas é visto como um erro. Veja a pontuação do xadrez .

Além disso, você também pode precisar armazenar texto livre à medida que os movimentos são descritos.

Estou assumindo que os movimentos são suficientes, portanto, não haverá anotações.

Notação Algébrica

Poderíamos simplesmente armazenar o texto do movimento aqui (“e4”, “Bxb5”, etc). Incluindo um byte de terminação, você está vendo cerca de 6 bytes (48 bits) por movimento (pior caso). Isso não é particularmente eficiente.

A segunda coisa a tentar é armazenar a localização inicial (6 bits) e a localização final (6 bits), portanto, 12 bits por movimento. Isso é significativamente melhor.

Alternativamente, podemos determinar todos os movimentos legais da posição atual de uma forma previsível e determinística e o estado que escolhemos. Isso então volta para a codificação de base variável mencionada acima. As brancas e as pretas têm 20 movimentos possíveis, cada um em seu primeiro movimento, mais no segundo e assim por diante.

Conclusão

Não há uma resposta absolutamente certa para essa pergunta. Existem muitas abordagens possíveis, das quais as acima são apenas algumas.

O que eu gosto sobre este e problemas semelhantes é que ele exige habilidades importantes para qualquer programador, como considerar o padrão de uso, determinar os requisitos com precisão e pensar em casos extremos.

Posições de xadrez tiradas como capturas de tela do Treinador de posição de xadrez .

É melhor apenas armazenar jogos de xadrez em um formato padrão legível por humanos.

O Portable Game Notation assume uma posição inicial padrão (embora não seja necessário ) e apenas lista os movimentos, turno a turno. Um formato padrão compacto e legível.

Por exemplo

[Event "F/S Return Match"]
[Site "Belgrade, Serbia Yugoslavia|JUG"]
[Date "1992.11.04"]
[Round "29"]
[White "Fischer, Robert J."]
[Black "Spassky, Boris V."]
[Result "1/2-1/2"]

1. e4 e5 2. Nf3 Nc6 3. Bb5 {This opening is called the Ruy Lopez.} 3... a6
4. Ba4 Nf6 5. O-O Be7 6. Re1 b5 7. Bb3 d6 8. c3 O-O 9. h3 Nb8  10. d4 Nbd7
11. c4 c6 12. cxb5 axb5 13. Nc3 Bb7 14. Bg5 b4 15. Nb1 h6 16. Bh4 c5 17. dxe5
Nxe4 18. Bxe7 Qxe7 19. exd6 Qf6 20. Nbd2 Nxd6 21. Nc4 Nxc4 22. Bxc4 Nb6
23. Ne5 Rae8 24. Bxf7+ Rxf7 25. Nxf7 Rxe1+ 26. Qxe1 Kxf7 27. Qe3 Qg5 28. Qxg5
hxg5 29. b3 Ke6 30. a3 Kd6 31. axb4 cxb4 32. Ra5 Nd5 33. f3 Bc8 34. Kf2 Bf5
35. Ra7 g6 36. Ra6+ Kc5 37. Ke1 Nf4 38. g3 Nxh3 39. Kd2 Kb5 40. Rd6 Kc5 41. Ra6
Nf2 42. g4 Bd3 43. Re6 1/2-1/2

Se você quiser torná-lo menor, basta compactá-lo . Tarefa concluída!

Ótimo quebra-cabeça!

Vejo que a maioria das pessoas está armazenando a posição de cada peça. Que tal adotar uma abordagem mais simplista e armazenar o conteúdo de cada quadrado ? Isso cuida da promoção e das peças capturadas automaticamente.

E permite a codificação Huffman . Na verdade, a frequência inicial de peças no tabuleiro é quase perfeita para isso: metade das casas estão vazias, metade das casas restantes são peões, etc.

Considerando a frequência de cada peça, construí uma árvore de Huffman no papel, que não vou repetir aqui. O resultado, onde crepresenta a cor (branco = 0, preto = 1):

• 0 para quadrados vazios
• 1c0 para peão
• 1c100 para torre
• 1c101 para cavaleiro
• 1c110 para bispo
• 1c1110 para rainha
• 1c1111 para rei

Para todo o conselho em sua situação inicial, temos

• quadrados vazios: 32 * 1 bit = 32 bits
• peões: 16 * 3 bits = 48 bits
• torres / cavaleiros / bispos: 12 * 5 bits = 60 bits
• rainhas / reis: 4 * 6 bits = 24 bits

Total: 164 bits para o estado inicial da placa. Significativamente menos do que os 235 bits da resposta mais votada no momento. E só vai ficar menor conforme o jogo avança (exceto depois de uma promoção).

Observei apenas a posição das peças no tabuleiro; estado adicional (cujo turno, quem fez roque, en passant, movimentos repetidos, etc.) terá que ser codificado separadamente. Talvez outros 16 bits no máximo, então 180 bits para todo o estado do jogo. Possíveis otimizações:

• Deixando de lado as peças menos frequentes e armazenando sua posição separadamente. Mas isso não vai ajudar ... substituir rei e rainha por um quadrado vazio economiza 5 bits, que são exatamente os 5 bits que você precisa para codificar sua posição de outra maneira.
• "Nenhum peão na linha de trás" poderia ser facilmente codificado usando uma tabela Huffman diferente para as linhas de trás, mas duvido que ajude muito. Você provavelmente ainda terminaria com a mesma árvore Huffman.
• "Um bispo branco, um bispo preto" pode ser codificado pela introdução de símbolos extras que não têm o cbit, que podem então ser deduzidos do quadrado em que o bispo está. (Peões promovidos a bispos atrapalham esse esquema ...)
• Repetições de quadrados vazios podem ser codificados em execução pela introdução de símbolos extras para, digamos, "2 quadrados vazios em uma linha" e "4 quadrados vazios em uma linha". Mas não é tão fácil estimar a frequência deles, e se você errar, vai doer em vez de ajudar.

A abordagem de tabela de pesquisa realmente grande

Posição - 18 bytes O
número estimado de posições legais é 10 ⁴³
Simplesmente enumere todas e a posição pode ser armazenada em apenas 143 bits. 1 bit a mais é necessário para indicar qual lado deve jogar a seguir

A enumeração não é prática, claro, mas isso mostra que pelo menos 144 bits são necessários.

Movimentos - 1 byte
Normalmente existem cerca de 30-40 movimentos legais para cada posição, mas o número pode ser tão alto quanto 218 Vamos enumerar todos os movimentos legais para cada posição. Agora, cada movimento pode ser codificado em um byte.

Ainda temos muito espaço para movimentos especiais como 0xFF para representar a renúncia.

Seria interessante otimizar o tamanho médio para jogos típicos jogados por humanos, em vez do pior caso. (A declaração do problema não diz qual; a maioria das respostas assume o pior caso.)

Para a sequência de movimentos, faça com que um bom mecanismo de xadrez gere lances de cada posição; ele produzirá uma lista de k movimentos possíveis, ordenados por sua classificação de qualidade. As pessoas geralmente escolhem bons movimentos com mais frequência do que movimentos aleatórios, então precisamos aprender um mapeamento de cada posição na lista para a probabilidade de que as pessoas escolham um movimento tão 'bom'. Usando essas probabilidades (com base em um corpus de jogos de algum banco de dados de xadrez da Internet), codifique os movimentos com codificação aritmética . (O decodificador deve usar o mesmo mecanismo de xadrez e mapeamento.)

Para a posição inicial, a abordagem de ralu funcionaria. Poderíamos refiná-lo com a codificação aritmética lá também, se tivéssemos alguma maneira de pesar as escolhas por probabilidade - por exemplo, peças frequentemente aparecem em configurações defendendo-se umas das outras, não ao acaso. É mais difícil ver uma maneira fácil de incorporar esse conhecimento. Uma idéia: recue na codificação de movimento acima, começando da posição de abertura padrão e encontrando uma sequência que termine no tabuleiro desejado. (Você pode tentar A * search com uma distância heurística igual à soma das distâncias das peças a partir de suas posições finais, ou algo nesse sentido.) Isso troca alguma ineficiência de especificar excessivamente a sequência de movimentos vs. eficiência de tirar vantagem do jogo de xadrez conhecimento.

Também é meio difícil estimar quanta economia isso representaria para você na complexidade de caso médio, sem reunir algumas estatísticas de um corpus real. Mas o ponto de partida com todos os movimentos igualmente prováveis, acho que já superaria a maioria das propostas aqui: a codificação aritmética não precisa de um número inteiro de bits por movimento.

Atacar um subproblema de codificação das etapas após uma posição inicial ter sido codificada. A abordagem é criar uma "lista vinculada" de etapas.

Cada etapa do jogo é codificada como o par "posição antiga-> nova posição". Você conhece a posição inicial no início do jogo de xadrez; percorrendo a lista vinculada de etapas, você pode chegar ao estado depois que X se move.

Para codificar cada etapa, você precisa de 64 valores para codificar a posição inicial (6 bits para 64 quadrados no quadro - quadrados 8x8) e 6 bits para a posição final. 16 bits para 1 movimento de cada lado.

A quantidade de espaço que a codificação de um determinado jogo ocuparia é proporcional ao número de movimentos:

10 x (número de movimentos brancos + número de movimentos pretos) bits.

ATUALIZAÇÃO: complicação potencial com peões promovidos. Precisa ser capaz de declarar para que o peão é promovido - pode precisar de bits especiais (usaria um código cinza para economizar espaço, já que a promoção do peão é extremamente rara).

ATUALIZAÇÃO 2: Você não precisa codificar as coordenadas completas da posição final. Na maioria dos casos, a peça que está sendo movida pode se mover para não mais do que X lugares. Por exemplo, um peão pode ter no máximo 3 opções de movimento em qualquer ponto. Ao perceber esse número máximo de movimentos para cada tipo de peça, podemos economizar bits na codificação do "destino".

Pawn: 
   - 2 options for movement (e2e3 or e2e4) + 2 options for taking = 4 options to encode
   - 12 options for promotions - 4 promotions (knight, biship, rook, queen) times 3 squares (because you can take a piece on the last row and promote the pawn at the same time)
   - Total of 16 options, 4 bits
Knight: 8 options, 3 bits
Bishop: 4 bits
Rook: 4 bits
King: 3 bits
Queen: 5 bits

Assim, a complexidade espacial por movimento de preto ou branco torna-se

6 bits para a posição inicial + (número variável de bits com base no tipo de coisa que é movida).

Eu vi essa pergunta ontem à noite e me intrigou, então me sentei na cama pensando em soluções. Minha resposta final é muito semelhante à de int3, na verdade.

Solução básica

Assumindo um jogo de xadrez padrão e que você não codifica as regras (como as brancas sempre vão primeiro), você pode economizar muito codificando apenas os movimentos que cada peça faz.

Há 32 peças no total, mas em cada movimento você sabe que cor está se movendo, então há apenas 16 quadrados com que se preocupar, o que significa 4 bits para cada peça que se move neste turno.

Cada peça tem apenas um moveset limitado, que você enumeraria de alguma forma.

• Peão: 4 opções, 2 bits (1 passo à frente, 2 passos à frente, 1 cada diagonal)
• Torre: 14 opções, 4 bits (máximo de 7 em cada direção)
• Bispo: 13 opções, 4 bits (se você tem 7 em uma diagonal, você só tem 6 na outra)
• Cavaleiro: 8 opções, 3 bits
• Rainha: 27 opções, 5 bits (Torre + Bispo)
• Rei: 9 opções, 4 bits (8 movimentos de uma etapa, mais a opção de roque)

Para a promoção, existem 4 peças para escolher (Torre, Bispo, Cavalo, Rainha), então nesse movimento adicionaríamos 2 bits para especificar isso. Acho que todas as outras regras são cobertas automaticamente (por exemplo, en passant).

Otimizações adicionais

Primeiro, após a captura de 8 peças de uma cor, você pode reduzir a codificação da peça para 3 bits, depois 2 bits para 4 peças e assim por diante.

A principal otimização, porém, é enumerar apenas os movimentos possíveis em cada ponto do jogo. Suponha que armazenamos os movimentos de um peão {00, 01, 10, 11}para 1 passo à frente, 2 passos à frente, diagonal esquerda e diagonal direita, respectivamente. Se alguns movimentos não forem possíveis, podemos removê-los da codificação para este turno.

Conhecemos o estado do jogo em cada estágio (acompanhando todos os movimentos), portanto, depois de ler qual peça se moverá, podemos sempre determinar quantos bits precisamos ler. Se percebermos que os únicos movimentos de um peão neste ponto são capturados diagonalmente para a direita ou avançamos um, sabemos que devemos ler apenas 1 bit.

Resumindo, o armazenamento de bits listado acima para cada peça é apenas um máximo . Quase todo movimento terá menos opções e geralmente menos bits.

Em cada posição, obtenha o número de todos os movimentos possíveis.

o próximo movimento é gerado como

index_current_move =n % num_of_moves //this is best space efficiency
n=n/num_of_moves

Provavelmente a melhor eficiência de espaço para armazenar jogos gerados aleatoriamente e precisa de aproximadamente 5 bits / movimento em média, uma vez que você tem 30-40 movimentos possíveis. Montar armazenamento é apenas gerar n na ordem inversa.

Armazenar a posição é mais difícil de quebrar, devido à grande redundância. (Pode haver até 9 rainhas no tabuleiro para um site, mas nesse caso não há peões e os bispos se no tabuleiro estão em casas de cores opostas), mas geralmente é como armazenar combinações das mesmas peças nas casas restantes.)

EDITAR:

O objetivo de salvar movimentos é armazenar apenas o índice de movimento. Em vez de armazenar Kc1-c2 e tentar reduzir esta informação, devemos adicionar apenas o índice de movimento gerado a partir do gerador de movimento determinístico (posição)

A cada movimento, adicionamos informações de tamanho

num_of_moves = get_number_of_possible_moves(postion) ;

na piscina e este número não pode ser reduzido

gerar pool de informações é

n=n*num_of_moves+ index_current_move

extra

Se houver apenas um movimento disponível na posição final, salve como o número de movimentos forçados feitos anteriormente. Exemplo: se a posição inicial tem 1 movimento forçado para cada lado (2 movimentos) e queremos salvar isso como um jogo de movimento, armazene 1 no pool n.

exemplo de armazenamento em pool de informações

Vamos supor que conhecemos as posições iniciais e fazemos 3 movimentos.

No primeiro movimento, há 5 movimentos disponíveis e nós pegamos o índice de movimento 4. No segundo movimento, há 6 movimentos disponíveis e pegamos o índice de posição 3 e no terceiro movimento há 7 movimentos disponíveis para esse lado e ele escolheu escolher o índice de movimento 2

Forma vetorial; índice = [4,3,2] n_moves = [5,6,7]

Estamos codificando essas informações ao contrário, então n = 4 + 5 * (3 + 6 * (2)) = 79 (não é necessário multiplicar por 7)

Como desenrolar isso? Primeiro temos posição e descobrimos que existem 5 movimentos disponíveis. assim

index=79%5=4
n=79/5=15; //no remainder

Pegamos o índice de movimento 4 e examinamos a posição novamente e, a partir deste ponto, descobrimos que existem 6 movimentos possíveis.

index=15%6=3
n=15/6=2

E pegamos o índice de movimento 3 que nos leva a uma posição com 7 movimentos possíveis.

index=2%7=2
n=2/7=0

Fazemos o último movimento do índice 2 e alcançamos a posição final.

Como você pode ver, a complexidade do tempo é O (n) e a complexidade do espaço é O (n). Editar: a complexidade do tempo é na verdade O (n ^ 2) porque o número que você multiplica aumenta, mas não deve haver problema em armazenar jogos de até 10.000 movimentos.

posição salvadora

Pode ser feito perto do ideal.

Quando descobrirmos informações e armazenarmos informações, deixe-me falar mais sobre isso. A ideia geral é diminuir a redundância (falarei sobre isso mais tarde). Vamos presumir que não houve promoções e nem retirada, então há 8 peões, 2 torres, 2 cavalos, 2 bispos, 1 rei e 1 rainha por lado.

O que temos que salvar: 1. posição de cada paz 2. posibilidades de roque 3. possibilidades de en-passant 4. lado que tem movimento disponível

Vamos supor que cada peça possa ficar em qualquer lugar, mas não 2 peças no mesmo lugar. O número de maneiras pelas quais 8 peões da mesma cor podem ser dispostos a bordo é C (64/8) (binomial) que é de 32 bits, então 2 torres 2R-> C (56/2), 2B -> C (54/2) , 2N-> C (52/2), 1Q-> C (50/1), 1K -> C (49/1) e o mesmo para outro local, mas começando com 8P -> C (48/8) e assim por diante .

Multiplicando isso para ambos os sites, obtemos o número 4634726695587809641192045982323285670400000 que é de aproximadamente 142 bits, temos que adicionar 8 para um possível en-passant (o peão en-passant pode estar em um de 8 lugares), 16 (4 bits) para limitações de roque e um pouco para o site que mudou. Acabamos com 142 + 3 + 4 + 1 = 150 bits

Mas agora vamos à caça de redundância no tabuleiro com 32 peças e nenhuma retirada.

1. ambos os peões pretos e brancos estão na mesma coluna e um de frente para o outro. Cada peão está enfrentando outro peão, o que significa que o peão branco pode estar no máximo na 6ª linha. Isso nos traz 8 * C (6/2) em vez de C (64/8) * C (48/8), que diminui a informação em 56 bits.

2. possibilidade de roque também é redundante. Se as torres não estiverem no local de partida, não há possibilidade de roque com aquela torre. Portanto, podemos adicionar imaginalmente 4 quadrados a bordo para obter informações extras se o roque com esta torre for possível e remover 4 bits de roque. Então, em vez de C (56/2) * C (40/2) * 16, temos C (58/2) * C (42/2) e perdemos 3,76 bits (quase todos de 4 bits)

3. en-passant: Quando armazenamos uma das 8 possibilidades en passant, sabemos a posição do peão preto e reduzimos a redundância de informações (se for um lance branco e tiver o terceiro peão en-passant, isso significa que o peão preto está em c5 e o peão branco também c2, c3 ou c4), portanto, em vez de C (6/2), temos 3 e perdemos 2,3 bits. Diminuímos alguma redundância se armazenarmos um número en-passant também do lado do qual pode ser feito (3 possibilidades -> esquerda, direita, ambas) e sabemos a possibilidade de peão que pode levar en passant. (por exemplo, do exemplo anterior e passant com preto em c5 o que pode estar na esquerda, direita ou ambos. se estiver em um site, temos 2 * 3 (3 para armazenar psissibilites e 2 movimentos possíveis para o peão preto na 7ª ou 6ª classificação ) em vez de C (6/2) e reduzimos em 1,3 bits e, se nos dois lados, reduzimos em 4,2 bits. Dessa forma, podemos reduzir em 2,3 + 1,3 = 3.

4. bisops: bisops podem estar em quadrados opostos apenas, isso reduz a redundância em 1 bit para cada site.

Se somarmos, precisamos de 150-56-4-3.6-2 = 85bits para armazenar a posição do xadrez se não houver ganhos

E provavelmente não muito mais se houver ganhos e promoções levados em consideração (mas vou escrever sobre isso mais tarde se alguém achar este longo post útil)

A maioria das pessoas tem codificado o estado da placa, mas em relação aos movimentos em si ... Aqui está uma descrição de codificação de bits.

Bits por peça:

• ID da peça: Máximo de 4 bits para identificar as 16 peças de cada lado. Branco / preto pode ser inferido. Tenha uma ordenação definida nas peças. Conforme o número de peças cai abaixo das respectivas potências de dois, use menos bits para descrever as peças restantes.
• Peão: 3 possibilidades no primeiro movimento, então +2 bits (avançar um ou dois quadrados, en passant.) Movimentos subsequentes não permitem avançar dois, então +1 bit é suficiente. A promoção pode ser inferida no processo de decodificação, observando quando o peão atingiu a última classificação. Se o peão for promovido, o decodificador esperará outros 2 bits indicando para qual das 4 peças principais ele foi promovido.
• Bispo: +1 bit para diagonal usado, Até +4 bits para distância ao longo da diagonal (16 possibilidades). O decodificador pode inferir a distância máxima possível que a peça pode se mover ao longo daquela diagonal, então se for uma diagonal mais curta, use menos bits.
• Cavalo: 8 movimentos possíveis, +3 bits
• Torre: +1 bit para horizontal / vertical, +4 bits para distância ao longo da linha.
• Rei: 8 movimentos possíveis, +3 bits. Indique o roque com um movimento 'impossível' - uma vez que o roque só é possível enquanto o rei estiver na primeira fila, codifique este movimento com uma instrução para mover o rei 'para trás' - isto é, para fora do tabuleiro.
• Rainha: 8 direções possíveis, + 3 bits. Até +4 bits a mais para distância ao longo da linha / diagonal (menos se a diagonal for mais curta, como no caso do bispo)

Assumindo que todas as peças estão no tabuleiro, estes são os bits por jogada: Peão - 6 bits no primeiro lance, 5 subsequentemente. 7 se promovido. Bispo: 9 bits (máximo), Cavalo: 7, Torre: 9, Rei: 7, Rainha: 11 (máximo).

O problema é fornecer uma codificação que seja mais eficiente para jogos de xadrez típicos ou uma que tenha a codificação de pior caso mais curta?

Para este último, a maneira mais eficiente é também a mais opaca: crie uma enumeração de todos os pares possíveis (tabuleiro inicial, sequência legal de movimentos), que, com a posição repetida três vezes e não mais do que -fifty-moves desde as regras de último-peão-movimento-ou-captura, é recursivo. Então, o índice de uma posição nesta sequência finita fornece a codificação de pior caso mais curta, mas também uma codificação igualmente longa para casos típicos e é, espero, muito caro para calcular. O jogo de xadrez mais longo possível deve ter mais de 5.000 movimentos, com normalmente 20-30 movimentos disponíveis em cada posição para cada jogador (embora menos quando houver poucas peças restantes) - isso dá algo como 40.000 bits necessários para esta codificação.

A ideia de enumeração pode ser aplicada para fornecer uma solução mais tratável, conforme descrito na sugestão de Henk Holterman para movimentos de codificação acima. Minha sugestão: não mínima, mas mais curta do que os exemplos acima que eu olhei, e razoavelmente tratável:

1. 64 bits para representar quais quadrados estão ocupados (matriz de ocupação), mais a lista de quais peças estão em cada quadrado ocupado (pode ter 3 bits para peões e 4 bits para outras peças): isso dá 190 bits para a posição inicial. Como não pode haver mais de 32 peças a bordo, a codificação da matriz de ocupação é redundante e, portanto, algo como posições comuns da placa podem ser codificadas, digamos como 33 bits definidos mais o índice da placa da lista de placas comuns.

2. 1 bit para dizer quem faz o primeiro movimento

3. Código de movimentos de acordo com a sugestão de Henk: tipicamente 10 bits por par de movimento branco / preto, embora alguns movimentos levem 0 bits, quando um jogador não tem movimentos alternativos.

Isso sugere 490 bits para codificar um jogo típico de 30 movimentos e seria uma representação razoavelmente eficiente para jogos típicos.

Aproximadamente a codificação da posição repetida três vezes e não mais do que cinquenta movimentos desde as regras de movimento ou captura do último peão: se você codificar os movimentos anteriores de volta para o último movimento ou captura de peão, então você tem informações suficientes para decidir se essas regras se aplicam: não há necessidade de todo o histórico do jogo.

A posição em uma placa pode ser definida em 7 bits (0-63 e 1 valor especificando que não está mais na placa). Portanto, para cada peça do tabuleiro, especifique onde ela está localizada.

32 peças * 7 bits = 224 bits

EDITAR: como Cadrian apontou ... nós também temos o caso 'peão promovido a rainha'. Sugiro que adicionemos bits extras no final para indicar qual peão foi promovido.

Portanto, para cada peão promovido, seguimos os 224 bits com 5 bits que indicam o índice do peão que foi promovido e 11111 se for o fim da lista.

Portanto, o caso mínimo (sem promoções) é 224 bits + 5 (sem promoções). Para cada peão promovido, adicione 5 bits.

EDITAR: Como o sapo felpudo indica, precisamos de mais um bit no final para indicar de quem é a vez; ^)

Eu usaria uma codificação de comprimento de execução. Algumas peças são únicas (ou existem apenas duas vezes), então posso omitir o comprimento após elas. Como o cleto, preciso de 13 estados exclusivos, então posso usar um nibble (4 bits) para codificar a peça. A placa inicial ficaria assim:

White Rook, W. Knight, W. Bishop, W. Queen, W. King, W. Bishop, W. Knight, W. Rook,
W. Pawn, 8,
Empty, 16, Empty, 16
B. Pawn, 8,
B. Rook, B. Knight, B. Bishop, B. Queen, B. King, B. Bishop, B. Knight, B. Rook

o que me deixa com 8 + 2 + 4 + 2 + 8 nibbles = 24 nibbles = 96 bits. Não posso codificar 16 com um nibble, mas como "Vazio, 0" não faz sentido, posso tratar "0" como "16".

Se o tabuleiro estiver vazio, exceto por um único peão no canto superior esquerdo, obtenho "Peão, 1, Vazio, 16, Vazio, 16, Vazio 16, Vazio, 15" = 10 nibbles = 40 bits.

O pior caso é quando tenho um quadrado vazio entre cada peça. Mas para a codificação da peça, preciso apenas de 13 dos 16 valores, então talvez eu possa usar outro para dizer "Vazio1". Então, eu preciso de 64 nibbles == 128bits.

Para os movimentos, preciso de 3 bits para a peça (a cor é dada pelo fato de que o branco sempre se move primeiro) mais 5 bits (0..63) para a nova posição = um byte por movimento. Na maioria das vezes, não preciso da posição antiga, pois apenas uma peça estará dentro do alcance. Para os casos ímpares, devo usar o único código não utilizado (só preciso de 7 códigos para codificar a parte) e, em seguida, 5 bits para a antiga e 5 bits para a nova posição.

Isso me permite codificar o roque em 13 mordidas (posso mover o Rei em direção à Torre, o que é o suficiente para dizer o que pretendo).

[EDITAR] Se você permitir um codificador inteligente, preciso de 0 bits para a configuração inicial (porque ele não precisa ser codificado de forma alguma: é estático) mais um byte por movimento.

[EDIT2] O que deixa a transformação do peão. Se um peão atingir a última linha, posso movê-lo no lugar para dizer "transforma" e depois adicionar os 3 bits para a peça pela qual ele é substituído (você não precisa usar uma rainha; você pode substituir o peão por qualquer coisa mas o rei).

Assim como eles codificam jogos em livros e papéis: cada peça tem um símbolo; já que é um jogo "legal", o branco se move primeiro - não há necessidade de codificar o branco ou o preto separadamente, apenas conte o número de movimentos para determinar quem se moveu. Além disso, cada movimento é codificado como (peça, posição final) onde a 'posição final' é reduzida ao mínimo de símbolos que permite discernir ambigüidades (pode ser zero). A duração do jogo determina o número de movimentos. Também é possível codificar o tempo em minutos (desde a última jogada) em cada etapa.

A codificação da peça pode ser feita atribuindo um símbolo a cada uma (32 no total) ou atribuindo um símbolo à classe, e usar a posição final para entender qual peça foi movida. Por exemplo, um peão tem 6 posições finais possíveis; mas, em média, apenas alguns estão disponíveis para ele em cada turno. Portanto, estatisticamente, a codificação pela posição final pode ser a melhor para este cenário.

Codificações semelhantes são usadas para trens de pico em neurociência computacional (AER).

Desvantagens: você precisa jogar de novo todo o jogo para chegar ao estado atual e gerar um subconjunto, da mesma forma que percorrer uma lista vinculada.

Existem 64 posições de placa possíveis, então você precisa de 6 bits por posição. Existem 32 peças iniciais, então temos 192 bits no total até agora, onde cada 6 bits indica a posição da peça dada. Podemos pré-determinar a ordem em que as peças aparecem, então não precisamos dizer qual é qual.

E se uma peça estiver fora do tabuleiro? Bem, podemos colocar uma peça no mesmo lugar que outra peça para indicar que ela está fora do tabuleiro, já que seria ilegal de outra forma. Mas também não sabemos se a primeira peça estará no tabuleiro ou não. Portanto, adicionamos 5 bits indicando qual peça é a primeira (32 possibilidades = 5 bits para representar a primeira peça). Então, podemos usar esse local para as peças subsequentes que estão fora do tabuleiro. Isso nos leva a um total de 197 bits. Tem de haver pelo menos uma peça no tabuleiro para que funcione.

Então precisamos de um bit para a vez de quem é - nos traz a 198 bits .

E a promoção do peão? Podemos fazer isso da maneira errada adicionando 3 bits por peão, acrescentando 42 bits. Mas então podemos notar que na maioria das vezes, os peões não são promovidos.

Portanto, para cada peão que está no tabuleiro, o bit '0' indica que ele não foi promovido. Se um peão não estiver no tabuleiro, não precisamos de nenhum pedaço. Então, podemos usar cadeias de bits de comprimento variável para as quais ele tenha promoção. Na maioria das vezes, será uma rainha, então "10" pode significar RAINHA. Então, "110" significa torre, "1110" significa bispo e "1111" significa cavalo.

O estado inicial levará 198 + 16 = 214 bits , já que todos os 16 peões estão no tabuleiro e não promovidos. Um final de jogo com duas rainhas de peões promovidas pode levar algo como 198 + 4 + 4, o que significa 4 peões vivos e não promovidos e 2 peões da rainha, por 206 bits total de . Parece muito robusto!

===

A codificação Huffman, como outros apontaram, seria o próximo passo. Se você observar alguns milhões de jogos, notará que cada peça tem muito mais probabilidade de estar em determinados quadrados. Por exemplo, na maioria das vezes, os peões ficam em linha reta, ou um à esquerda / um à direita. O rei geralmente fica perto da base.

Portanto, crie um esquema de codificação Huffman para cada posição separada. Os peões provavelmente receberão apenas em média 3-4 bits em vez de 6. O rei também deve receber alguns bits.

Também neste esquema, inclua "tomada" como uma posição possível. Isso também pode controlar o roque de forma muito robusta - cada torre e rei terão um estado extra de "posição original, movido". Você também pode codificar en passant nos peões desta forma - "posição original, pode en passant".

Com dados suficientes, essa abordagem deve produzir resultados realmente bons.

Eu tentaria usar a codificação Huffman . A teoria por trás disso é - em todo jogo de xadrez haverá algumas peças que se moverão muito e algumas que não se moverão muito ou serão eliminadas cedo. Se a posição inicial já tiver algumas peças removidas - tanto melhor. O mesmo vale para quadrados - alguns quadrados conseguem ver toda a ação, enquanto outros não são muito tocados.

Portanto, eu teria duas mesas Huffman - uma para peças, outra para quadrados. Eles serão gerados olhando para o jogo real. Eu poderia ter uma mesa grande para cada par de peças quadradas, mas acho que isso seria bastante ineficiente porque não há muitas instâncias da mesma peça se movendo na mesma casa novamente.

Cada peça teria um ID atribuído. Como existem 32 peças diferentes, eu precisaria de apenas 5 bits para o ID da peça. Os IDs das peças não mudam de jogo para jogo. O mesmo vale para IDs quadrados, para os quais precisaria de 6 bits.

As árvores de Huffman seriam codificadas anotando cada nó à medida que são percorridos em ordem (ou seja, primeiro o nó é gerado e, em seguida, seus filhos da esquerda para a direita). Para cada nó, haverá um bit especificando se é um nó folha ou um nó de ramificação. Se for um nó folha, ele será seguido pelos bits que fornecem o ID.

A posição inicial será simplesmente fornecida por uma série de pares de localização de peças. Depois disso, haverá um par de localização de peça para cada movimento. Você pode encontrar o final do descritor de posição inicial (e o início do descritor de movimentos) simplesmente encontrando a primeira peça mencionada duas vezes. No caso de um peão ser promovido, haverá 2 bits extras especificando o que ele se tornará, mas o ID da peça não mudará.

Para contabilizar a possibilidade de um peão ser promovido no início do jogo, também haverá uma "mesa de promoção" entre as árvores do huffman e os dados. No início, haverá 4 bits especificando quantos peões são atualizados. Então, para cada peão, haverá seu ID codificado por huffman e 2 bits especificando o que ele se tornou.

As árvores huffman serão geradas levando em consideração todos os dados (tanto a posição inicial quanto os movimentos) e a tabela de promoção. Embora normalmente a tabela de promoção esteja vazia ou tenha apenas algumas entradas.

Para resumir em termos gráficos:

<Game> := <Pieces huffman tree> <squares huffman tree> <promotion table> <initial position> (<moves> | <1 bit for next move - see Added 2 below>)

<Pieces huffman tree> := <pieces entry 1> <pieces entry 2> ... <pieces entry N>
<pieces entry> := "0" | "1" <5 bits with piece ID>

<squares huffman tree> := <squares entry 1> <squares entry 2> ... <squares entry N>
<Squares entry> := "0" | "1" <6 bits with square ID>

<promotion table> := <4 bits with count of promotions> <promotion 1> <promotion 2> ... <promotion N>
<promotion> := <huffman-encoded piece ID> <2 bits with what it becomes>

<initial position> := <position entry 1> <position entry 2> ... <position entry N>
<moves> := <position entry 1> <position entry 2> ... <position entry N>
<position entry> := <huffman-encoded piece ID> <huffman-encoded squre ID> (<2 bits specifying the upgrade - optional>)

Adicionado: ainda pode ser otimizado. Cada peça tem apenas alguns movimentos legais. Em vez de simplesmente codificar o quadrado alvo, pode-se fornecer IDs com base em 0 para os movimentos possíveis de cada peça. Os mesmos IDs seriam reutilizados para cada peça, portanto, no total, não haveria mais do que 21 IDs diferentes (a rainha pode ter no máximo 21 opções de movimento possíveis diferentes). Coloque isso em uma tabela huffman em vez dos campos.

No entanto, isso apresentaria uma dificuldade em representar o estado original. Pode-se gerar uma série de movimentos para colocar cada peça em seu lugar. Nesse caso, seria necessário marcar de alguma forma o fim do estado inicial e o início dos movimentos.

Alternativamente, eles podem ser colocados usando IDs quadrados de 6 bits não compactados.

Se isso representaria uma diminuição geral de tamanho - não sei. Provavelmente, mas deveria experimentar um pouco.

Adicionado 2: Mais um caso especial. Se o estado do jogo NÃO tiver movimentos, será importante distinguir quem se move em seguida. Adicione mais um bit no final para isso. :)

[editado depois de ler a pergunta corretamente] Se você assumir que todas as posições legais podem ser alcançadas a partir da posição inicial (que é uma definição possível de "legal"), então qualquer posição pode ser expressa como a sequência de movimentos desde o início. Um fragmento de jogo começando de uma posição fora do padrão pode ser expresso como a sequência de movimentos necessários para chegar ao início, um interruptor para ligar a câmera, seguido por movimentos subsequentes.

Portanto, vamos chamar o estado inicial da placa de bit único "0".

Os lances de qualquer posição podem ser enumerados numerando os quadrados e ordenando os lances por (início, fim), com o salto convencional de 2 quadrados indicando roque. Não há necessidade de codificar movimentos ilegais, porque a posição do tabuleiro e as regras sempre são conhecidas. O sinalizador para ligar a câmera pode ser expresso como um movimento especial dentro da banda ou, mais sensatamente, como um número de movimento fora da banda.

Existem 24 movimentos de abertura para cada lado, que podem caber em 5 bits cada. Os movimentos subsequentes podem exigir mais ou menos bits, mas os movimentos legais são sempre enumeráveis, de modo que a largura de cada movimento pode crescer ou se expandir. Não calculei, mas imagino que posições de 7 bits seriam raras.

Usando este sistema, um jogo de 100 meio movimento pode ser codificado em aproximadamente 500 bits. No entanto, pode ser aconselhável usar um livro de abertura. Suponha que ele contenha um milhão de sequências. Deixe então, um 0 inicial indica um início da placa padrão, e um 1 seguido por um número de 20 bits indica um início a partir dessa sequência de abertura. Jogos com aberturas um tanto convencionais podem ser encurtados em, digamos, 20 meios-movimentos ou 100 bits.

Esta não é a maior compressão possível, mas (sem o livro de abertura) seria muito fácil de implementar se você já tiver um modelo de xadrez, que a pergunta assume.

Para compactar ainda mais, você deseja ordenar os movimentos de acordo com a probabilidade, em vez de em uma ordem arbitrária, e codificar as sequências prováveis ​​em menos bits (usando, por exemplo, tokens de Huffman, como as pessoas mencionaram).

Se o tempo computacional não for um problema, você pode usar um gerador de posição possível determinística para atribuir ids únicos a uma determinada posição.

De uma determinada posição, primeiro gere o número de posições possíveis em uma mansão determinística, por exemplo, começando inferior esquerdo movendo para superior direito. Isso determina quantos bits você precisará para o próximo movimento; em algumas situações, pode ser apenas um. Então, quando a mudança for feita, armazene apenas o ID exclusivo para essa mudança.

A promoção e outras regras simplesmente contam como jogadas válidas, desde que sejam feitas de maneira determinística, por exemplo, para a rainha, para a torre, para o bispo, cada uma conta como uma jogada separada.

A posição inicial é a mais difícil e pode gerar cerca de 250 milhões de posições possíveis (eu acho) que exigiriam cerca de 28 bits mais um bit extra para determinar de quem é o movimento.

Supondo que saibamos quem é a vez (cada curva muda de branco para preto), o gerador determinístico seria algo como:

for each row
    for each column
        add to list ( get list of possible moves( current piece, players turn) )

'obter lista de movimentos possíveis' faria algo como:

if current piece is not null 
    if current piece color is the same as the players turn
        switch( current piece type )
            king - return list of possible king moves( current piece )
            queen - return list of possible queen moves( current piece )
            rook - return list of possible rook moves( current piece )
            etc.

Se o rei estiver em xeque, cada 'lista de possíveis xxx jogadas' retornará apenas lances válidos que mudem a situação de xeque.

A maioria das respostas ignorou a repetição de 3 vezes. infelizmente para a repetição de 3 vezes você tem que armazenar todas as posições jogadas até agora ...

A questão exigia que armazenássemos de maneira eficiente em termos de espaço, de modo que realmente não precisamos armazenar a posição, desde que possamos construí-la a partir da lista de movimentos (desde que tenhamos uma posição inicial padrão). Podemos otimizar PGN e pronto. O abaixo é um esquema simples.

Existem 64 quadrados no tabuleiro, 64 = 2 ^ 6. Se armazenarmos apenas o quadrado inicial e final de cada movimento, isso levaria 12 bits (a promoção será abordada mais tarde). Observe que este esquema já cobre o jogador para mover, enfatizar, peça capturada, roque etc; como isso pode ser construído apenas reproduzindo a lista de movimentos.

para promoção, podemos manter uma matriz separada de vetores que diriam "no movimento N, promova para a Peça XYZ". podemos manter um vetor de (int, byte).

É tentador otimizar o vetor (Para, De) também, uma vez que muitos desses vetores (Para, De) não são possíveis no xadrez. por exemplo. não haverá uma mudança de e1 para d8 etc. Mas eu não consegui pensar em nenhum esquema. Quaisquer outras ideias são bem-vindas.

Há muito tempo que penso nisso (+ - 2 horas). E não há respostas óbvias.

Supondo:

1. Ignorar o estado de tempo (um jogador não costumava ter um limite de tempo, portanto, poderia forçar um empate por não jogar)
2. Quando o jogo foi jogado?!? É importante porque as regras mudaram ao longo do tempo (então assumirá um jogo moderno no ponto seguinte um jogo moderno ...) Por favor, consulte a regra do peão morto, por exemplo (a wikipedia tem um problema muito famoso mostrando isso), e se você quiser Para voltar no tempo, boa sorte, o bispo costumava se mover lentamente e os dados costumavam ser usados. ri muito.

... regras modernas tão atualizadas. Primeiro, independentemente da repetição e do limite de repetição de movimento.

-C 25 bytes arredondados (64b + 32 * 4b + 5b = 325b)

= 64 bits (algo / nada) + 32 * 4 bits [1 bit = cor {preto / branco} + 3 bits = tipo de peça {Rei, Rainha, Bispo, kNoite, Torre, Peão, Parque Movido} NB: Peão movido ... por exemplo, se foi o último peão movido no turno anterior, indicando que um 'en passant' é viável. ] + 5 bits para o estado atual (quem é a vez, en passant, possibilidade de rooking ou não em cada lado)

Por enquanto, tudo bem. Provavelmente pode ser aprimorado, mas então haveria duração variável e promoção a serem levadas em consideração !?

Agora, as seguintes regras são aplicáveis ​​apenas QUANDO um jogador se candidata a um empate, ISSO NÃO É automático! Portanto, considere que esses 90 movimentos sem captura ou um movimento de peão são possíveis se nenhum jogador pedir empate! O que significa que todos os movimentos precisam ser registrados ... e disponíveis.

-D repetição da posição ... por exemplo, estado do tabuleiro como mencionado acima (ver C) ou não ... (ver a seguir sobre as regras da FIDE) -E Isso deixa o problema complexo de permissão para 50 movimentos sem captura ou movimento de peão ali a contador é necessário ... No entanto.

Então, como você lida com isso? ... Bem, realmente não há como. Porque nenhum dos jogadores pode querer desenhar ou perceber que isso ocorreu. Agora, no caso de E, um contador pode bastar ... mas aqui está o truque e mesmo lendo as regras da FIDE (http://www.fide.com/component/handbook/?id=124&view=article) Não consigo encontrar um resposta ... e quanto à perda de habilidade de rooking. Isso é uma repetição? Acho que não, mas esse é um assunto turvo, não abordado, não esclarecido.

Então aqui estão duas regras que são duas complexas ou indefinidas até mesmo para tentar codificar ... Saudações.

Portanto, a única maneira de realmente codificar um jogo é gravar tudo desde o início ... o que então entra em conflito (ou não?) Com a questão do "estado do tabuleiro".

Espero que ajude ... não muita matemática :-) Só para mostrar que algumas questões não são tão fáceis, muito abertas para interpretação ou pré-conhecimento para serem corretas e eficientes. Não é um que eu consideraria para entrevistar, pois abre muito de uma lata de verme.

Possível melhoria na posição inicial na solução de Yacoby

Nenhuma posição legal tem mais de 16 peças de cada cor. O número de maneiras de colocar até 16 peças pretas e 16 brancas em 64 quadrados é cerca de 3,63e27. Log2 (3,63e27) = 91,55. Isso significa que você pode codificar a posição e a cor de todas as peças em 92 bits. Isso é menor que os 64 bits para a posição + até 32 bits para a cor que a solução de Yacoby requer. Você pode economizar 4 bits no pior dos casos, às custas de uma complexidade considerável na codificação.

Por outro lado, aumenta o tamanho para posições com 5 ou mais peças em falta. Essas posições representam apenas <4% de todas as posições, mas provavelmente são a maioria dos casos em que você deseja registrar uma posição inicial diferente da posição inicial.

Isso leva à solução completa

1. Codifique a posição e a cor das peças de acordo com o método acima. 92 bits .
2. Para especificar o tipo de cada peça, use um Código Huffman: peão: '0', torre: '100', cavalo: '101', bispo: '110', rainha: '1110', rei: '1111'. Isso requer (16 * 1 + 12 * 3 + 4 * 4) = 68 bits para um conjunto completo de peças. A posição da placa completa pode ser codificada em 92 + 68 = 160 bits no máximo .
3. O estado de jogo adicional deve ser adicionado: turn: 1 bit, cujo roque é possível: 4 bits, “en passant” possível: até 4 bits (1 bit indica que é o caso e 3 bits indicam qual). A posição inicial é codificada em = 160 + 9 = 169 bits
4. Para a lista de movimentos, enumere todos os movimentos possíveis para uma determinada posição e armazene a posição do movimento na lista. A lista de jogadas inclui todos os casos especiais (roque, en passant e renúncia). Use apenas os bits necessários para armazenar a posição mais alta. Em média, não deve exceder 7 bits por jogada (16 peças possíveis e 8 lances legais por peça em média). Em alguns casos, quando um movimento é forçado, ele requer apenas 1 bit (mover ou renunciar).

Existem 32 peças no tabuleiro. Cada peça tem uma posição (uma em 64 quadrados). Então você só precisa de 32 inteiros positivos.

Eu sei que 64 posições têm 6 bits, mas eu não faria isso. Eu ficaria com os últimos pedaços para algumas bandeiras (peça caída, peão com rainha)

a resposta de cletus é boa, mas ele se esqueceu de codificar também de quem é a vez. Faz parte do estado atual e é necessário se você estiver usando esse estado para conduzir um algoritmo de pesquisa (como um derivado alfa-beta).

Não sou um jogador de xadrez, mas acredito que haja mais um caso esquivo: quantos lances foram repetidos. Assim que cada jogador fizer o mesmo movimento três vezes, o jogo termina empatado, não? Em caso afirmativo, você precisará salvar essas informações no estado porque, após a terceira repetição, o estado agora é terminal.

Como vários outros mencionaram, você poderia, para cada uma das 32 peças, armazenar em qual quadrado elas estão e se estão no tabuleiro ou não, isso dá 32 * (log2 (64) + 1) = 224 bits.

No entanto, os bispos só podem ocupar os quadrados pretos ou brancos, portanto, para eles, você só precisa de log2 (32) bits para a posição, o que dá 28 * 7 + 4 * 6 = 220 bits.

E como os peões não começam atrás e só podem avançar, eles só podem estar no 56, deve ser possível usar essa limitação para reduzir o número de bits necessários para os peões.

Um tabuleiro tem 64 quadrados e pode ser representado por 64 bits que mostram se um quadrado está vazio ou não. Só precisamos de informações sobre a peça se um quadrado tiver uma peça. Como o player + peça leva 4 bits (como mostrado anteriormente), podemos obter o estado atual em 64 + 4 * 32 = 192 bits. Jogue na curva atual e você terá 193 bits.

No entanto, também precisamos codificar os movimentos legais para cada peça. Primeiro, calculamos o número de movimentos legais para cada peça e acrescentamos essa quantidade de bits após o identificador de peça de um quadrado completo. Eu calculei da seguinte forma:

Peão: Avançar, primeiro gire dois para frente, en passant * 2, promoção = 7 bits. Você pode combinar o primeiro turno para a frente e a promoção em um único bit, já que eles não podem acontecer da mesma posição, então você tem 6. Torre: 7 quadrados verticais, 7 quadrados horizontais = 14 bits Cavaleiro: 8 quadrados = 8 bits Bispo: 2 diagonais * 7 = 14 bits Queen: 7 vertical, 7 horizontal, 7 diagonal, 7 diagonal = 28 bits King: 8 quadrados circundantes

Isso ainda significa que você precisaria mapear os quadrados visados ​​com base na posição atual, mas (deve ser) um cálculo simples.

Uma vez que temos 16 peões, 4 torres / cavalos / bispos e 2 rainhas / reis, isso é 16 * 6 + 4 * 14 + 4 * 8 + 4 * 14 + 2 * 28 + 2 * 8 = 312 bits a mais, trazendo o total para 505 bits no geral.

Quanto ao número de bits necessários por peça para possíveis movimentos, algumas otimizações poderiam ser adicionadas a isso e o número de bits provavelmente reduzido, usei apenas números fáceis para trabalhar. Por exemplo, para peças deslizantes, você pode armazenar a que distância elas podem se mover, mas isso exigiria cálculos extras.

Resumindo a história: armazene apenas dados extras (peça, etc.) quando um quadrado estiver ocupado e somente o número mínimo de bits para cada peça para representar seus movimentos legais.

EDIT1: Esqueci o roque e a promoção do peão para qualquer peça. Isso poderia elevar o total com posições explícitas a 557 movimentos (mais 3 bits para peões, 2 para reis)

Cada peça pode ser representada por 4 bits (peão ao rei, 6 tipos), preto / branco = 12 valores

Cada quadrado no tabuleiro pode ser representado por 6 bits (x coord, y coord).

As posições iniciais requerem no máximo 320 bits (32 peças, 4 + 6 bits)

Cada movimento subsequente pode ser representado por 16 bits (da posição, para a posição, peça).

O castling exigiria 16 bits extras, pois é um movimento duplo.

Os peões enfileirados podem ser representados por um dos 4 valores sobressalentes de 4 bits.

Sem fazer as contas em detalhes, isso começa a economizar espaço após o primeiro movimento em comparação com o armazenamento de 32 * 7 bits (matriz predefinida de peças) ou 64 * 4 bits (atribuição predefinida de quadrados)

Após 10 movimentos em ambos os lados, o espaço máximo necessário é de 640 bits

... mas, novamente, se identificarmos cada peça exclusivamente (5 bits) e adicionarmos um sexto bit para sinalizar os peões da raça, então precisamos apenas id da peça + para a posição para cada movimento. Isso muda o cálculo para ...

Posições iniciais = máx. 384 bits (32 peças, 6 + 6 bits) Cada movimento = 12 bits (para a posição, id da peça)

Então, após 10 movimentos de cada lado, o espaço máximo necessário é de 624 bits

Como Robert G, eu tenderia a usar PGN, pois é padrão e pode ser usado por uma ampla gama de ferramentas.

Se, no entanto, estou jogando um xadrez AI que está em uma sonda espacial distante e, portanto, cada bit é precioso, é isso que eu faria para os movimentos. Vou começar a codificar o estado inicial mais tarde.

Os movimentos não precisam registrar o estado; o decodificador pode controlar o estado e também quais movimentos são permitidos em qualquer ponto. Todos os movimentos precisam registrar é qual das várias alternativas legais é escolhida. Como os jogadores se alternam, um movimento não precisa registrar a cor do jogador. Visto que um jogador só pode mover suas próprias peças de cor, a primeira escolha é qual peça o jogador move (voltarei a uma alternativa que usa outra escolha mais tarde). Com no máximo 16 peças, isso requer no máximo 4 bits. À medida que um jogador perde peças, o número de escolhas diminui. Além disso, um determinado estado do jogo pode limitar a escolha das peças. Se um rei não pode se mover sem se colocar em xeque, o número de escolhas é reduzido em um. Se um rei está em xeque, qualquer peça que não consiga tirar o rei do xeque não é uma escolha viável.

Depois que a peça for especificada, ela terá apenas um certo número de destinos legais. O número exato depende muito do layout do tabuleiro e do histórico do jogo, mas podemos descobrir certos máximos e valores esperados. Para todos, exceto o cavalo e durante o roque, uma peça não pode passar por outra peça. Essa será uma grande fonte de limites de movimento, mas é difícil de quantificar. Uma peça não pode se mover para fora do tabuleiro, o que também limitará bastante o número de destinos.

Codificamos o destino da maioria das peças numerando os quadrados ao longo das linhas na seguinte ordem: W, NW, N, NE (o lado preto é N). Uma linha começa no quadrado mais afastado na direção indicada para a qual o movimento é legal e prossegue em direção a. Para um rei não sobrecarregado, a lista de movimentos é W, E, NW, SE, N, S, NE, SW. Para o cavalo, começamos com 2W1N e prosseguimos no sentido horário; o destino 0 é o primeiro destino válido nesta ordem.

• Peões: um peão não movido tem 2 opções de destino, exigindo, portanto, 1 bit. Se um peão pode capturar outro, normalmente ou en passant (o que o decodificador pode determinar, já que está monitorando o estado), ele também tem 2 ou 3 opções de movimentos. Fora isso, um peão pode ter apenas uma escolha, não exigindo bits. Quando um peão está na ^7ª fila, também adicionamos a opção de promoção. Uma vez que os peões são geralmente promovidos a rainhas, seguidos por cavalos, codificamos as escolhas como:
  • rainha: 0
  • cavaleiro: 10
  • bispo: 110
  • torre: 111
• Bispo: no máximo 13 destinos quando em {d, e} {4,5} para 4 bits.
• Torre: no máximo 14 destinos, 4 bits.
• Cavaleiros: no máximo 8 destinos, 3 bits.
• Reis: Quando o roque é uma opção, o rei está de volta ao S e não pode se mover para baixo; isso dá um total de 7 destinos. No resto do tempo, um rei tem no máximo 8 lances, dando no máximo 3 bits.
• Rainha: O mesmo que as opções para bispo ou torre, para um total de 27 opções, que são 5 bits

Como o número de opções nem sempre é uma potência de dois, o que foi dito acima ainda desperdiça bits. Suponhamos que o número de escolhas é C e a escolha particular é numerada C , e n = ceil (lg ( C )) (o número de bits exigido para codificar a escolha). Usamos esses valores desperdiçados examinando o primeiro bit da próxima escolha. Se for 0, não faça nada. Se for 1 e c + C <2 ⁿ , adicione C a c . Decodificar um número inverte isso: se o c > = C recebido , subtraia C e defina o primeiro bit para o próximo número como 1. Se c<2ⁿ - C e , em seguida, defina o primeiro bit para o próximo número como 0. Se 2 ⁿ - C <= c < C , não faça nada. Chame esse esquema de "saturação".

Outro tipo de escolha potencial que pode encurtar a codificação é escolher uma peça do oponente para capturar. Isso aumenta o número de escolhas para a primeira parte de um movimento, escolhendo uma peça, para no máximo um bit adicional (o número exato depende de quantas peças o jogador atual pode mover). Esta escolha é seguida pela escolha da peça de captura, que provavelmente é muito menor do que o número de movimentos de qualquer uma das peças do jogador. Uma peça só pode ser atacada por uma peça de qualquer direção cardinal mais os cavalos para um total de no máximo 10 peças de ataque; isso dá um máximo total de 9 bits para um movimento de captura, embora eu esperasse 7 bits em média. Isso seria particularmente vantajoso para capturas pela rainha, uma vez que muitas vezes ela terá alguns destinos legais.

Com a saturação, a captura-codificação provavelmente não oferece uma vantagem. Poderíamos permitir ambas as opções, especificando no estado inicial quais são usadas. Se a saturação não for usada, a codificação do jogo também pode usar números de escolha não usados ​​( C <= c <2 ⁿ ) para alterar as opções durante o jogo. Sempre que C for uma potência de dois, não poderíamos alterar as opções.

Thomas tem a abordagem certa para codificar a placa. No entanto, isso deve ser combinado com a abordagem de ralu para armazenar movimentos. Faça uma lista de todos os movimentos possíveis, escreva o número de bits necessários para expressar esse número. Visto que o decodificador está fazendo o mesmo cálculo, ele sabe quantos são possíveis e pode saber quantos bits ler, nenhum código de comprimento é necessário.

Assim, obtemos 164 bits para as peças, 4 bits para informações de roque (assumindo que estamos armazenando um fragmento de um jogo, caso contrário, ele pode ser reconstruído), 3 bits para informações de elegibilidade en passant - simplesmente armazene a coluna onde ocorreu a movimentação ( Se en passant não for possível, armazene uma coluna onde não for possível - tais colunas devem existir) e 1 para quem deve mover.

Os movimentos normalmente levam 5 ou 6 bits, mas podem variar de 1 a 8.

Um atalho adicional - se a codificação começar com 12 bits 1 (uma situação inválida - nem mesmo um fragmento terá dois reis de um lado) você aborta a decodificação, limpa o tabuleiro e inicia um novo jogo. O próximo bit será um pouco de movimento.

O algoritmo deve enumerar deterministicamente todos os destinos possíveis em cada movimento. Número de destinos:

• 2 bispos, 13 destinos cada = 26
• 2 torres, 14 destinos cada = 28
• 2 cavaleiros, 8 destinos cada = 16
• rainha, 27 destinos
• rei, 8 destinos

8 patas poderiam se tornar rainhas no pior caso (em termos de enumeração), tornando assim o maior número de destinos possíveis 9 * 27 + 26 + 28 + 16 + 8 = 321. Assim, todos os destinos para qualquer movimento podem ser enumerados por um número de 9 bits.

O número máximo de jogadas de ambas as partes é 100 (se não estou errado, não é um jogador de xadrez). Assim, qualquer jogo pode ser gravado em 900 bits. Além da posição inicial, cada peça pode ser gravada usando números de 6 bits, que totalizam 32 * 6 = 192 bits. Mais um bit para o registro de "quem se move primeiro". Assim, qualquer jogo pode ser gravado usando 900 + 192 + 1 = 1093 bits.

Armazenando o estado da placa

A maneira mais simples que pensei é primeiro ter um array de 8 * 8 bits representando a localização de cada peça (então 1 se houver uma peça de xadrez lá e 0 se não houver). Como este é um comprimento fixo, não precisamos de nenhum terminador.

Em seguida, represente cada peça de xadrez em ordem de localização. Usando 4 bits por peça, isso leva 32 * 4 bits (128 no total). O que é realmente um desperdício.

Usando uma árvore binária, podemos representar um peão em um byte, um cavalo e uma torre e um bispo em 3 e um rei e uma rainha em 4. Como também precisamos armazenar a cor da peça, que leva um byte extra ela acaba como (perdoe-me se isso estiver errado, eu nunca olhei para a codificação de Huffman em detalhes antes):

• Peão: 2
• Torre: 4
• Cavaleiro: 4
• Bispo: 4
• Rei: 5
• Rainha: 5

Dados os totais:

2*16 + 4*4 + 4*4 + 4*4 + 2*5 + 2*5 = 100

O que é melhor do que usar um conjunto de bits de tamanho fixo por 28 bits.

Portanto, o melhor método que encontrei é armazená-lo em uma matriz de 8 ² + 100 bits

8*8 + 100 = 164

Armazenando movimentos
A primeira coisa que precisamos saber é qual peça está se movendo para onde. Dado que há no máximo 32 peças no tabuleiro e sabemos o que cada peça é, em vez de um inteiro representando o quadrado, podemos ter um inteiro representando o deslocamento da peça, o que significa que só temos que ajustar 32 valores possíveis para representar um peça.

Infelizmente, existem várias regras especiais, como rocar ou derrubar o rei e formar uma república (referência de Terry Pratchett), portanto, antes de armazenarmos a peça para mover, precisamos de um único bit indicando se é um movimento especial ou não.

Portanto, para cada movimento normal, temos alguns 1 + 5 = 6bits necessários . (Tipo de 1 bit, 5 bits para a peça)

Depois que o número da peça foi decodificado, conhecemos o tipo de peça e cada peça deve representar seu movimento da maneira mais eficiente. Por exemplo (se minhas regras de xadrez são perfeitas), um peão tem um total de 4 movimentos possíveis (vire à esquerda, vire à direita, mova um para frente, mova dois para frente).
Portanto, para representar um movimento de peão, precisamos de '6 + 2 = 8' bits. (6 bits para o cabeçalho do movimento inicial, 2 bits para o movimento)

Mover para a rainha seria mais complexo, pois seria melhor ter uma direção (8 direções possíveis, então 3 bits) e um total de 8 quadrados possíveis para mover para cada direção (então outros 3 bits). Portanto, para representar o movimento de uma rainha, seriam necessários 6 + 3 + 3 = 12bits.

A última coisa que ocorre para mim é que precisamos armazenar quais jogadores são. Deve ser um único bit (branco ou preto para mover a seguir)

Formato resultante
Então, o formato do arquivo seria mais ou menos assim

[64 bits] Localização das peças iniciais
[máximo de 100 bits] Peças iniciais [1 bit] Vira do jogador
[n bits] Movimentos

Onde um movimento é
[1 bit] Tipo de movimento (especial ou normal)
[n bits] Detalhe do movimento

Se o movimento for um movimento normal, o detalhe do movimento se parece com um movimento de peça específico de
[5 bits]
[n bits] (geralmente na faixa de 2 a 6 bits]

Se for um movimento especial,
deve ter um tipo inteiro e, em seguida, qualquer informação adicional (como se é roque). Não consigo lembrar o número de movimentos especiais, então pode ser OK apenas indicar que é um movimento especial (se houver apenas um)

No caso básico do tabuleiro inicial mais movimentos subsequentes, considere o seguinte.

Use um programa de xadrez para atribuir probabilidades a todos os movimentos possíveis. Por exemplo, 40% para e2-e4 20% para d2-d4 e assim por diante. Se alguns movimentos forem legais, mas não considerados por esse programa, dê-lhes uma probabilidade baixa. Use a codificação aritmética para salvar qual escolha foi feita, que será algum número entre 0 e 0,4 para o primeiro movimento, 0,4 e 0,6 para o segundo e assim por diante.

Faça o mesmo para o outro lado. Por exemplo, se houver 50% de chance de e7-e5 como resposta a e2-e4, o número codificado estará entre 0 e 0,2. Repita até que o jogo termine. O resultado é um intervalo potencialmente muito pequeno. Encontre a fração binária com a menor base que se encaixa nesse intervalo. Isso é codificação aritmética.

Isso é melhor do que Huffman porque pode ser considerado como codificação de bits fracionários (mais alguns no final do jogo para arredondar para um bit inteiro).

O resultado deve ser mais compacto do que Huffman, e não há casos especiais para promoção, en passant, o movimento de 50 regras e outros detalhes, porque eles são tratados pelo programa de avaliação de xadrez.

Para jogar novamente, use novamente o programa de xadrez para avaliar o tabuleiro e atribuir todas as probabilidades a cada jogada. Use o valor aritmético codificado para determinar qual movimento foi realmente executado. Repita até terminar.

Se o seu programa de xadrez for bom o suficiente, você pode obter melhor compactação com um codificador de dois estados, onde as probabilidades são definidas com base nos movimentos para preto e branco. No caso mais extremo de mais de 200 estados, isso codifica todo o conjunto de todos os jogos de xadrez possíveis e, portanto, não é viável.

Esta é uma maneira muito diferente de dizer o que Darius já escreveu, apenas com um pequeno exemplo de como a codificação aritmética pode funcionar e um exemplo real de como usar um programa de xadrez existente para ajudar a avaliar a probabilidade do (s) próximo (s) movimento (s).