Chomp
# Chomp

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 se pueden considerar como los bloques de una tableta de chocolate. Los jugadores se turnan para elegir un bloque y "comérselo" (retirar del tablero), junto con los que están debajo y a su derecha. El bloque superior izquierdo está "envenenado" y el jugador que lo come pierde.

La formulación en tableta de chocolate de Chomp se debe a David Gale, pero Frederik Schuh publicó anteriormente un juego equivalente expresado en términos de elegir divisores de un entero fijo.

Chomp es un caso especial de un juego poset en el que el conjunto parcialmente ordenado en el que se juega el juego es un producto de los pedidos totales con el elemento mínimo (bloque venenoso) eliminado.

## Ejemplo

A continuación se muestra la secuencia de movimientos en un juego típico que comienza con una tableta de 5 × 4:

El jugador A come dos bloques desde 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 se 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 pierde.

Tenga en cuenta que, dado que se puede demostrar que el jugador A puede ganar cuando comienza desde una tableta de 5 × 4, al menos uno de los movimientos de A es un error.

## Ganar el juego

Chomp pertenece a la categoría de juegos de información perfecta imparcial para dos jugadores.

Para cualquier posición inicial rectangular, que no sea 1 × 1, el primer jugador puede ganar. Esto se puede demostrar usando un argumento de robo de estrategia: suponga que el segundo jugador tiene una estrategia ganadora contra cualquier movimiento inicial del primer jugador. Supongamos entonces que el primer jugador toma solo el cuadrado de la parte 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 haberlo jugado como su primer movimiento y, por lo tanto, forzado la victoria. Por tanto, el segundo jugador no puede tener una estrategia ganadora.

Las computadoras pueden calcular fácilmente los movimientos ganadores de este juego en tableros bidimensionales de tamaño razonable.

## Generalizaciones de Chomp

El Chomp tridimensional tiene una tableta de chocolate inicial de un cuboide de bloques indexadas como (i, j, k). Un movimiento es tomar un bloque junto con cualquier bloque cuyos índices sean mayores o iguales al índice correspondiente del bloque elegido. De la misma manera, Chomp se puede generalizar a cualquier número de dimensiones.

Chomp a veces se describe 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 previamente elegido. Este juego modela Chomp n- dimensional, donde el número natural inicial tiene n factores primos y las dimensiones del tablero Chomp están dadas por los exponentes de los números primos en su factorización prima. Ordinal Chomp se juega en un tablero infinito con algunas de sus dimensiones números ordinales: por ejemplo, una tableta 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 problema abierto notable; se ha ofrecido una recompensa de $ 100 por encontrar un primer movimiento ganador.

De manera más general, Chomp se puede jugar en cualquier conjunto parcialmente ordenado con un elemento mínimo. Un movimiento es eliminar cualquier elemento junto con todos los elementos más grandes. Un jugador pierde tomando el elemento mínimo.

Todas las variedades de Chomp también se pueden jugar sin recurrir al veneno utilizando la convención de juego de misère: el jugador que come el bloque de chocolate final no está envenenado, sino que simplemente pierde en virtud de ser el último jugador. Esto es idéntico a la regla ordinaria cuando se juega Chomp solo, pero difiere cuando se juega la suma disyuntiva de los juegos Chomp, donde solo pierde el último bloque de chocolate final.

