Come funziona esattamente la ricorsione MINIMAX?

Question

Così stavo cercando mini-max per un gioco Tic-Tac-Toe, ma non riuscivo a capire come funzionava la ricorsione?Ok, quindi fondamentalmente qui ci sono le mie domande:

.
1. In che modo Minimax sa di chi è il turno?Qual è il modo migliore per indicare il giocatore il cui turno sta generando?
2. Come genera possibili mosse?
3. Come fai a sapere quando sei in un nodo terminale e come genera i nodi del terminale?

Ad esempio in questo pseudo-code

function integer minimax(node, depth)
if node is a terminal node or depth <= 0:
    return the heuristic value of node
α = -∞
for child in node: # evaluation is identical for both players
    α = max(α, -minimax(child, depth-1))
return α

.

A node è una scheda corretta?Ed è la profondità di quanti piatti il codice deve andare giù nella ricorsione?Inoltre, qual è la funzione max e da dove vengono generati i nodi?

Ora, finora ho questo codice per creare una scheda:

class Board{
    public:
        Board();
        ~Board(){};
    public: // The board
        // In the board, 1 is x, 2 is o, 0 is empty square.
        int board[3][3];
};

.

Ma come vorrei sapere di chi è il turno?E come posso generare i nodi figlio per il tabellone?

Answer 1

Useremo il tuo TIC-TAC-TOE per primo.

.
• Un algoritmo di minimax funziona meglio per i giochi in cui i giocatori si alternano a turno, ma possono essere adattati ai giochi in cui i giocatori possono fare più mosse per turno. Assumiamo il primo, per semplicità. In tal caso, non è necessario archiviare "X per spostarsi" o "O per muoversi" con ciascun nodo, perché ciò può essere determinato solo dalla parità della profondità del nodo (se sono un numero pari di passaggi o uno strano Numero di passaggi, dall'alto).
• Generazione di mosse possibili da ogni posizione richiede di sapere il cui movimento è (che può essere determinato come prima) e le regole per le mosse legali da una particolare posizione. Per un semplice gioco come TIC-TAC-TOE, data una posizione, è sufficiente per enumerare tutti gli stati costituiti da una copia della posizione corrente più un nuovo pezzo, appartenente all'attuale giocatore, collocato in ogni quadrato vuoto a turno. Per i giochi come Othello, devi anche controllare ogni collocamento per garantire che segue le regole e aggiornano la posizione finale in base alle conseguenze della regola (per Othello, lanciando i colori di un gruppo di pezzi). In generale, da ciascuna posizione valida che stai monitorando, si enumera tutti i possibili posizioni di un nuovo pezzo e controllano quali sono consentiti da The Tolett.
• In generale, non si genera mai l'intero albero, poiché le dimensioni dell'albero di gioco possono superare facilmente la capacità di stoccaggio della Terra. Hai sempre impostato una profondità massima di iterazione. Un nodo terminale, quindi, è semplicemente un nodo nella profondità massima o un nodo da cui non esistono mosse legali (per TIC-TAC-TOE, una tavola con ogni quadrato pieno). Non generare prima i nodi del terminale; vengono generati naturalmente durante la costruzione dell'albero del gioco. Tic-Tac-Toe è abbastanza semplice da può Genera l'intero albero di gioco, ma quindi non provare a utilizzare il codice TIC-TAC-TOE per E.G. Otello.

Guardando il tuo pseudocodice:

.
• max(a, b) è qualsiasi funzione che restituisce il a b. Questo di solito è fornito da una biblioteca matematica o simile.
• Il depth è la profondità massima a cui cercherai.
• Il valore euristico che stai computer è un valore numerico che descrive il valore della scheda. Per un gioco come Tic-Tac-Toe, che è abbastanza semplice da poter immettere l'intero albero di gioco, è possibile designare 1 per una posizione di bordo che vince per il giocatore che esegue l'analisi, -1 per una posizione di bordo che vince per l'altro giocatore e 0 per qualsiasi posizione inconcludente. In generale, dovrai cucinare un te stesso euristico o usare un ben accettato.
• Genera i nodi al volo durante la tua analisi basata sui loro nodi genitori. Il tuo nodo radice è sempre la posizione da cui stai facendo analisi.

Se non hai ancora lavorato con grafici o alberi, ti suggerisco di farlo prima; L'albero primitivo, in particolare, è essenziale a questo problema.

---

.

Come risposta a un commento in questo thread chiedendo un esempio di determinare il cui turno è per un determinato nodo, offro questo pseudo-python:

who_started_first = None

class TreeNode:
    def __init__(self, board_position = EMPTY_BOARD, depth = 0):
        self.board_position = board_position
        self.children = []
        self.depth = depth
    def construct_children(self, max_depth):
        # call this only ONCE per node!
        # even better, modify this so it can only ever be called once per node
        if max_depth > 0:

            ### Here's the code you're actually interested in.
            if who_started_first == COMPUTER:
                to_move = (COMPUTER if self.depth % 2 == 0 else HUMAN)
            elif who_started_first == HUMAN:
                to_move = (HUMAN if self.depth % 2 == 0 else COMPUTER)
            else:
                raise ValueError('who_started_first invalid!')

            for position in self.board_position.generate_all(to_move):
                # That just meant that we generated all the valid moves from the
                # currently stored position. Now we go through them, and...
                new_node = TreeNode(position, self.depth + 1)
                self.children.append(new_node)
                new_node.construct_children(max_depth - 1)

.

Ogni nodo è in grado di tenere traccia della sua profondità assoluta dal nodo 'root'. Quando cerchiamo di determinare come dovremmo generare posizioni di bordo per la prossima mossa, controlliamo di vedere la cui mossa è basata sulla parità della nostra profondità (il risultato di self.depth % 2) e il nostro record di chi è stato spostato per primo.

Answer 2

.

1) Come si conosce il minimax di chi è il turno?Qual è il modo migliore per indicare il giocatore il cui turno sta generando?

