Hex (jogo de tabuleiro) - Hex (board game)

Este artigo é sobre o jogo abstrato de estratégia. Para outros usos, veja Jogo hexadecimal (desambiguação) .

Hex
Hex-board-11x11- (2) .jpg
Tabuleiro de jogo hexadecimal 11 × 11 mostrando uma configuração vencedora para Azul
Anos ativos 1942-presente
Gêneros Jogo de tabuleiro Jogo de
estratégia abstrato Jogo de
conexão
Jogadoras 2
Tempo de preparação Nenhum
Hora de brincar 30 minutos - 2 horas (11 × 11 tabuleiro)
Chance aleatória Nenhum
Habilidades requeridas Estratégia , tática

Hex é um jogo de tabuleiro de estratégia abstrato para dois jogadores, no qual os jogadores tentam conectar lados opostos de um tabuleiro hexagonal . Hex foi inventado pelo matemático e poeta Piet Hein em 1942 e independentemente por John Nash em 1948.

É tradicionalmente jogado em um tabuleiro de losango 11 × 11 , embora os tabuleiros 13 × 13 e 19 × 19 também sejam populares. Cada jogador recebe um par de lados opostos do tabuleiro que eles devem tentar conectar, colocando uma pedra de sua cor em qualquer espaço vazio. Uma vez colocadas, as pedras não podem ser movidas ou removidas. Um jogador ganha quando consegue conectar seus lados através de uma cadeia de pedras adjacentes. Os empates são impossíveis no Hex devido à topologia do tabuleiro de jogo.

O jogo tem estratégia profunda, táticas afiadas e uma base matemática profunda relacionada ao teorema de ponto fixo de Brouwer . O jogo foi comercializado pela primeira vez como um jogo de tabuleiro na Dinamarca sob o nome de Con-tac-tix , e a Parker Brothers comercializou uma versão dele em 1952, chamada Hex ; eles não estão mais em produção. Hex também pode ser jogado com papel e lápis em papel quadriculado pautado hexagonalmente.

A pesquisa relacionada ao hex é atual nas áreas de topologia, teoria de grafos e matróides , combinatória, teoria dos jogos combinatórios e inteligência artificial.

Tipo de jogo

Hex é um jogo de conexão e pode ser classificado como um jogo Maker-Breaker , um tipo particular de jogo posicional . O jogo nunca pode terminar em empate (empate) , ou seja, o Hex também é um “ jogo determinado ”.

Hex é um jogo de informação finito e perfeito , e um jogo de estratégia abstrato que pertence à categoria geral de jogos de conexão . Hex é um caso especial da versão "node" do jogo de comutação Shannon .

Como produto, Hex é um jogo de tabuleiro ; também pode ser jogado com papel e lápis .

História

Invenção

O jogo foi inventado pelo matemático dinamarquês Piet Hein , que o introduziu em 1942 no Instituto Niels Bohr . Embora Hein mais tarde o tenha renomeado para Con-tac-tix, ficou conhecido na Dinamarca sob o nome de Polygon devido a um artigo de Hein na edição de 26 de dezembro de 1942 do jornal dinamarquês Politiken , a primeira descrição publicada do jogo, no qual ele usou esse nome. O jogo foi reinventado independentemente em 1948 pelo matemático John Nash da Universidade de Princeton . De acordo com Martin Gardner , que apresentou Hex em sua coluna de Jogos Matemáticos de julho de 1957 , os outros jogadores de Nash chamavam o jogo de Nash ou John, com o último nome se referindo ao fato de que o jogo podia ser jogado em ladrilhos hexagonais de banheiro. Hein escreveu a Gardner em 1957 expressando dúvidas de que Nash descobriu Hex independentemente, mas Nash insiste que ele reinventou o jogo antes de ser exposto ao trabalho de Hein. Gardner foi incapaz de verificar ou refutar de forma independente a afirmação de Nash.

Jogos publicados

Uma edição Parker Brothers do jogo

