No es estrictamente una pregunta, más un rompecabezas ...

A lo largo de los años, he participado en algunas entrevistas técnicas con nuevos empleados. Aparte de hacer las preguntas estándar "¿Conoce la tecnología X?", También he tratado de tener una idea de cómo abordan los problemas. Por lo general, les enviaría la pregunta por correo electrónico el día anterior a la entrevista y espero que encuentren una solución al día siguiente.

A menudo, los resultados serían bastante interesantes, incorrectos, pero interesantes, y la persona aún obtendría mi recomendación si pudiera explicar por qué adoptó un enfoque en particular.

Así que pensé en lanzar una de mis preguntas para la audiencia de Stack Overflow.

Pregunta: ¿Cuál es la forma más eficiente en cuanto al espacio que se le ocurre para codificar el estado de una partida de ajedrez (o un subconjunto de la misma)? Es decir, dado un tablero de ajedrez con las piezas ordenadas legalmente, codifique tanto este estado inicial como todos los movimientos legales posteriores realizados por los jugadores en el juego.

No se requiere código para la respuesta, solo una descripción del algoritmo que usaría.

EDITAR: Como ha señalado uno de los carteles, no consideré el intervalo de tiempo entre movimientos. Siéntase libre de tenerlo en cuenta también como un extra opcional :)

EDIT2: Solo para una aclaración adicional ... Recuerde, el codificador / decodificador es consciente de las reglas. Lo único que realmente necesita ser almacenado son las elecciones del reproductor; cualquier otra cosa se puede asumir que el codificador / decodificador sabe.

EDIT3: Va a ser difícil elegir un ganador aquí :) ¡Muchas respuestas geniales!

Actualización: Me gustó tanto este tema que escribí Rompecabezas de programación, Posiciones de ajedrez y Codificación Huffman . Si lees esto, he determinado que la única forma de almacenar un estado de juego completo es almacenando una lista completa de movimientos. Siga leyendo para saber por qué. Así que utilizo una versión ligeramente simplificada del problema para el diseño de las piezas.

El problema

Esta imagen ilustra la posición inicial de Ajedrez. El ajedrez ocurre en un tablero de 8x8 y cada jugador comienza con un conjunto idéntico de 16 piezas que consta de 8 peones, 2 torres, 2 caballos, 2 alfiles, 1 reina y 1 rey, como se ilustra aquí:

Las posiciones generalmente se registran como una letra para la columna seguida por el número de la fila, por lo que la dama blanca está en d1. Los movimientos se almacenan con mayor frecuencia en notación algebraica , que no es ambigua y generalmente solo especifica la información mínima necesaria. Considere esta apertura:

1. e4 e5
2. Cf3 Cc6
3. ...

que se traduce en:

1. Las blancas mueven el peón de rey de e2 a e4 (es la única pieza que puede llegar a e4, de ahí “e4”);
2. Las negras mueven el peón del rey de e7 a e5;
3. Las blancas mueven el caballo (N) a f3;
4. Las negras mueven el caballo a c6.
5. ...

El tablero se ve así:

Una habilidad importante para cualquier programador es poder especificar el problema de forma correcta y sin ambigüedades .

Entonces, ¿qué falta o es ambiguo? Mucho resulta.

Estado del tablero frente al estado del juego

Lo primero que debe determinar es si está almacenando el estado de un juego o la posición de las piezas en el tablero. Codificar simplemente las posiciones de las piezas es una cosa, pero el problema dice "todos los movimientos legales posteriores". El problema tampoco dice nada sobre conocer los movimientos hasta este punto. Eso es realmente un problema, como explicaré.

Enroque

El juego ha procedido de la siguiente manera:

1. e4 e5
2. Cf3 Cc6
3. Bb5 a6
4. Aa4 Ac5

El tablero tiene el siguiente aspecto:

Las blancas tienen la opción de enroque . Parte de los requisitos para esto es que el rey y la torre correspondiente nunca se hayan movido, por lo que será necesario almacenar si el rey o cualquiera de las torres de cada bando se ha movido. Obviamente, si no están en sus posiciones iniciales, se han movido, de lo contrario, debe especificarse.

Hay varias estrategias que se pueden utilizar para abordar este problema.

En primer lugar, podríamos almacenar 6 bits adicionales de información (1 por cada torre y rey) para indicar si esa pieza se había movido. Podríamos simplificar esto almacenando solo un poco para uno de estos seis cuadrados si la pieza correcta está en él. Alternativamente, podríamos tratar cada pieza inmóvil como otro tipo de pieza, de modo que en lugar de 6 tipos de piezas en cada lado (peón, torre, caballo, alfil, reina y rey) hay 8 (agregando torre inmóvil y rey ​​inmóvil).

De paso

Otra regla peculiar y a menudo olvidada en el ajedrez es En Passant .

El juego ha progresado.

1. e4 e5
2. Cf3 Cc6
3. Bb5 a6
4. Aa4 Ac5
5. OO b5
6. Bb3 b4
7. c4

El peón negro en b4 ahora tiene la opción de mover su peón en b4 a c3 tomando el peón blanco en c4. Esto solo ocurre en la primera oportunidad, lo que significa que si las negras pasan la opción ahora, no pueden realizar el siguiente movimiento. Entonces tenemos que almacenar esto.

Si conocemos el movimiento anterior, definitivamente podemos responder si En Passant es posible. Alternativamente, podemos almacenar si cada peón en su cuarta fila acaba de moverse allí con un doble movimiento hacia adelante. O podemos mirar cada posible posición de En Passant en el tablero y tener una bandera para indicar si es posible o no.

Promoción

Es la jugada de las blancas. Si las blancas mueven su peón de h7 a h8, pueden ascender a cualquier otra pieza (pero no al rey). El 99% de las veces se asciende a Reina, pero a veces no lo es, generalmente porque eso puede forzar un punto muerto cuando, de lo contrario, ganarías. Esto está escrito como:

56. h8 = Q

Esto es importante en nuestro problema porque significa que no podemos contar con que haya un número fijo de piezas en cada lado. Es completamente posible (pero increíblemente improbable) que un bando termine con 9 reinas, 10 torres, 10 alfiles o 10 caballos si los 8 peones ascienden.

Estancamiento

Cuando esté en una posición en la que no pueda ganar, su mejor táctica es intentar un punto muerto . La variante más probable es donde no puedes hacer un movimiento legal (generalmente porque cualquier movimiento cuando pone a tu rey en jaque). En este caso, puede reclamar un empate. Este es fácil de atender.

La segunda variante es por repetición triple . Si la misma posición en el tablero ocurre tres veces en un juego (o ocurrirá una tercera vez en el próximo movimiento), se puede reclamar un empate. Las posiciones no tienen que ocurrir en ningún orden en particular (lo que significa que no tiene que repetirse la misma secuencia de movimientos tres veces). Este complica enormemente el problema porque tienes que recordar todas las posiciones anteriores de la tabla. Si este es un requisito del problema, la única solución posible al problema es almacenar cada movimiento anterior.