Hai quell'argomento depth.Se la profondità è pari, allora è il turno di un giocatore, se è strano, allora è il turno dell'altro giocatore.

.

2) Come si genera mosse possibili?

usando le regole del gioco.In Tic TAC, una possibile mossa significa posizionare il segno in una cella gratuita.

.

3) Come si sa quando sei in un nodo terminale e come genera i nodi del terminale?

Un nodo terminale è un nodo in cui qualcuno ha vinto.Generili con la ricorsione.Ogni chiamata ricorsiva dovrebbe essere data lo stato attuale del tabellone.Immagino che sia il node e i parametri child nel tuo pseudocodice.Quindi, se in quella situazione qualcuno ha vinto, allora è il terminale, altrimenti provi tutte le mosse legali e recurte.

Answer 3

Posso fornire un po 'un'idea su ciò che stai cercando, dal momento che ho scritto un algoritmo di minimax per Tic-Tac-Toe.

Per rispondere alle tue domande direttamente:

.

1. Il mio algoritmo minimax non ha determinato ciò. Ha accettato un argomento che ha determinato quale giocatore stava usando l'algoritmo.

2. Conoscere il giocatore a muoversi, loop attraverso tutti i quadrati vuoti sul tabellone, e per ognuno, generare un nodo con il token del giocatore corrente in quel quadrato. Procedere ricorsivamente da lì.

3. Ho usato una funzione che ha restituito un valore che indicava se il gioco era finito e se fosse un pareggio o una vittoria.

Il mio algoritmo di base ha fatto questo:

.
• Input: il giocatore per muoversi e lo stato del tabellone.
• Trova tutti gli spazi vuoti lasciati sulla lavagna.
  .
  • Genera una nuova scheda con la mossa del giocatore in quello spazio.
  • Se il gioco è finito, genera un nodo con il risultato del gioco.
  • Altrimenti, eseguire l'algoritmo, passando nell'altro giocatore e nella nuova scheda e genera un nodo con il risultato della mossa ideale dell'avversario.
• Determina quale nodo (mossa) porta al miglior caso peggiore possibile.
• Uscita: la mossa migliore e le informazioni sul risultato del gioco da esso.