Esempi di giochi
Puzzles e giochi a informazione
perfetta
Slides di Teoria dei Giochi,
Vincenzo Cutello
1
Sliding tiles: Euristiche
H1(n) = numero di tessere sbagliate
H2(n) = somma delle distanze di Manhattan
(cioè, il numero di caselle da quella desiderata di ogni
tessera)
5
1
6
8
13
2
10 15 7
11 14 12
9
3
4
1
2
3
4 5 6 7
8 9 10 11
12 13 14 15
Stato iniziale
Stato finale
H1(S) = ??
H2(S) = ??
Slides di Teoria dei Giochi,
Vincenzo Cutello
2
Sliding tiles: Euristiche migliori?
 Tutte le euristiche ammissibili ma il meno ottimistiche possibili.
 Come fare a migliorare ?
 Per esempio: Manhattan distance ignora le interazioni tra le caselle. Se
ne teniamo conto, almeno in parte, che succede ?
5
1
6
8
13
2
10 15 7
11 14 12
9
3
4
1
2
3
4 5 6 7
8 9 10 11
12 13 14 15
Stato iniziale
Stato finale
H1(S) = ??
H2(S) = ??
Slides di Teoria dei Giochi,
Vincenzo Cutello
3
Non-additive pattern db


Considera le caselle di confine (più quella vuota)
Qual è il numero minimo (esatto) di mosse da fare tenendo conto delle loro posizioni, ma
non delle posizioni delle altre caselle?
3
13
15 7
11 14 12



3
7
11
12 13 14 15
Stato iniziale
Stato finale
Calcoliamo questo numero per ognuna delle possibili permutazioni delle
caselle di confine: 16!/(16-8)!=518.918.400
Memorizziamo in una tabella: circa 495MB di spazio.
Come facciamo a calcolare tale numero minimo di mosse?
Slides di Teoria dei Giochi,
Vincenzo Cutello
4
Non-additive pattern db


Utilizziamo una BFS a partire dallo stato finale.
Ognuna delle configurazioni viene incontrata e la sua distanza minima calcolata
(proprietà della BFS)
3
3
3
7
11
12 13 14 15
7
11
12 13 14 15
7
11
12 13 14 15
Stato finale


d=1
d=1
Memorizziamo in una tavola indicizzata
Utilizziamo la distanza di Manhattan per le altre caselle
Slides di Teoria dei Giochi,
Vincenzo Cutello
5
Non-additive pattern db
 Risultati:
– Numero dei nodi generati ridotto din un fattore 346
– Running time ridotto di un fattore 6
– Se confrontanti solo con la Manhattan Distance
 Limiti
– Non si riescono a risolvere problemi grandi.
– Esempio: il puzzle 24, contiene 25 posizioni, e le posizioni delle
caselle di confine sono 25!/(25-10)! Numero troppo grande (provare
per credere)
Slides di Teoria dei Giochi,
Vincenzo Cutello
6
Sliding tiles: Disjoint pattern DB
 Estendiamo la distanza di Manhattan, invece di una casella singola,
gruppi di caselle.
 Nell’esempio, un gruppo di 7 (casella vuota esclusa) e un gruppo di 8
5
1
6
8
13
2
10 15 7
11 14 12
9
3
4
1
2
3
4 5 6 7
8 9 10 11
12 13 14 15
Stato iniziale: gruppo 1 e 2
Stato finale
 Vi sono 57.657.600 gruppi da 7 (da 0 a 33 mosse) e
518.918.400 gruppi da 8 (da 0 a 38 mosse).
Slides di Teoria dei Giochi,
Vincenzo Cutello
7
Puzzles: Sokoban
 Il giocatore deve spingere i pezzi attraverso un labirinto e portarli nel
posto finale
 Solo un pezzo alla volta può essere spinto
 Gli altri pezzi ed i muri sono ostacoli contro cui non si può spingere.
 Goal:
– Risolvere il puzzle
– Minimizzare spinte e mosse
Slides di Teoria dei Giochi,
Vincenzo Cutello
8
Sokoban cont.
 Sokoban è un problema NP-hard, e
addirittura, PSPACE-complete.
 Problema generale di motion-planning
Slides di Teoria dei Giochi,
Vincenzo Cutello
9
Sokoban: cont.

Cosa rende Sokoban difficile ?
Slides di Teoria dei Giochi,
Vincenzo Cutello
10
Sokoban: cosa lo rende difficile?


Alcune mosse sono irreversibili e possono
portare ad uno stato di stallo
Lo spazio di ricerca, su una griglia sottostante
20X20 è enorme (come vedremo).
Slides di Teoria dei Giochi,
Vincenzo Cutello
11
Sokoban: come attaccarlo ?




