Chomp

Da Wikipedia, l'enciclopedia libera.

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" (poset sta per partially ordered set, "insieme parzialmente ordinato"). La sua ideazione viene attribuita generalmente a David Gale (professore di computer science all'Università della California e autore anche del Bridg-It), 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 all'Università della California), che presenta diverse affinità con i giochi tradizionali della famiglia dei mancala.

Indice 1 Struttura del gioco 2 Esempio 3 Strategie 4 Generalizzazioni del Chomp 5 Bibliografia 6 Collegamenti esterni

[modifica] Struttura del gioco

Il "campo di gioco" del Chomp è un'ideale 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 sinitra è avvelenato, e io giocatore che si trova costretto a mangiarlo ha perso.

[modifica] Esempio

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

Inizio		Giocatore A		Giocatore B		Giocatore A		Giocatore B

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

[modifica] 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.

[modifica] 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). Una mossa consiste nel prendere un cubetto (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 il numero di fattori primi del numero iniziale, questo gioco è perfettamente equivalente al Chomp n − dimensionale in cui il campo da gioco iniziale aveva come dimensioni gli esponenti degli 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 l'elemento minimo.

Ogni varietà del Chomp può essere giocata anche con la regola misère: non perde chi mangia il cubetto avvelenato, ma chi fa l'ultima mossa. Sebbene questo non modifichi in alcun modo un singolo gioco di Chomp, è un cambiamento significativo in un'ulteriore versione del gioco, in cui i due giocatori si sfidano contemporaneamente in più partite a Chomp (facendo, a ciclo, una mossa ognuno in ogni partita). In tale versione, infatti, se la regola misère è valida perde chi prende l'ultimo cubetto avvelenato (invece che il primo).

[modifica] Bibliografia

• Gale, David: A Curious Nim-type game, American Mathematical Monthly, 81, 876-879, 1974.
• Gardner, Martin: Mathematical games: Sim, Chomp and Race Track: New games for the intellect (and not for Lady Luck), Scientific American, 228(1), 108-115, 1973.

[modifica] Collegamenti esterni

• (EN) Scheda sul Chomp, inclusi risultati analitici, varianti, e informazioni storiche
• (EN) Regole del Chomp
• (EN) Articolo Mathtrek sul Chomp
• (EN) Download di un programma per il Chomp
• (EN) Regole del Mancala di Eppstein presso manqala.org