¿Cómo diseñarías un sistema de aprendizaje automático para jugar a Angry Birds?

Question

Después de jugar demasiado a Angry Birds, empecé a observar mis propias estrategias. Resulta que desarrollé un enfoque muy específico para conseguir 3 estrellas en cada nivel.

Eso me hizo preguntarme por los retos de desarrollar un sistema de aprendizaje automático que fuera capaz de jugar a Angry Birds. Interactuar con el juego y lanzar los pájaros es trivial. Pero una pregunta que me surgió es sobre los "bloques de construcción" del sistema.

Los sistemas de aprendizaje automático parecen funcionar con conceptos o conocimientos sencillos sobre el problema. Esto suele codificarse como características de entrada. Así que parece que el sistema necesita tener la capacidad de entender algunos conceptos de alto nivel para generar una estrategia.

¿Es esto cierto? Además, ¿cuáles son los retos o las partes difíciles de desarrollar un sistema de este tipo?

EDITAR #1:

He aquí una aclaración. Conseguir 3 estrellas es un problema difícil porque hay que maximizar los puntos. Esto se puede hacer de dos maneras no excluyentes: 1) Minimizando el número de pájaros utilizados (obtienes 10.000 puntos por cada pájaro no utilizado). 2) Maximizando la destrucción de cristal, madera y otros objetos. Cada objeto destruido te da puntos. Es posible destruir más de 10.000 puntos en objetos con un solo pájaro.

He aquí una explicación más detallada de los "conceptos de alto nivel". Para maximizar los puntos descritos anteriormente, necesitas utilizar los poderes especiales de cada pájaro. Eso significa lanzar diferentes pájaros con diferentes trayectorias, dependiendo de la disposición del mapa. Y, mientras juego, desarrollo una estrategia que destruye ciertas zonas con determinados pájaros en un orden determinado.

Parece que sin una comprensión de cómo utilizar cada pájaro para destruir un área específica el sistema no podía aprender a conseguir 3 estrellas. Entonces, ¿cómo se gestiona y codifica algo así? ¿Cómo se garantiza que el sistema pueda aprender estos conceptos de alto nivel?

Answer 1

Suponiendo que puedas conseguir los ganchos adecuados en el software (o que trabajes con tu propia maqueta), algunas cosas serían fáciles aquí, y otras no tanto. Creo que es un problema bastante difícil. Como mencionó carlosdc, Aprendizaje por refuerzo (RL) es una posible vía, aunque no estoy seguro de que sea la correcta.

Cuando empiece, tendrá que definir cuál es su espacio de estado , espacio de acción , dinámica de transición y función de recompensa son. Los espacios de estado/acción pueden ser continuos o discretos, y la dinámica de transición puede venir dada por el problema o modelarse matemáticamente. Por último, la función de recompensa puede venir dada a-priori (con o sin ruido).

El espacio de acción es sencillo: se trata simplemente de la dirección y la potencia con la que disparas al pájaro actual. Para el ser humano, se trata de un problema discreto (el ratón/pantalla táctil es un dispositivo de entrada digital): digamos (por ejemplo) que hay 32 direcciones y 10 potencias posibles, lo que da 320 acciones posibles.

La función de recompensa también es bastante fácil de deducir: el objetivo es deshacerse de todos los cerdos con el menor número de pájaros (de acuerdo, hay puntos extra por otras cosas, pero ignorémoslo por ahora). Lo mejor sería conocer la función real que genera puntos por matar cerdos (depende del tamaño del cerdo, etc.), pero para un solo nivel podría modelarse perfectamente.

El espacio de estados y la dinámica de transición son mucho más difícil. Para modelar esto correctamente, tendríamos que conocer todo el trazado del mapa y la física del juego. La dinámica de transición dice "Si estoy en el estado x y realizo la acción y aterrizaré en el estado z ". Se puede ver la dificultad de esto, en primer lugar como la compleja física del sistema significa que esto será extremadamente difícil de modelar con precisión, y en segundo lugar como hay tantos posibles estados resultantes después incluso de la primera ronda (320), y esto es si suponemos que no hay ninguna estocasticidad en el motor de física, que por haberlo jugado sospecho que lo hay. Creo que a estas alturas te darías por vencido y te irías a casa.

Otro enfoque es tratarlo como lo hace un humano al principio, es decir, ensayo y error. El humano, al menos al principio, dispara prácticamente al azar (aunque con una prioridad bastante fuerte de enviar a los pájaros hacia los cerdos, pero esto se puede codificar fácilmente), hasta que se encuentra una serie de buenas acciones. Esto se parece más al bandido multibrazo ajuste. Los "brazos" de los bandidos son aquí las acciones posibles. El algoritmo intenta equilibrar la exploración y la explotación, es decir, explorar el espacio de acciones y explotar las buenas acciones cuando se encuentran. Para ello no necesitas saber nada sobre la dinámica subyacente, sólo sobre las acciones y las recompensas. Para hacerlo completamente tendrías que tener un brazo para cada acción posible en todas las rondas (por ejemplo, tienes 5 pájaros * 320 acciones = 320^5 = aproximadamente 10^12 acciones), ¡así que el espacio de acción es muy grande! Sin embargo podrías usar algunos trucos para mejorar esto si sabes un poco sobre el espacio de estados. Por ejemplo, probablemente puedas descartar acciones que envíen al pájaro lejos de los cerdos, al suelo, o sin suficiente potencia para alcanzar alguno de ellos. Además, sólo tienes que llegar al quinto pájaro si no has matado a los cerdos en las rondas anteriores, por lo que una parte de los estados de acción no son realmente posibles. Esto recuerda en cierto modo al planteamiento utilizado en el algoritmo MoGo que es un programa informático para jugar al Go basado en Límites superiores de confianza aplicados a los árboles un enfoque para resolver el problema del bandido armado múltiple.

Answer 2

¡Buena pregunta!

Parece que esta pregunta es sobre la técnica natural para este tipo de problema. Creo que la técnica natural para este tipo de problema es aprendizaje por refuerzo (RL). La RL trata de cómo un agente debe actuar en un entorno. en un entorno para maximizar algún tipo de recompensa acumulativa. Quizá la algoritmo más conocido de RL es Aprendizaje Q . Creo que esta es la primera pregunta en este sitio sobre el aprendizaje por refuerzo.

Creo que lo que preguntas es cierto si intentas enfocarlo como clasificación/regresión, pero no parecen la herramienta adecuada para este problema. Este es naturalmente un problema RL donde secuencias de acciones y resultados deben tenerse en cuenta.

Answer 3

Compruebe aquí cómo lo hacen otros o participe usted mismo: Angry Birds AI Challenge http://ai2012.web.cse.unsw.edu.au/abc.html

Answer 4

Acabo de mencionar esto en meta. Koza fue pionero en el uso de algoritmos genéticos para resolver el videojuego Pacman. construyó primitivas algorítmicas que podían sentir y actuar. si no recuerdo mal, se combinaron en árboles tipo Lisp para crear algoritmos más grandes. el cruce con árboles Lisp implica sustituir o intercambiar subárboles que representan las expresiones del algoritmo. la función de éxito es algo así como "puntos comidos" o "puntos más fantasmas comidos" o "tiempo permanecido vivo". todavía se está trabajando en este campo. hay una referencia a koza en este documento a continuación. el tiempo de entrenamiento puede ser muy largo y la "convergencia" muy gradual para este tipo de problemas.

Aprender a jugar al comecocos: un enfoque evolutivo basado en reglas por Gallagher y Ryan