java - Árbol de Monte Carlo que busca la implementación de UCT

tree artificial-intelligence

Question

¿Me puedes explicar cómo construir el árbol?

Comprendí perfectamente cómo se seleccionan los nodos, pero una explicación más agradable realmente me ayudaría a implementar este algoritmo. Ya tengo un tablero que representa el estado del juego, pero no sé (entiendo) cómo generar el árbol.

¿Alguien me puede indicar una implementación bien comentada del algoritmo (necesito usarlo para AI)? ¿O mejor explicación / ejemplos de ello?

No encontré muchos recursos en la red, este algoritmo es bastante nuevo ...

Answer 1

De http://mcts.ai/code/index.html :

Below are links to some basic MCTS implementations in various
programming languages. The listings are shown with timing, testing
and debugging code removed for readability.

Java

Python

Answer 2

Escribí este si estás interesado: https://github.com/avianey/mcts4j

Answer 3

La mejor manera de generar el árbol es una serie de playouts aleatorios. El truco es poder equilibrar entre exploración y explotación (aquí es donde entra en juego la UCT). Hay algunos buenos ejemplos de códigos y muchas referencias de trabajos de investigación aquí: https://web.archive.org/web/20160308043415/http://mcts.ai:80/index.html

Cuando implementé el algoritmo, usé reproducciones aleatorias hasta que llegué a un punto final o estado de terminación. Tuve una función de evaluación estática que calcularía la recompensa en este punto, luego la puntuación a partir de este punto se propagará hacia el árbol. Cada jugador o "equipo" asume que el otro equipo jugará el mejor movimiento para sí mismo y el peor movimiento posible para su oponente.

También recomendaría consultar los trabajos de Chaslot y su tesis doctoral, así como algunas de las investigaciones que hacen referencia a su trabajo (básicamente todo el trabajo de MCTS desde entonces).

Por ejemplo: el primer movimiento del jugador 1 podría simular 10 movimientos hacia el futuro alternando entre los movimientos del jugador 1 y el jugador 2. Cada vez que debes asumir que el jugador contrario intentará minimizar tu puntuación mientras maximiza su propia puntuación. Hay un campo completo basado en esto conocido como Teoría de juegos. Una vez que simules hasta el final de los 10 juegos, repetirás desde el punto de inicio nuevamente (porque no tiene sentido simular un conjunto de decisiones). Cada una de estas ramas del árbol debe puntuarse donde la puntuación se propaga hacia arriba y la puntuación representa la mejor recompensa posible para el jugador que realiza la simulación, asumiendo que el otro jugador también está eligiendo los mejores movimientos para sí mismo.

El MCTS consta de cuatro pasos estratégicos, que se repiten siempre que quede tiempo. Los pasos son los siguientes.

1. En el paso de selección, el árbol se recorre desde el nodo raíz hasta que llegamos a un nodo E, donde seleccionamos una posición que aún no se ha agregado al árbol.

2. A continuación, durante el paso de la jugada, los movimientos se juegan en auto-juego hasta que se llega al final del juego. El resultado R de este juego "simulado" es +1 en caso de ganar para el Negro (el primer jugador en LOA), 0 en caso de empate, y −1 en caso de ganar para el Blanco.

3. Posteriormente, en el paso de expansión, los hijos de E se agregan al árbol.

4. Finalmente, R se propaga a lo largo de la ruta desde E hasta el nodo raíz en el paso de propagación hacia atrás. Cuando se acaba el tiempo, el movimiento jugado por el programa es el hijo de la raíz con el valor más alto. (Este ejemplo está tomado de este documento - PDF

www.ru.is/faculty/yngvi/pdf/WinandsBS08.pdf

Aquí están algunas implementaciones:

Una lista de bibliotecas y juegos que utilizan algunas implementaciones de MCTS http://senseis.xmp.net/?MonteCarloTreeSearch

y una biblioteca UCT MCTS de código abierto independiente del juego llamada Fuego http://fuego.sourceforge.net/fuego-doc-1.1/smartgame-doc/group__sguctgroup.html