▷Rompecabezas del programador: codificación de un estado de tablero de ajedrez a lo largo de un juego ✔️ Foro Ayuda 【 2024 】

Solución:

Actualizar: Me gustó tanto este tema que escribí Rompecabezas de programación, Posiciones de ajedrez y Codificación Huffman. Si lee esto, he determinado que el solamente La forma de almacenar un estado completo del juego es almacenar 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 8×8 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:

e4 e5
Cf3 Cc6
…

que se traduce en:

Las blancas mueven el peón de rey de e2 a e4 (es la única pieza que puede llegar a e4, por lo tanto, “e4”);
Las negras mueven el peón del rey de e7 a e5;
Las blancas mueven el caballo (N) a f3;
Las negras mueven el caballo a c6.
…

El tablero se ve así:

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

Entonces, ¿qué falta o qué 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 acerca de conocer los movimientos hasta este punto. Eso es en realidad un problema, como explicaré.

Enroque

El juego ha procedido de la siguiente manera:

e4 e5
Cf3 Cc6
Bb5 a6
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 pueden haber 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 hacer frente a 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.

de paso

El juego ha progresado.

e4 e5
Cf3 Cc6
Bb5 a6
Aa4 Ac5
OO b5
Bb3 b4
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 sucede en la primera oportunidad, lo que significa que si las negras pasan la opción ahora, no pueden realizar el siguiente movimiento. Entonces necesitamos 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, puede ascender a cualquier otra pieza (pero no al rey). El 99% de las veces se asciende a Reina, pero a veces no lo es, por lo general porque eso puede forzar un punto muerto cuando, de lo contrario, ganarías. Esto está escrito como:

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 se ascienden los 8 peones.

Estancamiento

Cuando esté en una posición desde 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 por qué 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 hay 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 de la placa 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ápido. 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 a 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 tan eficientemente 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 significativamente aumento de los costos de manipulación.

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^dieciséis x 13⁴⁸ = 1.35e70 (aproximadamente), requiriendo 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 tiene la misma probabilidad.

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) son dos guiones y dos pitidos.

Tal esquema puede reducir significativamente el tamaño de un esperado mensaje, 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 tienen hasta 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 necesitemos reproducir exactamente.

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 es inequívoco.

Ésta 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 inequívoca.

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 static datos:

private final static List COLOURS;
private final static Map WEIGHTS;

static 
  List list = new ArrayList();
  list.add("White");
  list.add("Black");
  COLOURS = Collections.unmodifiableList(list);
  Map map = new HashMap();
  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);

private static class WeightComparator implements Comparator 
  @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 
  @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 queue = new PriorityQueue(WEIGHTS.size(),
      new WeightComparator());
  for (Map.Entry 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 nodes = new TreeMap(new PathComparator());
  addLeaves(nodes, queue.peek(), "");
  for (Map.Entry entry : nodes.entrySet()) 
    System.out.printf("%s %s%n", entry.getKey(), entry.getValue().getLabel());
  


public static void addLeaves(Map 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 es más probable que la mayoría de los tableros de ajedrez esperados (en lugar de los generados aleatoriamente) se parezcan, al menos en parte, 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 posiciones de final de juego 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 el mismo cuadro. 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 los cuadrados que están ocupados 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 mejores 4 y luego codificar un selector de esquema en los primeros dos 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 preferible a 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 tienes que determinar es ¿estás simplemente almacenando una lista de movimientos o estás anotando el juego? Las partidas de ajedrez suelen estar anotadas, por ejemplo:

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, es posible que también deba 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 del movimiento 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 inicial (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 si adoptamos 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 Codificación de Huffman. En realidad, la frecuencia inicial de piezas en el tablero es casi perfecta para esto: la mitad de las casillas están vacías, la mitad de las casillas 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 c representa 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 / caballos / alfiles: 12 * 5 bits = 60 bits
reinas / reyes: 4 * 6 bits = 24 bits

Total: 164 bits Para el inicial estado del tablero. 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. Tal vez otros 16 bits como máximo, así que 180 bits para todo el estado del juego. Posibles optimizaciones:

Dejando de lado 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, uno negro” introduciendo símbolos adicionales que no tienen la c bit, que luego se puede 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 ellos, y si se equivoca, será más doloroso que útil.

Te mostramos las comentarios y valoraciones de los usuarios

¡Haz clic para puntuar esta entrada!

(Votos: 0 Promedio: 0)

Rompecabezas del programador: codificación de un estado de tablero de ajedrez a lo largo de un juego