Em 1952, a Parker Brothers comercializou uma versão. Eles chamaram sua versão de "Hex" e o nome pegou. A Parker Brothers também vendeu uma versão com o nome "Con-tac-tix" em 1968. Hex também foi lançado como um dos jogos na 3M Paper Games Series de 1974; o jogo continha um 5+1 ⁄ 2 -por- 8+1 ⁄ 2 polegadas (140 mm × 220 mm) Bloco de 50 folhas de grades hexagonais pautadas. Hex é publicado atualmente pela Nestorgames em um tamanho 11x11 e um tamanho 14x14.

Máquina hexadecimal de Shannon

Por volta de 1950, o matemático e engenheiro elétrico americano Claude Shannon e EF Moore construíram uma máquina de jogo Hex analógica, que era essencialmente uma rede de resistência com resistores para bordas e lâmpadas para vértices. O movimento a ser feito correspondia a um determinado ponto de sela especificado na rede. A máquina jogou um jogo razoavelmente bom de Hex. Mais tarde, os pesquisadores tentando resolver o jogo e desenvolver algoritmos de computador Hex-playing emularam a rede de Shannon para fazer autômatos fortes.

Linha do tempo de pesquisa

Em 1952, John Nash expôs uma prova de existência de que em tabuleiros simétricos, o primeiro jogador tem uma estratégia vencedora.

Em 1964, o matemático Alfred Lehman mostrou que Hex não pode ser representado como uma matróide binária , então uma estratégia de vitória determinada como aquela para o jogo de troca de Shannon em uma grade retangular regular não estava disponível. Mais tarde, o jogo foi mostrado para ser PSPACE completo.

Em 2002, a primeira estratégia vencedora explícita (uma estratégia do tipo redução) em um tabuleiro 7 × 7 foi descrita.

Na década de 2000, usando algoritmos de computador de busca de força bruta , placas hexadecimais até o tamanho 9 × 9 (em 2016) foram completamente resolvidas.

Até 2019, os humanos permaneciam melhores que os computadores pelo menos em grandes tabuleiros como 19x19, mas em 30 de outubro de 2019 o programa Mootwo venceu o jogador humano com a melhor classificação ELO no LittleGolem, também vencedor de vários torneios (o jogo está disponível aqui ) Este programa foi baseado no Polygames (um projeto de código aberto, inicialmente desenvolvido pela Facebook Artificial Intelligence Research e várias universidades) usando uma mistura de:

  • zero-learning como em AlphaZero
  • invariância de boardize graças a redes neurais totalmente convolucionais (como em U-Net ) e pooling
  • e arquiteturas crescentes (o programa pode aprender em uma pequena placa e então extrapolar em uma grande placa, em oposição a alegações populares justificadas sobre métodos de inteligência artificial anteriores, como o AlphaGo original).

Autômatos

No início da década de 1980, a Dolphin Microware publicou Hexmaster , uma implementação para computadores Atari de 8 bits . Vários paradigmas resultantes da pesquisa do jogo foram usados ​​para criar autômatos de jogos hexadecimais de computador digital a partir de 2000. As primeiras implementações usaram funções de avaliação que emularam o modelo de circuito elétrico de Shannon e Moore embutido em uma estrutura de pesquisa alfa-beta com conhecimento artesanal. padrões baseados. A partir de 2006, os métodos de pesquisa de árvore de Monte Carlo emprestados de implementações de computador bem-sucedidas do Go foram introduzidos e logo dominaram o campo. Mais tarde, os padrões feitos à mão foram complementados por métodos de aprendizado de máquina para descoberta de padrões. Esses programas agora são competitivos contra jogadores humanos qualificados. Classificações baseadas em Elo foram atribuídas a vários programas e podem ser usadas para medir o progresso técnico, bem como avaliar a força de jogo contra humanos classificados como Elo. A pesquisa atual é frequentemente publicada no jornal trimestral ICGA ou na série anual Advances in Computer Games (van den Herik et al. Eds.).

Jogo

