Búsqueda de grafos Monte Carlo desde los principios fundamentales

 (github.com/lightvector)
3 puntos por GN⁺ 2024-03-11 | 1 comentarios | Compartir por WhatsApp
  • Monte-Carlo Graph Search (MCGS) es un enfoque que busca aplicar MCTS sobre un grafo dirigido en lugar de un árbol en juegos donde varias secuencias de jugadas transitan al mismo estado, para compartir la exploración duplicada
  • Si se trasladan directamente al DAG el conteo de visitas N y el valor promedio Q del MCTS tradicional, el número de visitas de un hijo compartido puede desalinearse de la estimación de política y valor del padre, y el algoritmo puede volverse incorrecto
  • Si se ve MCTS como una optimización de política regularizada, la distribución de visitas por acción que produce PUCT se interpreta como una política posterior, y Q como la utilidad esperada de esa política
  • Un MCGS correcto, además de las visitas del nodo hijo, rastrea por separado las visitas por arista N(n,a) y recalcula Q como suma ponderada de U(n) y de los Q de los hijos, preservando en el grafo el significado de política y valor
  • En la implementación real todavía quedan decisiones como stale Q, actualizaciones incrementales, si continuar el playout desde un hijo transpuesto, y el manejo de colisiones de hash y ciclos del juego; KataGo actualmente usa actualizaciones idempotentes

Estados transpuestos que la búsqueda en árbol pasa por alto

  • En la búsqueda en árbol para juegos, puede ocurrir que distintas secuencias de jugadas transpongan (transposition) al mismo estado
    • En ajedrez, 1. d4 d5 2. Nf3 y 1. Nf3 d5 2. d4 llegan a la misma posición
  • En juegos donde hay transposiciones, a mayor profundidad de búsqueda los estados duplicados pueden crecer exponencialmente, por lo que conviene compartir el cómputo del mismo estado
  • Una implementación común de MCTS trata el juego como un árbol de ramificación y vuelve a explorar múltiples instancias de la misma posición
    • Optimizaciones de bajo nivel como cachear evaluaciones de la red neuronal para posiciones repetidas pueden reducir el costo
    • Pero sigue existiendo el problema de que, aunque se descubra una táctica importante en una instancia y se corrija su evaluación, eso no se propaga a las demás instancias
  • Si se modela el espacio de estados como un grafo acíclico dirigido (DAG), cuando múltiples caminos llegan al mismo estado ese estado puede representarse como un solo nodo
  • Aquí se deja de lado en gran medida el tratamiento de juegos con ciclos reales y se pone el foco en cómo debería funcionar MCTS sobre un DAG

MCTS estándar: un árbol que acumula estadísticas de ejecución

  • El MCTS estándar guarda en memoria una estructura de nodos en árbol para la parte del juego ya explorada
  • Cada nodo normalmente rastrea los siguientes valores
    • N: número de playouts que hasta ahora pasaron por este nodo o terminaron en él
    • Q: promedio empírico de la utilidad muestreada por esos playouts
  • Un playout avanza en el siguiente orden
    • Empieza en la raíz y desciende eligiendo la siguiente acción según una fórmula de exploración
    • Cuando llega a un estado aún no explorado, agrega un nodo nuevo
    • Obtiene la utilidad U del nuevo estado. El ejemplo usa una consulta al value head de una red neuronal
    • Retrocede por el árbol incrementando N de cada nodo y actualizando el promedio Q
  • En el estilo de MCTS de AlphaZero, la selección de acciones usa la fórmula PUCT
    • N(a): cuántas veces se intentó la acción a; en el árbol esto coincide con el N del nodo hijo al que apunta esa acción
    • Q(a): utilidad promedio de la acción a; coincide con el Q del nodo hijo
    • PlayerToMove: refleja si el jugador actual maximiza o minimiza
    • P(a): probabilidad previa, como una predicción de política de la red neuronal
    • c_PUCT: constante ajustable
  • “PUCT” proviene de la familia Predictor UCT/UCB, que usa una distribución previa predictiva, aunque la variante de AlphaZero difiere en la forma funcional del original
  • El MCTS moderno puede ser determinista cuando usa evaluación por red neuronal, pero el “Monte-Carlo” del nombre viene de la práctica histórica de hacer rollouts aleatorios hasta el final para estimar la utilidad
  • Tras repetir playouts hasta agotar el presupuesto de cómputo del turno, en la raíz se elige como acción final no el Q, sino el hijo con mayor número de visitas N
    • Un hijo con Q alto y N bajo puede ser un error que salió artificialmente alto por ruido en una exploración superficial
  • La distribución de visitas en la raíz N(a) / ΣN(b) puede usarse como objetivo de aprendizaje de política en el bucle de entrenamiento de AlphaZero

