Teoria dei giochi
2. Forma estesa
(struttura ad albero e matrice dei
pagamenti)
Slides di Teoria dei Giochi,
Vincenzo Cutello
1
Struttura ad albero:
Gioco dei fiammiferi
2
1
0
2
2
A
2
0
1
1
1
0
0
1
B
2
0
0
 Struttura ad albero (mossa dopo mossa)
 Gioco finito ad informazione perfetta
 Vince sempre B (ossia il secondo che muove) in questo
esempio. Ma si può dimostrare in generale?
Slides di Teoria dei Giochi,
Vincenzo Cutello
2
Matrice dei pagamenti:
il dilemma del prigioniero
B
A
C
NC
C
NC
(2,2)
(7,0)
(0,7)
(1,1)
 Se B confessa, ad A conviene
confessare
 Se B non confessa, ad A conviene
confessare.
 Morale: se è razionale confessa.
Slides di Teoria dei Giochi,
Vincenzo Cutello
3
Assioma di razionalità
Un giocatore sceglie l’azione che gli consente di ottenere
i risultati migliori, qualunque sia la mossa
dell’avversario


Per entrambi i due prigionieri la strategia migliore è quella
di confessare.
Situazione di equilibrio.
B
A
C
NC
C
NC
(2,2)
(7,0)
(0,7)
(1,1)
Slides di Teoria dei Giochi,
Vincenzo Cutello
4
Teorema di Zermelo
Nel gioco degli scacchi (gioco finito a informazione perfetta) può
sussistere una ed una sola delle seguenti tre alternative:
1. Il bianco può forzare nero alla sconfitta
2. Il nero può forzare il bianco alla sconfitta
3. Entrambi i giocatori possono forzare il pareggio


Ma che razza di teorema è questo?
E perché mai è importante che il gioco sia finito a informazione
perfetta
Risposta: quanto vi piace disegnare alberi ?
Slides di Teoria dei Giochi,
Vincenzo Cutello
5
Esempio
1
2
3
4
5
9
13
6
10
14
7
11
15
8
12
16
 Due giocatori (A e B) a turno possono togliere
una casella dal quadrato
 Togliendo una casella si tolgono tutte quelle
sopra e quelle a destra della casella.
 Chi toglie la casella “13” perde.
Slides di Teoria dei Giochi,
Vincenzo Cutello
6
Esempio: cont.
 E’ un gioco finito e ad informazione perfetta:
 Non esiste il pareggio
 Per il teorema di Zermelo, o esiste una strategia
vincente per A (chi muove per primo) o esiste una
strategia vincente per B (chi muove per secondo).
 Secondo voi ??
Slides di Teoria dei Giochi,
Vincenzo Cutello
7
Giochi come problemi di ricerca
 Avversario “imprevedibile”  la soluzione è un
piano di emergenza
 Limiti di tempo  a meno di trovare la soluzione,
dobbiamo approssimare
 Piano di attacco:
• Algoritmi per giocatori perfetti (Von Neumann,
1944)
• Orizzonte finito, valutazione approssimata (Zuse,
1945; Shannon, 1950; Samuel, 1952-57)
• Taglio per ridurre i costi (McCarty, 1956)
Slides di Teoria dei Giochi,
Vincenzo Cutello
8
Tipi di giochi
Informazione
perfetta
Deterministici
Elemento di
fortuna
Scacchi, dama,
go, otello
Backgammon,
monopoli
Informazione
imperfetta
Bridge, poker,
guerra
Slides di Teoria dei Giochi,
Vincenzo Cutello
9
Minimax
 Giocatori perfetti per giochi deterministici ad informazione perfetta
 Idea: scegli la mossa che porta alla posizione con il più alto minimax
