Minimax

Minmax (às vezes Minimax, MM ou ponto de sela) é uma regra de decisão usada em inteligência artificial, teoria da decisão, teoria dos jogos, estatística e filosofia para minimimizar a perda possível para um cenário de pior caso (perda máxima). Ao lidar com ganhos, é referido como "maximin" – para maximizar o ganho mínimo. Originalmente formulado para a teoria dos jogos de soma zero com vários jogadores, abrangendo tanto os casos em que os jogadores fazem movimentos alternados quanto aqueles em que fazem movimentos simultâneos, também foi estendido para jogos mais complexos e para a tomada de decisão geral na presença de incerteza.

Teoria dos jogos

Em jogos gerais

O valor maximin é o valor mais alto que o jogador pode ter certeza de obter sem conhecer as ações dos outros jogadores; equivalentemente, é o valor mais baixo que os outros jogadores podem forçar o jogador a receber quando souberem da ação do jogador. Sua definição formal é:

vEu...Não. Não. = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =máx.umEu...minum- Sim. - Sim. Eu...vEu...(umEu...,um- Sim. - Sim. Eu...){displaystyle {underline {v_{i}}}=max _{a_{i}}min _{a_{-i}}{v_{i}(a_{i},a_{-i})}}

Onde:

• Eu... é o índice do jogador de interesse.
• - Sim. - Sim. Eu...- Sim. denota todos os outros jogadores exceto o jogador Eu....
• umEu...Não. a_{i}} é a ação tomada pelo jogador Eu....
• um- Sim. - Sim. Eu...Não. a_{-i}} denota as ações tomadas por todos os outros jogadores.
• vEu...Não. v_{i}} é a função de valor do jogador Eu....

Calcular o valor maximin de um jogador é feito em uma abordagem de pior caso: para cada ação possível do jogador, verificamos todas as ações possíveis dos outros jogadores e determinamos a pior combinação possível de ações – aquela que dá ao jogador i o menor valor. Em seguida, determinamos qual ação o jogador i pode realizar para garantir que esse menor valor seja o maior possível.

Por exemplo, considere o seguinte jogo para dois jogadores, onde o primeiro jogador ("jogador da linha") pode escolher qualquer um dos três movimentos, rotulados T, M ou B, e o segundo jogador (jogador da "coluna") pode escolher um dos dois movimentos, L ou R. O resultado da combinação de ambos os movimentos é expresso em uma tabela de pagamentos:

LRT3,12,- Sim. - Sim. 20.M5,0- Sim. - Sim. 10.,1B- Sim. - Sim. 100.,24,4{displaystyle {begin{array}{c|cc}hline &L&R\hline T&3,1&2,-20M&5,0&-10,1B&-100,2&4,4\hline end{array}}}

(onde o primeiro número em cada célula é o pagamento do jogador da linha e o segundo número é o pagamento do jogador da coluna).

A título de exemplo, consideramos apenas estratégias puras. Verifique cada jogador por sua vez:

• O jogador de linha pode jogar T, que lhes garante um pagamento de pelo menos 2 (playing) B é arriscado, uma vez que pode levar ao pagamento - 100.e jogando M pode resultar em um pagamento de - Sim.). Assim: vRoO quê?Não. Não. = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =2{displaystyle {underline {v_{row}}}=2}.
• O jogador da coluna pode jogar L e garantir um pagamento de pelo menos 0 (playing) R coloca-los no risco de ficar - Sim. - Sim. 20.Não.). Assim: vcoEu...Não. Não. = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =0{displaystyle {underline {v_{col}}}=0}.

Se ambos os jogadores jogarem suas respectivas estratégias máximas (T,L)(T,L)}, o vetor de payoff é (3,1)Não..

O valor minimax de um jogador é o menor valor que os outros jogadores podem forçar o jogador a receber, sem conhecer as ações do jogador; equivalentemente, é o maior valor que o jogador pode ter certeza de obter quando conhecer as ações dos outros jogadores. Sua definição formal é:

vEu...? ? = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =minum- Sim. - Sim. Eu...máx.umEu...vEu...(umEu...,um- Sim. - Sim. Eu...){displaystyle {overline {v_{i}}}=min _{a_{-i}}max _{a_{i}}{v_{i}(a_{i},a_{-i})}}

A definição é muito semelhante à do valor maximin – apenas a ordem dos operadores máximo e mínimo é inversa. No exemplo acima:

