Chomp - Chomp
Chomp é um jogo de estratégia para dois jogadores jogado em uma grade retangular composta de células quadradas menores , que podem ser consideradas os blocos de uma barra de chocolate. Os jogadores se revezam para escolher um bloco e "comê-lo" (retirá-lo do tabuleiro), junto com os que estão abaixo e à direita. O bloco superior esquerdo é "envenenado" e o jogador que comê-lo perde.
A formulação da barra de chocolate de Chomp é devida a David Gale , mas um jogo equivalente expresso em termos de escolha de divisores de um inteiro fixo foi publicado anteriormente por Frederik Schuh .
Chomp é um caso especial de um jogo poset onde o conjunto parcialmente ordenado em que o jogo é jogado é um produto de total de pedidos com o elemento mínimo (bloco venenoso) removido.
Jogo de exemplo
Abaixo mostra a sequência de movimentos em um jogo típico começando com uma barra 5 × 4:
O jogador A come dois blocos do canto direito inferior; O jogador B come três da linha inferior; O jogador A escolhe o bloco à direita do bloco envenenado e come onze blocos; O jogador B come três blocos da coluna restante, deixando apenas o bloco envenenado. O jogador A deve comer o último bloco e, portanto, perde.
Observe que, uma vez que é provável que o jogador A pode ganhar começando em uma barra 5 × 4, pelo menos um dos movimentos de A é um erro.
Ganhando o jogo
Chomp pertence à categoria de jogos imparciais de informação perfeita para dois jogadores .
Para qualquer posição inicial retangular, diferente de 1 × 1, o primeiro jogador pode ganhar. Isso pode ser mostrado usando um argumento de roubo de estratégia : suponha que o segundo jogador tenha uma estratégia vencedora contra qualquer movimento inicial do primeiro jogador. Suponha então que o primeiro jogador pegue apenas o quadrado inferior direito. Por nossa suposição, o segundo jogador tem uma resposta para isso que forçará a vitória. Mas se essa resposta vencedora existir, o primeiro jogador poderia ter jogado como seu primeiro movimento e, assim, forçado a vitória. O segundo jogador, portanto, não pode ter uma estratégia vencedora.
Os computadores podem calcular facilmente as jogadas vencedoras para este jogo em tabuleiros bidimensionais de tamanho razoável.
Generalizações de Chomp
O Chomp tridimensional tem uma barra de chocolate inicial de um cuboide de blocos indexados como (i, j, k). Um movimento é pegar um bloco junto com qualquer bloco cujos índices sejam maiores ou iguais ao índice correspondente do bloco escolhido. Da mesma forma, Chomp pode ser generalizado para qualquer número de dimensões.
Chomp às vezes é descrito numericamente. Um número natural inicial é dado, e os jogadores alternam escolhendo divisores positivos do número inicial, mas não podem escolher 1 ou um múltiplo de um divisor previamente escolhido. Este jogo modela o Chomp n- dimensional , onde o número natural inicial possui n fatores primos e as dimensões do tabuleiro Chomp são dadas pelos expoentes dos primos em sua fatoração primo . Ordinal Chomp é jogado em um tabuleiro infinito com alguns de seus números ordinais de dimensões : por exemplo, uma barra 2 × (ω + 4). Um movimento é pegar qualquer bloco e remover todos os blocos com ambos os índices maiores ou iguais aos índices correspondentes do bloco escolhido. O caso de ω × ω × ω Chomp é um problema aberto notável; uma recompensa de $ 100 foi oferecida por encontrar um primeiro movimento vencedor.
De modo mais geral, o Chomp pode ser reproduzido em qualquer conjunto parcialmente ordenado com um elemento mínimo . Um movimento consiste em remover qualquer elemento junto com todos os elementos maiores. Um jogador perde ao pegar o menor elemento.
Todas as variedades de Chomp também podem ser jogadas sem recorrer ao veneno, usando a convenção do misère play: o jogador que come o bloco de chocolate final não é envenenado, mas simplesmente perde por ser o último jogador. Isso é idêntico à regra comum ao jogar Chomp sozinho, mas difere ao jogar a soma disjuntiva dos jogos Chomp, em que apenas o último bloco de chocolate final perde.
Veja também
Referências
- ^ p. 482 in: Games of No Chance (RJ Nowakowski, ed.), Cambridge University Press, 1998.