Definizione di gioco combinatorio imparziale:

E' un gioco che soddisfa ai seguenti sei assiomi:

1) E' un gioco a due.
2) Ha un numero finito di configurazioni (dette anche posizioni) possibili.
3) E' definito un insieme di regole - uguali per entrambi i giocatori - che, data una configurazione, stabiliscono le configurazioni cui è lecito passare.
4) I due giocatori alternano le mosse.
5) Esistono configurazioni, dette terminali, dalle quali non è più possibile effettuare alcuna mossa, cioè non è lecito passare a nessun'altra configurazione.
6) Si arriva sempre ad una configurazione terminale in un numero finito di passi.

Perde chi al momento di giocare si trova in una situazione terminale, cioè non può fare alcuna mossa. Viceversa, vince chi arriva per primo in una posizione terminale: lui ha mosso e lascia l'altro senza mosse da fare.
Vediamo un esempio:

Il gioco dei decimali

Tutti i bambini di una quinta elementare hanno la calcolatrice, e il maestro vuole insegnare loro a sommare a mente numeri decimali.
Propone allora questo gioco:
"Prendete tutti la calcolatrice!
Vi sfido a questo gioco!
Si parte dal numero 0, che avete già sullo schermo.
Ogni volta si può aggiungere 0,1 o 0,2.
Giochiamo a turno io e voi, vince il primo che arriva a 1. Comincio io e metto 0,1.
Che cosa fate?"
La classe propone 0,2.
"Bene, scriviamo + 0,2 = , è venuto 0,3.
Io metto 0,1 e si arriva a 0,4. Che fate?"
La classe, per cambiare, propone 0,1.
"Siamo a 0,5. Io metto 0,2 e arriviamo a 0,7. Tocca a voi!"
La classe propone 0,1. Ma Elena obietta:
"Se giochiamo 0,1, si arriva a 0,8, lui gioca 0,2 e vince!"
Hanno cominciato a fare i conti.
Poi Franco aggiunge:
"Del resto se giochiamo 0,2 si arriva a 0,9, lui gioca 0,1 e vince! Ormai abbiamo perso..."
Dunque 0,7 è una posizione perdente.
Elena continua a ragionare e a fare conti:
"Avevamo già perso a 0,4, perché in ogni modo poteva obbligarci ad arrivare a 0,7.
Anzi avevamo già perso in partenza, a 0,1!"
I bambini ammisero la sconfitta senza volere arrivare alla fine, e si misero a discutere e fare un sacco di conti. Poi fecero al maestro questa proposta ridacchiando: "Facciamo lo stesso gioco, però vince chi arriva a 1,2! E giochi lei per primo!"
Esaminiamo le due versioni del gioco. E' chiaro che esistono posizioni perdenti e posizioni vincenti per il giocatore che si trova in esse.
Diciamo P l'insieme delle posizioni perdenti e V quello delle posizioni vincenti.
Vediamo quali sono nella prima versione i due insiemi.
Sicuramente 1 è perdente: è posizione terminale, dalla quale non vi sono più mosse. Bisogna distinguere bene tra essere in una posizione e arrivare in una posizione:

