Entendiendo AlphaZero

29

Muy recientemente, salió la noticia de que el equipo de investigación DeepMind de Alphabet ha ampliado su motor de aprendizaje automático para jugar tanto al Shogi como al ajedrez. Aparentemente, después de solo unas pocas horas de autoaprendizaje, es decir, solo jugando contra sí mismo dadas las reglas de los juegos, su rendimiento en el ajedrez ya ha superado el de los principales motores actuales como Stockfish 8. Personalmente, todavía no sé cómo se configuraron exactamente las coincidencias, ya que bajo qué condiciones se estableció Stockfish, ya que si los tiempos de cálculo son limitados, los motores pueden funcionar muy mal. En cualquier caso, este es un logro muy impresionante, porque incluso si resulta que uno podría haber configurado Stockfish de manera más óptima, con pocas horas adicionales de entrenamiento, AlphaZero superaría nuevamente el nivel de juego, lo que significa que AlphaZero es fundamentalmente más fuerte que cualquier corriente. motor de ajedrez estándar basado en funciones de evaluación heurística.

Ahora, a la luz de esta noticia, sería genial si alguien pudiera explicar las principales diferencias en el funcionamiento de un motor de ajedrez aprendido por la máquina en comparación con los motores estándar que todos estamos acostumbrados a usar. Más concretamente:

  1. ¿No es la función de evaluación que utiliza AlphaZero, entrenada por métodos de aprendizaje automático, al final otra función de evaluación heurística? En caso afirmativo, sería justo decir que la diferencia fundamental entre las funciones de evaluación de los dos motores es el hecho de que Stockfish tiene una función de evaluación optimizada ajustada a mano por los humanos, lo que significa que la definición de la función para optimizar es fija, mientras que para AlphaZero, ¿la función de evaluación de objetivos se redefine constantemente a través de capacitación adicional (por ejemplo, a través del auto-juego)? Hacer de este último un enfoque mucho más dinámico.
  2. En última instancia, vagamente hablando, un motor como Stockfish, aplica su función de evaluación al árbol de posibles movimientos, decidiendo qué ramas mantener y cuáles dejar caer, luego a través de un concreto más profundoEl análisis de cada rama, nuevamente a través de su función de evaluación, determina qué rama produjo el valor más alto, y eso se convierte en la variación principal (por supuesto, hay muchas técnicas avanzadas en torno a este proceso para podar eficientemente este gran árbol). Es decir, para cada posición, esta rutina extremadamente concreta debe repetirse para que Stockfish tome una decisión. Por el contrario, me imagino que AlphaZero hace algo muy diferente, es decir, no se basa en un análisis concreto del árbol de posibles movimientos en una posición determinada, sino que su función de evaluación esencialmente asigna un valor a esa posición (que intuitivamente es similar a poner la posición actual en analogía con todas las otras posiciones para las que ha sido entrenado), sin tener que realizar tareas concretasanálisis de la manera en que lo hace Stockfish, o incluso un jugador humano. ¿Es esta una imagen sonora del funcionamiento de AlphaZero o motores de aprendizaje automático con capacitación similar?

  3. Sabemos que el espacio de las posiciones de ajedrez es lo suficientemente grande como para que cualquier intento de muestrear todas las posiciones en él sea, en principio, completamente en vano (complejidad EXPTIME), lo que sugeriría que ninguna cantidad de entrenamiento a través del auto-juego sería suficiente para ha explorado todas las posiciones, entonces, ¿cómo puede ser bueno el resultado final a pesar de haber explorado potencialmente una pequeña fracción de las posiciones del espacio a través del auto-juego? ¿Cuál es la idea clave aquí en juego?

  4. Supongo que AlphaZero tiene una forma muy óptima de comparar cualquier posición dada, incluso si es nueva, con una previamente visitada en su conjunto de entrenamiento, cuanto más cercana sea la comparación, más válida será la evaluación que se pueda sacar de la comparación. Por ejemplo, cuando jugó el movimiento Bg5 en el juego 5 , debe haber explorado una estructura similar durante su entrenamiento, es decir, es capaz de reconocer que esta posición es esencialmente equivalente a una (posiblemente completamente) diferente estudiada en su entrenamiento, en analogía de cómo se logra el reconocimiento facial a través del aprendizaje automático, y como resultado concluye que Bg5 debería ser el mejor movimiento, como lo fue en esa (o esas) otras posiciones similares. ¿Es esto una suposición correcta? No tengo idea de cómo esta comparación está hecho, ya que seguramente no es posible almacenar todas las posiciones entrenadas y analizarlas cada vez.