Por último, está la regla de los cincuenta movimientos . Un jugador puede reclamar tablas si no se ha movido ningún peón y no se ha tomado ninguna pieza en los cincuenta movimientos consecutivos anteriores, por lo que necesitaríamos almacenar cuántos movimientos desde que se movió un peón o se tomó una pieza (el último de los dos. Esto requiere 6 bits (0-63).

¿De quién es el turno?

Por supuesto, también necesitamos saber de quién es el turno y esto es un solo bit de información.

Dos problemas

Debido al caso de estancamiento, la única forma factible o sensata de almacenar el estado del juego es almacenar todos los movimientos que llevaron a esta posición. Abordaré ese problema. El problema del estado del tablero se simplificará a esto: almacenar la posición actual de todas las piezas en el tablero ignorando el enroque, al paso, las condiciones de estancamiento y de quién es el turno .

El diseño de las piezas se puede manejar de dos maneras: almacenando el contenido de cada cuadrado o almacenando la posición de cada pieza.

Contenidos simples

Hay seis tipos de piezas (peón, torre, caballo, alfil, reina y rey). Cada pieza puede ser blanca o negra, por lo que un cuadrado puede contener una de las 12 piezas posibles o puede estar vacío, por lo que hay 13 posibilidades. 13 se puede almacenar en 4 bits (0-15) Entonces, la solución más simple es almacenar 4 bits por cada cuadrado multiplicado por 64 cuadrados o 256 bits de información.

La ventaja de este método es que la manipulación es increíblemente fácil y rápida. Esto incluso podría extenderse agregando 3 posibilidades más sin aumentar los requisitos de almacenamiento: un peón que se ha movido 2 espacios en el último turno, un rey que no se ha movido y una torre que no se ha movido, lo que servirá para mucho. de los problemas mencionados anteriormente.

Pero lo podemos hacer mejor.

Codificación Base 13

A menudo es útil pensar en la posición de la junta como un número muy grande. Esto se hace a menudo en informática. Por ejemplo, el problema de la detención trata un programa de computadora (con razón) como un gran número.

La primera solución trata la posición como un número de base 16 de 64 dígitos, pero como se demostró, hay redundancia en esta información (siendo las 3 posibilidades no utilizadas por “dígito”), por lo que podemos reducir el espacio numérico a 64 dígitos de base 13. Por supuesto, esto no se puede hacer de manera tan eficiente como la base 16, pero ahorrará en los requisitos de almacenamiento (y nuestro objetivo es minimizar el espacio de almacenamiento).

En base 10, el número 234 es equivalente a 2 x 10 ² + 3 x 10 ¹ + 4 x 10 ⁰ .

En base 16, el número 0xA50 es equivalente a 10 x 16 ² + 5 x 16 ¹ + 0 x 16 ⁰ = 2640 (decimal).

Entonces podemos codificar nuestra posición como p ₀ x 13 ⁶³ + p ₁ x 13 ⁶² + ... + p ₆₃ x 13 ⁰ donde p _i representa el contenido del cuadrado i .

2 ²⁵⁶ equivale aproximadamente a 1.16e77. 13 ⁶⁴ equivale aproximadamente a 1,96e71, lo que requiere 237 bits de espacio de almacenamiento. Ese ahorro de un mero 7,5% tiene un coste de costes de manipulación significativamente mayores.

Codificación de base variable

En tableros legales, determinadas piezas no pueden aparecer en determinadas casillas. Por ejemplo, los peones no pueden aparecer en el primer u octavo rango, lo que reduce las posibilidades de esos cuadrados a 11. Eso reduce los posibles tableros a 11 ¹⁶ x 13 ⁴⁸ = 1.35e70 (aproximadamente), lo que requiere 233 bits de espacio de almacenamiento.

En realidad, codificar y decodificar dichos valores desde y hacia decimal (o binario) es un poco más complicado, pero se puede hacer de manera confiable y se deja como un ejercicio para el lector.

Alfabetos de ancho variable

Los dos métodos anteriores pueden describirse como codificación alfabética de ancho fijo . Cada uno de los 11, 13 o 16 miembros del alfabeto se sustituye por otro valor. Cada "carácter" tiene el mismo ancho, pero la eficiencia se puede mejorar si se considera que cada carácter no es igualmente probable.

Considere el código Morse (en la foto de arriba). Los caracteres de un mensaje se codifican como una secuencia de guiones y puntos. Esos guiones y puntos se transfieren por radio (normalmente) con una pausa entre ellos para delimitarlos.

Observe cómo la letra E ( la letra más común en inglés ) es un solo punto, la secuencia más corta posible, mientras que Z (la menos frecuente) es dos guiones y dos pitidos.

Tal esquema puede reducir significativamente el tamaño de un mensaje esperado , pero tiene el costo de aumentar el tamaño de una secuencia de caracteres aleatoria.

Cabe señalar que el código Morse tiene otra característica incorporada: los guiones son tan largos como tres puntos, por lo que el código anterior se crea teniendo esto en cuenta para minimizar el uso de guiones. Dado que los 1 y 0 (nuestros bloques de construcción) no tienen este problema, no es una característica que debamos replicar.

Por último, hay dos tipos de silencios en código Morse. Se utiliza un breve descanso (la longitud de un punto) para distinguir entre puntos y guiones. Se utiliza un espacio más largo (la longitud de un guión) para delimitar los caracteres.

Entonces, ¿cómo se aplica esto a nuestro problema?

Codificación Huffman

Existe un algoritmo para tratar con códigos de longitud variable llamado codificación Huffman . La codificación de Huffman crea una sustitución de código de longitud variable, normalmente utiliza la frecuencia esperada de los símbolos para asignar valores más cortos a los símbolos más comunes.

En el árbol anterior, la letra E está codificada como 000 (o izquierda-izquierda-izquierda) y S es 1011. Debe quedar claro que este esquema de codificación no es ambiguo .

Esta es una distinción importante del código Morse. El código Morse tiene el separador de caracteres, por lo que puede realizar una sustitución ambigua (por ejemplo, 4 puntos pueden ser H o ​​2 Is) pero solo tenemos 1 y 0, por lo que elegimos una sustitución no ambigua.

A continuación se muestra una implementación simple:

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

con datos 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);
}

y:

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);
    }
  }
}

Un posible resultado es:

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

Para una posición inicial, esto equivale a 32 x 1 + 16 x 3 + 12 x 5 + 4 x 6 = 164 bits.

Diferencia de estado

Otro enfoque posible es combinar el primer enfoque con la codificación de Huffman. Esto se basa en la suposición de que la mayoría de los tableros de ajedrez esperados (en lugar de los generados aleatoriamente) tienen más probabilidades que no, al menos en parte, de parecerse a una posición inicial.

Entonces, lo que hace es XOR la ​​posición actual de la placa de 256 bits con una posición de inicio de 256 bits y luego codificar eso (usando la codificación Huffman o, digamos, algún método de codificación de longitud de ejecución ). Obviamente, esto será muy eficiente para comenzar (64 0 probablemente correspondan a 64 bits) pero aumentará el almacenamiento requerido a medida que avanza el juego.

Posición de la pieza

Como se mencionó, otra forma de atacar este problema es almacenar la posición de cada pieza que tiene un jugador. Esto funciona particularmente bien con las posiciones finales donde la mayoría de los cuadrados estarán vacíos (pero en el enfoque de codificación de Huffman, los cuadrados vacíos solo usan 1 bit de todos modos).

Cada lado tendrá un rey y 0-15 piezas más. Debido a la promoción, la composición exacta de esas piezas puede variar lo suficiente como para que no pueda asumir que los números basados ​​en las posiciones iniciales son máximos.

La forma lógica de dividir esto es almacenar una posición que consta de dos lados (blanco y negro). Cada lado tiene:

• Un rey: 6 bits para la ubicación;
• Tiene peones: 1 (sí), 0 (no);
• En caso afirmativo, número de peones: 3 bits (0-7 + 1 = 1-8);
• En caso afirmativo, la ubicación de cada peón está codificada: 45 bits (ver más abajo);
• Número de no peones: 4 bits (0-15);
• Para cada pieza: tipo (2 bits para reina, torre, caballo, alfil) y ubicación (6 bits)

En cuanto a la ubicación de los peones, los peones solo pueden estar en 48 casillas posibles (no 64 como las demás). Como tal, es mejor no desperdiciar los 16 valores adicionales que usaría usar 6 bits por peón. Entonces, si tienes 8 peones, hay 48 ⁸ posibilidades, lo que equivale a 28.179.280.429.056. Necesita 45 bits para codificar esa cantidad de valores.

Eso es 105 bits por lado o 210 bits en total. Sin embargo, la posición inicial es el peor de los casos para este método y mejorará sustancialmente a medida que retire las piezas.

Cabe señalar que hay menos de 48 ⁸ posibilidades porque los peones no pueden estar todos en la misma casilla. El primero tiene 48 posibilidades, el segundo 47 y así sucesivamente. 48 x 47 x… x 41 = 1.52e13 = 44 bits de almacenamiento.

Puede mejorar aún más esto eliminando las casillas que están ocupadas por otras piezas (incluido el otro lado) para que pueda colocar primero los que no son peones blancos, luego los que no son peones negros, luego los peones blancos y finalmente los peones negros. En una posición inicial, esto reduce los requisitos de almacenamiento a 44 bits para blanco y 42 bits para negro.

Enfoques combinados

Otra posible optimización es que cada uno de estos enfoques tiene sus fortalezas y debilidades. Podría, por ejemplo, elegir los 4 mejores y luego codificar un selector de esquema en los dos primeros bits y luego el almacenamiento específico del esquema después de eso.

Con la sobrecarga tan pequeña, este será, con mucho, el mejor enfoque.

Estado del juego

Vuelvo al problema de almacenar un juego en lugar de una posición . Debido a la triple repetición, tenemos que almacenar la lista de movimientos que se han producido hasta este punto.

Anotaciones

Una cosa que debes determinar es ¿simplemente estás almacenando una lista de movimientos o estás anotando el juego? Los juegos de ajedrez a menudo se anotan, por ejemplo:

17. Bb5 !! Cc4?

El movimiento de las blancas está marcado por dos signos de exclamación como brillante, mientras que el de las negras se ve como un error. Ver puntuación de ajedrez .

Además, también podría necesitar almacenar texto libre a medida que se describen los movimientos.

Supongo que los movimientos son suficientes, por lo que no habrá anotaciones.

Notación algebraica

Simplemente podríamos almacenar el texto de la jugada aquí (“e4”, “Axb5”, etc.). Incluyendo un byte de terminación, está viendo aproximadamente 6 bytes (48 bits) por movimiento (el peor de los casos). Eso no es particularmente eficiente.

Lo segundo que debe intentar es almacenar la ubicación de inicio (6 bits) y la ubicación final (6 bits) de modo que 12 bits por movimiento. Eso es significativamente mejor.

Alternativamente, podemos determinar todos los movimientos legales desde la posición actual de una manera predecible y determinista y el estado que hemos elegido. Esto luego vuelve a la codificación base variable mencionada anteriormente. Blanco y negro tienen 20 movimientos posibles cada uno en su primer movimiento, más en el segundo y así sucesivamente.

Conclusión

No hay una respuesta absolutamente correcta a esta pregunta. Hay muchos enfoques posibles, de los cuales los anteriores son solo algunos.

Lo que me gusta de este y otros problemas similares es que exige habilidades importantes para cualquier programador, como considerar el patrón de uso, determinar con precisión los requisitos y pensar en casos de esquina.

Posiciones de ajedrez tomadas como capturas de pantalla de Chess Position Trainer .

Es mejor almacenar las partidas de ajedrez en un formato estándar legible por humanos.

La notación de juego portátil asume una posición inicial estándar (aunque no es necesario ) y solo enumera los movimientos, turno por turno. Un formato estándar compacto, legible por humanos.

P.ej

