programa para mejor aprender app ajedrez algorithm language-agnostic puzzle chess

algorithm - programa - mejor app para aprender ajedrez



Programador Puzzle: codificación de un estado de tablero de ajedrez a través de un juego (30)

El enfoque de la tabla de búsqueda realmente grande

Posición - 18 bytes
El número estimado de posiciones legales es 10 43
Simplemente enumere todos y la posición se puede almacenar en solo 143 bits. Se requiere 1 bit más para indicar qué lado tocará 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 puede codificarse en un byte.

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

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

Con los años, he estado involucrado en algunas entrevistas técnicas de nuevos empleados. Además de hacer las preguntas estándar de "¿conoces la tecnología X?", También he tratado de tener una idea de cómo abordan los problemas. Por lo general, les enviaba la pregunta por correo electrónico el día anterior a la entrevista y esperaba que presentaran una solución al día siguiente.

A menudo, los resultados serían bastante interesantes, incorrectos, pero interesantes, y la persona seguiría recibiendo mi recomendación si pudieran explicar por qué adoptaron un enfoque 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 de espacio que se puede usar para codificar el estado de un juego de ajedrez (o un subconjunto del mismo)? Es decir, dado un tablero de ajedrez con las piezas dispuestas legalmente, codifique tanto este estado inicial como todos los movimientos legales subsecuentes tomados 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 dar cuenta de eso también como un extra opcional :)

EDIT2: Solo para una aclaración adicional ... Recuerde, el codificador / decodificador es consciente de las reglas. Las únicas cosas que realmente se deben almacenar son las elecciones del jugador; se puede suponer que el codificador / decodificador sabe cualquier otra cosa.

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

Agregaría interés para optimizar el tamaño promedio de los casos para los juegos típicos que juegan los 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 movimiento, haz que un buen motor de ajedrez genere movimientos desde cada posición; producirá una lista de k posibles movimientos, ordenados por su clasificación de su calidad. En general, las personas eligen buenos movimientos con más frecuencia que los movimientos aleatorios, por lo que debemos aprender un mapeo de cada posición en la lista a la probabilidad de que las personas escojan un movimiento que sea ''bueno''. Usando estas probabilidades (basado en un corpus de juegos de alguna base de datos de ajedrez en internet), codifica los movimientos con codificación aritmética . (El decodificador debe usar el mismo motor de ajedrez y el mapeo).

Para la posición de partida, el enfoque de ralu funcionaría. Podríamos refinarlo con codificación aritmética allí, si tuviéramos alguna manera de ponderar las elecciones por probabilidad, por ejemplo, las piezas suelen aparecer 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: recurrir a la codificación de movimiento anterior en su lugar, comenzando desde la posición de apertura estándar y encontrar una secuencia que finaliza en la placa deseada. (Puede intentar A * buscar con una distancia heurística que iguale la suma de las distancias de las piezas desde sus posiciones finales, o algo similar). Esto cambia cierta ineficiencia al sobreespecificar la secuencia de movimiento vs. eficiencia de aprovechar el juego de ajedrez. conocimiento. (Puede reducir parte de la ineficiencia al eliminar las opciones de movimiento que conducirían a una posición previamente explorada en la búsqueda A *: pueden obtener un peso 0 en el código aritmético).

También es difícil calcular cuánto ahorro le compraría en la complejidad de un caso promedio, sin reunir algunas estadísticas de un corpus real. Pero creo que el punto de partida con todos los movimientos igualmente probables 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.

Anoche vi esta pregunta 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.

Solución básica

Asumiendo un juego de ajedrez estándar y no codificando las reglas (como Blanco siempre va primero), entonces puedes 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, así que solo hay 16 plazas de las que preocuparte, que son 4 bits para los que la pieza se mueve en 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)
  • Obispo: 13 opciones, 4 bits (si tienes 7 en una diagonal, solo tienes 6 en la otra)
  • Knight: 8 opciones, 3 bits
  • Queen: 27 opciones, 5 bits (Rook + Bishop)
  • King: 9 opciones, 4 bits (8 movimientos de un solo paso, más la opción de enroque)

Para la promoción, hay 4 piezas para elegir (Torre, Obispo, Caballero, Reina), así que en ese movimiento agregaríamos 2 bits para especificar eso. Creo que todas las otras reglas se cubren automáticamente (por ejemplo, en passant).

Otras optimizaciones

En primer lugar, después de capturar 8 piezas de un color, puede reducir la codificación de la pieza a 3 bits, luego 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} para 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 (de seguir todos los movimientos), así que después de leer qué pieza se moverá, siempre podemos determinar cuántos bits necesitamos para leer. Si nos damos cuenta de que los únicos movimientos de un peón en este punto son capturar diagonalmente a la derecha o avanzar uno, sabemos que solo lee 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.

Atacando un subproblema de codificación de los pasos después de que una posición inicial ha sido codificada. El enfoque es crear una "lista vinculada" de pasos.

Cada paso del juego está codificado como el "par de posición anterior -> nueva posición". Conoces la posición inicial al comienzo del juego de ajedrez; al atravesar la lista de pasos enlazados, puede acceder al estado después de que X se mueve.

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 la codificación de un juego determinado tomaría es proporcional al número de movimientos:

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

ACTUALIZACIÓN: complicación potencial con peones promovidos. Necesita poder indicar en qué se promociona el peón, puede necesitar bits especiales (usaría un código gris para ahorrar espacio, ya que la promoción del 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 está moviendo puede moverse a no más de X lugares. Por ejemplo, un peón puede tener un máximo de 3 opciones de movimiento en cualquier punto dado. Al darnos cuenta de la cantidad máxima de movimientos para cada tipo de pieza, podemos guardar 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 negro o blanco se convierte

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

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

el próximo 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 tienes 30-40 movimientos posibles. El ensamblaje de almacenamiento solo está generando n en orden inverso.

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

EDITAR:

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

En cada movimiento agregamos información de tamaño

num_of_moves = get_number_of_possible_moves(postion) ;

en el grupo y este número no puede ser reducido

generar 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, guarde como número de movimientos forzados previamente realizados. Ejemplo: si la posición inicial tiene 1 movimiento forzado para cada lado (2 movimientos) y queremos guardar esto como un juego de movimiento, almacene 1 en el grupo n.

ejemplo de almacenamiento en el grupo de información

Supongamos que tenemos posiciones iniciales conocidas 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 3er movimiento hay 7 movimientos disponibles para ese lado y elige elegir el índice de movimiento 2.

Forma de vector; í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 se necesita multiplicar por 7)

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

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 descubrimos que hay 6 movimientos posibles.

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

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

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