Pertanto chi gioca ha come scopo quello di ARRIVARE IN POSIZIONI PERDENTI, dalle quali dovrà poi ripartire - se potrà, cioè se non sono posizioni terminali - l'avversario.
Tornando al nostro discorso 1 Î P.
Anche 0,7 Î P perché chi è in 0,7 qualsiasi cosa faccia finirà per essere in 1, se l'avversario gioca correttamente.
Così per 0,1 e 0,4. P = {1; 0,7; 0,4; 0,1}
Se si è in una posizione perdente, qualsiasi cosa si faccia si arriva per forza in una posizione vincente (per l'altro giocatore).
Le posizioni vincenti sono V = {0; 0,2; 0,3; 0,5; 0,6; 0,8; 0,9}
Se si è in una posizione vincente si può sempre arrivare in una posizione perdente (per l'avversario).
Nella prima versione del gioco dei decimali 0 è vincente. Quindi chi gioca per primo ha una strategia vincente: lascerà l'avversario, volente o nolente, nelle posizioni 0,1; 0,4; 0,7; 1 : vittoria!
Se analizzate la seconda versione del gioco, proposto dai bambini, questi sono gli insiemi:
P = { 1,2; 0,9; 0,6; 0,3; 0}
V = {1,1; 1; 0,8; 0,7; 0,5; 0,4; 0,2; 0,1}
In questo caso 0 è perdente, se i bambini giocano correttamente (e lo faranno!) il maestro perderà.
Vince chi gioca per secondo.
E' immediato constatare che il gioco dei decimali (in entrambe le versioni) soddisfa alle condizioni 1) - 6) : è un gioco combinatorio.
L'analisi fatta per il gioco dei decimali può essere estesa ad ogni gioco combinatorio.
Vediamo come.
Costruiamo P e V con un procedimento induttivo.
Per 5) esistono stati terminali che sono certamente in P.
All'inizio del processo induttivo V è vuoto e P contiene gli stati terminali.
Mettiamo ora in V tutte le configurazioni dalle quali in una mossa si arriva ad uno stato terminale (nel quale si lascerà l'avversario): esse sono tutte vincenti.
Ora è il turno di P. Sono certamente perdenti quelle configurazioni dalle quali qualsiasi mossa si faccia si finisce in una posizione vincente (per il nemico).
Le mettiamo tutte in P e torniamo a V, etc.
Andiamo avanti fino ad esaurimento delle configurazioni.
Esempio (gioco dei decimali, prima versione)

PROCESSO DI COSTRUZIONE INDUTTIVA DI P E V ATTRAVERSO 8 PASSI

N° PASSO	P	V
0 (iniziale)	{1}	Æ
1	{1}	{0,9; 0,8}
2	{1; 0,7}	{0,9; 0,8}
3	{1; 0,7}	{0,9; 0,8; 0,6; 0,5}
4	{1; 0,7; 0,4}	{0,9; 0,8; 0,6; 0,5}
5	{1; 0,7; 0,4}	{0,9; 0,8; 0,6; 0,5; 0,3; 0,2}
6	{1; 0,7; 0,4; 0,1}	{0,9; 0,8; 0,6; 0,5; 0,3; 0,2}
7	{1; 0,7; 0,4; 0,1}	{0,9; 0,8; 0,6; 0,5; 0,3; 0,2; 0}

Questo processo si può sempre eseguire per ogni gioco combinatorio. Quindi l'insieme di tutte le posizioni di gioco si dividerà sempre in due parti P e V.
Chi gioca per primo vincerà se la posizione iniziale appartiene a V, se all'inizio è in una posizione vincente.
Altrimenti vincerà il secondo giocatore.
Ovviamente questo vale se hanno decomposto il gioco e conoscono le strategie.
Abbiamo dunque provato un teorema molto bello e importante:

Teorema . Per qualsiasi gioco combinatorio imparziale esiste una strategia vincente, per il primo o per il secondo giocatore.

Gli insiemi P e V possono anche essere caratterizzati dalle proprietà 1) - 3)
[1] Tutte le posizioni terminali sono in P.
[2] Data una posizione in P ogni mossa a partire da essa porta in V.
[3] Data una posizione in V esiste sempre una mossa che, a partire da essa, porta in P.

Le figure illustrano la caratterizzazione di P e V.

Osserviamo che le proprietà 1-3 caratterizzano in modo unico gli insiemi P e V, nell'insieme X di tutte le posizioni del gioco.
Questo significa che se è data una partizione dell'insieme delle mosse X in due sottoinsiemi Q e Z tali che:
(i) Gli stati terminali appartengono a Q
(ii) A partire da Q ogni mossa porta in Z
(iii) A partire da Z almeno una mossa porta in Q
Allora Q = P e Z = V.
Prima di passare al Nim vediamo un altro esempio.

Gioco a togliere da una pila

Siano dati un insieme S di interi positivi ed una pila di gettoni con n elementi.
Una mossa consiste nel levare v gettoni dalla pila, dove v Î S.
Il gioco dei decimali è isomorfo (è come fosse lo stesso, ha la stessa forma) al gioco a togliere con n=10 e S={1,2}.
Ma la situazione può essere più complicata, supponiamo S={1,3,4}. C'è una sola posizione terminale, 0 gettoni.
Seguendo il processo di costruzione induttiva di P e V abbiamo:
P = {0} , V = Æ
V = {1,3,4} , P = {0,2}
V = {1,3,4,5,6} , P = {0,2,7}
... V = {1,3,4,5,6,8,10,11,12,13,15,...}
P = {0,2,7,9,14,16,...}

n :	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
	P	V	P	V	V	V	V	P	V	P	V	V	V	V	P

Il pattern di lunghezza 7 PVPVVVV si ripete per sempre.
Se si parte dalla posizione n (n gettoni)
x Î P Û n mod 7 = 0,2
x Î V Û n mod 7 = 1,3,4,5,6
Quindi se all'inizio n=100, poiché 100 mod 7 = 2, il primo giocatore perderà e vincerà il secondo (supposto che giochi in modo razionale).

