algoritmo Minimax

Question

Ho una semplice domanda per quanto riguarda l'algoritmo Minimax: per esempio per il gioco tic-tac-toe, come faccio a determinare la funzione di utilità di per ogni giocatore gioca? E non lo fa automaticamente, lo fa? Devo codificare i valori in gioco, non li può imparare da solo, vero?

Answer 1

No, un MiniMax non impara. Si tratta di una versione più intelligente di una ricerca albero di forza bruta.

Answer 2

In genere si dovrebbe implementare direttamente la funzione di utilità. In questo caso l'algoritmo non sarebbe imparare a giocare il gioco, sarebbe utilizzare le informazioni che si era esplicitamente hard-coded per l'attuazione.

Tuttavia, sarebbe possibile utilizzare programmazione genetica (GP) o qualche tecnica equivalente derivare automaticamente una funzione di utilità. In questo caso non avrebbe dovuto codificare qualsiasi strategia esplicita. Invece l'evoluzione avrebbe scoperto il suo modo di giocare bene la gara.

Si potrebbe o combinare il codice minimax e il codice GP in un unico (probabilmente molto lento) del programma adattivo, o si potrebbe correre il GP prima, trovare una buona funzione di utilità e quindi aggiungere questa funzione per il codice Minimax proprio come si farebbe qualsiasi funzione codificati a mano.

Answer 3

Tic-Tac-Toe è abbastanza piccolo per eseguire il gioco fino alla fine e assegnare 1 per vittoria, 0 per pareggio e -1 per perdere.

Altrimenti è necessario fornire una funzione che determina il valore di una posizione euristicamente. Nel gioco degli scacchi, per esempio un grande fattore è il valore del materiale, ma anche che controlla il centro o quanto facilmente i pezzi può muoversi.

Per quanto riguarda l'apprendimento, è possibile aggiungere fattori di peso a diversi aspetti della posizione e cercare di ottimizzare quelli ripetutamente giocare.

Answer 4

Come si determina la funzione di utilità per ogni gioco?

articolo mostra come una funzione di valutazione leggermente imperfetto (uno per es., che o non andare "in profondità" sufficiente a guardare avanti nell'albero di possibili plys, o uno che non riesce a catturare l'strengh relativo di alcune posizioni di bordo) risultati in un algoritmo debole complessiva (uno che perde più spesso).

non può li imparare da solo, vero?

No, non è così. Ci sono diversi modi, tuttavia, per rendere il computer impara la forza relativa delle posizioni di bordo. Per esempio, cercando in Donald Mitchie e il suo programma MENACE vedrete come un processo stocastico può essere utilizzato per imparare il bordo senza alcun a priori la conoscenza, ma le regole del gioco. La parte divertente è che, mentre questo può essere implementato in computer, a poche centinaia di perline colorate e scatole di fiammiferi sono tutto ciò che è necessario, grazie alle dimensioni relativamente ridotte dello spazio del gioco, e anche grazie a varie simmetrie.

Dopo aver imparato un modo così fresco di insegnare al computer come giocare, potremmo non essere così interessati a tornare a MinMax applicata alle Tic-Tac-Toe. Dopo tutto MinMax è un modo relativamente semplice per potare un albero di decisione , che è difficilmente necessario con piccolo spazio gioco del tic-tac-toe. Ma, se proprio dobbiamo ;-) [tornare a MinMax] ...

Possiamo esaminare la "scatola di fiammiferi" associati con il gioco successivo (vale a dire non andare in profondità a tutti), e utilizzare la percentuale di perline associati a ogni quadrato, come un fattore aggiuntivo. Possiamo quindi valutare un tradizionale albero, ma solo andando, dire 2 o 3 si muove in profondità (una profondità di look-ahead che in genere finiscono nel solito in perdite o pareggi) e valutare ogni mossa successiva sulla base del semplice -1 ( perdita), 0 (draw / sconosciuto), 1 (vittoria) Valutazione. Da allora combinando la percentuale di perle e la valutazione semplice (con l'aggiunta per esempio, non certo per moltiplicazione), siamo in grado di utilizzare efficacemente MinMax in un modo che è più simile al modo in cui viene utilizzato nei casi in cui non è possibile valutare l'albero di gioco fino alla fine.

In conclusione: Nel caso di Tic-Tac-Toe, MinMax diventa solo più interessante (per esempio per aiutarci a esplorare l'efficacia di una particolare funzione di utilità) quando togliamo la natura deterministica del gioco, associata con il facile la valutazione l'albero pieno. Un altro modo di rendere il gioco [matematicamente] interessante è quello di giocare con un avversario che fa gli errori ...