Come dimostrare che ogni sottosezione, la strategia è più ottimale nell'algoritmo minimax?

Question

La domanda è come il titolo suggerisce.

So che l'algoritmo di Minimax fa questo per il gioco di 2 persone (supponi che vogliamo massimizzare il profitto di A): quando è il turno di A, prendiamo il massimo dei valori del bambino perché stiamo massimizzando il profitto di A.B è il turno, prendiamo il minuto dei valori del bambino perché vogliamo minimizzare il profitto della B.

Tuttavia, non penso che la logica sopra riportata dimostra che ogni sotto-problema, la strategia è la più ottimale nell'algoritmo minimax.Qualche suggerimento o soluzioni alla domanda che ho proposto?Se lo fa la logica sopra, allora potresti elaborarlo?

Answer 1

La rivendicazione Minimax è: Minimax sta dando una strategia ottimale se l'altro giocatore utilizza anche la stessa strategia.

Base : Per una foglia nell'albero del gioco - c'è solo una strategia, che minimax ovviamente sceglie, ed è ottimale - poiché è l'unico.
Ipotesi : MINIMAX sceglie una strategia ottimale per un gioco di profondità d.
Proof :

Diamo un'occhiata a una partita di profondità d+1. Ci sono ovviamente 2 possibili scenari:

.
1. è fuori giro - questa è la fase max. In questo caso, da tutte le mosse possibili possiamo fare - MINIMAX valuta ricorsivamente il valore MIN-Max per ciascuna strategia di questo tipo e ci dà il risultato ottimale per un "sottogruppo", dove abbiamo scelto questa mossa. Ciascuno di questi sottogami è di profondità d, e dall'ipotesi di induzione, è ottimale.
   Dal momento che questa è la fase massima: l'algoritmo min-max sceglie il massimo, che è la soluzione ottimale per noi.
2. è il turno dell'avversario - questa è la fase min. Allo stesso modo alla logica di cui sopra, il minimox si divide il caso a tutte le mosse possibili, l'avversario può fare e valutare il loro risultato. Dall'ipotesi di induzione, le valutazioni sono ottimali, e scegliamo il minimo da loro - che sarà ciò che l'avversario avrebbe scelto, ed è una strategia ottimale per lui (e supponiamo che l'avversario scelga in modo ottimale per ogni fase del modo) - così il L'avversario sceglie la valutazione minima, che minimizza il nostro profitto, e quindi massimizza il suo profitto.

Qed

Sulla base di esso, è possibile concludere un'altra rivendicazione di MINIMAX - il valore restituito dalla strategia non è inferiore a quello che verrai effettivamente (indipendentemente dalla strategia dell'opsente). Questo può essere dimostrato per induzione molto simile a quello sopra.

Linee guida:

Base : solo una strategia, e lo stai restituendo, quando l'albero 'è in realtà una foglia.
Reclamo : Valore restituito da MINIMAX per il gioco di profondità d è un limite inferiore a tutti i giochi giocati da questo livello, dove hai scelto in base a Minimax e nessuna restrizione sull'avversario.
Proof :

Diamo un'occhiata al gioco di profondità d+1.

.
1. Se è il tuo turno, hai scelto il massimo di tutte le foglie, dal momento che tu avere la scelta qui Ognuna delle foglie ti garantisce (Induciton ipotesi) almeno un valore e scegliendo il massimo di loro - Garantire anche il valore scelto.
2. Se è il turno dell'avversario - non hai il controllo sulla scelta. Puoi essere sicuro che abbia scelto un po 'di mossa, nessuna idea che. Tuttavia, per tutte le possibili mosse - ottieni una nuova "sottotaccia" di profondità d, in cui l'ipotesi di induzione tiene. L'avversario può scegliere una di queste mosse, in modo da poter garantire che dopo questa mossa, avrai un valore di almeno min{game after opponent move}, che è esattamente ciò che il rendimento della fase min.

QED .

Answer 2

Non è possibile dimostrare che Minimax massimizza il profitto del giocatore, perché MiniMax non tenta di massimizzare il profitto del giocatore.

Che cosa fa MINIMAX minimizzare il giocatore possibile perdita ;Cioè, le sue decisioni sono conservative e presuppongono lo scenario peggiore (gioco ottimale dell'altro giocatore).Prova a dimostrare che uno;Lo troverai molto più semplice.