Problemas al aplicarlo ingenuamente a un DAG

  • Se podría dejar casi intacto el código de MCTS para árboles y hacer que, si un nuevo estado del juego ya existe en nodes_by_hash, simplemente apunte al nodo existente
  • Ese método ya no preserva el supuesto del árbol de que las visitas del nodo hijo son iguales a las visitas de la acción elegida en el padre
  • Ejemplo
    • El nodo A prefiere una acción que va al nodo C, y el Q de A está determinado en su mayor parte por unos 30 playouts que exploraron C
    • C también fue visitado unas 40 veces por otras rutas de transposición
    • Luego C recibe muchas más visitas por otras rutas y se descubre una táctica profunda, elevando su estimación de utilidad de 0.39 → 0.51
  • Como los playouts que actualizaron C no pasaron por A, el Q de A no refleja la nueva evaluación de C
  • Aunque A reciba playouts después, PUCT puede explorar otras acciones con pocas visitas en lugar de C, que tiene muchas
    • Porque C parece “ya suficientemente explorado”
    • Como resultado, el Q de A incluso puede bajar
  • La extensión ingenua a grafos puede hacer que, cuanto más visiten las rutas transpuestas una jugada muy preferida, más explore el padre otras jugadas, introduciendo un sesgo artificial en el promedio de playouts
  • Se vuelve un algoritmo incorrecto al punto de que ni siquiera está claro si converge a la mejor jugada con exploración infinita

Actualizar todos los padres tampoco lo resuelve

  • También podría pensarse en un método donde, cuando un playout actualiza un nodo, esa actualización se refleje no solo en los padres que realmente recorrió, sino en todos los padres y ancestros
  • En el caso anterior de A-C, este método sí podría actualizar también la utilidad de A
  • Pero en otro ejemplo, el padre D queda contaminado por muchas visitas a un hijo transpuesto F que en realidad no prefiere
    • El mejor hijo de D es E con Q = 0.56, y Q = 0.55 en D es coherente con eso
    • D solo exploró F una vez, pero F ya había sido visitado 9 veces por otras rutas, para un total de 10
    • Si después F recibe 100 visitas más por otras rutas y mantiene una utilidad baja, el método de actualizar todos los padres puede arrastrar el Q de D hasta 0.35
  • Desde la perspectiva de D, no quería asignar tantos playouts a F, así que actualizar todos los padres también rompe el significado de la política

Ver MCTS como optimización de política

valor que π maximiza:
Σ π(a) Q(a) - λ_N D_KL(P || π)
  • Significado de los componentes
    • Σ π(a) Q(a): utilidad esperada estimada al seguir la política π
    • D_KL(P || π): divergencia KL inversa que mide la diferencia entre la política previa P y la política posterior π
    • λ_N: coeficiente que determina la intensidad del término KL y disminuye a medida que aumenta el número de visitas
  • La distribución de visitas puede verse como una política posterior que toma como punto de partida la política previa P de la red neuronal y se va refinando a medida que más visitas acumulan evidencia sobre la utilidad de las acciones
  • Por lo tanto, MCTS puede interpretarse como un algoritmo que realiza simultáneamente un pequeño aprendizaje online de política en cada nodo del árbol
  • Esta perspectiva explica por qué la distribución de visitas se parece a la política de un agente fuerte y por qué se usa como objetivo de aprendizaje de política en AlphaZero
  • También sería posible calcular la solución exacta del problema de optimización y usarla directamente como política, pero en la práctica eso puede dar mucho peso a jugadas con pocas visitas y un Q que por azar parece alto
    • Si se usa la distribución de visitas como política posterior, una jugada necesita haber sido realmente muy explorada para recibir mucho peso, por lo que resulta más robusta

Reinterpretación de Q: del promedio de playouts al valor esperado de la política

  • En la definición estándar, Q(n) del nodo n es el promedio de utilidad de los playouts que visitaron n
Q(n) = (1 / N(n)) Σ U(p)
  • Reescribiéndolo en función de los hijos, queda así
