Como você projetaria um sistema de aprendizado de máquina para jogar o Angry Birds?

Depois de jogar muito Angry Birds, comecei a observar minhas próprias estratégias. Acontece que eu desenvolvi uma abordagem muito específica para obter 3 estrelas em cada nível.

Isso me fez pensar nos desafios de desenvolver um sistema de aprendizado de máquina capaz de jogar o Angry Birds. Interagir com o jogo e lançar os pássaros é trivial. Mas uma pergunta que eu tinha é sobre os "blocos de construção" do sistema.

Os sistemas de aprendizado de máquina parecem funcionar com conceitos simples ou compreensão sobre o problema. Isso geralmente é codificado como recursos como entradas. Portanto, parece que o sistema precisa ter a capacidade de entender alguns conceitos de alto nível para gerar uma estratégia.

Isso é verdade? Além disso, quais são os desafios ou partes difíceis do desenvolvimento de um sistema desse tipo?

EDIT # 1:

Aqui estão alguns esclarecimentos. Conseguir 3 estrelas é um problema difícil, porque você precisa maximizar os pontos. Isso pode ser feito de duas maneiras não exclusivas: 1) Minimizar o número de pássaros usados ​​(você recebe 10.000 pontos por cada pássaro não utilizado). 2) Maximizou a destruição de vidro, madeira e outros objetos. Cada objeto destruído dá pontos. É possível destruir mais de 10.000 pontos em objetos com um único pássaro.

Aqui está um pouco mais de explicação sobre "conceitos de alto nível". Para maximizar os pontos descritos acima, você precisa usar os poderes especiais de cada pássaro. Então, isso significa lançar diferentes pássaros com diferentes trajetórias, dependendo do layout do mapa. E, enquanto jogo, desenvolvo uma estratégia que destrói certas áreas com certos pássaros em uma certa ordem.

Parece que, sem entender como usar cada ave para destruir uma área específica, o sistema não poderia aprender a obter 3 estrelas. Então, como você gerencia e codifica algo assim? Como você garante que o sistema possa aprender esses conceitos de alto nível?

Supondo que você possa obter os ganchos certos no software (ou você trabalha com sua própria maquete), algumas coisas seriam fáceis aqui e outras menos. Este é um problema bastante difícil, eu acho. Como carlosdc mencionou, o Aprendizado por Reforço (RL) é uma via possível, embora não tenha certeza de que seja a correta.

Quando você começa, precisa definir qual é o seu espaço de estado , espaço de ação , dinâmica de transição e função de recompensa . Os espaços de estado / ação podem ser contínuos ou discretos, e a dinâmica de transição pode ser dada pelo problema ou modelada matematicamente. Finalmente, a função de recompensa pode ser dada a priori ou pode ser amostrada (com ou sem ruído).

O espaço de ação é simples: é simplesmente a direção e o poder em que você dispara no pássaro atual. Para o ser humano, esse é um problema discreto (o mouse / tela sensível ao toque é um dispositivo de entrada digital) - digamos (por exemplo) que há 32 direções possíveis e 10 poderes possíveis, dando 320 ações possíveis.

A função de recompensa também é fácil de obter: o objetivo é livrar-se de todos os porcos com o menor número de pássaros (ok, então há pontos extras para outras coisas, mas vamos ignorar isso por enquanto). O melhor seria se soubéssemos a função real que gera pontos ao matar porcos (depende do tamanho do porco, etc. IIRC) - mas, para um único nível, isso poderia ser modelado perfeitamente.

O espaço de estados e a dinâmica de transição são muito mais difíceis. Para modelar isso corretamente, teríamos que conhecer todo o layout do mapa e a física do jogo. A dinâmica de transição diz "Se eu estiver no estado x e executar a ação y , aterrarei no estado z ". Você pode ver a dificuldade disso, primeiro como a física complexa do sistema significa que isso será extremamente difícil de modelar com precisão, e segundo como existem tantos estados possíveis após a primeira rodada (320), e isso é se presumimos que não haja estocástico no mecanismo de física, que, por ter jogado, suspeito que exista. Acho que nesta fase você desistiria e voltaria para casa.

Outra abordagem é tratá-lo como um ser humano o faz desde o início - isto é, tentativa e erro. O ser humano, pelo menos no começo, dispara virtualmente aleatoriamente (embora com um forte antes de enviar os pássaros para os porcos, mas isso pode ser facilmente codificado), até que uma série de boas ações seja encontrada. Isto é mais como o bandido multi-armadoconfiguração. Os "braços" dos bandidos aqui são as ações possíveis. O algoritmo tenta equilibrar exploração e exploração - isto é, explorar o espaço de ação e explorar boas ações quando elas são encontradas. Para isso, você não precisa saber nada sobre a dinâmica subjacente - você só precisa saber sobre ações e recompensas. Para fazer isso completamente, você teria que ter um braço para cada ação possível em todas as rodadas (por exemplo, você tem 5 pássaros * 320 ação = 320 ^ 5 = aproximadamente 10 ^ 12 ações), portanto, o espaço de ação é muito grande! No entanto, você pode usar alguns truques para melhorar isso, se você souber um poucosobre o espaço do estado. Por exemplo, você provavelmente poderia descartar ações que enviam o pássaro para longe dos porcos, para o chão ou sem energia suficiente para alcançá-los. Além disso, você só precisa alcançar o quinto pássaro se não matou os porcos nas rodadas anteriores, portanto, uma proporção dos estados de ação não é realmente possível. Isso lembra um pouco a abordagem usada no algoritmo MoGo , que é um programa de computador para jogar Go com base nos limites de Confiança Superior aplicados a Trees , uma abordagem para resolver o problema de bandidos com várias armas.

Pergunta legal!

Parece que esta pergunta é sobre a técnica natural para esse tipo de problema. Eu acho que a técnica natural para esse tipo de problema é a aprendizagem por reforço (RL). RL é sobre como um agente deve executar ações em um ambiente para maximizar alguma noção de recompensa cumulativa. Talvez o algoritmo mais conhecido para RL seja o Q-learning . Eu acho que essa é a primeira pergunta neste site sobre aprendizado por reforço.

Eu acho que o que você está perguntando é verdade se você tentar abordar isso como classificação / regressão, mas essas não parecem ser a ferramenta certa para esse problema. Naturalmente, esse é um problema de RL em que seqüências de ações e resultados precisam ser levados em consideração.

Veja aqui como os outros estão participando ou participe: Angry Birds AI Challenge http://ai2012.web.cse.unsw.edu.au/abc.html

acabei de mencionar isso em meta. houve um uso pioneiro de algoritmos genéticos por Koza para resolver o videogame Pacman. ele construiu primitivas algorítmicas que podiam sentir e agir. pelo que me lembro, eles foram combinados em árvores semelhantes a Lisp para criar algoritmos maiores. o cruzamento com árvores Lisp envolve a substituição ou troca de subárvores que representam as expressões do algoritmo. a função de sucesso é algo como "pontos comidos" ou "pontos mais fantasmas comidos" ou "tempo que permaneceu vivo". ainda há algum trabalho nessa área. há uma referência koza neste artigo a seguir. o tempo de treinamento pode ser muito longo e a "convergência" muito gradual para esses tipos de problemas.

Aprendendo a jogar Pac-Man: uma abordagem evolutiva baseada em regras de Gallagher e Ryan