Preto vs branco em uma placa hexadecimal

Cada jogador tem uma cor atribuída, convencionalmente Vermelho e Azul ou Branco e Preto. Os jogadores se revezam colocando uma pedra de sua cor em uma única célula dentro do tabuleiro geral. Uma vez colocadas, as pedras não são movidas, capturadas, substituídas ou removidas do tabuleiro. O objetivo de cada jogador é formar um caminho conectado de suas próprias pedras ligando os lados opostos do tabuleiro marcados por suas cores, antes que seu oponente conecte seus lados de maneira semelhante. O primeiro jogador a completar sua conexão vence o jogo. Os hexágonos em cada um dos quatro cantos pertencem a ambos os lados adjacentes.

Não é necessário construir uma cadeia completa entre os lados ou encher todo o tabuleiro antes de o jogo ser decidido (mas se o fizer por construção, o jogador que colocar a última pedra vencerá); normalmente, apenas 1/3 a 40% do tabuleiro é preenchido antes de se tornar óbvio que um jogador ou outro pode forçar uma vitória. Isso é um tanto análogo a jogos de xadrez que terminam muito antes do xeque-mate - o jogo geralmente termina com um jogador ou outro desistindo.

Como o primeiro jogador a se mover em Hex tem uma vantagem distinta, a regra da pizza é geralmente implementada para fins de justiça. Esta regra permite que o segundo jogador escolha se deseja trocar de posição com o primeiro jogador após o primeiro jogador fazer o primeiro movimento.

Estratégia

A partir da prova de uma estratégia vencedora para o primeiro jogador, sabe-se que o tabuleiro Hex deve ter um tipo complexo de conectividade que nunca foi resolvido. O jogo consiste em criar pequenos padrões que possuem um tipo de conectividade mais simples denominado "conectado com segurança", e uni-los em sequências que formam um "caminho". Eventualmente, um dos jogadores conseguirá formar um caminho de pedras e espaços conectados com segurança entre seus lados do tabuleiro e vencer. A etapa final do jogo, se necessário, consiste no preenchimento dos espaços vazios do caminho.

Diagrama 1: ponte (A <--> C), um padrão conectado com segurança

Um padrão "conectado com segurança" é composto de pedras da cor do jogador e espaços abertos que podem ser unidos em uma cadeia, uma sequência ininterrupta de pedras adjacentes nas bordas, não importa como o oponente joga. Um dos padrões mais simples é a ponte (ver diagrama 1), que consiste em duas pedras da mesma cor (A e C) e um par de espaços abertos (B e D). Se o adversário joga em um dos espaços, o jogador joga no outro, criando uma cadeia contígua. Existem também padrões conectados com segurança que conectam as pedras às bordas. Existem muitos padrões mais conectados com segurança, alguns bastante complexos, construídos a partir de outros mais simples, como os mostrados. Padrões e caminhos podem ser interrompidos pelo oponente antes de serem concluídos, de modo que a configuração do tabuleiro durante um jogo real muitas vezes parece uma colcha de retalhos em vez de algo planejado ou projetado.

Existem tipos de conectividade mais fracos do que "conectado com segurança" que existem entre pedras ou entre padrões conectados com segurança que têm vários espaços entre eles. A parte intermediária do jogo consiste em criar uma rede de pedras e padrões tão fracamente conectados que permitirão ao jogador, ao preencher os links fracos, construir apenas um caminho conectado com segurança entre os lados conforme o jogo avança.

O sucesso na Hex requer uma habilidade particular de visualizar a síntese de padrões complexos de uma forma heurística, e estimar se tais padrões estão 'fortemente conectados' para permitir uma eventual vitória. A habilidade é um tanto semelhante à visualização de padrões, sequência de movimentos e avaliação de posições no xadrez.

Teoria matemática

Determinação

