Minimax - Projeto de algoritmo
Por: Daiana Couto • 26/4/2016 • Artigo • 870 Palavras (4 Páginas) • 645 Visualizações
Resumo
Trabalharemos a disciplina de Inteligência Artificial com o foco em algoritmo de busca competitiva, aprofundando as pesquisas especificamente no método Minimax(MinMax).
Será implementada uma aplicação na linguagem Java buscando entender melhor o funcionamento dessa técnica de busca. O propósito da aplicação se dá em implementar um exemplar do jogo da velha e explorar a inteligência aplicada ao algoritmo.
Introdução
O objetivo de um algoritmo Minimax, no caso de jogos, é decidir qual a melhor jogada que o jogador poderá fazer de forma a minimizar a melhor jogada possível do adversário.
Minimax lida com jogos como o jogo da velha, no qual cada jogador pode ganhar, perder ou empatar. Considerando que após a sua jogada, seu adversário vai escolher a melhor jogada possível e então você a partir dessa melhor jogada já pensa na melhor que você pode fazer e assim sucessivamente.
O jogador MAX sempre considera que MIN vai escolher a jogada que o deixa na pior situação (pior caso para MAX) e que ele (o MAX) vai escolher a melhor jogada para si. O algoritmo minimax ajuda a encontrar a melhor jogada ao caminhar pelas opções válidas a partir do fim do jogo. A cada passo assume-se que o jogador MAX está tentando maximizar as chances de MAX ganhar, enquanto na próxima rodada o jogador MIN está tentando minimizar as chances de isso acontecer (ao maximizar as chances de que ele próprio ganhe).
Objetivos
Construir um software que seguirá o padrão arquitetural MVC, onde haverá um módulo de controle que abrigará todos os arquivos necessários para a implementação do algoritmo.
Na modelagem teremos a especificação dos objetos a serem utilizados.
Por fim, no módulo de visão dispomos de todas as classes necessárias para a construção do jogo conhecido como “Jogo da Velha”, que contará com um tabuleiro 3x3, definindo o padrão de competição CPU (X) x Humano (O).
Referencial Teórico
Este teorema surgiu a partir da Zero-Sum Game Theory:
“Para qualquer jogo para dois jogadores que respeite a teoria zero-sum, existe uma estratégia mista para cada jogador tal que o resultado esperado para os dois é o mesmo valor V quando os jogadores usam esta estratégia. V é o melhor valor que cada um pode esperar de uma jogada. Isto é, estas estratégias mistas são as estratégias ótimas para os dois jogadores.”
Heurística = ∑ linhas/colunas/diagonais em aberto ->X
-
∑ linhas/colunas/diagonais em aberto ->O
O Teorema Minimax foi escrito por Von Neumann, que foi um brilhante matemático nascido
em Budapeste em 1903. Devido à demonstração do teorema minimax, ele foi considerado o pai da teoria dos jogos em 1926.
Pseudo-código Jogo da Velha:
Determinar
SE {
profundidade limite atingida
OU Nivel é Minimizador
OU Nivel é Maximizador }
ENTÃO
SE profundidade limite
...