[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

Si desea hacerlo más pequeño, simplemente ciérrelo . ¡Trabajo hecho!

¡Gran rompecabezas!

Veo que la mayoría de la gente almacena la posición de cada pieza. ¿Qué tal adoptar un enfoque más simple y almacenar el contenido de cada cuadrado ? Eso se encarga de la promoción y captura de piezas de forma automática.

Y permite la codificación Huffman . En realidad, la frecuencia inicial de piezas en el tablero es casi perfecta para esto: la mitad de los cuadrados están vacíos, la mitad de los cuadrados restantes son peones, etcétera.

Teniendo en cuenta la frecuencia de cada pieza, construí un árbol de Huffman en papel, que no repetiré aquí. El resultado, donde crepresenta el color (blanco = 0, negro = 1):

• 0 para cuadrados vacíos
• 1c0 para peón
• 1c100 para torre
• 1c101 para caballero
• 1c110 para obispo
• 1c1110 para reina
• 1c1111 para rey

Para toda la junta en su situación inicial, tenemos

• cuadrados vacíos: 32 * 1 bit = 32 bits
• peones: 16 * 3 bits = 48 bits
• torres / caballeros / alfiles: 12 * 5 bits = 60 bits
• reinas / reyes: 4 * 6 bits = 24 bits

Total: 164 bits para el estado inicial de la placa. Significativamente menos que los 235 bits de la respuesta más votada actualmente. Y solo se hará más pequeño a medida que avanza el juego (excepto después de una promoción).

Solo miré la posición de las piezas en el tablero; El estado adicional (cuyo turno, quién ha enrocado, al paso, movimientos repetidos, etc.) deberá codificarse por separado. Quizás otros 16 bits como máximo, es decir, 180 bits para todo el estado del juego. Posibles optimizaciones:

• Dejando fuera las piezas menos frecuentes y almacenando su posición por separado. Pero eso no ayudará ... reemplazar el rey y la reina por un cuadrado vacío ahorra 5 bits, que son exactamente los 5 bits que necesita para codificar su posición de otra manera.
• "No hay peones en la última fila" podría codificarse fácilmente usando una tabla de Huffman diferente para las últimas filas, pero dudo que ayude mucho. Probablemente terminarías con el mismo árbol de Huffman.
• Se puede codificar "Un alfil blanco, un alfil negro" introduciendo símbolos adicionales que no tienen el cbit, que luego se pueden deducir de la casilla en la que está el alfil. (Los peones ascendidos a alfiles interrumpen este esquema ...)
• Las repeticiones de cuadrados vacíos se pueden codificar en longitud de ejecución introduciendo símbolos adicionales para, por ejemplo, "2 cuadrados vacíos en una fila" y "4 cuadrados vacíos en una fila". Pero no es tan fácil estimar la frecuencia de estos, y si se equivoca, será más doloroso que útil.

El enfoque de tabla de búsqueda realmente grande

Posición - 18 bytes
El número estimado de posiciones legales es 10 ⁴³
Simplemente enumere todas y la posición se puede almacenar en solo 143 bits. Se requiere 1 bit más para indicar qué lado jugará a continuación

La enumeración no es práctica, por supuesto, pero esto muestra que se requieren al menos 144 bits.

Movimientos - 1 byte
Generalmente hay alrededor de 30-40 movimientos legales para cada posición, pero el número puede ser tan alto como 218. Vamos a enumerar todos los movimientos legales para cada posición. Ahora cada movimiento se puede codificar en un byte.

Todavía tenemos mucho espacio para movimientos especiales como 0xFF para representar la renuncia.

Agregaría interés para optimizar el tamaño de caso promedio para juegos típicos jugados por humanos, en lugar del peor de los casos. (El enunciado del problema no dice cuál; ​​la mayoría de las respuestas asumen el peor de los casos).

Para la secuencia de movimientos, tenga un buen motor de ajedrez que genere movimientos desde cada posición; producirá una lista de k posibles movimientos, ordenados por su clasificación de calidad. La gente generalmente elige buenos movimientos con más frecuencia que movimientos aleatorios, por lo que necesitamos aprender un mapeo de cada posición en la lista de la probabilidad de que la gente elija un movimiento que sea "bueno". Usando estas probabilidades (basadas en un corpus de juegos de alguna base de datos de ajedrez de Internet), codifique los movimientos con codificación aritmética . (El decodificador debe usar el mismo motor de ajedrez y mapeo).

Para la posición inicial, el enfoque de ralu funcionaría. También podríamos refinarlo con codificación aritmética allí, si tuviéramos alguna forma de ponderar las opciones por probabilidad, por ejemplo, las piezas a menudo aparecen en configuraciones que se defienden entre sí, no al azar. Es más difícil ver una manera fácil de incorporar ese conocimiento. Una idea: recurra a la codificación de movimientos anterior, comenzando desde la posición de apertura estándar y encontrando una secuencia que termine en el tablero deseado. (Puede intentar una búsqueda A * con una distancia heurística que iguale la suma de las distancias de las piezas desde sus posiciones finales, o algo por el estilo). Esto cambia cierta ineficiencia por sobreespecificar la secuencia de movimientos frente a la eficiencia por aprovechar el juego de ajedrez conocimiento.

También es un poco difícil estimar cuánto ahorraría esto en una complejidad de caso promedio, sin recopilar algunas estadísticas de un corpus real. Pero el punto de partida con todos los movimientos igualmente probables creo que ya superaría la mayoría de las propuestas aquí: la codificación aritmética no necesita un número entero de bits por movimiento.

Atacar un subproblema de codificar los pasos después de codificar una posición inicial. El enfoque es crear una "lista vinculada" de pasos.

Cada paso del juego se codifica como el par "posición anterior-> nueva posición". Conoces la posición inicial al comienzo del juego de ajedrez; recorriendo la lista vinculada de pasos, puede llegar al estado después de que X se mueva.

Para codificar cada paso, necesita 64 valores para codificar la posición inicial (6 bits para 64 cuadrados en el tablero - 8x8 cuadrados) y 6 bits para la posición final. 16 bits para 1 movimiento de cada lado.

La cantidad de espacio que ocuparía codificar un juego dado es proporcional al número de movimientos:

10 x (número de movimientos blancos + número de movimientos negros) bits.

ACTUALIZACIÓN: posible complicación con peones promocionados. Necesita poder indicar a qué se promueve el peón; puede necesitar bits especiales (usaría un código gris para esto para ahorrar espacio, ya que la promoción de peón es extremadamente rara).

ACTUALIZACIÓN 2: No es necesario codificar las coordenadas completas de la posición final. En la mayoría de los casos, la pieza que se mueve no puede moverse a más de X lugares. Por ejemplo, un peón puede tener un máximo de 3 opciones de movimiento en cualquier momento. Al darnos cuenta de ese número máximo de movimientos para cada tipo de pieza, podemos ahorrar bits en la codificación del "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

Entonces la complejidad espacial por movimiento de blanco o negro se vuelve

6 bits para la posición inicial + (número variable de bits según el tipo de cosa que se mueve).

Vi esta pregunta anoche y me intrigó, así que me senté en la cama pensando en soluciones. Mi respuesta final es bastante similar a la de int3 en realidad.

Solucion basica

Suponiendo un juego de ajedrez estándar y que no codifica las reglas (como si las blancas siempre van primero), entonces puede ahorrar mucho codificando solo los movimientos que hace cada pieza.

Hay 32 piezas en total, pero en cada movimiento sabes qué color se está moviendo, por lo que solo hay 16 cuadrados de los que preocuparte, que son 4 bits para qué pieza se mueve este turno.

Cada pieza solo tiene un conjunto de movimientos limitado, que enumerarías de alguna manera.

• Peón: 4 opciones, 2 bits (1 paso adelante, 2 pasos adelante, 1 cada diagonal)
• Torre: 14 opciones, 4 bits (máximo de 7 en cada dirección)
• Bishop: 13 opciones, 4 bits (si tienes 7 en una diagonal, solo tienes 6 en la otra)
• Caballero: 8 opciones, 3 bits
• Reina: 27 opciones, 5 bits (Torre + Alfil)
• Rey: 9 opciones, 4 bits (8 movimientos de un paso, más la opción de enroque)

Para la promoción, hay 4 piezas para elegir (Torre, Alfil, Caballo, Reina), por lo que en ese movimiento agregaríamos 2 bits para especificar eso. Creo que todas las demás reglas se cubren automáticamente (por ejemplo, al paso).

Más optimizaciones

Primero, después de capturar 8 piezas de un color, puede reducir la codificación de piezas a 3 bits, luego a 2 bits para 4 piezas y así sucesivamente.

Sin embargo, la principal optimización es enumerar solo los movimientos posibles en cada punto del juego. Supongamos que almacenamos los movimientos de un Peón como {00, 01, 10, 11}si fueran 1 paso adelante, 2 pasos adelante, diagonal izquierda y diagonal derecha respectivamente. Si algunos movimientos no son posibles, podemos eliminarlos de la codificación para este turno.

Conocemos el estado del juego en cada etapa (después de seguir todos los movimientos), por lo que después de leer qué pieza se moverá, siempre podemos determinar cuántos bits necesitamos leer. Si nos damos cuenta de que los únicos movimientos de un peón en este punto son capturar en diagonal a la derecha o avanzar uno, sabemos que solo leemos 1 bit.

En resumen, el almacenamiento de bits mencionado anteriormente para cada pieza es solo un máximo . Casi todos los movimientos tendrán menos opciones y, a menudo, menos bits.

En cada posición obtenga el número de todos los movimientos posibles.

el siguiente movimiento se genera como

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

Probablemente la mejor eficiencia de espacio para almacenar juegos generados aleatoriamente y necesita aproximadamente 5 bits / movimiento en promedio, ya que tiene 30-40 movimientos posibles. El almacenamiento de ensamblaje solo genera n en orden inverso.

La posición de almacenamiento es más difícil de romper debido a la gran redundancia. (Puede haber hasta 9 reinas en el tablero para un sitio, pero en ese caso no hay peones, y los alfiles si están en el tablero están en cuadrados de colores opuestos) pero generalmente es como almacenar una combinación de las mismas piezas sobre los cuadrados restantes).

EDITAR:

El punto de guardar movimientos es almacenar solo el índice de movimiento. En lugar de almacenar Kc1-c2 y tratar de reducir esta información, debemos agregar solo el índice de movimiento generado a partir de movegenerator determinista (posición)

