3 Ricerca per Giochi e CSP - home.deib.polimi.it · Esercizio 3.5 Applicare gli algoritmi di...

3 Ricerca per Giochi e CSP

Esercizio 3.1

Dire quale tecnica usereste per risolvere i seguenti giochi:

1. Backgammon

2. Scarabeo

3. Scacchi

4. Go

5. Monpoli

6. Poker

Motivate le risposte con adeguate ragioni basate sulle caratteristiche del gioco.

Esercizio 3.2

Considerare un problema in cui due ropicapi spaccaquindici devono essere risolti.

1. Fornire la formulazione del problema di ricerca.

2. Quanto è grande lo spazio degli stati?

3. Formulare il problema come un gioco in cui due giocatori giocano a turno e lascelta su quale dei due spaccaquindici deve essere modificato è dato dal lancio diuna moneta (bilanciata). Il gioco finisce quando uno dei due giocatori finisce unodei due rompicapi.

4. Quale algoritmo potreste usare per risolvere il gioco?

5. Come finirà il gioco se entrambi giocatori massimizzassero il proprio valore attesodi vittoria?

Motivate le risposte.

Esercizio 3.3

1


Considerare il seguente gioco: due agenti muovono sul seguente grafo a turni:

Il giocatore G (guardia) deve cercare di arrivare sul nodo di L (ladro) mentre il ladrodeve cercare di non farsi prendere. Il costo della guardia è pari al numero di passi fattidai due giocatori prima della cattura.

1. Costruire un albero di ricerca che rappresenti il gioco descritto fino al secondolivello.

2. Calcolare il valore dei nodi per il giocatore G

3. Possiamo dare un limite inferiore al valore del gioco?

4. Possiamo dire qualcosa sull’esito del gioco?

Motivate le risposte.

Esercizio 3.4

Mostrare un esempio di strategia subottima in un gioco MAX-MIN che ottiene più uti-lità contro un avversario subottimo di quanta ne ottenga la strategia ottima contro unavversario che gioca in maniera ottima.

Esercizio 3.5

Applicare gli algoritmi di MINIMAX e α-β pruning al seguente albero di gioco:

A.A.2017-2018 Intelligenza Artificiale - UniBG


per trovare la strategia ottima del giocatore MAX.

Esercizio 3.6

Applicare gli algoritmi di MINIMAX e α-β pruning al sequente albero di gioco:

per trovare la strategia ottima del giocatore MAX.

Esercizio 3.7

Considerare il seguente gioco:



in cui ognuno dei due giocatori decide se muovere in avanti o indietro di una posizione(se si trova ai lati del campo di gioco deve necessariamente muoversi). Nel caso incui un giocatore si trovi nella casella adiacente a quella dell’altro pumuoversi nellaprima casella libera dopo il giocatore avversario. Gli stati terminali sono quelli in cuiun giocatore riesce a raggiungere il lato opposto della scacchiera di gioco. Muove perprimo il giocatore A.

1. Disegnare l’albero di ricerca del gioco. Nel caso in cui si raggiungano delle posi-zioni già esplorare non si espanda ulteriormente l’albero.

2. Possiamo usare l’algoritmo MINIMAX per questo gioco? Se sì, applicarlo e tro-vare la strategia per i due giocatori. Se no, proporre una modifica all’algoritmoperché sia applicabile a questo problema.

3. Generalizzare tramite induzione la soluzione del problema nel caso in cui abbia-mo n caselle invece che 4.

Esercizio 3.8

Considerare il seguente gioco con nodi di casualità:



1. Calcolare il valore di ogni nodo

2. Conosciuti i valori dei primi 6 nodi foglia (partendo da sinistra), posso potare gliultimi due nodi?

3. E se conoscessi che il range di valori di utilità nella foglie è nell’intervallo [−2, 2]?

4. Avrei potuto anche non valutare altre foglie?

Esercizio 3.9

Rispondere alle sequenti domande e giustificare appropriatamente la risposta.

1. Un gioco che ha una trasformazione lineare degli outcame di un altro gioco adue giocatori ha la stessa strategia ottima, anche quando sono presenti nodi dicasualità.

