Inteligência artificial - Aula 10

Prévia do material em texto

- -1
INTELIGÊNCIA ARTIFICIAL APLICADA A 
JOGOS DIGITAIS
TÓPICOS AVANÇADOS EM IA
- -2
Olá!
Nesta aula, você irá:
1. Conceituar e abordar tópicos avançados em IA.
2. Mostrar ao aluno que a IA é uma disciplina em constante evolução, novas técnicas, algoritmos e ferramentas
são desenvolvidas constantemente.
1 Introdução
Neste capítulo finalizaremos o curso, apresentando e conceituando outras metodologias e ferramentas de IA, tais
como a Lógica Fuzzy e os Algoritmos Genéticos. Para cada uma delas faremos um breve comentário acerca de
sua aplicação em jogos.
2 A lógica de Fuzzy
A Lógica Fuzzy, também conhecida como "Lógica difusa", é uma extensão da lógica booleana. A lógica booleana é
aquela na qual estamos acostumados quando falamos do funcionamento interno dos computadores.
Computadores trabalham com bits, cada bit pode representar um valor lógico O (falso, desligado) ou 1
(verdadeiro ou ligado). Por exemplo, se usarmos na lógica booleana o valor de um bit para representar se um
personagem entrou ou não em um ambiente poderíamos ter: O -> não entrou 1 -> entrou
Na lógica fuzzy, são admitidos valores lógicos intermediários entre o 0 e 1, assim, no nosso exemplo anterior
poderíamos ter: -> não entrou 0.5 -> talvez 1 -> entrou sou ainda urna escala de 0 a 1 em passos de 0.1: 0.0, 0.1,
0.2, 0.3 ... 0.9, 1.0 Na realidade a lógica fuzzy permite unia escala infinita de valores, de 0 a 1.
Isso permite que estados indeterminados possam ser tratados por dispositivos de controle. Desse modo, é
possível avaliar conceitos não quantificáveis. Casos práticos: avaliar a temperatura (quente, morno, médio, etc...),
o sentimento de felicidade (radiante, feliz, apático, triste...), imagine as aplicações em jogos de simulação!
Este tipo de lógica engloba de certa forma conceitos estatísticos principalmente na área de Inferência.
3 Passos da Lógica Fuzzy
Inferência
- -3
Nesta etapa definem-se as regras ou proposições:
Depois que as variáveis linguísticas são definidas para o modelo, é preciso passar por regras que definirão a ação
a ser tomada. As regras geralmente usadas são comandos condicionais básicos como Se...Então. Como exemplo,
tem-se duas variáveis representando as energias de dois personagens do jogo sendo feito uma análise definindo
as ações que um dos personagens deve realizar.
SE (minha energia está Baixa E energia do oponente está Alta)
Então
FUGIR
SE (minha energia está Alta E energia do oponente está Baixa)
Então
ATACAR
Fuzzificação
Nesta etapa definem-se as variáveis linguísticas de forma subjetiva bem como os graus de pertinência (que
podem ser baseados em funções de pertinência).
Vamos imaginar um jogo de luta entre dois oponentes e seus respectivos níveis de energia. Poderíamos definir
variáveis linguísticas para (baixa, média e alta) e utilizar uma função de pertinênciatrês níveis de energia
(qualquer) para mapear os níveis de energia (baixa, média e alta) nos valores de energia (O a 10 por exemplo).
Defuzzificação
Um sistema baseado em fuzzy irá então aplicar as proposições vistas utilizando os valores fuzzificados (entre O e
1) dos níveis baixa e alta e calculando portanto uma resposta fuzzificada (entre O e 1). Essa resposta deve ser
convertida para uma variável linguística, tal como FUGIR e ATACAR, sendo esse o processo de defuzzificação.
Resumo do exemplo: Fuzzificação: Média, Baixa e Alta convertidos para valores fuzzy (entre O e 1) Inferência:
Proposições para tomada de decisão Defuzzificação: valores fuzzy convertidos para FUGIR e ATACAR
4 Algoritmos genéticos
Algoritmos genéticos (AGs) são métodos para resolução de problemas de busca e otimização inspirados no
princípio da evolução.
Algoritmos genéticos são implementados como uma simulação de computador em que uma população de
representações abstratas de solução é selecionada em busca de soluções melhores. A evolução geralmente se
inicia a partir de um conjunto de soluções criado aleatoriamente e é realizada por meio de gerações. A cada
geração, a adaptação de cada solução na população é avaliada, alguns indivíduos são selecionados para a
- -4
próxima geração, e recombinados ou mutados para formar uma nova população. A nova população então é
utilizada como entrada para a próxima iteração do algoritmo.
Ao longo das gerações, as populações evoluíram na terra utilizando os princípios definidos por Darwin (1859),
seleção natural e sobrevivência do mais forte. Os Algoritmos Genéticos (AG) tentam imitar esse processo para
encontrar soluções para os problemas do mundo real.
Quando os AGs são bem projetados é grande a possibilidade de encontrar a solução ótima, apesar que AGs não
encontram a melhor solução eles encontram sempre uma mais próxima. Baseados em testes empíricos eles irão
retornar sempre a solução mais próxima da melhor.
Basicamente os AGs tratam os problemas de otimização como um processo iterativo da busca pela melhor
solução para o problema. Iniciando com um conjunto de seleções naturais, constituindo a população inicial. Com
essa população é gerada uma nova população, sendo que a cada repetição a população é trocada, chegando até
uma solução.
5 Cromossomos dos algoritmos genéticos
Um algoritmo genético começa com um conjunto de soluções (representadas por cromossomos) chamado
população.
Os cromossomos podem ser representados (codificação) como uma série (string) binária, cada bit da série
representando alguma característica da solução.
A Codificação de um Cromossoma:
Certamente há muitas outras formas de codificar. A codificação dependerá principalmente do problema a ser
solucionado. Por exemplo, uma pessoa pode codificar diretamente números inteiros ou reais, algumas vezes é
útil codificar algumas permutações, e assim por diante.
- -5
Soluções de uma população são utilizadas para formar uma nova população. Isto é motivado pela esperança que
a nova população será melhor do que a primeira. Soluções que são selecionadas para formar novas gerações de
soluções são selecionadas de acordo com sua adequação - quanto melhores, mais chances de reprodução terão.
Esse processo é repetido até que alguma condição é satisfeita (por exemplo: o número de populações ou o
aperfeiçoamento da melhor solução).
6 Passos de um algoritmo genético
[Início] Gere uma população aleatória de n cromossomos (soluções adequadas para o problema). 
[Adequação] Avalie a adequação f(x) de cada cromossoma x da população. 
[Nova população] Crie uma nova população repetindo os passos seguintes até que a nova população esteja
completa.
[Seleção] Selecione de acordo com sua adequação (melhor adequação, mais chances de ser selecionado) dois 
cromossomas para serem os pais.
[Cruzamento] Com a probabilidade de cruzamento cruze os pais para formar a nova geração. Se não realizar 
cruzamento, a nova geração será uma cópia exata dos pais.
[Mutação] Com a probabilidade de mutação, altere os cromossomas da nova geração nos locus (posição nos
cromossomas).
[Aceitação] Coloque a nova descendência na nova população. 
[Substitua] Utilize a nova população gerada para a próxima rodada do algoritmo.
[Teste] Se a condição final foi atingida, pare, e retome a melhor solução da população atual.
[Repita] Vá para o passo 2.
Dica
Como você viu, a estrutura de um Algoritmo Genético Básico é bastante geral. Há muitos parâmetros e ajustes que
podem ser implementados de forma diferente em variados problemas.
7 Cruzamento e mutação
Para dar uma ideia prática de como o algoritmo pode ser implementado, vamos ver como poderiam ser
realizados os operadores básicos dos algoritmos genéticos:
Cruzamento
- -6
Depois de decidirmos que codificação usaremos, podemos proceder a operação de cruzamento. O cruzamento
opera em determinados genes dos cromossomos dos pais e cria novas descendências. A maneira mais simples de
fazer isso é escolher aleatoriamente alguns pontos de cruzamento e copiar tudo o que vem antes desse ponto de
um dos pais e então copiar tudo o que vem depois desseponto do outro pai.
O Cruzamento pode ser ilustrado da seguinte maneira: ( | é o ponto de cruzamento):
Há outras maneiras de fazer cruzamento. Por exemplo, nós podemos escolher mais pontos de cruzamento. O
cruzamento pode ser um pouco complicado e depender principalmente da codificação dos cromossomas.
Cruzamentos específicos feitos para problemas específicos
podem melhorar o desempenho dos algoritmos genéticos.
Mutação
Depois que um cruzamento é realizado, acontece a mutação. A mutação tem a intenção de prevenir que todas as
soluções do problema dessa população caiam em um ponto ótimo local. A operação de mutação muda
aleatoriamente a descendência criada pelo cruzamento. No caso de uma codificação binária, podemos mudar
aleatoriamente alguns bits escolhidos de 1 para 0, ou de 0 para 1. A mutação pode então ser ilustrada como a
seguir:
A técnica da mutação (da mesma forma que a do cruzamento) depende muito da codificação dos cromossomos.
Por exemplo, quando codificamos permutações, mutações podem ser realizadas como uma troca de dois genes.
- -7
8 Algoritmos genéticos em jogos
Alguns jogos de corrida como Gran Turismo possuem cerca de 500 carros. Cada um requer uma adaptação e
evolução de suas habilidades relacionadas em desempenho e direção, então, alguns fabricantes de jogos se
utilizam dos algoritmos genéticos para automatizar a atividade de tuning, gerando assim todas as possíveis
combinações de carros, modificando os parâmetros de desempenho dos carros chegando a obtenção de
resultados ótimos. Esses resultados serão guardados para serem utilizados durante o jogo.
Em jogos de estratégia ou de simulação como SimCity utilizam-se Algoritmos Genéticos para obter a população
da cidade em que está administrando.
CONCLUSÃO
Nesta aula, você:
• Conheceu tópicos avançados em IA.
• Percebeu que a ia é uma disciplina em constante evolução, novas técnicas, algoritmos e ferramentas são 
desenvolvidas constantemente.
• Finalizou o curso de inteligência artificial para jogos.
•
•
•
	Olá!
	1 Introdução
	2 A lógica de Fuzzy
	3 Passos da Lógica Fuzzy
	4 Algoritmos genéticos
	5 Cromossomos dos algoritmos genéticos
	6 Passos de um algoritmo genético
	7 Cruzamento e mutação
	8 Algoritmos genéticos em jogos
	CONCLUSÃO