Quale infallibile strategia possiamo usare per giocare a Nim non sbagliando nemmeno una mossa?
M: “Conosco un gioco in cui vinco sempre”
X: “Se non potete perdere, non è un gioco”
M: “Posso perdere, ma vinco sempre”
Il dialogo citato avviene tra i due protagonisti maschili di “L’anno scorso a Marienbad”, film del 1961 diretto da Alain Resnais. I personaggi della trama non hanno nomi e sono indicati con una lettera. M, interpretato da Sacha Pitoëff, sfida X, Giorgio Albertazzi al gioco del Nim, sicuro della sua vittoria.
Il Nim è un classico gioco combinatorio. Consiste nel creare vari mucchietti di oggetti e i giocatori, a turno, prelevano un numero qualsiasi di oggetti da uno solo dei mucchietti. Ovviamente, si può giocare usando solo carta e penna, disegnando dei bastoncini e cancellandoli a turno. Nella versione classica del gioco vince chi, con una mossa, preleva tutti gli oggetti restanti.
In diverse scene del film vengono usate delle carte, dei fiammiferi, degli stuzzicadenti o tessere del domino. I due giocano la versione “a dispetto”, cioè chi prende l’ultimo oggetto perde e, ogni volta, come anticipato da M, X perde prendendo l’ultimo oggetto. E’ quindi chiaro che M segua una strategia per essere sicuro di avere la vittoria.
Giorgio Albertazzi che gioca a Nim nel film “L’anno scorso a Marienbad”. Fonte immagine: Wikipedia
Per elaborare una strategia in un gioco combinatorio bisogna tenere conto delle diverse configurazioni. Si parte, infatti, dalla configurazione iniziale dei mucchietti e a ogni mossa la configurazione cambia, fino ad arrivare alla configurazione finale, che è l’assenza di oggetti dal tavolo.
Il passo successivo consiste nel trovare un modo efficace per suddividere le configurazioni in due insiemi: quelle favorevoli (F) per chi ha appena fatto la mossa e quelle sfavorevoli (S). I due insiemi devono essere disgiunti e ogni configurazione deve essere per forza di un tipo o dell’altro. Inoltre, valgono le seguenti regole:
- La configurazione finale è favorevole (come gioco del Nim classico, in cui vince chi fa l’ultima mossa)
- Da ogni configurazione sfavorevole è possibile ottenere, con una mossa, una configurazione sfavorevole
- Da una configurazione favorevole qualsiasi mossa porta a una configurazione sfavorevole
Si possono, allora, avere due possibilità, in base alla configurazione iniziale che può essere favorevole o sfavorevole.
F → S →F→…→S→F
S → F →S→…→S→F
Quindi la vittoria di uno o l’altro dei giocatori dipenderà da chi fa la prima mossa.
Facciamo un esempio: supponiamo di avere un insieme di monete, e i giocatori ne prendono una alla volta, chi prende l’ultima vince. Qui si capisce che le configurazioni favorevoli sono quelle in cui ci sono zero o un numero pari di monete, mentre quelle sfavorevoli corrispondono a un numero dispari. Se inizialmente ci sono un numero dispari di monete conviene muovere per primi, altrimenti per secondi.
Bene, ora possiamo chiederci: quali sono le configurazioni favorevoli e sfavorevoli per il gioco del Nim? Per rispondere, bisogna rispolverare il codice binario.
Supponiamo, allora, che la configurazione di oggetti sia: 1 2 4 5. Quello che bisogna fare è scrivere ogni numero in codice binario (qui una spiegazione su come fare la conversione) mettendoli in colonna, allineando l’ultima cifra a sinistra, ottenendo
| 1 | ||
| 1 | 0 | |
| 1 | 0 | 0 |
| 1 | 0 | 1 |
Va poi eseguita, per ogni colonna, la somma modulo due (cioè secondo la regola che 1+1=0, qui un articolo sulla somma con i moduli) degli elementi su ogni colonna. Otterremo così la terna 0 1 0, la terna di numeri ottenuti viene chiamata, appunto somma Nim.
Nel gioco del Nim classico, le configurazioni favorevoli corrispondono a quelle che hanno somma Nim nulla, cioè data da soli zeri. Questo significa che, nel caso che stiamo considerando, per vincere dobbiamo muovere per primi, in modo da ottenere una configurazione a somma nulla. Potremmo, ad esempio, eliminare il secondo mucchietto, così da avere la configurazione favorevole
| 1 | ||
| 0 | ||
| 1 | 0 | 0 |
| 1 | 0 | 1 |
A questo punto, qualunque sarà la mossa del nostro avversario, la configurazione risultante avrà somma Nim non nulla, e quindi sfavorevole. Andando avanti in questo modo, l’ultima mossa vincente sarà dunque la nostra.
A questo link potete giocare online e sfidare la scimmietta a Nim mangiando biscotti!
Di sicuro una strategia del genere non è immediata da applicare e richiede almeno carta e penna per calcolare ogni mossa, ma è probabile che con molto allenamento si possa memorizzare quali sono le buone configurazioni da ottenere per vincere. Sicuramente il personaggio di M nel film aveva questa capacità.
Inoltre, che nel gioco a dispetto giocato nella pellicola, la distinzione tra configurazioni favorevoli e sfavorevoli coinvolge più elementi rispetto alla sola somma Nim. In questo caso, essendo la configurazione iniziale favorevole (1 3 5 7), M lascia giocare X per primo. Tuttavia, nell’ultima partita giocata, X chiede a M di fare la prima mossa. Anche in questo caso, però perde.
La spiegazione si può trovare nella sua narrazione che si sente in sottofondo “e ancora una volta camminavo solo […] scegliendo a caso la strada nel dedalo di questi labirinti”, cioè M non segue nessuna strategia. Quindi dove non arriva un’infallibile strategia, anche un po’ di fortuna può farci vincere lo stesso!
Per saperne di più:
Puntata del podcast in cui parliamo del gioco del Nim
Un’applicazione del calcolo binario:il gioco del Nim
Nim, A Game with a Complete Mathematical Theory
Immagine di copertina: THEBILLJR/Shutterstock