2. In un gioco completamente osservabile, a turni, a somma zero tra due giocatorirazionali, è utile per il primo giocatore sapere quale strategia sta utilizzando ilsecondo giocatore.

3. Un agente perfettamente razionale non perderà mai a backgammon.

4. In un gioco parzialmente osservabile, a turni, a somma zero tra due giocatorirazionali, è utile per il primo giocatore sapere quale strategia sta utilizzando ilsecondo giocatore.



Esercizio 3.10

1. Se esiste, l’algoritmo AC-3 trova la soluzione ottima ad un problema di CSP.

2. Un problema di CSP può essere risolto efficientemente con algoritmi di ricercainformata.

3. Specificare l’ordine di assegnamento delle variabili è significativo per la soluzionedi un CSP.

4. Nella rappresentazione ad albero della ricerca di un CSP, un solo stato è quellocorrispondente alla soluzione.

Esercizio 3.11

Formalizzare il problema delle 8 regine come un CSP e risolverlo tramite ricerca inprofondità con MAC (verifica di consistenza d’arco).

Esercizio 3.12

Formalizzare i seguenti problemi come CSP:

1. rectilinear floor planning: trovare all’interno di un rettangolo la posizione di altrirettangoli in modo che non si sovrappongano

2. orario delle lezioni: dato un insieme di professori, di aule, di lezioni e degli oraridelle lezioni, trovare uno schedule delle lezioni. Ricordarsi che ogni professorepotrà tenere solo un sottoinsieme di tutte le possibili lezioni

3. tour hamiltoniano: data una rete di città, trovare un ordine per cui le città vengonotutte visitate una e una sola volta

Esercizio 3.13

Risolvere il problema della colorazione (RGB) del seguente grafo:



Prima di risolvere il problema, quale dei nodi pensate che sia il più critico? Il problemaha una sola soluzione?

Esercizio 3.14

Formalizzare il problema di costruire un cruciverba. Sia dato lo schema iniziale e undizionario di parole ammesse. Come suggerimento valutare se l’azione da compiere èsia l’inserimento di una parola o di una lettera nello schema.

1. Formulare il problema come un problema di ricerca. Specificare se l’utilizzo diun’euristica può essere di aiuto in questo problema specifico.

2. Formulare il problema come un CSP.

3. Quale delle due formulazioni pensate possa essere più efficiente? Perché?

Esercizio 3.15

Mostrare che un vincolo ternario del tipoA+B = C può essere trasformato in tre vincolibinari. Suggerimento: introdurre una nuova variabile che tenga conto dei valori di A eB allo stesso tempo.

Generalizzare il procedimento per vincoli N -ari.



Answers

Soluzione dell’esercizio 3.1

1. Backgammon: expectiMINIMAX, in quanto abbiamo la presenza di nodi di ca-sualità

2. Scarabeo: se il problema venisse solamente visto nel limite del turno, allora nonsarebbe neanche un algoritmo di ricerca con avversari, differente è il discorsose ragionassi sulla partita completa. In quel caso devo introdurre degli stati dicredenza, in quanto non conosco le lettere a disposizione dell’altro giocatore.

3. Scacchi: α-β pruning con profondità limitata, in quanto lo spazio per la ricerca inprofondità completa sarebbe troppo complessa computazionalmente.

4. Go: UCT, in quanto lo spazio dell’esplorazione è troppo vasto.

5. Monpoli: expectiMINIMAX, in quanto il lancio del dado implica la presenza dinodi di casualità.

6. Poker: non avendo una conoscenza completa dello stato, dobbiamo utilizzarealgoritmi che prendano in considerazione degli stati di credenza.


1. • Insieme degli stati: disposizione delle 14 tessere sulla scacchiera sui duerompicapi

• Stato iniziale: una configurazione delle tessere

• Azioni ammissibili: spostare una delle quattro tessere adiacenti nella posi-zione libera in uno dei due rompicapi

• Modello di transizione: deterministico

• Test obbiettivo: le tessere sono ordinate dall’uno al quattrodici in entrambi irompicapi

• Costo di passo: uno per ogni mossa (azione)

