Game AI

Palestra sobre inteligência artificial em jogos

1. Game AI
Inteligência Artificial para Jogos
Eletrônicos
J. Gabriel Lima
[email protected]
http://jgabriellima.wordpress.com
Laboratório de Planejamento de Redes de Alto Desempenho - LPRAD
Empresa Júnior de Engenharia de Computação /UFPa

2. Histórico
Técnicas de Inteligência Artificial para Jogos
Motores de IA e plataformas de Desenvolvimento
Por onde começar?


Agenda

3. Um Breve Histórico

4. •Máquina de jogar xadrez supostamente
provida de inteligência artificial

•Construída por Wolfgang para
impressionar a imperatriz Maria Tereza
da Áustria

•A “máquina” venceu a maioria dos jogos
e fez demonstrações pela Europa e
América durante mais de 84 anos

•Ganhou disputas contra os famosos:
Napoleão Bonaparte e Benjamin
Franklin

•Era na verdade uma ilusão mecânica que
permitia que um jogador de xadrez
escondido, controlasse a máquina.

•Algumas imitações foram propostas ao
longo dos anos:
•O Egípcio (Ajeeb) – 1868 – Charles Hooper
•Mephisto – 1878 – Charles Gumpel
•El Ajedrecista - 1912


“O Turco” (1770)

5. •A indústria percebeu que a inclusão
de um modo para um jogador
poderia atrair um público maior,
desta forma, aumentando os lucros

•Técnicas já conhecidas no meio
acadêmico passaram a ser utilizadas
para simular o comportamento
humano

6. •Lançado em 1978

•Construído pela Taito Corporation

•foi um dos primeiros jogos de tiro
com gráfico bidimensional

•Implantou as primeiras entidades
inteligentes em jogos

•foi um sucesso e gerou centenas
de milhões de dólares, não só
para os desenvolvedores mas
também para outras empresas
que imitaram a fórmula de
sucesso do jogo.


Space Invaders

7. •Criado em 1980 pora a empresa Namco

•Tornou-se um dos jogos mais
populares no momento

•O jogador era uma cabeça redonda
com uma boca que se abre e fecha,
posicionado em um labirinto simples
repleto de pastilhas e 4 fantasmas
que o perseguiam. O objetivo era
comer todas as pastilhas sem ser
alcançado pelos fantasmas, em ritmo
progressivo de dificuldade.

•Pac-man conta com movimentos
padronizados dos inimigos

•Porém cada fantasma tem um modo
diferente de caçar o jogador
Pac-Man

8. •Desenvolvido em 1990

•O primeiro jogo de estratégia em
tempo real, Herzog ZWei, é lançado.

•A busca de caminho apresentada
nesse jogo era de baixa qualidade

•Enquanto o jogador controlava um
veículo que podia se transformar em
avião de transporte ou robô de guerra,
ele precisava controlar o maior
número de zonas estratégicas, que por
sua vez aumentavam o fluxo de
recursos para seu caixa.

•O game oferece nativamente suporte
para dois jogadores.

•Faltava muita refinação, mas a
presença desses mesmos elementos
continua intacta em dezenas de jogos
do gênero até hoje.
Herzog ZWei

9. • Foi desenvolvido utilizando-se redes
neurais.
O estilo do jogo é "você e sua nave contra o
universo".
• Cada personagem do jogo, exeto o
controlado pelo jogador, é dirigido por
uma rede neural,

•Os oponentes também usam redes
neurais para combater, negociar, etc.

• Este jogo causou muita controvérsia pois
seus desenvolvedores afirmam ter
utilizado técnicas de IA, como redes
neurais, no seu desenvolvimento mas
muitos discordam desse fato.

•O jogo usa uma rede neural para todas
as decisões orientadas ao seu objetivo,
e em alguns casos usa também lógica
fuzzy.
BattleCruiser: 3000AD

10. •Desenvolvido em 1998 pela Valve
Software

•Foi um dos jogos mais revolucionários
da história do estilo em primeira
pessoa

•Comparado com o clássico e pioneiro
DOOM

•É lançado como a melhor Game IA
até então.


Half-Life

11. Resumo Histórico

13. IA e Game IA

14. Para as empresas desenvolvedoras de jogos eletrônicos, as
aplicações computacionais de IA e o significado do termo IA são
diferente dos encontrados no meio acadêmico.

