Como resolver o "Campo Minado" (e torná-lo melhor)

Campo Minado é um jogo simples, com regras simples, no entanto, algumas de suas configurações criam dificuldades interessantes. Neste artigo, criaremos um solucionador Minesweeper com crescente complexidade e refletiremos sobre como a dinâmica do jogo muda com um aumento gradual no nível de ajuda. No final, desenvolveremos uma nova versão do jogo com uma jogabilidade muito mais interessante.

Raciocínio local: zero minas vizinhas

No jogo original , um mecanismo automático é usado: quando um jogador abre uma célula, próximo à qual não há minas, o mecanismo do jogo abre todas as células vizinhas. Isso não ameaça o jogo, então você pode deixar o computador com segurança, e a situação em si é imediatamente clara para o jogador e não interfere na jogabilidade.

Esse raciocínio é completamente local: somente uma informação da célula é levada em consideração para decidir a próxima ação.

É difícil chegar a uma situação em que o jogo pioraria sem essa ajuda automática. Tente jogar esse jogo para ter uma idéia de como ele funciona sem abrir automaticamente as células [no artigo original, todos os exemplos são interativos] :

Considerações locais com base no ambiente

Será fácil para um novo jogador entender que, se o número de minas vizinhas, ou seja, o número mostrado na célula, for igual ao número de células vizinhas não descobertas, todas essas células deverão ser minas, portanto, você deve colocar bandeiras nelas. Da mesma forma, quando o número de minas vizinhas é igual ao número de sinalizadores vizinhos, as células vizinhas não descobertas restantes devem estar vazias.

Nestas regras, uma célula é levada em consideração, assim como o estado das células vizinhas (aberta / marcada).

A implementação manual dessas regras pode ser divertida. Se você adicionar um cronômetro, o player começará a aprender como aplicá-los com rapidez e precisão. Isso transforma o caça- minas em um jogo de reação . O que acontece se automatizarmos essas regras?


Essa automação tem um efeito colateral interessante - marcar a caixa pode ter consequências fatais instantaneamente.

Caso contrário, podemos enfrentar situações que podem ser divididas em três categorias:

1. Jogos totalmente resolvidos aplicando regras automáticas
2. Situações complicadas que exigem mais células para raciocínio
3. Estados do jogo em que não há caminho lógico - o jogador pode escolher apenas por acaso, possivelmente levando em conta as probabilidades.

A situação 1 parece bonita, mas não particularmente interessante se surgir com muita frequência. Esses jogos seriam melhores sem uma solução automática? Talvez não; esses jogos são muito simples, mesmo quando resolvidos manualmente, e o jogador não está particularmente interessado em jogar jogos nos quais não há dificuldades. Embora, é claro, sempre haja dificuldade no jogo de reação: você precisa agir o mais rápido possível.

A situação 2. parece muito atraente para mim.Nós nos concentramos mais em resolver condições lógicas, gastando menos tempo em direcionar com precisão e pressionar os botões certos. Isso torna o Sapper mais parecido com um quebra-cabeça ativo .

A situação 3 destrói completamente toda a diversão. No entanto, ouvi dizer que algumas pessoas gostam de jogar aleatoriamente .

É possível se livrar da situação 3?

Solução completa: Raciocínio global

Para a detecção algorítmica de todas as condições lógicas necessárias para o estado do jogo, precisamos realizar uma pesquisa exaustiva por todos os estados do jogo. O Campo Minado provou ser uma tarefa completa de NP . Abaixo está um exemplo pequeno, mas interessante e ilustrativo, do estado do jogo, com apenas uma solução lógica, mas para encontrá-lo, é necessário levar em consideração o estado do jogo como um todo:


É possível pesquisar todo o espaço de estados do jogo? Quantas variações do estado s existem?

Dado:

w = largura do campo

h = altura do campo

k = número de minutos

n = w

Então o número de estados possíveis s é

$$

$$s = \ begin {pmatrix} n \\ k \ end {pmatrix}$$

Para os níveis padrão "Iniciante", "Amador" e "Profissional", isso nos dá:

$$

$$s_b = \ begin {pmatrix} 8 * 8 \\ 10 \ end {pmatrix} = 151473214816$$

$$

$$s_i = \ begin {pmatrix} 16 * 16 \\ 40 \ end {pmatrix} = 1.050 * 10 ^ {47}$$

$$

$$s_e = \ begin {pmatrix} 30 * 16 \\ 99 \ end {pmatrix} = 5.602 * 10 ^ {104}$$

Entendemos que uma abordagem ingênua é completamente inapropriada aqui. Vamos ver como um algoritmo ingênuo pode parecer e descobrir se ele pode ser otimizado para algo que funcione.

Algoritmo ingênuo

A tarefa do algoritmo é encontrar todas as condições lógicas necessárias para o estado especificado do campo. Seria difícil implementar isso considerando cuidadosamente as soluções; o computador faz um trabalho muito melhor ao executar rapidamente várias ações estúpidas.

O que podemos fazer de “estúpido”: gerar todas as permutações possíveis das posições das minas para todas as minas restantes. Se essa permutação corresponder a todos os números em aberto, será a solução correta para o jogo. Depois estudamos todas as permutações possíveis, encontramos todas as soluções possíveis, mas ainda não sabemos qual é a correta.

