Ciências

O Jogo de Hex

por Felipe Pait

O jogo de Hex, inventado nos anos 1940 independentemente por Piet Hein em Copenhagen e por John Nash em Princeton, é disputado num tabuleiro em forma de losango, composto por casas hexagonais. O tabuleiro começa vazio, e cada um dos dois jogadores ocupa alternadamente uma das casas, com o objetivo de fazer uma ligação ininterrupta entre seus 2 lados opostos. Uma vez colocadas no tabuleiro, as pedras não se movem nem são retiradas.

Os tamanhos mais comuns são 11 x 11 e 13 x 13. Em tabuleiros menores, são conhecidas estratégias de vitória garantida para o primeiro jogador; e em tabuleiros maiores o jogo se torna demorado demais para um simples divertimento. Por sua invenção recente, o Hex não tem a literatura extensa dos jogos mais tradicionais, como o xadrez ou o Go, sobre o qual escrevemos no mês de julho. Mesmo as cores das pedras não são fixas: na primeira ilustração abaixo evitamos o preto e o branco, ou o vermelho e o azul que hoje adquiriram conotações políticas, e optamos por representar as pedras colorindo os hexágonos com as patrióticas cores verde e amarelo. Colorimos também os lados opostos verdes e amarelos para facilitar a visualização dos objetivos de cada jogador.

Mesmo que não exista a captura das pedras como em outros jogos de tabuleiro, o Hex não é um jogo cooperativo. Pelo contrário, a única forma de um jogador evitar a derrota, impedindo a conexão entre os lados do adversário, é ganhar o jogo completando a ligação entre seus próprios lados. Se no Hex não existem batalhas entre as pedras, também não existe empate.

Por que não? Considere que uma partida de Hex terminou, e todas as casas foram ocupadas com pedras das 2 cores. Vamos agora dividir as casas amarelas em 3 conjuntos: as conectadas ao lado direito amarelo, as conectadas ao lado esquerdo amarelo, e as que não se conectam a nenhum dos 2 lados. Estas últimas são irrelevantes para o resultado do jogo; podemos igualmente supor que elas estejam vagas. Então há 2 alternativas: ou os 2 conjuntos de casas amarelas são conectados, e as amarelas venceram o jogo, ou não são.

Vamos traçar por fora do tabuleiro uma curva unindo os lados verdes, como ilustrado na segunda figura. (As casas vazias na figura não são relevantes para o raciocínio a seguir; apenas importam aquelas ocupadas por alguma das cores.) Se continuarmos esse caminho para dentro do tabuleiro passando apenas por casas verdes, há 2 possibilidades: ou as verdes conseguiram conectar seus lados opostos, ou então não existe conexão.

Nesse momento para completar nossa análise devemos recorrer à matemática e lembrar do teorema de Jordan, que afirma que toda curva fechada, que não cruza a si própria, divide o plano em 2 pedaços: a parte interna e a parte externa à curva fechada. Trata-se de afirmação tão óbvia quanto difícil de provar. Pois bem: se as verdes conseguiram conectar seus lados opostos, então somos capazes de traçar uma curva fechada, passando por fora do tabuleiro, que separa as casas amarelas entre internas e externas. Mas se não houver conexão entre as casas verdes, e portanto não for possível traçar uma curva fechada separando os 2 conjuntos de casas amarelas, então os conjuntos estão unidos, e nesse caso vencem as amarelas. Um dos jogadores deve portanto vencer.

Será possível transformar esse argumento razoável, porém informal, numa demonstração rigorosa capaz de satisfazer às exigências da matemática? Esta é uma pergunta além do conhecimento do autor dessa coluna, assim como a demonstração do teorema da curva fechada de Jordan. É suficiente, em casos como esses, confiar no trabalho de especialistas que demonstraram tanto esse último teorema como o fato de que o jogo de Hex termina sempre com a vitória de um dos lados.

Quão difícil é na prática o jogo de Hex? Considerando um tabuleiro da mesma dimensão de um tabuleiro de Go, a cada posição o número de jogadas em Hex é igual ao número de jogadas do jogo de Go, pois em ambos a jogada consiste em ocupar uma das casas vazias. Igualmente, o número de posições possíveis é semelhante, pois cada casa pode estar ocupada por pedras de uma cor, da outra cor, ou desocupada. A única diferença entre os jogos é devida à possibilidade de captura, que inexiste nas regras do Hex. Desta forma mesmo em tabuleiros da dimensão usual, o número de posições admissíveis no Hex é de 3 elevado à potência 121, e o número de partidas possível da ordem de 121 fatorial, muito superior ao número de partidas possíveis de xadrez.

Formalmente tudo isso é verdade. Porém, quem já jogou os Hex sabe que na prática o jogo é mais intuitivo e fácil de aprender do que o xadrez. A literatura do Hex é muito menos vasta que a dos jogos tradicionais, e desconheço uma argumentação clara a respeito das razões para tal discrepância entre a dificuldade formal e a real do jogo. Um dos motivos é que a inexistência de captura de peças diminui as variações possíveis e simplifica o estudo do Hex. Talvez mais importante seja o fato de que a relação entre a localização das pedras no Hex e a situação do jogo se presta a uma análise intuitiva, visual, geométrica, que dispensa o cálculo exaustivo das alternativas. As pedras têm uma “ação à distância”, e é possível visualizar que 2 ou mais pedras poderiam ser conectadas sem a necessidade de calcular as jogadas necessárias para efetuar as conexões entre elas.

Existem então fatos mais ou menos óbvios porém difíceis de provar, assim como existem resultados surpreendentes cuja demonstração é relativamente simples. Qual a forma de raciocínio mais eficaz para a solução de problemas, a análise formal ou a intuição? Voltaremos a essa questão num artigo futuro.

Felipe Pait

Felipe Pait é professor no Laboratório de Automação & Controle da Escola Politécnica da Universidade de São Paulo. Estudou engenharia elétrica na USP e na Universidade Yale.