Ricerca dell'albero di Monte Carlo nel gioco AI

Question

Ricerca dell'albero di Monte Carlo nel gioco AI

#1 da (2 voti)

2

Sono molto confuso nell'implementazione di MCTS per un gioco di connessione 5. Secondo Wikipedia :

Selezione: inizia dalla radice R e seleziona i nodi figli successivi fino a un nodo foglia L.

Diciamo che è il turno dell'AI. Lo stato attuale della scheda è R . Non dovrebbero esserci nodi figli di R , giusto? Quindi, come è possibile "selezionare i nodi secondari successivi su un nodo foglia L "? Perché non hai nodi figli di R. Il nodo figlio L significa ogni singola mossa che l'IA può fare da R ?

Se quel nodo figlio L , che è uno stato di gioco, non è una vittoria né per l'IA né per il giocatore, giocate casualmente delle mosse fino ad alcune vittorie, e retrocopate fino a R . Cosa fai dopo il backpropagating?

Non capisco come si seleziona il nodo figlio L . Ancor prima, non sono sicuro di come viene creato L . Sembra molto strano perché sembra che tu stia "selezionando" un nodo figlio sul primissimo passaggio.

Sarebbe bello se qualcuno potesse semplificarlo. Grazie.

data-structures algorithms artificial-intelligence

posta Dashadower 28.05.2017 - 15:24

fonte

1 risposta

Leggi altre domande sui tag data-structures algorithms artificial-intelligence

esiste un modo per conoscere il tipo di applicazione per il controllo della versione basata sul web da un URL git? Come testare il software su altre piattaforme

score 2 · Accepted Answer

All'inizio hai solo un nodo, la radice R, che è anche il nodo foglia L del primo passaggio di selezione del tondo.

There should be no child nodes of R, right? Then, how can you "select successive child nodes down to a leaf node L"?

Basta selezionare L = R. (penso che l'articolo di Wikipedia abbia alcuni difetti. Non devi selezionare un nodo foglia ma un nodo che ha ancora alcuni bambini ancora inesplorati.)

If that child node L , which is a game state, is not a victory for neither the AI or the player, you randomly play moves until some wins, and backpropagate up to R.

No, secondo l'articolo di Wikipedia, è necessario prima prendere il passaggio di espansione. Scegli uno qualsiasi dei bambini inesplorati di L come nodo C. Devi espandere l'albero per arrivare ovunque.

What do you do after backpropagating?

Ripeti la procedura a meno che tu non abbia più tempo.

I dont understand how you select child node L

Questa è la vera chiave dell'algoritmo. Devi attraversare l'albero dalla radice fino a raggiungere un nodo che ha alcuni bambini inesplorati. Per ogni passaggio devi scegliere un nodo, bilanciamento tra larghezza e profondità dell'albero. Prova la formula UCT per questo scopo.

Mi aspetto che non sarebbe troppo difficile definire una buona funzione di valutazione per Connect 5. Se questo è il caso, la ricerca dell'albero Monte Carlo probabilmente non è l'algoritmo più efficiente per l'attività.