sapos y ranas

Juego combinatorio con piezas saltarinas.

Un ejemplo del juego combinatorio Toads And Frogs.

El juego combinatorio Toads and Frogs es un juego partidista inventado por Richard Guy . Este juego matemático se utilizó como juego introductorio en el libro Winning Ways for your Mathematical Plays . ^[1]

Conocido por su simplicidad y la elegancia de sus reglas, Toads-and-Frogs es útil para ilustrar los principales conceptos de la teoría de juegos combinatorios. En particular, no es difícil evaluar juegos simples que involucran sólo un sapo y una rana, construyendo el árbol de juego de la posición inicial. ^[1] Sin embargo, se sabe que el caso general de evaluación de una posición arbitraria es NP-duro. Hay algunas conjeturas abiertas sobre el valor de algunas posiciones notables.

También se ha considerado una versión del juego de rompecabezas para un jugador.

Normas

Toads and Frogs se juega en una  franja de cuadrados de 1 × n . En cualquier momento, cada casilla está vacía u ocupada por un solo sapo o rana. Aunque el juego puede comenzar con cualquier configuración, se acostumbra comenzar con sapos ocupando casillas consecutivas en el extremo izquierdo y ranas ocupando casillas consecutivas en el extremo derecho de la franja.

Cuando es el turno de movimiento del jugador de la izquierda, puede mover un sapo una casilla hacia la derecha, hacia una casilla vacía, o "saltar" un sapo dos casillas hacia la derecha, sobre una rana, hacia una casilla vacía. No se permiten saltos sobre un cuadrado vacío, un sapo o más de un cuadrado. Se aplican reglas análogas para la Derecha: en un turno, el jugador Derecha puede mover una rana hacia la izquierda a un espacio vacío vecino, o saltar una rana sobre un solo sapo a un cuadrado vacío inmediatamente a la izquierda del sapo. Según la regla de juego normal convencional de la teoría de juegos combinatorios, el primer jugador que no pueda moverse en su turno pierde.

Notación

Una posición de Sapos y Ranas se puede representar con una cadena de tres caracteres: para un sapo, para una rana y para un espacio vacío. Por ejemplo, la cuerda representa una tira de cuatro cuadrados con un sapo en el primero y una rana en el último. ${\displaystyle T}$ ${\displaystyle F}$ ${\displaystyle \square }$ ${\displaystyle T\square \square F}$

En la teoría de juegos combinatoria , una posición se puede describir recursivamente en términos de sus opciones, es decir, las posiciones a las que pueden moverse el jugador izquierdo y el jugador derecho. Si la Izquierda puede moverse de una posición a las posiciones , , ... y la Derecha a las posiciones , , ..., entonces la posición se escribe convencionalmente ${\displaystyle P}$ ${\displaystyle L_{1}}$ ${\displaystyle L_{2}}$ ${\displaystyle R_{1}}$ ${\displaystyle R_{2}}$ ${\displaystyle P}$ ${\displaystyle P=\{L_{1},L_{2},\dots |R_{1},R_{2},\dots \}.}$

En esta notación, por ejemplo, . Esto significa que la izquierda puede mover un sapo un cuadrado hacia la derecha y la derecha puede mover una rana un cuadrado hacia la izquierda. ${\displaystyle T\square \square F=\{\square T\square F|T\square F\square \}}$

Valores de la teoría de juegos

La mayor parte de la investigación sobre Toads-and-Frogs se ha centrado en determinar los valores de la teoría de juegos de algunas posiciones particulares de Toads-and-Frogs, o determinar si algunos valores particulares pueden surgir en el juego.

Las formas de ganar para tus jugadas matemáticas mostraron primero numerosos valores posibles. Por ejemplo, :

${\displaystyle T\square \square F=0}$

${\displaystyle TF\square \square =1}$

${\displaystyle T\square F\square ={\frac {1}{2}}}$

${\displaystyle TFT\square F=\{0|0\}=\star }$

${\displaystyle T\square TFF=\{0|\star \}=\uparrow }$

En 1996, Jeff Erickson demostró que para cualquier número racional diádico q (que son los únicos números que pueden surgir en juegos finitos), existe una posición de Sapos y Ranas con valor q. También encontró una fórmula explícita para algunas posiciones notables, como , y formuló seis conjeturas sobre los valores de otras posiciones y la dureza del juego. ^[2] ${\displaystyle T^{a}\square ^{b}F}$

Estas conjeturas impulsaron más investigaciones. Jesse Hull demostró la conjetura 6 en 2000, ^[3] que establece que determinar el valor de una posición arbitraria de Toads-and-Frogs es NP-difícil. Doron Zeilberger y Thotsaporn Aek Thanatipanonda demostraron las conjeturas 1, 2 y 3 y encontraron un contraejemplo a la conjetura 4 en 2008. ^[4] La conjetura 5, la última aún abierta, establece que es un valor infinitesimal, para todo (a, b ) excepto (3, 2). ${\displaystyle T^{a}\square ^{b}F^{a}}$

Rompecabezas para un jugador

Cronogramas de solución a los problemas de sapos y ranas para un jugador con 1, 2 y 3 de cada anfibio, con el eje vertical indicando el tiempo.

Es posible que un juego de Toads and Frogs termine antes de tiempo. Una versión de rompecabezas para un jugador del juego Toads and Frogs, publicada en 1883 por Édouard Lucas , solicita una secuencia de movimientos que comienza en la posición inicial estándar y dura el mayor tiempo posible, terminando con todos los sapos a la derecha y todos. de las ranas de la izquierda. No es necesario alternar los movimientos entre sapos y ranas. ^[5]

Referencias

1. Berlekamp, ​​Elwyn R .; Conway, John H .; Guy, Richard K. (2001), "Toads-and-Frogs", Winning Ways for your Mathematical Plays , vol. 1 (2ª ed.), AK Peters, págs. 12-13
2. Erickson, Jeff (1996), "Nuevos resultados de sapos y ranas", en Nowakowski, Richard J. (ed.), Games of No Chance, Publicaciones del Instituto de Investigación de Ciencias Matemáticas, vol. 29, Cambridge University Press, págs. 299–310
3. Como lo mencionan tanto Erickson en su sitio web como Thanatipanonda en su artículo.
4. Thanatipanonda, Thotsaporn (2011), "Más saltos con sapos y ranas", Electronic Journal of Combinatorics , 18 (1): P67:1–P67:12, arXiv : 0804.0640 , doi :10.37236/554, MR  2788684, S2CID  35020735
5. Levitin, Anany (2011). "Sapos y Ranas". Rompecabezas algorítmicos . Prensa de la Universidad de Oxford. pag. 53.