Últimamente movemos el índice 2 y alcanzamos 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 multiplique aumenta, pero no debería haber problemas para almacenar juegos de hasta 10.000 movimientos.

posición de ahorro

Se puede hacer cerca de lo óptimo.

Cuando descubramos información y almacenemos información, permítanme hablar más al respecto. La idea general es disminuir la redundancia (hablaré de eso más adelante). Vamos a suponer que no hubo promociones y no tomar, por lo que hay 8 peones, 2 torres, 2 caballeros, 2 obispos, 1 rey y 1 reina por lado.

Qué tenemos que guardar: 1. posición de cada paz 2. posibilidades de enroque 3. posibilidades de en-passant 4. lado que tiene movimiento disponible

Supongamos que cada pieza puede colocarse en cualquier lugar pero no en 2 piezas en el mismo lugar. El número de 8 peones del mismo color que se pueden organizar a bordo es C (64/8) (binomial) 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 .

Al multiplicar esto para ambos sitios obtenemos el número 4634726695587809641192045982323285670400000 que tiene 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 las limitaciones de enroque y un bit para el sitio que tiene movimiento. Terminamos con 142 + 3 + 4 + 1 = 150bits

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

  1. ambos peones en blanco y negro 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 6 ° rango. Esto nos trae 8 * C (6/2) en lugar de C (64/8) * C (48/8) que disminuyen 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 podemos agregar 4 cuadrados a bordo para obtener la información adicional si se enroca con esta torre es posible 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 los 4 bits)

  3. en-passant: cuando almacenamos una de las 8 posibilidades de paso, conocemos la posición de peón negro y reducimos la redindancia informativa (si es un movimiento blanco y tiene un 3er empeño de peón que significa que el peón negro está en c5 y el peón blanco es c2, c3 o c4) por lo tanto insensible a C (6/2) tenemos 3 y hemos perdido 2.3 bits. Disminuimos la redundancia si almacenamos un número de en-passant que también se puede hacer (3 posibilidades-> izquierda, derecha, ambas) y conocemos la posibilidad de un peón que puede pasar de largo. (por ejemplo, desde el ejemplo previo en blanco con negro en c5, que puede estar en la izquierda, derecha o ambas). Si está en un sitio, tenemos 2 * 3 (3 para almacenar psissibilites y 2 movimientos posibles para peón negro en 7 o 6 ) en C (6/2) y reducimos en 1.3 bits y si en ambos lados reducimos en 4.2 bits. De esa manera podemos reducir en 2.3 + 1.3 = 3.6 bits por en passant.

  4. obispos: los bisop pueden estar en cuadrados de opostita solamente, esto reduce la redundancia en 1 bit para cada sitio.

Si sumamos, necesitamos 150-56-4-3.6-2 = 85bits para almacenar la posición de ajedrez si no hubiera tomas

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

Gran rompecabezas!

Veo que la mayoría de la gente está almacenando la posición de cada pieza. ¿Qué tal si tomamos un enfoque más simple y almacenamos el contenido de cada cuadrado ? Eso se ocupa de la promoción y de las piezas capturadas automáticamente.

Y permite la codificación de 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.

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

  • 0 para cuadrados vacíos
  • 1c0 por peón
  • 1c100 para torre
  • 1c101 para caballero
  • 1c110 para el alfil
  • 1c1110 para la 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
  • grajos / caballeros / obispos: 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 actualmente más votados. Y solo se irá reduciendo a medida que el juego progrese (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, en paso, repetición de movimientos, etc.) tendrá que codificarse por separado. Tal vez otros 16 bits como máximo, por lo que 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 rey y reina por un cuadrado vacío guarda 5 bits, que son exactamente los 5 bits que necesita para codificar su posición de otra manera.
  • "Sin peones en la última fila" podría codificarse fácilmente utilizando una tabla Huffman diferente para las últimas filas, pero dudo que ayude mucho. Probablemente aún termines con el mismo árbol de Huffman.
  • "Un blanco, un alfil negro" se puede codificar introduciendo símbolos adicionales que no tienen el bit c , que luego se pueden deducir del cuadrado en el que se encuentra el alfil. (Los peones promovidos a obispos interrumpen este esquema ...)
  • Las repeticiones de casillas vacías podrían codificarse por longitud de recorrido introduciendo símbolos adicionales para, por ejemplo, "2 casillas vacías en una fila" y "4 casillas vacías en una fila". Pero no es tan fácil estimar la frecuencia de esos, y si lo haces mal, va a doler en lugar de ayudar.

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 codificación de bits.

Bits por pieza:

  • Piece-ID: 4 bits máximos para identificar las 16 piezas por lado. Blanco / negro se puede inferir. Tener un pedido definido en las piezas. A medida que el número de piezas cae por debajo de las potencias respectivas de dos, usa menos bits para describir las piezas restantes.
  • Peón: 3 posibilidades en el primer movimiento, por lo que +2 bits (adelante por uno o dos cuadrados, en paso). 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 al observar cuándo el peón ha alcanzado el último rango. Si se sabe que el peón se promueve, el decodificador esperará otros 2 bits que indiquen a cuál de las 4 piezas principales se ha promocionado.
  • Obispo: +1 bit para la diagonal utilizada, hasta +4 bits para la distancia a lo largo de la diagonal (16 posibilidades). El decodificador puede deducir la máxima distancia posible que la pieza puede moverse a lo largo de esa diagonal, por lo que si es una diagonal más corta, utilice menos bits.
  • Caballero: 8 movimientos posibles, +3 bits
  • Torre: +1 bit para horizontal / vertical, +4 bits para la 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 el primer rango, codifique este movimiento con una instrucción para mover al rey "hacia atrás", es decir, fuera del tablero.
  • Queen: 8 possible directions, +3bits. Up to +4 more bits for distance along the line / diagonal (less if the diagonal is shorter, as in the bishop''s case)

Assuming all pieces are on the board, these are the bits per move: Pawn - 6 bits on first move, 5 subsequently. 7 if promoted. Bishop: 9 bits (max), Knight: 7, Rook: 9, King: 7, Queen: 11 (max).

Lo mejor es almacenar los juegos de ajedrez en un formato estándar legible para humanos.

La Notación de juegos portátiles asume una posición de inicio estándar (aunque no es necesario ) y simplemente enumera los movimientos, giro por turno. Un formato estándar, compacto y legible para 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 quieres hacerlo más pequeño, simplemente asegúralo . ¡Trabajo hecho!

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

El problema

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