En cada movimiento agregamos información de tamaño

num_of_moves = get_number_of_possible_moves(postion) ;

en la piscina y este número no se puede reducir

la generación de grupo de información es

n=n*num_of_moves+ index_current_move

extra

Si solo hay un movimiento disponible en la posición final, guárdelo como el número de movimientos forzados realizados anteriormente. Ejemplo: si la posición inicial tiene 1 movimiento forzado para cada lado (2 movimientos) y queremos guardar esto como un juego de un movimiento, almacene 1 en el grupo n.

ejemplo de almacenamiento en grupo de información

Supongamos que conocemos posiciones iniciales y hacemos 3 movimientos.

En el primer movimiento hay 5 movimientos disponibles, y tomamos el índice de movimiento 4. En el segundo movimiento hay 6 movimientos disponibles y tomamos el índice de posición 3 y en el 3º movimiento hay 7 movimientos disponibles para ese lado y él eligió elegir el índice de movimiento. 2.

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

Estamos codificando esta información al revés, por lo que n = 4 + 5 * (3 + 6 * (2)) = 79 (no es necesario multiplicar por 7)

¿Cómo desbloquear esto? Primero tenemos la posición y descubrimos que hay 5 movimientos disponibles. Entonces

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

Tomamos el índice de movimiento 4 y examinamos la posición nuevamente y desde este punto encontramos que hay 6 movimientos posibles.

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

Y tomamos el índice de movimientos 3 que nos lleva a una posición con 7 movimientos posibles.

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

Hacemos el último movimiento índice 2 y llegamos a la posición final.

Como puede ver, la complejidad del tiempo es O (n) y la complejidad del espacio es O (n). Editar: la complejidad del tiempo es en realidad O (n ^ 2) porque el número que multiplica por aumenta, pero no debería haber problemas para almacenar juegos de hasta 10,000 movimientos.

posición de ahorro

Se puede hacer cerca del óptimo.

Cuando averigüemos acerca de la información y el almacenamiento de información, permítame hablar más al respecto. La idea general es disminuir la redundancia (hablaré de eso más adelante). Supongamos que no hubo ascensos ni tomas, por lo que hay 8 peones, 2 torres, 2 caballos, 2 alfiles, 1 rey y 1 reina por lado.

Qué tenemos que salvar: 1. Posición de cada paz 2. Posibilidades de enroque 3. Posibilidades de en-passant 4. Bando que tiene movimiento disponible

Supongamos que cada pieza puede colocarse en cualquier lugar, pero no 2 piezas en el mismo lugar. La cantidad de formas en que se pueden colocar 8 peones del mismo color a bordo es C (64/8) (binomio), que es de 32 bits, luego 2 torres 2R-> C (56/2), 2B -> C (54/2) , 2N-> C (52/2), 1Q-> C (50/1), 1K -> C (49/1) y lo mismo para otro sitio pero comenzando con 8P -> C (48/8) y así sucesivamente .

Multiplicando esto para ambos sitios, obtenemos el número 4634726695587809641192045982323285670400000 que es aproximadamente 142 bits, tenemos que agregar 8 para un posible en-passant (el peón en-passant puede estar en uno de 8 lugares), 16 (4 bits) para limitaciones de enroque y un poco para el sitio que se ha movido. Terminamos con 142 + 3 + 4 + 1 = 150 bits

Pero ahora vayamos a la caza de la redundancia en el tablero con 32 piezas y sin tomar.

1. Ambos peones blancos y negros están en la misma columna y uno frente al otro. Cada peón se enfrenta a otro peón, lo que significa que el peón blanco puede estar como máximo en el sexto rango. Esto nos trae 8 * C (6/2) en lugar de C (64/8) * C (48/8) que disminuye la información en 56 bits.

2. La posibilidad de enroque también es redundante. Si las torres no están en el lugar de inicio, no hay posibilidad de enroque con esa torre. Así que imaginamos que podemos añadir 4 casillas en el tablero para obtener información extra si es posible enrocar con esta torre y eliminar 4 bits de enroque. Entonces, en lugar de C (56/2) * C (40/2) * 16 tenemos C (58/2) * C (42/2) y perdimos 3.76 bits (casi todos de 4 bits)

3. en-passant: Cuando almacenamos una de 8 posibilidades en passant, conocemos la posición del peón negro y reducimos la redindancia informativa (si es un movimiento blanco y tiene un 3er peón en-passant, eso significa que el peón negro está en c5 y el peón blanco es c2, c3 o c4) así que en lugar de C (6/2) tenemos 3 y perdimos 2.3 bits. Disminuimos algo de redundancia si almacenamos con número al paso también lado desde el que se puede hacer (3 posibilidades-> izquierda, derecha, ambas) y sabemos la posibilidad de peón que puede tomar al paso. (por ejemplo, del ejemplo anterior al paso con negro en c5, lo que puede estar en la izquierda, la derecha o en ambos. Si está en un sitio, tenemos 2 * 3 (3 para almacenar psisibilidades y 2 movimientos posibles para el peón negro en la séptima o sexta fila). ) en lugar de C (6/2) y reducimos en 1,3 bits y si en ambos lados reducimos en 4,2 bits, así podemos reducir en 2,3 + 1,3 = 3.

4. obispos: los bisops solo pueden estar en cuadrados opostite, esto reduce la redundancia en 1 bit para cada sitio.

Si sumamos, necesitamos 150-56-4-3.6-2 = 85 bits para almacenar la posición del ajedrez si no hubo ganancias.

Y probablemente no mucho más si se tienen en cuenta las recaudaciones y las promociones (pero escribiré sobre eso más adelante si alguien encuentra útil esta publicación larga)

La mayoría de la gente ha estado codificando el estado de la placa, pero con respecto a los movimientos en sí ... Aquí hay una descripción de la codificación de bits.

Bits por pieza:

• ID de pieza: Max 4 bits para identificar las 16 piezas por lado. Se puede inferir blanco / negro. Tener un orden definido en las piezas. A medida que el número de piezas desciende por debajo de las respectivas potencias de dos, utilice menos bits para describir las piezas restantes.
• Empeñar: 3 posibilidades en el primer movimiento, por lo que +2 bits (hacia adelante en una o dos casillas, al paso). Los movimientos posteriores no permiten avanzar en dos, por lo que +1 bit es suficiente. La promoción se puede inferir en el proceso de decodificación notando cuándo el peón ha alcanzado el último rango. Si se sabe que el peón ha sido promovido, el decodificador esperará otros 2 bits que indiquen a cuál de las 4 piezas principales se ha promocionado.
• Bishop: +1 bit para la diagonal utilizada, hasta +4 bits para la distancia a lo largo de la diagonal (16 posibilidades). El decodificador puede inferir la distancia máxima posible a la que la pieza puede moverse a lo largo de esa diagonal, por lo que si es una diagonal más corta, use menos bits.
• Caballero: 8 movimientos posibles, +3 bits
• Torre: +1 bit para horizontal / vertical, +4 bits para distancia a lo largo de la línea.
• Rey: 8 movimientos posibles, +3 bits. Indique el enroque con un movimiento "imposible", dado que el enroque solo es posible mientras el rey está en la primera fila, codifique este movimiento con una instrucción para mover al rey "hacia atrás", es decir, fuera del tablero.
• Reina: 8 direcciones posibles, + 3 bits. Hasta +4 bits más para la distancia a lo largo de la línea / diagonal (menos si la diagonal es más corta, como en el caso del alfil)

Suponiendo que todas las piezas están en el tablero, estos son los bits por movimiento: Peón: 6 bits en el primer movimiento y 5 en el siguiente. 7 si asciende. Alfil: 9 bits (máx.), Caballo: 7, Torre: 9, Rey: 7, Reina: 11 (máx.).

¿El problema es dar una codificación que sea más eficiente para las partidas de ajedrez típicas o una que tenga la codificación más corta en el peor de los casos?

Para este último, la forma más eficiente es también la más opaca: crear una enumeración de todos los pares posibles (tablero inicial, secuencia legal de movimientos), que, con la posición de dibujar-en-tres-veces-repetidas y no-más-de -cincuenta-movimientos desde las reglas del último peón-movimiento-o-captura, es recursivo. Entonces, el índice de una posición en esta secuencia finita da la codificación más corta en el peor de los casos, pero también una codificación igualmente larga para los casos típicos y es, espero, muy costoso de calcular. Se supone que el juego de ajedrez más largo posible tiene más de 5000 movimientos, y normalmente hay entre 20 y 30 movimientos disponibles en cada posición para cada jugador (aunque menos cuando quedan pocas piezas); esto da algo así como 40000 bits necesarios para esta codificación.

La idea de enumeración se puede aplicar para dar una solución más manejable, como se describe en la sugerencia de Henk Holterman para codificar movimientos más arriba. Mi sugerencia: no mínima, pero más corta que los ejemplos anteriores que he visto, y razonablemente manejable:

1. 64 bits para representar qué casillas están ocupadas (matriz de ocupación), más una lista de qué piezas están en cada casilla ocupada (puede tener 3 bits para peones y 4 bits para otras piezas): esto da 190 bits para la posición inicial. Dado que no puede haber más de 32 piezas a bordo, la codificación de la matriz de ocupación es redundante, por lo que se pueden codificar posiciones comunes de la placa, por ejemplo, como 33 bits establecidos más el índice de la placa de la lista de placas comunes.

2. 1 bit para decir quién da el primer paso

3. El código se mueve según la sugerencia de Henk: típicamente 10 bits por par de movimiento blanco / negro, aunque algunos movimientos tomarán 0 bits, cuando un jugador no tiene movimientos alternativos.