John Nash foi o primeiro a provar (c. 1949) que Hex não pode terminar em empate, um resultado não trivial coloquialmente chamado de "teorema Hex", que agora sabemos ser equivalente ao teorema de ponto fixo de Brouwer. Aparentemente, ele não publicou a prova. A primeira exposição disso aparece em um relatório técnico interno em 1952, no qual afirma que "conectar e bloquear o oponente são atos equivalentes". A primeira prova rigorosa foi publicada por John R. Pierce em seu livro de 1961 , Symbols, Signals and Noise . Em 1979, David Gale publicou uma prova que também mostrou que ela pode ser usada para provar o teorema de ponto fixo bidimensional de Brouwer , e que a determinação das variantes de dimensões superiores prova o teorema de ponto fixo em geral. Um breve esboço do requisito de finalização sem empate de Hex desse papel é apresentado abaixo:

  1. Comece com um tabuleiro hexadecimal totalmente preenchido com hexágonos marcados com X ou O (indicando qual jogador jogou naquele hexágono).
  2. Começando em um vértice do hexágono no canto do tabuleiro onde os lados X e O se encontram, desenhe um caminho ao longo das bordas entre os hexágonos com marcações X / O diferentes.
  3. Uma vez que cada vértice do caminho é cercado por três hexágonos, o caminho não pode se auto-interceptar ou fazer um loop, uma vez que a parte de interseção do caminho teria que se aproximar entre dois hexágonos da mesma marcação. Portanto, o caminho deve terminar.
  4. O caminho não pode terminar no meio do tabuleiro, pois cada borda do caminho termina em um nó cercado por três hexágonos - dois dos quais devem ser marcados de forma diferente pela construção. O terceiro hexágono deve ser marcado de forma diferente dos dois adjacentes ao caminho, para que o caminho possa continuar para um lado ou outro do terceiro hexágono.
  5. Da mesma forma, se as laterais do tabuleiro forem consideradas uma parede sólida de hexágonos X ou O, dependendo de qual jogador está tentando se conectar ali, o caminho não pode terminar nas laterais.
  6. Assim, o caminho só pode terminar em outro canto.
  7. Os hexágonos de cada lado da linha formam uma cadeia contínua de hexágonos X de um lado e hexágonos O do outro por construção.
  8. O caminho não pode terminar no canto oposto porque as marcações X e O seriam invertidas naquele canto, violando a regra de construção do caminho.
  9. Como o caminho conecta cantos adjacentes, o lado do tabuleiro entre os dois cantos (digamos, um lado X) é cortado do resto do tabuleiro por uma cadeia contínua de marcações opostas (O, neste caso). Essa cadeia ininterrupta conecta necessariamente os outros dois lados adjacentes aos cantos.
  10. Portanto, o tabuleiro hexadecimal totalmente preenchido deve ter um vencedor.

Há uma prova de existência reductio ad absurdum atribuída a John Nash c. 1949 que o primeiro jogador em Hex em um tabuleiro de qualquer tamanho tem uma estratégia vencedora . Tal prova não dá nenhuma indicação de uma estratégia correta de jogo. A prova é comum a vários jogos, incluindo Hex, e passou a ser chamada de argumento do roubo de estratégia . Aqui está uma declaração informal altamente condensada da prova:

  1. É impossível que o jogo termine empatado (veja acima), portanto, o primeiro ou o segundo jogador deve vencer.
  2. Como Hex é um jogo de informação perfeito , deve haver uma estratégia vencedora para o primeiro ou segundo jogador.
  3. Suponhamos que o segundo jogador tenha uma estratégia vencedora.
  4. O primeiro jogador pode agora adotar a seguinte defesa. Ele faz um movimento arbitrário. Depois disso, ele joga a estratégia vencedora do segundo jogador assumida acima. Se, ao jogar esta estratégia, ele for obrigado a jogar na célula onde um movimento arbitrário foi feito, ele faz outro movimento arbitrário. Desta forma, ele joga a estratégia vencedora com uma peça extra sempre no tabuleiro.
  5. Esta peça extra não pode interferir com a imitação do primeiro jogador da estratégia vencedora, pois uma peça extra é sempre uma vantagem e nunca uma desvantagem. Portanto, o primeiro jogador pode vencer.
  6. Como agora contradizemos nossa suposição de que existe uma estratégia vencedora para o segundo jogador, somos forçados a abandonar essa suposição.
  7. Conseqüentemente, deve haver uma estratégia vencedora para o primeiro jogador.

