Kasparov X Deep Blue - Uma Abordagem Computacional 30 anos depois

Em 1997, houve um confronto que tem uma importância grande para a humanidade, longe dos campos de batalha e dos discursos políticos, confronto onde um super computador enfrentava aquele que até o momento era considerado por muitos como o maior enxadrista da história, de um lado um computador de milhões de dólares e do outro uma mente genial. Kasparov contra Deep Blue além de ser um marco na história da computação também o era para a humanidade, pois ao seu desfecho o maior enxadrista do mundo já não era humano.

De um lado do ringue, nascido na antiga União Soviética, se tornou campeão mundial aos 22 anos – até o momento era o mais jovem da história – ao vencer, em um confronto marcado por questões políticas, o também soviético Anatholy Karpov, conhecido por seu estilo posicional e por ser um grande estrategista. Kasparov que manteve seu título por quase 20 anos, conhecido por sua grande preparação de aberturas(formas de desenvolver as primeiras jogadas) e um estilo de jogo agressivo que buscava a “iniciativa”, que é quando após fazer um lance obriga o outro jogador responder e colocando-o na defensiva.

Do outro, um supercomputador de milhões de dólares, criação do cientista da computação Feng-hsiung Hsu, que durante seu doutorado nos Estados Unidos passou a estudar engines de xadrez — programas especializados em jogar xadrez -. Após ingressar na IBM, dedicou-se ao projeto de construir uma máquina capaz de derrotar o campeão mundial

O primeiro confronto ocorreu em 1996 e terminou com uma vitória convincente de Kasparov. O campeão aceitou uma revanche no ano seguinte, e é justamente esse segundo confronto — em especial a primeira das seis partidas — que será analisado neste texto.

A Matemática por trás das Engines:

O Xadrez é considerado um jogo computacionalmente intratável e durante muito tempo se acreditou que computadores não poderiam jogar o jogo. Mas o que isso quer dizer? Para cada lance feito, o número de possibilidades de movimento cresce exponencialmente, chegando ao número de Shannon que tem um valor inimaginavelmente grande de 10^120 lances.

Essa crença refutada pela história, vinha da ideia da “explosão de combinatória” que é quando o número de combinações de um experimento matemático cresce de forma muito rápida e da ideia que um computador teria que “avaliar” todos os lances. Diante dessa dificuldade surgiu uma ideia: Os computadores deveriam em vez de avaliar todos os exemplos, procurar apenas aquelas que faziam sentido.

Para isso, os engenheiros desenvolveram uma função de avaliação capaz de atribuir uma nota a cada posição do tabuleiro. Essa função era calibrada com base no conhecimento de mestres e na análise de milhares de partidas de alto nível, utilizando métodos estatísticos para ajustar a importância de fatores como material, segurança do rei, estrutura de peões e mobilidade.

Assim, o computador conseguia estimar quais posições eram mais favoráveis e direcionar sua busca para as variantes mais promissoras.
Em resumo, ela poderia encontrar os lances mais promissores, ao “atribuir notas” à lances e posições, fazendo ela “podar” linhas ruins ou perdedoras.(guarde esta informação)

Tática e Estratégia
Como um jogo estratégia, é esperado que o xadrez se baseie em planos. Planos de longo prazo são chamados de estratégia e os de curto prazo que miram uma vantagem imediata são chamadas de tática.

No caso o “longo prazo”, seria as desenvolver as peças, posicionando-as da forma mais “eficiente possível”, as tornando o mais ativas:
As torres atuam melhor quando trabalham juntas em colunas abertas;
Os bispos atuam melhor em diagonais longas, posições abertas e quando temos ambos no tabuleiro, de forma que cada um cubra as casas escuras ou brancas;
Os cavalos atuam melhor em posições fechadas pois podem “saltar” sobre as peças e quando apoiadas por um peão, que é chamado de base de operações;
A Dama é a peça mais poderosa de todas e é o coração do ataque, ela trabalha muito bem em conjunto com todas as outras peças;
O rei vale o jogo e só deve ser utilizado em finais;
E o peão? É a alma do jogo! Os peões limitam as ações das peças inimigas e podem definir o vencedor de uma partida.

Peças bem posicionadas ou ter peças a mais criam uma vantagem, no caso posicional ou material.

A Primeira Partida

Essa partida à primeira vista pode parecer estranha. Mesmo conduzindo as peças brancas, Kasparov joga de forma encolhida e defensiva, evitando complicações táticas imediatas e conduzindo o jogo para uma posição fechada, evitando o contato, muito diferente de seu estilo naturalmente agressivo. Essa escolha fazia parte de uma estratégia conhecida como tática anti-computacional. Na década de 1990, programas como o Deep Blue eram extraordinários em posições táticas, nas quais algoritmos de força bruta e o cálculo profundo encontravam rapidamente as melhores sequências de lances. Em posições fechadas, entretanto, os planos estratégicos de longo prazo tinham maior importância, exigindo que a função de avaliação do computador captasse nuances posicionais mais difíceis de quantificar. Além disso, ao escolher uma variante pouco comum, Kasparov buscava retirar o Deep Blue de seu livro de aberturas logo nas primeiras jogadas, obrigando-o a depender apenas de seus algoritmos de busca e avaliação.

Podemos pensar na “tática anti-computacional” de Kasparov como forçar o computador a jogar posições onde ele tinha mais dificuldade, posições fechadas e com poucas partidas de referência que faziam o Deep Blue sair de seu livro de aberturas mais cedo. E neste cenário, algoritmos de força bruta e algoritmos de busca perdiam eficiência devido à explosão de combinatória. Nesse cenário se sobressai as estratégias de longuíssimo prazo, aos poucos construir uma posição superior, acumulando pequenas vantagens e forçando o computador ao erro até o derrotar.

Após muitos lances sem contato entre as peças:

Kasparov permite que o computador tome sua torre com o bispo o que parece uma loucura: mesmo que tome o bispo de casas negras do Deep Blue, a torre é muito superior ao bispo. Isso era parte do plano. Computadores tem dificuldade de avaliar vantagens posicionais, sua função de avaliação tinha maior dificuldade para mensurar a compensação estratégica obtida por Kasparov, especialmente o avanço inevitável dos peões passados que viria logo em seguida, entrando em uma posição perdida.

Agora Kasparov tem dois peões passados e conectados(um peão apoia o outro), que inevitavelmente vão chegar ao fim do tabuleiro sendo coroados para uma dama e vencendo o jogo. Poucos lances depois, os engenheiros do Deep Blue jogaram a toalha e admitiram a derrota.

Apesar dessa vitória, Kasparov teve que trocar sua estratégia de jogo, pois era perigoso demais jogar em um estilo que não era o dele, esse estilo não era só “anti-computacional” mas também “anti-Kasparov”.
Entretanto, a vitória de Kasparov seria apenas temporária. O Deep Blue empatou a segunda partida e, ao final do confronto, venceu o match por 3½ a 2½. Pela primeira vez, um campeão mundial em atividade era derrotado por um computador em condições oficiais, um marco na história da computação e da inteligência artificial.