Sapos y ranas
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 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 evaluar una posición arbitraria es NP-difícil. Hay algunas conjeturas abiertas sobre el valor de algunas posiciones notables.
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.
Una posición de Toads-and-Frogs 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 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 se puede mover desde una posición de las posiciones , , ... y derecho a las posiciones , , ..., entonces la posición se escribe convencionalmente