Para distinguir a inteligência artificial utilizada em jogos e no
meio acadêmico, os desenvolvedores adotaram o termo Game AI

A principal diferença entre a IA acadêmica e a IA para jogos é o
objetivo que cada uma busca.

15. IA Acadêmica
Dentre outras coisas, um dos objetivos, é buscar a solução para problemas
complexos, como imitar o reconhecimento que os humanos são capazes de
realizar (reconhecimento facial e de imagens e objetos, por exemplo),
entender e construir agentes inteligentes, por exemplo.


O objetivo de usar inteligência artificial é a diversão. Sua importância é quanto
aos resultados que o sistema irá gerar, e não como o sistema chega até os
resultados.

Isso se deve pelo fato que jogos eletrônicos são negócios.

Os consumidores desses produtos os compram em busca de diversão, e não
lhes interessa como a inteligência de um personagem no jogo foi criada.
Game IA

16. Alguns pesquisadores afirmam que a indústria de jogos está muito anos à
frente do meio acadêmico com relação à construção de soluções práticas
de IA para certos problemas.

Outros afirmam que estudos formais de IA podem levar anos para
formular teorias de comportamento, examinar possíveis soluções e
desenvolver protótipos para testes.

Apesar disso, a falta de uma metodologia científica faz com que muitas
das soluções encontradas pelos desenvolvedores de jogos não sejam
aceitas como um apoio aos estudos formais de IA.

17. IA em Jogos

18. Há diversas razões para que os pesquisadores de IA migrem para a área de
desenvolvimento de jogos:

As empresas desenvolvedoras de jogos já perceberam a necessidade de construir cada vez
mais personagens inteligentes.
A área de jogos eletrônicos é altamente competitiva e a tecnologia que será o grande
diferencial a partir de agora é o desenvolvimento de IA.
A cargo de programador de IA, já está comum na área de desenvolvimento de jogos
O mercado de jogos fatura mais que a do cinema.
Com a evolução dos hardwares de processamento gráfico e a sua otimização sobra mais
processamento para os algoritmos de IA.

19. Alguns dos tipos de Inteligência Artificial voltada para área dos
jogos, em ordem crescente de complexidade, são:

Algoritmos determinísticos e Padrões de Movimento
Máquina de Estado Finita
Sistemas Baseados em Regras
Algoritmos de Busca
Redes Neurais
Algoritmos Genéticos

20. Utilizados nos primeiros jogos eletrônicos da historia
Compostos por:
Movimentos aleatórios
Algoritmos de perseguição
Algoritmo de Evasão

O algoritmo de perseguição verifica a posição de um personagem 1 em
relação a posição de um personagem 2, e avança em direção a ele.

O algoritmo de evasão faz o personagem 1 se distancie do personagem
2.

Exemplo: Gun Fight (1975)
Padrões de Movimento

21. Define os estados em que um personagem pode se encontrar e quando o
mesmo muda de estado.

Recurso de fácil entendimento, implementação e depuração

Exemplo: no pac-man, uma máquina de estados é utilizada para cada
fantasma, sendo os estados possíveis:
Procurando o jogador
Perseguindo o jogador
Fugindo do jogador


Máquina de Estado Finito

22. Quando o fantasma procura o jogador, ele apenas se movimenta pelo
labirinto ate encontrar o jogador

Quando ele encontra o jogador ele verifica se pode perseguir o jogador ou se
precisa fugir e troca de estado para “perseguindo jogador” e tenta alcançar o
jogador

Se durante esse tempo o jogador ganha a habilidade de engolir o fantasma, o
fantasma muda seu estado para “fugindo do jogador”
Máquina de Estado Finito

23. Maquinas de estado são uteis para situações locais
Onde dado um estado, apenas algumas condições podem ser
aplicadas como saída.
Máquina de Estado Finito

24. Quando o fantasma procura o jogador, ele apenas se movimenta pelo
labirinto ate encontrar o jogador

Quando ele encontra o jogador ele verifica se pode perseguir o jogador ou se
precisa fugir e troca de estado para “perseguindo jogador” e tenta alcançar o
jogador

Se durante esse tempo o jogador ganha a habilidade de engolir o fantasma, o
fantasma muda seu estado para “fugindo do jogador”
Máquina de Estado Finito

25. Representação de comportamento muito utilizada em jogos

Mais flexível que a abordagem puramente estimulo-resposta.

SBRs apresentam algumas vantagens como as pessoas normalmente pensam sobre
conhecimento

