4) { while ($ads2 == $ads1) { $ads2 = rand(1, $slides); } } $ads3 = rand(1, $slides); if ($slides > 4) { while (($ads3 == $ads2) || ($ads3 == $ads1)) { $ads3 = rand(1, $slides); } } ?>
INF1771 - INTELIGÊNCIA ARTIFICIAL  
TRABALHO 1 BUSCA HEURÍSTICA  
Descrição:  
Durante o torneio da Guerra Galáctica, os Cavaleiros de Bronze descobrem que  
Saori é a reencarnação de Atena e que o Grande Mestre tentou matá-la ainda bebê.  
Decididos a apoiar Saori, os Cavaleiros de Bronze partem para o Santuário para  
enfrentar o Grande Mestre.  
Ao chegar ao Santuário, Saori e os Cavaleiros são recepcionados por Tremy, um  
Cavaleiro de Prata, que ataca o grupo e atinge Saori com uma flecha mortal.  
Para salvar Atena, os Cavaleiros devem percorrer um caminho composto pelas 12  
Casas do Zodíaco, cada uma protegida por um Cavaleiro de Ouro, e chegar à casa do  
Grande Mestre, o único capaz de remover a flecha do peito de Saori. Para complicar  
ainda mais, os Cavaleiros tem um prazo máximo de 12 horas para realizar essa tarefa!  
O seu objetivo é ajudar Seiya, Shiryu, Hyoga, Shun e Ikki a passar pelas 12 Casas do  
Zodíaco, derrotando todos os Cavaleiros de Ouro e salvando Atena o mais rápido  
possível!.  
Figura 1. Os Cavaleiros de Bronze.  
Figura 2. As 12 Casas do Zodíaco.  
O Trabalho 1 consiste em implementar um agente capaz de guiar autonomamente Seiya,  
Shiryu, Hyoga, Shun e Ikki pelas 12 Casas do Zodíaco, planejando a melhor forma de  
derrotar os 12 Cavaleiros de Ouro e salvar Atena. Para isso, você deve utilizar o  
algoritmo de busca heurística A*.  
O agente deve ser capaz de calcular automaticamente a melhor rota para percorrer as  
1
2 Casas do Zodíaco e derrotar os 12 Cavaleiros de Ouro no menor tempo possível.  
O mapa das 12 Casas do Zodíaco é mostrado na Figura 3.  
Figura 3. Mapa das 12 Casas do Zodíaco.  
No caminho das 12 Casas do Zodíaco existem 3 tipos de terrenos: montanhoso (região  
cinza escuro), plano (região cinza) e rochoso (região cinza claro).  
Para passar por cada tipo de terreno, os Cavaleiros gastam uma determinada quantidade  
de tempo:  
Montanhoso: +200 minutos  
Plano: +1 minuto  
Rochoso: +5 minutos  
Os Cavaleiros de Bronze iniciam a sua jornada na entrada do santuário (região em  
vermelho no mapa) e terminam ao chegar à casa do Grande Mestre (região verde no  
mapa).  
Ao chegar a uma Casa do Zodíaco, o agente deve decidir quais Cavaleiros vão lutar  
contra o Cavaleiro de Ouro que protege a casa. Cada Cavaleiro de Ouro apresenta um  
nível de dificuldade diferente. Este nível determina o tempo gasto pelos Cavaleiros de  
Bronze para pode vencê-lo e avançar para a próxima Casa.  
A Tabela 1 mostra os níveis de dificuldade das 12 Casas do Zodíaco.  
Casa  
Dificuldade  
1
2
3
4
5
6
7
8
9
1
1
1
°
°
°
°
°
°
°
°
°
Casa de Áries  
Casa de Touro  
Casa de Gêmeos  
Casa de Câncer  
Casa de Leão  
Casa de Virgem  
Casa de Libra  
Casa de Escorpião  
Casa de Sagitário  
50  
55  
60  
70  
75  
80  
85  
90  
95  
0° Casa de Capricórnio  
1° Casa de Aquário  
2° Casa de Peixes  
100  
110  
120  
Tabela 1. Níveis de dificuldade das 12 Casas do Zodíaco.  
O número de Cavaleiros de Bronze participando das batalhas contra os Cavaleiros de  
Ouro influência o tempo gasto na batalha. Além disso, cada Cavaleiro possui um  
determinado nível de poder cósmico que também influencia no tempo gasto nas  
batalhas. Quanto mais Cavaleiros lutando, mais rápido o Cavaleiro de Ouro será  
derrotado.  
A Tabela 2 mostra o poder cósmico dos Cavaleiros de Bronze.  
Cavaleiro  
Seiya  
Shiryu  
Hyoga  
Shun  
Poder Cósmico  
1.5  
1.4  
1.3  
1.2  
1.1  
Ikki  
Tabela 2. Poder cósmico dos Cavaleiros de Bronze.  
O tempo gasto nas batalhas contra os Cavaleiros de Ouro é dado por:  
ꢅꢆꢇꢆꢈꢉꢊꢋꢌꢋꢁ ꢋꢌ ꢍꢌꢎꢌ  
= ꢏꢄꢋꢁꢐ ꢍꢄꢎꢂꢆꢈꢄ ꢋꢄꢎ ꢍꢌꢑꢌꢊꢁꢆꢐꢄꢎ ꢏꢌꢐꢒꢆꢈꢆꢃꢌꢓꢋꢄ ꢋꢌ ꢔꢌꢒꢌꢊℎꢌ  
Além do poder cósmico, cada Cavaleiro de Bronze também possui 5 pontos de energia.  
Ao participar de uma batalha, o Cavaleiro perde -1 ponto de energia. Se o Cavaleiro  
perder todos os pontos de energia, ele morre.  
Informações Adicionais:  
O mapa principal deve ser representado por uma matriz 42 x 42 (igual à  
mostrada na Figura 3).  
O agente sempre inicia a jornada na entrada do santuário (região em vermelho  
no mapa).  
O agente sempre termina a sua jornada ao chegar à casa do Grande Mestre  
(
região verde no mapa).  
O agente não pode andar na diagonal, somente na vertical e na horizontal.  
O agente obrigatoriamente deve utilizar um algoritmo de busca para encontrar  
o melhor caminho e planejar as batalhas.  
Deve existir uma maneira de visualizar os movimentos do agente, mesmo que a  
interface seja bem simples. Podendo até mesmo ser uma matriz desenhada e  
atualizada no console.  
Os mapas devem ser configuráveis, ou seja, deve ser possível modificar o tipo  
de terreno em cada local. O mapa pode ser lido de um arquivo de texto ou deve  
ser facilmente editável no código.  
A dificuldade das casas e o poder cósmico dos Cavaleiros de Bronze devem  
ser configuráveis e facilmente editáveis.  
O programa deve exibir o custo do caminho percorrido pelo agente enquanto  
ele se movimenta pelo mapa e também o custo final ao terminar a execução.  
O programa pode ser implementado em qualquer linguagem.  
O trabalho pode ser feito individualmente ou em grupos de no máximo 3  
pessoas.  
O programa deve ser apresentado durante a aula por todos os membros do  
grupo:  
1
2
) O membro do grupo que não comparecer receberá nota zero;  
) O membro do grupo que não souber explicar algo relacionado ao  
trabalho perderá 5.0 pontos.  
Dicas:  
Neste trabalho existem dois problemas distintos:  
1
2
) Encontrar o melhor caminho para passar pelas 12 Casa do Zodíaco e  
chegar até a Casa do Grande Mestre;  
) Encontrar a melhor ordem de equipes para lutar contra os Cavaleiros de  
Bronze.  
Os dois problemas podem ser resolvidos individualmente ou tratando ambos em  
um único problema. Você deve definir a melhor maneira de estruturar a sua  
solução.  
Forma de Avaliação:  
Será avaliado se:  
(
(
(
(
1) O trabalho atendeu a todos os requisitos especificados anteriormente;  
2) Os algoritmos foram implementados e aplicados de forma correta;  
3) O código foi devidamente organizado;  
4) O trabalho foi apresentado corretamente em sala de aula;  
Bônus:  
(
1) A interface gráfica não é o objetivo desse trabalho, mas quem implementar uma  
boainterface gráfica (2D ou 3D) para representar o ambiente e o agente  
receberá até 2 pontos extras na nota.  
(
2) O trabalho que conseguir encontrar a solução ótima no menor tempo de  
execução do algoritmo de busca, receberá 1.0 ponto extra na nota. Para poder  
participar da competição, o trabalho deverá implementar um mecanismo para  
calcular o tempo de execução do algoritmo e deverá ser executado em Windows  
(
se bibliotecas auxiliares forem usadas, todos os arquivos necessários deverão  
ser incluídos no projeto para que ele possa ser executado).  
Data de Entrega:  
7/04  
2
Forma de Entrega:  
O programa deve ser apresentado na aula do dia 27/04 (segunda) e enviando até o  
mesmo dia para o email edirlei.slima@gmail.com.  
Trabalhos entregues atrasados perderam 1.0 ponto para cada dia de atraso.