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" (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.
Struttura del gioco
modificaIl "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 sinistra è avvelenato, e il giocatore che si trova costretto a mangiarlo ha perso.
Esempio
modificaRiportiamo 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.
Strategie
modificaChomp 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.
Generalizzazioni del Chomp
modificaNel Chomp tridimensionale, il "campo da gioco" non è più una tavoletta ma un parallelepipedo di cioccolato, i cui cubetti sono numerati con tre indici . Una mossa consiste nel prendere un cubetto 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 il numero di fattori primi del numero iniziale, questo gioco è perfettamente equivalente al Chomp dimensionale in cui il campo da gioco iniziale aveva come dimensioni gli esponenti degli 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).
Bibliografia
modifica- David Gale, A Curious Nim-type game, American Mathematical Monthly, 81, 876-879, 1974.
- Martin Gardner, Mathematical games: Sim, Chomp and Race Track: New games for the intellect (and not for Lady Luck), Scientific American, 228(1), 108-115, 1973.
Altri progetti
modifica
Wikimedia Commons contiene immagini o altri file su Chomp
Collegamenti esterni
modifica- (EN) Scheda sul Chomp, inclusi risultati analitici, varianti e informazioni storiche, su win.tue.nl.
- (EN) Articolo su ScienceNews, "column" Math Trek, sul Chomp, su sciencenews.org. URL consultato il 30 aprile 2019 (archiviato dall'url originale il 17 aprile 2008).
- (EN) Regole del Mancala di Eppstein, su wikimanqala.org. URL consultato il 2 maggio 2009 (archiviato dall'url originale l'11 ottobre 2008).