São bastante expressivos e permitem a modelagem de comportamentos complexos

Modelam o conhecimento de uma maneira modular

São fáceis de escrever e são mais concisos que maquinas de estados finitos

Sistemas Baseados em
Regras

26. Como funciona?
O conhecimento é definido através de um conjunto de parâmetros (variáveis) e um
conjunto de regras que trabalham sobre esses parâmetros, de modo que durante a
“Tomada de Decisão” essas regras são então processadas

Exemplo: Supondo que o conjunto de parâmetros seja definido como:
Distancia do Inimigo
Energia do Agente
Energia do Inimigo
Quantidade de Munição
Sistemas Baseados em
Regras

27. E uma vez definidos os parâmetros de entrada, seja também concebido o conjunto de ações
possíveis do agente:
 fugir
procurar
Atirar
SE (distancia do inimigo > 100) E (energia do agente > 50) E ( energia do inimigo < 50)
ENTAO procurar.
E se a seguinte condição fosse assim:
- Se há um osso por perto e o cachorro esta com fome, ele irá comê-lo;
- Se o cachorro está com fome, mas não há nenhum osso por perto, ele procura por um;
- Se o cachorro não está com fome, mas está com sono, ele irá dormir;
- Se o cachorro não está com fome e não esta com sono, o cachorro irá andar e latir.

Sistemas Baseados em
Regras

28. Essas quatro sentenças são difíceis de serem representadas através de uma
maquina de estados
Cada sentença leva a um estado da maquina e cada estado pode transitar para
qualquer um dos outros estados.

Nesse exemplo, o cachorro se comporta de acordo com um conjunto de
prioridades ou regras. Um sistema baseado em regras tem a forma:
“Condição _ Ação”
Fome & osso por perto _ comer;
Fome & não osso por perto _ procurar;
Não fome & com sono _ dormir;
Não fome & sem sono _ andar e latir
Sistemas Baseados em
Regras

29. A busca é um dos problemas mais básicos de IA para jogos
Algumas das principais consequências de uma busca “pobre” são:
Personagens que parecem totalmente artificiais
Personagens sem inteligência de navegar entre locais e desviar de obstáculos

Para solucionar o problema de busca (sair de uma ponto e chegar a um destino),
diversos algoritmos podem ser utilizados

Algoritmo A* (Lê-se A estrela) o mais famoso e implementado em jogos

Outros:
Algoritmo de Dijkstra e waypoints também são utilizados
Algoritmos de Busca

30. O A* é um algoritmo onde utiliza uma função heurística que determina a
qualidade de cada um dos estados possíveis, por meio de um custo para a
melhor rota até o destino passando pelo nó atual.

Esse custo determina a qualidade do caminho, quanto menor o custo melhor
é o caminho.

Essa técnica é amplamente utilizada para jogos de estratégia, onde os
agentes devem procurar a melhor rota para se deslocar no cenário essa busca
é conhecida como pathfinding.
Algoritmos de Busca

31. Pode-se utilizar a analise do terreno para aumentar ou diminuir o custo do
caminho, onde pontos do mapa são identificados como pontes, travessias ou
rios.

A busca A* é a forma de busca pela melhor escolha mais conhecida.

Ela avalia nós combinando g(n), o custo para alcançar cada nó, e h(n), o custo
para ir do nó até o objetivo:
f(n) = g(n) + h(n)
Algoritmos de Busca

32. Desse modo, se tenta encontrar a solução de custo mais baixo, a opção razoável seria
experimentar o menor valor de g(n) + h(n).

Desde que a função heurística h(n) satisfaça certas condições, a busca A* será ao
mesmo tempo completa e ótima.

O algoritmo de A* é utilizado em jogos para realmente encontrar o melhor caminho a
ser tomado, sendo mais utilizado em jogos de estratégia como Age of Empires ou
WarCraft, onde deve-se mover unidades de exército ou unidades normais
Algoritmos de Busca

33. Exemplo:





Algoritmos de Busca

37. Método de solucionar problemas de inteligência artificial, construindo um
sistema que tenha circuitos que simulem o cérebro humano

 Comportamento
Aprendizagem,
Erros
Descobertas

São técnicas computacionais que apresentam um modelo inspirado na estrutura
neural de organismos inteligentes e que adquirem conhecimento através da
experiência
Redes Neurais

38. As principais vantagens das redes neurais são:

Tolerância a falhas
Podem ser treinadas para reconhecerem padrões distorcidos e até
mesmo incompletos

Compatibilidade com a tecnologia
Funciona em hardware de baixo custo

Auto-organização
Capacidade de aprendizagem adaptativa

Redes Neurais

39. Redes neurais são formadas por vários neurônios artificiais

O número de neurônios do qual a rede é formada depende da tarefa que ela
irá desempenhar, podendo variar de poucos neurônios (3 ou 4) a milhares
deles.


Redes Neurais

40. Em aplicações da vida real, as RNs são utilizadas no reconhecimento de padrões,
categorização, aprendizado, competição, auto-organização, entre outras áreas

Toda rede neural recebe como entrada um conjunto de números reais.

O problema ocorre quando precisamos utilizar outros tipos de valores de entrada,
como enumerações e valores lógicos verdadeiro/falso –o que é comum na
implementação de jogos.



Redes Neurais

41. Em jogos é utilizada onde os personagens necessitam de aprendizado
através das escolhas do jogador

São usadas em conjunto com outras técnicas, executando tarefas que
necessitam um certo grau de aprendizado ou para realizar tarefas em
que as unidades controladas pelo computador sejam menos previsíveis.
Exemplo:
Simuladores de vôo
Onde as decisões do jogador podem ser mapeadas a fim de obter padrão de
comportamento

Redes Neurais

42. Baseada nos estudos sobre a evolução das espécies, de Charles Darwin,
moldando a população de indivíduos através da sobrevivência dos membros
mais aptos a viver naquele ambiente

Os seres mais “fortes” e capazes de sobreviver passam adiante suas
características para a próxima geração

A geração resultante é fruto da combinação de dois cromossomos da
geração atual, num processo denominado crossover

Algoritmos Genéticos

43. Nessa combinação podem ocorrer mutações aleatórias, e, se estas mutações
contribuírem para a sobrevivência da espécie, elas serão também passadas
para as gerações futuras

No desenvolvimento de jogos, os algoritmos genéticos visam a busca de uma
solução ótima para um determinado problema

Geralmente, os algoritmos genéticos são utilizados quando se deseja uma IA
que atue mesmo em situações não previstas pelo desenvolvedor, como em
tomadas de decisão de acordo com o comportamento do jogador
Algoritmos Genéticos

44. São ótimos para resolver problemas de otimização combinatória, onde o
espaço de busca é grande e complexo

Para problemas como o do pathfinding, (nos quais já existem algoritmos
sólidos para sua resolução) não é recomendado o uso dos algoritmos
genéticos, pois estes são mais custosos computacionalmente


Algoritmos Genéticos

45. A implementação dos algoritmos genéticos em jogos pode ser dividida em quatro etapas:

1- Inicialização: primeiramente, é preciso definir um modo de codificar os
cromossomos da população de criaturas de IA que iremos criar.

Exemplo:
Suponha que a população de criaturas controladas pelo computador tenham que responder de
acordo com a arma em uso pelo jogador(espada, arco, lança e machado), e as respostas
possíveis são: usarEscudo (1), ataqueComEspada (2), fugir (3), esconder (4) e ataqueComArco
(5). Então os cromossomos destas criaturas serão representados por um vetor de quatro
posições, onde a posição 1 contém o identificador da ação a ser executada caso o jogador tenha
uma espada, a posição 2 será executada caso o jogador tenha um arco, e assim por diante. Cada
posição do vetor assume um valor de 1 a 5.

Algoritmos Genéticos

46. 2- Validação da aptidão

Nesta etapa do processo evolucionário, deve se avaliar quais indivíduos da
população são os mais aptos a resolver o problema em questão.

Utilizamos uma função de avaliação de aptidão

Para o exemplo acima, uma boa função avaliação é contabilizar a diferença entre o
dano que a criatura causou ao jogador e o dano recebido.

Algoritmos Genéticos

47. 3- Seleção

Nesta etapa é utilizada a função calculada na etapa anterior para que sejam
escolhidos os indivíduos que participarão do processo evolucionário.

Na vida real, geralmente dois pais contribuem com seus cromossomos para a
geração seguinte.

No mundo dos jogos, podemos escolher qualquer número dentre os melhores
indivíduos
Algoritmos Genéticos

48. 4- Evolução

Nesta última etapa, serão criados os novos indivíduos que serão
introduzidos no ambiente do jogo.

São selecionados os melhores indivíduos e combinados seus genes no
processo de crossover.

São introduzidas mutações aleatórias
Algoritmos Genéticos

50. Futuramente, espera-se que a IA aprenda cada vez mais com o jogador,
utilizando redes neurais artificiais e até mesmo os algoritmos genéticos, que
até o momento têm sido pouco utilizados, salvo em implementações
específicas.

51. Motores de IA

52. A evolução dos motores e frameworks para o desenvolvimento de jogos
eletrônicos seguiu a idéia de dividir e conquistar, após a divisão das áreas de
engine o desenvolvedor só precisaria juntar todas as engines para construir o
jogo.

Essas engines abordam diversas áreas, porém a área de IA ainda não teve um
aprofundamento e consta de forma tímida em grande maioria das engines
para jogos, deixando o trabalho para o desenvolvedor criar a IA

Alguns motores de jogos se destacam na ênfase que dão para a área da IA,
porém ainda que timidamente:

53. Unreal Engine 3

Framework desenvolvido pela Epic Games
Especialmente feito para os novos consoles: Playstation 3, Xbox 360 e Nitendo Wii, além dos PC’s.
O sistema de IA aborda:
Suporte ao pathfiding
Comporta objetos complexos como portas e elevadores
Permite navegação entre cenários
Personagens interagem com objeto
Navegação de Alto Nível
Suporta táticas de combate
IA baseada em times
Adequada para jogos de tiro em primeira pessoa e estratégia

54. A Unreal Engine é um framework proprietário tendo três tipos de licença:
· Royalty-Bearing;
· Royalty-Free;
· Custom.

Royalty-Bearing: possui o valor de U$$ 350.000,00 mais U$$ 50.000,00 por plataforma de
desenvolvimento, além de pagar uma taxa de 3% em cima do faturamento do jogo.
 Royalty-Free: possui o valor de US$750.000,00 mais US$100.000,00 por plataforma, não
cobrando nenhuma taxa por jogo vendido.
Custom: essa última licença a empresa interessada deverá entrar em contato com a Epic Games
para a aquisição do produto. Sendo destinada para projetos não comerciais voltados mais para
aprendizado.

55. Source Engine

Framework, Desenvolvido pela Valve Software para produção de jogos envolvendo animação de
personagens, física, baseada em shaders e uma avançada IA.

Foi usado para o desenvolvimento de jogos famosos como Half-Life, Counter-Strike e Day of Defeat.

Os recursos da engine consistem em um sistema de entrada e saída dando o controle da IA para os
desenvolvedores.

Possui um sistema de navegação onde os personagens podem correr, voar, pular.

Permite tratar eventos relacionado aos sentidos humanos e ainda adicionar relacionamentos que
definem o status amigo ou inimigo

56. Reality Engine

Motor para o desenvolvimento de jogos produzido pela Artificial Studios.

Desenvolvido em cima da plataforma DirectX9 podendo rodar em DirectX7 ou 8.

Foi criada com o objetivo de competir com a Source Engine e a Unreal Engine 3, tendo
uma qualidade gráfica bem superior.

Possui um suporte a IA com técnicas importantes como, pathfinding, tomada de
decisões baseadas em máquinas de estados, além de dar aos agentes inteligentes a
possibilidade de responder a estímulos sonoros e visuais.

A arquitetura da engine foi desenvolvida para melhorar a performance da IA

57. Reality Engine

Motor para o desenvolvimento de jogos produzido pela Artificial Studios.

Desenvolvido em cima da plataforma DirectX9 podendo rodar em DirectX7 ou 8.

Foi criada com o objetivo de competir com a Source Engine e a Unreal Engine 3, tendo
uma qualidade gráfica bem superior.

Possui um suporte a IA com técnicas importantes como, pathfinding, tomada de
decisões baseadas em máquinas de estados, além de dar aos agentes inteligentes a
possibilidade de responder a estímulos sonoros e visuais.

A arquitetura da engine foi desenvolvida para melhorar a performance da IA

58. Por onde começar?

59. Obrigado!
Dúvidas?
[email protected]

60. Game AI
Inteligência Artificial para Jogos
Eletrônicos
J. Gabriel Lima
[email protected]
http://jgabriellima.wordpress.com
Laboratório de Planejamento de Redes de Alto Desempenho - LPRAD
Empresa Júnior de Engenharia de Computação /UFPa