comenzando la posición de ajedrez http://img222.imageshack.us/img222/5970/chess.png

Las posiciones generalmente se registran como una letra para la columna seguida por el número de la fila, por lo que la reina 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. Considera esta apertura:

  1. e4 e5
  2. Nf3 Nc6
  3. ...

que se traduce a:

  1. El blanco mueve el peón del rey de e2 a e4 (es la única pieza que puede llegar a e4, por lo tanto, "e4");
  2. El negro mueve el peón del rey de e7 a e5;
  3. Blanco mueve el caballero (N) a f3;
  4. Negro mueve el caballo a c6.
  5. ...

El tablero se ve así:

apertura anticipada http://img222.imageshack.us/img222/371/chessx.png

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

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

Estado del tablero vs 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 lo explicaré.

Enroque

El juego ha procedido de la siguiente manera:

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

El tablero se ve de la siguiente manera:

Blanco tiene la opción de castling . Parte de los requisitos para esto es que el rey y la torre correspondiente nunca se hayan movido, por lo que será necesario almacenar el rey o cualquier torre de cada lado. Obviamente, si no están en sus posiciones iniciales, se han movido, de lo contrario, debe especificarse.

Existen varias estrategias que se pueden usar para enfrentar 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 bit para uno de estos seis cuadrados si la pieza correcta pasa a estar en él. Alternativamente, podríamos tratar cada pieza no movida como otro tipo de pieza, así que en lugar de 6 tipos de piezas en cada lado (peón, torre, caballero, alfil, reina y rey) hay 8 (sumando torre no movida y rey ​​no movido).

De paso

Otra regla peculiar y a menudo descuidada en Chess es En Passant .

en passant http://img37.imageshack.us/img37/6535/chessa.png

El juego ha progresado.

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

El peón negro en b4 ahora tiene la opción de mover su peón de b4 a c3 tomando el peón blanco en c4. Esto solo ocurre en la primera oportunidad, lo que significa que si Black pasa la opción ahora no puede realizar el movimiento siguiente. 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 4 ° rango acaba de moverse hacia allí con un doble movimiento hacia adelante. O podemos ver cada posible posición de En Passant en el tablero y tener una bandera para indicar si es posible o no.

Promoción

promoción de peones http://img689.imageshack.us/img689/5970/chess.png

Es el movimiento de White. Si las blancas mueven su peón de h7 a h8, pueden promocionarse a cualquier otra pieza (pero no al rey). El 99% del tiempo es promovido a una reina pero a veces no lo es, generalmente porque eso puede forzar un punto muerto cuando de otro modo ganarías. Esto está escrito como:

  1. 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 totalmente posible (pero increíblemente improbable) que un lado termine con 9 reinas, 10 coronas, 10 obispos o 10 caballeros si se promueven los 8 peones.

Estancamiento

Cuando estás en una posición desde la que no puedes ganar tu mejor táctica es intentar un stalemate . La variante más probable es donde no se puede hacer un movimiento legal (por lo general, debido a cualquier movimiento al poner a tu rey bajo control). En este caso, puede reclamar un sorteo. Este es fácil de atender.

La segunda variante es por en.wikipedia.org/wiki/Threefold_repetition . Si la misma posición del tablero ocurre tres veces en un juego (o ocurrirá una tercera vez en el próximo movimiento), se puede reclamar un sorteo. Las posiciones no necesitan ocurrir en ningún orden en particular (lo que significa que no tiene que repetirse la misma secuencia de movimientos tres veces). Esto complica enormemente el problema porque tienes que recordar cada posición anterior de la tabla. Si esto 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 un empate 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 tendríamos que almacenar cuántos movimientos se movieron desde un peón o una pieza tomada (el último de los dos. 6 bits (0-63).

¿De quién es el turno?

Por supuesto, también necesitamos saber de quién es el turno y esta es una información única.

Dos problemas

Debido al caso de punto muerto, la única manera factible o sensata de almacenar el estado del juego es almacenar todos los movimientos que condujeron a esta posición. Abordaré ese único problema. El problema del estado del tablero se simplificará a esto: almacene la posición actual de todas las piezas en el tablero ignorando las condiciones de enroque, en pasante, punto muerto y a quién le toca el turno .

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

Contenido simple

Hay seis tipos de piezas (peón, torre, caballero, alfil, reina y rey). Cada pieza puede ser blanca o negra, por lo que un cuadrado puede contener una de las 12 posibles piezas o puede estar vacía, por lo que hay 13 posibilidades. 13 se pueden almacenar en 4 bits (0-15) Así que 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 podría incluso ampliarse agregando 3 posibilidades más sin aumentar los requisitos de almacenamiento: un peón que se ha movido 2 espacios en el último giro, un rey que no se ha movido y una torre que no se ha movido, que servirá para muchos de los problemas mencionados anteriormente.

Pero lo podemos hacer mejor.

Codificación de 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 ciencias de la computación. Por ejemplo, el problema de detención trata a un programa de computadora (correctamente) como un gran número.

La primera solución trata la posición como un número base 64 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 número de espacio a 64 dígitos base 13. Por supuesto, esto no se puede hacer tan eficientemente como base 16, pero ahorrará en requisitos de almacenamiento (y nuestro objetivo es minimizar el espacio de almacenamiento).

En la base 10, el número 234 es equivalente a 2 x 10 2 + 3 x 10 1 + 4 x 10 0 .

En la base 16, el número 0xA50 es equivalente a 10 x 16 2 + 5 x 16 1 + 0 x 16 0 = 2640 (decimal).

Entonces podemos codificar nuestra posición como p 0 x 13 63 + p 1 x 13 62 + ... + p 63 x 13 0 donde p i representa el contenido del cuadrado i .

2 256 es igual a aproximadamente 1.16e77. 13 64 es igual a aproximadamente 1.96e71, lo que requiere 237 bits de espacio de almacenamiento. Ese ahorro de solo 7.5% tiene un costo de costos de manipulación significativamente mayores.

Codificación de base variable

En las juntas legales, ciertas piezas no pueden aparecer en ciertas casillas. Por ejemplo, los peones no pueden ocurrir en el primer u octavo rango, reduciendo las posibilidades para esos cuadrados a 11. Eso reduce los posibles tableros a 11 16 x 13 48 = 1.35e70 (aproximadamente), que requieren 233 bits de espacio de almacenamiento.

En realidad, la codificación y decodificación de dichos valores desde y hacia el decimal (o binario) es un poco más complicada, 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 "personaje" tiene el mismo ancho pero la eficiencia se puede mejorar si se considera que cada personaje no es igualmente probable.

Considere el código Morse (foto arriba). Los caracteres en un mensaje están codificados como una secuencia de guiones y puntos. Esos puntos y rayas se transfieren a través de la 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 punto único, 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 aleatorios.

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 con esto en mente para minimizar el uso de guiones. Dado que 1s y 0s (nuestros componentes básicos) no tienen este problema, no es una función que necesitemos replicar.

Por último, hay dos tipos de silencios en el código Morse. Un breve descanso (la longitud de un punto) se usa para distinguir puntos y rayas. Un espacio más largo (la longitud de un guión) se usa para delimitar 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 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 se codifica 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 hacer una sustitución ambigua (p. Ej., 4 puntos pueden ser H o ​​2 Es), pero solo tenemos 1s y 0s, 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 del 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 al azar) tienen más probabilidades que no de parecerse, 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 inicial de 256 bits y luego codificar eso (usando la codificación Huffman o, por ejemplo, algún método de codificación de longitud de ejecución ). Obviamente, esto será muy eficiente para comenzar (64 0s probablemente corresponden a 64 bits) pero se requiere un aumento en el almacenamiento 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 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 otras piezas. 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 abajo);
  • Número de no-empeños: 4 bits (0-15);
  • Para cada pieza: tipo (2 bits para reina, torre, caballero, alfil) y ubicación (6 bits)

