El presente art culo explora la utilizacion de Machine Learning para la produccion automatizada de agentes inteligentes en videojuegos. Concretamente, se muestra la creacion de jugadores automaticos del videojuego clasico Breakout para la consola Atari 2600. La simplicidad de este videojuego permite centrarse en el problema principal tratado: el correcto ajuste de parametros para la obtencion de resultados deseados. En concreto, se analiza el ajuste de Q-Learning y su relacion con los resultados de aprendizaje obtenidos. La metodolog a aplicada en este art culo es facilmente aplicable a cualquier otro videojuego o entorno, permitiendo la utilizacion de Q-Learning para generar distintos agentes inteligentes de manera automatica cuyo comportamiento sea ajustablemente imperfecto a la par que su cientemente variable pero predecible.
Una de las areas del videojuego que mayor interes y expansion estan teniendo en
los ultimos an~os es la Inteligencia Arti cial [
El desarrollo de personajes arti ciales en videojuegos es comunmente tratado
como creacion de contenido. Un ejemplo lo encontramos en Half Life [
Una posible forma de reducir estos costes y ampliar los l mites de los
personajes disen~ados es utilizar Machine Learning. Machine Learning permite generar
personajes arti ciales mediante entrenamiento. Este entrenamiento depende de
parametros que afectan directamente al resultado. Conociendo la in uencia de
los parametros en el resultado se pueden generar distintos tipos de personajes
arti ciales. Este art culo explora esta in uencia en los agentes entrenados con
Q-Learning [21][22]. Utilizando el videojuego Breakout [
La seccion 2 presenta algunas de niciones y el entorno en que se desarrolla el presente trabajo. La seccion 3 repasa algunos trabajos previos, mientras que la seccion 4 describe el desarrollo principal de este trabajo. La seccion 5 muestra los resultados de los experimentos y, nalmente, la seccion 6 enumera las conclusiones y trabajos futuros. 2
A continuacion se de nen los conceptos que se utilizan en el desarrollo de este
trabajo:
{ Atari 2600 es una videoconsola desarrollada en 1977 y vendida durante
mas de una decada. Posee una CPU de proposito general con una frecuencia
de reloj de 1:19Mhz. Mas de 500 juegos originales fueron publicados para este
sistema y aun hoy siguen apareciendo nuevos t tulos desarrollados por fans.
Una de las partes mas caracter sticas de esta videoconsola es el joystick,
que se puede apreciar junto a la videoconsola en la gura 1. La memoria
RAM tiene muy poca capacidad, concretamente 128 bytes. Debido a las
claras limitaciones de la videoconsola, los juegos de esta son relativamente
sencillos. Esto los convierte en un buen benchmark para tecnicas de Machine
Learning actuales.
{ Breakout es un juego de tipo arcade, como todos los juegos de Atari 2600,
que tiene como objetivo romper todos los bloques que cubren la mitad
superior de la pantalla. El jugador es una pala o raqueta que puede moverse
a la izquierda o a la derecha para golpear una pelota y romper con ella los
bloques. Hay que impedir que la pelota caiga, contando con 5 oportunidades
antes de perder el juego. Se trata de un juego de habilidad que requiere
re ejos, calculo y reaccion rapida para poder dominarlo. En la gura 1 se
muestra una captura del momento inicial del juego.
{ Arcade Learning Environment (ALE, entorno de aprendizaje de Arcade)
es un entorno de programacion que incluye el emulador Stella [
action reward state Agent
Enviroment { Reinforcement Learning (aprendizaje por refuerzo) es un tipo espec co de aprendizaje dentro del campo del Machine Learning muy utilizado para juegos y entornos interactivos [17]. Se caracter za por realizar un entrenamiento mediante sen~ales de refuerzo, por no poder determinarse a priori la mejor decision absoluta ante un estado cualquiera. En este caso, las sen~ales de refuerzo representan una evaluacion de las acciones tomadas similar a una funcion de idoneidad. Los entornos interactivos y juegos tienen en comun esta ultima parte: no es posible determinar la existencia de una mejor accion absoluta ante un determinado estado del mundo, pero s evaluar las acciones en funcion de los resultados. 3
Desde los inicios del Machine Learning hasta la actualidad han habido numerosos avances importantes. En todo este tiempo, los juegos han estado siempre presentes. Ya en 1957, Arthur L. Samuel se intereso por el juego de las damas [13] introduciendo algunas tecnicas de Machine Learning iniciales como rote learning. Samuel manifesto su pensamiento de que ensen~ar a los ordenadores a jugar era mucho mas productivo que disen~ar tacticas espec cas para cada juego.
En 1992, Gerald Tesauro desarrollo una de las primeras aplicaciones de Reinforcement Learning conocidas en juegos: TD-Gammon [19][18]. TD-Gammon es el primer programa que consiguio jugar al Backgammon por encima del nivel de un humano profesional. TD-Gammon utiliza una red neuronal entrenada mediante Temporal-Di erence jugando 1.5 millones de partidas contra s misma. La red aproxima el valor de las jugadas, pudiendo obtener la mejor o una muy buena aproximacion, incluso en situaciones que nunca antes ha visto.
Aunque el objetivo del Machine Learning es el aprendizaje autonomo a partir
de datos, los algoritmos han sido aplicados tradicionalmente con un proposito
concreto. Los ejemplos de Samuel y Tesauro [13][19][18] son una muestra:
concebidos para jugar al Backgammon y las damas exclusivamente, similar al conocido
DeepBlue[
Pese a los grandes avances en Machine Learning, el sector profesional del
desarrollo de videojuegos sigue disen~ando los personajes arti ciales manualmente
[
Es importante matizar que la metodolog a propuesta incluye extraccion
manual de caracter sticas, por lo que no es valida para la resolucion de problemas
generales como en [20][
Los algoritmos de Reinforcement Learning desconocen el entorno en que actuan. El entrenamiento es el proceso por el cual un agente aprende de la experiencia, es decir, que ajusta sus patrones observacion-accion a patir de un conjunto de observaciones
< st; at; rt+1; st+1 > donde st es el estado actual, at la accion tomada, rt+1 el reward (recompensa) por tomar dicha accion y st+1 el estado siguiente. El objetivo de los agentes es el de realizar las acciones que maximicen su futuro reward. En el juego Breakout, existen tres posibles acciones en cada instante de toma de decision: ir a la izquierda, a la derecha o no moverse.
Para aprender de la experiencia se utilizara Q-Learning [21][22]. El funcionamiento de Q-Learning se basa en Q(s; a), conocida como la funcion actionvalue (accion-valor). Q(s; a) devuelve el valor medio del reward al aplicar la accion a estando en el estado s.
Q(s; a) = E " 1
X krt+k+1 k=0 st = s; at = a #
El factor 2 [0; 1] es el llamado discount factor (factor de descuento). Cuanto mayor sea el valor de , mas \vision" tendra el algoritmo: sera capaz de asociar acciones a futuros rewards (long term reward ). A priori puede intuirse que los valores de cercanos a 1 seran mas optimos para el juego Breakout, ya que los rewards no se obtienen inmediatamente despues de aplicar una accion: es tras la ejecucion de varias acciones posteriores cuando se conoce si una accion concreta era positiva.
Sea Q (s; a) la funcion accion-valor que maximiza el reward. Cuando el numero de iteraciones se acerca a in nito, el algoritmo Q-Learning garantiza la convergencia. Puesto que esto es impracticable, su valor se aproximara actualizandola iterativamente mediante Temporal-Di erence.
Q(st; at)
Q(st; at) + h rt+1 + max Q(st+1; a) a
El parametro 2 [0; 1] es el llamado learning rate (ratio de aprendizaje). Si = 0, Q(s; a) nunca es actualizada y, por tanto, no se produce aprendizaje. Si = 1, Q(s; a) se actualiza lo maximo posible en cada iteracion. Aunque actualizar el maximo puede resultar atractivo, debe tenerse en cuenta que el resultado puede tambien olvidar lo aprendido anteriormente. Un equilibrado ajuste de este parametro es fundamental para potenciar el rendimiento del QLearning.
Es vital que el algoritmo explore en profundidad el conjunto de estados, manteniendo el equilibrio entre exploracion y explotacion. Exploracion es ejecutar acciones que no son las mejores, para actualizar estados no explorados de la funcion Q(s; a). Explotacion es reforzar y perfeccionar el uso de la mejor accion que hemos encontrado hasta el momento (Conocida como greedy action). La bondad de los resultados dependera del equilibrio de estas dos aternativas. En [17] se discuten criterios de seleccion y la di cultad de saber cual de ellos funciona mejor a priori. En este trabajo se utiliza la estrategia -greedy policy por su sencillez y resultados. En cada turno se realiza una accion aleatoria con probabilidad , o la mejor accion encontrada con probabilidad 1 .
En esta propuesta, cada estado s se describe con una 4-tupla: s = (Ball y, Ball vx, Ball vy, Di x) (ver gura 3). Di x evita el uso de una 5-tupla para representar el estado, reduciendo la cantidad total de estados posibles a explorar. Como contrapartida, impide que el algoritmo detecte donde estan las paredes puesto que desconoce la posicion horizontal absoluta de la pelota y el jugador (ver gura 4). Todos los valores se obtienen a partir de la RAM de la consola emulada durante la ejecucion.
La implementacion de Q-Learning propuesta utiliza una tabla en la que cada combinacion de estado s y accion a tiene un valor asociado Q(s; a) (ver la tabla 1 como ejemplo). Inicialmente, todas las combinaciones tienen valor 0. La regla de actualizacion 3 modi ca los valores en tiempo de ejecucion.
Es importante el numero de posibles estados jsj del entorno: cuanto menor sea jsj, mas rapido se actualizara Q(s; a), acelerando el aprendizaje. En un espacio continuo, jsj = inf, por lo que una discretizacion previa ser a imprescindible. Breakout no esta en un espacio continuo, pero jsj por sus dimensiones puede asimilarse. La estrategia propuesta sera discretizar el espacio dividiendo Di x y Ball y entre un factor de discretizacion d. Cuanto mas grande sea d, menor sera jsj, pero menos precisa sera la percepcion, lo que podra in uir en la calidad de las decisiones. 5
El primer paso es seleccionar un factor de discretizacion d adecuado. Para ello, testeamos nuestro algoritmo con d 2 fN \ [1; 30]g, visualizando los resultados en la gura 5. Atendiendo a la gra ca, d = 10 resulta apropiado por ser el valor mas bajo con recompensas en la zona alta (12-15). Aunque otros d > 10 producen recompensas ligeramente superiores, d = 10 genera un entorno mas preciso. Esto se muestra en la parte inferior de la gura 5: conforme d aumenta, el numero de estados en la tabla Q(s; a) se reduce drasticamente. Por tanto, menos estados, mas actualizaciones, menos tiempo de aprendizaje, menos precision. En estos experimentos, los valores de y se mantienen constantes (se han utilizado f = 0:2, = 1g).
Tras seleccionar d, se buscan valores optimos para y mediante grid search (busqueda en rejilla). Se realizan nuevos entrenamientos con d jo y 2 [0; 1], 2 [0; 1]. La gura 6 la rejilla con los resultados. Los valores optimos se encuentran 2 [0:1; 0:3], 2 [0:9; 1]. Observese que las representaciones gra cas de las guras 5 y 6 nos permiten elegir parametros suboptimos para la tarea u optimos en distintos intervalos. Distintos valores daran lugar a distintos resultados de aprendizaje, pudiendo generar personajes inteligentes de distintos tipos.
Tras haber obtenido unos valores optimizados, el siguiente experimento consiste en alargar el periodo de entrenamiento y observar su evolucion a mas largo plazo. En la gura 7 se observan las curvas de aprendizaje de tres ejecuciones de 15000 episodios para 2 f0:05; 0:1; 0:2g. Resulta interesante ver que = 0:05 obtiene el mejor reward nal pese a no pertenecer al rango optimo seleccionado anteriormente. En cambio, = 0:2 obtiene un aprendizaje mucho mas rapido durante los primeros 2000 episodios pero pronto se produce un estancamiento. Este es el efecto comentado anteriormente del learning rate : valores altos producen un aprendizaje rapido pero menos profundo, mientras que valores bajos tardan mas en aprender pero pueden alcanzar un mejor rendimiento.
Para mejorar mas los resultados de aprendizaje se necesita una combinacion: debe ser alto para aprender rapido y bajo para aprender profundo a largo plazo. Una forma de combinar ambos es usar la tecnica learning rate decay (descenso del ratio de aprendizaje). As pues, se utiliza un nuevo parametro decay D 2 [0; 1]. indicando el factor de reduccion de por cada 1000 episodios. Por tanto, siendo i el learning rate para el episodio i, i = 0 Es decir, con D = 0:2 el learning rate se reduce un 20% cada 1000 episodios. Esto permite acelerar el aprendizaje al inicio y profundizar a largo plazo. Tras introducir decay, los resultados mejoran como puede verse en la gura 8.
La gura 8 muestra como valores altos como D = 0:5 hacen disminuir el learning rate demasiado rapido afectando al aprendizaje. Sin embargo, resulta interesante tambien apreciar que la curva se vuelve mas estable (la varianza se reduce). Ajustando D = 0:2 el aprendizaje parece crecer linealmente incluso mas alla de los 15000 episodios. Aun siendo un buen resultado, el efecto del decay hara tender a 0, por lo que la curva terminara convergiendo igualmente. En este trabajo hemos hecho enfasis en las potenciales ventajas del Machine Learning a la hora de potenciar nuevas v as de produccion de Inteligencia Arti cial en la industria del videojuego. Utilizando Reinforcement Learning es posible generar distintos tipos de personajes arti ciales con capacidades con inteligencias cre bles, variables y mas humanas. Todo depende de una buena seleccion de parametros de entrenamiento.
El principal problema con los algoritmos de Reinforcement Learning como Q-Learning es su delicado ajuste para conseguir convergencia en valores de rendimiento deseados. En este estudio hemos mostrado paso a paso como el adecuado ajuste de parametros y la aplicacion de tecnicas como la discretizacion y el learning rate decay mejoran los resulados y nos permiten generar distintas variantes.
Tambien hemos mostrado las limitaciones del algoritmo Q-Learning con respecto al taman~o de su tabla de estados. Sin utilizar discretizacion, incluso problemas con pocas variables como el presentado alcanzan cardinalidades muy elevadas en el conjunto de estados, requiriendo un tiempo de exploracion exponencialmente mayor. En la practica esto equivale a no conseguir aprendizaje, ya que el tiempo que se requerir a para hacerlo es generalmente inasumible.
Continuando con los metodos de optimizacion presentados, en futuros trabajos se explorara el uso de aproximaciones de la funcion Q(s; a). Una adecuada tecnica de funtion approximation permitir a mejorar los resultados y escalar el metodo a problemas de mayor taman~o. Ademas, podr a ser otra ventaja el hecho de que el algoritmo resultante fuera mas general. Quiza un solo algoritmo pudiera servir para la generacion de muchos tipos de agente inteligente para distintos juegos. >Ser a posible conseguir esto sin empeorar el rendimiento de los agentes resultantes? 9. Gunther, M., Schi el, S., Thielscher, M.: Factoring general games. In: in Proc. of
IJCAI Workshop on General Game Playing (GIGA (2009) 10. Hausknecht, M.J., Stone, P.: Deep recurrent q-learning for partially observable mdps. CoRR abs/1507.06527 (2015), http://arxiv.org/abs/1507.06527 11. Liang, Y., Machado, M.C., Talvitie, E., Bowling, M.H.: State of the art control of atari games using shallow reinforcement learning. CoRR abs/1512.01563 (2015), http://arxiv.org/abs/1512.01563 12. Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A.A., Veness, J., Bellemare, M.G., Graves, A., Riedmiller, M., Fidjeland, A.K., Ostrovski, G., Petersen, S., Beattie, C., Sadik, A., Antonoglou, I., King, H., Kumaran, D., Wierstra, D., Legg, S., Hassabis, D.: Human-level control through deep reinforcement learning. Nature 518(7540), 529{533 (02 2015), http://dx.doi.org/10.1038/nature14236 13. Samuel, A.L.: Some studies in machine learning using the game of checkers. IBM
J. Res. Dev. 3(3), 210{229 (Jul 1959), http://dx.doi.org/10.1147/rd.33.0210 14. Schi el, S., Thielscher, M.: Fluxplayer: A successful general game player. In: AAAI '07: Proc. 22nd AAAI Conf. Arti cial Intelligence. pp. 1191{1196. AAAI Press (Jul 2007) 15. Silver, D., Huang, A., Maddison, C.J., Guez, A., Sifre, L., van den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M., Dieleman, S., Grewe, D., Nham, J., Kalchbrenner, N., Sutskever, I., Lillicrap, T., Leach, M., Kavukcuoglu, K., Graepel, T., Hassabis, D.: Mastering the game of go with deep neural networks and tree search. Nature 529, 484{503 (2016), http://www.nature.com/nature/journal/v529/n7587/full/nature16961.html 16. Spronck, P., Ponsen, M., Postma, E.: Adaptive game ai with dynamic scripting.
In: Machine Learning. pp. 217{248. Kluwer (2006) 17. Sutton, R.S., Barto, A.G.: Reinforcement Learning, An Introduction. MIT Press
Cambridge, MA, USA c 1998 (1998) 18. Tesauro, G.: Practical issues in temporal di erence learning. In: Machine Learning.
pp. 257{277 (1992) 19. Tesauro, G.: Td-gammon, a self-teaching backgammon program, achieves master-level play. Neural Comput. 6(2), 215{219 (Mar 1994), http://dx.doi.org/10.1162/neco.1994.6.2.215 20. Veness, J., Bellemare, M., Hutter, M., Chua, A., Desjardins, G.: Compress and control. In: Proc. 29th AAAI Conference on Arti cial Intelligence (AAAI'15). pp. 3016{3023. AAAI Press, Austin, USA (2015), http://arxiv.org/abs/1411.5326 21. Watkins, C.J.C.H.: Learning from Delayed Rewards. Ph.D. thesis, King's Collage (1989) 22. Watkins, C.J.C.H., Dayan, P.: Q-learning. Machine Learning 8(3-4), 279{292 (1992)