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

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

Eso me hizo preguntarme sobre los desafíos de desarrollar un sistema de aprendizaje automático que pudiera jugar a Angry Birds. Interactuar con el juego y lanzar los pájaros es trivial. Pero una pregunta que tuve es sobre los "bloques de construcción" del sistema.

Los sistemas de aprendizaje automático parecen funcionar con conceptos simples o comprensión sobre el problema. Esto a menudo se codifica como características como entradas. Por lo tanto, parece que el sistema necesita tener la capacidad de comprender algunos conceptos de alto nivel para generar una estrategia.

¿Es esto cierto? Además, ¿cuáles son los desafíos o las partes difíciles del desarrollo de dicho sistema?

EDITAR # 1:

Aquí hay algunas aclaraciones. Obtener 3 estrellas es un problema difícil porque tienes que maximizar los puntos. Esto se puede hacer de dos maneras no exclusivas: 1) Minimizando el número de aves utilizadas (obtienes 10,000 puntos por cada ave no utilizada). 2) Maximizó la destrucción de vidrio, 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.

Aquí hay una pequeña explicación sobre los "conceptos de alto nivel". Para maximizar los puntos descritos anteriormente, debes usar los poderes especiales de cada ave. Entonces, eso significa lanzar diferentes pájaros con diferentes trayectorias, dependiendo del diseño del mapa. Y, mientras juego, desarrollo una estrategia que destruye ciertas áreas con ciertas aves en cierto orden.

Parece que sin una comprensión de cómo usar cada ave para destruir un área específica, el sistema no podría aprender a obtener 3 estrellas. Entonces, ¿cómo manejas y codificas algo así? ¿Cómo se asegura de que el sistema pueda aprender estos conceptos de alto nivel?

Suponiendo que pueda obtener los ganchos correctos en el software (o trabaje con su propia maqueta), algunas cosas serían fáciles aquí, y otras no tanto. Este es un problema bastante difícil, creo. Como mencionó carlosdc, Reinforcement Learning (RL) es una posible vía, aunque no estoy seguro de que sea la correcta.

Cuando comience, debe definir cuáles son su espacio de estado , espacio de acción , dinámica de transición y función de recompensa . Los espacios de estado / acción pueden ser continuos o discretos, y la dinámica de transición podría ser dada por el problema o modelada matemáticamente. Finalmente, la función de recompensa se puede asignar a priori o se puede muestrear (con o sin ruido).

El espacio de acción es simple: es simplemente la dirección y el poder al que disparas al pájaro actual. Para el ser humano, este es un problema discreto (el mouse / pantalla táctil es un dispositivo de entrada digital); digamos (por ejemplo) que hay 32 direcciones posibles y 10 poderes posibles, lo que da 320 acciones posibles.

La función de recompensa también es bastante fácil de obtener: el objetivo es deshacerse de todos los cerdos con el menor número de aves (OK, entonces hay puntos adicionales para otras cosas, pero ignoremos eso por ahora). Lo mejor sería si supiéramos la función real que genera puntos al matar cerdos (depende del tamaño del cerdo, etc. IIRC), pero para un solo nivel esto podría modelarse perfectamente.

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

Otro enfoque es tratarlo como lo hace un humano desde el principio, es decir, prueba y error. El ser humano, al menos para empezar, dispara de forma prácticamente aleatoria (aunque con un previo bastante fuerte para enviar a las aves hacia los cerdos, pero esto puede codificarse fácilmente), hasta que se encuentre una gama de buenas acciones. Esto es más como el bandido multi-armadoajuste. Los "brazos" de los bandidos aquí son las posibles acciones. El algoritmo intenta equilibrar la exploración y la explotación, es decir, explorar el espacio de acción y explotar las buenas acciones cuando se encuentran. Para esto, no necesita saber nada sobre la dinámica subyacente, solo necesita saber sobre acciones y recompensas. Para hacerlo completamente, deberías 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 pocoSobre el espacio de estado. Por ejemplo, probablemente podría descartar acciones que alejen al ave de los cerdos, la tiren hacia el suelo o sin suficiente energía para alcanzar a ninguno de ellos. Además, solo necesita alcanzar el quinto pájaro si no ha matado a los cerdos en las rondas anteriores, por lo que una proporción de los estados de acción no es realmente posible. Esto recuerda un poco el enfoque utilizado en el algoritmo MoGo , que es un programa de computadora para jugar Go basado en los límites de Confianza Superior aplicados a los Árboles , un enfoque para resolver el problema de los bandidos con múltiples brazos.

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 el aprendizaje por refuerzo (RL). RL se trata de cómo un agente debe tomar medidas en un entorno para maximizar alguna noción de recompensa acumulativa. Quizás el algoritmo más conocido para RL es Q-learning . Creo que esta es la primera pregunta en este sitio sobre el aprendizaje por refuerzo.

Creo que lo que estás preguntando es cierto si intentas enfocar esto como clasificación / regresión, pero esas no parecen ser la herramienta adecuada para este problema. Esto es naturalmente un problema de RL donde las secuencias de acciones y resultados deben tenerse en cuenta.

Mira aquí cómo lo hacen otros o participa tú mismo: Angry Birds AI Challenge http://ai2012.web.cse.unsw.edu.au/abc.html

acabo de mencionar esto en meta. Hubo un uso pionero de algoritmos genéticos por parte de Koza para resolver el videojuego Pacman. construyó primitivas algorítmicas que podían sentir y actuar. Como recuerdo, estos se combinaron en árboles similares a Lisp para crear algoritmos más grandes. El cruce con árboles Lisp implica la sustitución o el intercambio de 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 "el tiempo se mantuvo vivo". Todavía hay algo de trabajo en esta área. Hay una referencia de koza en el siguiente documento. El tiempo de entrenamiento puede ser muy largo y la "convergencia" muy gradual para este tipo de problemas.

Aprendiendo a jugar Pac-Man: un enfoque evolutivo basado en reglas por Gallagher y Ryan