Inteligência Artificial para Jogos Eletrônicos – draft 1 (12/3/2005)



Baixar 64.45 Kb.
Encontro05.02.2019
Tamanho64.45 Kb.




Inteligência Artificial para Jogos Eletrônicos –

draft 1 (12/3/2005) (não corrigido)

Bruno Campagnolo de Paula
Programa de Pós-Graduação em Informática Aplicada

Pontifícia Universidade Católica do Paraná


Curitiba, Março de 2006.

O objetivo deste artigo é desenvolver uma contextualização inicial para a área de Inteligência Artificial para jogos. Comenta-se, inicialmente, sobre Inteligência Artificial para jogos clássicos. Por fim, alguns marcos da Inteligência Artificial para Games são tratados fazendo referência aos jogos que se destacaram nesta área.



    1. Aplicação de Inteligência Artificial em Jogos Clássicos

Desde meados da década de 50, jogos têm sido utilizados para examinar e testar conceitos em diversas áreas da Ciência da Computação, principalmente na subárea da Inteligência Artificial. As primeiras pesquisas foram baseadas em jogos clássicos como Damas e Xadrez que se caracterizam pela simplicidade das regras e objetivos e pela capacidade de permitir que um programa acesse o estado do mundo do jogo de maneira completa.

Com tal percepção completa de cada movimento possível e de sua conseqüência direta, a criação de um programa que joga Xadrez pode ser simplificada com a utilização de um algoritmo de busca que escolhe o melhor movimento a ser feito a partir das finitas possibilidades de movimento em cada rodada. Destaca-se, que no caso do Xadrez, a árvore de busca gerada é muito grande. Considerando-se que cada turno possui em média 35 jogadas possíveis e os jogos perduram por 50 turnos para cada jogador, a árvore de busca gerada terá 35100 nós [RUS95]. Eliminando as posições impossíveis sobram 1040 diferentes posições possíveis em um jogo de Xadrez.

Justifica-se, portanto, que a pesquisa na área de IA para jogos manteve-se em constante evolução já que, para grande parte dos jogos clássicos, é extremamente caro computacionalmente construir um jogador automático limitando-se a utilizar uma técnica de busca. Deve-se destacar que Xadrez e Damas foram os jogos escolhidos como campo de teste da IA devido à propriedade de serem bem definidos, ou seja, com todas as variáveis de estado a cada turno sendo observáveis. Nos jogos citados, além de todas as jogadas serem conhecidas por todos os jogadores envolvidos, não há o fator sorte envolvido. Tais jogos podem ser classificados como jogos determinísticos de informação perfeita.

Outros jogos, porém, como Gamão e Banco Imobiliário inserem o fator sorte através do uso de dados. Dessa forma, o número de nós da árvore de busca cresce em relação ao número de possibilidades que o dado insere. Jogos deste tipo não deixam de ser classificados como jogos de informação perfeita. Entretanto, são classificados como jogos não-determinísticos.

Por outro lado, existe uma classe de jogos nos quais os jogadores possuem informações parciais referentes ao estado do jogo, ou seja, são jogos de informação imperfeita. Exemplos de jogos de informação imperfeita são: poker, bridge, pif e batalha naval. Dentre os jogos citados apenas o jogo de batalha naval não é influenciado pela sorte. Reafirma-se, assim, a dificuldade para aplicar uma abordagem de busca por força bruta em todos os tipos de jogos. Em um jogo de bridge, por exemplo, se cada carta possível for considerada um nó da árvore de busca será gerado 5,6x1044 nós no pior caso e 2.3x1024 nós no caso médio [SMI1998].

Além da busca heurística, outras técnicas também foram utilizadas. Em 1959, Samuel aplicou conceitos de aprendizagem de máquina para a geração de um jogador automático de damas [SAM59]. Os resultados obtidos, inclusive, constituíram as bases para a Aprendizagem de Máquina como ciência, sendo que a maioria das idéias desenvolvidas por Samuel para a aprendizagem continua em uso e com grande aplicação na área de game playing [FÜR1996].