Esto es simplemente un intento de obtener información sobre el funcionamiento de AlphaZero y cómo se llega a una decisión dada una posición.

usuario929304
fuente

Respuestas:

18
  • ¿Cómo selecciona AlphaZero un movimiento en la búsqueda?

Esto es muy obvio en el periódico.

Cada simulación procede seleccionando en cada estado un movimiento con un recuento bajo de visitas, una alta probabilidad de movimiento y una alta selección de vale ...

Qué significa eso? AlphaZero tiene probabilidades entrenadas para cada movimiento (final de la página 2 en el documento) desde una red neuronal profunda. Durante la búsqueda, selecciona un movimiento proporcional a esa probabilidad, y también nodos que tienen un recuento bajo (para garantizar que se explore el espacio de muestreo). Este no es un concepto nuevo, Monte Carlo Tree Search ha estado en la literatura antes de que Google existiera.

------ (Muy) ejemplo áspero ------

Tenemos una posición y tenemos dos movimientos legales.

  • Move 1 es bueno y razonable
  • Move 2 pone a tu propio rey en peligro sin compensación

Según el documento, un modelo profundo entrenado podría estimar las probabilidades como (0.90, 0.10). Digamos que AlphaZero usa 4 iteraciones en Monte Carlo. Las iteraciones podrían verse así:

Iteración 1 : Elija el movimiento 1 porque tiene la mayor probabilidad. Haga una simulación del movimiento 1. Iteración 2 : Elija el movimiento 1 porque tiene la mayor probabilidad. Haga una simulación del movimiento 1. Iteración 3 : Elija el movimiento 1 porque tiene la mayor probabilidad. Haz una simulación del movimiento 1.

Ahora, estamos en la iteración 4. Aunque el movimiento 1 tiene la mayor probabilidad estimada, pero no se ha buscado el movimiento 2 ("recuento bajo de visitas" en el documento), ahora AlphaZero elegiría el movimiento 2 y haría la simulación.

Se considerarían ambos movimientos, pero AlphaZero pondría más recursos informáticos en el movimiento 1 (algo bueno).

AlphaZero luego elegiría la jugada con el mejor resultado esperado.

------------------ Tus preguntas: ------------------

¿No es la función de evaluación que utiliza AlphaZero, entrenada por métodos de aprendizaje automático, al final otra función de evaluación heurística?

La función de evaluación entrenado es una red neuronal profundo, que es no un conjunto de reglas heurísticas, como lo que ves en Bacalao. Nadie entiende completamente (ni siquiera el equipo de Google) la red capacitada, simplemente funciona. Así es como funciona NN en general.

mientras que para AlphaZero, la función de evaluación objetivo se redefine constantemente a través de la función de evaluación objetivo se redefine constantemente a través de capacitación adicional.

La función de evaluación en AlphaZero es un conjunto de neuronas entrenadas (sesgo + pesos). El equipo de Google utilizó máquinas muy potentes para entrenar los parámetros. En general, cuantos más recursos pueda invertir en la capacitación de un modelo de aprendizaje profundo, mejores parámetros obtendrá.

(2)

Stockfish usa alfa-beta, mientras que AlphaZero usa Monte-Carlo. Son dos algoritmos muy diferentes. El algoritmo alfa-beta asume un límite inferior / superior, mientras que Monte-Carlo crea simulaciones desde la raíz hasta la hoja.

