I  A resposta de ontem

Dois inventores e nenhum empate

Piet Hein, poeta, matemático e designer dinamarquês, apresentou o jogo a estudantes do instituto de Niels Bohr, em Copenhague, e o publicou no jornal Politiken em 26 de dezembro de 1942. O nome original era Polygon, e o jornal passou a vender blocos de folhas com o tabuleiro impresso.

Hein queria um jogo com quatro qualidades: regra curta, partida que sempre termina com vencedor, vantagem para quem pensa melhor e duração razoável. O Polygon cumpria as quatro e virou passatempo de café na Dinamarca ocupada pela Alemanha.

Seis anos mais tarde, John Forbes Nash Jr., estudante de doutorado em matemática na Universidade de Princeton, chegou ao mesmo jogo sem conhecer o dinamarquês. Os colegas jogavam na sala comum do prédio Fine Hall e chamavam o tabuleiro de Nash, ou simplesmente de John.

Foi Nash quem demonstrou, em 1948, que o primeiro jogador tem estratégia vencedora. Décadas depois, em 1994, ele dividiria o Nobel de Economia por outro trabalho, sobre equilíbrio em jogos com vários participantes.

O nome Hex veio da fábrica de brinquedos americana Parker Brothers, que lançou o tabuleiro em 1952. O jogo ganhou público grande em julho de 1957, quando Martin Gardner o apresentou na coluna de jogos matemáticos da revista Scientific American.

Por que ninguém empata

Pense nas peças vermelhas como água e nas azuis como pedras de um dique. A água vermelha quer escorrer de uma margem vermelha à outra.

Se as pedras azuis formam um muro contínuo cruzando o tabuleiro, a água para. Só que um muro azul contínuo, de margem azul a margem azul, é exatamente a conexão que dá a vitória ao azul.

Se o muro tem qualquer brecha, a água vermelha passa por ela e liga as margens vermelhas. Não há terceira hipótese: ou o muro existe, ou a passagem existe.

O hexágono faz o argumento funcionar. Cada casa encosta em 6 vizinhas, e em cada canto se encontram exatamente 3 casas. Num tabuleiro de quadrados, duas diagonais podem se cruzar sem se tocar, e os dois lados ficam bloqueados ao mesmo tempo; no Hex, esse cruzamento não acontece.

Em 1979, o matemático americano David Gale publicou na revista American Mathematical Monthly o artigo The Game of Hex and the Brouwer Fixed-Point Theorem (O jogo de Hex e o teorema do ponto fixo de Brouwer). Ele mostrou que a impossibilidade do empate equivale a um teorema clássico da topologia (o ramo que estuda formas contínuas): toda deformação contínua de um disco sobre ele próprio deixa ao menos um ponto parado.

II  O Enigma do dia

O lance a mais que nunca atrapalha

Dá pra resolver com papel e lápis. Desenhe 4 hexágonos em losango: duas casas em cima, duas embaixo, a fileira de baixo deslocada meia casa para a direita.

A primeira pista vale para o tabuleiro pequeno. Conte quantas vizinhas cada casa tem. Duas casas tocam as outras três; duas tocam só duas.

A segunda pista vale para a peça a mais. No Hex, peça nenhuma se move e nenhuma é capturada. Pergunte se existe alguma posição em que uma peça sua ajude o adversário.

A terceira pista vale para o argumento final. Imagine que o segundo jogador tenha um plano perfeito, escrito num papel. O primeiro jogador pode ler o papel?

A quarta pista: se os dois jogadores tivessem planos perfeitos ao mesmo tempo, cada um venceria o outro na mesma partida. Procure a contradição.

Onde o raciocínio escorrega

A primeira armadilha é abrir num canto qualquer do tabuleiro de 2 por 2. Dois cantos tocam só duas casas, e o adversário fecha a passagem com uma peça.

A segunda é achar que uma peça mal colocada pode virar obstáculo para o próprio dono. Ela pode ser inútil, mas nunca bloqueia caminho de quem a pôs.

A terceira é esquecer o empate. Sem a garantia de que alguém sempre vence, a contradição prova apenas que o segundo não vence, e não que o primeiro vence.

Responda por escrito: a casa de abertura no 2 por 2, o motivo de a peça extra não atrapalhar e o argumento contra o segundo jogador.

III  Sequência

O roubo de estratégia de Nash

No 2 por 2, o primeiro jogador abre numa das duas casas que tocam as outras três. Ela encosta nas duas casas da margem oposta, e o adversário só consegue bloquear uma. A peça a mais nunca atrapalha porque no Hex mais peças só abrem caminhos. O argumento de Nash fecha em quatro passos.

1. Suponha que o segundo jogador tenha uma estratégia vencedora.

2. O primeiro joga uma peça qualquer e, dali em diante, finge ser o segundo, seguindo a estratégia dele lance por lance.

3. Se a estratégia mandar jogar na casa onde já está a peça extra, ele joga em outra casa livre; a peça extra continua ajudando ou fica neutra.

4. Então o primeiro também vence, e os dois não podem vencer a mesma partida. Como o empate não existe, alguém tem estratégia vencedora, e só sobra o primeiro.

A prova não diz em que casa abrir. Ela garante que existe um plano, e só. No 11 por 11, o número de partidas possíveis é grande demais para ser percorrido.

Em 1981, o pesquisador alemão Stefan Reisch provou que decidir quem vence uma posição de Hex num tabuleiro de tamanho qualquer pertence à classe PSPACE-completa (grupo de problemas que, até onde se sabe, exigem cálculo que explode conforme o tabuleiro cresce). O resultado explica por que o computador avança devagar.

Na Universidade de Alberta, no Canadá, o grupo de Ryan Hayward resolveu os tabuleiros menores. Em 2009, Philip Henderson, Broderick Arneson e Hayward resolveram todas as aberturas do 8 por 8. Em 2013, Jakub Pawlewicz e Hayward provaram que abrir na casa central do 9 por 9 vence.

Para tirar a vantagem de quem começa, os torneios usam a regra da troca: depois do primeiro lance, o segundo jogador pode ficar com aquela peça como se fosse dele. Quem abre, então, escolhe de propósito uma casa nem forte nem fraca.

A Sequência é o placar de quem fecha sozinho. Um ponto por enigma resolvido antes de conferir a solução, e o placar zera quando você espia fora da hora.

“Em que casa você abriria no 11 por 11?”

Teste hoje: desenhe um Hex de 5 por 5, jogue 6 partidas com alguém e anote quem venceu cada uma, alternando quem começa. Nas partidas em que o primeiro abre na casa central, conte as vitórias dele: o esperado é que ele vença quase todas.

missão de hoje

Segundo o texto, em que ano Nash provou que o primeiro jogador tem estratégia vencedora no Hex?

Veja o ranking de quem mais acerta →

Como foi a edição de hoje?

Qual edição você quer ver amanhã?

Voto aberto até 09/10, 15h30

Civilizações Perdidas

Às 20:20 na sua caixa: o capítulo do dia sobre um império que nasceu, prosperou e colapsou. E o que esse ciclo revela sobre o presente.

Quero receber →