Uma queixa bastante frequente nos videogames é que a inteligência artificial dos oponentes toma decisões ruins. Por esse motivo, em alguns casos diretamente trapaceiam, mas às vezes acontece o contrário, e eles apresentam estratégias muito eficazes em jogos que podemos considerar "simples". Uma das razões é a aplicação do Teorema Minimax, um algoritmo que tem como objetivo minimizar a perda máxima esperada em jogos de dois participantes, com informação perfeita para ambas as partes.
Muitos jogos escondem informações dos participantes como parte de sua mecânica. Sem ir muito longe, pense no "fog of war" de jogos clássicos (StarCraft e Civilization vêm à mente). Esse recurso permite que a inteligência artificial conjure 20 ou 30 unidades por mágica sem que você perceba (entre outras coisas), e sua eliminação é um passo essencial, seja enviando unidades para explorar, ou desenvolvendo tecnologias que cancelam seu efeito (como os Satélites em Civ).
Mas o que acontece quando a informação é perfeita? Como se comporta uma inteligência artificial quando não há nada a esconder, e todos os elementos da partida são conhecidos desde o início? Uma das muitas possibilidades para o desenvolvedor da vez é a implementação do Teorema Minimax. A descrição oficial fala de um "método de decisão para minimizar a perda máxima esperada", e isso pode parecer simples na superfície, mas merece uma exploração mais profunda:
Jogos de soma zero e o algoritmo Minimax
O canal BitBoss faz um excelente trabalho resumindo o algoritmo Minimax, e a melhor parte é que leva menos de quatro minutos. Basicamente, o Minimax funciona em jogos de soma zero, ou seja, nossa ganância ou vantagem se torna perda para o oponente. O xadrez é um exemplo clássico de jogo de soma zero com informação perfeita, mas o vídeo nos leva por um caminho mais simples, usando como referência o jogo da velha.
Cada fase da partida pode ser definida com um número, positivo para um jogador e negativo para o outro. A estratégia do algoritmo Minimax busca selecionar a melhor jogada disponível, assumindo completamente que o oponente também selecionará a melhor jogada contra você. Se uma inteligência artificial Minimax alcança a vitória com um número positivo, suas decisões tentarão seguir o caminho que favoreça esse número.
O gráfico mostra os últimos seis movimentos possíveis de uma inteligência artificial em uma partida de jogo da velha. Quatro deles expressam uma vitória para a IA (amarelo) com uma condição de 1, e os outros dois para o jogador humano (azul), com -1. Os movimentos são analisados de baixo para cima, ou de trás para frente: como à inteligência artificial só resta um movimento, os valores para cada um se movem para o passo anterior. Seguindo a mesma lógica, o jogador humano possui duas jogadas que lhe garantem um -1, e uma terceira que o obriga a escolher 1. Portanto, a IA garante a vitória colocando pressão nesse caminho, que começa com uma cruz no centro.
Obviamente, este é um exemplo simples demais, e possível apenas graças aos limites naturais do jogo da velha. Se transferirmos o método Minimax para jogos de alta complexidade como xadrez ou go, o número de estados a verificar cresce de forma exponencial, e a aplicação do Minimax se torna inviável. Uma possível solução é limitar a profundidade de exploração e, em termos gerais, é mais do que suficiente para dar uma surra nos n00bs.