Outras técnicas de IA também foram utilizadas com sucesso desde a década de 50. Redes Neurais e agentes destacam-se, entre as técnicas mais usuais. Em menor escala, para Algoritmos Genéticos e Case-Based Reasoning também existem aplicações em jogos. Na década de 90, segundo Schaffer [SCH2001], destacam-se o sucesso de técnicas novas como Simulação Montecarlo e Aprendizagem por Diferença Temporal.

Os principais marcos para a Inteligência Artificial para jogos clássicos são as vitórias dos jogadores automáticos. Em 1994, Chinook torna-se o primeiro programa de computador a vencer um campeão mundial em um jogo. Mais especificamente, o programa vence o campeão mundial Marion Tinsley que teve de se retirar devido a problemas de saúde após seis empates. No domínio do Xadrez, tem importância a vitória do programa Deep Blue em uma série de jogos de exibição contra o campeão mundial Kasparov. Em outro marco, no ano de 1997, o programa Logistello vence todos os jogos contra o campeão mundial de Othello, determinando a superioridade da máquina no jogo.

Independente da técnica utilizada percebe-se que a evolução dos jogadores automáticos foi bastante considerável nos últimos anos. Alguns jogos, inclusive, já não representam desafio algum para o computador, como, por exemplo, Othello. Tais jogos são considerados resolvidos, ou seja, todas as suas possibilidades são discerníveis algoritmicamente e não existe possibilidade do computador ser derrotado. A tabela abaixo sumariza os jogos clássicos que já foram completamente resolvidos e os jogos que ainda não são páreo para o raciocínio humano em qual estado o jogador automático está.


Jogo

Tipo do Jogo

Estado atual do jogador automático

Connect Four (Lig 4)

Determinístico

Informação Perfeita



Resolvido

Go-Moku

Determinístico

Informação Perfeita



Resolvido

Qubic

Determinístico

Informação Perfeita



Resolvido

Nine man’s Morris (Trilha ou Moinho)

Determinístico

Informação Perfeita



Resolvido

Othello

Determinístico

Informação Perfeita



Joga melhor que os seres humanos.

Damas

Determinístico

Informação Perfeita



Joga melhor que qualquer ser humano vivo.

Gamão

Jogo com Sorte

Informação Perfeita



Joga melhor que todos os seres humanos exceto cerca de 10.

Xadrez

Determinístico

Informação Perfeita



Joga melhor que qualquer ser humano exceto cerca de 250.

Go

Determinístico

Informação Perfeita



Joga pior que o melhor campeão de nove anos de idade.

Bridge

Determinístico

Informação Imperfeita



Joga pior que jogadores humanos medianos.

Tabela 1 - Desempenho de programas de computador em alguns jogos clássicos. Tabela baseada em [SMI1998].

Observando a tabela, deduz-se que jogos de informação imperfeita ou com um número proibitivo de possibilidades como Go ainda constituem um desafio relevante para a pesquisa no campo da IA para jogos clássicos. Quanto a Go, cabe um comentário sobre o porquê da dificuldade. Além de o jogo ter uma árvore de busca bastante profunda, os jogadores humanos não sabem explicar o motivo de uma configuração ser boa ou ruim. A vantagem do ser humano tem tanto destaque que existe um prêmio de um milhão de dólares para o primeiro programa que vencer um campeão tailandês júnior [THE2002].

Destaca-se, portanto, a necessidade da continuidade das pesquisas na área de geração de jogadores automáticos. É importante uma sucinta contextualização desta área.


    1. Aplicação de inteligência artificial em jogos de computador

Desde o desenvolvimento dos primeiros jogos comerciais diversas técnicas foram aplicadas para simular uma inteligência aos elementos da tela. Uma das primeiras estratégias perceptíveis pelo público em geral foi a inteligência artificial dos fantasmas do jogo Pac-man. O algoritmo utilizado transmitia a sensação que os fantasmas objetivavam a captura do jogador, perseguindo-o. Este comportamento é implementado através de regras. Entretanto, após algumas partidas, era perceptível a previsibilidade de movimento dos fantasmas, pois as regras eram fixas e simples. Pode-se afirmar, portanto, que os primeiros jogos não utilizavam técnicas de Inteligência Artificial clássica, apenas tentavam transmitir uma ilusão de inteligência.

