Qual é a estratégia vencedora para o primeiro jogador nos jogos Connect Four?

Melhor resposta

A “estratégia” real é bastante complexa e envolve uma busca exaustiva de pontos para lidar com as táticas, por isso não é prático usar manualmente.

Por outro lado, os insights estratégicos e algumas regras de uso geral são fáceis de usar para um ser humano e provavelmente o tornarão relativamente bom jogador.

Histórico

Vamos começar revisando rapidamente o connect-4. O jogo é jogado em um tabuleiro de 6 × 7; podemos rotular cada linha com um número e cada coluna com uma letra:

Cada jogador se reveza para escolher uma coluna; sua pedra é colocada na célula aberta mais abaixo na coluna. Podemos escrever um jogo usando apenas as colunas; por exemplo, se ambos os jogadores jogarem na coluna central, podemos escrever dd. Isso levaria ao seguinte tabuleiro:

(Por convenção, o jogador 1 será azul e o jogador 2 vermelho.)

Um jogo pode ser ganho conectando quatro peças de sua cor horizontalmente, verticalmente ou diagonalmente:

Uma última noção útil é uma ameaça , que é apenas três peças em uma linha com o quarto quadrado aberto (mas não necessariamente acessível). Aqui, o azul tem uma ameaça na diagonal:

Estratégia

O jogo está resolvido: o primeiro jogador (azul) sempre pode forçar uma vitória. As ideias principais por trás da estratégia vencedora são bastante simples: controlar zugzwang e controlar ímpar / par linhas.

Zugzwang

“Zugzwang” como um termo significa perder porque você tem que fazer um movimento. Uma ilustração simples seria ter duas ameaças uma em cima da outra. Aqui está um exemplo do azul forçando uma vitória na coluna c com o vermelho para se mover:

No entanto, ameaças duplas como essa são razoavelmente fáceis de reconhecer com antecedência e contra-atacar. Na prática, uma forma muito mais útil de Zugzwang envolve apenas esperar até que todo o tabuleiro seja preenchido e haja apenas um movimento restante. Considere o exemplo simples em que o vermelho vence à esquerda, com a força real acontecendo apenas após vários movimentos:

Ameaças pares / ímpares

Quem quer que tenha uma ameaça que será inexoravelmente preenchida vencerá no final. Como vimos no exemplo anterior, o vermelho pode vencer com uma ameaça em um linha par . Por outro lado, o azul precisa de uma ameaça ímpar para vencer: é aqui que está a assimetria do jogo surge.

Uma ameaça estranha “limita” uma coluna e essencialmente inverte quem pode pegar qual linha ao preencher toda a boa rd. Em particular, isso significa que uma ameaça ímpar válida é “mais forte” do que uma ameaça par válida: se o azul tiver uma ameaça ímpar em uma coluna e o vermelho uma ameaça par em outra, o azul ainda assim vencerá. Aqui está um exemplo (azul para jogar):

Desta posição, podemos preencher repetidamente até chegarmos a um posição onde o vermelho tem que jogar c porque g (que tem um número ímpar de peças) resultaria na vitória do azul. Isso permite a coluna c é preenchida até que o vermelho seja forçado a perder:

O a ameaça ímpar “funciona” porque limita uma única coluna para ter um número ímpar de posições – efetivamente transformando o tabuleiro em um número par de quadrados (42) para um número ímpar, que inverte a dinâmica do jogo. Isso também significa que se ambos vermelho e azul têm ameaças ímpares independentes, eles se cancelam: tendo duas colunas ímpares trazem o total de volta a ser par.

Mais geralmente, a distinção ímpar / par nos dá uma noção de controle : o vermelho normalmente controla o jogo, mas o azul pode ganhar o controle estabelecendo uma ameaça ímpar. Na prática, controle significa ser capaz de jogar qualquer casa par ou, como opção, jogar uma casa ímpar, mas permitir que seu oponente jogue uma casa par em troca.

Táticas

A distinção ímpar / par nos permite jogar “estrategicamente” – um monte de jogadas à frente, pelo menos. Para realmente vencer de forma consistente, temos que combinar nosso conhecimento sobre estratégia de longo prazo com movimentos táticos sólidos de curto prazo. Temos que manter pequenas armadilhas como esta em mente:

Regras

A estratégia de vitória real para o jogo se resume a um conjunto de nove regras baseadas nos princípios estratégicos descritos anteriormente e táticas.As regras foram desenvolvidas por Victor Allis em 1988 – acho que ele foi a primeira pessoa a resolver o jogo.

As regras podem “t sempre encontre a solução ideal: às vezes, você teria que fazer uma pesquisa real pelas possibilidades, principalmente para lidar com questões táticas.

Aqui estão o que considero as regras mais importantes, com os nomes que Allis deu a elas . Existem mais algumas regras, mas são para casos especiais ou apenas combinações de regras anteriores; você pode ler sobre todas as regras na tese real: Uma abordagem baseada no conhecimento do Connect Four .

• baseinverse : você sempre pode reivindicar um dos dois quadrados acessíveis quando seu oponente reivindicar o outro, então você sempre pode bloquear um quatro em uma linha que precisa de dois quadrados como esse. Por exemplo, o vermelho sempre pode jogar um dos quadrados verdes depois que o azul reproduz o ther:

• vertical : você sempre pode bloquear um quatro-em-linha vertical, jogando um dos dois quadrados diretamente acima do outro. O vermelho sempre pode bloquear as quatro linhas verticais em d tocando um dos quadrados destacados:

• Claimeven : quem quer que tenha controle do jogo (ou seja, vermelho, a menos que o azul tenha uma ameaça estranha ) pode jogar um quadrado em uma linha par (contanto que esse quadrado não seja imediatamente jogável). Esta regra incorpora a estratégia ímpar / par básica.
• aftereven : se você tem controle e tem uma ameaça em uma linha uniforme, você poderá reproduzir essa linha por meio do Claimeven. Isso significa que todas as ameaças na mesma coluna acima daquela são bloqueadas. Por exemplo, aqui o azul não será capaz de reproduzir b3, pois o vermelho tem uma ameaça em b2:

• lowinverse : se houver duas colunas com um número ímpar de quadrados, o resultado é par. Se houver dois quadrados ímpares es em tais colunas que não são diretamente jogáveis, quem quer que controle o jogo poderá jogar pelo menos uma delas. Isso também pode se aplicar a quadrados que estão longe de serem jogáveis ​​e não próximos um do outro. Nestes dois exemplos simples, o vermelho pode obter pelo menos um dos dois quadrados destacados:

Vencendo

O jogo foi realmente resolvido por meio de uma combinação dessas regras e algumas pesquisas exaustivas – as regras por si só, infelizmente, não são suficientes.

Muitas das regras dependem do controle do jogo. Como o vermelho tem controle inicialmente, o azul não pode usar muitas das regras até que consigam estabelecer uma ameaça ímpar. O azul pode estabelecer uma ameaça ímpar usando algumas das regras que não dependem do controle ou apenas do pensamento tático, como combinar grupos de duas peças para garantir uma ameaça ímpar no futuro.

Acontece que a primeira o jogador pode fazer isso contra o jogo ideal, desde que o primeiro movimento seja d1. Isso significa que o primeiro jogador sempre pode vencer. A pesquisa que realmente estabeleceu isso também é detalhada na tese.

Para jogadores humanos, esse tipo de lógica é difícil de trabalhar. Felizmente, outra pessoa encontrou um conjunto de boas aberturas que geralmente você pode usar: Expert Play no Connect-Four .

Além disso, como um aparte, fiz todas as ilustrações usando o maravilhoso pacote diagramas de Haskell. Na verdade, toda essa resposta foi, na verdade, um exercício apenas para aprender como usar a biblioteca, o que pretendo fazer há algum tempo! Você pode dar uma olhada no código nesta essência. O código é confuso, mas é “uma ótima demonstração de que, ao contrário da crença popular, Haskell é realmente ótimo para prototipagem interativa e escrita de código descartável.

Além disso, eu acho “legal ver como o Emacs pode visualizar SVGs e PNGs em um buffer, essencialmente me dando um ambiente sob medida para desenvolver imagens como este: