Minimax (às vezes Minmax, MM ou ponto de sela) é uma regra de decisão usada em inteligência artificial, teoria da decisão, teoria dos jogos combinatória, estatística e filosofia. Seu objetivo é minimizar 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 de jogos de soma zero com vários jogadores, cobrindo tanto os casos em que os jogadores fazem movimentos alternados quanto aqueles em que fazem movimentos simultâneos, também foi estendido a jogos mais complexos e à tomada de decisão geral na presença de incerteza.
O conceito é central em cenários adversariais, onde o ganho de um jogador é a perda de outro. Nesses contextos, minimax fornece uma estratégia conservadora: assuma que o oponente sempre escolherá a ação que é pior para você e selecione o movimento que maximiza seu retorno garantido. Esse princípio fundamenta muitos algoritmos em aprendizado de máquina e aprendizado profundo, particularmente no treinamento de modelos generativos e no design de sistemas robustos.
Fundamentos da Teoria dos Jogos
Na teoria dos jogos, o valor maximin é o maior valor que um jogador pode ter certeza de obter sem conhecer as ações dos outros jogadores; equivalentemente, é o menor valor que os outros jogadores podem forçar o jogador a receber quando conhecem a ação do jogador. A definição formal é: v_i_underline = max_{a_i} min_{a_{-i}} v_i(a_i, a_{-i}), onde i é o índice do jogador, a_i é a ação tomada pelo jogador i, a_{-i} denota as ações de todos os outros jogadores e v_i é a função de valor do jogador i.
Calcular o valor maximin usa uma abordagem de pior caso: para cada ação possível do jogador, verifique todas as ações possíveis dos outros e determine a pior combinação – aquela que dá o menor valor. Então, escolha a ação que torna esse menor valor o mais alto possível. Por exemplo, considere um jogo de dois jogadores onde o jogador da linha pode escolher T, M ou B, e o jogador da coluna pode escolher L ou R, com pagamentos mostrados em uma tabela. O jogador da linha pode jogar T, garantindo um pagamento de pelo menos 2 (B é arriscado com −100, M pode render −10), então v_row_underline = 2. O jogador da coluna pode jogar L, garantindo pelo menos 0 (R arrisca −20), então v_col_underline = 0. Se ambos jogarem suas estratégias maximin (T, L), o vetor de pagamento é (3, 1).
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 conhece as ações dos outros. Sua definição formal é: v_i_overline = min_{a_{-i}} max_{a_i} v_i(a_i, a_{-i}). Em jogos de soma zero, o valor minimax é igual ao valor maximin para cada jogador, levando ao teorema minimax.
Teorema Minimax e Jogos de Soma Zero
O teorema minimax, provado por John von Neumann em 1928, afirma que em jogos finitos, de dois jogadores e de soma zero com estratégias mistas, o valor maximin é igual ao valor minimax. Este teorema fornece uma base para a análise de equilíbrio. Nesses jogos, o valor do jogo é o pagamento esperado quando ambos os jogadores jogam de forma ótima. O teorema garante que um jogador pode garantir pelo menos esse valor, e o oponente pode limitá-lo a no máximo esse valor.
Para jogos de movimento simultâneo, o conceito se estende a estratégias mistas, onde os jogadores randomizam sobre ações puras. O teorema minimax garante a existência de um ponto de sela em estratégias mistas, que é um par de estratégias onde nenhum jogador pode melhorar seu pagamento desviando unilateralmente. Esse resultado é fundamental no treinamento de redes neurais, onde exemplos adversariais são analisados usando princípios semelhantes de pior caso.
Aplicações em Inteligência Artificial
Em IA, minimax é amplamente usado na tomada de decisão para jogos e cenários adversariais. O exemplo clássico é o algoritmo minimax para jogos de dois jogadores por turnos, como xadrez, damas ou jogo da velha. O algoritmo avalia recursivamente a árvore de jogo, assumindo que o oponente joga de forma ótima. Em cada nó, o jogador escolhe o movimento que maximiza seu ganho mínimo, enquanto o oponente escolhe o movimento que minimiza o ganho máximo do jogador. Isso é frequentemente combinado com poda alfa-beta para reduzir a complexidade computacional.
Em modelos de linguagem grandes e arquiteturas transformer, princípios minimax aparecem no treinamento adversarial, onde modelos são treinados para serem robustos contra perturbações de pior caso. Por exemplo, redes adversariais generativas (GANs) usam um objetivo minimax: o gerador tenta minimizar a capacidade do discriminador de distinguir dados reais de falsos, enquanto o discriminador tenta maximizar sua precisão. Esse processo adversarial é uma aplicação direta de minimax em aprendizado profundo.
Extensões e Variações
Minimax foi estendido a jogos mais complexos, incluindo jogos com chance (como gamão) usando expectiminimax, e jogos com informação imperfeita usando técnicas como minimização de arrependimento contrafactual. Em aprendizado por reforço, minimax é usado em controle robusto e cenários multiagente, onde agentes devem considerar o comportamento de pior caso do oponente. O conceito também aparece em otimização e estatística, onde estimadores minimax minimizam o risco máximo.
No xadrez computacional e outros jogos de IA, minimax com poda alfa-beta permanece uma técnica central, embora sistemas modernos como OpenAI e Google DeepMind frequentemente usem abordagens de aprendizado de máquina que incorporam objetivos semelhantes a minimax. O princípio também é relevante na teoria da decisão para escolher ações sob incerteza, onde um tomador de decisão seleciona a opção que minimiza a perda de pior caso.
Contexto Histórico e Conceitos Relacionados
A regra minimax tem raízes na teoria dos jogos e na teoria da decisão, com contribuições de matemáticos como John von Neumann e Oskar Morgenstern. Está intimamente relacionada ao conceito de ponto de sela em otimização e ao equilíbrio de Nash em jogos de soma não zero. Na filosofia, minimax é usado em discussões sobre racionalidade e aversão ao risco.
Na IA moderna, minimax é frequentemente contrastado com a teoria da decisão bayesiana, que usa probabilidades a priori em vez de suposições de pior caso. Enquanto minimax é conservador, métodos bayesianos podem ser mais flexíveis. A escolha entre eles depende da disponibilidade de informações probabilísticas. Na pesquisa em IA, minimax permanece um referencial para avaliar algoritmos de tomada de decisão, especialmente em ambientes adversariais.
Ver Também
- Poda alfa-beta
- Teoria dos jogos
- Jogo de soma zero
- Aprendizado de máquina adversarial