Indietro

ⓘ Chomp




Chomp
                                     

ⓘ Chomp

Il Chomp è un gioco astratto, uno dei giochi di riferimento più citati nella letteratura sulla teoria dei giochi combinatori, insieme ad Hackenbush e Nim. Da un punto di vista matematico, viene classificato come gioco "poset". La sua ideazione viene attribuita generalmente a David Gale, ma può essere interpretato come una variante del gioco dei divisori proposto da Fred Schuh nel 1952. Fu Martin Gardner a dare al gioco il nome "Chomp", con cui esso è oggi noto.

Del Chomp sono state proposte in letteratura molte varianti. Fra queste si può citare il mancala di Eppstein inventato da David Eppstein, collega di Gale allUniversità della California, che presenta diverse affinità con i giochi tradizionali della famiglia dei mancala.

                                     

1. Struttura del gioco

Il "campo di gioco" del Chomp è unideale tavoletta di cioccolata rettangolare suddivisa in cubetti tutti uguali. A turno, i giocatori prendono un cubetto e lo "mangiano" tolgono dalla tavoletta, insieme ad ogni cubetto che sta nella parte sotto e a destra della tavoletta. Il cubetto in alto a sinistra è avvelenato, e il giocatore che si trova costretto a mangiarlo ha perso.

                                     

2. Esempio

Riportiamo una sequenza di mosse che può prodursi partendo da una tavoletta di dimensioni 3 × 5:

A questo punto, il giocatore A è obbligato a mangiare lultimo blocco e quindi ha perso.

                                     

3. Strategie

Chomp appartiene alla categoria dei giochi imparziali a informazione completa a due giocatori.

Per ogni tavoletta di partenza di dimensioni maggiori di 1x1, se il giocatore A gioca intelligentemente, vince. Può essere verificato con una dimostrazione per furto di strategia: supponiamo che il giocatore B abbia viceversa una strategia vincente. Allora la sua strategia contempla ogni possibile prima mossa del giocatore A. Supponiamo allora che il giocatore A come prima mossa stacchi soltanto il cubetto in basso a destra. Il giocatore B avrà una risposta che lo porta a vincere. Ma allora il primo giocatore avrebbe potuto giocare direttamente questa mossa come prima mossa. In conclusione, il giocatore B non può avere una strategia vincente.

Un computer può facilmente calcolare le mosse vincenti in questo gioco, giocato su tavolette bidimensionali di dimensioni ragionevoli.

                                     

4. Generalizzazioni del Chomp

Nel Chomp tridimensionale, il "campo da gioco" non è più una tavoletta ma un parallelepipedo di cioccolato, i cui cubetti sono numerati con tre indici i, j, k {\displaystyle i,j,k}. Una mossa consiste nel prendere un cubetto a, b, c {\displaystyle a,b,c} ancora attaccato e con esso tutti i cubetti aventi tutti tre gli indici minori. Similmente, il Chomp può essere generalizzato in qualsiasi dimensione.

Il Chomp può essere descritto numericamente: dato un numero naturale iniziale, i giocatori a turno scelgono un divisore proprio positivo di tale numero che non sia 1 e non sia multiplo di un divisore già scelto. Dato n {\displaystyle n} il numero di fattori primi del numero iniziale, questo gioco è perfettamente equivalente al Chomp n − {\displaystyle n-} dimensionale in cui il campo da gioco iniziale aveva come dimensioni gli esponenti degli n {\displaystyle n} primi nella sua fattorizzazione.

Il Chomp ordinale si gioca su un campo infinito, in cui alcune delle dimensioni sono date da numeri ordinali: per esempio, una tavoletta di dimensioni 2 × ω + 4. Una mossa consiste nel prendere un cubetto e insieme ogni cubetto avente tutti gli indici maggiori o uguali degli indici di tale blocchetto. Il caso ω × ω × ω è un celebre problema aperto; sono stati messi in palio dei premi per chi trovi una prima mossa vincente.

Più in generale, Chomp si può giocare su qualsiasi insieme parzialmente ordinato avente un elemento minimo. Una mossa consiste nel rimuovere un elemento e tutti quelli maggiori; perde il giocatore costretto a rimuovere il lelemento minimo.

Ogni varietà del Chomp può essere giocata anche con la regola misère: non perde chi mangia il cubetto avvelenato, ma chi fa lultima mossa. Sebbene questo non modifichi in alcun modo un singolo gioco di Chomp, è un cambiamento significativo in unulteriore versione del gioco, in cui i due giocatori si sfidano contemporaneamente in più partite a Chomp. In tale versione, infatti, se la regola misère è valida perde chi prende lultimo cubetto avvelenato invece che il primo.