Jogos de estratégia destacam-se como os pioneiros na utilização de técnicas de IA [TOZ2002]. Técnicas de pathfinding foram características neste gênero através da aplicação de algoritmos de busca como o A*. A Inteligência Artificial para jogos de computador focou-se nesta área por anos devido ao fato que as restrições quanto à velocidade de processamento e quantidade de memória exigida para a busca sempre foram questões críticas. Como o processamento gráfico era mais importante, técnicas de IA mais caras não poderiam ser aplicadas.

Aos poucos algumas técnicas mais tradicionais foram utilizadas em gêneros específicos. Por exemplo, jogos de simulação como The Sims e Creatures utilizam conceitos de vida artificial. FPSs (first-person shooters – jogos de tiro em primeira pessoa) como Quake aplicam máquinas de estado para representar o comportamento dos personagens. Máquinas de estado do tipo Fuzzy, por sua vez, permitem mais profundidade e aleatoriedade no comportamento dos personagens sendo utilizadas, também, em The Sims.

Um destaque na aplicação bem sucedida de técnicas de IA, no caso, de Aprendizagem de Máquina, é Black & White [EVA2001]. Tal jogo foi projetado de forma a utilizar a utilizar a IA como parte integrante da jogabilidade. Dessa forma, o jogador controla um agente que possui capacidade de aprender. O jogo merece uma explanação sucinta por seu pioneirismo na aplicação prática de conceitos-chave de Aprendizagem de Máquina e Agentes. Embora em um jogo comercial, geralmente, as decisões de IA sejam, fechadas, o projetista de sua IA disponibilizou uma visão pessoal sobre a arquitetura utilizada no jogo.

Os agentes do mundo do jogo, representados por uma criatura semi-controlável pelo jogador, deveriam preencher dois requisitos: parecer pessoas, ou seja, serem psicologicamente plausíveis, maleáveis e empáticas; as criaturas também deveriam ser úteis para o jogador, auxiliando na resolução de desafios no mundo do jogo, sendo que para isso deveriam poder ser treinadas.

O primeiro requisito é preenchido através da aplicação de uma arquitetura de agentes BDI [RAO1995] (Befief-Desire-Intention – Crença-Desejo-Intenção). Crenças sobre objetos individuais são representadas simbolicamente como uma lista de pares atributo-valor, crenças sobre tipos de objetos são representadas através de árvores de decisão e os desejos são representados através de perceptrons. Para fazer com que o agente seja plausível, há uma explanação clara durante o jogo dos porquês de ter certas crenças e desejos, sendo estas absorvidas através da percepção do ambiente através de seus sentidos. Quanto à maleabilidade, o agente tem capacidade de aprender através da realimentação do jogador, através de comandos explícitos, observando as atitudes dos outros agentes e refletindo sobre a sua própria experiência. Para permitir estes tipos de aprendizagem a criatura constrói dinamicamente uma árvore de decisão para minimizar a entropia do conhecimento adquirido a partir dos atributos observáveis do mundo. Tal tarefa é feita baseando-se no trabalho de Quinlan com o sistema ID3 [QUI1986]. Para que o jogador pudesse ter empatia pelas criaturas objetivou-se assegurar que estas tivessem empatia recíproca por quem as controla. Dessa forma, a mente da criatura inclui um modelo simplificado da mente do jogador construído através das observações do que ele está fazendo. Esse modelo mental foi arquiteturado através de uma representação com estruturas de dados simbólicas. Outro ponto interessante para a geração da empatia é a associação de objetivos à criatura relacionados diretamente com seu controlador, como, por exemplo, o desejo de ajudar seu mestre e o desejo de ter atenção.

Rememora-se o segundo requisito referente aos agentes do Black & White: eles devem ser úteis para o jogador, ou seja, ajudá-lo em algumas tarefas. Embora pareça ser conflitante com o primeiro requisito, por implicar no tolhimento da autonomia do agente, a solução encontrada foi a criação de um agente completamente autônomo de início e que evolui, através do treinamento, para um agente que só faz aquilo as atividades ordenadas pelo jogador. Tal modificação no agente dá ao jogador sentimento de satisfação por ter conseguido treinar a sua criatura.

