Adriana Enriques: un altro articolo sul gioco

Giuoco con tre gruppi di oggetti è un altro articolo che Adriana Enriques pubblicò nel Periodico di Matematiche. Il gioco del Nim e possibili varianti.

Nei giorni scorsi è stata ricordata la figura di Adriana Enriques. Ne hanno parlato Biagio Scognamiglio e Adriana Lanza in due pregevoli interventi che ne pongono in risalto, tra l’altro, la collaborazione alla Mathesis e al Periodico di Matematiche.

In considerazione di ciò, piace portare all’attenzione dei lettori un secondo articolo di Adriana Enriques pubblicato nel PdM.

È del 1930: Giuoco con tre gruppi di oggetti, che è probabilmente uno dei primi articoli di Teoria dei Giochi in lingua italiana. [VEDI]

La Teoria dei Giochi affonda le radici nei lavori che portarono alla nascita della Teoria della Probabilità. È però nel 1920 che Borel dà l’avvio, anche inventandone il nome, alla teoria matematica che punta alla formalizzazione di ogni forma di situazione competitiva e all’elaborazione di strategie che massimizzino l’esito della competizione. Tale teoria riceve poi il suo massimo impulso nel 1944 con la pubblicazione di Theory of Games and Economic Behavior di von Neumann e Morgenstern.

In questo articolo Adriana Enriques espone le regole di un gioco sostanzialmente semplice.

Il gioco è appena più complicato del più famoso tris, e ne descrive una matematizzazione che permette di elaborare una strategia che porta a vittoria certa (purché sotto determinate condizioni che analizzeremo più avanti). Come il gioco del tris, quindi, anche il gioco presentato da Adriana Enriques, sulla carta, è un gioco “inutile”: se entrambi i giocatori conoscono la strategia ottimale, l’esito della partita è prevedibile prima ancora che essa inizi.

Tuttavia questa strategia si basa su concetti matematici ben più profondi di quelli che portano alla strategia ottimale per il tris, e di conseguenza non è facile apprendere tale strategia solo sulla base dell’esperienza di gioco.

Il lavoro di Adriana Enriques, quindi, è pregevole soprattutto perché mostra come l’opportuna formalizzazione matematica permetta di far emergere in modo naturale regolarità nascoste dentro alla dinamica di ogni sistema, e che questa formalizzazione opportuna può passare attraverso concetti matematici del tutto inaspettati rispetto al sistema in esame.

Nel seguito riformuliamo la strategia presentata da Adriana Enriques in un linguaggio più moderno, che non mescola tra loro la rappresentazione binaria e quella non binaria.

Il gioco del Nim

Il gioco descritto dall’articolo di Adriana Enriques è noto oggi con il nome di “Gioco del Nim”.

L’origine di questo gioco è incerta. In tutto il territorio che abbraccia Europa, Medio-Oriente e Africa Mediterranea esistono numerosi giochi antichi basati sullo spostamento o sottrazione di elementi da gruppi separati di oggetti uguali.

Il gioco del Nim consiste nel suddividere un certo numero di oggetti (in genere cerini, e nel prosieguo di questa nota faremo riferimento a questa scelta) in gruppetti (in genere 3) di cardinalità arbitraria. A turno ogni giocatore sceglie un gruppetto di cerini e toglie una quantità a piacere dei suoi elementi. Non è possibile “passare”, cioè terminare il proprio turno senza aver rimosso almeno un cerino dal tavolo. Vince chi prende l’ultimo cerino dal tavolo.

Questo gioco è famoso per essere uno dei giochi in cui è presente una strategia di vittoria semplice, infatti questo gioco è classificato tra quelli di complessità di grado L.¹

La strategia ottimale

Tale strategia si basa sull’uso dei numeri 1 e 0 sia come cifre binarie per rappresentare numeri interi sia come valori di logica booleana. Consideriamo come esempio una partita in cui ci siano tre gruppetti rispettivamente di, 4, 7  e 9 cerini.

Rappresentiamo i tre numeri in base 2, avendo cura di usare lo stesso numero di cifre per tutti i numeri, abbiamo quindi 0100, 0111 e 1001. Ora eseguiamo la somma di questi numeri ignorando i riporti (un modo equivalente è considerare la somma delle cifre dello stesso posto come valori di verità connessi dalla disgiunzione esclusiva XOR). Questo tipo di somma è anche chiamata “somma Nim”. Nell’esempio scelto abbiamo