• O jogador de linha pode obter um valor máximo de 4 (se o outro jogador tocar R) ou 5 (se o outro jogador tocar L), assim: vRoO quê?? ? = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =4.{displaystyle {overline {v_{row}}}=4.}
• O leitor de coluna pode obter um valor máximo de 1 (se o outro jogador tocar T), 1 (se) M) ou 4 (se) B). Assim: vcoEu...? ? = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =1.{displaystyle {overline {v_{col}}}=1.}

Para cada jogador i, o maximin é no máximo o minimax:

vEu...Não. Não. ≤ ≤ vEu...? ? {displaystyle {underline {v_{i}}}leq (v_{i}}

Intuitivamente, no maximin a maximização vem depois da minimização, então o jogador i tenta maximizar seu valor antes de saber o que os outros vai fazer; no minimax a maximização vem antes da minimização, então o jogador i está em uma posição muito melhor – eles maximizam seu valor sabendo o que os outros fez.

Outra forma de entender a notação é lendo da direita para a esquerda: Quando escrevemos

vEu...? ? = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =minum- Sim. - Sim. Eu...máx.umEu...vEu...(umEu...,um- Sim. - Sim. Eu...)= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =minum- Sim. - Sim. Eu...(máx.umEu...vEu...(umEu...,um- Sim. - Sim. Eu...)){displaystyle {overline {v_{i}}}=min _{a_{-i}}max _{a_{i}}{v_{i}(a_{i},a_{-i})}=min _{a_{-i}} Grande (}max _{a_{i}}{v_{i}(a_{i},a_{-i})}{ Grande)}}

o conjunto inicial de resultados vEu...(umEu...,um- Sim. - Sim. Eu...){displaystyle v_{i}(a_{i},a_{-i}) ? depende de ambos umEu...{displaystyle {a_{i}} } e um- Sim. - Sim. Eu....{displaystyle {a_{-i}}.} Nós primeiro marginalizar fora umEu...Não. {a_{i}}} a partir de vEu...(umEu...,um- Sim. - Sim. Eu...){displaystyle v_{i}(a_{i},a_{-i})}, maximizando sobre umEu...{displaystyle {a_{i}} } (para cada valor possível de um- Sim. - Sim. Eu...Não. {a_{-i}}}) produzir um conjunto de resultados marginais vEu...?(um- Sim. - Sim. Eu...),{displaystyle v'_{i}(a_{-i}),} que depende apenas de um- Sim. - Sim. Eu....{displaystyle {a_{-i}}.} Então minimizamos um- Sim. - Sim. Eu...{displaystyle {a_{-i}} } sobre estes resultados. (Conversamente para maximin.)

Embora seja sempre o caso de vRoO quê?Não. Não. ≤ ≤ vRoO quê?? ? {displaystyle {underline {v_{row}}}leq} (v_{row)} e vcoEu...Não. Não. ≤ ≤ vcoEu...? ? ,{displaystyle {underline {v_{col}}}leq} {overline {v_{col}}},} o vetor payoff resultante de ambos os jogadores que jogam suas estratégias minimax, (2,- Sim. - Sim. 20.){displaystyle (2,-20) } no caso de (T,R){displaystyle (T,R) } ou (- Sim. - Sim. 10.,1)(10,1)} no caso de (M,R),{displaystyle (M,R),} não pode igualmente ser classificado contra o vetor payoff (3,1){displaystyle (3,1) } resultante de ambos os jogadores jogando sua estratégia maximin.

Em jogos de soma zero

Em jogos de soma zero para dois jogadores, a solução minimax é igual ao equilíbrio de Nash.

No contexto de jogos de soma zero, o teorema minimax é equivalente a:

Para cada jogo de duas pessoas, zero-sum com muitas estratégias finitas, existe um valor V e uma estratégia mista para cada jogador, tal que

(a) Dada a estratégia do Jogador 2, o melhor pagamento possível para o Jogador 1 é Ve

(b) Dada a estratégia do Jogador 1, o melhor pagamento possível para o Jogador 2 é −V.

Equivalentemente, a estratégia do Jogador 1 garante a eles um pagamento de V independentemente da estratégia do Jogador 2, e da mesma forma, o Jogador 2 pode garantir a si mesmo um pagamento de −V. O nome minimax surge porque cada jogador minimiza o ganho máximo possível para o outro – uma vez que o jogo é de soma zero, eles também minimizam sua própria perda máxima (ou seja, maximizam seu ganho mínimo). Veja também exemplo de jogo sem valor.

Exemplo