En cuanto a la ubicación del peón, 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 8 posibilidades, que equivalen a 28,179,280,429,056. Necesitas 45 bits para codificar esos muchos valores.

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

Debe señalarse que hay menos de 48 8 posibilidades porque los peones no pueden estar todos en el mismo cuadrado. 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 no peones blancos, luego los 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 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 guardar un juego en lugar de una posición . Debido a la repetición triple tenemos que almacenar la lista de movimientos que han ocurrido hasta este punto.

Anotaciones

Una cosa que debes determinar es si simplemente guardas una lista de movimientos o anotas el juego. Los juegos de ajedrez a menudo son anotados, por ejemplo:

  1. Bb5 !! Nc4?

El movimiento de White está marcado por dos signos de exclamación como brillantes, mientras que Black es visto 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.

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

Notación Algebraica

Simplemente podríamos almacenar el texto del movimiento aquí ("e4", "Bxb5", etc.). Incluyendo un byte de terminación que está viendo alrededor de 6 bytes (48 bits) por movimiento (el peor caso). 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 sean 12 bits por movimiento. Eso es significativamente mejor.

Alternativamente, podemos determinar todos los movimientos legales de 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 para esta pregunta. Hay muchos enfoques posibles de los cuales los anteriores son solo algunos.

Lo que me gusta de esto y de 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 .

Possible improvement on the starting position in Yacoby''s solution

No legal position has more than 16 pieces of each color. The number of ways to place up to 16 black and 16 white pieces on 64 squares is about 3.63e27. Log2(3.63e27)=91.55. This means you can encode the position and color of all pieces in 92 bits. This is less than the 64 bits for position + up to 32 bits for color that Yacoby''s solution requires. You can save 4 bits in the worst case at the expense of considerable complexity in the encoding.

On the other hand, it increases the size for positions with 5 or more pieces missing. These positions represent only <4% of all positions, but they are probably a majority of the cases where you want to record a starting position different than the inital position.

This leads to the complete solution

  1. Encode the position and color of pieces according to the method above. 92 bits .
  2. To specify the type of each piece, use a Huffman Code: pawn: ''0'', rook: ''100'', knight: ''101'', bishop: ''110'', queen: ''1110'', king: ''1111''. This requires (16*1 + 12*3 + 4*4) = 68 bits for a full set of pieces. The full board position can be encoded in 92 + 68 = 160 bits maximum .
  3. Additional game state shoud be added: turn: 1 bit, which castling is possible: 4 bits, “en passant” possible: up to 4 bits (1 bit tells it is the case and 3 bits tell which one). The starting position is encoded in = 160 + 9 = 169 bits
  4. For the list of moves, enumerate all possible moves for a given position and store the position of the move in the list. The list of moves includes all special cases (castling, en passant, and resigning). Use only as many bits as necessary to store the highest position. On average it shouldn''t exceed 7 bits per move (16 possible pieces and 8 legal moves per piece on average). In some case, when a move is forced, it requires only 1 bit (move or resign).

Storing the board state

The simplest way I thought of is too first have a array of 8*8 bits representing the location of each piece (So 1 if there is a chess piece there and 0 if there isn''t). As this is a fixed length we don''t need any terminator.

Next represent every chess piece in order of its location. Using 4 bits per piece, this takes 32*4 bits (128 in total). Which is really really wasteful.

Using a binary tree, we can represent a pawn in one byte, a knight and rook and bishop in 3 and a king and queen in 4. As we also need to store the color of the piece, which takes an extra byte it ends up as (forgive me if this is wrong, I have never looked at Huffman coding in any detail before):

  • Pawn : 2
  • Rook: 4
  • Knight: 4
  • Bishop: 4
  • King: 5
  • Queen: 5

Given the totals:

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

Which beats using a fixed size set of bits by 28 bits.

So the best method I have found is to store it in a 8 2 + 100 bit array

8*8 + 100 = 164



Storing Moves
The first thing we need to know with is which piece is moving to where. Given that there are at maximum 32 pieces on the board and we know what each piece is, rather than an integer representing the square, we can have an integer representing the piece offset, which means we only have to fit 32 possible values to represent a piece.

Unfortunately there are various special rules, like castling or overthrowing the king and forming a republic (Terry Pratchett reference), so before we store the piece to move we need a single bit indicating if it is a special move or not.

So for each normal move we have a necessary 1 + 5 = 6 bits. (1 bit type, 5 bits for the piece)

After the piece number has been decoded, we then know the type of piece, and each piece should represent its move in the most efficient way. For example (If my chess rules are up to scratch) a pawn has a total of 4 possible moves (take left, take right, move one forward, move two forward).
So to represent a pawn move we need ''6 + 2 = 8'' bits. (6 bit for initial move header, 2 bits for what move)

Moving for the queen would be more complex, in that it would be best to have a direction (8 possible directions, so 3 bits) and a total of 8 possible squares to move to for each direction (so another 3 bits). So to represent moving a queen it would require 6 + 3 + 3 = 12 bits.

The last thing that occurrences to me is that we need to store which players turn it is. This should be a single bit (White or black to move next)



Resultant Format
So the file format would look something like this

