More Braaains

Continuando o assunto sobre Inteligência Artificial, vou hoje falar um pouco sobre algo que implementei no meu antigo projeto de RPG Maker XP: a habilidade de personagens não controláveis aprenderem quais os melhores ataques contra cada  tipo de inimigo.
Num primeiro nível, para poder dar a possibilidade do personagem escolher qual o ataque mais eficaz contra certo inimigo, este tinha que ter a possibilidade de testar todos os seus possíveis ataques, e conseguir estabelecer um padrão. A primeira atitude “inteligente” do personagem é usar aleatoriamente qualquer um dos seus possíveis ataques (que geralmente eram 4), e memorizar um histórico desses ataques. Este histórico guarda, para cada inimigo diferente, o tanto de dano tirado por cada ataque num determinado número de vezes no passado.
Para a segunda parte, um tanto mais complicada, decidi usar uma rede neural. A idéia aqui era que o personagem pudesse avaliar suas decisões e estabelecer novas prioridades para seus ataques, no intuito de adaptar-se e chegar ao ponto de usar apenas os ataques realmente efetivos.
O modelo de rede neural que usei foi um Multilayer Perceptron (MLP), usando um algoritmo de Backpropagation. Não explicarei a fundo como funcionam estas técnicas porque meu entendimento sobre o assunto não chega ao nível de poder ensinar, mas o objetivo dessa utilização é poder testar as ações, verificar seus resultados, e adaptar a rede para que suas próximas ações cheguem mais próximas do seu objetivo.
A modelagem da rede foi a seguinte: Usei 4 entradas, que correspondem cada uma a um dos 4 ataques possíveis dos personagens. Os valores de entrada eram sempre a divisão de 1 pela média do dano geral já causado por cada ataque. A camada escondida possui 3 nodos, e saída possui novamente 4 nodos, correspondentes aos mesmos ataques da saída. Os valores desejados para a saída são a média do dano geral causado por cada ataque, dividido por 100 (portanto, é sempre equivalente a entrada).
Durante o jogo, a cada ataque que o personagem dá, sua rede é treinada. Quando os valores da entrada são calculados e chegam na saída, duas coisas acontecem: a primeira, é aplicar o algoritmo de backpropagation para levar o erro da saída até os pesos das entradas.  A segunda coisa, que é a mais importante, é usar o valor das saídas, desconsiderando o erro, para decidir se o ataque é efetivo ou não.
Sendo os valores da saída sempre entre 0 e 1, é possível obter-se uma porcentagem apenas multiplicando as saídas por 100. É definido que todos os ataques com pelo menos x% de efetividade podem ser usados contra o inimigo, mas ataques com maiores porcentagens tem maior probabilidade de serem usados. Com uma taxa de aprendizagem bem ajustada, os valores de porcentagem de todos os ataques permanecem dentro dos limites por tempo suficiente para que os ataques realmente efetivos sejam elevados à percentagens bem altas, devido ao ajuste dos pesos que ocorre. Neste ponto, os ataques menos efetivos começam a dimiuir sua percentagem de uso a ponto de passarem usar raramente, ou até mesmo nunca, se os valores das saídas ficarem abaixo do valor de ativação.
E então tem-se um personagem que fogo derrete gelo e água apaga o fogo!

Aqui vão alguns gráficos que mostram os avanços dos valores de pesos, entradas, saídas, erros e saídas desejadas para testes usando um ataque altamente efetivo contra certo inimigo, em 3 estágios de testes: Após ter lutado contra 3, 15 e 25 inimigos iguais, usando os mesmo ataques.

Para descobrir um pouco mais sobre os perceptrons e redes neurais em geral:
http://en.wikipedia.org/wiki/Perceptron
http://www.ai-junkie.com/ann/evolved/nnt1.html
Aceitando feedback, como sempre!

