Busca Competitiva (ou Adversarial)
Este texto é parte da disciplina de Fundamentos de Inteligência Artificial do Programa de Pós-Graduação em Computação da Universidade Federal de Pelotas e não foi feito para fazer muito sentido fora deste contexto.
Muitos problemas podem ser solucionados se tratados como um problema de busca — dado um estado inicial, deseja-se encontrar uma solução que satisfaça algum critério. Por exemplo, no caso do Quebra Cabeça Deslizante abaixo, dado o estado atual (raíz da árvore), sabemos pelas regras do jogo quais são os estados possíveis.
O algoritmo de busca deve então escolher qual o próximo estado a ser visitado. Esta escolha pode ser dada por uma estrutura do tipo pilha ou fila (busca sem informação) ou informada por alguma heurística (busca com informação), mas é totalmente definida pelo algoritmo. Isto é, uma vez que o algoritmo decida visitar um estado, nada impede que ele o faça e isso é verdade para todos estados visitados.
Porém, este não é o caso sempre. Considere um jogo de dois jogadores como xadrez ou jogo-da-velha. Por um lado, ele é um problema bem definido como o Quebra Cabeça Deslizante ou Sudoku. Todas partes são observáveis. O estados são finitos. Os movimentos são determinísticos. Se sabe quando se chega a um estado final de forma inequívoca. Podemos então aplicar, por exemplo, o A* para solucionar o xadrez e sempre vencer, desconsiderando custos computacionais? O que é diferente?
A diferença, claro, é a presença de um adversário. Este oponente opera sobre a mesma árvore de busca que nosso algoritmo, mas de forma competitiva — tentando evitar que atinjamos um estado de vitória e direcionando o jogo em direção a um estado de derrota para nosso algoritmo. Isto significa que não temos mais controle sobre qual será o próximo estado para todos níveis da árvore. O oponente controla a busca em certos momentos.
Este tipo de problema, conhecidos como jogos, exigem algoritmos diferentes para solucioná-los. A IA faz amplo uso da área de Teoria dos Jogos para definir estes algoritmos.
Jogos vêm em múltiplos sabores. O tipo mais "simples" é como o xadrez. Dois jogadores, turnos alternados, estados totalmente observáveis, soma zero (i.e. ou um jogador ganha ou se empata), determinístico. Mas há jogos como pôquer, onde há múltiplos jogadores e os estados são parcialmente observáveis (você não sabe as cartas dos oponentes) ou Starcraft, onde múltiplos jogadores atuam em tempo real.
Mesmo jogos "simples" podem ser bem difíceis de resolver. Afinal, apenas em 1997 obtivemos sucesso em vencer um campeão mundial de xadrez, quando Gary Kasparov foi derrotado pelo Deepblue da IBM.
Por trás do Deepblue, e de essencialmente todos algoritmos para jogos deste tipo, está o algoritmo Minimax. A ideia do algoritmo é bastante simples: tratamos o problema de busca considerando as decisões do adversário, de forma a maximizar a pontuação que podemos obter (consideramos por tradição que uma vitória dá uma pontuação de +1, uma derrota -1 e um empate 0), enquanto assumimos que o adversário tenta minimizar nossa pontuação (já que, para ele, -1 é uma vitória).
Este é um bom momento para ler a Seção 6.4 e o restante do Capítulo 6 da nossa referência.
Como no caso dos algoritmos de busca tradicionais, a busca competitiva também esbarra nos limites da computação. O Minimax puro teoricamente pode jogar uma partida de xadrez perfeita, mas expandir toda a árvore é completamente inviável. O uso de heurísticas para reduzir a árvore de busca é semelhante ao uso que o A* faz mas, observe, esta heurística afeta diretamente a qualidade do algoritmo e é determinante se este irá vencer ou não (enquanto no A* afeta apenas o custo computacional para encontrar a solução). Bons jogadores Minimax fazem pelo menos duas coisas muito bem: utilizam boas heurísticas e são capazes de expandir a árvore significativamente (i.e. "olhar muitas jogadas à frente").
As heurísticas utilizadas pelo Deepblue foram fornecidas por mestres enxadristas, levantando a questão de se o Deepblue é realmente "inteligente" ou apenas segue o conhecimento obtido e codificado por esses especialistas. É bastante provável que o Deepblue seja capaz de vencer seus criadores, porém. Isso importa?
Por outro lado, o AlphaZero, uma variação em cima do AlphaGo (o primeiro algoritmo a vencer um campeão mundial de Go), é capaz de aprender heurísticas sozinho, apenas jogando contra si mesmo. Isso o torna mais inteligente que o Deepblue?
Jogos cativam a cultura popular ligada a IA por associarmos bons jogadores a inteligência. Construir algoritmos que joguem bem é um dos objetivos da IA desde seu princípio — Alan Turing tem um artigo delineando os princípios de um jogador de xadrez, por exemplo. Ainda que jogos tradicionais sejam bons benchmarks para a área, as técnicas desenvolvidas neste contexto são úteis para IAs que precisam conviver com pessoas ou outras IAs que possuem objetivos conflitantes.