0100
0111
1001
1010

Qualunque configurazione che ha somma Nim pari a 0 è chiamata vincente, mentre tutte quelle con somma Nim diversa da 0 sono dette perdenti. L’origine di questi nomi è facile da capire dato che la configurazione presente al termine dell’ultima mossa, che decreta il vincitore, è evidentemente una configurazione con somma Nim nulla.

Una configurazione vincente presenta un numero pari di 1 in ciascuna colonna, mentre una perdente vede almeno una colonna con un numero dispari di 1.

Se un giocatore inizia il proprio turno con una configurazione perdente può facilmente trasformarla in una vincente, infatti basta prendere il numero più grande e variarne tutte le cifre delle colonne in cui compare un 1 nel risultato della somma Nim. Nel nostro caso modifichiamo il terzo numero da 1001 e 0011. Dal punto di vista della codifica binaria questo significa che la tabella della somma Nim diventa

0100
0111
0011
0000

mentre dal punto di vista del gioco, significa che gli elementi del terzo gruppetto devono variare da 9 a 3, quindi il giocatore di turno deve rimuovere 6 elementi dal terzo gruppetto.

Se un giocatore inizia il proprio turno con una configurazione vincente non può evitare di trasformarla in una perdente.

0100
0111
0011
0000

Infatti se la somma Nim è già 0, qualunque variazione di uno solo dei numeri (bisogna necessariamente sottrarre gli elementi da un solo gruppetto per ogni turno) farà variare una cifra binaria in almeno una delle colonne e di conseguenza su quella colonna lo  del risultato diventerà 1.

Quindi il giocatore che, ad un certo punto della partita, inizia il proprio turno con una configurazione perdente sul tavolo, se applica correttamente la strategia descritta ha la vittoria assicurata. Infatti se il giocatore A ha cura di trasformare ogni configurazione perdente in vincente, l’avversario B non potrà fare altro che restituire una configurazione perdente al termine del proprio turno. Dato che il numero di oggetti cala continuamente, anche la somma Nim delle varie configurazioni è decrescente e pertanto, saltando da una configurazione vincente ad un’altra, A prima o poi potrà trasformare una configurazione perdente nella configurazione vincente che vede 0 come cardinalità di tutti i gruppi e non solo della somma Nim.

Se entrambi i giocatori applicano correttamente la strategia corretta, la vittoria è univocamente determinata dalla configurazione iniziale e la partita vedrà vincitore il primo giocatore di turno se la configurazione iniziale è perdente, altrimenti a vincere sarà il secondo di turno.

Dato che il carattere della configurazione iniziale è determinato dal risultato sostanzialmente di una somma espressa in binario, la distribuzione dei possibili risultati della somma Nim (se il numero di gruppetti e le loro cardinalità sono scelte a caso) non è uniforme. Tuttavia è prevedibile che un risultato iniziale di n cifre 0 non possa avere una probabilità equivalente a tutte le altre possibili sequenze di n cifre binarie considerate insieme e che anzi tale probabilità diminuisca al crescere di n. Pertanto, in generale, il primo giocatore ha un’alta probabilità di iniziare con una configurazione perdente e quindi, se conosce la strategia corretta, sarà il vincitore.

Una possibile variante 

Esiste una variante, nota come “Marienbad”,² in cui chi è costretto a raccogliere l’ultimo cerino perde. In questo caso la situazione è ribaltata rispetto a quanto detto prima: sono vincenti le configurazioni con somma Nim non nulla e sono perdenti le configurazioni con somma Nim nulla.

Il gioco diventa strategicamente più interessante perché se si riceve una configurazione perdente la si può trasformare in vincente con una mossa qualunque. Contemporaneamente non è più vero che se il gioco è in una configurazione vincente a inizio turno la si debba necessariamente trasformare in perdente: si è costretti a tale mossa solo di fronte ad un numero dispari di gruppetti non vuoti che contengono ciascun un solo cerino, cioè di fronte a configurazioni con somma Nim pari a 1.

Tuttavia l’analisi strategica di questa variante ci porterebbe lontano dal contenuto dell’articolo di Adriana Enriques e pertanto la rimandiamo ad un eventuale successivo articolo.

NOTE