Esto sugiere 490 bits para codificar un juego típico de 30 movimientos, y sería una representación razonablemente eficiente para juegos típicos.

Sobre la codificación de la posición de robar tres veces repetida y no más de cincuenta movimientos desde las reglas del último movimiento o captura del peón: si codifica los movimientos anteriores hasta el último movimiento o captura del peón, entonces Tener suficiente información para decidir si se aplican estas reglas: no es necesario el historial completo del juego.

La posición en una placa se puede definir en 7 bits (0-63 y 1 valor que especifica que ya no está en la placa). Por lo tanto, para cada pieza del tablero, especifique dónde se encuentra.

32 piezas * 7 bits = 224 bits

EDITAR: como señaló Cadrian ... también tenemos el caso del 'peón ascendido a reina'. Sugiero que agreguemos bits adicionales al final para indicar qué peón ha sido promovido.

Entonces, para cada peón que ha sido promovido seguimos los 224 bits con 5 bits que indican el índice del peón que ha sido promovido, y 11111 si es el final de la lista.

Entonces, el caso mínimo (sin promociones) es de 224 bits + 5 (sin promociones). Por cada peón promovido, agregue 5 bits.

EDITAR: Como señala Shaggy Frog, necesitamos otro bit al final para indicar de quién es el turno; ^)

Usaría una codificación de longitud de ejecución. Algunas piezas son únicas (o existen solo dos veces), por lo que puedo omitir la longitud después de ellas. Como cletus, necesito 13 estados únicos, por lo que puedo usar un nibble (4 bits) para codificar la pieza. El tablero inicial se vería así:

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

lo que me deja con 8 + 2 + 4 + 2 + 8 nibbles = 24 nibbles = 96 bits. No puedo codificar 16 con un nibble, pero como "Empty, 0" no tiene sentido, puedo tratar "0" como "16".

Si el tablero está vacío, excepto por un solo peón en la esquina superior izquierda, aparece "Peón, 1, Vacío, 16, Vacío, 16, Vacío 16, Vacío, 15" = 10 mordiscos = 40 bits.

El peor de los casos es cuando tengo un cuadrado vacío entre cada pieza. Pero para la codificación de la pieza, solo necesito 13 de los 16 valores, así que quizás pueda usar otro para decir "Empty1". Entonces, necesito 64 nibbles == 128bits.

Para los movimientos, necesito 3 bits para la pieza (el color viene dado por el hecho de que el blanco siempre se mueve primero) más 5 bits (0..63) para la nueva posición = un byte por movimiento. La mayoría de las veces, no necesito la posición anterior, ya que solo una pieza estará dentro del rango. Para el caso extraño, debo usar el código único sin usar (solo necesito 7 códigos para codificar la pieza) y luego 5 bits para la posición anterior y 5 bits para la nueva posición.

Esto me permite codificar el enroque en 13 bocados (puedo mover al Rey hacia la Torre, lo cual es suficiente para decir lo que pretendo).

[EDITAR] Si permite un codificador inteligente, entonces necesito 0 bits para la configuración inicial (porque no tiene que estar codificado de ninguna manera: es estático) más un byte por movimiento.

[EDIT2] Lo que deja la transformación de peones. Si un peón llega a la última fila, puedo moverlo a su lugar para decir "transforma" y luego agregar los 3 bits de la pieza con la que se reemplaza (no tienes que usar una reina; puedes reemplazar el peón con cualquier cosa pero el Rey).

Al igual que codifican juegos en libros y papeles: cada pieza tiene un símbolo; ya que es un juego "legal", las blancas mueven primero; no es necesario codificar blanco o negro por separado, solo cuenta el número de movimientos para determinar quién se movió. Además, cada movimiento se codifica como (pieza, posición final) donde la 'posición final' se reduce a la menor cantidad de símbolos que permite discernir ambigüedades (puede ser cero). La duración del juego determina el número de movimientos. También se puede codificar el tiempo en minutos (desde el último movimiento) en cada paso.

La codificación de la pieza se puede hacer asignando un símbolo a cada una (32 en total) o asignando un símbolo a la clase, y usar la posición final para entender cuál pieza se movió. Por ejemplo, un peón tiene 6 posibles posiciones finales; pero, en promedio, solo un par está disponible en cada esquina. Entonces, estadísticamente, la codificación por posición final podría ser la mejor para este escenario.

Se utilizan codificaciones similares para trenes de picos en neurociencia computacional (AER).

Inconvenientes: es necesario volver a jugar todo el juego para llegar al estado actual y generar un subconjunto, muy parecido a atravesar una lista vinculada.

Hay 64 posiciones de placa posibles, por lo que necesita 6 bits por posición. Hay 32 piezas iniciales, por lo que tenemos un total de 192 bits hasta ahora, donde cada 6 bits indica la posición de la pieza dada. Podemos predeterminar el orden en que aparecen las piezas, por lo que no tenemos que decir cuál es cuál.

¿Qué pasa si una pieza está fuera del tablero? Bueno, podemos colocar una pieza en el mismo lugar que otra para indicar que está fuera del tablero, ya que de lo contrario sería ilegal. Pero tampoco sabemos si la primera pieza estará en el tablero o no. Entonces agregamos 5 bits indicando qué pieza es la primera (32 posibilidades = 5 bits para representar la primera pieza). Luego, podemos usar ese lugar para las piezas posteriores que están fuera del tablero. Eso nos lleva a 197 bits en total. Tiene que haber al menos una pieza en el tablero, para que funcione.

Entonces necesitamos un bit para quién es el turno, lo que nos lleva a 198 bits .

¿Qué pasa con la promoción de peones? Podemos hacerlo de una mala manera agregando 3 bits por peón, agregando 42 bits. Pero luego podemos notar que la mayoría de las veces, los peones no ascienden.

Entonces, por cada peón que está en el tablero, el bit '0' indica que no está promocionado. Si un peón no está en el tablero, no necesitamos nada en absoluto. Entonces podemos usar cadenas de bits de longitud variable para qué promoción tiene. La mayoría de las veces será una reina, por lo que "10" puede significar REINA. Entonces "110" significa torre, "1110" significa alfil y "1111" significa caballo.

El estado inicial tomará 198 + 16 = 214 bits , ya que los 16 peones están en el tablero y no promocionados. Un final de partida con dos peones-reinas promovidos podría tomar algo como 198 + 4 + 4, lo que significa 4 peones vivos y no promocionados y 2 peones de reina, por 206 bits. total de . ¡Parece bastante robusto!

===

La codificación de Huffman, como han señalado otros, sería el siguiente paso. Si observa algunos millones de juegos, notará que es mucho más probable que cada pieza esté en ciertos cuadrados. Por ejemplo, la mayoría de las veces, los peones permanecen en línea recta, o uno a la izquierda / uno a la derecha. El rey normalmente se quedará en la base de operaciones.

Por lo tanto, diseñe un esquema de codificación de Huffman para cada posición separada. Los peones probablemente solo tomarán un promedio de 3-4 bits en lugar de 6. El rey también debería tomar algunos bits.

También en este esquema, incluya "tomado" como una posición posible. Esto también puede manejar el enroque de manera muy robusta: cada torre y rey ​​tendrá un estado adicional de "posición original, movido". También puede codificar en passant en los peones de esta manera - "posición original, puede en passant".

Con suficientes datos, este enfoque debería producir resultados realmente buenos.

Intentaría usar la codificación Huffman . La teoría detrás de esto es que en cada juego de ajedrez habrá algunas piezas que se moverán mucho y otras que no se moverán mucho o serán eliminadas temprano. Si ya se han quitado algunas piezas de la posición inicial, mucho mejor. Lo mismo ocurre con los cuadrados: algunos pueden ver toda la acción, mientras que otros no se tocan mucho.

Por lo tanto, tendría dos mesas de Huffman, una para piezas y otra para cuadrados. Se generarán observando el juego real. Podría tener una mesa grande para cada par pieza-cuadrado, pero creo que sería bastante ineficiente porque no hay muchas instancias de la misma pieza moviéndose nuevamente en el mismo cuadrado.

Cada pieza tendría una identificación asignada. Como hay 32 piezas diferentes, necesitaría solo 5 bits para la identificación de la pieza. Los ID de las piezas no cambian de un juego a otro. Lo mismo ocurre con los ID cuadrados, para los que necesitaría 6 bits.

Los árboles de Huffman se codificarían escribiendo cada nodo a medida que se atraviesan en orden (es decir, primero se genera el nodo y luego sus hijos de izquierda a derecha). Para cada nodo habrá un bit que especificará si es un nodo hoja o un nodo de rama. Si es un nodo hoja, irá seguido de los bits que dan el ID.

La posición inicial simplemente vendrá dada por una serie de pares de ubicación de pieza. Después de eso, habrá un par pieza-ubicación para cada movimiento. Puede encontrar el final del descriptor de posición inicial (y el inicio del descriptor de movimientos) simplemente encontrando la primera pieza que se menciona dos veces. En caso de que un peón sea promovido, habrá 2 bits adicionales que especifican en qué se convierte, pero el ID de la pieza no cambiará.

Para tener en cuenta la posibilidad de que se promueva un peón al comienzo del juego, también habrá una "tabla de promoción" entre los árboles huffman y los datos. Al principio, habrá 4 bits que especifican cuántos peones se actualizan. Luego, para cada peón habrá su ID codificada en huffman y 2 bits que especifiquen en qué se ha convertido.

Los árboles de huffman se generarán teniendo en cuenta todos los datos (tanto la posición inicial como los movimientos) y la tabla de promoción. Aunque normalmente la mesa de promoción estará vacía o tendrá pocas entradas.

Para resumirlo en términos 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>)