Q(n) = (1 / N(n)) ( U(n) + Σ N(c) Q(c) )
  • Aquí U(n) es la estimación cruda de utilidad por red neuronal del propio nodo n, y N(c) Q(c) es el valor del hijo ponderado por su número de visitas
  • Por lo tanto, Q puede interpretarse como un promedio ponderado por la distribución de visitas de los Q de los hijos
  • Si la distribución de visitas es la política posterior que MCTS optimiza, entonces Q(n) es la utilidad esperada regularizada al seguir esa política posterior
  • Bajo esta interpretación, cada nodo sigue optimizando su política para maximizar el Q que reportan sus hijos, y actualiza su propio Q como la mejor estimación actual de la utilidad esperada alcanzable con esa política
  • Si Q de los nodos hijo converge al valor óptimo en sentido de teoría de juegos, entonces la política y el Q del padre también convergen recursivamente al valor óptimo

MCGS correcto: separar visitas por arista y visitas por hijo

  • El problema en grafos aparece porque se asume que las visitas a un hijo del padre solo ocurren a través de ese padre
  • Si hay rutas transpuestas, el número de visitas al nodo hijo puede diferir arbitrariamente del número de visitas que PUCT quería asignar desde ese padre
  • La solución es rastrear por separado cuántas veces PUCT eligió cada acción en un nodo dado
  • Cada nodo n rastrea los siguientes valores
    • N(n): número total de veces que se visitó este nodo
    • N(n,a): número de veces que PUCT eligió la acción a en el nodo n, es decir, visitas por arista
    • Q(n) = (1 / N(n)) ( U(n) + Σ N(n,a) Q(n,a) )
  • Aquí Q(n,a) es igual al Q(c) del nodo hijo c alcanzado al jugar la acción a
  • En el cálculo de PUCT también se usan visitas por arista, no visitas del hijo
argmax_a PlayerToMove(n) * Q(n,a)
       + c_PUCT P(n,a) sqrt(Σ N(n,b)) / (1 + N(n,a))
  • El algoritmo básico selecciona las acciones del camino del playout, y si el estado transpuesto ya existe conecta al nodo existente; al retroceder, incrementa las visitas por arista y luego recalcula N y Q como función de los valores de los hijos
  • Este enfoque es similar a alto nivel a Monte-Carlo Graph Search for AlphaZero de Czech, Korus y Kersting, pero aquí se deriva desde la perspectiva de optimización de política y no desde estadísticas de ejecución

Opciones de implementación: stale Q y forma de actualización

  • El pseudocódigo presentado actualiza solo los nodos del camino realmente recorrido por el playout
  • Por eso, el Q de nodos en caminos no recorridos puede volverse stale Q
  • Aun así, teóricamente sigue siendo correcto
    • Fórmulas de exploración estándar como PUCT prueban todas las acciones infinitamente muchas veces en el límite
    • Cuando un nodo se vuelve a visitar, calcula directamente el Q correcto usando el Q actual de los hijos y las visitas por arista
    • En un DAG, en el límite puede converger al valor óptimo en sentido de teoría de juegos
  • El stale Q sí puede reducir la eficiencia de la búsqueda
    • Puede mantenerse un puntero inmediato a los padres para actualizar también su Q
    • Puede actualizarse a todos los ancestros en orden topológico para eliminar el estado stale
    • Puede actualizarse solo el camino del playout mientras un hilo paralelo separado busca y actualiza nodos stale
  • El pseudocódigo usa actualizaciones idempotentes
    • Sin importar qué actualizaciones intermedias hayan ocurrido antes, una sola visita a un nodo deja N y Q correctos respecto a los valores actuales de sus hijos
  • También son posibles las actualizaciones incrementales, pero en grafos es más difícil hacerlas equivalentes, o equivalentes en el límite
  • Czech et al. abordaron esto desde la perspectiva de estadísticas de ejecución, por lo que usan fórmulas más incrementales
    • Guardan no solo las visitas por arista, sino también el Q de la arista
    • Incluyen un mecanismo para que stale Q se ponga al día gradualmente con el valor más reciente, junto con hiperparámetros de tolerancia al error
  • El pseudocódigo presentado muestra que MCGS puede funcionar sin nuevos parámetros de tolerancia al error ni almacenamiento de Q por arista
  • KataGo actualmente usa la fórmula idempotente