Se em todas as soluções possíveis houver algo em comum, seja entre células abertas ou entre células marcadas como minas, entendemos que esse comum deve fazer parte da decisão correta para o campo atual. E, de fato: é impossível criar a solução certa que não possui esses elementos correspondentes, caso contrário, nós os teríamos descoberto.

Assim, podemos encontrar todas as condições lógicas necessárias para o estado atual do campo.

Células com e sem restrições

O algoritmo acima tem um problema óbvio: o número de estados que ele precisa investigar. Mas nem todas as células são iguais. As células fechadas ao lado de um número estão obviamente limitadas a esse número. Vamos chamar essas células de limitadas. As células restantes chamaremos ilimitadas.

Se implementarmos o algoritmo acima, mas pesquisaremos apenas no espaço de estado das células restritas, e voltaremos assim que quebrarmos a restrição, em muitos jogos podemos resolver todas as condições lógicas em um período de tempo razoável:


No caso de células ilimitadas, não podemos descobrir onde as minas estão localizadas e, logicamente, sabemos imediatamente sobre isso. Isso significa que você pode excluí-los do cálculo e considerar apenas a localização das minas ao lado dos números em aberto.

No entanto, sabemos que um certo número de minas pode entrar em muitas células ilimitadas; se houver 6 minutos e 4 células restritas, em células limitadas, pode haver um máximo de 4 minas, ou seja, pelo menos 2 minutos deverão estar em células ilimitadas. Pela mesma lógica, às vezes podemos determinar que todas as células ilimitadas devem estar vazias ou que contêm minas.

No caso mostrado abaixo, conhecemos as posições de todas as minas; portanto, a IA deve entender que as células restantes não estão ocupadas:


No caso a seguir, não sabemos as posições de todas as minas, mas podemos entender que a mina restante deve ser colocada em uma das duas células no canto superior esquerdo. Isso significa que a célula restante no canto inferior direito está livre:

Versão aleatória

Se executarmos automaticamente o solucionador global, obteremos uma versão otimizada aleatoriamente do Minesweeper:


Você pode dividir os jogos nesta versão em três categorias:

1. Jogos nos quais o jogador faz escolhas e vence arbitrariamente.
2. Jogos nos quais o jogador faz escolhas e perde arbitrariamente.
3. Jogos nos quais a IA exige muito tempo, e o jogador pode realmente usar o raciocínio.

Obviamente, este é um jogo de azar. Qual é o apelo de tais jogos? Em termos de lógica, o jogo mostrado acima é semelhante a este:


Mas qual jogo aleatório é melhor? Parece que o significado de outros jogos com aleatoriedade reside na existência de uma relação complexa entre as ações do jogador e a vitória / derrota. Para desenhar números de loteria, são usadas máquinas complexas que não têm pressa para selecionar um número e fazer um show inteiro mostrando esse número.

Talvez um campo grande decidido automaticamente seja um jogo muito bom
com aleatoriedade, dado que o jogador está assistindo a abertura gradual de todas as células.

Podemos criar um tipo diferente de jogo?

Versão determinística

Agora temos uma IA capaz de determinar todas as etapas lógicas de um determinado estado do jogo. Às vezes, ele não conseguirá encontrar etapas lógicas. Em tais situações, o jogador tem que adivinhar e ele pode perder se não tiver sorte.

E se adicionarmos outra regra? Quando o jogo não tem um caminho lógico, podemos pedir ajuda. Se a IA concordar que o jogador não pode fazer nada, ele vem em seu auxílio. Caso contrário, o jogador perde imediatamente. Isso pode ser interessante. Que tipo de ajuda pode ser essa? Talvez você precise abrir uma célula, independentemente da presença de minas nela:


Assim, nos livramos completamente de situações nas quais alguém poderia perder por acaso.

No entanto, há uma exceção: ainda há a possibilidade de situações degeneradas nas quais o solucionador global não pode concluir os cálculos em um período de tempo razoável. Infelizmente, este é o resultado inevitável de que a tarefa Minesweeper é NP-complete.

Como o botão "Pedir ajuda" afeta a jogabilidade? Isso leva ao fato de que o jogo se concentra mais na lógica; Esta é a versão mais "intrigante" do "Campo Minado". Alguém pode pensar que o jogo se tornará mais fácil, mas na verdade está se tornando mais complicado. Agora não há desculpas pelos erros do jogador, e o botão o punirá se ele perder alguma coisa. Sem um botão, é fácil concluir que você esgotou todas as possibilidades lógicas e a única opção para o desenvolvimento de eventos é tentar adivinhar aleatoriamente. Mas devido à existência do botão, o jogador deve estar certo nessa avaliação.

Em conclusão

Tendo implementado o solucionador completo do Solver "Campo Minado", pudemos criar uma variação do jogo livre de sua maldição: agora é impossível perder devido ao fato de que você deve escolher por acaso quando já tiver quase decidido todo o campo. Esta versão difere do jogo original apenas nos momentos em que você precisa adivinhar aleatoriamente, então posso assumir que é muito mais divertido que o jogo original.

Além disso, desenvolvemos uma versão do jogo que resolve automaticamente regras locais simples. A decisão de usar essa ajuda depende de você. Ele muda o foco do jogo do clique mecânico para uma jogabilidade mais intrigante. Ao mesmo tempo, não é necessário usar o aprimoramento da jogabilidade fornecido pelo botão "Pedir ajuda".