2. Nella prima posizione della scacchiera possono esserci 15 differenti tessere (con-siderando anche quella vuota), in quella successiva ci possono essere 14 differentitessere (tutte quelle avanzate) e cosvia. Avremo quindi uno spazio degli stati con15! differenti stati. Se dobbiamo considerare i due rompicapi contemporaneamen-te avremmo uno spazio degli stati di cardinalità (15!)2.



3. Dobbiamo introdurre il turno dei due giocatori, quindi in questo caso dobbiamospecificare che i due giocatori giocano in maniera sequenziale. Inoltre dovremolimitare la giocata del giocatore sul rompicapo scelto dal lancio della moneta.

4. expectiMINIMAX, in quanto avremmo un nodo di casualità ogni volta che lan-ciamo la moneta

5. Considerate lo stato in cui uno dei due rompicapi è a due passi dalla configurazio-ne obbiettivo. Il giocatore attivo dovrà chiedersi se c’è più probabilità di vittorianel caso in cui muovo verso la soluzione o mi ci allontano. Se muovo verso lasoluzione, l’avversario vince se:

• al primo lancio la moneta lo fa giocare su quel rompicapo (con probabilità1/2)

• entrambi i giocatori lanciano e giocano sull’altro rompicapo e poi l’avversa-rio lancia e può giocare sul primo rompicapo (con probabilità 1/8)

• entrambi i giocatori lanciano e giocano sull’altro rompicapo per due volte epoi l’avversario lancia e può giocare sul primo rompicapo (con probabilità1/32)

• etc.

Quindi la probabilità che l’avversario vinca è di:

1

2+

1

8+

1

32+ . . . =

1

2

∑i

4−i =1

2

4

3=

2

3.

Da qui la mossa migliore è quella di tornare indietro per cercare di far evitare divincere l’avversario.


Un limite inferiore al costo della guardia è il numero di nodi tra la guardia e il ladro.

L’albero del gioco diventa:



Essendo un grafo finito e non essendoci percorsi ciclici, prima o poi la guardia prenderàil ladro.


Per esempio in un gioco a somma zero con due azioni per il primo giocatore e due azioniper il secondo in cui i payoff siano u(a11, a21) = 2, u(a11, a22) = 12, u(a12, a21) = 3,u(a12, a22) = 5, se il primo giocatore dovesse giocare in maniera razionale avremmoche l’utilità del primo giocatore sarebbe 3. Se invece il secondo fosse meno razionalee dovesse giocare randomicamente, allora la sua migliore strategia sarebbe quella digiocare a11 ottenendo un’utilità attesa di 7.


Applicando MINIMAX avremo che il primo ramo darà un’utilità di 2, il secondo di 1 edil terzo di 0. Quindi la migliore azione per il giocatore MAX è la prima con cui prende2.

Utilizzando α-β pruning, supponendo di esplorare i nodi da sinistra a destra, esplore-remmo tutto il primo ramo, nel secondo ci limiteremmo a controllare la prima foglia enel terzo le prime due.


I valori per il MIN sono (da sinistra a destra) −2,−8,−3,−5,−4,−6, 1,−7. Dopodichéquelli per il livello superiore del giocatore MAX sono (da sinistra a destra)−2,−3,−4, 1.Infine il MIN sceglierebbe −3,−4, quindi il valore finale sarebbe −3.




1.

2. L’algoritmo MINIMAX, essendo un algoritmo in profondità, andrebbe all’infinitoin profondità. Se invece decidessimo di fermarci nell’esplorazione ogniqualvoltaraggiungessimo uno stato già visitato, allora possiamo trovare una soluzione.

3. Con 4 caselle vince chi inizia, con 5 chi parte per secondo. L’analisi del problemaa n caselle utilizza dimostrazione per induzione su questi due casi.


1. I nodi al livello più basso hanno valore (da sinistra a destra) 2, 1, 0,−1. I nodi dicasualità hanno valore 1.5,−0.5 e quindi il valore del nodo più altro è 1.5.



2. No perché la media degli ultimi due valori potrebbe essere alta in maniera arbi-traria e quindi il valore del nodo di casualità di destra avrebbe potuto avere unvalore arbitrariamente alto.

3. In questo caso la media del ramo di destra non sarebbe potuta essere più alta diquella del ramo di sinistra.

