Hex (jogo)

Hex
Hex (jogo) Uma partida de Hex num tabuleiro 19x19.
Autor	Piet Hein, John Nash
Fabricante	Parker Brothers
Lançamento	1952
N.º de jogadores	2
Faixa etária	Acima de 4
Tempo de montagem	Nenhuma
Tempo de jogo	15 minutos (tabuleiro 11x11)
Complexidade	Baixa
Nível estratégico	Alto
Influência da sorte	Nenhuma
Habilidades	Tática, Estratégia, Posicionamento
BoardGameGeek	Hex (jogo)no BoardGameGeek

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.

História

Tabuleiro de Hex 11x11

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. Tornou-se conhecido na Dinamarca sob o nome de Polygon (embora Hein o chamou de CON-TAC-TIX); Nash disse a alguns jogadores que inicialmente chamou o jogo de Nash. De acordo com Martin Gardner, alguns dos alunos da Universidade de Princeton também se referiram ao jogo como John (de acordo com algumas fontes isso foi porque eles jogaram o jogo usando o mosaico do chão do banheiro). No entanto, de acordo com a biografia de Sylvia Nasar sobre John Forbes Nash, A Beautiful Mind, o jogo ficou conhecido como "Nash" ou "John" por conta de seu criador aparente. John Nash falou que pensou neste jogo, independente de Hein, durante seus anos de pós-graduação na Universidade de Princeton. Em 1952, a Parker Brothers comercializou uma versão. Chamaram sua versão "Hex", e o nome pegou.

Hex é um jogo de estratégia abstrata que pertence à categoria geral de jogos de conexão. Jogos de "conexão" incluem Omni, Y e Havannah. Todos estes jogos tem diferentes graus de semelhança com o antigo jogo asiático Go.

Regras

Configuração de vitória com o azul.

Cada jogador tem uma cor, vermelho e azul ou branco e preto sendo convencionais. Os jogadores se revezam colocando uma pedra da sua cor em uma única célula dentro do tabuleiro global de jogo. O objetivo é formar um caminho conectado de suas pedras que liga os lados opostos do tabuleiro marcados com suas cores, antes de seu oponente conecte os seus lados de forma semelhante. O primeiro jogador a completar a sua ligação ganha o jogo. Os quatro cantos de cada hexágono das bordas pertencem a ambos os lados adjacentes.

Uma vez que o primeiro jogador a mover-se em Hex tem uma vantagem distinta, a regra da torta geralmente é implementada por justiça. Esta regra permite que o segundo jogador escolha se quer trocar de posições com o primeiro jogador após o primeiro jogador fazer o primeiro movimento.

Estratégia

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.

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.

Pontes e conexões

O jogador vermelho não pode impedir o jogador azul de conectar A e C na próxima jogada.

Dois (grupos de) pedras são seguramente conectados se nada pode impedi-los de estar conectados, mesmo se o adversário tiver a próxima jogada. Um exemplo disto é a ponte. Sejam A, B, C e D os hexágonos que compõem um losango, com A e C sendo o par de não-conexão.

Para formar uma ponte, um jogador coloca as pedras em A e C, deixando B e D vazio. Se o adversário coloca uma pedra em B ou D, o hexágono restante pode ser preenchido para conectar-se as duas pedras originais em um único grupo. Esta estratégia é muito útil durante todo o jogo.

Caminhos

Dois grupos de pedras são ditos n-ligados se você pode conectá-los com segurança nos n movimentos (ou, mais precisamente, o número de movimentos que você deve fazer para conectar com segurança os dois grupos, menos o número de movimentos do seu adversário faz, é n). Pedras conectadas com segurança, tais como pedras adjacentes, são 0-conectadas. As pontes são também 0-conectadas. O menor n é, o melhor para você.

Um caminho consiste de dois (ou mais) grupos de pedras e um conjunto vazio de pontos, que é o conjunto de hexágonos vazios que são necessários para as conexões dadas. Por exemplo, o caminho da ponte compreende o grupo (membro único) de pedras em A e um outro grupo (membro único) de pedras em C. O conjunto vazio de pontos é feito sobre os hexágonos B e D. Para dois caminhos coexistirem e manterem o nível de conectividade que eles têm enquanto independentes, seu conjunto de pontos vazios não deve conter qualquer um dos mesmos hexágonos (caso contrário, o adversário poderia jogar lá).

Dois caminhos 1-conectados podem ser consolidados em conjunto, se os dois grupos de pedras que iniciam e terminam nele são os mesmos e os seus conjuntos de pontos vazios não se sobrepõem.

Modelos

Um conceito importante na teoria do Hex é o modelo. Os modelos podem ser considerados um tipo especial de caminhos 0-conectados onde um dos grupos de pedras é a borda que você está tentando se conectar.

Escadas