Black & White é o exemplo mais significativo, mas outros jogos também utilizaram técnicas de IA provenientes da academia. A tabela em anexo sumariza exemplos de técnicas de IA para jogos e iniciativas comerciais que as aplicaram. Assim, cada vez mais a IA está integrada ao ciclo de desenvolvimento dos jogos e, a IA para jogos e a sua integração com a IA acadêmica estão sendo levadas mais a sério pelos desenvolvedores e pela academia. Steve Rabin, editor da série AI Game Programming Wisdom [RABIN2004] dá uma ordem de grandeza do tamanho da área de IA para jogos: de 2002 ao início de 2004 cerca de 150 artigos envolvendo técnicas de IA para jogos foram escritos por membros da indústria de jogos. O autor também comenta que IAs que aprendam e se adaptem serão requeridas para a maioria dos gêneros de jogos. Deve-se destacar, porém, que ainda existem desafios a serem cumpridos quanto à aplicação de técnicas de Aprendizagem de Máquina no contexto da IA comercial.

Independente da técnica utilizada, a IA para jogos de computador tem uma diferença importante quanto ao objetivo em relação a IA para jogos clássicos. Enquanto esta se preocupa em superar o ser humano, aquela se foca não na otimização do desempenho de um NPC (non player character – personagem controlado pelo computador) mas na diversão do jogador e sua experiência geral.



Referências Bibliográficas

[EVA2001] EVANS, RICHARD. The Future of AI in Games: A personal view. Game Developer Magazine, Agosto de 2001.

[FÜR1996] FÜRNKRANZ, JOHANNES. Machine Learning in Games: a Survey. 2000, report no. OEFAI-TR-2000-31.

[QUI1986] QUINLAN, J. Induction of decision trees. Machine Learning, vol. 1 p. 81–106, 1986.

[RABIN2004] RABIN, STEVE. AI Game Programming Wisdom II. Charles River Media. Rockland. 2004.

[RAO1995] A. S. RAO; M. GEORGEFF. BDI Agents: from theory to practice. In Proceedings of the First International Conference on Multi-Agent Systems (ICMAS-95), p. 312–319. 1995.

[RUS95] RUSSELL, S.; NORVIG, P. Artificial Intelligence: A Modern Approach. Prentice Hall. 1995.

[SAM59] A. L. Samuel. Some Studies in Machine Learning using the Game of



Checkers. IBM Journal of Research and Development, 3(3), pp 210-

229, 1959

[SCH2001] SCHAEFFER, JONATHAN.A Gamut of Games. AI Magazine, 2001, p. 30-46.

[SMI1998] SMITH, STEPHEN J. J.; NAU, DANA S.; THROOP, TOM.Computer Bridge: A Big Win for AI Planning. AI Magazine, 1998, p. 93-105.

[THE2002] THE GUARDIAN. Guardian Unlimited | Online | Do not pass Go. 2002. disponível em: http://www.guardian.co.uk/online/story/0,3605,817484,00.html .

[TOZ2002] TOZOUR, PAUL. The Evolution of Game AI. AI Programming Wisdom, Charles River Media, 2002, p. 3-15.



Anexo 1 - Técnicas com grau de utilização comum nos jogos comerciais

Técnica

Principais gêneros de jogo aplicáveis

Exemplos de Jogos (e desenvolvedores) que utilizaram cada técnica

Comentário

Pathfinding com A*

RTS (Real time strategy - Jogos de estratégia em tempo real)

Praticamente todos os RTSs desde Warcraft (Blizzard).

Busca de caminhos através de busca heurística.

Command Hierarchy (hierarquia de comandos)

RTS

Série Close Combat (Atom Games)

Estratégia para lidar com a IA em diferentes níveis: do general ao soldado raso modelados através de uma hierarquia militar.

Dead Reckoning

FPS (First-person shooter);

jogos de esporte;

jogos online


Quake III (id Games)

Método que objetiva a projeção do movimento futuro de cada agente a partir de sua velocidade, posição e aceleração. Em jogos online é utilizado para combater a latência. Em jogos de esporte para prever a posição do jogador de outro time.

Emergent Behaviour (comportamento emergente)

Jogos de corrida;

Jogos de simulação de vida artificial



