Esercizio - Euristiche dell'8-puzzle e fattore di diramazione effettivo (slide del corso)

Esercizio ricavato dalle slide del corso di Intelligenza Artificiale, Ing. dell'Informazione UniPD, sul puzzle dell'8: calcolo delle due euristiche (tessere fuori posto e distanza di Manhattan) sullo stato delle slide, prime espansioni di A∗, dominanza, fattore di diramazione effettivo $b^\ast$ con i dati misurati. Teoria in Ricerca informata - greedy best-first, A* ed euristicheLa ricerca informata usa una funzione euristica h(n) che stima il costo da n all'obiettivo. Greedy best-first espande il nodo con h minima (f = h): veloce ma non ottima né in generale completa. A∗ usa f = g + h e, con h ammissibile (mai sopra il costo vero) e, sul grafo con tabella dei raggiunti, consistente, è completa e ottima; il fattore di diramazione effettivo b∗ misura la qualità di h, e un'euristica che ne domina un'altra espande meno nodi. A∗ pesato (f = g + W h) rinuncia all'ottimalità per espandere meno nodi. Per i problemi in cui conta solo lo stato finale esiste la ricerca locale (hill climbing, simulated annealing, beam search, algoritmi genetici). In appendice, cenni di ricerca avversaria (minimax e potatura alfa-beta).Ricerca informata - greedy best-first, A* ed euristiche →; la formulazione del problema è in Ricerca nello spazio degli stati - formulazione dei problemi e ricerca non informataUn agente risolutore di problemi è un agente basato su obiettivi con rappresentazione atomica: formula un problema (stato iniziale, azioni, modello di transizione, test dell'obiettivo, costo dei passi) e cerca una sequenza di azioni che porta a uno stato obiettivo costruendo un albero di ricerca. Le strategie non informate usano solo la definizione del problema e si distinguono per l'ordine di espansione della frontiera: ampiezza (coda FIFO), costo uniforme (coda con priorità sul costo g), profondità (pila LIFO), profondità limitata, approfondimento iterativo e ricerca bidirezionale. Si confrontano per completezza, ottimalità, tempo e spazio in funzione di b, d, m; tutte sono casi di best-first search con una diversa funzione di valutazione f.Ricerca nello spazio degli stati - formulazione dei problemi e ricerca non informata →. Tutti i numeri sono verificati con il programma in fondo.

Testo

Si consideri il puzzle dell'8 con stato iniziale $S$ e obiettivo come in figura (la casella vuota è _):

$$S = \begin{matrix} 7 & 2 & 4 \\ 5 & \_ & 6 \\ 8 & 3 & 1 \end{matrix} \qquad \text{obiettivo} = \begin{matrix} \_ & 1 & 2 \\ 3 & 4 & 5 \\ 6 & 7 & 8 \end{matrix}$$

1. Calcolare $h_1(S)$ (numero di tessere fuori posto) e $h_2(S)$ (distanza di Manhattan totale: per ogni tessera da 1 a 8, il numero di caselle, righe più colonne, dalla posizione finale).
2. Mostrare che $h_1$ e $h_2$ sono ammissibili e che $h_2$ domina $h_1$.
3. Con A∗ e $h_2$, scrivere i quattro successori di $S$ con $g$, $h$, $f$.
4. Risolvere con ampiezza, A∗($h_1$) e A∗($h_2$) e confrontare i nodi generati e il fattore di diramazione effettivo.
5. Verificare con la definizione i valori di $b^\ast$ della tabella delle slide.

Punto 1 - le due euristiche

Posizioni come (riga, colonna) da $(0, 0)$ in alto a sinistra. In $S$: 7 in $(0,0)$, 2 in $(0,1)$, 4 in $(0,2)$, 5 in $(1,0)$, vuoto in $(1,1)$, 6 in $(1,2)$, 8 in $(2,0)$, 3 in $(2,1)$, 1 in $(2,2)$. Nell'obiettivo: 1 in $(0,1)$, 2 in $(0,2)$, 3 in $(1,0)$, 4 in $(1,1)$, 5 in $(1,2)$, 6 in $(2,0)$, 7 in $(2,1)$, 8 in $(2,2)$.

Tutte le 8 tessere sono fuori posto: $h_1(S) = 8$. La somma delle distanze è $$h_2(S) = 3 + 1 + 2 + 2 + 2 + 3 + 3 + 2 = 18,$$ come nella slide. La casella vuota non si conta (non è una tessera).

Punto 2 - ammissibilità e dominanza

Ogni mossa sposta una tessera di una casella. Quindi:

• una tessera fuori posto richiede almeno una mossa: servono almeno $h_1(n)$ mosse, $h_1(n) \le h^\ast(n)$;
• una tessera a distanza di Manhattan $d$ dalla sua casella richiede almeno $d$ mosse, e ogni mossa avvicina una sola tessera: servono almeno $h_2(n)$ mosse, $h_2(n) \le h^\ast(n)$.

Entrambe valgono 0 solo nell'obiettivo: sono ammissibili. Dominanza: una tessera fuori posto ha distanza di Manhattan almeno 1, quindi $h_2(n) \ge h_1(n)$ per ogni stato (verificato anche su 2000 stati casuali). Quindi $h_2$ domina $h_1$ e A∗($h_2$) espande al più i nodi di A∗($h_1$), perché A∗ espande tutti i nodi con $f(n) < C^\ast$ (e alcuni con $f = C^\ast$), e $f_2 \ge f_1$. Qui $h_2(S) = 18 > h_1(S) = 8$.

Euristiche da problemi rilassati. $h_1$ è il costo esatto del problema in cui una tessera può saltare dovunque in una mossa; $h_2$ è il costo esatto di quello in cui una tessera si può muovere di una casella anche sopra una casella occupata. Meno vincoli, costo minore: per questo non sovrastimano.

Punto 3 - i successori di $S$ con A∗($h_2$)

Il vuoto è in $(1,1)$ e ha quattro mosse. Ogni successore ha $g = 1$ (un passo di costo 1).

Come cambia $h_2$: spostare la tessera 2 verso il basso la allontana dalla sua casella $(0,2)$ (distanza da 1 a 2: $h_2 = 19$); spostare la 3 verso l'alto la avvicina ($(2,1) \to (1,1)$, distanza da 2 a 1) e così per la 5 e la 6: $h_2 = 17$. Tre successori hanno la stessa $f = 18$: A∗ ne sceglie uno secondo la regola di pareggio. Si noti che $f = 18$ è anche $h_2(S)$: nessuna mossa ha peggiorato la stima. Con $h_2$ consistente ogni mossa cambia $h_2$ di $\pm 1$, quindi $f$ non decresce lungo un cammino e arriva a $26$ sull'obiettivo.

Punto 4 - risoluzione e confronto

Soluzione ottima: 26 mosse (il vuoto: sinistra, su, destra, giù, giù, sinistra, su, destra, destra, su, sinistra, sinistra, giù, destra, destra, giù, sinistra, sinistra, su, destra, destra, su, sinistra, giù, sinistra, su; rieseguendo le mosse si arriva all'obiettivo; con un altro criterio di pareggio la sequenza può cambiare, la lunghezza no, ed è confermata dall'ampiezza). Nodi generati (con tabella dei raggiunti) e $b^\ast$ risolvendo $N + 1 = \sum_{i=0}^{26} (b^\ast)^i$:

A∗($h_2$) genera circa 10 volte meno nodi di A∗($h_1$) e circa 29 volte meno dell'ampiezza, e il suo fattore di diramazione effettivo è il più vicino a 1 (il fattore di diramazione massimo del puzzle è 4, con il vuoto al centro). Una sola esecuzione, non una media su 100 puzzle come nelle slide: i valori hanno lo stesso ordine di grandezza della riga $d = 26$ della tabella ($b^\ast$: $1{,}58$, $1{,}50$, $1{,}35$).

Con il peso. Con $f = g + W h_2$, sullo stesso $S$: $W = 1{,}4$ trova ancora 26 mosse con 1202 nodi; $W = 2$ trova 30 mosse con 638 nodi (circa 10 volte meno nodi, il 15% di mosse in più): meno nodi ma niente ottimo (Ricerca informata - greedy best-first, A* ed euristicheLa ricerca informata usa una funzione euristica h(n) che stima il costo da n all'obiettivo. Greedy best-first espande il nodo con h minima (f = h): veloce ma non ottima né in generale completa. A∗ usa f = g + h e, con h ammissibile (mai sopra il costo vero) e, sul grafo con tabella dei raggiunti, consistente, è completa e ottima; il fattore di diramazione effettivo b∗ misura la qualità di h, e un'euristica che ne domina un'altra espande meno nodi. A∗ pesato (f = g + W h) rinuncia all'ottimalità per espandere meno nodi. Per i problemi in cui conta solo lo stato finale esiste la ricerca locale (hill climbing, simulated annealing, beam search, algoritmi genetici). In appendice, cenni di ricerca avversaria (minimax e potatura alfa-beta).Ricerca informata - greedy best-first, A* ed euristiche →).

Punto 5 - i $b^\ast$ delle slide

La tabella delle slide (dati medi su 100 puzzle per ogni profondità $d$) dà il numero di nodi generati e $b^\ast$. Risolvendo $N + 1 = 1 + b^\ast + \dots + (b^\ast)^d$ per $N$ e $d$ date si ritrovano i valori stampati. Esempi:

• $d = 6$: BFS $N = 128$: $129 = 1 + b + \dots + b^6$ dà $b^\ast = 2{,}01$; A∗($h_1$) $N = 24$ dà $1{,}42$; A∗($h_2$) $N = 19$ dà $1{,}34$.
• $d = 14$: BFS 6783 dà $1{,}77$; A∗($h_1$) 678 dà $1{,}47$; A∗($h_2$) 174 dà $1{,}31$.
• $d = 28$: BFS 463 234 dà $1{,}53$; A∗($h_1$) 202 565 dà $1{,}49$; A∗($h_2$) 22 055 dà $1{,}36$.

Su tutte le 12 righe (da $d = 6$ a $d = 28$) i 36 valori calcolati coincidono con quelli delle slide, salvo due scarti di $0{,}01$ (A∗($h_2$) per $d = 10$: $1{,}28$ invece di $1{,}27$; per $d = 16$: $1{,}33$ invece di $1{,}32$), dovuti all'arrotondamento dei dati medi.

Per ogni profondità $d$ della tabella A∗($h_2$) ha $b^\ast$ tra $1{,}27$ e $1{,}36$, contro $1{,}42$-$1{,}50$ di A∗($h_1$): l'euristica più informata tiene $b^\ast$ più vicino a 1.

Programma di verifica

import heapq, itertools

S = (7, 2, 4, 5, 0, 6, 8, 3, 1)       # 0 = casella vuota
G = (0, 1, 2, 3, 4, 5, 6, 7, 8)

def successori(s):
    z = s.index(0); r, c = divmod(z, 3)
    for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
        rr, cc = r + dr, c + dc
        if 0 <= rr < 3 and 0 <= cc < 3:
            l = list(s); l[z], l[rr*3 + cc] = l[rr*3 + cc], l[z]
            yield tuple(l)

def h1(s): return sum(1 for i, t in enumerate(s) if t and t != G[i])
def h2(s):
    return sum(abs(i//3 - G.index(t)//3) + abs(i%3 - G.index(t)%3) for i, t in enumerate(s) if t)

def astar(start, h, w=1):
    conta = itertools.count()
    fr = [(w*h(start), next(conta), 0, start)]
    best = {start: 0}
    generati = 1
    while fr:
        f, _, g, s = heapq.heappop(fr)
        if g > best[s]: continue
        if s == G: return g, generati
        for t in successori(s):
            if t not in best or g + 1 < best[t]:
                best[t] = g + 1; generati += 1
                heapq.heappush(fr, (g + 1 + w*h(t), next(conta), g + 1, t))

def b_star(N, d):                     # N + 1 = 1 + b + ... + b^d, per bisezione
    lo, hi = 1.0001, 10
    for _ in range(100):
        m = (lo + hi) / 2
        if sum(m**i for i in range(d + 1)) < N + 1: lo = m
        else: hi = m
    return lo

print(h1(S), h2(S))                                 # 8 18
for nome, h in (('h1', h1), ('h2', h2)):
    d, N = astar(S, h)
    print(nome, d, N, round(b_star(N, d), 3))       # h1 26 62570 1.463 / h2 26 6130 1.325
print(astar(S, h2, w=1.4), astar(S, h2, w=2))       # (26, 1202) (30, 638)
print(round(b_star(24, 6), 2), round(b_star(12, 2), 2))   # 1.42 3.0