O cientista da computação que encontra lições de vida em jogos

Escolha Shang Hua Teng, a ciência da computação teórica nunca foi puramente teórica. Agora com 58 anos, Teng é professor de ciência da computação na University of Southern California e duas vezes vencedor do Prêmio Gödel, um prêmio anual que reconhece trabalhos teóricos inovadores. Mas ele frequentemente se esforça para conectar essa teoria abstrata à vida cotidiana de maneiras práticas e lúdicas.

Nascido em Pequim na véspera da Revolução Cultural Chinesa, Teng veio para os Estados Unidos para planejar uma pós-graduação para estudar arquitetura de computadores, mas logo mudou de direção para se concentrar em uma teoria matemática mais abstrata. Ele recebeu seu doutorado na Carnegie Mellon University em 1991 por provar um teorema sobre a melhor forma de particionar gráficos – teias de pontos, ou nós, conectados por linhas ou arestas.

Embora teórico, o trabalho tinha aplicações práticas – e muitas vezes, ele descobriu, aplicações práticas levavam a novos insights teóricos. Durante uma bolsa de verão da NASA em 1993, Teng se juntou a uma equipe de simulação de dinâmica de fluidos usando métodos de “elementos finitos”, que modelam estruturas complexas como montagens de muitas peças minúsculas. Essas montagens podem ser tratadas como gráficos, e a tarefa de Teng foi adaptar o método de particionamento de sua pesquisa de pós-graduação a esse novo cenário. Mas ele ficou curioso sobre a técnica de particionamento que a equipe da NASA havia usado anteriormente e começou a investigar sua estrutura matemática subjacente junto com seu colega cientista da computação. Daniel Spielman, agora professor de ciência da computação na Universidade de Yale. Esse projeto de pesquisa conjunto deu início a uma colaboração de décadas que lhes rendeu os dois Prêmios Gödel.

Não foi a única vez que ele viu uma ligação profunda entre teoria e prática. “Cada vez, essas coisas aparentemente totalmente práticas tinham essa bela matemática por trás delas”, disse Teng.

Mais recentemente, Teng voltou sua atenção para a bela matemática por trás de jogos como jogo da velha, xadrez e Go. Nesses jogos “combinatórios”, não há elemento de sorte e ambos os jogadores sempre sabem tudo sobre o estado do tabuleiro. No entanto, os jogos combinatórios permanecem desafiadores porque o número de maneiras pelas quais um jogo pode se desenrolar pode ser estonteantemente grande.

Os pesquisadores da teoria dos jogos gostam de generalizar esses jogos para tabuleiros cada vez maiores - ampliando o jogo da velha de 3 por 3 quadrados para n-A-n, por exemplo — e quantificar a dificuldade de determinar qual jogador vencerá dado algum estado inicial do tabuleiro. As diferentes respostas possíveis classificam os jogos no mesmo “classes de complexidade” que surgem ao longo da ciência da computação teórica.

Uma classe de complexidade famosa atende pelo nome prosaico P, para “tempo polinomial”, e contém o tipo de problemas que podem ser resolvidos em um período de tempo razoável, grosso modo. Problemas na igualmente famosa classe NP podem levar um tempo excessivo para serem resolvidos, mas suas soluções são fáceis de verificar. Para problemas em outra classe de complexidade, denominada PSPACE, nem mesmo essa verificação eficiente é garantida. Quando os pesquisadores consideram a “lógica profunda” dos jogos para dois jogadores – “se você fizer X, e depois se eu fizer Y, e depois se você fizer Z” e assim por diante – eles geralmente se veem falando sobre o PSPACE. Mas, como Teng ajudou a provar, a matemática dos jogos combinatórios nem sempre é direta.

Quanta conversou com Teng recentemente para discutir seu caminho para a ciência da computação, a matemática por trás dos jogos de tabuleiro e a influência de seu pai. A entrevista foi condensada e editada para maior clareza.

Como foi estudar na China?

Nasci um pouco antes da Revolução Cultural e meu pai era chefe do departamento de engenharia civil de uma universidade. Quando a revolução aconteceu, ele estava em cativeiro no campus. Então todo o campus foi enviado para o interior.

Eu costumava coletar lixo para vender até praticamente terminar o ensino fundamental e, de repente, a China mudou. Se você estudasse, poderia entrar na faculdade, e não tínhamos outra perspectiva de ter um emprego fixo. Acordei e disse: “Preciso estudar”.

Como você escolheu a ciência da computação?

