Esercizio - Formulazione delle 8 regine, hill climbing e simulated annealing (slide del corso)

Esercizio ricavato dalle slide del corso di Intelligenza Artificiale, Ing. dell'Informazione UniPD, sul problema delle 8 regine: dimensione dello spazio degli stati nelle due formulazioni, calcolo dell'euristica $h$ sullo stato della slide, minimi locali, hill climbing e simulated annealing. Teoria 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 → (formulazione) e 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 → (ricerca locale). Tutti i numeri sono stati verificati con i programmi sotto.

Testo

Mettere 8 regine su una scacchiera $8 \times 8$ in modo che nessuna ne attacchi un'altra (due regine si attaccano se stanno sulla stessa riga, colonna o diagonale).

1. Formulazione 1: stati = qualunque disposizione di 0-8 regine; azione = aggiungere una regina in una casella vuota. Quante sequenze di azioni (disposizioni di 8 regine una dopo l'altra) vanno esaminate? Formulazione 2: stati = disposizioni di $n$ regine, una per colonna nelle $n$ colonne più a sinistra, senza attacchi; azione = aggiungere una regina in una casella non attaccata della colonna vuota più a sinistra. Quanti stati?
2. Nella ricerca locale uno stato ha 8 regine, una per colonna, e $h$ è il numero di coppie di regine che si attaccano; i vicini si ottengono muovendo una regina dentro la sua colonna. Lo stato della slide ha le regine nelle righe $q = (4, 5, 6, 3, 4, 5, 6, 5)$ (colonne da sinistra a destra, righe dall'alto a partire da 0). Calcolare $h$ e il numero di vicini.
3. Dire quali sono le mosse migliori e il loro $h$; dire se l'hill climbing si può bloccare.
4. Lo stato $(7, 2, 6, 3, 1, 4, 0, 5)$ ha $h = 1$: è una soluzione? Che cosa succede all'hill climbing?
5. Eseguire hill climbing da stati casuali e simulated annealing, e confrontare le percentuali di successo.

Punto 1 - la formulazione conta

Formulazione 1. Si aggiungono regine una alla volta in una casella vuota qualsiasi: la prima ha 64 posizioni, la seconda 63, ..., l'ottava 57. Le sequenze sono $$64 \cdot 63 \cdot 62 \cdot 61 \cdot 60 \cdot 59 \cdot 58 \cdot 57 = \frac{64!}{56!} = 178\,462\,987\,637\,760 \approx 1{,}8 \cdot 10^{14}.$$

Formulazione 2. Una regina per colonna, a partire dalla colonna 0, in una casella non attaccata. Le colonne si riempiono in ordine, quindi uno stato è determinato dalle righe delle prime $n$ colonne: il numero di stati si conta con una ricorsione sulle colonne:

def ok(q, r):                       # la regina in riga r nella colonna len(q) è attaccata?
    c = len(q)
    return all(r != qr and abs(r - qr) != c - i for i, qr in enumerate(q))

stati = soluzioni = 0
def rec(q):
    global stati, soluzioni
    stati += 1
    if len(q) == 8:
        soluzioni += 1
        return
    for r in range(8):
        if ok(q, r):
            rec(q + [r])

rec([])
print(stati, soluzioni)             # 2057 92

2057 stati, di cui 92 sono soluzioni complete (8 regine). La seconda formulazione ha 2057 stati contro $1{,}8 \cdot 10^{14}$ sequenze: la prima enumera anche disposizioni con regine che si attaccano a metà strada, la seconda le vieta subito. Con la seconda anche l'ampiezza o la profondità risolvono il problema in un istante.

Punto 2 - $h$ dello stato della slide

$q = (4, 5, 6, 3, 4, 5, 6, 5)$: la regina della colonna $c$ è nella riga $q_c$. Due regine nelle colonne $i < j$ si attaccano se $q_i = q_j$ (stessa riga) o $\lvert q_i - q_j\rvert = j - i$ (stessa diagonale; stessa colonna è impossibile). Controllando tutte le $\binom{8}{2} = 28$ coppie:

• stessa riga (5 coppie): colonne $(0,4)$ riga 4; $(1,5)$ e $(1,7)$ e $(5,7)$ riga 5; $(2,6)$ riga 6;
• stessa diagonale (12 coppie): $(0,1)$, $(0,2)$, $(1,2)$, $(1,3)$, $(2,4)$, $(3,4)$, $(3,5)$, $(3,6)$, $(4,5)$, $(4,6)$, $(5,6)$, $(6,7)$.

Totale $h = 5 + 12 = \mathbf{17}$ coppie, come nella slide. Esempio di controllo: colonne $(3, 5)$: $\lvert 3 - 5 \rvert = 2 = 5 - 3$, diagonale. Le regine attaccate sono 8 su 8 (tutte hanno almeno un'attaccante): il numero 17 conta le coppie, non le regine (la slide lo descrive come "somma delle regine sotto attacco", ma le regine sotto attacco sono 8; 17 è il numero di coppie in conflitto). I vicini sono $8 \cdot 7 = 56$: 8 colonne, 7 righe alternative.

Punto 3 - le mosse migliori

Si calcola $h$ per tutti i 56 vicini (la slide mostra la scacchiera con i valori). Esempi: la regina della colonna 0 spostata in riga 0 dà $h = 18$ (peggiora); la colonna 1 in riga 1 dà $16$; la colonna 2 in riga 0 dà $14$; la colonna 7 in riga 7 dà $18$. Il minimo è $h = 12$, raggiunto da 8 mosse (colonna, riga di arrivo): $(1,0)$, $(1,2)$, $(4,1)$, $(4,7)$, $(5,0)$, $(5,2)$, $(6,1)$, $(6,7)$. L'hill climbing ne sceglie una (a caso tra le 8) e passa a $h = 12$.

L'hill climbing si può bloccare perché guarda solo i vicini: in uno stato dove tutti i vicini hanno $h$ maggiore o uguale, termina anche se $h > 0$ (minimo locale per $h$, massimo locale per $-h$).

Punto 4 - un minimo locale

Stato $(7, 2, 6, 3, 1, 4, 0, 5)$: l'unica coppia in conflitto è quella delle colonne $(3, 6)$ (righe 3 e 0, differenza $3 = 6 - 3$: stessa diagonale), la coppia cerchiata nella slide. Quindi $h = 1$: non è una soluzione. Dei suoi 56 vicini, nessuno ha $h < 2$ (il minimo è $h = 2$, raggiunto da 15 mosse): non si può migliorare con una mossa sola, quindi l'hill climbing si ferma. Per eliminare il conflitto bisogna spostare più di una regina passando da stati con $h$ maggiore: il paesaggio ha un minimo locale con $h = 1$ e quelli globali ($h = 0$) lontani.

Punto 5 - esperimenti

import random, math

def h(q):                      # q[c] = riga della regina nella colonna c; coppie di regine che si attaccano
    return sum(q[i] == q[j] or abs(q[i] - q[j]) == j - i
               for i in range(8) for j in range(i + 1, 8))

def successori(q):             # muovere una regina dentro la sua colonna: 8 * 7 = 56 vicini
    return [q[:c] + [r] + q[c + 1:] for c in range(8) for r in range(8) if r != q[c]]

def hill_climbing(q):
    passi = 0
    while True:
        migliore = min(h(n) for n in successori(q))
        if migliore >= h(q):                      # nessun vicino migliore: minimo locale
            return q, passi
        q = random.choice([n for n in successori(q) if h(n) == migliore])
        passi += 1

def simulated_annealing(q, T=2.0, alpha=0.995, Tmin=1e-3):
    while T > Tmin:
        if h(q) == 0: return q
        c, r = random.randrange(8), random.randrange(8)
        n = q[:c] + [r] + q[c + 1:]
        dE = h(q) - h(n)                          # valore = -h: dE > 0 se n è migliore
        if dE > 0 or random.random() < math.exp(dE / T):
            q = n
        T *= alpha
    return q

random.seed(0)
casuale = lambda: [random.randrange(8) for _ in range(8)]
q = [4, 5, 6, 3, 4, 5, 6, 5]                      # stato della slide
print(h(q), min(h(n) for n in successori(q)), sum(h(n) == 12 for n in successori(q)))
prove = [hill_climbing(casuale()) for _ in range(2000)]
riusciti = [p for q, p in prove if h(q) == 0]
print(len(riusciti) / 2000, sum(riusciti) / len(riusciti))
sa = [simulated_annealing(casuale()) for _ in range(500)]
print(sum(h(q) == 0 for q in sa) / 500)

Output (con random.seed(0)):

17 12 8
0.138 4.108695652173913
0.816

Risultati:

• Hill climbing più ripido: da stati casuali arriva a $h = 0$ nel 13,8% dei casi (2000 prove) e in quel caso impiega in media 4,1 passi; nell'86,2% restanti si blocca in un minimo locale. Con i riavvii casuali (si rilancia finché riesce) servono in media $1/0{,}138 \approx 7{,}2$ lanci; una simulazione di 300 serie di riavvii ne ha dati 6,9 in media. Ogni lancio costa pochi passi, quindi anche con i riavvii il problema è risolto in un istante, mentre ci sono $8^8 = 16\,777\,216$ stati.
• Simulated annealing con $T_0 = 2$, $T_{t+1} = 0{,}995\,T_t$ fino a $T < 10^{-3}$ (circa 1500 passi): trova una soluzione nell'81,6% dei casi (500 prove). Accetta anche mosse peggiorative con probabilità $e^{\Delta E/T}$: a $T = 2$ un peggioramento di 1 passa con probabilità $e^{-1/2} \approx 0{,}61$, a $T = 0{,}1$ con $e^{-10} \approx 4{,}5 \cdot 10^{-5}$ (quindi l'algoritmo si comporta come un hill climbing nella fase finale).

Confronto. Senza riavvii il simulated annealing ha successo 6 volte più spesso dell'hill climbing (81,6% contro 13,8%), pagando circa 1500 passi per tentativo contro i ~4 dell'hill climbing: ogni passo di annealing costa il calcolo di un solo vicino, quello dell'hill climbing 56 valutazioni. Con i riavvii l'hill climbing è competitivo su problemi piccoli come questo; il vantaggio dell'annealing si vede quando i minimi locali sono tanti e i riavvii non bastano.