Braaains

  [estive mais um bom tempo sem postar hein? >.<]

  O assunto que venho abordar dessa vez é um tanto abrangente, então possivelmente irei continuar em outros posts futuros. O assunto em questão provém de idéias que tive para a criação de um jogo singleplayer que focasse grande parte da jogabilidade na interação com os NPCs. Para isso, comecei a desenvolver a idéia da criação de um “cérebro”, que estaria presente em todos os personagens do jogo, e que guardariam as mais diversas informações sobre as ações do jogador, e os rumos que o jogo estaria tomando em função destas.
   O projeto inicial desse cérebro estava baseado em uma entidade que possuiria algumas categorias de conhecimentos e estados, e cada uma dessas categorias estaria responsável por uma parte do processamento das informações que seria trocadas com o ambiente, com o jogador e com os outros NPCs. Essas categorias deveriam ser auto-adaptáveis, ou seja, deveriam estar prontas a aprender novos comportamentos em caso de serem submetidas à novas experiências, e também mudar este comportamento quando as respostas deixassem de ser as desejadas. Exemplificando, imagine que uma dessas categorias do cérebro seja o controle das emoções do personagem. Essa categoria deveria estar pronta para aprender a rir, caso algo engraçado acontecesse, mas também deveria estar disposta a parar de rir, caso o contexto passasse a não aceitar mais as risadas (risadas num velório??).
  As categorias base que imaginei para o desenvolvimento de um cérebro para os personagens seriam:

•  Percepção do Ambiente: capacidade de entender o cenário e se adaptar, além de aprender as funções dos objetos em cena e entender possíveis mudanças no ambiente. Exemplos:  descobrir pontos do cenário para se proteger de tiros/flechas, aprender que pedras podem ser pegadas e arremessadas, aprender que certas distâncias podem ou não ser alcançadas com um pulo, aprender que na hora da chuva deve-se voltar para casa.
• Resposta ao Jogador: capacidade de dar Feedback para as ações do jogador, ou adaptar comportamento devido a essas ações. Exemplos: contra-atacar o jogador, caso for inimigo, se afastar e fazer perguntas do tipo “por que está fazendo isso?”, caso for amigo, brigar com o jogador caso este quebre alguma coisa que era de posse do NPC.
• Aprendizagem e Adaptação: capacidade de mudar os comportamentos padrões do NPC. Enquanto os itens anteriores tratavam de respostas mais instantâneas e que podiam não durar para sempre, este tipo de adaptação prevê que mudanças no comportamento serão tidas como padrão até que haja uma nova mudança relevante. Como exemplos, leve em consideração que um caixeiro NPC viajante sempre toma um caminho para ir de um lugar ao outro.  Em certa ocasião, esse caminho passa a ficar bloqueado (uma rocha gigante talvez). Na primeira viagem do NPC após esse acontecimento, ele deve aprender que este caminho não é mais válido, e então deve passar a sempre usar um caminho alternativo.
• Emoções e FSM: dois tipos de máquinas de estados diferentes, que devem controlar os diversos estados do NPC, como situação de combate, se está dormindo ou acordado, humor do dia e etc. O diferencial da Finite State Machine que controlaria esses estados para o controle de emoções estaria em que o controle de emoções seria uma Fuzzy State Machine que aceita diferentes emoções ao mesmo tempo, e também aceitaria diferentes respostas para as mesmas ações, como numa situação de batalha ficar muito bravo e violento, e em outra covarde (devido a um número maior de inimigos, por exemplo). Além disso, o controle de emoções deveria ter um controle de afinidades entre o NPC e certas ações ou entre os NPCs ( NPC “A” gosta de conversar com “B”, mas não com “C”, e gosta de pescar, mas somente com chuva).

  Bom, tendo aí a idéia base do que seria o cérebro dos NPCs, alguém pergunta: isso é fácil de implementar?
  A resposta é simples: não. Muitos conceitos de Inteligência Artificial estão englobados nesse projeto, portanto muita coisa poderia não funcionar, ou ser deixada de lado, num cenário real de desenvolvimento de jogos (talvez não no profissional, mas provavelmente aconteceria com desenvolvimento independente).
  Mas de qualquer forma, é uma idéia interessante de se trabalhar, então num próximo post irei falar sobre um exemplo de sistema que já desenvolvi e que pode ser considerado como uma parte desse sistema grandioso.

Até mais, aceito feedback \o/

[PS: Caso alguém não saiba o que é um NPC, significa Non-player Character, um personagem não controlável pelo jogador, podendo ser tanto um parceiro controlado pelo computador, um inimigo, um cachorro, ou o tiozinho que vende poção na lojinha.]