[64 bits] Initial piece locations
[100 bits max] Initial pieces [1 bit] Player turn
[n bits] Moves

Where a Move is
[1 bit] Move type (special or normal)
[n bits] Move Detail

If the Move is a normal move, the Move Detail looks something like
[5 bits] piece
[n bits] specific piece move (usually in the range of 2 to 6 bits]

If it is a special move
It should have an integer type and then any additional information (like if it is castling). I cannot remember the number of special moves, so it may be OK just to indicate that it is a special move (if there is only one)

cletus '' answer is good, but he forgot to also encode whose turn it is. It is part of the current state, and is necessary if you''re using that state to drive a search algorithm (like an alpha-beta derivative).

I''m not a chess player, but I believe there''s also one more corner case: how many moves have been repeated. Once each player makes the same move three times, the game is a draw, no? If so, then you''d need to save that information in the state because after the third repeat, the state is now terminal.

A board has 64 squares, and can be represented by 64 bits showing if a square is empty or not. We only need piece information if a square has a piece. Since the player + piece takes 4 bits (as shown earlier) we can get the current state in 64 + 4 * 32 = 192 bits. Throw in the current turn and you have 193 bits.

However, we also need to encode the legal moves for each piece. First, we calculate the number of legal moves for each piece, and append that many bits after the piece identifier of a full square. I calculated as follows:

Pawn: Forward, first turn two forward, en passant * 2, promotion = 7 bits. You can combine the first turn forward and promotion into a single bit since they cannot happen from the same position, so you have 6. Rook: 7 vertical squares, 7 horizontal squares = 14 bits Knight: 8 squares = 8 bits Bishop: 2 diagonals * 7 = 14 bits Queen: 7 vertical, 7 horizontal, 7 diagonal, 7 diagonal = 28 bits King: 8 surrounding squares

This still means you would need to map the targeted squares based on the current position, but it (should be) a simple calculation.

Since we have 16 pawns, 4 rooks/knights/bishops, and 2 queens/kings, this is 16 * 6 + 4 * 14 + 4 * 8 + 4 * 14 + 2 * 28 + 2 * 8 = 312 more bits, bringing the total to 505 bits overall.

As for the number of bits required per piece for possible moves, some optimisations could be added to that and the number of bits probably reduced, I just used easy numbers to work with. For example, for sliding pieces you could store how far away they could move, but this would require extra calculations.

Long story short: Only store extra data (piece, etc) when a square is occupied, and only store the minimum number of bits for each piece to represent its legal moves.

EDIT1: Forgot about castling and pawn promotion to any piece. This could bring the total with explicit positions to 557 moves (3 more bits for pawns, 2 for kings)

Algorithm should deterministically enumerate all possible destinations at each move. Number of destinations:

  • 2 bishops, 13 destinations each = 26
  • 2 rooks, 14 destinations each = 28
  • 2 knights, 8 destinations each = 16
  • queen, 27 destinations
  • king , 8 destinations

8 paws could all become queens in worst (enumeration-wise) case, thus making largest number of possible destinations 9*27+26+28+16+8=321. Thus, all destinations for any move can be enumerated by a 9 bit number.

Maximum number of moves of both parties is 100 (if i''m not wrong, not a chess player). Thus any game could be recorded in 900 bits. Plus initial position each piece can be recorded using 6 bit numbers, which totals to 32*6 =192 bits. Plus one bit for "who moves first" record. Thus, any game can be recorded using 900+192+1=1093 bits.

As several others have mentioned you could for each of the 32 pieces you could store which square they''re on and if they''re on the board or not, this gives 32 * (log2(64) + 1) = 224 bits.

However the bishops can only occupy either the black or white squares so for these you only need log2(32) bits for the position, which give 28 * 7 + 4 * 6 = 220 bits.

And since the pawns don''t start at the back and can only move forward, they can only be on 56, it should be possible to use this limitation to reduce the number of bits needed for the pawns.

Each piece can be represented by 4 bits (pawn to king, 6 types), black/white = 12 values

Each square on the board can be represented by 6 bits (x coord, y coord).

Initial positions require maximum of 320 bits (32 pieces, 4 + 6 bits)

Each subsequent move can be represented by 16 bits (from-position, to-position, piece).

Castling would require an extra 16 bits, as it''s a dual move.

Queened pawns could be represented by one of the 4 spare values out of 4 bits.

Without doing the maths in detail, this starts to save space after the first move compared to storing 32 * 7 bits (predefined array of pieces) or 64 * 4 bits (predefined assignment of squares)

After 10 moves on both sides, the maximum space required is 640 bits

...but then again, if we identify each piece uniquely (5 bits) and add a sixth bit for flagging queened pawns, then we only need piece-id + to-position for each move. This changes the calculation to...

Initial positions = max 384 bits (32 pieces, 6 + 6 bits) Each move = 12 bits (to-position, piece-id)

Then after 10 moves on each side the maximum space required is 624 bits

I''d try to use Huffman encoding . The theory behind this is - in every chess game there will be some pieces that will move around a lot, and some that don''t move much or get eliminated early. If the starting position has some pieces already removed - all the better. The same goes for squares - some squares get to see all action, while some don''t get touched much.

Thus I''d have two Huffman tables - one for pieces, other for squares. They will be generated by looking at the actual game. I could have one large table for every piece-square pair, but I think that would be pretty inefficient because there aren''t many instances of the same piece moving on the same square again.

Every piece would have an assigned ID. Since there are 32 different pieces, I would need just 5 bits for the piece ID. The piece IDs are not changing from game to game. The same goes for square IDs, for which I would need 6 bits.

The Huffman trees would be encoded by writing each node down as they are traversed in inorder (that is, first the node is output, then its children from left to right). For every node there will be one bit specifiying whether it''s a leaf node or a branch node. If it''s a leaf node, it will be followed by the bits giving the ID.

The starting position will simply be given by a series of piece-location pairs. After that there will be one piece-location pair for every move. You can find the end of the starting position descriptor (and the start of the moves descriptor) simply by finding the first piece that is mentioned twice. In case a pawn gets promoted there will be 2 extra bits specifying what it becomes, but the piece ID won''t change.

To account for the possibility that a pawn is promoted at the start of the game there will also be a "promotion table" between the huffman trees and the data. At first there will be 4 bits specifying how many pawns are upgraded. Then for each pawn there will be its huffman-encoded ID and 2 bits specifying what it has become.

The huffman trees will be generated by taking into account all the data (both the starting position and the moves) and the promotion table. Although normally the promotion table will be empty or have just a few entries.

To sum it up in graphical terms:

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

