Sapos y Ranas

Un ejemplo del juego combinatorio Toads And Frogs.

Toads and Frogs (Sapos y Ranas) es un juego combinatorio y partisano inventado por Richard Guy. Este juego matemático se utilizó como juego introductorio en el libro Winning Ways for your Mathematical Plays.​

Conocido por su simplicidad y la elegancia de sus reglas, Toads-and-Frogs es útil para ilustrar los conceptos principales de la teoría de juegos combinatorios. En particular, no es difícil evaluar juegos simples que involucran solo un sapo y una rana, construyendo el árbol de juego de la posición inicial.​ Sin embargo, se sabe que el caso general de evaluar una posición arbitraria es NP-difícil. 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.

Reglas

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 en cualquier configuración, se acostumbra comenzar con sapos que ocupan cuadrados consecutivos en el extremo izquierdo y ranas que ocupan cuadrados consecutivos en el extremo derecho de la franja.

Cuando es el turno del jugador Izquierdo de moverse, puede mover un sapo un cuadrado a la derecha, a un cuadrado vacío, o "saltar" un sapo dos cuadrados a la derecha, sobre una rana, a un cuadrado vacío. 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 de la Derecha puede mover una rana a la izquierda a un espacio vacío vecino, o saltar una rana sobre un solo sapo en un cuadrado vacío inmediatamente a la izquierda del sapo. Según la regla de juego normal convencional para la teoría de juegos combinatorios, el primer jugador que no pueda moverse en su turno pierde.

Notación

Una posición de Toads-and-Frogs se puede representar con una cadena de tres caracteres: $T$ para un sapo, $F$ para una rana, y $\square$ por un espacio vacío. Por ejemplo, la cadena $T\square \square F$ representa una franja de cuatro cuadrados con un sapo en el primero y una rana en el último.

En la teoría de juegos combinatorios, una posición se puede describir de forma recursiva en términos de sus opciones, es decir, las posiciones a las que pueden moverse el jugador de la izquierda y el jugador de la derecha. Si la Izquierda puede moverse desde una posición $P$ a las posiciones $L_{1}$, $L_{2}$, ... y Derecha a las posiciones $R_{1}$, $R_{2}$, ..., entonces la posición $P$ está escrito convencionalmente $P=\{L_{1},L_{2},\dots |R_{1},R_{2},\dots \}.$

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

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 teóricos del juego de algunas posiciones particulares de Toads-and-Frogs, o determinar si algunos valores particulares pueden surgir en el juego.

Winning Ways for your Mathematical Plays mostró primero numerosos valores posibles. Por ejemplo,:

$T\square \square F=0$

$TF\square \square =1$

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

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

$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 Toads-and-Frogs con valor q. También encontró una fórmula explícita para algunas posiciones notables, como $T^{a}\square ^{b}F$, y formuló seis conjeturas sobre los valores de otras posiciones y la dureza del juego.​

Estas conjeturas impulsaron nuevas investigaciones. Jesse Hull demostró la conjetura 6 en 2000,​ 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 probaron las conjeturas 1, 2 y 3 y encontraron un contraejemplo de la conjetura 4 en 2008.​ La conjetura 5, la última aún abierta, establece que $T^{a}\square ^{b}F^{a}$ es un valor infinitesimal, para todos (a, b) excepto (3, 2)

Rompecabezas para un jugador

Es posible que una partida de Toads and Frogs termine antes. Una versión de rompecabezas para un jugador del juego Toads and Frogs, publicado en 1883 por Édouard Lucas, pide una secuencia de movimientos que comience en la posición inicial estándar que dure el mayor tiempo posible, terminando con todos los sapos a la derecha y todos de las ranas de la izquierda. Los movimientos no son necesarios para alternar entre sapos y ranas.​

Referencias

• Datos: Q7811378