O seguinte exemplo de um jogo de soma zero, onde A e B fazem movimentos simultâneos, ilustra soluções maximin. Suponha que cada jogador tenha três opções e considere a matriz de pagamento para A exibida na mesa ("matriz de pagamento para o jogador A"). Suponha que a matriz de pagamento para B seja a mesma matriz com os sinais invertidos (ou seja, se as opções forem A1 e B1, então B paga 3 para A). Então, a escolha maximin para A é A2, pois o pior resultado possível é pagar 1, enquanto a escolha maximin simples para B é B2, pois o pior resultado possível é então nenhum pagamento. No entanto, esta solução não é estável, pois se B acredita que A escolherá A2, então B escolherá B1 para ganhar 1; então, se A acreditar que B escolherá B1, então A escolherá A1 para ganhar 3; e então B escolherá B2; e, eventualmente, ambos os jogadores perceberão a dificuldade de fazer uma escolha. Portanto, uma estratégia mais estável é necessária.

Algumas escolhas são dominadas por outras e podem ser eliminadas: A não escolherá A3, pois A1 ou A2 produzirão um resultado melhor, não importa o que B escolhe; B não escolherá B3, pois algumas misturas de B1 e B2 produzirão um resultado melhor, não importa o que A escolha.

O jogador A pode evitar ter que fazer um pagamento esperado de mais de 1 /3 escolhendo A1 com probabilidade 1/6 e A2 com probabilidade 5/ 6: o retorno esperado para A seria 3 × 1/6 − 1 × 5/ 6 = -+1/3 caso B escolha B1 e −2 × 1/6 + 0 × 5/6 = -+1 /3 caso B escolheu B2. Da mesma forma, B pode garantir um ganho esperado de pelo menos 1/3, não importa o que A escolha, usando uma estratégia aleatória de escolha de B1 com probabilidade 1/3 e B2 com probabilidade 2/3. Essas estratégias minimax mistas não podem ser melhoradas e agora estão estáveis.

Maximin

Frequentemente, na teoria dos jogos, maximin é diferente de minimax. Minimax é usado em jogos de soma zero para denotar a minimização do pagamento máximo do oponente. Em um jogo de soma zero, isso é idêntico a minimizar a própria perda máxima e maximizar o ganho mínimo.

"Maximin" é um termo comumente usado para jogos de soma diferente de zero para descrever a estratégia que maximiza o próprio pagamento mínimo. Em jogos de soma diferente de zero, isso geralmente não é o mesmo que minimizar o ganho máximo do oponente, nem o mesmo que a estratégia de equilíbrio de Nash.

Em jogos repetidos

Os valores minimax são muito importantes na teoria dos jogos repetidos. Um dos teoremas centrais desta teoria, o teorema popular, baseia-se nos valores minimax.

Teoria dos jogos combinatórios

Na teoria combinatória dos jogos, existe um algoritmo minimax para soluções de jogos.

Uma versão simples do algoritmo minimax, indicado abaixo, lida com jogos como jogo da velha, onde cada jogador pode ganhar, perder ou empatar. Se o jogador A conseguir vencer em um lance, seu melhor lance é o lance vitorioso. Se o jogador B souber que um movimento levará à situação em que o jogador A pode vencer em um movimento, enquanto outro movimento levará à situação em que o jogador A pode, na melhor das hipóteses, empatar, então o jogador B&# A melhor jogada de 39 é aquela que leva ao empate. No final do jogo, é fácil ver qual é o "melhor" movimento é. O algoritmo minimax ajuda a encontrar a melhor jogada, trabalhando de trás para frente desde o final do jogo. Em cada etapa, assume que o jogador A está tentando maximizar as chances de vitória de A, enquanto no turno seguinte o jogador B está tentando minimizar as chances de vitória de A (ou seja,, para maximizar as chances de vitória de B).

Algoritmo Minimax com movimentos alternativos

Um algoritmo minimax é um algoritmo recursivo para escolher o próximo movimento em um jogo para n jogadores, geralmente um jogo para dois jogadores. Um valor é associado a cada posição ou estado do jogo. Esse valor é calculado por meio de uma função de avaliação de posição e indica o quão bom seria para um jogador alcançar aquela posição. O jogador então faz a jogada que maximiza o valor mínimo da posição resultante das possíveis jogadas seguintes do oponente. Se for a vez de A, A atribui um valor a cada um dos seus movimentos legais.

