¿Cómo usar árboles minmax con Q-learning?

Question

¿Cómo usar árboles minmax con Q-learning?

Quiero implementar un agente Q-Learning Connect Four y escuchar que agregar árboles Minmax en él ayuda.

Answer 1

Q-learning es un Aprendizaje de diferencia temporal algoritmo. Para cada estado posible (Junta), aprende el valor de las acciones disponibles (movimientos). Sin embargo, no es adecuado para su uso con Mínimo, Debido a que el algoritmo Minomax necesita una función de evaluación que devuelva el valor de una posición, no el valor de una acción en esa posición.

Sin embargo, los métodos de diferencia temporal se pueden usar para aprender dicha función de evaluación. En particular, Gerald Tesauro utilizó el algoritmo TD (λ) ("TD lambda") para crear Td-gamon, un programa de juego de backgammon competitivo humano. Escribió un artículo que describe el enfoque, que puedes encontrar aquí.

TD (λ) se extendió más tarde a Tdleaf (λ), específicamente para tratar mejor las búsquedas Minimax. Tdleaf (λ) se ha utilizado, por ejemplo, en el programa de ajedrez KnightCap. Puedes leer sobre TDLeaf en este papel.

Answer 2

Minimax le permite mirar una serie de movimientos hacia el futuro y jugar para maximizar sus posibilidades de anotar en ese momento. Esto es bueno para Connect-4, donde un juego puede terminar casi en cualquier momento y el número de movimientos disponibles en cada turno no es muy grande. Q-Learning le proporcionaría una función de valor para guiar la búsqueda Minimax.