spiegazione Minimax "per i manichini"

Question

Sono abbastanza nuovo per gli algoritmi e stavo cercando di capire il minimax, ho letto un sacco di articoli, ma non riesco ancora a ottenere come implementarlo in un tic-tac-toe gioco in python. Puoi provare a spiegarmelo il più facilmente possibile magari con qualche pseudo-codice o qualche codice python ?.

Ho solo bisogno di capire come funziona. Ho letto un sacco di cose su questo e ho capito le basi, ma non riesco ancora a capire come possa restituire una mossa.

Se potete, per favore, non collegarmi tutorial e campioni come (http://en.literateprograms.org/Tic_Tac_Toe_(Python)), so che sono buoni, ma ho semplicemente bisogno di una spiegazione idiota.

grazie per il vostro tempo :)

Answer 1

l'idea di "minimax" è che in una partita a due giocatori, un giocatore sta cercando di massimizzare qualche forma di punteggio e un altro giocatore sta cercando di minimizzarlo. Ad esempio, in Tic-Tac-Toe la vittoria di X potrebbe essere valutata come +1 e la vittoria di O come -1. X sarebbe il giocatore massimo, cercando di massimizzare il punteggio finale e O sarebbe il giocatore min, cercando di minimizzare il punteggio finale.

X è chiamato il giocatore massimo perché quando è il movimento di X, X deve scegliere una mossa che massimizza il risultato dopo quella mossa. Quando O giocatori, O ha bisogno di scegliere una mossa che minimizza il risultato dopo quella mossa. Queste regole vengono applicate in modo ricorsivo, così ad es. se ci sono solo tre posizioni della tavola aperte per giocare, la migliore giocata di X è quella che obbliga O a scegliere una mossa con valore minimo il cui valore è il più alto possibile.

In altre parole, il valore minimax teoria dei giochi V per una posizione di bordo B è definito come

V(B) = 1 if X has won in this position 
V(B) = -1 if O has won in this position 
V(B) = 0 if neither player has won and no more moves are possible (draw) 

altrimenti

V(B) = max(V(B1), ..., V(Bn)) where board positions B1..Bn are 
     the positions available for X, and it is X's move 
V(B) = min(V(B1), ..., V(Bn)) where board positions B1..Bn are 
     the positions available for O, and it is O's move 

La strategia ottimale per X è sempre a spostarsi da B a Bi tale che V (Bi) è massimo, cioè corrisponde al valore gametorico V (B), e per O, analogamente, scegliere una posizione minima successore.

Tuttavia, questo non è generalmente possibile calcolare in giochi come gli scacchi, perché per calcolare il valore gametorico è necessario enumerare l'intero albero di gioco fino alle posizioni finali e quell'albero è solitamente molto grande. Pertanto, un approccio standard consiste nel coniare una "funzione di valutazione" che mappa le posizioni della board in punteggi che si spera siano correlati ai valori gametoretici. Per esempio. nei programmi di scacchi le funzioni di valutazione tendono a dare un punteggio positivo per il vantaggio materiale, le colonne aperte, ecc. Un algoritmo minimox consente di minimizzare il punteggio della funzione di valutazione anziché il valore gametrale teorico (non memorizzabile) di una posizione della scheda.

Un'ottimizzazione standard significativa a minimax è "alfa-beta potatura". Dà gli stessi risultati della ricerca minimax ma più veloce. Minimax può anche essere castato in termini di "negamax" dove il segno del punteggio è invertito ad ogni livello di ricerca. È solo un modo alternativo per implementare minimax ma gestisce i giocatori in modo uniforme. Altri metodi di ricerca dell'albero di gioco includono l'approfondimento iterativo, la ricerca del numero di prova e altro ancora.

Answer 2

Minimax è un modo di esplorare lo spazio di possibili mosse in una partita a due giocatori con turni alternati. Stai cercando di vincere e il tuo avversario sta cercando di impedirti di vincere.

Un'intuizione chiave è che se è attualmente il tuo turno, una sequenza di due mosse che ti garantisce una vittoria non è utile, perché il tuo avversario non coopererà con te. Cerchi di fare mosse che massimizzano le tue possibilità di vincita e il tuo avversario fa mosse che minimizzano le tue possibilità di vincita.

Per questo motivo, non è molto utile esplorare i rami dalle mosse che si fanno male per te, o le mosse che il tuo avversario fa per te.