Um possível método de alocação consiste em atribuir um determinado ganho para A como +1 e para B como -1. Isso leva à teoria combinatória dos jogos desenvolvida por J.H. Conway. Uma alternativa é usar uma regra que se o resultado de um movimento for uma vitória imediata para A, é atribuído infinito positivo e se for uma vitória imediata para B, infinito negativo. O valor para A de qualquer outro movimento é o mínimo dos valores resultantes de cada uma das possíveis respostas de B'. Por esta razão, A é chamado de jogador maximizador e B é chamado de jogador minimizador, daí o nome algoritmo minimax. O algoritmo acima atribuirá um valor de infinito positivo ou negativo a qualquer posição, pois o valor de cada posição será o valor de alguma posição vencedora ou perdedora final. Freqüentemente, isso geralmente só é possível no final de jogos complicados, como xadrez ou go, uma vez que não é computacionalmente viável olhar para a frente até a conclusão do jogo, exceto no final e, em vez disso, as posições recebem valores finitos como estimativas do grau de crença de que eles levarão à vitória de um ou outro jogador.

Isso pode ser estendido se pudermos fornecer uma função de avaliação heurística que forneça valores para estados de jogo não finais sem considerar todas as sequências completas seguintes possíveis. Podemos então limitar o algoritmo minimax para olhar apenas para um certo número de movimentos à frente. Esse número é chamado de "look-ahead", medido em "plies". Por exemplo, o computador de xadrez Deep Blue (o primeiro a derrotar o atual campeão mundial, Garry Kasparov na época) previu pelo menos 12 camadas e aplicou uma função de avaliação heurística.

O algoritmo pode ser pensado como explorando os nós de uma árvore de jogo. O fator de ramificação efetivo da árvore é o número médio de filhos de cada nó (ou seja, o número médio de movimentos legais em uma posição). O número de nós a serem explorados geralmente aumenta exponencialmente com o número de camadas (é menos exponencial se avaliar movimentos forçados ou posições repetidas). O número de nós a serem explorados para a análise de um jogo é, portanto, aproximadamente o fator de ramificação elevado à potência do número de camadas. Portanto, é impraticável analisar completamente jogos como o xadrez usando o algoritmo minimax.

O desempenho do algoritmo minimax ingênuo pode ser melhorado dramaticamente, sem afetar o resultado, pelo uso da poda alfa-beta. Outros métodos de poda heurística também podem ser usados, mas nem todos garantem o mesmo resultado da pesquisa não podada.

Um algoritmo minimax ingênuo pode ser modificado trivialmente para retornar adicionalmente uma variação principal inteira junto com uma pontuação minimax.

Pseudocódigo

O pseudocódigo para o algoritmo minimax limitado em profundidade é fornecido abaixo.

função minimax (nodo, profundidade, maximizandoPlayer) o se profundidade = 0 ou nó é um nó terminal então retorno o valor heurístico do nó
 se maximizar Jogador entãovalor:= −∞
 para cada criança do nó dovalor:= max (valor, minimax (criança, profundidade − 1, FALSE))
 retorno valor
 mais (* minimizar jogador *)valor:= +∞
 para cada criança do nó dovalor:= min (valor, minimax (criança, profundidade − 1, TRUE))
 retorno valor

(* Chamada inicial *)minimax (origem, profundidade, TRUE)

A função minimax retorna um valor heurístico para nós folha (nós terminais e nós na profundidade máxima de pesquisa). Os nós não folha herdam seu valor de um nó folha descendente. O valor heurístico é uma pontuação que mede a favorabilidade do nó para o jogador maximizador. Portanto, os nós que resultam em um resultado favorável, como uma vitória, para o jogador maximizador têm pontuações mais altas do que os nós mais favoráveis para o jogador minimizador. O valor heurístico para nós de folha terminal (final do jogo) são pontuações correspondentes a vitória, derrota ou empate, para o jogador maximizador. Para nós folha não terminais na profundidade máxima de busca, uma função de avaliação estima um valor heurístico para o nó. A qualidade dessa estimativa e a profundidade da pesquisa determinam a qualidade e a precisão do resultado minimax final.

Minimax trata os dois jogadores (o jogador que maximiza e o jogador que minimiza) separadamente em seu código. Com base na observação que máx.(um,b))= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =- Sim. - Sim. min(- Sim. - Sim. um,- Sim. - Sim. b)),{displaystyle \max(a,b)=-min(-a,-b)} minimax pode ser frequentemente simplificado no algoritmo negamax.

Exemplo

Um exemplo de árvore minimax

Um exemplo pedagógico animado que tenta ser humano-amigável substituindo valores infinitos iniciais (ou arbitrariamente grandes) para o vazio e evitando usar as simplificações de codificação negamax.

Suponha que o jogo que está sendo jogado tenha no máximo dois movimentos possíveis por jogador a cada turno. O algoritmo gera a árvore da direita, onde os círculos representam as jogadas do jogador que executa o algoritmo (maximizando o jogador), e os quadrados representam as jogadas do oponente (minimizando o jogador). Devido à limitação de recursos de computação, conforme explicado acima, a árvore é limitada a um look-ahead de 4 movimentos.

