Algunas dudas sobre la aplicación del aprendizaje por refuerzo a juegos como el ajedrez

9

Inventé un juego de tablero similar al ajedrez. Construí un motor para que pueda jugar de forma autónoma. El motor es básicamente un árbol de decisión. Está compuesto por:

  1. Una función de búsqueda que en cada nodo encuentra todos los movimientos legales posibles
  2. Una función de evaluación que asigna un valor numérico a la posición del tablero (positivo significa que los primeros jugadores están ganando la delantera, negativo significa que el segundo jugador está ganando)
  3. Un algoritmo de poda alfabeta negamax

El principal problema de este motor es que la optimización de la función de evaluación es realmente complicada. No sé qué factores considerar y qué pesos poner. La única forma en que veo para mejorar el motor es iterar juegos intentando cada vez diferentes combinaciones de factores y pesos. Sin embargo, computacionalmente parece una hazaña muy difícil (¿Puedo propagar hacia atrás sin usar el aprendizaje profundo?).

Me gustaría utilizar el aprendizaje por refuerzo para mejorar el motor jugando contra sí mismo. He estado leyendo sobre el tema, pero todavía estoy bastante confundido.

¿Qué otra recompensa hay en un juego como parte del resultado de ganar o perder (1 o 0)? Si uso otras recompensas, como el resultado de la función de evaluación en cada turno, ¿cómo puedo implementarlo? ¿Cómo modifico la función de evaluación para obtener mejores recompensas iteración tras iteración?

Pigna
fuente

Respuestas:

6

Me gustaría utilizar el aprendizaje por refuerzo para mejorar el motor jugando contra sí mismo. He estado leyendo sobre el tema pero todavía estoy bastante confundido.

Tenga cuidado: el aprendizaje por refuerzo es un tema grande y complejo. Aunque puede llevarlo a un desvío de los bots que juegan juegos, es posible que desee estudiar los conceptos básicos de RL. Un buen lugar para comenzar es Sutton & Barto Reinforcement Learning: An Introduction

¿Qué otra recompensa hay en un juego como parte del resultado de ganar o perder (1 o 0)?

Dependiendo de tu juego, eso suele ser. En realidad, para un juego de ganar / empatar / perder como el ajedrez, la recompensa de cada acción es 0, excepto por ganar (+1) o perder (-1) al final. En un juego de suma cero, esto se alinea muy bien con minimax, poda alfabeta, etc.

El aprendizaje por refuerzo está destinado a abordar entornos con recompensas retrasadas. Agregar recompensas de "ayuda" para no objetivos provisionales suele ser contraproducente.

Si uso otras recompensas, como el resultado de la función de evaluación en cada turno, ¿cómo puedo implementarlo?

Por lo general no lo haces. Lo que aplicará el RL de auto-juego es aprender una función de retorno (a veces llamada utilidad ) que predice la expectativa de su recompensa total + 1/0 / -1 al final del juego. Usaría esto en lugar de su heurística actual para la búsqueda de minimax. O, potencialmente, ajustaría su función heurística actual para emitir en el mismo rango y usaría RL para optimizar sus pesos para hacer la mejor aproximación a la verdadera función de retorno de juego óptima (que probablemente sea demasiado compleja para calcularla exactamente).

¿Cómo modifico la función de evaluación para obtener mejores recompensas iteración tras iteración?

Eso es lo que los diferentes RL se acercan a todo intento de hacer, hay una variedad de diferentes solucionadores. No hay una forma corta de explicarlo. Puede comenzar con un método simple como Q-Learning . Q-Learning aprende estimaciones de Q (s, a) (llamado el valor de acción), que es el rendimiento esperado cuando está en estado sy toma la acción a, y luego sigue una política óptima. Para comenzar, hace una suposición arbitraria y la refina más cerca del verdadero valor con cada paso realizado en el entorno de aprendizaje. Los estudiantes de Q tabulares simples hacen este refinamiento simplemente almacenando una gran tabla de todos los estados y acciones con la mejor estimación hasta el momento del valor verdadero, y promediando cada nueva estimación a medida que se experimenta.

También es posible combinar un método de RL para heurística con búsqueda de minimax con anticipación: eso es lo que hizo el AlphaGo original y lo que hace AlphaGo Zero durante el entrenamiento. Este es un enfoque poderoso porque la búsqueda minimax funcionará para verificar dos veces la heurística generada por RL. Aunque para juegos lo suficientemente simples, RL puede aprender heurística perfecta y solo necesitaría una búsqueda local (cuál debería ser el próximo movimiento).

A menos que su juego sea muy simple (todos los estados posibles cabrían en la memoria), necesitará algún tipo de aproximador de funciones dentro del algoritmo RL. Las redes neuronales son una opción estándar. Tener algo para esa parte es inevitable, aunque otra buena opción es definir un conjunto de características proxy (que podría usar para construir una heurística a mano) y usar un aproximador lineal, solo una suma ponderada de todas las características. Esto puede funcionar lo suficientemente bien, y se ha utilizado, por ejemplo, en damas (draft) jugadores entrenados con RL.

De hecho, siempre que su propia función heurística no sea demasiado inusual, probablemente pueda tratarla como un aproximador lineal y usar RL para aprender los mejores pesos para ella.

Neil Slater
fuente
"El aprendizaje por refuerzo está destinado a abordar entornos con recompensas retrasadas. Agregar recompensas" auxiliares "para las no metas provisionales suele ser contraproducente". Me gustaría señalar que hay un documento que intenta resolver el problema de las escasas recompensas mediante la introducción de objetivos intermedios " Retrospectiva de experiencia retrospectiva ".
nbro
1
@nbro: Hay muchos intentos de resolver recompensas escasas, es una gran pregunta abierta en RL, una forma de aumentar el desafío de un problema es hacer que las recompensas sean más escasas. Los rastros de elegibilidad son otro intento, Hierarchical RL es otra área prometedora. . . Sin embargo, no creo que quiera agregar estas técnicas a la respuesta aquí, ya que se trata más de la viabilidad del problema de OP y una introducción al tema
Neil Slater