Este trabalho vale nota e será utilizado para calcular a média junto com as notas dos testes e do primeiro trabalho, para quem escolheu ser avaliado por 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 o humano). O utilizador poderá optar por começar o jogo ou deixar o computador iniciar. Também poderá escolher o símbolo (X ou O) a utilizar.
Trabalhos cuja implementação criam a árvore de jogo e a mantém em memória serão penalizados. A árvore deve ser construída a cada jogada e em profundidade, de acordo com os algoritmos básicos dados em aula e apresentados nos livros texto.
O que entregar:
Organização do trabalho escrito:
Descrição de jogos com oponentes e algoritmos para resolvê-los.
Descrição
Descrição
Descrição do jogo. Objetivos.
Discussão sobre os dois algoritmos aplicados ao jogo do galo. Estruturas de dados utilizadas. 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.
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.
Não esquecer de citar no texto, nos locais adequados, a biliografia listada nesta seção.
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.