Il gioco del Nim

Il gioco del Nim è un gioco a togliere da k pile con n₁, n₂, ... n_k gettoni ognuna. Un giocatore, quando è il suo turno, può levare quanti gettoni vuole da una singola pila.
Se c'è una sola pila, la strategia è banale: togliere tutti i gettoni.
P = {0} , V = {1,2,3, ..., n} per ogni n.
Supponiamo ci siano due pile.
Sono perdenti le posizioni con un egual numero di gettoni e vincenti le altre:
P = {(0,0), {1,1}, {2,2}, ..., {n,n}}
V = {(x,y) : x ¹ y}
Vediamo che vale la caratterizzazione data sopra:
[1] La posizione terminale (0,0) Î P
[2] Se (a,a) Î P ogni mossa di P fa passare ad una posizione (x,y) con x ¹ y perché si tolgono gettoni da una sola pila.
[3] Se (x,y) Î V, allora x ¹ y e p.e. x>y
Allora togliendo x-y gettoni dalla prima pila si arriva a (y,y) Î P. Dunque da V si può sempre andare in P.

La sorpresa ora è che se le pile sono tre, la questione si fa così complessa che non essere visibile se non ad un occhio matematico!
Perché (9,19,26) è perdente e (25,15,18) e vincente?
E' stato Bonton nel 1902 (100 anni precisi or sono!) a trovare la soluzione, pubblicata in un articolo sulla prestigiosa rivista Annals of Mathematics: "Nim, a game with a complete mathematical theory".
Come sovente accade la soluzione dipende da una opportuna codifica del problema.
Una posizione del gioco è una terna di interi positivi o nulli x = (n₁, n₂, n₃), per esempio x = (9,19,26) cioè n₁=9, n₂=19, n₃=26.
Abbiamo espresso i numeri in notazione decimale.
Proviamo a scriverli in binario

	9 =	01001 =	0 x 16 + 1 x 8 + 0 x 4 + 0 x 2 + 1 x 1
T1	19 =	10011 =	1 x 16 + 1 x 2 + 1 x 1
	26 =	11010 =	1 x 16 + 1 x 8 + 1 x 2

I numeri vanno allineati: a quelli più piccoli bisogna premettere a sinistra tanti zeri quanti bastano: p.e.
9 = 01001 (ma anche 9 = 1001, 9 = 0001001 ...)
Notiamo che se leggiamo le colonne della tabella T1 in esse c'è un numero pari di 1.
Questo vale sempre.
Dimostriamo il bellissimo teorema:

Teorema . Nel Nim sono perdenti le posizioni in cui (scritti i numeri dei gettoni nelle pile in binario) in ogni colonna della tabella binaria c'è un numero pari di 1. Sono vincenti tutte le altre.

Dimostrazione . Diciamo P l'insieme delle posizioni, scritte in binario dove la somma degli 1 in tutte le colonne è pari.
Diciamo V il complementare, cioè l'insieme delle posizioni scritte in binario, dove la somma degli 1 in almeno una colonna è dispari.
Allora [1] è verificata, perché (0,0,0) Î P.
Se x Î P, x = (n₁, n₂, n₃) allora la tavola è

T1

Se faccio una mossa qualsiasi, posso agire comunque su una sola pila, cioè su di una sola riga della tabella.
La riga risultante, poiché ho fatto qualcosa, sarà diversa dalla riga precedente in almeno un posto.
In corrispondenza di questo posto la somma della colonna sarà ora dispari, sono passato a V.
Devo ora vedere che da V si può sempre passare a P.
Ora nella tavola almeno una colonna ha somma dispari. Tra quelle che hanno somma dispari prendo quella più a sinistra.
A sinistra di questa tutte le somme sono pari e non devo cambiare niente per passare a P.

Per esempio possiamo avere:

Sono dispari le colonne 3 e 5 (da sinistra).
Quella più a sinistra è la 3.
Le colonne 1 e 2 sono a posto, hanno somma pari.
Considero ora una riga che contiene un uno (della colonna) più a sinistra.
(in questo caso la seconda, se ce n'è più di una, la prendo a caso).
In questa riga (nell'esempio *) e a partire da questo 1 (nell'esempio ) andando verso destra cambio 1 in 0 o 0 in 1 in modo da parificare tutte le colonne.
La mossa è lecita perché corrisponde per forza ad una diminuzione del numero di gettoni nella pila corrispondente.
Nell'esempio se sono in T2 (Î V) passo a

Levo 45-39=6 gettoni dalla seconda pila e passo da (18,45,53) --> (18,39,53) e lascio l'avversario in posizione perdente!

PARTE II. Rimanere nei punti di equilibrio.

Giochi a due persone

Consideriamo i giochi con due contendenti, A e B.
Il gioco contempla un numero finito di situazioni e di mosse possibili per ognuno dei giochi.
Una strategia è una funzione che ad ogni situazione del gioco associa una mossa.
Naturalmente si può giocare senza avere prima una strategia.
Ci si trova in una situazione e semplicemente si fa una mossa.
Al tempo del gioco comunque noi abbiamo (senza saperlo) usato una delle strategie possibile preesistenti.
Le strategie sono ovviamente un numero finito,
siano R₁, R₂, ... , R_n le strategie per A e
C₁, C₂, ... , C_m per B.
Sono date inoltre due funzioni di utilità (o guadagno) m_A per il giocatore A e m_B per il giocatore B le quali ad ogni coppia di strategia R_i e C_j associano
m_A (R_i, C_j)= vincita di A se A gioca con la strategia R_i e B con la strategia C_j

m_B (R_i, C_j)= vincita di B se A gioca con la strategia R_i e B con la strategia C_j
Questo è tutto.
Il gioco può essere rappresentato da una tabella delle vincite (payoff)

che al posto i, j contiene due numeri entrambi relativi al caso che A giochi R_i e B C_j: il primo è la vincita di A, il secondo è la vincita di B.
Se la vincita è negativa, rappresenta una perdita.
Consideriamo il caso particolare, ma interessante, dei giochi a somma zero: sono i giochi dove
m_B (R_i, C_j)= - m_A (R_i, C_j).
Questi giochi possono essere rappresentati da una matrice con n righe ed m colonne dove al posto i, j c'è m_A (R_i, C_j) : infatti si può sottintendere m_B (R_i, C_j) che è semplicemente - m_A (R_i, C_j).

Suppongo ora di essere A, di partecipare ad un gioco a due persone a somma zero e di analizzare la tabella delle vincite (*): i numeri nella matrice rappresentano le mie vincite (o perdite).
Sono prudente, voglio essere certo di non perdere più di tanto.
Cerco dunque di minimizzare la perdita (ovvero di minimizzare la vincita dell'avversario).
In ogni riga cerco allora il minimo (il caso peggiore per me) e gioco la strategia che corrisponde al massimo di questi minimi : strategia maxmin.
Il giocatore B ragiona analogamente sulle colonne, ma con una relazione di ordinamento invertita perché le mie vincite sono le sue perdite: cercherà il massimo in ogni colonna e giocherà la strategia che corrisponde al minimo di questi massimi: strategia minmax.
Se a=maxmin delle righe e b=minmax delle colonne, allora si ha sempre a £ b.
a viene detto valore inferiore e b valore superiore del gioco.
Supponiamo che la matrice del gioco sia la seguente(3 strategie a testa):

La mia strategia maxmin ottimale è R₂.
La strategia minmax ottimale di B è C₂.
Queste strategie si mostrano instabili.
Finché io gioco R₂ e B C₂ la vincita per me è 6, tra il valore minimo (3) e massimo (7) del gioco.
Se però B si accorge (ripetendo il gioco) che io gioco sempre R₂ passerà a C₁ ed io guadagnerò solo 3. Ma allora io passo a R₁ e guadagnerò 9 e così via.
Quando il valore minimo del gioco ed il valore massimo del gioco coincidono, cioè a=b , questo valore comune è detto valore del gioco e lo indichiamo con v. Esempio

L'elemento 6 è il più piccolo nella sua riga ed il più grande nella sua colonna: a sinistra e a destra si sale, verso l'alto e verso il basso si scende: è un punto di sella.
Giochiamo allora (R₃, C₂). Se B sa che io giocherò R₃ non può fare di meglio che giocare C₂, per ogni altra scelta io guadagnerei di più.
Se io so che B giocherà C₂, giocherò R₃ perché qualsiasi altra scelta mi farà vincere di meno.
Questi punti di sella sono punti di equilibrio, sono stabili: nessuno dei due ha interesse ad abbandonarli perché comunque ci rimetterà.
Se il gioco ha un valore v=a=b ed esiste quindi un punto di equilibrio A ha una strategia che gli permette di vincere almeno v qualsiasi cosa faccia B e B ha una strategia che gli permette di perdere non più di v qualsiasi cosa faccia A.
Se l'avversario non gioca con equilibrio (ovvero nel punto di equilibrio) sarà punito: vincerà di meno o perderà di più!
Questa è la soluzione del gioco a somma zero tra due persone nel caso che la matrice del gioco abbia un punto di sella.

Strategie miste

Se A gioca la strategia R_i (o B gioca C_j) si dice che hanno usato strategie pure.
Spesso nella realtà utilizziamo strategie miste.
Consideriamo il gioco pari o dispari:
A e B mettono fuori - ognuno - da 0 a 5 dita; se la somma è pari A vince 1 se la somma è dispari A vince –1 (cioè B guadagna 1). Per A e per B ci sono solo due strategie: mettere un numero pari o un numero dispari di dita.
La matrice del gioco è questa

Se A e B giocano tante volte e B vede che A usa sempre - o più spesso - la strategia P (un numero pari di dita) userà D e vincerà. Ma se A se ne accorge passerà a D etc. etc.
Se A tira una moneta e gioca P se viene testa e D se viene croce, allora questa è una strategia mista.
Nel caso in esame allora A giocherà P con probabilità ½ e D con probabilità ½.
Se B usa la strategia pura P, qual è il guadagno atteso di A?
Ci sono solo due casi

La vincita attesa è 0, come ci attendiamo.
Supponiamo ora che B usi una strategia mista.
B gioca P con probabilità q, 0£q£1, e gioca D (di conseguenza) con probabilità 1-q.
Abbiamo quattro casi:

A	B	vincita di A	prob
P	P	1	½ q
D	P	-1	½ q
P	D	-1	½ (1-q)
D	D	1	½ (1-q)

Vincita attesa:
(1/2 q)ּ1+(1/2 q)ּ(-1)+(1/2ּ(1-q))ּ(-1)+(1/2ּ(1-q))=0
Se A usa la strategia (½, ½) qualsiasi cosa faccia B il guadagno di A sarà mediamente 0.
Lo stesso vale per B. C’è dunque un punto di equilibrio. Qualsiasi cosa faccia l’altro giocatore per noi non potrà andare peggio e per lui non potrà andare meglio!
Non si tratta di un caso particolare.
Abbiamo il notevole teorema (caso particolare di un più generale teorema di Nash):

Teorema . Ogni gioco a somma zero, a due giocatori con 2 strategie (gioco 2 x 2) ha un punto di equilibrio nelle strategie miste.

Dimostrazione
La matrice del gioco sia

Se la matrice ha un punto di sella, allora c’è un equilibrio con strategie pure e quindi con strategie miste (giocare R₁ è come giocare R₁ con probabilità 1 ed R₂ con probabilità 0). Supponiamo allora che la matrice non abbia un punto di sella.
Io sono A e decido di usare R₁ con prob p e R₂ (di conseguenza) con prob. 1-p.
Non so che cosa farà il mio avversario, B.
Se B usa C₁ la mia vincita attesa sarà:

A	B	prob	vincita
R1	C1	p	pe
R2	C1	1-p	(1-p)h

con vincita attesa pe+(1-p)h (°)
Se B usa C2 la mia matrice attesa sarà:

A	B	prob	vincita
R1	C2	p	pg
R2	C2	1-p	(1-p)f

con vincita attesa pg+(1-p)f (°°)
Io voglio trovare p in modo tale che (°)=(°°):
sarà così certo che il risultato non cambierà qualsiasi cosa B faccia.
Ottengo
(°°°) pe+(1-p)h=pg+(1-p)f che
risolta fornisce immediatamente

Si constata facilmente che se la matrice non ha punti di sella (come nelle ipotesi fatte) allora 0£p£1.
Quindi p rappresenta effettivamente una probabilità.
Il mio guadagno v sarà allora

Si noti che per la (°°°)

Vediamo il caso di B.
B decide di giocare C₁ con prob q e C₂ con prob. 1-q.
Supponiamo che A giochi R₁, ci sono due casi:

B	A	prob	vincita
C1	R1	q	qe
C2	R1	1-q	(1-q)g

con vincita attesa qe+(1-q)g (*)
Se invece A gioca R₂…

B	A	prob	vincita
C1	R2	q	qh
C2	R2	1-q	(1-q)f

con vincita attesa qh+(1-q)f (**)

Per annullare l’influenza del gioco di A
si deve avere (*)=(**) ovvero
qe+(1-q)g=qh+(1-q)f
Ricavando q si ha

Il guadagno atteso di B (qualsiasi cosa faccia A) è

come del resto doveva essere perchè il gioco è a somma 0.