Eu queria estudar biologia depois do ensino médio. Não sei por que, mas meu pai não gostou muito disso. Eu estava indo bem em matemática e ele me perguntou se eu queria fazer matemática. Eu disse não. [Risos] E então ele disse: “Sabe, há uma nova disciplina chamada ciência da computação, e é muito boa”. De alguma forma, ele me incentivou a me formar em ciência da computação.

A educação naquela época era muito básica. Não éramos expostos à maioria das coisas e a ciência da computação nem era um departamento; era uma especialização em engenharia elétrica. Mas, por sorte totalmente aleatória, fomos treinados como estudantes de matemática em cálculo, e aprendi algumas coisas que acabaram sendo úteis para me tornar um teórico. Sem isso eu provavelmente não teria nenhuma chance de passar. Hoje em dia, as crianças são muito mais talentosas: desde o ensino médio, elas são matemáticas mais talentosas do que eu quando vim para este país.

Como essas lacunas em seu conhecimento afetaram sua experiência na pós-graduação?

Um dia [meu conselheiro, Gary Miller] descobriu que nunca tinha ouvido falar de NP. Foi em uma discussão. Ele disse: “Este problema parece NP-difícil”. Eu disse: “Uh-huh”. Ele disse: “Você não acredita em mim?” E então ele começou a prová-lo e, no meio do caminho, virou-se bruscamente para mim, porque eu estava sentado lá, e disse: "Você sabe o que é NP-difícil?" Eu disse não.

Achei que era meu último dia trabalhando com ele, mas ele continuou e me contou a definição. Ele disse: “Se você não sabe, não importa, contanto que você seja capaz de pensar”. Ele teve um tremendo impacto sobre mim.

Você é principalmente um teórico, mas ao longo de sua carreira fez incursões na indústria. Como esse trabalho prático se conectou à sua pesquisa teórica?

Na minha tese desenvolvi alguns métodos geométricos para particionar grafos. Consegui mostrar que essa família de métodos geométricos fornecia cortes comprovadamente bons para gráficos de elementos finitos.

Por recomendação do meu mentor, comecei a dar palestras na NASA e na Boeing Aerospace. Na Boeing, lembro que o modelo 3D de uma das asas já tinha quase um milhão de elementos - eles não podiam nem carregar isso em uma máquina. Então, eles queriam dividir esse gráfico em diferentes componentes, colocá-los em diferentes máquinas com cargas computacionais semelhantes e minimizar a comunicação. É por isso que matematicamente a fórmula é um corte gráfico.

Na ciência da computação teórica, muitas vezes os princípios matemáticos subjacentes permanecem inalterados, mesmo quando a aparência do problema muda drasticamente, da otimização para a teoria dos jogos. Quando você está fazendo a pesquisa, não parece uma mudança drástica.

Falando em teoria dos jogos, vi que você ajudou a criar um jogo de tabuleiro. Como isso aconteceu?

Ah, eu amo jogos de tabuleiro! Existem belas conexões com a teoria da complexidade. Mas principalmente eu sou o aluno dos meus alunos.

Eu estava dando uma palestra na Universidade de Boston sobre um belo teorema discreto chamado lema de Sperner. É muito simples em uma dimensão. Você tem um segmento de linha onde uma extremidade é vermelha e a outra é azul. Você o divide em subsegmentos [com nós em ambas as extremidades] e colore cada novo nó de vermelho ou azul. Então [não importa como você os colore] sabemos que deve haver um segmento que tenha ambas as cores.

Em duas dimensões, é muito fascinante. Você tem um triângulo e agora tem três cores: um canto é vermelho, um é azul e um é verde. Você divide este triângulo em triângulos menores, então as arestas são quebradas em segmentos. Cada borda externa segue a regra unidimensional: os nós só podem usar as cores das duas extremidades. Dentro do triângulo, você pode fazer as três cores do jeito que quiser. O lema de Sperner diz que de qualquer maneira que você o divide, se você fizer essa coloração, deve haver um triângulo que tenha todas as três cores.

Kyle Burke era meu aluno, trabalhando em análise numérica na época. Ele veio ao meu escritório e disse que poderia haver um belo jogo de tabuleiro do lema de Sperner: dois jogadores pintam iterativamente um tabuleiro e quem induzir um triângulo de três cores perderá o jogo. Os melhores jogos de tabuleiro têm vencedores em vez de empates e, aqui, claramente alguém vencerá. Porque? Porque o lema de Sperner!