As escadas são sequências de movimentos forçados onde as pedras são colocadas em duas linhas paralelas. Elas podem ser consideradas modelos de borda normais e podem ser analisados utilizando a análise do caminho da mesma maneira que as pontes, os caminhos, e os modelos possíveis.

Teoria e provas

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 concluiram 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 de Brouwer bidimensional, como David Gale mostrou em 1979, e o determinismo de variantes de dimensões superiores, prova o teorema do ponto fixo em geral.

Variantes

Blockbusters

Hex teve uma encarnação como o tabuleiro de questões no programa televisivo de jogos Blockbusters. Para jogar um "movimento", os participantes tinham que responder a uma pergunta corretamente. O tabuleiro tinha 5 colunas alternadas de 4 hexágonos, o jogador solo podia se conectar de cima para baixo, em 4 movimentos, enquanto a equipe de dois jogadores podia se conectar da esquerda para a direita em 5 movimentos.

Os jogos de Y e Havannah

O jogo de Y é uma generalização de Hex na medida que qualquer posição sobre um tabuleiro de Hex pode ser representada como uma posição equivalente em um tabuleiro de Y maior.

O Havannah tem algumas semelhanças com Hex, mas as estruturas de vitória (objetivo do jogo) são diferentes.

Mind Ninja

Mind Ninja é outro jogo que é uma generalização do Hex, embora de forma bastante ampla. Como em Hex, dois jogadores competem para criar padrões que se excluem mutuamente, preenchendo as células de uma superfície de azulejos. Em Ninja Mind, no entanto, os próprios jogadores definem os padrões, sujeitos a certas restrições. Mind Ninja difere de Hex também na medida em que pode ser jogado em qualquer superfície de azulejos, e cada jogador pode preencher uma célula com qualquer cor disponível, ao invés de apenas uma.

Chameleon

Utilizando o mesmo tabuleiro e peças do Hex, Chameleon dá aos jogadores a opção de colocar uma peça de qualquer cor no tabuleiro. Um jogador está tentando conectar-se às extremidades norte e sul, e o outro está tentando conectar-se às extremidades leste e oeste. O jogo é ganho quando uma conexão entre as bordas-objetivo de um jogador é formada usando qualquer cor. Se uma peça é colocada e cria uma conexão entre as bordas de ambos os objetivos dos jogadores (ou seja, todas as arestas estão conectadas), o vencedor é o jogador que colocou a peça final.

Chameleon é descrito no livro de Cameron Browne Connection Games: Variations on a Theme (2005) e foi descoberto independentemente por Randy Cox e Taylor Bill.

O jogo de switching de Shannon

O jogo de switching de Shannon envolve dois jogadores colorindo as arestas de um grafo arbitrário, cada um tentando se conectar dois vértices distintos com bordas de sua cor. Foi inventado pelo "pai da teoria da informação", Claude Shannon. Uma grade retangular é comumente usado para o grafo, desta forma o jogo foi inventado independentemente por David Gale, e tem sido conhecido como Gale, Bridg-It, e Bird Cage.

Ao contrário de Hex, este jogo não é PSPACE rígido.

Pex

Pex é quase idêntico ao Hex, exceto que ele é jogado em um losango de azulejos em forma de pentágonos irregulares, em vez de hexágonos regulares. os azulejos de Pex são notáveis pelo fato de que metade dos pentágonos conectam-se a sete vizinhos adjacentes, enquanto a outra metade conecta-se a apenas a cinco vizinhos. Táticas de Pex são muito mais nítidas do que as de Hex.

Hecks

Hecks uma outra variante do Hex em que as casas do tabuleiro quadrado são polígonos irregulares e o grafo formado pelas arestas do polígono é trivalente, isto é, cada nodo tem precisamente três arcos incidentes. A condição de trivalência se destina a evitar a decisão sobre a validade do contato entre dois azulejos que compartilham somente um vértice. Um aspecto interessante do Hecks é que os lados do tabuleiro não tem cor pré-definida: os jogadores negros e brancos não têm que declarar antecipadamente que par de lados eles tentam se conectar, e o primeiro jogador que completa um caminho através do tabuleiro ganha.

Ver também

• Teoria dos Jogos
• Jogos matemáticos

Ligações externas

• HexWiki, uma wiki dedicada ao Hex. (em inglês)
• Dissertação sobre Hex História, classificação e complexidade. (em inglês)
• Jogo de Hex no MathWorld com links para periódicos matemáticos relacionados. (em inglês)
• University of Alberta Computer Hex Research Group (em inglês)
• Página de teorias reunindo os trabalhos teóricos sobre o jogo. (em inglês)
• Tabuleiros de Hecks Tabuleiros de demonstração de Hecks do Wolfram Demonstration Project. (em inglês)
• Hexy Hexy é um forte jogador de Hex para Windows.
• jeudhex.com Étude sur le jeu d'hex Une approche mathématique par Edouard Rodrigues (em francês)
• Jogue Hex Online