Downforce (Smartdog)

Comportamento que não é explicitamente programado mas emerge devido a interação de comportamentos mais simples. Flocking é o exemplo clássico de comportamento emergente.

Flocking

RTS

FPS



Half-life (Valve);

Unreal (Atari)



Técnica inserida em Emergent Behaviour e responsável pelo movimento de grupos de criaturas através da utilização de regras simples.

Formations (formações)

RTS

Empire Earth (Stainless Stell Studios)

Técnica que objetiva mimetizar as formações militares. Diferencia-se de flocking pois cada unidade é guiada a partir de um objetivo específico a partir de sua hierarquia e posição.

Influence Mapping (mapeamento de influência)

RTS;

Jogos de simulação



Age of Empires (Emsemble Studios)

Sim City (Maxis);



Mapeamento de influência é um método de visualização da distribuição do poder em um espaço a partir de uma representação bidimensional que reflete a influência de cada unidade na célula que está contida e em seus vizinhos.

Level-of-detail AI (LOD-AI)

RPG;

RTS;


Jogos de simulação

Republic – The Revolution (Elixir Studios)

Variação na freqüência de atualização das computações realizadas pela IA conforme a proximidade do jogador. Por exemplo, se o personagem não está sendo visto pelo jogador, a sua IA pode ser atualizada apenas quando o resultado for perceptível.

Manager Task Assignment (Atribuição de tarefas por um gerenciador)

Jogos de esporte

Microsoft Baseball 3D (Microsoft)

O gerenciamento de tarefas considera, para a resolução de um problema, um conjunto de tarefas e um grupo de agentes. Um gerenciador centralizado prioriza as tarefas e as distribui ao melhor candidato para resolver cada tarefa.

Obstacle Avoidance (desvio de obstáculos)

FPS;

RTS





Enquanto algoritmos de pathfinding utilizando A* encaixam em ambientes estáticos, nos jogos os ambientes, muitas vezes são dinâmicos e o personagem deve desviar de obstáculos no caminho.

Scripting

Todos os gêneros

Black & White (Lionheart);

Half-Life II (Valve);

Monkey Island 4 (LucasArts).

Técnica que corresponde à especificação dos dados ou da lógica do jogo fora do código-fonte principal do jogo. Cada jogo pode ter um nível de scripting diferente e quanto mais “scriptado” maior é o poder do designer no código do jogo, abrindo a possibilidade, até mesmo, de criação de IAs extensíveis pelo jogador. Linguagens comuns utilizadas para a geração de scripts são Lua e Python.

FSM - Finite-State machines (máquinas de estado)

Todos os gêneros

Half-Life (Valve)

Conjunto finito de estados e transições, com apenas um estado ativo de cada vez. Cada estado representa, geralmente, um comportamento. É um dos padrões de projeto mais populares na indústria de jogos.

Stack-based State Machine também conhecido como push-down automata

Todos os gêneros principalmente FPS e RTS

Thief: The Dark Project (Looking Glass Studios)

Extensão à FSM que permite o retorno a um estado pelo qual a máquina já passou. Útil para tratar interrupções momentâneas causadas por eventos externos à máquina.

Subsumption Architecture

FPS;

RTS


Jogos cujo movimento de uma unidade não pode conflitar com os objetivos de alto-nível.

Halo (Bungie)

Halo 2 (Bungie)

Nesta arquitetura há a separação do comportamento de um agente em diversas camadas concorrentes. A camada mais baixa, e com mais prioridade, cuida dos comportamentos mais elementares e as mais altas vão sendo responsáveis por comportamentos cada vez mais complexos, como, por exemplo, estratégias de ataque.

Terrain Analysis

RTS

FPS


Empire Earth(Stainless Stell Studios)

Age Of Empires (Emsemble Studios)

C&C Renegade(Westwood Studios)

Conjunto de métodos que objetivam a análise de terrenos dentro de um jogo para encontrar locais com elementos estratégicos como recursos e emboscadas.

Esta abordagem contrasta com a determinação destes elementos de forma fixa pelo editor do mapa.



Tabela 2 – Exemplo de aplicação de Inteligência Artificial em Jogos.






©aneste.org 2017
enviar mensagem

    Página principal