Liguei para meu amigo David Eppstein, de Irvine, para falar sobre o que torna um bom jogo de tabuleiro. Ele disse: “Um bom jogo tem regras simples e um belo tabuleiro, e tem que ser PSPACE-hard”. Porque se você pudesse resolvê-lo em tempo polinomial, um computador venceria você o tempo todo.

Então passamos por esses critérios. Kyle disse: "Este jogo é simples?" Eu disse: “Sim, é uma frase!” Ele disse: “Este jogo é colorido?” Eu disse: “By design!” Então ele disse: “Se eu provar que é PSPACE-difícil, posso obter um Ph.D.?” Eu disse que sim, e ele fez. Existem muitas facetas diferentes de seu teorema. Ele revela certas coisas sobre pontos fixos, que são um conceito muito bonito em matemática.

Posso jogar em qualquer lugar?

Está disponível, com alguns ajustes, online.

Quais jogos você gosta de jogar?

Sou um teórico dos jogos. [Risos] Eu brinco um pouco com minha filha, mas não cresci jogando. Ao contrário dos meus alunos, que jogaram a vida toda.

Que outro trabalho você fez na matemática dos jogos de tabuleiro?

Nós tinhamos um papel recentemente sobre uma questão em aberto: se você colocar dois jogos resolvíveis em tempo polinomial juntos, lado a lado, isso os tornaria PSPACE-difíceis? A cada jogada você só pode jogar uma delas. Isso é chamado de soma de jogos.

O que significa colocar dois jogos juntos?

No antigo jogo Go, quando você coloca pedras suficientes, você obtém muitas arenas separadas, então, de certa forma, você está jogando uma soma de jogos. Você tem que se preocupar com este canto e aquele canto. Você quer ganhar tudo, mas isso não significa que você tem que ganhar todas as partes.

É filosoficamente interessante, certo? É como se você tivesse uma guerra, com muitas batalhas, mas sua atenção é finita. A qualquer momento, você só pode tomar uma única decisão em um dos campos de batalha, e seu oponente pode responder ou dobrar em algum outro campo de batalha. Eu estava tentando explicar isso ao meu pai. Quando você joga uma soma de jogos, isso realmente significa: Como você perde estrategicamente?

Provamos isso para dois jogos, mas você pode colocar três jogos juntos e o teorema ainda é verdadeiro: três jogos de tempo polinomial juntos podem se tornar PSPACE-difíceis.

Desde que ele empurrou você para a ciência da computação, como seu pai reagiu ao trabalho diferente que você fez ao longo dos anos?

Ele sempre me perguntava: “Por que você está fazendo isso?” Trabalhando na teoria, muitas vezes você fica anos sem resultado, e ele foi entendendo isso aos poucos. No começo eu poderia falar sobre o método de elementos finitos - eles ensinam isso na engenharia civil também. Mas eu não conseguia descobrir como falar sobre essa matemática recreativa.

Então pensei em uma expressão derivada desse famoso romance chinês chamado Romance dos Três Reinos. Um dos personagens, Zhuge Liang, era quase um estrategista perfeito, e a expressão diz: “Três engraxates são melhores do que Zhuge Liang”. É usado dessa maneira alegre para dizer que três pessoas medianas podem ser perfeitas quando juntam suas cabeças. Mas quando você olha para a história desse idioma, as coisas eram pronunciadas de maneira diferente em diferentes regiões, e “engraxador de sapatos” tinha o mesmo som de “general de campo”. Então diz: “Três generais de campo juntos são melhores do que este estrategista perfeito”.

Eu disse ao meu pai que é exatamente o teorema que provamos com a soma dos jogos. Os generais de campo representam [algoritmos para resolver] jogos de tempo polinomial: Em cada campo de batalha, eles sabem como vencer. Mas a parte difícil é saber quando perder, não como vencer cada um dos jogos componentes. Se alguém pode jogar esse jogo difícil, eles realmente são os melhores estrategistas. Os generais de campo não tomam essas decisões lógicas profundas, mas, de alguma forma, se você as juntar bem, elas não serão piores do que esse estrategista perfeito.

Eu disse ao meu pai: “Finalmente percebi esse teorema matemático que é equivalente a uma de nossas famosas expressões idiomáticas!” Ele tinha 94 anos na época, muito afiado, e disse: “Essa é uma boa tentativa”. Eu não o convenci muito. Essa foi minha última conversa técnica com ele; alguns meses depois ele faleceu. Sempre que penso em explicar meu trabalho, esse é meu destaque.