Si conviene continuar el playout desde un hijo transpuesto

  • En MCTS de árbol, incrementar una visita por arista e incrementar una visita del hijo son el mismo evento
  • En grafos, por la transposición, el nodo hijo puede haber sido visitado muchas más veces que esa arista en particular
  • En ese caso podría considerarse que el nodo hijo ya fue suficientemente visitado, detener el playout, incrementar solo la visita por arista y luego actualizar el padre y sus ancestros
  • Razones para preferir detenerse
    • Si la visita por arista es baja y la visita del hijo es alta, la información marginal de darle otra visita adicional al hijo puede ser pequeña
  • Razones para preferir continuar
    • Un nodo con más visitas del hijo que visitas por arista probablemente reciba transposiciones desde muchos padres, y por eso una evaluación más precisa puede ser importante porque impacta a más padres
  • Esta decisión sigue siendo un área experimental
    • También es posible un enfoque por umbral que solo se detenga cuando el número de visitas del hijo sea suficientemente mayor que el número de visitas por arista
  • KataGo por defecto detiene el playout, pero ofrece opciones de configuración para continuarlo o detener solo una fracción de ellos de manera probabilística
  • El pseudocódigo no detiene el playout, y si se quiere puede añadirse una verificación de una línea con la condición child.N <= edge_visits

Hashes, nodos terminales y ciclos reales del juego

  • En el pseudocódigo, los nodos terminales del juego se recalculan con N = 1, U = Q = utilidad del resultado del juego, sin importar el número de visitas
    • Como el número de visitas de la arista correspondiente en el padre sí aumenta normalmente, este enfoque también funciona
    • Si el resultado del juego es probabilístico y no puede calcularse directamente la utilidad esperada, puede ser importante incrementar N en cada visita al nodo terminal y promediar los resultados muestreados
  • También es posible tratar la utilidad terminal de forma más amplia para propagar más rápido valores demostrables hacia arriba en el grafo
    • MCTS/MCGS general no tiene un mecanismo para reconocer valores de utilidad ciertos, así que cuando los estados terminales son importantes no converge al valor óptimo tan barato como búsquedas clásicas tipo alpha-beta
  • Para encontrar transposiciones se asume un hash único del estado del juego
    • Construir un hash realmente libre de colisiones para estados complejos de juego puede ser difícil y costoso
    • Un Zobrist hash lo bastante grande, de 128 o 192 bits, suele ser suficiente en la práctica para evitar colisiones salvo en estados creados de forma adversarial
    • Para evitar recursión infinita cuando una colisión de hash genere un ciclo, puede añadirse detección de ciclos
  • No se trata en detalle el manejo de ciclos que surgen de reglas reales del juego, como superko en Go o la triple repetición en ajedrez
  • El apéndice del 2024-03-10 ofrece un enlace a Google Docs con ideas más preliminares sobre repeticiones y manejo de ciclos, y puede requerirse experimentar con heurísticas específicas de cada juego
  • En el tratamiento de Go de KataGo se aprovecha un teorema específico del juego que dice que, tras cierta jugada, para volver a la posición original hacen falta al menos S + E - 1 jugadas, con lo que se puede limitar de forma estable el compartido de nodos en situaciones relacionadas con ciclos

Lecturas relacionadas

