Hex com Matemática

Hex é um jogo de tabuleiro jogado em uma grade hexagonal, teoricamente de qualquer tamanho e diversas formas possíveis, mas tradicionalmente como um losango 11x11. Outras dimensões populares são 13x13 e 19x19 como resultado da relação do jogo com o antigo jogo asiático Go. De acordo com o livro A Beautiful Mind, John Nash (um dos inventores do jogo) defendeu 14x14 como o tamanho ideal.

O jogo foi inventado pelo matemático dinamarquês Piet Hein, que o introduziu em 1942 no Instituto Niels Bohr. Foi independentemente re-inventado em 1947 pelo matemático John Nash na Universidade de Princeton.

Em 1952, a Parker Brothers comercializou uma versão. Chamaram sua versão "Hex", e o nome pegou. Várias versões deste jogo já foram publicadas pelo Mundo.

O jogo nunca pode terminar em um empate, um fato provado por John Nash: a única maneira de evitar que o seu adversário forme um caminho conectado, é também formar um caminho. Em outras palavras, Hex é um jogo determinado.

Quando os lados da grelha são iguais, o jogo favorece o primeiro jogador. Um padrão não-construtivo do argumento do roubo de estratégia prova que o primeiro jogador tem uma estratégia vencedora da seguinte forma:

Desde de que Hex é um recurso finito, um jogo de informação perfeita que não pode terminar em empate, o primeiro ou o segundo jogador devem possuir uma estratégia vencedora. Note que um movimento extra para qualquer jogador em qualquer posição, somente pode melhorar a posição do jogador. Portanto, se o segundo jogador tem uma estratégia vencedora, o primeiro jogador poderia "roubar" isso, fazendo um movimento irrelevante, e seguir a estratégia do segundo jogador. Se a estratégia sempre chamada para a movimentação no tabuleiro já estiver escolhida, o primeiro jogador pode então fazer uma outra medida arbitrária. Isto assegura uma vitória do primeiro jogador.

1974

Pode-se tentar compensar a desvantagem do segundo jogador, tornando os lados do segundo jogador próximos, jogando em um paralelogramo, em vez de um losango. No entanto, usando uma estratégia de emparelhamento simples, esta forma tem sido comprovada resultar em uma vitória fácil para o segundo jogador.

Hex é um jogo de ligação, e pode ser classificado como um jogo de maker-breaker, um tipo particular de jogo de posicionamento.

John Nash provou em 1952 que um jogo de Hex não pode terminar em empate, e que para um tabuleiro simétrico existe uma estratégia vencedora para o jogador que faz o primeiro movimento (com o argumento do roubo de estratégia). No entanto, o argumento é não-construtivo: ele só mostra a existência de uma estratégia vencedora, sem descrevê-la explicitamente. Encontrar uma estratégia explícita tem sido o principal tema de pesquisa desde então.

Uma estratégia vencedora explícita com um argumento de emparelhamento existe em tabuleiros não-simétricos nxm, que deixa apenas tabuleiros simétricos nxn como o centro de interesse.

Em 1981, Stefan Reisch provou que Hex generalizado em um tabuleiro nxn é PSPACE-completo. Na teoria da complexidade computacional, é amplamente conjecturado que problemas PSPACE-completos não podem ser resolvidos com algoritmos (polinomiais) eficientes. Este resultado limita a eficiência dos melhores algoritmos possíveis quando se consideram os tabuleiros de tamanho arbitrário, mas não descarta a possibilidade de computar estratégias explícitas sobre pequenos tabuleiros de um determinado tamanho.

Em 2002, Yang Jing, Simon Liao e Mirek Pawlak encontraram uma estratégia explícita de vitória para o primeiro jogador em tabuleiros de Hex de tamanho 7x7. Eles estenderam o método para os tabuleiros de 8x8 e 9x9 em 2003.

Em 2009, Philip Henderson, Broderick Arneson e Ryan B. Hayward concluíram a análise do tabuleiro de 8x8 com um exame cuidadoso no computador, resolvendo todos os inícios possíveis. A mesma equipe tem resolvido mais inícios 9x9, mas alguns deles ainda são desconhecidos.

O determinismo de Hex tem outras consequências matemáticas: ele pode ser usado para provar o Teorema do Ponto Fixo Bidimensional de Brouwer, como David Gale mostrou em 1979,e o determinismo de variantes de dimensões superiores.

Interessado em estudar matematicamente o Hex ou é melhor aproveitar os jogos sem pensar na teoria por trás deles?