Added: This could still be optimized. Every piece only has a few legal moves. Instead of simply encoding the target square one could give 0-based IDs for the possible moves of every piece. The same IDs would get reused for every piece, so in total there would be no more than 21 different IDs (the queen can have at most 21 diffferent possible move options). Put this in a huffman table instead of the fields.

This would however present a difficulty in representing the original state. One might generate a series of moves to put each piece in its place. In this case it would be necessary to somehow mark the end of the initial state and start of the moves.

Alternatively they could be placed by using uncompressed 6-bit square IDs.

Whether this would present an overall decrease in size - I don''t know. Probably, but should experiment a bit.

Added 2: One more special case. If the game state has NO moves it becomes important to distinguish who moves next. Add one more bit at the end for that. :)

I''d use a run length encoding. Some pieces are unique (or exist only twice), so I can omit the length after them. Like cletus, I need 13 unique states, so I can use a nibble (4 bits) to encode the piece. The initial board would then look like this:

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

which leaves me with 8+2+4+2+8 nibbles = 24 nibbles = 96 bits. I can''t encode 16 with a nibble but since "Empty, 0" doesn''t make sense, I can treat "0" as "16".

If the board is empty but for a single pawn in the upper left corner, I get "Pawn, 1, Empty, 16, Empty, 16, Empty 16, Empty, 15" = 10 nibbles = 40 bits.

The worst case is when I have an empty square between each piece. But for the encoding of the piece, I just need 13 out of 16 values, so maybe I can use another one to say "Empty1". Then, I need 64 nibbles == 128bits.

For the movements, I need 3 bits for the piece (the color is given by the fact that white always moves first) plus 5 bits (0..63) for the new position = one byte per movement. Most of the time, I don''t need the old position since only a single piece will be within range. For the odd case, I must use the single unused code (I just need 7 codes to encode the piece) and then 5 bits for the old and 5 bits for the new position.

This allows me to encode castling in 13 bites (I can move the King towards the Rook which is enough to say what I intend).

[EDIT] If you allow a smart encoder, then I need 0 bits for the initial setup (because it doesn''t have to be encoded in any way: It''s static) plus one byte per move.

[EDIT2] Which leaves the pawn transformation. If a pawn reaches the last row, I can move it in place to say "transforms" and then add the 3 bits for the piece it is replaced with (you don''t have to use a queen; you can replace the pawn with anything but the King).

I''ve thought about that one for a long time (+- 2hours). And there is no obvious answers.

Asumiendo:

  1. Ignoring time state (A player didn''t use to have a time limit therefore could force a draw by not playing)
  2. When was the game played?!? It''s important because the rules have changed over time (so will assume a modern game in the subsequent point a modern game...) Please refer to dead pawn rule for example (wikipedia has a very famous problem showing it), and if you want to go back in time good luck bishop used to only move slowly and dice used to be used. lol.

... so up to date modern rules it is. First irrespective of repetition and move repitition limit.

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

=64 bits (something/nothing) +32*4 bits [ 1bit=color{black/withe} +3bit=type of piece{King,Queen,Bishop,kNight,Rook,Pawn,MovedPawn} NB:Moved pawn... eg if it was the last moved pawn in the previous turn indicating that an ''en passant'' is feasible. ] +5bit for the actual state (who''s turn, en passant, possibility of rooking or not on each sides)

Hasta aquí todo bien. Probably can be enhanced but then there would be variable length and promotion to take in consideration!?

Now, following rules are only applicable WHEN a player apllies for a draw, IT IS NOT automatic! So consider this 90 moves without a capture or aa pawn move is feasible if no player calls for a draw! Meaning that all moves need to be recorded... and available.

-D repetion of position... eg state of board as mentioned above (see C) or not... (see following regarding the FIDE rules) -E That leaves the complex problem of 50 move allowance without capture or pawn move there a counter is necessary... However.

So how do you deal with that?... Well really there is no way. Because neither player may want to draw, or realize that it has occurred. Now in case E a counter might suffice... but here is the trick and even reading the FIDE rules (http://www.fide.com/component/handbook/?id=124&view=article) I can''t find an answer... what about loss of ability of rooking. Is that a repetition? I think not but then this is a blurred subject not addressed, not clarified.

So here is two rules that are two complex or undefined even to try to encode... Cheers.

So the only way to truly encode a game is to record all from start... which then conflict (or not?) with the "board state" question.

Hope this help... not too much math :-) Just to show that some question are not as easy, too open for interpretation or pre-knowledge to be a correct and efficient. Not one I would consider for interviewing as it open too much of a can of worm.

If computational time is not an issue then you could use a deterministic possible position generator to assign unique ids to a given position.

From a given position first generate number of possible positions in a deterministic manor, eg starting bottom left moving to top right. That determines how many bits you''ll need for the next move, some situations it could be as little as one. Then when the move is made store just the unique id for that move.

Promotion and other rules simply count as valid moves as long as they are handled in a deterministic way, eg to queen, to rook, to bishop each count as a separate move.

The initial position is hardest and could generate around 250 million possible positions (I think) which would require about 28 bits plus an extra bit to determine whose move it is.

Assuming we know who''s turn it is (each turn flips from white to black) the deterministic generator would look something like:

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

''get list of possible moves'' would do something like:

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.

If the king is in check then each ''list of possible xxx moves'' only returns valid moves that change the check situation.

In the base case of the initial board plus subsequent moves, consider the following.

Use a chess program to assign probabilities to all possible moves. For example, 40% for e2-e4 20% for d2-d4, and so on. If some moves are legal but not considered by that program, give them some low probability. Use arithmetic coding to save which choice was taken, which will be some number between 0 and 0.4 for the first move, 0.4 and 0.6 for the second, and so on.

Do the same for the other side. For example, if there is a 50% chance of e7-e5 as the response to e2-e4 then the encoded number will be between 0 and 0.2. Repeat until the game is done. The result is a potentially very small range. Find the binary fraction with the smallest base which fits in that range. That''s arithmetic coding.

This is better than Huffman because it can be thought of as fractional bit encoding (plus some at the end of the game to round up to a whole bit).

The result should be more compact than Huffman, and there are no special cases for promotion, en passant, the 50 rule move, and other details because they are handled by the chess evaluation program.

To replay, again use the chess program to evaluate the board and assign all probabilities to each move. Use the arithmetic encoded value to determine which move was actually played. Repeat until done.

If your chess program is good enough, you can get better compression with a two-state encoder, where the probabilities are defined based on moves for both black and white. In the most extreme case of some 200+ states, this encodes the entire set of all possible chess games, and is therefore not feasible.