Agregado: esto aún podría optimizarse. Cada pieza solo tiene unos pocos movimientos legales. En lugar de simplemente codificar el cuadrado de destino, se podrían dar ID basados ​​en 0 para los posibles movimientos de cada pieza. Los mismos ID se reutilizarían para cada pieza, por lo que en total no habría más de 21 ID diferentes (la reina puede tener como máximo 21 diferentes opciones de movimiento posibles). Pon esto en una tabla de huffman en lugar de en los campos.

Sin embargo, esto presentaría una dificultad para representar el estado original. Se podría generar una serie de movimientos para poner cada pieza en su lugar. En este caso, sería necesario marcar de alguna manera el final del estado inicial y el inicio de los movimientos.

Alternativamente, podrían colocarse utilizando ID cuadrados de 6 bits sin comprimir.

Si esto presentaría una disminución general de tamaño, no lo sé. Probablemente, pero debería experimentar un poco.

Agregado 2: Un caso especial más. Si el estado del juego NO tiene movimientos, es importante distinguir quién se mueve a continuación. Agregue un poco más al final para eso. :)

[editado después de leer la pregunta correctamente] Si asume que se puede alcanzar cada posición legal desde la posición inicial (que es una posible definición de "legal"), entonces cualquier posición puede expresarse como la secuencia de movimientos desde el principio. Un fragmento de juego que comienza desde una posición no estándar se puede expresar como la secuencia de movimientos necesarios para llegar al inicio, un interruptor para encender la cámara, seguido de movimientos posteriores.

Así que llamemos al estado inicial de la placa el bit único "0".

Los movimientos desde cualquier posición se pueden enumerar numerando los cuadrados y ordenando los movimientos por (inicio, fin), con el salto convencional de 2 cuadrados indicando enroque. No es necesario codificar movimientos ilegales, porque la posición del tablero y las reglas siempre se conocen. La bandera para encender la cámara podría expresarse como un movimiento especial dentro de la banda, o más sensiblemente como un número de movimiento fuera de banda.

Hay 24 movimientos de apertura para cada lado, que pueden caber en 5 bits cada uno. Los movimientos posteriores pueden requerir más o menos bits, pero los movimientos legales siempre son enumerables, por lo que el ancho de cada movimiento puede crecer o expandirse felizmente. No lo he calculado, pero imagino que las posiciones de 7 bits serían raras.

Con este sistema, un juego de 100 medios movimientos podría codificarse en aproximadamente 500 bits. Sin embargo, sería conveniente utilizar un libro de aperturas. Suponga que contiene un millón de secuencias. Entonces, un 0 inicial indica un inicio desde la placa estándar, y un 1 seguido de un número de 20 bits indica un inicio desde esa secuencia de apertura. Los juegos con aperturas algo convencionales pueden acortarse en, digamos, 20 medios movimientos, o 100 bits.

Esta no es la mayor compresión posible, pero (sin el libro de apertura) sería muy fácil de implementar si ya tiene un modelo de ajedrez, lo que asume la pregunta.

Para comprimir aún más, querrá ordenar los movimientos de acuerdo con la probabilidad en lugar de en un orden arbitrario, y codificar las secuencias probables en menos bits (usando, por ejemplo, tokens de Huffman como la gente ha mencionado).

Si el tiempo computacional no es un problema, entonces puede usar un generador de posición posible determinista para asignar identificadores únicos a una posición determinada.

Desde una posición dada, primero genere un número de posiciones posibles en una mansión determinista, por ejemplo, comenzando desde abajo a la izquierda hacia arriba a la derecha. Eso determina cuántos bits necesitará para el próximo movimiento; en algunas situaciones, podría ser tan pequeño como uno. Luego, cuando se realiza el movimiento, almacene solo la identificación única para ese movimiento.

La promoción y otras reglas simplemente cuentan como jugadas válidas siempre que se manejen de una manera determinista, por ejemplo, a la reina, a la torre, al alfil, cada una cuenta como una jugada separada.

La posición inicial es la más difícil y podría generar alrededor de 250 millones de posiciones posibles (creo) que requerirían alrededor de 28 bits más un bit extra para determinar de quién es el movimiento.

Suponiendo que sepamos quién es el turno (cada turno cambia de blanco a negro), el generador determinista se vería así:

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

'obtener una lista de posibles movimientos' haría 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.

Si el rey está en jaque, entonces cada 'lista de posibles movimientos xxx' solo devuelve movimientos válidos que cambian la situación de jaque.

La mayoría de las respuestas pasaron por alto la repetición triple. Desafortunadamente, para la repetición de 3 veces, debe almacenar todas las posiciones jugadas hasta ahora ...

La pregunta requería que almacenáramos de manera eficiente en el espacio, por lo que realmente no necesitamos almacenar la posición siempre que podamos construirla a partir de la lista de movimientos (siempre que tengamos una posición inicial estándar). Podemos optimizar PGN y eso es todo. Bellow es un esquema simple.

Hay 64 casillas en el tablero, 64 = 2 ^ 6. Si almacenamos sólo la casilla inicial y final de cada movimiento, eso tomaría 12 bits (la promoción se abordará más adelante). Tenga en cuenta que este esquema ya cubre jugador para mover, enfatizar, pieza capturada, enroque, etc. a partir de estos se pueden construir simplemente reproduciendo la lista de movimientos.

para la promoción, podemos mantener una matriz separada de vectores que dirían "en el movimiento N promover a la pieza XYZ". podemos mantener un vector de (int, byte).

Es tentador optimizar también el vector (Hasta, Desde), ya que muchos de estos vectores (Hasta, Desde) no son posibles en el ajedrez. p.ej. no habrá un movimiento de e1 a d8, etc. Pero no se me ocurrió ningún esquema. Cualquier otra idea es bienvenida.

He pensado en eso durante mucho tiempo (+ - 2 horas). Y no hay respuestas obvias.

Asumiendo:

1. Ignorar el estado de tiempo (un jugador no solía tener un límite de tiempo, por lo tanto, podría forzar un empate al no jugar)
2. ¿Cuándo se jugó el juego? Es importante porque las reglas han cambiado con el tiempo (por lo que asumiremos un juego moderno en el punto siguiente, un juego moderno ...) Por favor, consulte la regla del peón muerto, por ejemplo (wikipedia tiene un problema muy famoso para mostrarlo), y si lo desea para retroceder en el tiempo, el alfil de la buena suerte solía moverse lentamente y solía usarse los dados. lol.

... tan actualizadas las reglas modernas. Primero, independientemente de la repetición y el límite de repetición del movimiento.

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

= 64 bits (algo / nada) + 32 * 4 bits [1bit = color {negro / blanco} + 3bit = tipo de pieza {Rey, Reina, Alfil, kNoche, Torre, Peón, Peón movido} NB: Peón movido ... por ejemplo, si fue el último peón movido en el turno anterior, lo que indica que es factible un "al paso". ] + 5 bits para el estado actual (quién es el turno, al paso, posibilidad de hacer torre o no en ambos lados)

Hasta aquí todo bien. Probablemente se pueda mejorar, pero entonces habría que tener en cuenta la duración y la promoción variables.

Ahora, las siguientes reglas solo son aplicables CUANDO un jugador solicita un sorteo, ¡NO ES automático! ¡Así que considere que estos 90 movimientos sin una captura o un movimiento de peón son factibles si ningún jugador pide tablas! Lo que significa que todos los movimientos deben registrarse ... y estar disponibles.

-D repetición de la posición ... por ejemplo, estado del tablero como se mencionó anteriormente (ver C) o no ... (ver a continuación con respecto a las reglas de la FIDE) -E Eso deja el complejo problema de la asignación de 50 movimientos sin captura o movimiento de peón allí contador es necesario ... Sin embargo.

Entonces, ¿cómo lidias con eso? ... Bueno, realmente no hay manera. Porque ninguno de los jugadores puede querer dibujar o darse cuenta de que ha ocurrido. Ahora, en caso de que E, un contador podría ser suficiente ... pero aquí está el truco e incluso leyendo las reglas de la FIDE (http://www.fide.com/component/handbook/?id=124&view=article) no puedo encontrar un respuesta ... ¿qué pasa con la pérdida de capacidad de torre? ¿Eso es una repetición? Creo que no, pero este es un tema borroso que no se aborda, no se aclara.

Así que aquí hay dos reglas que son dos complejas o indefinidas incluso para intentar codificarlas ... Saludos.

Entonces, la única forma de codificar realmente un juego es grabar todo desde el principio ... lo que luego entra en conflicto (¿o no?) Con la pregunta del "estado del tablero".

Espero que esto ayude ... no demasiadas matemáticas :-) Solo para mostrar que algunas preguntas no son tan fáciles, demasiado abiertas para que la interpretación o el conocimiento previo sean correctas y eficientes. No uno que consideraría para entrevistar, ya que abre demasiado una lata de gusano.

Posible mejora en la posición inicial en la solución de Yacoby.

Ningún cargo legal tiene más de 16 piezas de cada color. El número de formas de colocar hasta 16 piezas negras y 16 blancas en 64 cuadrados es aproximadamente 3.63e27. Log2 (3,63e27) = 91,55. Esto significa que puede codificar la posición y el color de todas las piezas en 92 bits. Esto es menos que los 64 bits para la posición + hasta 32 bits para el color que requiere la solución de Yacoby. Puede guardar 4 bits en el peor de los casos a expensas de una complejidad considerable en la codificación.

Por otro lado, aumenta el tamaño para posiciones en las que faltan 5 o más piezas. Estas posiciones representan solo <4% de todas las posiciones, pero probablemente sean la mayoría de los casos en los que desea registrar una posición inicial diferente a la posición inicial.

Esto conduce a la solución completa