O algoritmo avalia cada nó folha usando uma função de avaliação heurística, obtendo os valores mostrados. As jogadas em que o jogador maximizador vence são atribuídas com infinito positivo, enquanto as jogadas que levam à vitória do jogador minimizador são atribuídas com infinito negativo. No nível 3, o algoritmo escolherá, para cada nó, o menor dos valores do nó filho e o atribuirá a esse mesmo nó (por exemplo, o nó à esquerda escolha o mínimo entre "10" e "+∞", atribuindo assim a si mesmo o valor "10"). A próxima etapa, no nível 2, consiste em escolher para cada nó o maior dos valores de nó filho. Mais uma vez, os valores são atribuídos a cada nó pai. O algoritmo continua avaliando os valores máximo e mínimo dos nós filhos alternadamente até chegar ao nó raiz, onde escolhe o movimento com o maior valor (representado na figura com uma seta azul). Esta é a jogada que o jogador deve fazer para minimizar a máxima perda possível.

Minimax para decisões individuais

Minimax diante da incerteza

A teoria Minimax foi estendida para decisões onde não há outro jogador, mas onde as consequências das decisões dependem de fatos desconhecidos. Por exemplo, a decisão de prospecção de minerais acarreta um custo, que será desperdiçado se os minerais não estiverem presentes, mas trará grandes recompensas se estiverem. Uma abordagem é tratar isso como um jogo contra a natureza (veja movimento por natureza) e, usando uma mentalidade semelhante à lei de Murphy ou resistencialismo, adote uma abordagem que minimize a perda máxima esperada, usando as mesmas técnicas dos jogos de soma zero para duas pessoas.

Além disso, foram desenvolvidas árvores expectiminimax, para jogos de dois jogadores em que o acaso (por exemplo, dados) é um fator.

Critério Minimax na teoria da decisão estatística

Na teoria da decisão estatística clássica, temos um estimador δ δ {displaystyle delta } que é usado para estimar um parâmetro θ θ ∈ ∈ Θ Θ .{displaystyle \theta in Theta .} Também assumimos uma função de risco R(θ θ ,δ δ ).{displaystyle R(thetadelta).} geralmente especificado como a integral de uma função de perda. Neste quadro, δ δ ~ ~ } é chamado minimax se satisfizer

Vamos.θ θ R(θ θ ,δ δ ~ ~ )= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =infδ δ Vamos.θ θ R(θ θ ,δ δ ).{displaystyle sup _{theta }R(theta{tilde {delta }})=inf _{delta } sup _{theta } R(thetadelta).}

Um critério alternativo no quadro teórico da decisão é o estimador Bayes na presença de uma distribuição prévia D D .{displaystyle Pi .} Um estimador é Bayes se minimizar o média risco de risco

∫ ∫ Θ Θ R(θ θ ,δ δ )D⁡ ⁡ D D (θ θ ).{displaystyle int _{Theta }R(thetadelta)operatorname {d} Pi (theta).}

Teoria da decisão não probabilística

Uma característica fundamental da tomada de decisão minimax é ser não probabilística: em contraste com as decisões que usam valor esperado ou utilidade esperada, não faz suposições sobre as probabilidades de vários resultados, apenas análise de cenário de quais são os resultados possíveis. É, portanto, robusto a mudanças nas suposições, em contraste com essas outras técnicas de decisão. Existem várias extensões desta abordagem não probabilística, notadamente o arrependimento minimax e a teoria da decisão Info-gap.

Além disso, minimax requer apenas medição ordinal (que os resultados sejam comparados e classificados), não medições de intervalo (que os resultados incluem "quanto melhor ou pior") e retorna ordinal dados, usando apenas os resultados modelados: a conclusão de uma análise minimax é: "essa estratégia é minimax, pois o pior caso é (resultado), que é menos ruim do que qualquer outra estratégia". Compare com a análise de valor esperado, cuja conclusão é da forma: "Esta estratégia produz ℰ(X) = n." Minimax, portanto, pode ser usado em dados ordinais e pode ser mais transparente.

Maximin em filosofia

Na filosofia, o termo "maximin" é freqüentemente usado no contexto de Uma Teoria da Justiça de John Rawls, onde ele se refere a isso no contexto do Princípio da Diferença. Rawls definiu esse princípio como a regra que afirma que as desigualdades sociais e econômicas devem ser arranjadas de modo que "elas sejam do maior benefício para os membros menos favorecidos da sociedade".