AlphaGo Zero

Tenemos que el juego de Go se puede ver como un MDP episódico finito. Este algoritmo implementa una variante del MCTS usual que funciona como un operador de iteración de política, es decir evalua y mejora una política dada.

Como el espacio de estados es de aproximadamente ${10}^{170}$ lo más viable es usar una aproximación para la función de valor, en este caso se usa una red neuronal $f_{\theta }$ que tiene como input el tablero con las posiciones de las fichas y como output la probabilidad de cada acción es el estado $s$ y una estimación del valor $v$, $(p,v)=f_{\theta }(s)$. Por la naturaleza del los datos la arquitectura de la red esta basada sobre el estado actual del arte en reconocimiento de imágenes.

MTCS y la red neuronal combinados.

Esta variante de MCTS en lugar de ejecutar el paso usual de simulación o rollout con una política aleatoria, este MCTS usa a $f_{\theta }$ como política de simulación.

Para evaluar la última política se juegan partidas contra sí mismo (self-play) usando el MCTS para seleccionar movimientos, como cada partida termina en algún momento sabemos con seguridad el resultado si se gana o se pierde, entonces se asigna la recompensa $1$ o $-1$, respectivamente.

Estos datos obtenidos de las partidas contra sí mismo se usan para entrenar a la red neuronal $f_{\theta }$.

Así se itera varias veces, inicializando los paramétros ${\theta }_0$ aleatoriamente.

Observación

Este enfoque es más directamente aplicable a los juegos de suma cero de información perfecta. Además notemos que en el MDP asociado, la función de transición $P(s|a)$ es determinista, de hecho las acciones legales son un subconjunto de los estados, dado un estado $s$ y una acción $a$ ésta determina completamente el siguiente único posible siguiente estado $s^{\prime }$.

El algoritmo de self-play de AlphaGo Zero puede entenderse de manera similar como un esquema de iteración de políticas aproximado en el que MCTS se utiliza tanto para la mejora como para la evaluación de la política. La mejora de la política comienza con una política basada en una red neuronal, ejecuta un MCTS basado en las recomendaciones de esa política y luego proyecta la política de búsqueda (mucho más fuerte) de vuelta en el espacio de funciones de la red neuronal. La evaluación de la política se aplica a la política de búsqueda (mucho más fuerte): los resultados de las partidas de self-play también se proyectan de vuelta en el espacio de funciones de la red neuronal. Estos pasos de proyección se logran entrenando los parámetros de la red neuronal para que coincidan, respectivamente, con las probabilidades de búsqueda y los resultados de las partidas de self-play.