Complexidade computacional de generalizações

Em 1976, Shimon Even e Robert Tarjan provaram que determinar se uma posição em um jogo de Hex generalizado jogado em gráficos arbitrários é uma posição vencedora é PSPACE completo . Um fortalecimento deste resultado foi provado por Reisch reduzindo a fórmula booleana quantificada na forma normal conjuntiva para Hex jogado em gráficos planares arbitrários . Na teoria da complexidade computacional , é amplamente conjecturado que problemas PSPACE-completos não podem ser resolvidos com algoritmos eficientes (tempo polinomial). Este resultado limita a eficiência dos melhores algoritmos possíveis ao considerar posições arbitrárias em tabuleiros de tamanho ilimitado, mas não descarta a possibilidade de uma estratégia vencedora simples para a posição inicial (em tabuleiros de tamanho ilimitado), ou um simples vencedor estratégia para todas as posições em um conselho de um tamanho específico.

Árvore do jogo de 11 por 11 hexadecimais

Em 11 × 11 Hex, existem aproximadamente 2,4 × 10 56 posições legais possíveis; isso se compara a 4,6 × 10 46 posições legais no xadrez.

Uma estimativa grosseira do número de nós na árvore do jogo pode ser obtida como uma função exponencial do fator de ramificação médio e do número médio de camadas em um jogo, assim: b d onde d é a profundidade da camada eb é o fator de ramificação. Em Hex, o fator de ramificação médio é uma função da profundidade da camada. Foi afirmado que o fator de ramificação médio é cerca de 100; isso implica em uma profundidade de camada média de 43 (haverá 121 espaços abertos no tabuleiro quando o primeiro jogador fizer seu primeiro movimento, e 79 quando ele fizer sua 22ª jogada, a 43ª folha - o número médio de espaços abertos , ou seja, o fator de ramificação, durante o jogo é (121 + 120 + ... + 79) / 43 = 100). Portanto, o tamanho da árvore do jogo tem um limite superior de aproximadamente 100 43 = 10 86 . O limite inclui um certo número de posições ilegais devido a jogar quando há uma cadeia completa para um jogador ou outro, bem como exclui posições legais para jogos com mais de 43 folhas. Outro pesquisador obteve uma estimativa de espaço de estado de 10 57 e um tamanho de árvore de jogo de 10 98 usando um limite superior de 50 camadas para o jogo. Isso se compara ao tamanho da árvore do jogo de xadrez de 10 123 nós.

Reduções interessantes da árvore do jogo estão disponíveis observando que o tabuleiro tem simetria bilateral dupla, bem como simetria rotacional de 180 °: para cada posição, uma posição topologicamente idêntica é obtida virando o tabuleiro da esquerda para a direita, de cima para baixo ou girando-o 180 ° .

Estratégias computadas para placas menores

Em 2002, Jing Yang, Simon Liao e Mirek Pawlak encontraram uma estratégia de vitória explícita para o primeiro jogador em tabuleiros hexadecimais de tamanho 7 × 7 usando um método de decomposição com um conjunto de padrões locais reutilizáveis. Eles estenderam o método para resolver fracamente o par central de aberturas topologicamente congruentes em placas 8 × 8 em 2002 e a abertura central em placas 9 × 9 em 2003. Em 2009, Philip Henderson, Broderick Arneson e Ryan B. Hayward completaram a análise de a placa 8 × 8 com pesquisa no computador, resolvendo todas as aberturas possíveis. Em 2013, Jakub Pawlewicz e Ryan B. Hayward resolveram todas as aberturas para tabuleiros 9 × 9 e um movimento de abertura (o mais central) no tabuleiro 10 × 10. Para cada N≤10, um primeiro movimento vencedor em N × N Hex é o mais central, sugerindo a conjectura de que isso é verdadeiro para cada N≥1.

