Intelligenza Artificiale Min Max problem & cut

[devAngnew]

Ciao a tutti non riesco a capire come funzionano i tagli nell'algoritmo di min max.
http://img96.imageshack.us/img96/7961/minmax.png

L'albero è costruito tendo conto che in radice la prima mossa la fà min.
Ad esempio guardando l'immagine non capisco perchè venga tagliato il figlio di F cioè O e non l'intero sotto albero F. Poichè a livello 1 il giocatore è Max, l'unica scelta possibile per massimizzare il suo punteggio è scegliere il nodo E.

Bhoo

[devAngnew]

Up

[wingman87]

Dovresti farti spostare il thread nella sezione Programmazione:
http://www.hwupgrade.it/forum/forumdisplay.php?f=38

[cionci]

Meglio in scienza e tecnica.

[lowenz]

C'è anche un esempio animato su wikipedia :o

http://en.wikipedia.org/wiki/Minimax

[devAngnew]

Ho dato un'occhiata su wikipedia interessante, ma ho ancora lo stesso dubbio
se qualcuno conosce la ricerca min max con i Tagli e commenta il mio esempio gli sarei grato.

[JaneDoe]

Originariamente inviato da devAngnew

Ho dato un'occhiata su wikipedia interessante, ma ho ancora lo stesso dubbio
se qualcuno conosce la ricerca min max con i Tagli e commenta il mio esempio gli sarei grato.

Provo a spiegarti come ho capito io:

• il nodo E è un nodo min, quindi tra K,L ed M l'algoritmo sceglierà K che ha il costo minore (cioè 1)
  
• anche il nodo F è min, quindi l'algoritmo esamina il primo figlio di F (N) e vede che il costo -2 è già minore del costo dato ad E. Quindi non serve andare ad esaminare gli altri figli di F (nello specifico si tratta solo del nodo O) poichè B è un nodo max e sceglierà in ogni caso il nodo E, per cui vengono tagliati i figli di F ad eccezione ovviamente di N che è già stato esaminato (e questo dovrebbe rispondere alla tua domanda iniziale)

Detto in altre parole, tu devi pensare che dei nodi che vengono tagliati l'algoritmo non ne sa niente, poichè non li esamina proprio. Con riferimento all'esempio, anche se sul disegno ad esempio vedi scritto che il nodo H ha costo -8 questa informazione l'algoritmo non la conosce, poichè ha tagliato H.
L'algoritmo esamina tutti i nodi di un sottoalbero finchè non riesce a concludere che quel ramo non verrà mai scelto e solo allora effettuerà il taglio dei restanti nodi non ancora esaminati.

Forse sono stata un po' contorta nella spiegazione, ma spero di esserti stata utile

[devAngnew]

Originariamente inviato da JaneDoe

Provo a spiegarti come ho capito io:
.....

Gazie, mi sembra più chiaro....

ciao.