TD-Gammon es un programa informático de backgammon desarrollado en la década de 1990 por Gerald Tesauro en el Centro de Investigación Thomas J. Watson de IBM. Su nombre deriva de su uso de una red neuronal artificial entrenada mediante aprendizaje por diferencias temporales, específicamente TD-Lambda. Exploró estrategias que los humanos no habían seguido y condujo a avances en la teoría del juego correcto de backgammon. En 1993, TD-Gammon (versión 2.1) fue entrenado con 1.5 millones de partidas de auto-juego y alcanzó un nivel de juego ligeramente inferior al de los mejores jugadores humanos de backgammon de la época. En 1998, durante una serie de 100 partidas, fue derrotado por el campeón mundial por un margen de solo 8 puntos. Su evaluación poco convencional de algunas estrategias de apertura fue aceptada y adoptada por jugadores expertos. TD-Gammon es comúnmente citado como un éxito temprano del aprendizaje por refuerzo y las redes neuronales, y fue referenciado en artículos sobre Q-learning profundo y AlphaGo.
Algoritmo para Jugar y Aprender
Durante el juego, TD-Gammon examina en cada turno todos los movimientos legales posibles y todas sus posibles respuestas (búsqueda de lookahead), alimenta cada posición resultante del tablero en su función de evaluación y elige el movimiento que conduce a la posición del tablero que obtuvo la puntuación más alta. En este aspecto, TD-Gammon no es diferente de casi cualquier otro programa de juegos de tablero por computadora. La innovación de TD-Gammon fue en cómo aprendió su función de evaluación.
El algoritmo de aprendizaje de TD-Gammon consiste en actualizar los pesos de su red neuronal después de cada turno para reducir la diferencia entre su evaluación de las posiciones del tablero de turnos anteriores y su evaluación de la posición del tablero del turno actual - de ahí "aprendizaje por diferencias temporales". La puntuación de cualquier posición del tablero es un conjunto de cuatro números que reflejan la estimación del programa de la probabilidad de cada posible resultado del juego: Blanco gana normalmente, Negro gana normalmente, Blanco gana un gammon, Negro gana un gammon. Para la posición final del tablero del juego, el algoritmo compara con el resultado real del juego en lugar de su propia evaluación de la posición del tablero.
El núcleo de TD-Gammon es una red neuronal con 3 capas. La capa de entrada tiene dos tipos de neuronas. Un tipo codifica la posición del tablero: enteros no negativos que van de 0 a 15, indicando el número de fichas blancas o negras en cada ubicación del tablero, con 99 neuronas de entrada para cada uno, totalizando 198 neuronas. Otro tipo codifica características diseñadas a mano previamente utilizadas en Neurogammon, codificando conceptos estándar usados por expertos humanos como "ancla avanzada", "fuerza de bloqueo", "fuerza del tablero de casa" y la probabilidad de que un "blot" (ficha individual) sea golpeado. La capa oculta contiene neuronas ocultas, con versiones posteriores teniendo más. La capa de salida contiene 4 neuronas, representando la estimación de la red de la probabilidad ("equidad") de que el tablero actual conduzca a: victoria normal de Blanco, victoria por gammon de Blanco, victoria normal de Negro, victoria por gammon de Negro. La victoria por backgammon es tan rara que Tesauro optó por no representarla.
Después de cada turno, el algoritmo de aprendizaje actualiza cada peso según la regla: w_{t+1} - w_t = alpha (Y_{t+1} - Y_t) sum_{k=1}^{t} lambda^{t-k} grad_w Y_k, donde alpha es la tasa de aprendizaje, Y_t es la evaluación en el turno t, y lambda es el parámetro de decaimiento. Se encontró que elegir un lambda pequeño ofrecía un rendimiento aproximadamente igual de bueno, y un lambda grande degradaba el rendimiento. Debido a esto, después de 1992, TD-Gammon fue entrenado con lambda = 0, degenerando en aprendizaje TD estándar, lo que ahorró cómputo por un factor de 2.
Historia del Desarrollo
La versión 1.0 usaba una búsqueda simple de 1-ply: cada movimiento siguiente es puntuado por la red neuronal, y se selecciona el movimiento con la puntuación más alta. Las versiones 2.0 y 2.1 usaban búsqueda de 2-ply: primero un análisis de 1-ply para eliminar movimientos poco probables ("poda hacia adelante"), luego un análisis minimax de 2-ply solo para los movimientos probables, eligiendo el mejor movimiento ponderado por probabilidad de cada uno de los 21 posibles lanzamientos de dados del oponente (ponderando los no dobles el doble que los dobles). Las versiones 3.0 y 3.1 usaban búsqueda de 3-ply, usando 21^2 = 441 posibles lanzamientos de dados en lugar de 21. La última versión, 3.1, fue entrenada específicamente para un partido de exhibición contra Malcolm Davis en el AAAI Hall of Champions de 1998. Perdió con -8 puntos, principalmente debido a un error grave, donde TD-Gammon optó por doblar y fue gammoneado con -32 puntos.
Experimentos y Etapas de Entrenamiento
A diferencia de programas anteriores de backgammon con redes neuronales como Neurogammon (también escrito por Tesauro), donde un experto entrenaba el programa proporcionando la evaluación "correcta" de cada posición, TD-Gammon fue inicialmente programado "sin conocimiento". En experimentos tempranos, usando solo una codificación cruda del tablero sin características diseñadas por humanos, TD-Gammon alcanzó un nivel de juego comparable a Neurogammon: el de un jugador humano de backgammon de nivel intermedio.
Aunque TD-Gammon descubrió características perspicaces por sí mismo, Tesauro se preguntó si su juego podría mejorarse usando características diseñadas a mano como las de Neurogammon. De hecho, el TD-Gammon auto-entrenado con características diseñadas por expertos pronto superó a todos los programas anteriores de backgammon por computadora. Dejó de mejorar después de aproximadamente 1,500,000 partidas (auto-juego) usando una red neuronal de tres capas, con 198 unidades de entrada codificando características diseñadas por expertos, 80 unidades ocultas y una unidad de salida representando la probabilidad predicha de ganar.
Avances en la Teoría del Backgammon
El entrenamiento exclusivo de TD-Gammon a través del auto-juego (en lugar de aprendizaje por imitación) le permitió explorar estrategias que los humanos no habían considerado previamente o habían descartado erróneamente. Su éxito con estrategias poco ortodoxas tuvo un impacto significativo en la comunidad de backgammon. A finales de 1991, Bill Robertie, Paul Magriel y Malcolm Davis fueron invitados a jugar contra TD-Gammon (versión 1.0). Se jugaron un total de 51 partidas, con TD-Gammon perdiendo con -0.25 ppg. Robertie encontró que TD-Gammon estaba al nivel de un jugador humano fuerte, y sus movimientos poco convencionales fueron posteriormente adoptados por expertos, cambiando la comprensión de la estrategia de apertura.
Legado e Influencia
TD-Gammon es ampliamente reconocido como un hito en el aprendizaje automático y la inteligencia artificial, demostrando que una red neuronal podía aprender juegos estratégicos complejos a través del auto-juego y el aprendizaje por diferencias temporales. Su éxito inspiró trabajos posteriores en aprendizaje por refuerzo, incluido el desarrollo de redes Q profundas y AlphaGo. La capacidad del programa para descubrir estrategias novedosas que los humanos habían pasado por alto destacó el potencial de las redes neuronales para superar la intuición humana en el juego, y sigue siendo un ejemplo clásico en la historia de la investigación en IA.