Los juegos octales son una clase de juegos para dos jugadores que implican retirar 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. [1] [2]
Los juegos octales son imparciales, lo que significa que cada movimiento disponible para un jugador también lo es para el otro jugador. Se diferencian entre sí en la cantidad de fichas que se pueden quitar en un solo movimiento y (según esta cantidad) en si se permite quitar un montón entero, reducir el tamaño de un montón o dividir un montón en dos montones. Estas variaciones de reglas se pueden describir de forma compacta mediante un sistema de codificación que utiliza números octales .
Se juega un juego octal con fichas divididas en montones. Dos jugadores se turnan para mover hasta que no sea posible ningún movimiento. Cada movimiento consiste en seleccionar solo uno de los montones y elegir uno de ellos.
Los montones que no sean el montón seleccionado permanecen inalterados. El último jugador en mover gana en el juego normal . El juego también se puede jugar en modo misère play , en el que pierde el último jugador en mover.
Los juegos jugados 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. [1] 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 retiradas del montón.
El código octal de un juego se especifica como
donde el dígito octal d n especifica si el jugador puede dejar cero, uno o dos montones después de retirar n fichas de un montón. El dígito d n es la suma de
Los tokens cero no se cuentan como un montón. Por lo tanto, el dígito d n es impar si se puede eliminar por completo un montón de n tokens, y par en caso contrario. La especificación de un montón que da como resultado d n se aplica a la eliminación de n tokens de un montón de más de n . Los resultados de dos montones que dan como resultado d n se aplican a la eliminación de n tokens de un montón de al menos n +2 y a la separación del 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. Sin embargo, la notación de juegos octales estándar no tiene el poder de expresar la restricción de partes desiguales.
Los juegos octales con sólo un número finito de dígitos distintos de cero se denominan juegos octales finitos .
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 un montón atrás. El código octal para Nim es 0,333… y aparece en la literatura publicada como
para indicar la parte repetida como en un decimal periódico . Sin embargo, es importante darse cuenta de que la parte repetida no juega el mismo papel que en las fracciones octales, ya que los juegos
y
no son idénticas, a pesar de su igualdad como fracciones octales.
El juego Kayles se suele visualizar como un juego en el que se juega con una fila de n bolos, pero se puede representar con un montón de n fichas. Se permite retirar una o dos fichas de un montón y organizar el resto en cero, uno o dos montones. El código octal de Kayles es 0,77 .
El ajedrez de Dawson es un juego que surge de un problema de ajedrez planteado por Thomas Rayner Dawson en Wild Roses de Caissa , 1938. [3] El problema se planteó como si involucrara filas opuestas de peones separados por una sola fila. Aunque el problema no se plantea como un juego imparcial , la suposición de que las capturas son obligatorias implica que el movimiento de un jugador en cualquier fila solo da como resultado la eliminación de esa fila y sus vecinas (si las hay) de una consideración posterior, y el jugador opuesto debe 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 montón en dos o tres fichas, o puede dividir un montón en dos partes después de eliminar tres fichas. El ajedrez de Dawson se representa así con el código octal 0.137 .
En el juego 0.07 , llamado Dawson's Kayles , un movimiento consiste en retirar exactamente dos fichas de un montón y distribuir el resto en cero, uno o dos montones. Dawson's Kayles recibe su nombre por su similitud (no obvia) con Dawson's Chess, en el sentido de que un montón de Dawson's Kayles de n +1 fichas actúa exactamente como un montón de Dawson's Chess de n fichas. Se dice que Dawson's Kayles es un primo hermano de Dawson's Chess.
Los juegos octales como Nim , en los que cada movimiento transforma un montón en cero o un montón, se denominan juegos cuaternarios porque los únicos dígitos que aparecen son 0, 1, 2 y 3. La notación octal también se puede ampliar para incluir juegos hexadecimales , en los 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 los juegos cuaternarios, octales y hexadecimales muestra que estas clases de juegos son marcadamente diferentes entre sí, [1] y el comportamiento de las bases más grandes no ha recibido tanto escrutinio.
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, normalmente denominado G(n). El análisis de un juego octal consiste entonces en hallar la secuencia de los valores nim para montones de tamaño creciente. Esta secuencia G(0), G(1), G(2) ... se denomina normalmente 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 en última instancia periódicos es una pregunta abierta. Richard Guy lo menciona como un problema importante en el campo de los juegos combinatorios . [4]
Un análisis completo de un juego octal da como resultado el hallazgo de 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.
A lo largo de los años se han analizado juegos octales con un máximo de 3 dígitos octales. Existen 79 juegos octales no triviales, de los cuales 14 han sido resueltos:
Aún quedan 63 de estos juegos, a pesar del cálculo de millones de valores nim realizado por Achim Flammenkamp. [5]
