Havannah - Havannah

Este artigo é sobre o jogo de tabuleiro. Para a vila inglesa, veja Havannah, Cheshire . Para outros usos, veja Havana (desambiguação) .
Exemplos das três estruturas vencedoras em Havannah, em um tabuleiro de base 8. Da esquerda para a direita, eles são a bifurcação , o anel e a ponte .

Havannah é um jogo de tabuleiro abstrato de estratégia para dois jogadores inventado por Christian Freeling . Pertence à família de jogos comumente chamados de jogos de conexão ; seus parentes incluem Hex e TwixT . Havannah tem "uma estratégia sofisticada e variada" e é melhor jogada em um tabuleiro hexagonal de base 10, 10 células hexadecimais de cada lado.

O jogo foi publicado por um período na Alemanha pela Ravensburger , com um tabuleiro menor, de base 8, adequado para iniciantes. Hoje em dia é produzido apenas pela Hexboards.

Regras do jogo

Um jogador joga como preto; o outro joga como branco. As brancas começam, após o que os movimentos se alternam. As regras são as seguintes:

  • Cada jogador coloca uma pedra de sua cor no tabuleiro por turno.
  • As pedras nunca são movidas, capturadas ou alteradas de outra forma.
  • Um jogador ganha quando conclui uma das três estruturas diferentes de linhas ininterruptas, ou caminhos, de pedras conectadas, todas de suas cores:
    • Um anel é um loop em torno de uma ou mais células (não importa se as células circundadas estão ocupadas por algum jogador ou vazias);
    • Uma ponte , que conecta quaisquer duas das seis células de canto do tabuleiro;
    • Um garfo , que conecta quaisquer três arestas da placa; os pontos de canto não são considerados partes de uma aresta.

Um exemplo de todas as três combinações vencedoras é mostrado acima. A estrutura no centro do tabuleiro é um anel; a estrutura do lado esquerdo é uma bifurcação; a estrutura do lado direito é uma ponte.

Uma vez que o primeiro jogador a se mover em Havannah 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.

Jogadores com forças diferentes ainda podem jogar um jogo interessante quando o jogador mais fraco (como as brancas) pode colocar duas ou mais pedras no primeiro turno.

Diferença em comparação com Hex

No Hex, quando o tabuleiro estiver completamente preenchido, exatamente um jogador terá uma conexão vencedora; em Havannah, um tabuleiro completamente preenchido normalmente terá mais de uma estrutura vencedora (mas o jogo termina com a primeira estrutura vencedora).

Ao contrário de Hex, em Havannah os empates são tecnicamente possíveis, mas na prática são extremamente raros. Existe um empate conhecido entre jogadores humanos. As táticas são muito mais fáceis de dominar do que a estratégia, e as diferenças no nível de jogo são consideráveis.

Havannah de computador

Em 2002, o Freeling ofereceu um prêmio de 1000 euros, disponível até 2012, para qualquer programa de computador que pudesse vencê-lo em até mesmo um jogo de uma partida de dez jogos. Por muitos anos, os programas de computador ficaram muito atrás dos jogadores humanos. No entanto, desde 2010, vários programas de jogo em Havannah aplicaram técnicas de pesquisa em árvore de Monte Carlo , resultando em alguma melhoria notável na força de jogo. O "Havannah Challenge 2012" foi realizado de 15 a 19 de outubro de 2012, durante o qual Freeling jogou dez jogos contra três dos mais fortes programas de Havannah disponíveis, jogando (pelo menos) um jogo como preto e um como branco contra cada oponente. Freeling perdeu o desafio quando teve que renunciar a um jogo com as brancas contra o programa de Lajkonik.

Até 2019, os melhores humanos ainda eram muito mais fortes do que os computadores. No entanto, MetaTotoro , baseado em Polygames (um projeto de código aberto, inicialmente desenvolvido pelo Facebook Artificial Intelligence Research e várias universidades), venceu quatro vezes consecutivas no tabuleiro de tamanho 8 contra o jogador humano com a melhor classificação ELO no LittleGolem , que também foi o vencedor de vários torneios.

Este resultado foi alcançado pelo mesmo programa usado para derrotar os melhores humanos na Hex . É um algoritmo baseado em aprendizagem zero, como em AlphaZero, mas com novidades: invariância de boardize graças a redes neurais totalmente convolucionais (como em U-Net) e pooling global. Isso permite arquiteturas crescentes, o que significa que o programa pode aprender em uma pequena placa e, em seguida, extrapolar em uma grande placa.

Complexidade computacional

Resolvendo Havannah é PSPACE completo no que diz respeito ao tamanho do gráfico de entrada. A prova é por uma redução da geografia generalizada e é baseada no uso de ameaças em anel para representar o gráfico da geografia. Em detalhes, uma vez que Lichtenstein e Sipser provaram que a geografia generalizada permaneceu PSPACE-difícil, mesmo se o gráfico for apenas bipartido e de grau no máximo 3 , resta apenas construir uma posição Havannah equivalente a partir de tal gráfico, o que é conseguido através da construção de vários gadgets em Havannah.

Referências

links externos