O minimax, na teoria dos jogos, é um método que visa minimizar a perda esperada. Para isso, o jogador assume que a decisão do adversário será desfavorável. Ou seja, o pior cenário é esperado antes da movimentação do adversário.
Em outras palavras, o método minimax consiste em como tomar a melhor decisão assumindo que o outro jogador escolherá o pior cenário para você.
Devemos levar em conta que este método é aplicável em um jogo de duas pessoas (dois jogadores) e que não é cooperativo, mas sim um jogo de soma zero. Isso significa que o que um jogador ganha é perdido pelo outro e vice-versa. Conseqüentemente, cada agente estará interessado em maximizar sua própria utilidade, mesmo que isso prejudique o outro.
Nesse ponto, devemos lembrar também que a teoria dos jogos é um ramo da matemática e da economia que estuda a escolha que otimiza a situação de um indivíduo quando os custos e benefícios não são fixados com antecedência, mas dependem das decisões dos outros.
Algoritmo Minimax em uma árvore de decisão
Podemos ver como o método minimax é aplicado em uma árvore de decisão com vários nós. O jogo começa na parte inferior e termina com um resultado no nível superior.
Na base da árvore, o oponente faz o primeiro movimento, portanto, o pior resultado é esperado. Depois, no segundo nível, cabe ao jogador x que buscará maximizar seu lucro, levando em consideração a decisão previamente tomada pelo adversário.
No terceiro nível, é novamente a vez do oponente e assim por diante. Vamos mostrar um exemplo abaixo.
Exemplo de algoritmo Minimax
Na árvore de decisão a seguir, mostramos os resultados obtidos pelo jogador x em cada momento do jogo. Na base, no primeiro nível, o adversário toma a decisão. Por esse motivo, são apresentados os cenários em que o jogador pode perder -10 ou ganhar 5.
No segundo nível, depende do jogador x, então ele maximizará seu lucro. Entre perder 10 ou ganhar 1, você ganhará 1. Da mesma forma, entre ganhar 5 ou 7, você ganhará 7.
Depois, é a vez do adversário novamente, portanto serão dados os cenários em que o jogador x tem o pior resultado, -3 e 4, dependendo do caso. Finalmente, entre perder 3 ou ganhar 4, o jogador x tomará a decisão que permitirá a última.
Devemos levar em consideração que os valores de cada nó dependerão de uma função utilidade.
Para entender melhor a árvore, suponha que na base a decisão seja sobre a distribuição do produto. O competidor (o adversário) pode terceirizar a distribuição (veja o lado esquerdo da árvore). Nesse caso, ele deve escolher, por exemplo, entre o carteador A e B. Assim, ele escolhe o primeiro, fazendo com que o jogador x perca 10 (se escolhesse B, o jogador x ganharia 12).
Porém, talvez o adversário prefira distribuir ele mesmo sua mercadoria, podendo alugar veículos motorizados ou comprar um caminhão. De ambos os cenários, escolha o primeiro que for menos lisonjeiro para o jogador x porque ele ganha 5 e não 10.