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.]

Questões de vida (artificial), apenas

Andei nos últimos dias estudando e desenvolvendo uma inteligência artificial para o meu jogo, até agora está em uma fase bastante inicial, mas já envolve bastante conceitos e definitivamente não é fácil de implementar. Achei que seria interessante falar de alguns dos principais tópicos sobre Inteligência Artificial para games, para dar uma introdução para quem quer ter personagens ou sistemas mais naturais e reais nos seus jogos e quem quer saber como toda essa coisa funciona.

State Machines

O uso de State Machines é uma das técnicas mais utilizadas na IA para games. As Finite State Machines seguem a lógica que um dado sistema tem um determinado número de estados, do qual ele pode estar em algum deles e mudar para outro conforme certas ocasiões.
Um exemplo de Finite State Machine é termos um inimigo que não está vendo o herói. Ele está no estado Normal. Neste estado, ele pode fazer coisas como andar de um lugar para outro ou ficar parado. Se o herói entra no campo de visão do inimigo, este muda de estado para Seguindo Herói. Neste estado, o inimigo passa a executar outras ações, como seguir o herói ou atacar se estiver bastante próximo. Se o herói se afasar o bastante, o inimigo volta para o estado Normal. Caso o herói ataque o inimigo, este pode entra num estado Machucado. Neste estado, o inimigo poderia fugir do herói, recuperar a vida e retornar ao estado Normal ou Seguindo Herói, dependendo da distância atual. Caso no estado Seguindo Herói, o inimigo ataque o herói, ele pode então entrar num estado Euforia, onde o inimigo estaria de baixa guarda por alguns segundos, dando chance para o herói contra-atacar.
Uma evolução do sistema de Finite State Machines é o Fuzzy State Machines, onde o dado sistema pode não apenas estar em um estado ou em outro, mas sim estar parcialmente em certos estados. Aplicado no exemplo anterior, poderiamos ter o inimigo com uma porcentagem variável no estado Seguindo Herói, onde quanto mais próximo o herói chega, mais rápido o inimigo o segue, e conforme se afasta, o inimigo reduz sua velocidade e vai voltando ao ponto de repouso dele.

Fuzzy Logic

O conceito da Fuzzy logic é que algo que originalmente deveria ser considerado apenas como “Verdadeiro ou Falso”, “Ligado ou Desligado”, “Longe ou Perto”, possa ter valores intermediários, como “Meio verdadeiro”, “27% ligado”, “consideravelmente perto”. A idéia disso é ter pré-determinados estados, determinar as condições para que cada um seja verdadeiro, e então fazer com que o sistema, dada a situação do momento, calcule qual dos estados é o mais relevante.

Flocking

Flocking é um sistema de comportamento. A idéia do flocking é ter uma movimentação de um grupo, este constituído de seres independentes. Com isso, pode-se criar multidões de pessoas, cardumes de peixes, grupos de pássaros, entre outros. Cada indivíduo consegue se adequar ao grupo seguindo 4 regras: evitar colisão com os vizinhos, alinhar-se em relação aos vizinhos, mover-se de acordo com o posicionamento dos vizinhos e desviar de obstáculos.
Um exemplo clássico do flocking é o grupo de pássaros. Pode-se ter, inicialmente, vários pássaros voando em diferentes velocidades e direções, mas conforme se aproximam de outros pássaros, vão se agrupando aos poucos, e logo todos os pássaros estão agrupados.

Pathfinding – A*

O algoritmo A* ( pronunciado “A Star”) é um algoritmo bastante utilizado para calcular o melhor caminho entre um ponto inicial e um ponto de chegada. Para funcionar, o algoritmo necessita que o terreno esteja divido de alguma forma, o que torna o algortimo difícil de implementar, porque existem muitas formas de divisão de terrenos, e cada uma se adapta melhor a certas exigências, e para cada divisão o algoritmo vai ser mais ou menos eficiente em certos fatores.
O que esse algortimo faz é pegar a posição inicial, e para cada divisão adjacente, verificar se o personagem pode se mover até lá ou não. Fazendo isso recursivamente, o algoritmo vai encontrar certos caminhos possíveis, e então vai escolher o que for mais rápido para chegar até o destino.

Neural Nets

As redes neurais são um dos sistemas de inteligência artificial mais complexos, mas ao mesmo tempo mais interessantes. As redes neurais funcionam através de neurônios artificiais criados com base nos neurônios reais. Esses neurônios interligam-se em camadas, criando a rede. Através de valores que são passados como entrada, e determinados pesos para cada valor, é produzida uma saída. Através desse processo de informações, é possível treinar um sistema, e fazer com que ele aprenda através das suas ações e resultados.
As possibilidades do que se pode fazer com uma rede neural são infinitas: inimigos que reconheçam padrões de luta do jogador e aprendam a “contra-lutar”, NPCs que mudem sua personalidade conforme suas interações com o jogador, equipamentos que se adaptem ao jogador e às batalhas…

Com esses conceitos apresentados, acredito que algumas pessoas já tenham começado a entender como funcionam alguns sistemas inteligentes, e até talvez já saibam quais sistemas usar e não usar para determinadas ocasiões que queiram criar em seus jogos. Não vou postar nenhum link sobre os assuntos, mas pesquisando se acha bastante coisa. Até mais!