HomeO Gambito da Rainha e a complexidade
Em 2020, o mundo redescobriu a paixão pelo xadrez após o grande sucesso da minissérie da Netflix, O Gambito da Rainha. O enredo conta a história de uma jogadora de xadrez altamente habilidosa em seu caminho de sucesso. Durante sua evolução, o público consegue ver o quão complexo um único movimento pode ser e as repercussões que cada um pode ter. Mas quão difícil pode ser um jogo de tabuleiro 8x8?
A estrutura do jogo e um conjunto claro de regras são atraentes para profissionais de matemática aplicada. Essas características transformaram o xadrez em um pano de fundo clássico para muitos estudos de caso, especialmente em teoria dos jogos e otimização combinatória.
O primeiro campo busca entender as interações entre jogadores racionais, onde cada um quer maximizar seu ganho. O ponto culminante desse esforço é saber qual dos três resultados possíveis de uma partida (vitórias das brancas, vitórias das pretas ou empate) ocorre se os dois jogadores jogarem perfeitamente. Atualmente, os especialistas estão longe de saber as respostas, mesmo quando apoiados pelos melhores supercomputadores. É possível imaginar sua complexidade comparando-o a outro jogo 8x8, o damas, que foi resolvido em 2007 [1]. Este jogo mais simples levou quase 28 anos para ser desvendado enquanto se investigava as mais de 5 x 1020 (500 bilhões de bilhões) de posições possíveis no tabuleiro.
O segundo caso é ilustrado pelo Problema do Cavalo. Ele consiste em encontrar uma sequência de movimentos que permita ao cavalo visitar todas as casas do tabuleiro exatamente uma vez.
Figura: Uma solução para o Problema do Cavalo
Para o tabuleiro 8x8 clássico, o problema foi resolvido. Existem 19 x 1015 (19 milhões de bilhões) de caminhos dirigidos possíveis [2]. Isso está longe de qualquer estimativa que alguém pudesse adivinhar apenas olhando para o tabuleiro e já tendo dificuldade em encontrar apenas um caminho viável!
Ser um mestre do xadrez exige habilidades analíticas extraordinárias, já que o jogador tem que prever muitos cenários com antecedência. Podemos erroneamente pensar que existe um número “limitado” de jogos e que, depois de alguns anos, você saberá como proceder em uma determinada situação. Novamente, a percepção está longe da realidade. Um jogo de xadrez tem, em média, 80 rodadas e cerca de três movimentos sensatos (significativos) em cada rodada, o que gera cerca de 1040 jogos sensatos possíveis. Isso significa muito mais do que seria possível para toda a população do planeta jogar todos os dias, mesmo desde a formação da Terra!
Esses exemplos destacam a diferença de magnitude entre a complexidade real de um problema e a percepção que podemos ter dele. A sociedade testemunhou muitas vezes em que a Inteligência Artificial (IA) derrotou os grandes mestres do jogo, em partidas como Deep Blue x Kasparov e Watson x Ken Jennings. Isso cria uma falsa sensação de que todo problema formulado matematicamente pode ser resolvido em apenas alguns minutos por uma máquina. Os avanços no processamento de dados, como computação quântica e GPGPU, aumentaram significativamente as capacidades de resolução dos computadores. No entanto, dado o número de soluções possíveis, ainda contamos com a criatividade das pessoas para construir algoritmos eficientes para resolver problemas complexos.
References
[1] Schaeffer, J.; Burch, N.; Bjornsson, Y.; Kishimoto, A.; Muller, M.; Lake, R.; Lu, P. & Sutphen, S. (2007), 'Checkers Is Solved', Science , 1144079+.
[2] The On-Line Encyclopedia of Integer Sequences - OEIS Foundation Inc. (2020).
Coautor: Emmanuel Marchal - Managing Partner na Cassotis Consulting