Minimax - Jogo Da Velha

UNIVERSIDADE FEDERAL RURAL DO RIO DE JANEIRO

Instituto Multidisciplinar de Nova Iguaçu

Departamento de Tecnologias e Linguagens

Ciências da Computação

Laboratório de Inteligência Artificial

Implementação de um Jogo de Velha utilizando o algoritmo MiniMax

Relatório apresentado como requisito final para obtenção de aprovação na disciplina Laboratório de Inteligência Artificial, no Curso de Ciências da Computação, na Universidade Federal Rural do Rio de Janeiro

Aluno: Tiago da Silva Pimentel Matricula: 201178528-4

Prof. Ronaldo Goldsmith

1. INTRODUÇÃO

Este trabalho tem como objetivo, demonstrar o uso da Inteligência Artificial para a resolução de problemas em jogos, computando a melhor alternativa.

Para demonstração do uso da Inteligência Artificial, foi desenvolvido um Jogo da Velha, para partidas entre um HUMANO e o COMPUTADOR. Neste jogo, ganha o jogador que conseguir formar uma seqüência de três símbolos idênticos consecutivos (em linha reta).

Para as escolhas das jogadas do Computador, foi utilizado o algoritmo MiniMax.

O jogo foi desenvolvido na Linguagem Java, uma linguagem orientada à objetos, mas poderia ser desenvolvido em qualquer linguagem computacional.

2. O PROBLEMA DO JOGO

Em um Jogo da Velha são usados os símbolos ‘X’ (xis) e ‘O’ (bola), analisando o número de combinações possíveis de dispor um dos símbolos no “tabuleiro”, encontramos 362.880 (ou 9!) maneiras de se fazer isso.

Quando consideramos as combinações vencedoras, existem 255.168 jogos possíveis. Assumindo que ‘X’ inicia o jogo (se considerar que ‘O’ inicia, os resultados passam a ser inversos), temos:

• 131.184 jogos finalizados são ganhos por ‘X’

o 1.440 são ganhos por ‘X’ após 5 movimentos

o 47.952 são ganhos por ‘X’ após 7 movimentos

o 81.792 são ganhos por ‘X’ após 9 movimentos

• 77.904 jogos finalizados são ganhos por ‘O’

o 5.328 são ganhos por ‘O’ após 6 movimentos

o 72.576 são ganhos por ‘O’ após 8 movimentos

o 46.080 jogos finalizados resultam em empate

Ignorando jogadas simétricas (outras jogadas rotacionadas ou refletidas), existem 138 resultados únicos. Assumindo novamente que ‘X’ sempre inicia o jogos, temos:

• 91 resultados únicos são ganhos por ‘X’

o 21 são ganhos por ‘X’ após 5 movimentos

o 58 são ganhos por ‘X’ após 7 movimentos

o 12 são ganhos por ‘X’ após 9 movimentos

• 44 resultados únicos são ganhos por ‘O’

o 21 são ganhos por ‘O’ após 6 movimentos

o 23 são ganhos por ‘O’ após 8 movimentos

o 3 resultados únicos são empates