Escriba un algoritmo o programa que pueda codificar y decodificar un tablero de ajedrez. El objetivo es hacer la representación más pequeña de un tablero de ajedrez que pueda usarse (una vez decodificado) para determinar todas las posibilidades de movimiento para un jugador en ese turno.
La codificación debe poder mostrar:
- De quién es el turno.
- Si el jugador puede enrocarse en cada lado.
- Si el jugador puede realizar un pase, y si es así, ¿cuál de sus peones?
- Posiciones de todas las piezas.
Nota importante sobre el enroque: si las blancas mueven a su rey un turno, y luego lo retrocede al siguiente, debe quedar claro que no pueden enrocarse en ningún lado después de eso. Lo mismo ocurriría si movieran su torre izquierda o derecha. Aunque el tablero está visualmente en el mismo estado que hace dos turnos, el estado del juego ha cambiado. Más información aquí: http://en.wikipedia.org/wiki/Chess#Castling
Nota importante sobre en-passant: este también es un movimiento sensible al giro. Lea las reglas para más información. http://en.wikipedia.org/wiki/Chess#En_passant
Determine la entrada y salida según sea necesario. ¡Grandes apoyos para quien pueda comprimirlo más!
Su puntaje se determina en el peor de los casos: tamaño máximo posible en bits. Asegúrese de mostrar cómo calculó ese número y lo que representó. ¡Dispara por el peor de los casos!
fuente
Respuestas:
Mín .: 12 bits
Máx .:
Promedio:
Anoche pensé que posiblemente podría hacerlo aún más pequeño.
¡El resultado es un tamaño impresionante de 12 bits !
Entonces, ¿qué pasa con K +1 otro tipo de pieza?
Hay 2 posibles arreglos del subárbol.
Ambas dan como resultado los mismos tamaños de bits para todas las piezas. Por lo tanto, no importa cuál usemos, elegiré el primero.
Así que en King +2 otros tipos de piezas
Hay 5 posibles subárboles (usaré 1 y 2 para indicar cuál de las piezas).
Por lo tanto, necesitaremos 3 bits para codificar qué subárbol usar.
Sigo haciendo el análisis para más piezas
+3 Otro
+4 Otro
+5 Otro
Max: 208?
¿Es posible codificar todos estos subárboles en 9 bits?
Si sumamos todos los subárboles posibles, obtenemos 392 subárboles posibles.
Usar ID de frecuencia
Desde allí 164603 frecuencias de piezas únicas .
(+000) (+00) Enroque
Máx .: = 204 bits
rev 3
Mín .: 82 Máx .: 199 Promedio: 160
Finalmente me puse a hacer un análisis para encontrar el tamaño máximo de bit. Con codificación huffman óptima para cada una de las frecuencias de piezas únicas .
Tenga en cuenta que este es el peor tamaño posible, que la columna En-Passant muerde si el número de peones es mayor que uno. Independientemente de los colores y la posición de esos peones, existe la posibilidad de que algunas tablas sean 3 bits más pequeñas.
Además, solo hay 144 tamaños diferentes (el peor de los casos) para el tamaño del tablero.
75 - 216 bits (v2) v1 El tamaño mínimo es de 98 bits (12.25 bytes), solo los dos reyes en el tablero.
El tamaño máximo es de solo 216 bits (27 bytes). En el caso improbable: -
En promedio, el tamaño será de alrededor de 157 bits (19.625 bytes).
Piezas
Para codificar el tablero, estoy usando un esquema de codificación de árbol binario. Un cuadrado vacío es el más frecuente desde cualquier lugar entre 32 y 62 apariciones. Luego están los peones, luego Rooks, Knights, Bishops y los menos frecuentes son Queen y King.
La placa de inicio se puede codificar en solo 166 bits (20,75 bytes)
Para indicar quién se mueve, solo se necesita un bit
El enroque puede codificarse en 4 bits.
Entonces uso 171 bits (21.375 bytes)
En-Passe se puede codificar en solo 16 bits (2 bytes)
Entonces, en total, eso es 187 bit (23.375 bytes).
Diseño
Aún no se ha escrito ningún código.
Observe que 3 de los bits que no se utilizan. Entonces el máximo es 213bits .
Posibles mejoras
1) Se redujo el bloque de encabezado de 24 a 8 bits (con la sugerencia de @Peter Taylor)
2) encabezado de longitud variable
Un pequeño encabezado fijo de 4 bits
Siguiente bloque de bits adicionales (si el enroque aún es posible)
Siguiente bloque de bits adicionales (si hay peones)
Así que ahora tengo un encabezado de longitud variable de 4 a 11 bits
3) Use un esquema de codificación diferente según las piezas que queden en el tablero.
Al cambiar la codificación del árbol dependiendo de qué piezas están en el tablero y su frecuencia.
Una posible codificación para un estado final del juego (sin peones)
Que es aproximadamente ~ 4 bits por pieza.
¿Qué tipo de piezas están presentes en el tablero?
La permutación es de longitud variable de 0-5 bits. Si solo queda un tipo de pieza, no lo incluya.
¿Qué permutación de esas piezas usar para el árbol? Este es el factorial del número de piezas en el ejemplo anterior, son 5 piezas, por lo que se pueden codificar 120 permutaciones posibles.
Recuerde que hay bits de adición para los cuadrados vacíos y el color.
Ejemplos
Pongamos un ejemplo de solo QK restante
81 bits en total
Vamos a dar un ejemplo de los reyes que quedan
Poner todo junto
Entonces calculo la codificación más pequeña para la placa a 75 bits (9 bits 3 bits)
Aún no se ha calculado cómo este esquema de codificación afecta el tamaño máximo.
Mejora 4
Reduzca el número de bits para enrocar a solo 2 bits. Solo enroque para el jugador que es el turno.
Pensando en ello, quizás sea mejor incluir los 2 bits dentro del bloque de encabezado.
fuente
1111
para "no en passant possible" o la columna como un número binario de lo contrario).192 bits (peor caso)
Aquí hay un esquema de almacenamiento muy simple que debería hacer frente a promociones arbitrarias de peones, y nunca requiere más de 64 + 4 × 32 = 192 bits:
Los primeros 64 bits almacenan un tablero de bits que dice dónde están las piezas (pero no cuáles son). Es decir, almacenamos un bit para cada cuadrado del tablero de ajedrez (comenzando en el cuadrado a1, luego b1, c1, etc. hasta el cuadrado h8) de modo que un cuadrado vacante esté representado por 0 y un cuadrado ocupado por 1.
A continuación, para cada uno de los cuadrados marcados como ocupados en el tablero de bits, almacenamos un mordisco de 4 bits que codifica la pieza en ese cuadrado. El primero de los cuatro bits codifica el color de la pieza (0 = blanco, 1 = negro), mientras que los tres bits restantes codifican el tipo de pieza:
Tenga en cuenta las dos codificaciones para el rey, que se utilizan para determinar qué turno de jugador debe mover. (De hecho, dado que siempre hay dos reyes en el tablero, lo que permite cuatro combinaciones de los códigos 5 y 6, podríamos codificar fácilmente un segundo bit de información aquí).
Para codificar la información adicional necesaria para las reglas al pasar y enrocar, introducimos un tipo de pieza adicional, que denota un peón o una torre, dependiendo de la fila en la que aparece:
Poniendolo todo junto:
El número total de bits necesarios para codificar el estado de la placa es, por lo tanto, 64 + 4 × # de piezas a bordo. Como nunca puede haber más de 32 piezas en el tablero, la longitud máxima de esta codificación es de 192 bits.
Por ejemplo, utilizando la codificación descrita anteriormente, el estado inicial de la placa se codificaría como (espacio en blanco insertado para facilitar la lectura):
o, en hexadecimal:
fuente
160 bits peor de los casos
Después de publicar mi respuesta anterior de 22 bytes, comencé a preguntarme si podríamos llegar a 21 bytes. Sin embargo, cuando vi los increíbles 166 bytes de Peter Taylor pensé "Espera, ¡parece que cinco palabras de 32 bits podrían ser posibles!"
Entonces, después de pensarlo mucho, se me ocurrió esto: 159.91936391 bytes (¡un ajuste bastante ajustado!) Este nivel de compresión necesitaría un programa bastante complicado, pero he pensado cómo hacerlo funcionar en un tiempo razonable.
Esta será una publicación larga, así que tengan paciencia conmigo, publicaré lo que pueda hoy y agregaré algunos bits de código pronto.
Entonces, aquí está cómo hacerlo:
En Passant y castling codificados por posiciones ilegales (0 bits)
De paso
Como se mencionó en otras respuestas, hay un máximo de 5 casillas posibles en las que puede colocarse un peón vulnerable al paso. Estas son las casillas al lado de los peones del jugador cuyo turno es.
Para codificar esto, el peón vulnerable a passant se intercambia con lo que esté en uno de los cuadrados en la primera o última fila. Esto puede ser un hombre o un cuadrado vacío. Esto produce una posición ilegal, ya que los peones no pueden estar en estas filas. El decodificador debe devolver el peón a su posición correcta, extrayendo la información pasante.
Para que esto no interfiera con la codificación del enroque, es importante que los cuadrados en los que se encuentran los reyes al comienzo del juego no se alteren, y que el procedimiento de codificación pasivo no coloque a los reyes uno al lado del otro, lo cual sería una posición de rey ilegal. Para satisfacer el segundo de estos puntos, el codificador tiene dos opciones en cuanto a qué casilla intercambia el peón al pasar. El primer cuadrado de elección para cada uno de los 5 peones son A8, B8, C8, G8, H8. Segunda opción: A1, B1, C1, G1, H1.
Enroque
Un rey al que se le permite castillo está, por definición, todavía en su casilla inicial. Con el rey blanco en su casilla inicial, hay un total de 63 casillas donde el rey negro puede pararse, 58 de las cuales son legales (no se le permite moverse justo al lado del rey blanco porque se pondría a sí mismo bajo control). Si al rey blanco se le permite enrocarse, se le permite hacerlo con su torre izquierda, su torre derecha o ambas. Por lo tanto, hay 3x58 = 174 posibilidades en las que el rey blanco puede enrolar, otras 174 en las que el rey negro puede enrutar, y otras 3x3 = 9 en las que ambos pueden enloquecer, un total de 357.
Hay 420 arreglos ilegales de los dos reyes donde están en casillas adyacentes: 3x4 = 12 cuando el rey blanco está en la esquina, 5x24 = 120 cuando está en el borde y 8x36 = 288 cuando está en otra casilla. Por lo tanto, hay suficientes posiciones ilegales para codificar todas las posibilidades posibles de enroque.
Si al menos un rey tiene permiso para castillo, el codificador buscaría los datos de enroque y los datos posicionales de aquellos reyes a los que no se les permite castillo en una tabla (o, alternativamente, usar un algoritmo que no especificaré aquí) y producir un ilegal posición de los dos reyes. Luego intercambiaría a los reyes con lo que sucediera en estas casillas.
Es importante que esto se codifique después y se decodifique antes del paso, de lo contrario, existen algunas posibles interferencias.
Comparación
¡Hasta ahora no he usado pedacitos! Mirando la respuesta de Peter, todavía tengo lo siguiente para codificar:
Esto es para el peor caso de 29 hombres (vea la respuesta de Peter). A continuación, mostraré cómo realizo una mejora marginal (al menos para el caso de 29 hombres) en los dos puntos marcados en **.
¿Qué casillas están ocupadas / de quién es el turno?
La manera fácil de codificar qué cuadrados están ocupados es con una cuadrícula de 64 bits. Esto también nos dice cuántos cuadrados están ocupados. Sin embargo, es un poco derrochador porque no es posible que haya más de 32 casillas ocupadas. Mi solución es usar 1's para codificar los cuadrados ocupados cuando es el turno de White y 0's para codificar los cuadrados ocupados cuando es el turno de Black. Ahora se utilizan todas las combinaciones y no hay desperdicio.
Por lo tanto, ahorramos un poco para almacenar el turno: menos de 32 1's, es el turno de las blancas, más de 32 1's, es el turno de las negras. El único caso ambiguo es cuando todos los hombres están en el tablero y hay 32 1 y 32 0. Por lo tanto, se necesita un bit extra solo para este caso. Como no puede haber promociones hasta que se haya producido una captura, este bit adicional no afecta el peor de los casos en general (que ocurre con 3 hombres capturados y 29 restantes).
Color de los hombres que ocupan los cuadrados.
Sabemos por lo anterior cuántos hombres hay. El siguiente extracto del triángulo de Pascal indica cuántas posibilidades hay para las diferentes distribuciones de blanco y negro. Por ejemplo, para 3 hombres, las posibilidades son: 3 hombres negros (1 permutación) 2 negros, 1 blanco, (3 permutaciones), 1 negro, 2 blancos (3 permutaciones), 3 blancos (1 permutación). El total es 2 3 = 8. En general, para el menor número de hombres hay 2 n posibilidades. Sin embargo, todas las posibilidades de negro y blanco son ilegales (al menos el rey de cada lado debe estar en el tablero), por lo que el número real de permutaciones legales es 2 n -2 (ignore los 1 en el triángulo de Pascal).
Para más de 16 hombres en total, existe una restricción adicional en el sentido de que no puede haber más de 16 hombres de cada color en el tablero. Por lo tanto, cuando los 32 hombres están en el tablero, debe haber 16 de cada uno y el número total de posibilidades es 601080390, que es bastante menor que 2 32 .
El número de posibilidades se puede encontrar sumando las "filas" de este extracto del triángulo de pascales (con lo cual me refiero a las diagonales NE-SW de la tabla, porque giré el triángulo 45 grados en sentido contrario a las agujas del reloj para una presentación conveniente). para codificar el turno, los cuadrados ocupados y el color de los hombres son, por lo tanto, los siguientes:
Hasta 25 hombres: un poco menos de 64+ (número de hombres)
Para más de 25 hombres:
Para los dos colores, ¿qué hombres y en qué orden?
Según las respuestas anteriores, no se pueden promover peones hasta que se haya producido una captura, porque cada peón está bloqueado por un peón del color opuesto en la misma columna. La respuesta de Peter consideró (como límite superior) que cada captura podría conducir a una promoción para el lado que se está capturando y dos para la captura del lado. Sin embargo, podemos dividir esto en varios casos:
El peón negro captura el peón blanco: ahora el peón capturador es libre de promocionar ya que ahora está en una columna diferente. Su colega en la misma columna también puede promocionar. El peón negro en la columna original del peón blanco también puede promover. Este es el único caso que permite 3 promociones.
El peón negro pasa el peón blanco en la columna adyacente y luego captura la pieza blanca (que no sea el peón) detrás. Esto permite que el peón de captura y el peón blanco que estaba en la columna original promocionen. Una promoción para cada lado.
El peón blanco es capturado por pieza (que no sea el peón). Esto normalmente permitiría una promoción solo para negros. La única excepción es cuando libera una formación de peón bloqueada que ya fue causada por varias capturas que movían peones a la misma columna.
Entonces, como caso base, podemos considerar que cada captura permite una promoción cada una para ambos lados. En el caso de que el hombre capturado sea un peón, puede haber una promoción adicional para el lado de captura.
He escrito un programa similar al de Peter. Es algo más crudo, pero tiene una adición importante: puede calcular el número de permutaciones posibles cuando un jugador comienza con menos de los 8 peones normales. Aquí hay algunos datos producidos por el programa:
Podemos ver que para un caso como 8 peones, 15 hombres, 0 promociones, el número de permutaciones es solo ligeramente menor que para 8 peones, 16 hombres, 0 promociones. Sin embargo, si consideramos un caso como 7 peones, 15 hombres, 0 promociones (que es lo mismo que considerar que el hombre capturado fue definitivamente un peón) obtenemos aproximadamente la mitad del número de permutaciones.
Entonces, para el caso en que las negras tienen 16 hombres y las blancas tienen 15 hombres, podemos considerar una estimación del límite superior de 2 promociones para las negras y una promoción para las blancas:
Sin embargo, podemos hacerlo mejor si procedemos de la siguiente manera.
A. Considere una promoción para cada uno en blanco y negro, suponiendo que el hombre que White ha perdido podría ser de cualquier tipo:
B. Considere las posibilidades adicionales para las negras si tiene dos promociones, multiplicadas solo por las posibilidades para las blancas en las que ha perdido un peón.
Sumando estos dos juntos obtenemos 2.25072E + 18, que es un número menor que 3.55766E + 18. A continuación se enumeran todas las posibilidades para hasta 3 capturas (quedan 29 hombres).
Entonces, para el peor caso de un lado con 15 hombres y el otro con 14 hombres, necesitamos 67.804 bits.
Agregando esto a los 92.116 bits requeridos para especificar qué cuadrados y qué color, obtenemos un total de 67.804 + 92.116 = 159.92 bits.
fuente
177 bits peor caso
Este algoritmo, aunque no es simple, da el peor de los casos de 177 bits (184b = 23B en la práctica), el mejor de los casos en 13b (16b = 2B) cuando solo quedan 2 reyes.
fuente
sum_{i=0}^{15} sum_{j=0}^{15} 62! / (i! j! (62-i-j)!) < 2^87.45
.166 bits
1
bit: ¿de quién es el turno?2
bits: ¿qué opciones de enroque están abiertas? (Nota: al leer detenidamente la pregunta, solo es necesario registrar las opciones de enroque para el jugador cuyo turno es).lg 6 ~= 2.585
bits: ¿qué opciones pasantes están abiertas? (Ver mi otra respuesta)lg sum_{i=1}^{16} sum_{j=1}^{16} 64! / (i! j! (64-i-j)! = lg 3629590441720924477681996172 ~= 91.552
bits: ¿qué cuadrados están ocupados por hombres de qué color?lg 451366131803622235200 ~= 68.613
para indicar qué hombres y en qué orden (ver más abajo)Usando la codificación aritmética (ya que en cada paso estamos aplicando una distribución uniforme) podemos lograr
ceil(3 + 2.585 + 91.552 + 68.613) = 166
bits.La codificación para los hombres: dado que sabemos cuántos hombres de un color dado hay, podemos enumerar fácilmente todas las posibles distribuciones / conjuntos múltiples de hombres (por ejemplo, con 5 hombres podríamos tener un Rey, una Reina, dos Rooks y un Peón) y luego podemos considerar todas las permutaciones posibles de cada distribución.
Sin embargo, podemos hacerlo aún mejor teniendo en cuenta las interdependencias. Solo estoy haciendo esto en un nivel muy básico: ¿cuántas promociones posibles? Un peón solo se puede "pasar" y puede promocionar de tres maneras: captura y, por lo tanto, se mueve a una columna diferente; o su peón opuesto captura y se mueve a una columna diferente; o su peón contrario es capturado. Por lo tanto, una captura para blanco crea potencialmente dos peones pasados para blanco y uno para negro.
Podemos construir una tabla parcial de los límites superiores en las promociones:
También podemos calcular el número de permutaciones dado que un jugador tiene
N
hombres y no más queP
peones promovidos:Combinando los dos, podemos obtener la cantidad de bits necesarios para especificar ambas permutaciones dada la cantidad de hombres en ambos lados:
Si no está en esta sección de la tabla, podemos suponer que ambas partes tienen hasta 8 promociones y todavía lo estamos haciendo mejor que en el peor de los casos, que es 68.613 bits cuando uno tiene 14 hombres y el otro tiene 15 hombres.
Tenga en cuenta que esto aún está lejos de ser una representación perfecta, ya que permite muchas posiciones ilegales.
Código para calcular la tabla de permutación:
fuente
<
lugar de<=
en mi programa. Gracias por mencionarlo. Todavía podría recuperar el puntaje anterior con un revestimiento especial de los 32 hombres que están en el tablero, pero no lo haré en este momento.178 bits (¡174 en un apuro!) Peor de los casos
Hola, acabo de volver a la codificación, lo que realmente no he hecho desde la universidad. Vi este sitio y pensé que esto parecía interesante. Hice una pequeña comprobación teórica y parece que se necesitan al menos 146 bits para un algoritmo perfecto, probablemente bastantes más (explicaré en los comentarios cuando tenga un momento).
De todos modos, esta es la forma en que estructuro los datos. El concepto básico viene en 178 bits, pero con algo de jiggery pokery puede reducirse a 174 (eso es 21 3/4 bytes). 175 es un poco más fácil de programar, es más legible para los humanos y aún tiene 22 bytes.
A) Posición de ambos reyes: 6 bits cada uno para blanco y negro de 12 BITS
B) De los 62 cuadrados restantes, ¿cuáles están ocupados? Una matriz de 62 BITS
C) ¿De quién es el turno? 1 BIT
TOTAL HASTA AHORA: 75 BITS
D) En Passant. Si es el turno de las blancas de moverse, puede parecer que hasta 5 peones negros podrían ser capturados en Passant. El peón negro debe estar en la fila 5 (de abajo hacia arriba comenzando en cero) y tener un peón blanco al lado. Una situación con el número máximo de capturas posibles se ve así:
BWBBWBBW
Si hubiera 6 peones negros en la fila 5, las blancas solo tendrían 2 cuadrados para pararse y solo podrían amenazar a 4 peones negros, por lo que no es posible tener más de 5 peones negros aparentemente amenazados por En passant al mismo tiempo. Por lo tanto, necesitamos un número del 1 al 5 que indique cuál de los (hasta 5) peones en la fila 5 que tiene un peón hostil (en este caso blanco) junto a él avanzó 2 casillas en el último turno ( o cero si no hay peón en esta situación se movió de esta manera en el último turno).
E) De los hasta 30 cuadrados ocupados (sin incluir reyes), ¿qué contienen?
Hay 10 posibilidades, cada una representada por un número decimal.
El bit menos significativo representa el color.
Por lo tanto, los números pares son blancos, los impares son negros.
Blanco negro
Peón 0/1 (o Torre que se le permite al castillo *)
Caballero 2/3
Obispo 4/5
Torre 6/7
Reina 8/9
* Una torre que se le permite al castillo (y por lo tanto nunca se ha movido de la primera o última fila) está representada por 0 o 1 en lugar de 6 o 7. No se puede confundir con un peón, porque no se pueden encontrar peones en la primera o la última fila.
Esto proporciona un número decimal de hasta 30 dígitos, que podemos multiplicar por 6 y luego agregar el código para En passant. El número resultante se ajustará a 103 bits, que cuando se agrega a los 75 mencionados anteriormente es 103 + 75 = 178 bits . En realidad, si simplemente multiplicamos por 10 en lugar de 6, no importa el número de bits utilizados, y la decodificación es más fácil.
Esto es solo 2 bits más de 22 bytes. Sin embargo, podemos reducirlo a 174 bits, como se explica a continuación.
Si no se ha capturado ninguna pieza, entonces es imposible promover un peón .
La prueba es como sigue. Imagina que las blancas están obsesionadas con promocionar su peón en (por ejemplo) la columna E, desde el comienzo del juego. Hay un peón negro enfrente de este peón que está en el camino. Por lo tanto, para promover este peón, debe ocurrir uno de los siguientes:
1) Se captura el peón negro.
2) El peón negro captura otra pieza y, por lo tanto, se aparta del camino.
3) el peón blanco captura un peón en una columna adyacente, como la columna D.
4) el peón blanco pasa (o pasa) un peón negro en una columna adyacente y luego captura una pieza en esa misma columna adyacente, lo que hace que el peón blanco cambie de columna.
El caso 4 es el más interesante, porque no es solo el peón blanco que comenzó en la columna E el que ahora tiene un camino claro hacia la promoción. El peón negro en la columna que permanece en la columna E también puede promover. Por lo tanto, una sola captura puede despejar el camino para que un peón de cada color se promueva.
De todos modos, el hecho de que ningún peón pueda promocionar hasta que se capture una pieza significa que no tenemos que almacenar la pieza 30. Podemos resolverlo por eliminación (o por sustracción, porque el conjunto completo de códigos de pieza al comienzo del juego siempre suma la misma cantidad = 80). Un punto menor es que debemos asegurarnos de que los cuadrados donde están las torres al comienzo del juego se encuentran los primeros escaneados (porque si fueran los últimos, no sabríamos si la torre podría enrocarse o no). Esto se hace fácilmente escaneando la fila 0 y luego las filas 7 a 1: Para r = Fila de exploración 8 a 1 [r mod 8].
Entonces, la matriz de bits en (B) nos dirá cuántas piezas hay (excluyendo reyes). Si hay un total de 30, ignore la última pieza al codificar, el decodificador resolverá cuál era. Ahora tenemos un número decimal de hasta 29 dígitos, que multiplicamos por 6 y agregamos al código En Passant. El número resultante se comprimirá en 99 bits, dando un total de 99 + 75 = 174 bits.
Como ejemplo, aquí hay una posición real. Las blancas acaban de hacer su primer movimiento (peón del rey avanzado) y es el turno de las negras.
A) Posición de los reyes (Blanco / Negro en octal, 12 bits ): 03 73 = 000011 111011
B) ¿Qué cuadrados están ocupados? Comience con la fila cero (fila inferior), luego todas las demás filas de arriba a abajo, omitiendo a los reyes:
C) Turno negro: Bit de giro = 1
D) En Passant. No hay peón blanco al lado de un peón negro, por lo tanto, no hay peón que se pueda tomar de pasada (aunque este peón sí avanzó el último movimiento), entonces D = 0.Si, en lugar de considerar solo los peones que tienen un peón hostil junto a ellos, consideramos todos los peones que no tienen piezas amigas al lado de ellos en ambos lados, entonces D sería 1, ya que hay uno de esos peones en esta situación, y esto en particular el peón se movió de hecho en el último turno.
E) Nuevamente, primero la fila inferior, luego todas las demás filas de arriba a abajo, omitiendo a los reyes, y con las cuatro torres no extendidas denominadas 0 o 1 (números normalmente reservados para los peones).
El trigésimo dígito (entre paréntesis) se puede descartar.
Aunque no es muy evidente aquí, el peón que las blancas han avanzado está realmente en un extremo de la lista de peones, porque escaneamos fila por fila.
Nuestros datos ahora se ven así, con 29 códigos para el contenido de cuadrados, más el código En Passant:
Es mejor escanear de derecha a izquierda al decodificar y de izquierda a derecha (orden inverso) al codificar. Esto significa que cuando haya menos piezas tendremos un número menor, al tiempo que mantendremos la máxima consistencia (es decir, queremos que el espacio en blanco / ceros sean iniciales, no finales, para permitir la compresión de tablas escasamente ocupadas). Cuando solo tenemos 2 reyes en el tablero, tendremos los 75 bits mencionados anteriormente, más 3 bits para almacenar datos passant = 78 bits en el mejor de los casos. Cada pieza adicional viene en un poco menos de 3.5 bits (2 piezas se pueden almacenar en 7 bits, porque 100 <128).
Existe un problema práctico en el sentido de que un número entero de 99 bits es demasiado grande para caber en una variable entera de 64 bits, lo que significa que muchos lenguajes de programación no lo admiten (no puede convertir simplemente una representación de cadena de 29-30 dígitos número en un número entero.) Como una manera fácil de codificar para 22 bytes, podemos dividir un número de 30 dígitos (códigos de 29 piezas + código pasante) en dos números de 15 dígitos, cada uno de los cuales cabrá en 50 bits cada uno (total de 100 bits además de los 75 mencionados anteriormente, el peor caso es de 175 bits).
Para una compresión máxima, como se indicó anteriormente, 29 dígitos decimales más el código En Passant (6 valores posibles), casi encajarán en 99 bits (para un total de 174 bits) pero sin el soporte del lenguaje para enteros de este tamaño es complicado de programar Puede ser más fácil separar los 29 bits de color y trabajar con los códigos de pieza (5 posibilidades) y el código En passant (6 posibilidades) por separado de los colores (70 bits, casi encaja en una variable de 64 bits).
fuente
Aquí hay una solución completa, el peor de los casos, 181 bits
El enfoque aquí es un programa simple que puedes entender fácilmente
La entrada es FEN, aquí está la posición de apertura, tiene seis campos (5 y 6 ignorados):
El primer campo (colocación de piezas) se analiza
Para producir:
Campo uno: codifica la ubicación de los reyes (12 bits):
Campo dos: codificar piezas (hasta 5 bits por pieza):
Campo tres: color activo (1 bit)
Campo cuatro: disponibilidad de enroque (4 bits)
Campo cinco: en passant (cero o 3 bits)
Ingenuo peor caso 200 bits
QRRBBNN QQQQQQQQ
- 75 bitsqrrbbnn qqqqqqqq
- 75 bitsEl peor caso real
Cada jugador no puede promover todos los peones sin capturar otras piezas . Aquí está el efecto de entropía de la captura de piezas:
PpR
(3 + 3 + 5 = 11 bits) =>Qq_
(5 + 5 + 1 = 11 bits)PPpp
(3 + 3 + 3 + 3 = 12 bits) =>QQq_
(5 + 5 + 5 + 1 = 16 bits)Entonces, en realidad, el peor caso es:
QRRBBNN QQQQQQQQ
- 75 bitsqrrbbnn qqqq
- 55 bitsEl peor de los casos es promover todas las piezas en lugar de dejar el peón para pasar.
TOTAL CASO PEOR REAL CON CÓDIGO MOSTRADO 12 + 75 + 55 + 34 + 1 + 4 = 181 bits
FIQ muestra dos mejoras a este esquema simple, pero son más difíciles de codificar:
El único código restante que no se muestra en esta respuesta (por brevedad) es: romper la entrada FEN en los campos (
split /\s/
) y la asignación de variables.fuente
PPpp
=>QQq_
Los datos totales necesitan 33 bytes
(Gracias a alguien en los comentarios, me di cuenta de que esto no funciona para la promoción de peones. Actualizaré esto cuando pueda resolverlo)
para el primer byte usamos cinco bits:
los siguientes 32 bytes se usan para representar cada pieza de ajedrez, en un orden predefinido
representa si se ha capturado. 0 = no capturado
(si puede pasar, definitivamente no se captura)
Algún código C para representar esta idea (que en realidad no funciona)
fuente
256242 bitsAquí hay un algoritmo de compresión básico que probablemente pueda mejorarse porque no excluye ciertas posiciones ilegales de ser representadas.
El tablero comienza con 5 bits de información de encabezado, de la siguiente manera:
Luego, una cadena de 12 bits que representa las posiciones de los reyes.
Luego, un gran número de 64 dígitos en la base 11, que luego se multiplica por 9 para agregar otro dígito al final que represente el estado de en-passant. Cada dígito en la base 11 representa un cuadrado en el tablero, con los siguientes valores posibles:
Y los dígitos en la base 9:
11 64 × 9 es aproximadamente 2 224.57 , que requiere 225 bits para codificar. Además, los 17 bits de encabezado en la parte superior son 242 bits en total.
Gracias a ugoren por las mejoras.
fuente
13^64 * 9
es 239.99, ahorrando 11 bits. Ahorre más codificando posiciones de rey por separado.? pedacitos
(≥ 217 en el peor de los casos, 17 en el mejor de los casos, 179 para la placa inicial)
Descripción de codificación
Los metadatos adicionales consisten en el turno de quién es (un bit) y el enroque (cuatro bits, es decir, ¿puede el castillo blanco en el lado de los reyes? ¿En el lado de las reinas? Y de manera similar para el negro).
Para la posición del tablero en sí, lo codificamos como un conjunto de piezas activas. Bueno, en realidad, nos aseguramos de enumerar las piezas en un orden particular por razones que explicaré más adelante. Para cada pieza almacenamos su color (un bit), su tipo (tres bits para abarcar 6 tipos, más un tipo adicional para "peón que puede ser tomado por passant"), así como su posición.
Aquí está la parte interesante: para codificar la posición de una pieza, en lugar de almacenarla como una coordenada, almacenamos su distancia relativa de la última pieza al enumerar las piezas en orden de izquierda a derecha, de arriba a abajo (es decir, A8 , B8, ..., G1, H1). Además, almacenamos la distancia como un número de longitud variable, usando
1
que significa que esta pieza está justo al lado de la anterior,0xx
para saltar 1-3 piezas,000xxx
para saltar 4-10 piezas,000000xxxx
para 11-25,0000000000xxxxx
para 26-56 y finalmente000000000000000xxx
por 57-62.Ejemplos
Hice una idea general de algunas posiciones codificadas con esta codificación, y anoté la de la posición inicial con algunos comentarios.
No sé cómo analizar el tamaño de bits en el peor de los casos, pero siguiendo los ejemplos en la esencia, creo que el algoritmo debería ser algo eficiente al menos.
Implementación de decodificador
A continuación se muestra un decodificador rápido y sucio para esta codificación (tomando como entrada los datos binarios codificados en el texto, como en el ejemplo anotado anteriormente, y omitiendo cosas que no son '0' o '1'). Produce un tablero de ajedrez unicode para stdout.
fuente
Máx .: 184 bits, Mín .: 75 bits
Me inspiró la codificación Huffman de @ AdamSpeight para piezas para intentar crear mi propio esquema. Dudo que esto gane, pero tiene límites calculables.
Este esquema trata las piezas de ajedrez como si hubiera 11 tipos diferentes de piezas. Seguí aproximadamente el algoritmo de codificación de Huffman para agrupar estas clases por sus frecuencias y tipos reales para generar las siguientes codificaciones:
El código de cada pieza puede estar precedido por dos bits para mostrar a qué equipo pertenece (
10
para Blanco,11
para Negro).0
se puede usar para codificar espacios vacíos. Estas ideas nos permiten construir una codificación cuadrado por cuadrado para toda la placa utilizando el procedimiento que queramos. Asumiré el orden de iteracióna1, b1, c1, ... f8, g8, h8
. Esto significa que solo enumerar estos códigos como se muestra arriba codifica toda la información, excepto de quién es el turno. Un motor de ajedrez muy simple puede usar las "clases" para los peones, torres y reyes para determinar si el enroque y el pase son legales. Además, este esquema maneja fácilmente las promociones de peones. Si un jugador promueve un peón a una torre, se pueden usar los códigos del lado del rey o la reina siempre que se elija la variante "movida".A excepción de las posiciones patológicas que no creo que puedan suceder, el peor de los casos para esta codificación es cuando todas las piezas aún están en el tablero y el jugador anterior movió un peón dos espacios hacia adelante. Como ejemplo, la tabla a continuación codifica
1. e4
:Esto significa que la codificación en el peor de los casos tiene 184 bits: 1 para indicar el jugador, 32 para los espacios vacíos, 45 para los peones no movidos, 6 para el peón de salto de dos espacios, 24 para los caballeros, 24 para los obispos, 28 para las torres, 12 para las reinas y 12 para los reyes.
A medida que las piezas se mueven y se capturan, el tamaño de la codificación disminuirá. El mejor de los casos está representado por dos reyes solos en el tablero: 1 bit para indicar al jugador + 62 bits para indicar los cuadrados vacíos + 12 bits para indicar que los reyes dan una longitud mínima de 75 bits.
Volveré y editaré esta respuesta con algún código que demuestre esta codificación en acción más tarde hoy o mañana. Por ahora, tengo curiosidad por ver lo que otras personas piensan de esta codificación.
fuente
11001
significaB'S MOVE
W CAN KSC
W CANT QSC
B CANT KSC
B CAN QSC
). Eso es 4 bits en lugar de los 5 bits por lado en su codificación, o 3 bits por lado si elimina el marcador lateral en las torres. (KSC
= Castillo del lado del rey.QSC
= Castillo del lado de la reina)184 bits = 23 bytes en el peor de los casos, y no demasiado complicado:
A. Qué cuadrados ocuparon: 64 bits = 8 bytes B. Qué colores para los <= 32 cuadrados ocupados: 32 bits = 4 bytes Y ahora usando solo los <= 30 cuadrados ocupados por no reyes: B. use PNBRQ codificado en radix 5, para 5 ^ 30 posibilidades; y 32 * 31 * 2 * 4 * 4 * 9 para posiciones de rey, color de movimiento, derechos de enroque en blanco y negro, cuadrado pasajero (entre 8 posibilidades más ninguna, un noveno); este número 5 ^ 30 * 32 * 31 * 2 * 4 * 4 * 9 = 266075134277343750000000000 = 2 ^ 87.782 cabe en 88 bits para un total de 64 + 32 + 88 = 184 bits para toda la codificación.
Esto se puede reducir, por ejemplo, 32 * 31 * 2 * 4 * 4 * 9 = 285696 se puede reducir a 2 * (32 * 31 + 31 * 3 + 31 * 3 + 3 * 3) * 6 = 14244, utilizando a lo sumo 6 víctimas-candidatos pasantes (incluido ninguno), y codificar los derechos de enroque y las posiciones de rey dentro del mismo conjunto utilizando los derechos de enrutamiento de hecho solo importan cuando el rey está en la casilla inicial. Esto ahorra 4 bits.
Tengo razones para creer que no es posible alcanzar 18 bytes, es decir, el número total de posiciones de ajedrez legales supera los 2 ^ 144.
Su esquema de 160 bits es muy ingenioso, pero creo que debe darse como programas de codificación / decodificación antes de tener plena confianza en él.
fuente
171 bits peor de los casos:
He combinado un par de ideas, así como algunos de mis propios pensamientos.
Vamos a comenzar con una placa de 64 bits. Cada bit representa un espacio ocupado en el tablero. Se llenan a lo largo de las filas. Entonces el comienzo se ve así:
1111 1111 1111 1111 0000 0000 0000 0000 0000 0000 0000 0000 1111 1111 1111 1111
Ahora, cada pieza estará representada por 4 bits. 1 ° bit: color (
0=white, 1=black
) 2 °-4 ° bits: uno de los 8 tipos.Al final incluiremos un poco para designar el turno.
0=white, 1=black
.4 bits * 32 piezas = 128 bits y ya tengo 64 + 1 de turno y tablero. Eso da un total de 128 + 64 + 1 = 193 que ni siquiera he comenzado con passant o castling. Muy por encima de mi límite sin nada, ni siquiera giros. Aquí es donde comienzan los trucos.
Bien, ¿ves esos tipos arriba? Bishop0 y Bishop1? Peón0 y peón1? Esos tipos se designan así, porque nos dicen un poco para insertar después de esta pieza. Entonces Bishop0 significa que después de eso, habrá un 0, es decir, que la siguiente pieza es blanca. Bishop1 nos dice que la siguiente pieza es negra, y el peón0 y el peón1 funcionan igual. (Si esta pieza es la última pieza que se enumera, entonces nos informa sobre el próximo turno).
Mi peor caso involucra todas las piezas en el tablero, así que con 16 peones y 4 obispos, esto me ahorra 20 bits. Estoy abajo a 173.
Bueno. Por otro lado, en mi peor caso, una vez que hay 16 de un color codificado, dejamos de codificar el color, tal como lo conocemos en adelante. Mi peor caso ahora involucra una pieza blanca que llega a la esquina más alejada sin capturas. Ahí solo guardo un poco. 172)
Ahora voy a cambiar el orden en que nombro las piezas. Los nombraremos a lo largo de las columnas comenzando en el exterior. El tablero nombrado al principio seguirá siendo el mismo, pero cuando coloco piezas en él, comienzo desde los blancos de abajo a la derecha, y subo esa columna. Luego salto a la parte inferior derecha del negro y subo esa columna. Salto a la celda desconocida inferior derecha del blanco, y así sucesivamente, esto significa que mi peor caso es nuevamente el comienzo. Mi razón tiene que ver con mi truco pasajero, los siguientes dos bits que pierdo y el enroque.
Ahora, para que un peón sea promovido (como se ha discutido extensamente) se debe capturar una pieza. Por lo tanto, cuando sabemos que hay 32 piezas, solo necesitamos denotar 31 de ellas. La última pieza se identifica de forma única. Como resultado, para mí, esto solo ahorra 2 bits, porque mi última pieza podría ser un peón / alfil (que normalmente me cuesta 3 bits porque guardo uno en la siguiente pieza), cuyo color ya está determinado y solo lo fue 2 bits Estoy a 170 bits.
Cuando los peones son promovidos, simplemente cambian su tipo. Por cada pieza que sale del tablero me libero de (mínimo) 3 bits, y dos promociones de peón me cuestan 2 bits, por lo que estoy disminuyendo (lentamente) en las promociones.
Enroque. Para que ocurra el enroque, ni el rey ni la torre relevante pueden haberse movido. Por lo tanto, cuando una torre es capaz de enrocarse, tanto él como el rey estarán en sus lugares originales. Entonces, las torres capaces de enrocarse aparecerán en el mismo lugar que los reyes de ese color. Como esto es ilegal (dos reyes o tres reyes del mismo color en el tablero) y solo puede suceder en tres configuraciones posibles para cada color (izquierda, derecha, ambas torres se enumeran como reyes): la decodificación es completamente posible. Entonces, para ningún bit hemos codificado el enroque.
De paso Aquí también usaremos posiciones ilegales. Solo un peón puede estar en peligro de pasarse a la vez. Debe estar en su cuarta fila. El peón que sea vulnerable será 'volteado' a su fila de inicio, cambiado con lo que esté allí. Como ese peón está en su propia primera fila, una posición ilegal, la situación será obvia para el decodificador, revertirá las posiciones y marcará el peón como vulnerable al paso.
Necesitábamos manipular el pedido porque la última pieza tiene que ser 'identificada de manera única'. En un orden estándar, no podríamos saber si la torre en la esquina trasera podría enrocarse, eso no se sabe. Cuando trabajamos desde afuera hacia adentro, garantizamos que donde sea que esa torre esté 'listada', ya sea en su propia esquina, o en el medio del tablero porque se cambió con un peón vulnerable al paso, habrá una pieza listada después es así que nos dicen el tipo de torre. Sabemos que habrá una pieza después porque, para que un peón sea vulnerable, debe haber un peón en su interior (que se codificará más adelante según las instrucciones anteriores).
Ah, y para ayudar a asegurarnos de que el peor de los casos involucra a todas las piezas en el tablero, una vez que tengamos menos de 32 piezas, podemos usar el tablero de 64 bits para identificar las posiciones de turno y ocupadas usando 0 para representar piezas cuando el blanco gire y 1 cuando sea negro gire.
Así que nos pusimos en marcha y enrocamos gratis. Recogimos la última pieza gratis, aunque tomó un poco de tiempo para que la jugada fuera agradable con las reglas pasantes y de enroque. Eliminamos 20 bits en las piezas estándar. Creo que el peor de los casos aquí involucra un peón blanco midde movido hacia adelante y una pieza negra entre él y su reina mientras todas las piezas están en el tablero. Comprobación rápida doble: se captura la primera pieza: llámelo un peón, a 3 bits del tablero en el peón, 3 bits en el tablero en forma de una última pieza, un bit en el marcador de turno que desaparece. Promueve dos peones de 2 bits en el tablero. Ah maldición, estoy en 171.
EDITAR He agregado código para un decodificador (¿funciona?) - en R - a continuación. Toma vectores de booleanos como entrada - (lo siento, no soy capaz de codificar bien nada que me permita usar los bits) También he incluido la posición de inicio.
Este código construye 4 funciones. Uno que hace una separación básica de las piezas y la estructura del tablero, así como averiguar el tipo de pieza y cualquier pieza 'implícita'. La siguiente función completa la estructura del tablero con esas piezas en un orden ligeramente extraño (y diferente al de mi algoritmo inicial) [explicado en los comentarios del código]. La siguiente función toma el tablero lleno y detecta cualquier posición ilegal; luego las repara y cambia el nombre de los peones que son vulnerables a pasar "x peón-e" y cualquier torre que pueda formar "x rook-c". La función final es un contenedor que ejecuta esas funciones en orden y proporciona una salida que es la placa actual, así como el turno.
También he incluido la codificación de la posición de inicio (aunque para verla tendrás que llamar
c(startboard,newpieces)
y el código llama a la función de contenedor en esa posición.fuente
229/226 bits
Esto no resulta ser muy exitoso, pero podría salvar a otras personas por el mismo camino.
La versión simple:
1
poco para quién es el turno4
bits para las cuatro posibilidades de enroque3
bits para las posibilidades pasantes . Esto tiene más profundidad que al principio entendí. En passant debe hacerlo un peón que se mueva del mismo rango (fila) que el peón que se captura. El análisis de casos indica que una vez que sepamos cuántos peones del color que se movieron por última vez han avanzado exactamente dos cuadrados, habrá a lo sumo 6 casos en passant (incluido el caso de que no haya peón vulnerable a passant ). El peor de los casos son 5 peones (potencialmente todos vulnerables: p. Ej.PpPPpPPp
tiene cinco vulnerablesP
). Con 6 peones hay como máximo 2 peones enemigos en el mismo rango, cada uno de los cuales puede amenazar a lo sumo 2 peones al pasar . Por lo tanto, necesitamosceil(lg 6) = 3
bits aquí.Luego el tablero. El tablero tiene 64 cuadrados, por lo que un índice cuadrado puede codificarse en 6 bits. Enumeramos a los hombres por rango, alternando colores, comenzando con el rey.
6
bits: posición del rey blanco. (Garantizado para estar en el tablero).6
bits: posición del rey negro. (Garantizado para estar en el tablero. En el peor de los casos en que el rey blanco está en una esquina, hay 60 lugares posibles en los que podría estar; en el mejor de los casos en que el blanco no está en un borde, hay 55).6
bits: posición de la reina blanca. Si no hay una reina blanca, repite la posición del rey blanco como una señal.1
bit seguido de 6 bits para la posición.0
poco0
bit final .Esto cuesta ciertos
12
bits para los reyes y2*7*5-1 = 69
bits para los otros hombres. En el peor de los casos en que los 32 hombres están en el tablero, cuesta7
un poco para cada hombre que no sean los reyes, para un total de12 + 7*30 - 1 = 221 bits
. Entonces, con los8
bits iniciales para el estado global tenemos 229 bits .La versión avanzada:
Mediante el uso de la codificación aritmética podemos operar en
lg num_possibilities
lugar deceil(lg num_possibilities)
y simplemente tomar unoceil
al final.1
poco para quién es el turno4
bits para las cuatro posibilidades de enroquelg 6
bits para las posibilidades pasantes .6
pedacitos para el rey blancolg 60
bits (peor caso) para el rey negrolg 63
bits (porque no quiero complicarlo al nivel de mirar cheques) para la reina blanca, usando la posición del rey blanco si no hay ninguno1
poco seguido delg 62
,lg 61
, etc. bits para su posición.0
pocolg 63
bits (o menos, si hubiera reinas blancas) para la reina negra.El enésimo hombre que está realmente presente tiene
66-n
valores posibles. Si falta un tipo para un color, gastamos66-#men so far
bits en grabar eso (más un bit para el separador). Los casos extremos son:5+lg 6
en estado global,6+lg 60
en reyes,29
en bits separadores ySUM_{n=32}^{63} lg n
bits en posiciones. Gran total:ceil(225.82)
bits. Decepcionante.5+lg 6
en el estado global,6+lg 60
en los reyes,29
en los bits separadores,8*lg 63
diciendo que no hay otras piezas, ySUM_{n=48}^{63} lg n
en las posiciones de los peones. Gran total:ceil(188.94)
bits. Mejor: al guardar la segunda torre, caballero y alfil para cada lado, hemos avanzado un poco.Entonces, el peor de los casos parece ser 226 bits , para un ahorro miserable de 3.
Definitivamente podemos mejorar en el caso promedio al codificar los peones antes que las piezas, ya que están restringidos a 48 cuadrados en lugar de los 64 completos. Sin embargo, en el peor de los casos, todos los hombres están en el tablero y todos los peones han sido promovidos, creo esto terminaría costando 2 bits más porque necesitaríamos una bandera de "no peones" en lugar de poder contar a los hombres.
fuente
Este es un tema de discusión en los círculos de ajedrez.
Aquí hay una prueba muy simple con 164 bits https://groups.google.com/forum/#!topic/rec.games.chess.computer/vmvI0ePH2kI 155 se muestra aquí http://homepages.cwi.nl/~tromp /chess/chess.html
Estrategia sobre simplificada:
fuente
Min: 0 bits
Max:
1734243 bits (4.3354.401 bits / tablero amortizado)Esperado:
351177 bits (4.3764.430 bits / tablero amortizado)Como puedo determinar la entrada y la salida que quiera, decidí seguir codificando la historia del juego hasta este momento. Una ventaja es que la información adicional de quién es el turno, pasa y quién tiene la capacidad de atacar dónde se puede derivar y no codificar.
Intento 1:
Ingenuamente pensé que puedo codificar cada movimiento en 12 bits, 4 tripletas de la forma (inicio x, inicio y, final x, final y) donde cada uno es de 3 bits.
Asumiríamos la posición inicial y moveríamos las piezas desde allí con las blancas primero. El tablero está dispuesto de tal manera que (0, 0) es la esquina inferior izquierda del blanco.
Por ejemplo el juego:
Sería codificado como:
Esto lleva a una codificación de 12 m bits, donde m es el número de movimientos realizados
Por un lado, esto podría ser realmente grande, por otro lado, puede considerar que cada movimiento es su propio juego, por lo que cada codificación realmente codifica m "tableros de ajedrez". Si amortizaste esto, obtienes que cada "tablero de ajedrez" es de 12 bits. Pero siento que esto es un poco trampa ...
Intento 2:
Me di cuenta de que cada movimiento en el intento anterior codifica muchos movimientos ilegales. Así que decidí codificar solo movimientos legales. Enumeramos posibles movimientos de la siguiente manera, numera cada cuadrado de manera que (0, 0) → 0, (1, 0) → 1, (x, y) → x + 8 y. Itere a través de las fichas y compruebe si hay una pieza y si puede moverse. Si es así, agregue las posiciones a las que puede ir a una lista. Elija el índice de la lista que es el movimiento que desea hacer. Agregue ese número al total acumulado de movimientos ponderados por 1 más el número de movimientos posibles.
Ejemplo como el anterior: desde la posición inicial, la primera pieza que puede moverse es el caballero en el cuadrado 1, puede moverse al cuadrado 16 o 18, así que agréguelos a la lista
[(1,16),(1,18)]
. El siguiente es el caballero en el cuadrado 6, agregue sus movimientos. En general obtenemos:[(1,16),(1,18),(6,21),(6,23),(8,16),(8,24),(9,17),(9,25),(10,18),(10,26),(11,19),(11,27),(12,20),(12,28),(13,21),(13,29),(14,22),(14,30),(15,23),(15,31)]
Como queremos el movimiento (12, 28), codificamos esto como 13 en la base 20, ya que hay 20 movimientos posibles.
Entonces ahora tenemos el número de juego g 0 = 13
A continuación, hacemos lo mismo para el negro, excepto que numeramos las fichas al revés (para que sea más fácil, no obligatorio) obtener la lista de movimientos:
[(1,16),(1,18),(6,21),(6,23),(8,16),(8,24),(9,17),(9,25),(10,18),(10,26),(11,19),(11,27),(12,20),(12,28),(13,21),(13,29),(14,22),(14,30),(15,23),(15,31)]
Como queremos el movimiento (11, 27), codificamos esto como 11 en la base 20, ya que hay 20 movimientos posibles.
Entonces ahora obtenemos el número de juego g 1 = (11 ⋅ 20) + 13 = 233
A continuación obtenemos la siguiente lista de movimientos para las blancas:
[(1,16),(1,18),(3,12),(3,21),(3,30),(3,39),(4,12),(5,12),(5,19),(5,26),(5,33),(5,40),(6,12),(6,21),(6,23),(8,16),(8,24),(9,17),(9,25),(10,18),(10,26),(11,19),(11,27)(13,21),(13,29),(14,22),(14,30),(15,23),(15,31)]
Como queremos el movimiento (6, 21), codificamos esto como 13 en la base 29 ya que hay 29 movimientos posibles.
Entonces ahora obtenemos el número de juego g 2 = ((13 ⋅ 20) + 11) 20 + 13 = 5433
A continuación obtenemos la siguiente lista de movimientos para las negras:
[(1,11),(1,16),(1,18),(2,11),(2,20),(2,29),(2,38),(2,47),(3,11),(4,11),(4,18),(4,25),(4,32),(6,21),(6,23),(8,16),(8,24),(9,17),(9,25),(10,18),(10,26),(12,20),(12,28),(13,21),(13,29),(14,22),(14,30),(15,23),(15,31)]
Como queremos el movimiento $ (10, 18) $ (10, 18)
Entonces ahora obtenemos el número de juego g 3 = (((19 ⋅ 29 + 13) 20) + 11) 20 + 13 = 225833
Y continúe este proceso para todos los movimientos restantes. Puedes pensar en g como la función g (x, y, z) = x y + z. Así g 0 = g (1, 1, 13), g 1 = g (g (1, 1, 11), 20, 13), g 2 = g (g (g (1, 1, 13), 20, 11), 20, 13), g 3 = g (g (g (g (1, 1, 19), 29, 13), 20, 11), 20, 13)
Para decodificar un número de juego g 0 , comenzamos en la posición inicial y enumeramos todos los movimientos posibles. Luego calculamos g 1 = g 0 // l , m 0 = g 0 % l , donde l es el número de movimientos posibles, '//' es el operador de división entera y '%' es el operador de módulo. Debe sostener que g 0 = g 1 + m 0 . Luego hacemos el movimiento m 0 y repetimos.
Del ejemplo anterior si g 0 = 225833, entonces g 1 = 225833 // 20 = 11291 ym 0 = 225833% 20 = 13. A continuación g 2 = 11291 // 20 = 564 ym 1 = 11291% 20 = 11. Luego g 3 = 11291 // 20 = 564 y m 2 = 11291% 20 = 11. Por lo tanto, g 4 = 564 // 29 = 19 y_m_ 3 = 564% 29 = 13. Finalmente g 5 = 19 // 29 = 0 ym 4 = 19% 29 = 19.
Entonces, ¿cuántos bits se usan para codificar un juego de esta manera?
Por simplicidad, digamos que siempre hay 20 movimientos cada turno y para el peor de los casos siempre elegimos el más grande, 19. El número que obtendremos es 19 ⋅ 20 m
+ 19 ⋅ 20 m-1 + 19 ⋅ 20 m-2 + ⋯ + 19 ⋅ 20 + 19 = 20 m + 1 - 1 donde _m es el número de movimientos. Para codificar 20 m + 1 - 1 necesitamos aproximadamente log 2 (20 m + 1 ) bits, que es aproximadamente (m + 1) ∗ log 2 (20) = 4.3219 ∗ (m + 1)
En promedio m = 80 (40 movimientos por jugador), por lo que se necesitarían 351 bits para codificar. Si estuviéramos grabando muchos juegos necesitaríamos una codificación universal ya que no sabemos cuántos bits necesitará cada número
El peor de los casos cuando m = 400 (200 movimientos por jugador), por lo que se necesitarían 1734 bits para codificar.
Tenga en cuenta que la posición que queremos codificar nos debe ser dada a través del camino más corto para llegar siguiendo las reglas. Por ejemplo, el juego teorizado aquí no necesita m = 11741 para codificar la posición final. En su lugar, ejecutamos una búsqueda Breadth-First para encontrar la ruta más corta a esa posición y codificarla en su lugar. No sé qué tan profundo tendríamos que llegar para enumerar todas las posiciones de ajedrez, pero sospecho que 400 es una sobreestimación.
Cálculo rápido
Hay 12 piezas únicas o el cuadrado puede estar vacío, por lo que colocarlas en un tablero de ajedrez es 13 64 . Esta es una gran sobreestimación ya que incluye muchas posiciones inválidas. Cuando estamos m se mueve en el juego que hemos creado unos 20 m posiciones. Entonces estamos buscando cuando 20 m = 13 64 . Registre ambos lados para obtener m = 64 * log 20 (13) = 54.797. Esto muestra que deberíamos poder llegar a cualquier posición en 55 movimientos.
Ahora que calculé que el peor de los casos sería m = 55 no m = 400, editaré mis resultados. Para codificar una posición donde m = 55 toma 243 bits. También voy a decir que el caso promedio es de alrededor de m = 40, que toma 177 bits para codificar.
Si utilizamos el argumento de amortización de antes, estamos codificando 400 "tableros de ajedrez" en 1734 bits, de modo que obtenemos que cada "tablero de ajedrez" ocupa 4.335 bits en el peor de los casos.
Tenga en cuenta que g = 0 denota un juego válido, aquel en el que la pieza en el cuadrado más bajo se mueve al cuadrado más bajo que puede.
Notas adicionales:
Si desea referirse a una posición específica en el juego, es posible que deba codificar el índice. Esto se puede agregar manualmente, por ejemplo, concatenar el índice al juego, o agregar un movimiento "final" adicional como el último movimiento posible en cada turno. Esto ahora puede dar cuenta de los jugadores que conceden, o 2 seguidos para denotar que los jugadores aceptaron un empate. Esto solo es necesario si el juego no terminó en jaque mate o estancado según la posición, en este caso está implícito. En este caso, lleva el número de bits necesarios en promedio a 356 y, en el peor de los casos, a 1762.
fuente