Minimax - Projeto de algoritmo

---

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