value = miglior risultato raggiungibile contro il miglior avversario
Per esempio, gioco a 2 giocatori:
MAX
3
A1
2
3
MIN
A11
3
A12
12
A3
A2
A21
A13
8
2
A22
2
A23
4
Slides di Teoria dei Giochi,
Vincenzo Cutello
6
A31
14
A32
5
A33
2
10
Algoritmo Minimax
function DECISIONE-MINIMAX (gioco)
returns un operatore
for each op in OPERATORI[gioco] do
VALORE[op]  VALORE-MINIMAX
(APPLICA(op,game), game)
end
return op con il più alto valore VALORE[op]
function VALORE-MINIMAX (stato, gioco)
returns un valore di utilità
if VERIFICA-TERMINALE[gioco]
then return UTILITA’[gioco](stato)
else if MAX deve muovere nello stato
then return
il più alto valore VALORE-MINIMAX di
SUCCESSORI(stato)
else return
il più basso valore VALORE-MINIMAX di
SUCCESSORI(stato)
Slides di Teoria dei Giochi,
Vincenzo Cutello
11
Proprietà di minimax
 Completo ??
– Si, se l’albero è finito (gli scacchi hanno regole
specifiche per questo)
 Ottimo ??
– Si, contro un avversario ottimale. Altrimenti ?
 Complessità temporale ??
– O(bm)
 Complessità spaziale ??
– O(bm) (esplorazione depth-first)
– Per gli scacchi b ≈ 35, m ≈ 100 per partite tipiche 
soluzione esatta non raggiungibile
Slides di Teoria dei Giochi,
Vincenzo Cutello
12
Limiti delle risorse
Supponiamo di avere 100 secondi, esploriamo
104 nodi/secondo  106 nodi per mossa
Approccio standard:
• Test di taglio
cioè, limite di profondità (probabile aggiunta della
ricerca di quiescenza)
• Funzione di valutazione
stima della desiderabilità di una posizione
Slides di Teoria dei Giochi,
Vincenzo Cutello
13
Funzioni di valutazioni
 Per gli scacchi, una tipica somma lineare pesata delle
