Juego octal

Los juegos octales son una clase de juegos para dos jugadores que implican quitar fichas (piezas de juego o piedras) de montones de fichas. Se han estudiado en la teoría de juegos combinatorios como una generalización de Nim, Kayles y juegos similares.​​

Los juegos octales son imparciales, lo que significa que todos los movimientos disponibles para un jugador también están disponibles para el otro jugador. Se diferencian entre sí en la cantidad de tokens que se pueden eliminar en un solo movimiento y (dependiendo de este número) si se permite eliminar un montón completo, reducir el tamaño de un montón o dividir un montón en dos montones. Estas variaciones de las reglas se pueden describir de forma compacta mediante un sistema de codificación que utiliza números octales.

Especificación del juego

Un juego octal se juega con fichas divididas en montones. Dos jugadores se turnan para moverse hasta que no es posible realizar ningún movimiento. Cada movimiento consiste en seleccionar solo uno de los montones, y

• eliminar todos los tokens del montón, sin dejar ningún montón,
• eliminando algunos pero no todos los tokens, dejando un montón más pequeño, o
• quitando algunas de las fichas y dividiendo las fichas restantes en dos montones no vacíos.

Los montones distintos del montón seleccionado permanecen sin cambios. El último jugador en moverse gana en el juego normal. El juego también se puede jugar en juego misère, en el que el último jugador en mover pierde.

Los juegos que se juegan con montones de esta manera, en los que los movimientos permitidos para cada montón están determinados por el tamaño del montón original, se denominan juegos de tomar y romper en la literatura.​ Los juegos octales son un subconjunto de los juegos de tomar y romper en los que los movimientos permitidos están determinados por la cantidad de fichas que se eliminan del montón.

El código octal de un juego se especifica como

0 . d₁ d₂ d₃ d₄ …,

donde el dígito octal d_n especifica si el jugador puede dejar cero, uno o dos montones después de eliminar n tokens de un montón. El dígito d_n es la suma de

• 1 si se permite dejar cero montones, 0 en caso contrario;
• 2 si se permite dejar un montón, 0 en caso contrario; y
• 4 si se permite dejar dos montones, 0 en caso contrario.

Los tokens cero no se cuentan como un montón. Por lo tanto, el dígito d_n es impar si un montón de n tokens puede eliminarse por completo, e incluso de lo contrario. La especificación de los resultados de un montón en d_n aplica a la eliminación de n tokens de un montón de más de n . Los resultados de dos montones en d_n se aplican a eliminar n tokens de un montón de al menos n +2 y separar el resto en dos montones no vacíos.

Los juegos octales pueden permitir dividir un montón en dos partes sin quitar ninguna ficha, mediante el uso del dígito 4 a la izquierda del punto decimal. Esto es similar al movimiento en el juego de Grundy, que consiste en dividir un montón en dos partes desiguales. La notación de juego octal estándar, sin embargo, no tiene el poder de expresar la restricción de partes desiguales.

Los juegos octales con solo un número finito de dígitos distintos de cero se denominan juegos octales finitos.

Partidos octales particulares

Nim

El juego más fundamental en la teoría de juegos combinatorios es Nim, en el que se puede eliminar cualquier número de fichas de un montón, dejando cero o uno. El código octal para Nim es 0.333… , apareciendo en la literatura publicada como

$0.{\dot {3}}$,

para indicar la parte repetida como un decimal periódico. Sin embargo, la parte repetida no juega el mismo papel que en las fracciones octales, ya que los juegos

$0.0{\dot {7}}$

y

$0.1$

no son idénticos, a pesar de su igualdad como fracciones octales.

Kayles

El juego Kayles generalmente se visualiza como jugado con una fila de n pines, pero puede ser modelado por un montón de n contadores. A uno se le permite eliminar uno o dos tokens de un montón y organizar el resto en cero, uno o dos montones. El código octal de Kayles es 0,77.

Ajedrez de Dawson

El ajedrez de Dawson es un juego que surge de un rompecabezas de ajedrez planteado por Thomas Rayner Dawson en Caissa's Wild Roses, 1938.​ El rompecabezas se planteó como si tuviera filas opuestas de peones separados por una sola fila. Aunque el acertijo no se plantea como un juego imparcial, la suposición de que las capturas son obligatorias implica que el hecho de que un jugador se mueva en cualquier archivo solo da como resultado la eliminación de ese archivo y sus vecinos (si los hay) de una consideración adicional, con el jugador opuesto para mover. Modelando esto como un montón de n fichas, un jugador puede eliminar un montón completo de una, dos o tres fichas, puede reducir cualquier pila en dos o tres fichas, o puede dividir una pila en dos partes después de quitar tres fichas. El ajedrez de Dawson está representado por el código octal 0.137.

Kayles de Dawson

En el juego 0.07, llamado Kayles de Dawson, un movimiento consiste en quitar exactamente dos fichas de un montón y distribuir el resto en cero, uno o dos montones. El Kayles de Dawson se llama así por su similitud (no obvia) con el Ajedrez de Dawson, ya que el montón de n +1 fichas de Kayles de Dawson actúa exactamente como el montón de n fichas de Ajedrez de Dawson. Se dice que Kayles de Dawson es primo hermano del Ajedrez de Dawson.

Generalización a otras bases

Los juegos octales como Nim, en los que cada movimiento transforma un montón en cero o uno montones, se denominan juegos cuaternarios porque los únicos dígitos que aparecen son 0, 1, 2 y 3. La notación octal también puede extenderse para incluir juegos hexadecimales, en el que los dígitos permiten la división de un montón en tres partes. De hecho, son posibles bases arbitrariamente grandes. El análisis de juegos cuaternarios, octales y hexadecimales muestra que estas clases de juegos son marcadamente diferentes entre sí,​ y el comportamiento de bases más grandes no ha recibido tanto escrutinio.

Secuencia nim

El teorema de Sprague-Grundy implica que un montón de tamaño n es equivalente a un montón nim de un tamaño dado, generalmente denominado G (n). El análisis de un juego octal consiste entonces en encontrar la secuencia de los valores nim para montones de tamaño creciente. Esta secuencia G(0), G(1), G(2)... generalmente se llama la secuencia nim del juego.

Todos los juegos octales finitos analizados hasta ahora han mostrado una secuencia nim en última instancia periódica, y si todos los juegos octales finitos son finalmente periódicos es una cuestión abierta. Está catalogado por Richard Guy como un problema importante en el campo de los juegos combinatorios.​

Registros de computación

Un análisis completo de un juego octal da como resultado encontrar su período y preperíodo de su secuencia nim. En Winning Ways for your Mathematical Plays se muestra que solo se necesita un número finito de valores de la secuencia nim para demostrar que un juego octal finito es periódico, lo que abrió la puerta a los cálculos con computadoras.

Los juegos octales con un máximo de 3 dígitos octales se han analizado a lo largo de los años. Hay 79 juegos octales no triviales, entre los que se han resuelto 14:

• .156 por Jack Kenyon en 1967​
• .356, .055, .644 y .165 por Richard Austin en 1976​
• .16, .56, .127 y .376 por Anil Gangolli y Thane Plambeck en 1989​
• .454, .104, .106, .054 y .354 por Achim Flammenkamp entre 2000 y 2002​

Quedan 63 de estos juegos, a pesar del cálculo de millones de valores nim por Achim Flammenkamp.​

Referencias

• Datos: Q3177938