This is pretty much a different way of saying what Darius already wrote, only with a bit of example of how arithmetic coding might work, and a real example of using an existing chess program to help evaluate the probability of the next move(s).

Is the problem to give an encoding that is most efficient for typical chess games, or one that has the shortest worst case encoding?

For the latter, the most efficient way is also the most opaque: create an enumeration of all possible pairs (initial board, legal sequence of moves), which, with the draw-on-thrice-repeated-position and no-more-than-fifty-moves since last-pawn-move-or-capture rules, is recursive. Then the index of a position in this finite sequence gives the shortest worst-case encoding, but also and equally long encoding for typical cases, and is, I expect, very expensive to compute. The longest possible chess game is supposed to be over 5000 moves, with there typically being 20-30 moves available in each position to each player (though fewer when there are few pieces left) - this gives something like 40000 bits needed for this encoding.

The idea of enumeration can be applied to give a more tractable solution, as described in Henk Holterman''s suggestion for encoding moves above. My suggestion: not minimal, but shorter than the examples above I''ve looked at, and reasonable tractable:

  1. 64 bits to represent which squares are occupied (occupancy matrix), plus list of which pieces are in each occupied square (can have 3 bits for pawns, and 4 bits for other pieces): this gives 190 bits for start position. Since there can''t be more than 32 pieces on board, the encoding of the occupancy matrix is redundant & so something like common board positions can be encoded, say as 33 set bits plus index of board from common boards list.

  2. 1 bit to say who makes first move

  3. Code moves per Henk''s suggestion: typically 10 bits per pair of white/black move, though some moves will take 0 bits, when a player has no alternative moves.

This suggests 490 bits to code a typical 30-move game, and would be a reasonably efficient representation for typical games.

Abouth encoding the draw-on-thrice-repeated-position and no-more-than-fifty-moves since last-pawn-move-or-capture rules: if you encode thepast moves back to the last pawn move or capture, then you have enough information to decide whether these rules apply: no need for the whole game history.

Just like they encode games on books and papers: every piece has a symbol; since it''s a "legal" game, white moves first - no need to encode white or black separetely, just count the number of moves to determine who moved. Also, every move is encoded as (piece,ending position) where ''ending position'' is reduced to the least amount of symbols that allows to discern ambiguities (can be zero). Length of game determines number of moves. One can also encode the time in minutes (since last move) at every step.

Encoding of the piece could be done either by assigning a symbol to each (32 total) or by assigning a symbol to the class, and use the ending position to understand which of the piece was moved. For example, a pawn has 6 possible ending positions; but on average only a couple are available for it at every turn. So, statistically, encoding by ending position might be best for this scenario.

Similar encodings are used for spike trains in computational neuroscience (AER).

Drawbacks: you need to replay the entire game to get at the current state and generate a subset, much like traversing a linked list.

Like Robert G, I''d tend to use PGN since it''s standard and can be used by a wide range of tools.

If, however, I''m playing a chess AI that''s on a distant space probe, and thus every bit is precious, this is what I''d do for the moves. I''ll come bock to encoding the initial state later.

The moves don''t need to record state; the decoder can take keep track of state as well as what moves are legal at any given point. All the moves need to record is which of the various legal alternatives is chosen. Since players alternate, a move doesn''t need to record player color. Since a player can only move their own color pieces, the first choice is which piece the player moves (I''ll come back to an alternative that uses another choice later). With at most 16 pieces, this requires at most 4 bits. As a player loses pieces, the number of choices decreases. Also, a particular game state may limit the choice of pieces. If a king can''t move without placing itself in check, the number of choices is reduced by one. If a king is in check, any piece that can''t get the king out of check isn''t a viable choice. Number the pieces in row major order starting at a1 (h1 comes before a2).

Once the piece is specified, it will only have a certain number of legal destinations. The exact number is highly dependent on board layout and game history, but we can figure out certain maximums and expected values. For all but the knight and during castling, a piece can''t move through another piece. This will be a big source of move-limits, but it''s hard to quantify. A piece can''t move off of the board, which will also largely limit the number of destinations.

We encode the destination of most pieces by numbering squares along lines in the following order: W, NW, N, NE (black side is N). A line starts in the square furthest in the given direction that''s legal to move to and proceeds towards the. For an unencumbered king, the list of moves is W, E, NW, SE, N, S, NE, SW. For the knight, we start with 2W1N and proceed clockwise; destination 0 is the first valid destination in this order.

  • Pawns: An unmoved pawn has 2 choices of destinations, thus requiring 1 bit. If a pawn can capture another, either normally or en passant (which the decoder can determine, since it''s keeping track of state), it also has 2 or 3 choices of moves. Other than that, a pawn can only have 1 choice, requiring no bits. When a pawn is in its 7 th rank, we also tack on the promotion choice. Since pawns are usually promoted to queens, followed by knights, we encode the choices as:
    • queen: 0
    • knight: 10
    • bishop: 110
    • rook: 111
  • Bishop: at most 13 destinations when at {d,e}{4,5} for 4 bits.
  • Rook: at most 14 destinations, 4 bits.
  • Knights: at most 8 destinations, 3 bits.
  • Kings: When castling is an option, the king has it''s back to S and can''t move downwards; this gives a total of 7 destinations. The rest of the time, a king has at most 8 moves, giving a maximum of 3 bits.
  • Queen: Same as choices for bishop or rook, for a total of 27 choices, which is 5 bits

Since the number of choices isn''t always a power of two, the above still wastes bits. Suppose the number of choices is C and the particular choice is numbered c , and n = ceil(lg( C )) (the number of bits required to encode the choice). We make use of these otherwise wasted values by examining the first bit of the next choice. If it''s 0, do nothing. If it''s 1 and c + C < 2 n , then add C to c . Decoding a number reverses this: if the received c >= C , subtract C and set the first bit for the next number to 1. If c < 2 n - C , then set the first bit for the next number to 0. If 2 n - C <= c < C , then do nothing. Call this scheme "saturation".

Another potential type of choice that might shorten the encoding is to choose an opponents piece to capture. This increases the number of choices for the first part of a move, picking a piece, for at most an additional bit (the exact number depends on how many pieces the current player can move). This choice is followed by a choice of capturing piece, which is probably much smaller than the number of moves for any of the given players pieces. A piece can only be attacked by one piece from any cardinal direction plus the knights for a total of at most 10 attacking pieces; this gives a total maximum of 9 bits for a capture move, though I''d expect 7 bits on average. This would be particularly advantageous for captures by the queen, since it will often have quite a few legal destinations.

