Minimax

Minimax representa a partida como uma árvore de possibilidades. Cada ramo é um lance, e cada nível alterna entre um lado e o outro. Um motor de xadrez, isto é, um programa que analisa posições e escolhe lances, considera suas próprias opções e depois as melhores respostas do adversário. Sua premissa central é cautelosa: não depende de o adversário cometer um erro.

Nos níveis em que o motor joga, o algoritmo mantém o resultado mais favorável. Nos níveis do adversário, mantém o resultado menos favorável para o motor, pois pressupõe que o adversário resistirá da melhor forma possível. Esses valores são então propagados de volta das posições futuras até a posição atual. Assim, os lances iniciais podem ser comparados pelo resultado que cada um garante contra a melhor defesa.

Uma busca prática raramente consegue examinar a partida inteira. Em seu limite de profundidade, ela usa uma função de avaliação, uma fórmula que estima qual lado está melhor. Portanto, uma escolha minimax com profundidade limitada não é uma prova absoluta: depende de até onde a busca chegou e da precisão dessa estimativa. Ela também pode sofrer o efeito horizonte, quando uma consequência importante fica logo além do corte.

Os motores tornam esse modelo eficiente com técnicas como a ordenação de lances, que examina primeiro opções promissoras para que ramos irrelevantes possam ser rejeitados mais cedo. Outros sistemas, entre eles a busca em árvore de Monte Carlo, distribuem o esforço de forma diferente, mas perseguem o mesmo objetivo prático: identificar o lance que merece maior confiança.