Minimax

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Question book.svg
Esta página não cita fontes fiáveis e independentes (desde julho de 2014). Por favor, adicione referências e insira-as no texto ou no rodapé, conforme o livro de estilo. Conteúdo sem fontes poderá ser removido.
Searchtool.svg
Esta página ou secção foi marcada para revisão, devido a inconsistências e/ou dados de confiabilidade duvidosa. Se tem algum conhecimento sobre o tema, por favor, verifique e melhore a consistência e o rigor deste artigo. Considere utilizar {{revisão-sobre}} para associar este artigo com um WikiProjeto e colocar uma explicação mais detalhada na discussão.

Em teoria da decisão, o minimax (ou minmax) é um método para minimizar a perda máxima possível. 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, seu melhor movimento é o movimento para a vitória. Se o jogador B identifica que um movimento levará a uma situação em que o adversário pode ganhar em um movimento, enquanto outro movimento levará a uma situação de empate, então a melhor jogada do jogador B é a que leva para o empate. Após algumas rodadas é fácil identificar qual é o melhor movimento. 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 A está tentando maximizar as chances de A 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 \max ( a,b ) = - \min ( -a,-b ). 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]