With saturation, capture-encoding probably doesn''t afford an advantage. We could allow for both options, specifying in the initial state which are used. If saturation isn''t used, the game encoding could also use unused choice numbers ( C <= c < 2 n ) to change options during the game. Any time C is a power of two, we couldn''t change options.

Most of the answers overlooked 3 fold repetition. unfortunately for 3 fold repetition you have to store all the positions played so far...

The question required us to store in space efficient manner so we really don''t need to store position as long as we can construct it from the list of moves (provided we have standard starting position). We can optimize PGN and thats it we are done. Bellow is a simple scheme.

There are 64 squares on the board, 64 = 2^ 6. If we store only the initial and final square of each move that would take 12 bits (Promotion will be tackled later). Note that this scheme already covers player to move, emphassant, piece captured, castling etc; as of these can be constructed from just replaying the move list.

for promotion we can keep a separate array of vectors which would say "at move N promote to Piece XYZ". we can keep a vector of (int, byte).

It is tempting to optimize (To,From) vector also, Since many of these (To,From) vectors are not posible in chess. p.ej. there wont be a move from e1 to d8 etc. But I couldnt come up with any scheme. Any further ideas are most welcomed.

The position on a board can be defined in 7 bits (0-63 , and 1 value specifying it is not on the board anymore). So for every piece on the board specify where it is located.

32 pieces * 7 bits = 224 bits

EDIT: as Cadrian pointed out... we also have the ''promoted pawn to queen'' case. I suggest we add extra bits at the end to indicate which pawn have been promoted.

So for every pawn which has been promoted we follow the 224 bits with 5 bits which indicate the index of the pawn which has been promoted, and 11111 if it is the end of the list.

So minimal case (no promotions) is 224 bits + 5 (no promotions). For every promoted pawn add 5 bits.

EDIT: As shaggy frog points out, we need yet another bit at the end to indicate whose turn it is ;^)

There are 32 pieces on the board. Each piece has a position (one in 64 squares). So you just need 32 positive integers.

I know 64 positions hold in 6 bits but I wouldn''t do that. I''d keep the last bits for a few flags (dropped piece, queen''ed pawn)

There are 64 possible board positions, so you need 6 bits per position. There are 32 initial pieces, so we have 192 bits total so far, where every 6 bits indicates the position of the given piece. We can pre-determine the order the pieces appear in, so we don''t have to say which is which.

What if a piece is off the board? Well, we can place a piece on the same spot as another piece to indicate that it is off the board, since that would be illegal otherwise. But we also don''t know whether the first piece will be on the board or not. So we add 5 bits indicating which piece is the first one (32 possibilities = 5 bits to represent the first piece). Then we can use that spot for subsequent pieces that are off the board. That brings us to 197 bits total. There has to be at least one piece on the board, so that will work.

Then we need one bit for whose turn it is - brings us to 198 bits .

What about pawn promotion? We can do it a bad way by adding 3 bits per pawn, adding on 42 bits. But then we can notice that most of the time, pawns aren''t promoted.

So, for every pawn that is on the board, the bit ''0'' indicates it is not promoted. If a pawn is not on the board then we don''t need a bit at all. Then we can use variable length bit strings for which promotion he has. The most often it will be a queen, so "10" can mean QUEEN. Then "110" means rook, "1110" means bishop, and "1111" means knight.

The initial state will take 198 + 16 = 214 bits , since all 16 pawns are on the board and unpromoted. An end-game with two promoted pawn-queens might take something like 198 + 4 + 4, meaning 4 pawns alive and not promoted and 2 queen pawns, for 206 bits total. Seems pretty robust!

===

Huffman encoding, as others have pointed out, would be the next step. If you observe a few million games, you''ll notice each piece is much more likely to be on certain squares. For example, most of the time, the pawns stay in a straight line, or one to the left / one to the right. The king will usually stick around the home base.

Therefore, devise a Huffman encoding scheme for each separate position. Pawns will likely only take on average 3-4 bits instead of 6. The king should take few bits as well.

Also in this scheme, include "taken" as a possible position. This can very robustly handle castling as well - each rook and king will have an extra "original position, moved" state. You can also encode en passant in the pawns this way - "original position, can en passant".

With enough data this approach should yield really good results.

Thomas has the right approach for encoding the board. However this should be combined with ralu''s approach for storing moves. Make a list of all possible moves, write out the number of bits needed to express this number. Since the decoder is doing the same calculation it knows how many are possible and can know how many bits to read, no length codes are needed.

Thus we get 164 bits for the pieces, 4 bits for castling info (assuming we are storing a fragment of a game, otherwise it can be reconstructed), 3 bits for en passant eligibility info--simply store the column where the move occurred (If en passant isn''t possible store a column where it''s not possible--such columns must exist) and 1 for who is to move.

Moves will typically take 5 or 6 bits but can vary from 1 to 8.

One additional shortcut--if the encode starts with 12 1 bits (an invalid situation--not even a fragment will have two kings on one side) you abort the decode, wipe the board and set up a new game. The next bit will be a move bit.

[edited after reading the question properly] If you assume every legal position can be reached from the initial position (which is a possible definition of "legal"), then any position can be expressed as the sequence of moves from the start. A snippet of play starting from a non-standard position can be expressed as the sequence of moves needed to reach the start, a switch to turn the camera on, followed by subsequent moves.

So let''s call the initial board state the single bit "0".

Moves from any position can be enumerated by numbering the squares and ordering the moves by (start, end), with the conventional 2 square jump indicating castling. There is no need to encode illegal moves, because the board position and the rules are always already known. The flag to turn the camera on could either be expressed as a special in-band move, or more sensibly as an out-of-band move number.

There are 24 opening moves for either side, which can fit in 5 bits each. Subsequent moves might require more or less bits, but the legal moves are always enumerable, so the width of each move can happily grow or expand. I have not calculated, but I imagine 7 bit positions would be rare.

Using this system, a 100 half-move game could be encoded in approximately 500 bits. However, it might be wise to use an opening book. Suppose it contains a million sequences. Let then, an initial 0 indicate a start from the standard board, and a 1 followed by a 20 bit number indicate a start from that opening sequence. Games with somewhat conventional openings might be shortened by say 20 half-moves, or 100 bits.

This is not the greatest possible compression, but (without the opening book) it would be very easy to implement if you already have a chess model, which the question assumes.

To further compress, you''d want to order the moves according to likelihood rather than in an arbitrary order, and encode the likely sequences in fewer bits (using eg Huffman tokens as people have mentioned).