Variantes

Outros jogos de conexão com objetivos semelhantes, mas com estruturas diferentes, incluem jogo de troca de Shannon e TwixT . Ambos possuem algum grau de semelhança com o antigo jogo asiático Go .

Grades retangulares e papel e lápis

O jogo pode ser jogado em uma grade retangular como um tabuleiro de xadrez, de damas ou de go, considerando que os espaços (intersecções no caso de go) estão conectados em uma direção diagonal, mas não na outra. O jogo pode ser jogado com papel e lápis em uma matriz retangular de pontos ou papel quadriculado da mesma maneira, usando dois lápis de cores diferentes.

Tamanhos de tabuleiro

As dimensões populares diferentes do 11x11 padrão são 13 × 13 e 19 × 19, como resultado da relação do jogo com o jogo mais antigo Go . De acordo com o livro A Beautiful Mind , John Nash (um dos inventores do jogo) defendeu 14 × 14 como o tamanho ideal.

Rex (Hex reverso)

A variante misère de Hex. Cada jogador tenta forçar seu oponente a fazer uma corrente. Rex é mais lento do que Hex, pois, em qualquer tabuleiro vazio com dimensões iguais, a jogada perdedora pode atrasar uma perda até que todo o tabuleiro esteja cheio. Em tabuleiros com dimensões desiguais, o jogador cujos lados estão mais afastados pode vencer independentemente de quem jogar primeiro. Em tabuleiros com dimensões iguais, o primeiro jogador pode ganhar em um tabuleiro com um número par de células por lado, e o segundo jogador pode ganhar em um tabuleiro com um número ímpar. Em tabuleiros com um número par, uma das jogadas vencedoras do primeiro jogador é sempre colocar uma pedra no canto agudo.

Blockbusters

Hex teve uma encarnação como o painel de perguntas do game show de televisão Blockbusters . Para fazer uma "jogada", os competidores tinham que responder a uma pergunta corretamente. O tabuleiro tinha 5 colunas alternadas de 4 hexágonos; o jogador solo pode se conectar de cima para baixo em 4 movimentos, enquanto a equipe de dois pode se conectar da esquerda para a direita em 5 movimentos.

Y

O jogo de Y é Hex, jogado em uma grade triangular de hexágonos; o objetivo é que cada jogador conecte os três lados do triângulo. Y é uma generalização de Hex na medida em que qualquer posição em um tabuleiro Hex pode ser representada como uma posição equivalente em um tabuleiro Y maior.

Havannah

Havannah é um jogo baseado em Hex. Ele difere do Hex por ser jogado em uma grade hexagonal de hexágonos e uma vitória é obtida ao formar um de três padrões.

Projex

Projex é uma variação do Hex jogado em um plano projetivo real , onde os jogadores têm o objetivo de criar um loop não contrátil . Como no Hex, não há empates e não há posição em que ambos os jogadores tenham uma conexão vencedora.

Concorrência

Em 2016, houve torneios over-the-board relatados do Brasil, República Tcheca, Dinamarca, França, Alemanha, Itália, Holanda, Noruega, Polônia, Portugal, Espanha, Reino Unido e Estados Unidos.

Um dos maiores torneios Hex é organizado pelo Comitê Internacional de Jogos Matemáticos em Paris, França, que é realizado anualmente desde 2013.

Hex também faz parte da Olimpíada de Computador .

Veja também

Referências

Leitura adicional

  • Hex Strategy: Making the Right Connections , Browne C. (2000), AK Peters Ltd. Natick, MA. ISBN  1-56881-117-9 (brochura comercial, 363pgs)
  • HEX: The Full Story , Hayward R. com Toft B. (2019), CRC Press Boca Raton, FL. ISBN  978-0-367-14422-7 (brochura)

links externos