Minimax

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Question book.svg
Esta página não cita fontes confiáveis e independentes, o que compromete sua credibilidade (desde julho de 2014). Por favor, adicione referências e insira-as corretamente no texto ou no rodapé. Conteúdo sem fontes poderá ser removido.
Encontre fontes: Google (notícias, livros e acadêmico)
Searchtool.svg
Esta página foi marcada para revisão, devido a incoerências e/ou dados de confiabilidade duvidosa. Se tem algum conhecimento sobre o tema, por favor, verifique e melhore a coerência e o rigor deste artigo.

Em teoria da decisão, o minimax (ou minmax) é um método para minimizar a possível perda máxima. Pode ser considerado como a maximização do ganho mínimo (maximin). Começa-se com dois jogadores 0-0 da teoria dos jogos, cobrindo ambos os casos em que os jogadores tomam caminhos alternados (por rodadas) ou simultaneamente. Pode-se estender o conceito para jogos mais complexos e para tomada de decisão na presença de incertezas. Nesse caso, não existe outro jogador, as consequências das decisões dependem de fatores desconhecidos.

Uma versão simples do algoritmo minimax lida com jogos como o jogo da velha, no qual cada jogador pode ganhar, perder ou empatar. Se o jogador A pode vencer com um movimento, esse é o seu melhor movimento. Se o jogador B identifica que um movimento levará a uma situação em que o adversário pode ganhar no próximo movimento, e que existe outro movimento que poderá levar a uma situação em que o adversário pode, no máximo, empatar, então, este último é o melhor movimento para ele. Após algumas rodadas, é fácil identificar qual é o melhor movimento. O algoritmo minimax ajuda a encontrar a melhor jogada, ao se caminhar pelas opções válidas, a partir do fim do jogo. A cada passo, assume-se que o jogador A está tentando maximizar as chances dele ganhar, enquanto na próxima rodada o jogador B está tentando minimizar as chances de isso acontecer (ao maximizar as chances de que ele próprio ganhe).

Algoritmo[editar | editar código-fonte]

O algoritmo minimax (usando uma heurística para terminar o vasculhamento após uma dada profundidade) é mostrado abaixo, em pseudocódigo.

ROTINA minimax(nó, profundidade)
    SE nó é um nó terminal OU profundidade = 0 ENTÃO
        RETORNE o valor da heurística do nó
    SENÃO SE o nó representa a jogada de algum adversário ENTÃO
        α ← +∞
        PARA CADA filho DE nó
            α ← min(α, minimax(filho, profundidade-1))
        FIM PARA
        RETORNE α
    SENÃO
        α ← -∞
        PARA CADA filho DE nó
            α ← max(α, minimax(filho, profundidade-1))
        FIM PARA
        RETORNE α
    FIM SE
FIM ROTINA

A versão negamax deste mesmo algoritmo é apresentada abaixo. Essa versão baseia-se na observação que . Embora essa versão funcione apenas em jogos com dois jogadores, ela evita a necessidade do algoritmo tratar os jogadores separadamente.

ROTINA negamax(nó, profundidade)
    SE nó é um nó terminal OU profundidade = 0 ENTÃO
        RETORNE o valor da heurística do nó
    SENÃO
        α ← -∞                       { a avaliação é idêntica para ambos os jogadores }
        PARA CADA filho DE nó
            α ← max(α, -negamax(filho, profundidade-1))
        FIM PARA
        RETORNE α
    FIM SE
FIM ROTINA

Ver também[editar | editar código-fonte]