1. Codifique la posición y el color de las piezas de acuerdo con el método anterior. 92 bits .
2. Para especificar el tipo de cada pieza, use un Código Huffman: peón: '0', torre: '100', caballo: '101', alfil: '110', reina: '1110', rey: '1111'. Esto requiere (16 * 1 + 12 * 3 + 4 * 4) = 68 bits para un conjunto completo de piezas. La posición de la placa completa se puede codificar en 92 + 68 = 160 bits como máximo .
3. Se debe agregar un estado de juego adicional: turno: 1 bit, cuyo enroque es posible: 4 bits, posible “al paso”: hasta 4 bits (1 bit indica cuál es el caso y 3 bits indica cuál). La posición inicial está codificada en = 160 + 9 = 169 bits
4. Para la lista de movimientos, enumere todos los movimientos posibles para una posición determinada y almacene la posición del movimiento en la lista. La lista de movimientos incluye todos los casos especiales (enroque, al paso y renuncia). Utilice solo tantos bits como sea necesario para almacenar la posición más alta. En promedio, no debe exceder los 7 bits por movimiento (16 piezas posibles y 8 movimientos legales por pieza en promedio). En algunos casos, cuando se fuerza un movimiento, solo requiere 1 bit (mover o renunciar).

Hay 32 piezas en el tablero. Cada pieza tiene una posición (una en 64 cuadrados). Entonces solo necesitas 32 enteros positivos.

Sé que 64 posiciones se mantienen en 6 bits, pero no haría eso. Me quedaría con los últimos bits por algunas banderas (pieza caída, peón con reina)

La respuesta de cletus es buena, pero se olvidó de codificar también de quién es el turno. Es parte del estado actual y es necesario si está utilizando ese estado para impulsar un algoritmo de búsqueda (como un derivado alfa-beta).

No soy un jugador de ajedrez, pero creo que también hay un caso de esquina más: cuántos movimientos se han repetido. Una vez que cada jugador hace el mismo movimiento tres veces, el juego es un empate, ¿no? Si es así, necesitaría guardar esa información en el estado porque después de la tercera repetición, el estado ahora es terminal.

Como varios otros han mencionado, para cada una de las 32 piezas, podría almacenar en qué cuadrado están y si están en el tablero o no, esto da 32 * (log2 (64) + 1) = 224 bits.

Sin embargo, los alfiles solo pueden ocupar los cuadrados negros o blancos, por lo que para estos solo necesita log2 (32) bits para la posición, lo que da 28 * 7 + 4 * 6 = 220 bits.

Y dado que los peones no comienzan desde atrás y solo pueden avanzar, solo pueden estar en 56, debería ser posible usar esta limitación para reducir la cantidad de bits necesarios para los peones.

Un tablero tiene 64 cuadrados y se puede representar con 64 bits que muestran si un cuadrado está vacío o no. Solo necesitamos información de la pieza si un cuadrado tiene una pieza. Dado que el jugador + pieza toma 4 bits (como se mostró anteriormente) podemos obtener el estado actual en 64 + 4 * 32 = 192 bits. Agregue el turno actual y tiene 193 bits.

Sin embargo, también necesitamos codificar los movimientos legales para cada pieza. Primero, calculamos el número de movimientos legales para cada pieza y agregamos esa cantidad de bits después del identificador de pieza de un cuadrado completo. Calculé lo siguiente:

Peón: Adelante, primero gire dos hacia adelante, al paso * 2, promoción = 7 bits. Puede combinar el primer giro hacia adelante y la promoción en un solo bit, ya que no pueden ocurrir desde la misma posición, por lo que tiene 6. Torre: 7 cuadrados verticales, 7 cuadrados horizontales = 14 bits Caballero: 8 cuadrados = 8 bits Alfil: 2 diagonales * 7 = 14 bits Reina: 7 verticales, 7 horizontales, 7 diagonales, 7 diagonales = 28 bits Rey: 8 cuadrados circundantes

Esto aún significa que necesitaría mapear los cuadrados de destino en función de la posición actual, pero (debería ser) un cálculo simple.

Como tenemos 16 peones, 4 torres / caballos / alfiles y 2 reinas / reyes, esto es 16 * 6 + 4 * 14 + 4 * 8 + 4 * 14 + 2 * 28 + 2 * 8 = 312 bits más, lo que trae el total a 505 bits en total.

En cuanto a la cantidad de bits requeridos por pieza para posibles movimientos, se podrían agregar algunas optimizaciones y probablemente se reduciría la cantidad de bits, solo usé números fáciles para trabajar. Por ejemplo, para las piezas deslizantes, puede almacenar qué tan lejos pueden moverse, pero esto requeriría cálculos adicionales.

En pocas palabras: solo almacena datos adicionales (pieza, etc.) cuando una casilla está ocupada y solo almacena el número mínimo de bits de cada pieza para representar sus movimientos legales.

EDIT1: Olvidé el enroque y la promoción de peones a cualquier pieza. Esto podría llevar el total con posiciones explícitas a 557 movimientos (3 bits más para peones, 2 para reyes)

Cada pieza puede estar representada por 4 bits (peón a rey, 6 tipos), negro / blanco = 12 valores

Cada cuadrado del tablero se puede representar con 6 bits (coord x, coord y).

Las posiciones iniciales requieren un máximo de 320 bits (32 piezas, 4 + 6 bits)

Cada movimiento subsiguiente puede representarse con 16 bits (desde posición, hasta posición, pieza).

El enroque requeriría 16 bits adicionales, ya que es un movimiento dual.

Los peones retenidos podrían representarse por uno de los 4 valores de reserva de 4 bits.

Sin hacer los cálculos matemáticos en detalle, esto comienza a ahorrar espacio después del primer movimiento en comparación con el almacenamiento de 32 * 7 bits (matriz predefinida de piezas) o 64 * 4 bits (asignación predefinida de cuadrados)

Después de 10 movimientos en ambos lados, el espacio máximo requerido es de 640 bits

... pero, de nuevo, si identificamos cada pieza de forma única (5 bits) y agregamos un sexto bit para marcar peones rematados, entonces solo necesitamos ID de pieza + to-position para cada movimiento. Esto cambia el cálculo a ...

Posiciones iniciales = máximo 384 bits (32 piezas, 6 + 6 bits) Cada movimiento = 12 bits (a posición, id de pieza)

Luego, después de 10 movimientos en cada lado, el espacio máximo requerido es de 624 bits

Como Robert G, yo tendería a usar PGN ya que es estándar y puede ser usado por una amplia gama de herramientas.

Sin embargo, si estoy jugando una IA de ajedrez que está en una sonda espacial distante y, por lo tanto, todo es valioso, esto es lo que haría con los movimientos. Vendré a codificar el estado inicial más tarde.

Los movimientos no necesitan registrar el estado; el decodificador puede realizar un seguimiento del estado y de los movimientos que son legales en un momento dado. Todo lo que se necesita registrar es cuál de las diversas alternativas legales se elige. Dado que los jugadores se alternan, un movimiento no necesita registrar el color del reproductor. Dado que un jugador solo puede mover sus propias piezas de color, la primera opción es qué pieza mueve el jugador (volveré a una alternativa que usa otra opción más adelante). Con un máximo de 16 piezas, esto requiere un máximo de 4 bits. A medida que un jugador pierde piezas, el número de opciones disminuye. Además, un estado de juego particular puede limitar la elección de piezas. Si un rey no puede moverse sin ponerse en jaque, el número de opciones se reduce en uno. Si un rey está en jaque, cualquier pieza que no pueda sacarlo de jaque no es una opción viable.

Una vez concretada la pieza, solo tendrá un cierto número de destinos legales. El número exacto depende en gran medida del diseño del tablero y del historial del juego, pero podemos calcular ciertos valores máximos y esperados. Para todos menos el caballo y durante el enroque, una pieza no puede moverse a través de otra pieza. Esta será una gran fuente de límites de movimiento, pero es difícil de cuantificar. Una pieza no puede moverse fuera del tablero, lo que también limitará en gran medida el número de destinos.

Codificamos el destino de la mayoría de las piezas numerando los cuadrados a lo largo de las líneas en el siguiente orden: W, NW, N, NE (el lado negro es N). Una línea comienza en el cuadrado más alejado en la dirección dada a la que es legal moverse y avanza hacia. Para un rey sin trabas, la lista de movimientos es W, E, NW, SE, N, S, NE, SW. Para el caballo, comenzamos con 2W1N y seguimos en sentido horario; el destino 0 es el primer destino válido en este orden.

• Peones: un peón inmóvil tiene 2 opciones de destinos, por lo que requiere 1 bit. Si un peón puede capturar a otro, ya sea normalmente o al paso (lo que el decodificador puede determinar, ya que está realizando un seguimiento del estado), también tiene 2 o 3 opciones de movimientos. Aparte de eso, un peón solo puede tener 1 opción, sin necesidad de bits. Cuando un peón está en su ^séptima posición, también tomamos la opción de promoción. Dado que los peones generalmente se promueven a reinas, seguidos de caballos, codificamos las opciones como:
  • reina: 0
  • caballero: 10
  • obispo: 110
  • torre: 111
• Bishop: como máximo 13 destinos cuando está en {d, e} {4,5} para 4 bits.
• Torre: como máximo 14 destinos, 4 bits.
• Caballeros: como máximo 8 destinos, 3 bits.
• Reyes: cuando el enroque es una opción, el rey tiene que volver a S y no puede moverse hacia abajo; esto da un total de 7 destinos. El resto del tiempo, un rey tiene como máximo 8 movimientos, dando un máximo de 3 bits.
• Reina: Igual que las opciones para alfil o torre, para un total de 27 opciones, que son 5 bits.