haber explorado todas las posiciones, entonces, ¿cómo puede ser bueno el resultado final a pesar de haber explorado potencialmente una pequeña fracción de las posiciones del espacio a través del auto-juego? ¿Cuál es la idea clave aquí en juego?

Google no afirmó que habían resuelto el ajedrez, ni siquiera sus poderosas máquinas podrían enumerar todas las posiciones de ajedrez. Pero no tenían que ... ese es el punto para el aprendizaje automático, el modelo "aprende" del conjunto de entrenamiento. En este caso, el conjunto de entrenamiento proviene del juego personal. La idea clave es jugar tantos juegos de buena calidad contra sí mismo como sea posible y rápidamente.

Por ejemplo, cuando jugó el movimiento Bg5 en el juego 5, debe haber explorado una estructura similar durante su entrenamiento,

No creo que AlphaZero haya encontrado exactamente la misma posición en los juegos de entrenamiento. Creo que una buena lectura de Montecarlo es una buena idea:

https://chessprogramming.wikispaces.com/Monte-Carlo+Tree+Search

AlphaZero pudo jugar el movimiento alcanzando suficiente profundidad. El algoritmo estima la probabilidad esperada de ganar para cada movimiento, aparentemente, el movimiento Bg5 dio la mayor probabilidad esperada.

Puede pensar que AlphaGo pudo buscar tan bien que vio que la probabilidad de ganar es mayor después de Ag5, mientras que Stockfish no consideró el movimiento en serio (y por lo tanto perdió).

SmallChess
fuente
2
"Monte Carlo Tree Search ha estado en la literatura antes de que Google existiera" Solo puedo rastrear el MCTS hasta alrededor de 2006.
CodesInChaos
2
@CodesInChaos MCTS no es una técnica nueva. Google ciertamente no inventó Monte Carlo.
SmallChess
44
Brügmann 1993 es claramente solo MC. MC Go Dev. (2003) combina MC y árboles, pero de una manera primitiva. Chang (2005) está bastante cerca, pero en un contexto diferente y creo que todavía carece de la elección adecuada del nodo para expandir y propagar las estimaciones. Selectividad eficiente y operadores de respaldo en MCTS Remi Coulom (2006) es un MCTS adecuado, por lo que puedo decir, el primero.
CodesInChaos
1
@SmallChess Partes de su respuesta parecen ser contradictorias: "ahora AlphaZero elegiría el movimiento 2 y realizaría la simulación. Ambos movimientos se considerarían, pero AlphaZero pondría más recursos informáticos en el movimiento 1 (algo bueno)". contradice la afirmación Cada simulación procede seleccionando en cada estado un movimiento con un recuento bajo de visitas ... ya que, en su ejemplo, sería 2 en lugar de 1. Para ser sincero, el documento no contiene ninguna información útil para el comprensión, ya que no muestran forma de reproducir el experimento o dar una idea de la forma en que entrenan las redes.
Gented
1
Lo que hacen es esencialmente decir "utilizamos el algoritmo X y funciona", lo que proporciona poca o ninguna comprensión de los métodos en sí mismos, por lo que no me enfocaría demasiado en el papel para tratar de descubrir qué es lo que realmente hace.
Gented
0

Creo que mi pregunta sería cómo la red neuronal "aprende" qué hacer en una posición que no ha encontrado. Decir que el AZ real ejecuta un MCTS usando el sesgo + pesos de la red neuronal entrenada simplemente lo empuja un paso hacia atrás a cómo la red neuronal calcula estos valores. Si fue a través del juego aleatorio, sin conocimiento humano, ¿cómo decide cómo ponderar una posición que nunca ha visto?

Roy Koczela
fuente
1
Creo que podría responderte, pero no aquí. Por favor, comience una nueva pregunta.
SmallChess