El juego combinatorio Toads and Frogs es un juego de mesa 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 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. [1] Sin embargo, se sabe que el caso general de evaluación de una posición arbitraria es NP-hard. Hay algunas conjeturas abiertas sobre el valor de algunas posiciones notables.
También se ha considerado una versión del juego con formato rompecabezas para un solo jugador.
Toads and Frogs se juega en una franja de cuadrados de 1 × n . En cualquier momento, cada cuadrado está vacío u ocupado por un solo sapo o rana. Aunque el juego puede comenzar con cualquier configuración, es habitual comenzar con los sapos ocupando cuadrados consecutivos en el extremo más a la izquierda y las ranas ocupando cuadrados consecutivos en el extremo más a la derecha de la franja.
Cuando es el turno del jugador de la izquierda, puede mover un sapo una casilla hacia la derecha, hacia una casilla vacía, o hacer que un sapo "salte" dos casillas hacia la derecha, sobre una rana, hacia una casilla vacía. No se permiten saltos sobre una casilla vacía, un sapo o más de una casilla. Se aplican reglas análogas para el jugador de la derecha: en un turno, el jugador de la derecha puede mover una rana hacia la izquierda hacia un espacio vacío vecino, o hacer que una rana salte sobre un solo sapo hacia una casilla vacía 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.
Una posición de Sapos y Ranas puede representarse con una cadena de tres caracteres: para un sapo, para una rana y para un espacio vacío. Por ejemplo, la cadena representa una tira 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 recursivamente 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 a las posiciones , , ... y la derecha a las posiciones , , ..., entonces la posición se escribe convencionalmente
En esta notación, por ejemplo, . Esto significa que la izquierda puede mover un sapo una casilla hacia la derecha y la derecha puede mover una rana una casilla hacia la izquierda.
La mayor parte de la investigación en torno a Toads-and-Frogs se ha centrado en determinar los valores teóricos de juegos de algunas posiciones particulares de Toads-and-Frogs, o en determinar si pueden surgir algunos valores particulares en el juego.
Formas ganadoras para sus jugadas matemáticas mostraron primero numerosos valores posibles. Por ejemplo:
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 Toads-and-Frogs 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 dificultad del juego. [2]
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-hard. Doron Zeilberger y Thotsaporn Aek Thanatipanonda demostraron las conjeturas 1, 2 y 3 y encontraron un contraejemplo para la conjetura 4 en 2008. [4] La conjetura 5, la última aún abierta, establece que es un valor infinitesimal, para todos (a, b) excepto (3, 2).
Es posible que un juego de sapos y ranas termine antes de tiempo. Una versión de rompecabezas para un jugador del juego de sapos y ranas, publicada en 1883 por Édouard Lucas , pide una secuencia de movimientos que comienza en la posición inicial estándar y dura lo más posible, terminando con todos los sapos a la derecha y todas las ranas a la izquierda. No es necesario que los movimientos alternen entre sapos y ranas. [5]