Dado que la cantidad de opciones no siempre es una potencia de dos, lo anterior aún desperdicia bits. Suponga que el número de opciones es C y que la opción particular está numerada c , y n = ceil (lg ( C )) (el número de bits necesarios para codificar la elección). Hacemos uso de estos valores que de otro modo serían desperdiciados examinando el primer bit de la siguiente opción. Si es 0, no hagas nada. Si es 1 y c + C <2 ⁿ , entonces suma C a c . Decodificar un número invierte esto: si el c > = C recibido , reste C y establezca el primer bit para el siguiente número en 1. Si c<2ⁿ - C , luego establezca el primer bit para el siguiente número en 0. Si 2 ⁿ - C <= c < C , entonces no haga nada. Llame a este esquema "saturación".

Otro tipo potencial de elección que podría acortar la codificación es elegir una pieza del oponente para capturar. Esto aumenta el número de opciones para la primera parte de un movimiento, elegir una pieza, como máximo un bit adicional (el número exacto depende de cuántas piezas puede mover el jugador actual). A esta elección le sigue la opción de capturar la pieza, que probablemente sea mucho menor que el número de movimientos de cualquiera de las piezas del jugador. Una pieza solo puede ser atacada por una pieza desde cualquier dirección cardinal más los caballos para un total de 10 piezas atacantes como máximo; esto da un máximo total de 9 bits para un movimiento de captura, aunque esperaría 7 bits en promedio. Esto sería particularmente ventajoso para las capturas realizadas por la reina, ya que a menudo tendrá bastantes destinos legales.

Con la saturación, la codificación de captura probablemente no ofrece ninguna ventaja. Podríamos permitir ambas opciones, especificando en el estado inicial cuáles se utilizan. Si no se usa la saturación, la codificación del juego también podría usar números de elección no utilizados ( C <= c <2 ⁿ ) para cambiar las opciones durante el juego. Cada vez que C es una potencia de dos, no podemos cambiar las opciones.

Thomas tiene el enfoque correcto para codificar la placa. Sin embargo, esto debería combinarse con el enfoque de ralu para almacenar movimientos. Haga una lista de todos los movimientos posibles, escriba el número de bits necesarios para expresar este número. Dado que el decodificador está haciendo el mismo cálculo, sabe cuántos son posibles y puede saber cuántos bits leer, no se necesitan códigos de longitud.

Por lo tanto, obtenemos 164 bits para las piezas, 4 bits para la información de enroque (asumiendo que estamos almacenando un fragmento de un juego, de lo contrario se puede reconstruir), 3 bits para la información de elegibilidad al paso; simplemente almacene la columna donde ocurrió el movimiento ( Si de paso no es posible, almacene una columna donde no sea posible (tales columnas deben existir) y 1 para quién se moverá.

Los movimientos suelen tardar 5 o 6 bits, pero pueden variar de 1 a 8.

Un atajo adicional: si la codificación comienza con 12 1 bits (una situación no válida, ni siquiera un fragmento tendrá dos reyes en un lado), aborta la decodificación, borra el tablero y configura un nuevo juego. El siguiente bit será un poco de movimiento.

El algoritmo debería enumerar de forma determinista todos los destinos posibles en cada movimiento. Numero de destinos:

• 2 obispos, 13 destinos cada uno = 26
• 2 torres, 14 destinos cada una = 28
• 2 caballeros, 8 destinos cada uno = 16
• reina, 27 destinos
• rey, 8 destinos

8 patas podrían convertirse todas en reinas en el peor de los casos (enumeración), lo que hace que el mayor número de destinos posibles sea 9 * 27 + 26 + 28 + 16 + 8 = 321. Por lo tanto, todos los destinos de cualquier movimiento se pueden enumerar mediante un número de 9 bits.

El número máximo de movimientos de ambas partes es 100 (si no me equivoco, no soy un jugador de ajedrez). Por lo tanto, cualquier juego podría grabarse en 900 bits. Además de la posición inicial de cada pieza, se puede registrar utilizando números de 6 bits, que suman 32 * 6 = 192 bits. Más un bit para el registro de "quién se mueve primero". Por lo tanto, cualquier juego se puede grabar usando 900 + 192 + 1 = 1093 bits.

Almacenamiento del estado de la placa

La forma más sencilla en la que pensé es primero tener una matriz de 8 * 8 bits que represente la ubicación de cada pieza (por lo tanto, 1 si hay una pieza de ajedrez allí y 0 si no la hay). Como se trata de una longitud fija, no necesitamos ningún terminador.

A continuación, represente cada pieza de ajedrez en orden de ubicación. Usando 4 bits por pieza, esto toma 32 * 4 bits (128 en total). Lo que es realmente un desperdicio.

Usando un árbol binario, podemos representar un peón en un byte, un caballo y una torre y un alfil en 3 y un rey y una reina en 4. Como también necesitamos almacenar el color de la pieza, lo cual requiere un byte extra, termina como (perdóneme si esto está mal, nunca antes había visto la codificación de Huffman en detalle):

• Peón: 2
• Torre: 4
• Caballero: 4
• Obispo: 4
• Rey: 5
• Reina: 5

Dados los totales:

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

Que supera el uso de un conjunto de bits de tamaño fijo por 28 bits.

Entonces, el mejor método que he encontrado es almacenarlo en una matriz de 8 ² + 100 bits

8*8 + 100 = 164

Almacenamiento de movimientos
Lo primero que debemos saber es qué pieza se está moviendo hacia dónde. Dado que hay un máximo de 32 piezas en el tablero y sabemos qué es cada pieza, en lugar de un número entero que represente el cuadrado, podemos tener un número entero que represente el desplazamiento de la pieza, lo que significa que solo tenemos que ajustar 32 valores posibles para representar un trozo.

Desafortunadamente existen varias reglas especiales, como enrocar o derrocar al rey y formar una república (referencia de Terry Pratchett), por lo que antes de almacenar la pieza para mover necesitamos un solo bit que indique si es un movimiento especial o no.

Entonces, para cada movimiento normal, tenemos los 1 + 5 = 6bits necesarios . (Tipo 1 bit, 5 bits por pieza)

Una vez que se ha decodificado el número de pieza, conocemos el tipo de pieza y cada pieza debe representar su movimiento de la manera más eficiente. Por ejemplo (si mis reglas de ajedrez están a la altura) un peón tiene un total de 4 movimientos posibles (tomar a la izquierda, tomar a la derecha, avanzar uno, avanzar dos).
Entonces, para representar un movimiento de peón, necesitamos '6 + 2 = 8' bits. (6 bits para el encabezado de movimiento inicial, 2 bits para qué movimiento)

Moverse para la reina sería más complejo, ya que sería mejor tener una dirección (8 direcciones posibles, es decir, 3 bits) y un total de 8 cuadrados posibles para moverse en cada dirección (es decir, otros 3 bits). Entonces, para representar mover una reina, se necesitarían 6 + 3 + 3 = 12bits.

Lo último que se me ocurre es que tenemos que almacenar qué jugadores tiene el turno. Debe ser un solo bit (blanco o negro para pasar a continuación)

Formato resultante
Entonces el formato de archivo se vería así

[64 bits] Ubicación de las piezas iniciales
[100 bits máx.] Piezas iniciales [1 bit] Turno del jugador
[n bits] Movimientos

Donde un movimiento es
[1 bit] Tipo de movimiento (especial o normal)
[n bits] Detalle de movimiento

Si el movimiento es un movimiento normal, el detalle del movimiento se parece a
[5 bits] pieza
[n bits] movimiento de pieza específica (generalmente en el rango de 2 a 6 bits)

Si es un movimiento especial
, debe tener un tipo entero y luego cualquier información adicional (como si se tratara de un enroque). No puedo recordar la cantidad de movimientos especiales, por lo que puede estar bien indicar que es un movimiento especial (si solo hay uno)

En el caso base del tablero inicial más movimientos posteriores, considere lo siguiente.

Utilice un programa de ajedrez para asignar probabilidades a todos los movimientos posibles. Por ejemplo, 40% para e2-e4 20% para d2-d4 y así sucesivamente. Si algunos movimientos son legales pero ese programa no los considera, déles una probabilidad baja. Utilice la codificación aritmética para guardar qué opción se tomó, que será un número entre 0 y 0.4 para el primer movimiento, 0.4 y 0.6 para el segundo, y así sucesivamente.

Haz lo mismo con el otro lado. Por ejemplo, si hay un 50% de probabilidad de que e7-e5 sea la respuesta a e2-e4, entonces el número codificado estará entre 0 y 0,2. Repita hasta que termine el juego. El resultado es un rango potencialmente muy pequeño. Encuentre la fracción binaria con la base más pequeña que se ajuste a ese rango. Eso es codificación aritmética.

Esto es mejor que Huffman porque se puede considerar como una codificación de bits fraccionarios (más algo al final del juego para redondear a un bit completo).

El resultado debería ser más compacto que el de Huffman, y no hay casos especiales de promoción, al paso, el movimiento de las 50 reglas y otros detalles porque son manejados por el programa de evaluación de ajedrez.

Para volver a jugar, use nuevamente el programa de ajedrez para evaluar el tablero y asignar todas las probabilidades a cada movimiento. Utilice el valor codificado aritméticamente para determinar qué movimiento se jugó realmente. Repita hasta que esté listo.

Si su programa de ajedrez es lo suficientemente bueno, puede obtener una mejor compresión con un codificador de dos estados, donde las probabilidades se definen en función de los movimientos tanto para blanco como para negro. En el caso más extremo de más de 200 estados, esto codifica el conjunto completo de todos los juegos de ajedrez posibles y, por lo tanto, no es factible.

Esta es una forma bastante diferente de decir lo que Darius ya escribió, solo con un poco de ejemplo de cómo podría funcionar la codificación aritmética y un ejemplo real de cómo usar un programa de ajedrez existente para ayudar a evaluar la probabilidad de los siguientes movimientos.