Sapos y Ranas
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.
También se ha considerado una versión del juego de rompecabezas para un jugador.
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.
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.
representa una franja de cuatro cuadrados con un sapo en el primero y una rana en el último.
Esto significa que Izquierda puede mover un sapo un cuadrado a la derecha y Derecha puede mover una rana un cuadrado a la izquierda.
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,: 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.
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.
es un valor infinitesimal, para todos (a, b) excepto (3, 2) 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.
