Segundo Trabalho de Sistemas Inteligentes: JOGOS

Entrega: 13/04/2015

23 de Março de 2015

Este trabalho vale nota e será utilizado para calcular a média junto com as notas dos testes e do primeiro trabalho. O material para consulta sobre este assunto está no capítulo 12 do livro do Nilsson (Artificial Intelligence, a new synthesis), e no capítulo 5 do livro do Russell e Norvig (3a edição, Artificial Intelligence, a modern approach), ambos disponíveis na biblioteca. Além destes dois livros, há bastante material disponível na internet sobre a aplicação dos algoritmos min-max e alfa-beta ao jogo do galo.

Implementar os algoritmos min-max e alfa-beta para o jogo do galo (interativo, ou seja, computador jogando com ser humano).

O que entregar:

1. trabalho escrito com a análise dos dois algoritmos.

   Organização do trabalho escrito:

   Introdução

   Descrição de jogos com oponentes e algoritmos para resolvê-los.

   Algoritmo Min-Max

   Descrição

   Algoritmo Alfa-Beta

   Descrição

   Jogo do Galo

   Descrição do jogo. Objetivos.

   Minimax e Alfa-beta aplicados ao Jogo do Galo

   Discussão sobre os dois algoritmos aplicados ao jogo do galo. Resultados obtidos e porções da árvore de procura que são cortadas pelo algoritmo alfa-beta. Discutir também sobre a função utilidade que utilizou assim como a estratégia para explorar a árvore de jogos (o algoritmo vai até as configurações de vitória, empate ou derrota ou limita a profundidade?)

   Mostrar curvas de desempenho (tempos de execução) dos dois algoritmos neste jogo, para cada jogada.

   Comentários Finais e Conclusões

   Comentar sobre o desempenho dos dois algoritmos para o jogo do galo em relação ao número de nós expandidos e tempo de resposta para cada jogada e para o jogo inteiro. Concluir dizendo qual foi o melhor algoritmo para este jogo.

   Bibliografia

   Não esquecer de citar no texto, nos locais adequados, a biliografia listada nesta seção.

2. o código fonte do programa, como compilar e formato da entrada para cada problema, isto é, um pequeno manual de como correr o programa (pode ser um 'help' ou 'readme'). Além disso, especificar em que ambiente foi compilado (tipos e versões do SO e da linguagem). Seu programa deve correr na minha máquina (com fedora instalado). Não assuma que eu tenho uma IDE (Integrated Development Environment) de qualquer tipo. O programa deve correr na linha de comando.

   A submissão será através do Moodle UP. Por favor, não inclua caracteres acentuados no nome do ficheiro de submissão.

O trabalho pode ser feito em grupo de no máximo dois estudantes. Todos os trabalhos deverão ser apresentados em data a combinar. Todos os componentes do grupo deverão estar presentes durante a demonstração. Um dos componentes do grupo será aleatoriamente escolhido para responder perguntas. Quem não estiver presente vai ter nota zero! Cada componente do grupo deverá comentar sobre sua contribuição no trabalho.