4. Sì la sesta, perché essendo un nodo di minimo avrei una media tra un numerominore o uguale a zero e un numero al massimo 2, che è comunque inferiore a 1.5


1. VERO: per la proprietà di linearità della media.

2. FALSO: normalmente posso dire quale azione fa il secondo giocatore razionale.Questo solo se non esistono pareggi o se è stato codificato il comportamento incaso di pareggi.

3. FALSO: la razionalità sta nel massimizzare l’utilità attesa e non quella istantanea.

4. VERO: è un’informazione che normalmente non avrei e che potrebbe portarmi adun vantaggio strategico. Il gioco non sarebbe più parzialmente osservabile macompletamente osservabile.


1. MAL FORMULATA: non esiste il concetto di ottimo nelle soluzioni dei problemidi CSP.

2. FALSO: i problemi di ricerca informata considerano anche l’ordinamento dellevariabili assegnate nel processo di ricerca, il che non è necessario nei CSP.

3. FALSO: la soluzione di un CSP richiede solo che vengano assegnate tutte le va-riabili, l’ordine con cui abbiamo effettuato questo procedimento non conta. Dif-ferente questione è quella dell’ordinamento delle variabili durante il processo diricerca, dove invece l’ordine può condizionare la velocità dell’algoritmo di ricerca.

4. FALSO: I problemi di CPS possono avere multiple soluzioni. Per esempio, ilproblema del coloramento dell’Australia ha almeno 3 soluzioni (una per ognicolorazione della Tasmania).


• Variabili: X = X1, . . . , X8 posizione di ognuna delle regine;



• Domini: Di = 1, . . . , 8 riga sulla scacchiera;

• Vincoli: Xi 6= Xj , Xi 6= Xi+k + k, ∀k ∈ 1, 8− i.


1. rectilinear floor planning:

• Variabili: X1, . . . , Xn posizione degli angoli in alto a sinistra dei rettangoli,Y1, . . . , Yn angoli in basso a destra dei rettangoli;

• Domini: se il rettangolo è definito da Ω ⊂ R2, ogni angolo deve stare in Ω;

• Vincoli: ∀i 6= j,Xi > Yj dove con relazione d’ordine si intende che entrambele coordinate soddisfano la diseguaglianza.

2. orario delle lezioni:

• Variabili:

• Domini:

• Vincoli:

3. tour hamiltoniano:

• Variabili:

• Domini:

• Vincoli:


Il nodo più critico sembra essere il nodo H , poiché ha lo stessa cardinalità del dominiodegli altri nodi ma ha molti più vincoli binari con le altre variabili.

Decidiamo innanzitutto un ordine delle variabili da assegnare e un ordine sui colori.Diciamo H,A1, A2, A3, A4, T, F2, F2 e R,G,B.

Facciamo una ricerca in profondità.

(H,R)→ (A1, R)→ Fallimento

(H,R)→ (A1, G)→ (A2, R)→ Fallimento

(H,R)→ (A1, G)→ (A2, G)→ Fallimento



Sembra essere un po’ macchinoso. Utilizziamo anche la verifica della consistenza d’ar-co.

(H,R)→ (A1, G)→ (A2, B)→ (A3, G)→ (A4, B)→ (T,G)→ (F1, R)→ (F2, R)



Definiamo la variabile AB che prende come valore tutte le coppie (A,B) valide. Orapossiamo definire un vincolo binario tra A e AB che è verificato solo per le coppie percui il valore del primo elemento di AB è uguale ad A. La stessa cosa possiamo definirlaperB eAB. Infine, possiamo definire un nuovo vincolo traAB e C che è verificato solose la somma dei due elementi di AB è uguale a C.

I vincoli N -ari possono essere trattati nello stesso modo, creando un vincolo binarioper ogni variabile nell’espressione a destra dell’uguale e un vincolo finale che vada aconsiderare la somma.


3 Ricerca per Giochi e CSP - home.deib.polimi.it · Esercizio 3.5 Applicare gli algoritmi di...

Documents

Transcript of 3 Ricerca per Giochi e CSP - home.deib.polimi.it · Esercizio 3.5 Applicare gli algoritmi di...