Chomp es un juego de estrategia para dos jugadores que se juega en una cuadrícula rectangular formada por celdas cuadradas más pequeñas , que pueden considerarse como los bloques de una barra de chocolate . Los jugadores eligen por turnos un bloque y lo "comen" (lo retiran del tablero), junto con los que están debajo y a su derecha. El bloque superior izquierdo está "envenenado" y el jugador que se lo come pierde.
La formulación de barra de chocolate de Chomp se debe a David Gale , pero un juego equivalente expresado en términos de elección de divisores de un entero fijo fue publicado anteriormente por Frederik Schuh .
Chomp es un caso especial de un juego poset donde el conjunto parcialmente ordenado en el que se juega el juego es un producto de órdenes totales con el elemento mínimo (bloque venenoso) eliminado.
A continuación se muestra la secuencia de movimientos en un juego típico que comienza con una barra de 5 × 4:
El jugador A come dos bloques de la esquina inferior derecha; el jugador B come tres de la fila inferior; el jugador A elige el bloque a la derecha del bloque envenenado y come once bloques; el jugador B come tres bloques de la columna restante, dejando solo el bloque envenenado. El jugador A debe comerse el último bloque y, por lo tanto, pierde.
Téngase en cuenta que, dado que es demostrable que el jugador A puede ganar cuando comienza desde una barra de 5 × 4, al menos uno de los movimientos de A es un error.
Las posiciones intermedias en un Chomp m × n son particiones enteras (secuencias no crecientes de números enteros positivos) λ 1 ≥ λ 2 ≥···≥ λ r , con λ 1 ≤ n y r ≤ m . Su número es el coeficiente binomial , que crece exponencialmente con m y n . [1]
Chomp pertenece a la categoría de juegos imparciales de información perfecta para dos jugadores , lo que lo hace también analizable por Nim debido al teorema de Sprague-Grundy .
En cualquier posición inicial rectangular, distinta de 1×1, el primer jugador puede ganar. Esto se puede demostrar utilizando un argumento de robo de estrategia : supongamos que el segundo jugador tiene una estrategia ganadora contra cualquier movimiento inicial del primer jugador. Supongamos entonces que el primer jugador toma solo la casilla inferior derecha. Según nuestra suposición, el segundo jugador tiene una respuesta a esto que forzará la victoria. Pero si existe tal respuesta ganadora, el primer jugador podría haberla jugado como su primer movimiento y, por lo tanto, forzado la victoria. Por lo tanto, el segundo jugador no puede tener una estrategia ganadora.
Las computadoras pueden calcular fácilmente las jugadas ganadoras para este juego en tableros bidimensionales de tamaño razonable. Sin embargo, como el número de posiciones crece exponencialmente, esto no es factible para tableros más grandes.
Para una posición inicial cuadrada (es decir, n × n para cualquier n ≥ 2), la estrategia ganadora se puede dar fácilmente de forma explícita. El primer jugador debe presentar al segundo una forma de L de una fila y una columna solamente, de la misma longitud, conectadas en el cuadrado venenoso. Luego, haga lo que haga el segundo jugador en un brazo de la L , el primer jugador responde con el mismo movimiento en el segundo brazo, presentando siempre al segundo jugador nuevamente una forma de L simétrica . Finalmente, esta L degenerará en el único cuadrado venenoso, y el segundo jugador perdería.
El Chomp tridimensional tiene como base una barra de chocolate formada por un cuboide de bloques indexados como (i,j,k). Un movimiento consiste en tomar un bloque junto con cualquier bloque cuyos índices sean todos mayores o iguales al índice correspondiente del bloque elegido. De la misma manera, el Chomp se puede generalizar a cualquier número de dimensiones.
Chomp se describe a veces numéricamente. Se da un número natural inicial y los jugadores se alternan eligiendo divisores positivos del número inicial, pero no pueden elegir 1 o un múltiplo de un divisor elegido previamente. Este juego modela Chomp n- dimensional , donde el número natural inicial tiene n factores primos y las dimensiones del tablero de Chomp están dadas por los exponentes de los primos en su factorización prima . Chomp ordinal se juega en un tablero infinito con algunas de sus dimensiones números ordinales : por ejemplo, una barra de 2 × (ω + 4). Un movimiento es elegir cualquier bloque y eliminar todos los bloques con ambos índices mayores o iguales a los índices correspondientes del bloque elegido. El caso de Chomp ω × ω × ω es un notable problema abierto; se ha ofrecido una recompensa de $100 [2] por encontrar un primer movimiento ganador.
En términos más generales, Chomp se puede jugar en cualquier conjunto parcialmente ordenado con un elemento menor . Un movimiento consiste en eliminar cualquier elemento junto con todos los elementos mayores. Un jugador pierde si toma el elemento menor.
Todas las variedades de Chomp también se pueden jugar sin recurrir al veneno, utilizando la convención de juego de miseria : el jugador que se come el último bloque de chocolate no se envenena, sino que simplemente pierde por ser el último jugador. Esta regla es idéntica a la regla habitual cuando se juega a Chomp por sí solo, pero difiere cuando se juega la suma disyuntiva de juegos de Chomp, donde solo pierde el último bloque de chocolate final.