caratteristiche
EVAL(s) = w1f1(s)+ w2f2(s)+…+ wnfn(s)
per esempio,
–
–
–
–
–
w1 = 9
f1(s) = (# di regine bianche)-(# di regine nere)
w2 = 7
f2(s) = (# di torri bianche)-(# di torri nere)
etc
Slides di Teoria dei Giochi,
Vincenzo Cutello
14
Valore esatto ?
MAX
1
MIN
1
2
2
2
1
4
1
2
20
2
400
 Il comportamento è preservato rispetto ad una qualsiasi
trasformazione monotonica di EVAL: Interessa solo
l’ordine
 Payoff nei giochi deterministici agisce come una funzione
di utilità ordinale
Slides di Teoria dei Giochi,
Vincenzo Cutello
15
Tagliando la ricerca
MINIMAXCUTOFF è
identica alla VALOREMINIMAX eccetto per
 Terminale rimpiazzata
da CUTOFF ?
 UTILITA’ rimpiazzata
da EVAL
Funziona in pratica ?
function MINIMAX-CUTOFF(stato,
gioco)
returns un valore di utilità
if VERIFICA-CUTOFF[gioco]
then return EVAL[gioco](stato)
else if MAX deve muovere nello stato
then return
il più alto valore VALOREMINIMAX di SUCCESSORI(stato)
else return
il più basso valore VALOREMINIMAX di SUCCESSORI(stato)
Slides di Teoria dei Giochi,
Vincenzo Cutello
16
Esempio di α-β pruning
≥3
MAX
≤2
3
MIN
3
12
8
2
X
2
≤14
≤5
X
Slides di Teoria dei Giochi,
Vincenzo Cutello
14
5
2
17
Proprietà di α-β
 Il pruning non altera il risultato finale
 Il buon ordinamento delle mosse migliora l’efficienza
 del pruning
Con “ordine perfetto”, complessità temporale = O(bm/2)
 doppia profondità di ricerca
 Può facilmente raggiungere profondità 8 e giocare
bene a scacchi
Slides di Teoria dei Giochi,
Vincenzo Cutello
18
Perché si chiama α-β ?
MAX
MIN
..
..
..
..
α
MAX
MIN
V
α è il miglior valore (rispetto a MAX) trovato fino ad ora nel
percorso corrente
Se V è peggiore di α, MAX lo eviterà  pota quel ramo
Definiamo β similmente per MIN
Slides di Teoria dei Giochi,
Vincenzo Cutello
19
L’algoritmo α-β
function MAX-VALUE(stato, gioco, α, β)
returns il valore minimax di stato
inputs: stato, stato corrente del gioco
gioco, descrizione del gioco
α, il miglior punteggio per MAX attrraverso il percorso per stato
β, il miglior punteggio per MIN attraverso il percorso per stato
if TEST-DI-TAGLIO(stato) then return EVAL(stato)
for each s in SUCCESSORI (stato) do
α  MAX(α, MIN-VALUE(s, gioco, α, β))
if α ≥ β then return β
end
return α
_____________________________________________________________________
function MIN_VALUE (stato, game, α, β)
returns il valore minimax di stato
if TEST-DI-TAGLIO(stato) then return EVAL(stato)
for each s in SUCCESSORI(stato) do
β  MIN (β, MAX-VALUE (s, gioco, α, β))
if β ≤ α then return α
end
Slides di Teoria dei Giochi,
Vincenzo Cutello
return β
20
Giochi deterministici in pratica
 Dama:
– Chinook pose termine al dominio assoluto durato 40 anni della
campionessa del mondo Marion Tinsley in 1994.
– Venne usato un database per le posizioni finali che definiva una
strategia perfetta per tutte le posizioni che coinvolgevano al più 8
pezzi sulla scacchiera per un totale di 443.748.401.247 posizioni.
 Scacchi:
– Deep Blue sconfisse il campione del mondo Gary Kasparov nel
1997.
– Deep Blue ricercava 200 milioni di posizioni al secondo, una
valutazione molto sofisticata e alcuni metodi per estendere la
ricerca fino a 40 mosse
Slides di Teoria dei Giochi,
Vincenzo Cutello
21
Giochi deterministici in pratica
 Othello: I campioni umani rifiutano di
competere contro i computer perché sono di
gran lunga superiori.
 Go: I campioni umani rifiutano di competere
contro i computer perché sono troppo
scarsi.
 Nel Go, b > 300, così la maggior parte dei
programmi usa basi di conoscenza per
effettuare delle mosse plausibili.
Slides di Teoria dei Giochi,
Vincenzo Cutello
22
Giochi non deterministici
Per esempio, nel risico, i dadi determinano le mosse legali
Esempio semplificato con lancio della moneta al posto dei dadi
MAX
CHANCE
-1
2.5
0.5
1
MIN
1
0.5
0.5
0
4
4
7
0.5
4
6
Slides di Teoria dei Giochi,
Vincenzo Cutello
-2
0
5
-2
23
Algoritmo per giochi non
deterministici
EXPECTIMINIMAX fornisce un giocatore perfetto
Come il MINIMAX eccetto per il fatto che dobbiamo
gestire i nodi di fortuna
…
if stato è un nodo di fortuna then
return la media di EXPECTIMINIMAX-VALUE
di SUCCESSORI(stato)
…
Slides di Teoria dei Giochi,
Vincenzo Cutello
24
Giochi non deterministici nella
pratica
 Il lancio dei dadi incrementa b:
– 11 possibili risultati con 2 dadi
 Mentre la profondità incrementa la
probabilità di raggiungere un dato nodo
diminuisce
 diminuisce il valore di lookahead
 α-β pruning è meno efficace in questo caso
Slides di Teoria dei Giochi,
Vincenzo Cutello
25
Valori esatti necessari
Il comportamento è preservato solo da trasformazioni lineari
positive di EVAL
Quindi EVAL dovrebbe essere proporzionale al payoff atteso
MAX
CHANCE
MIN
2
2.1
21
1.3
0.9
0.1
0.9
0.1
2
3
1
4
2 3
3 1
1 4
4 20
Slides di Teoria dei Giochi,
Vincenzo Cutello
40.9
0.9
0.1
0.9
0.1
20
30
1
400
20 30
30 1
1 400 400
26
Riassunto
I giochi sono divertenti ! (e pericolosi)
Tramite essi si illustrano parecchi importanti
questioni inerenti l’AI
 La perfezione non è ottenibile ==> dobbiamo approssimare
 Buona idea per pensare su cosa occorre pensare
 L’incertezza vincola l’assegnamento del valore agli stati
PENSIERO FINALE:
I giochi stanno all’AI
come la Formula 1 sta all’industria automobilistica
Slides di Teoria dei Giochi,
Vincenzo Cutello
27