1 comentarios

 
GN⁺ 2024-03-11
Opiniones en Hacker News

  • Creo que este tipo de búsqueda en grafos es necesaria para hacer avanzar el razonamiento de la IA. Es muy probable que un LLM por sí solo falle.
    El enlace contiene muchas buenas referencias, incluida la hashing de Zobrist para tablas de juego: https://en.wikipedia.org/wiki/Zobrist_hashing
    Para que el costo computacional de la búsqueda en grafos no explote, hay que encontrar un buen hashing adecuado para descripciones de estado basadas en lenguaje.
    Sobre búsqueda en árboles, también vale la pena leer Thinking Fast and Slow: https://arxiv.org/abs/1705.08439 y Teaching Large Language Models to Reason with Reinforcement Learning, que compara un enfoque MCTS con otras estrategias actuales de aprendizaje por refuerzo: https://arxiv.org/abs/2403.04642

    • Esto me parece demasiado de bajo nivel.
      Una forma de ir un paso más allá podría ser aprender conjuntamente la representación de estado y el algoritmo de búsqueda. Sería algo así como que el algoritmo de búsqueda explore sobre una representación de estado de una red neuronal, de la cual pueda obtener costos.
      https://sites.google.com/view/genie-2024/
      Genie de DeepMind es un buen ejemplo de modelado de estados discretos. La red neuronal aprende una representación muy compleja que incluye detección de colisiones y acciones. En vez de decodificar ese estado a píxeles, probablemente se podría buscar directamente sobre ese estado.
      Claro que, en la práctica, esta estructura podría ser bastante distinta.
    • Aunque está demasiado simplificado, creo que un enfoque que valdría la pena explorar sería este:
      tomar un conjunto de argumentos lógicos, encontrar una forma de asignarle un hash a cada argumento y representar esos hashes de argumentos como un árbol de Merkle superpuesto según primeros principios.
      Si un argumento es refutado con éxito, cambia el hash de ese argumento y también quedan invalidados los hashes de los argumentos inferiores.
    • Me pregunto si no será posible combinar ambos de alguna manera. Es difícil creer que el cerebro use una sola técnica para todo; parece más probable que tenga varias herramientas y, por encima de ellas, un selector que decide qué herramienta usar y cuándo.

  • Al ver el autor en la URL de HN, enseguida reconocí que era el genio que creó KataGo: https://github.com/lightvector/KataGo
    Sus publicaciones en https://www.reddit.com/r/cbaduk/ también son consistentemente excelentes.

    • La URL está literalmente dentro del repositorio de KataGo.

  • No tengo muchísima experiencia en ajedrez, pero soy escéptico ante la afirmación de que, dentro del árbol de búsqueda, las mismas posiciones se repiten con una frecuencia lo bastante importante. Me gustaría ver mediciones reales con Leela Zero.
    Si se incluyen en el estado la triple repetición y la regla de los 50 movimientos, la probabilidad de repetición debería bajar mucho más; y aun sin considerar esa parte, me parece que es así.

    • En go, el ko es muy común. No se puede repetir exactamente la posición del tablero, pero si la búsqueda en árbol no evalúa correctamente las posiciones de ko, es fácil crear situaciones en las que la IA haga malas jugadas.

  • Me parece raro el pasaje que dice que, pese al nombre “Monte-Carlo Tree Search”, en el algoritmo anterior no hay nada de Monte Carlo y es completamente determinista. ¿El MCTS que se implementa normalmente es determinista? Yo pensaba que había aleatoriedad en el muestreo.

    • Originalmente MCTS sí tenía aleatoriedad. Creo que el texto también lo menciona: consistía en hacer playouts para evaluar la posición al final.
      En los proyectos similares actuales, eso se reemplazó por evaluaciones de redes neuronales de mayor calidad. Jugar movimientos aleatorios para ver quién gana no es una gran estrategia, pero era la mejor conocida en ese momento.
      Al final, la parte Monte Carlo no era un elemento esencial de lo que todavía se llama MCTS, sino más bien una alternativa inferior. Por eso el nombre terminó siendo un poco desafortunado.
    • En sentido estricto, es otro algoritmo bajo el mismo nombre “monte carlo”.
      Lo interesante es que la mayoría de los métodos Monte Carlo dependen de generadores pseudoaleatorios y no de verdaderos generadores de números aleatorios, así que, con la misma semilla y la misma entrada, son métodos deterministas que siempre producen el mismo resultado.
      Este algoritmo, en vez de usar un generador pseudoaleatorio general y heurísticas separadas, consulta a una red neuronal. La red neuronal es una heurística sobre un espacio de búsqueda enorme, así que según su entrenamiento funciona como un generador pseudoaleatorio muy malo, fuertemente sesgado hacia ciertos resultados, y termina viéndose como un generador pseudoaleatorio con heurística aplicada.
      Lo importante es que esto es una especialización de MCTS, por lo que técnicamente no se ajusta a todos los casos de uso.
    • Si hay aleatoriedad, me pregunto si converge y qué cantidad de recursos-tiempo necesita. También puede variar según se mida en CPU, RAM, GPU, TPU o QPU.

  • Cuando investigué MCTS, el paper mencionado en el artículo estaba completamente fuera de mi radar. Creo que sería bastante interesante probar esta modificación directamente en una próxima oportunidad.

  • Estaría bueno tener una introducción sencilla.

    • Al crear una IA para jugar, y en términos amplios esto aplica a toda IA, una de las técnicas más prometedoras es la búsqueda en árbol. Consiste en clasificar la jugada actual en función de las jugadas posteriores.
      En juegos donde se puede llegar al mismo estado por múltiples caminos, se puede desperdiciar mucha memoria registrando repetidamente el mismo nodo de estado en distintas ramas.
      Este artículo analiza bien el enfoque de la búsqueda en grafos. En esencia, consiste en hacer el cálculo adicional de hashear el estado del juego para comprobar si es un nodo ya visitado y, a cambio, ahorrar memoria.
      Como ya no hace falta registrar de nuevo nodos que ya se vieron, el árbol sin ciclos se convierte en un grafo acíclico dirigido.
      Por eso, para obtener resultados correctos, hay que ajustar un poco la búsqueda en árbol. En particular, la unidad de optimización debe alinearse más con las aristas —es decir, acciones o jugadas— que con los vértices, es decir, los estados.
      Es un ensayo técnico bien escrito, en estilo de programación literaria, hecho por alguien que entiende muy bien el tema.