Knowledge representation
Algoritmi di ricerca
Capacità di apprendimento
Gestione di eccezioni e sub-goals.
Slides di Teoria dei Giochi,
Vincenzo Cutello
12
Sokoban: complessità ?
15-Puzzle
Cubo di Rubik
Sokoban
Branching
Factor
4
18
144
Lunghezza
soluzione
53 (1-80)
18 (1-20)
260 (97-674)
Dimensione
spazio di
ricerca
10**13
10**19
10**98
Complessità A*
O(n) -> O(1)
O(n) -> O(1)
O(n**3) ->
O(n**2)
Grafo
Non orientato
Non orientato
Orientato
Slides di Teoria dei Giochi,
Vincenzo Cutello
13
Due semplici problemi: complessità?
 Qual è la dimensione dello spazio di ricerca in entrambi i
casi ?
– 1000 (pushes)
– 23000 (pushes)
 Poca speranza senza usare conoscenza specifica
Slides di Teoria dei Giochi,
Vincenzo Cutello
14
Sokoban cont.
 Sokoban può essere attaccato con versioni
appropriate di IDA*, estese con tecniche di
conoscenza specifiche del dominio.
 I livelli più complessi di Sokoban sono
ancora fuori dalla portata di un sistema
automatico di risoluzione.
Slides di Teoria dei Giochi,
Vincenzo Cutello
15
Tavole per i deadlocks
 Calcolare gli angoli morti.
 Costruire una tavola per gli stalli.
 Riduzione del branching factor
Slides di Teoria dei Giochi,
Vincenzo Cutello
16
Analisi dinamica dei deadlock


Quale mossa può portare ad un deadlock?
Risolvi aggiungendo una “pietra” alla volta
Slides di Teoria dei Giochi,
Vincenzo Cutello
17
Analisi dinamica dei deadlock
Slides di Teoria dei Giochi,
Vincenzo Cutello
18
Analisi dinamica dei deadlock

Introduci una “penalità” per la mossa che porta
ad uno stallo
Slides di Teoria dei Giochi,
Vincenzo Cutello
19
Tavole di trasposizione

Riconosci sequenze di mosse
già fatte.
Slides di Teoria dei Giochi,
Vincenzo Cutello
20
Dentro un tunnel !


Quando sei in un tunnel non puoi che
continuare sino a quando non esci dal
tunnel.
Verifica se il tunnel è a senso unico o a
doppio senso
Slides di Teoria dei Giochi,
Vincenzo Cutello
21
Goal Area: suddivisione del problema


Problema 1: porta le pietre all’ingresso
Problema 2: sistema le pietre nella zona
finale
Slides di Teoria dei Giochi,
Vincenzo Cutello
22
Suddivisione del problema: tagli


Non è necessario considerare tutte le mosse
legali.
Solo quelle rilevanti per la risoluzione del
sotto-problema
Slides di Teoria dei Giochi,
Vincenzo Cutello
23
Giochi a informazione perfetta: Othello


Othello (anche detto Reversi) è
un gioco da tavolo astratto a
informazione perfetta, per due
giocatori.
Ogni giocatore dispone di 32
dischi bicolori (neri da un lato,
bianchi dall'altro) ed il terreno di
gioco è costituito da una tavola
quadrata di 8 x 8 caselle di colore
uniforme.
Slides di Teoria dei Giochi,
Vincenzo Cutello
24
Othello cont.


Prima di iniziare a giocare si posizionano
due pedine bianche e due nere nelle
quattro caselle centrali.
Regole:
–
–
–
Si muove alternativamente (inizia il nero)
appoggiando una nuova pedina in una casella
vuota in modo da imprigionare, tra la pedina che
si sta giocando e quelle del proprio colore già
presenti sulla scacchiera, una o più pedine
avversarie.
A questo punto le pedine imprigionate devono
essere rovesciate e diventano di proprietà di chi
ha eseguito la mossa.
È possibile incastrare le pedine in orizzontale, in
verticale e in diagonale e, a ogni mossa, si
possono girare pedine in una o più direzioni.
Slides di Teoria dei Giochi,
Vincenzo Cutello
25
Othello: cont.

Sono ammesse solo le mosse con le quali si gira
almeno una pedina, se non è possibile farlo si
salta il turno.

Quando nessuno dei giocatori ha la possibilità di
muovere (quasi sempre accade quando la
scacchiera è piena), si contano le pedine e si
assegna la vittoria a chi ne ha il maggior numero.
Slides di Teoria dei Giochi,
Vincenzo Cutello
26
Othello: cont.
 I migliori programmi per Othello vincono
facilmente contro esseri umani.
 Nel 1997, Logistello sconfisse il campione
mondiale Takeshi Murakami per 6:0.
 Esseri umani non riescono a vincere contro
i programmi perché riescono a guardare
avanti nell’albero del gioco in grande
profondità.
Slides di Teoria dei Giochi,
Vincenzo Cutello
27
Othello: cont.





Da un punto di vista matematico, Othello è
ancora insoluto.
E’ un gioco finito a informazione perfetta. Esiste
una strategia vincente ?
Ipotesi: su una scacchiera (othelliera) 8 per 8 la
migliore strategia per entrambi i giocatori porta
ad un pareggio.
In generale, n per n, il problema di determinare
se il primo a muovere ha una strategia vincente è
PSPACE-complete.
Per 4 per 4, e 6 per 6 il secondo giocatore ha
una strategia vincente.
Slides di Teoria dei Giochi,
Vincenzo Cutello
28