🍁 🔷 💑 Kaboom: um sapador incomum 🚐 🦀 👊🏼

Quando criança, sentei-me no trabalho de meu pai três vezes por semana, durante uma hora e meia. Eu tinha permissão para ir a um computador, onde, no entretenimento, havia apenas um sapador e um Paint. Eu estava cansado de desenhar rapidamente, mas o desejo de abrir todo o campo e não explodir me motivou a procurar novas e novas maneiras de jogar este jogo. Muitos anos depois, acidentalmente me deparei com um artigo interessante sobre um clone de um sapador, e não consegui passar. Eu sugiro que você se familiarize com isso. Esta é uma história sobre o desenvolvimento do Kaboom, um clone do lendário jogo Minesweeper com seu próprio entusiasmo.

Campo Minado apareceu há muito tempo pelos padrões de um jogo de computador. Mas parece-me que a maioria das pessoas lembra dos jogos que faziam parte das versões anteriores do Windows. Eu nunca fui bom no Campo Minado, mas jogava de vez em quando. Algumas pessoas jogam mais a sério . E para quem quer se animar, recomendo assistir Minesweeper - The Movie .

Idéia

Recentemente, tive uma ideia: e se você tivesse que jogar o Campo Minado contra um computador mais sábio?

Normalmente, a localização das minas é determinada no início do jogo (mas há alguns truques aqui - por exemplo, para que você não perca o primeiro clique). Mas e se a localização das minas não fosse determinada com antecedência e o jogo pudesse escolher a localização das minas após o início do jogo?

Isso seria muito cruel: se você clicar em um quadrado que pode conter uma mina, ela sempre a conterá! Assim, você deve provar antecipadamente que o quadrado é seguro.

Na imagem acima, nas células marcadas com um ponto, não há minas garantidas, e as células marcadas com um ponto de exclamação têm garantia de conter uma. Pontos de interrogação significam incerteza: talvez se você abrir mais células, você pode calcular se uma mina está escondida lá ou

não.Por outro lado, há situações em que você deve adivinhar:

existe uma mina em uma das células inferiores. Mas em qual deles é impossível entender. Você deve escolher um deles. Mas de acordo com a condição de que acabei de falar, isso significaria morte certa! Eu queria que o jogo fosse brutal, mas agora está obviamente perdendo.
Portanto, vou mudar um pouco a ideia. Você pode adivinhar, mas apenas se não houver células seguras. Assim, o jogo será cruel, mas justo.

Em outras palavras:

, .
, , .
, :
1. , , .
2. , , .

Como implementar esse jogo? Eu poderia tentar calcular todos os campos possíveis, mas isso não é realista: mesmo um pequeno campo 10x10 significa 2 ^ 100 possibilidades. Selecionar apenas aqueles que contêm exatamente N min não ajuda.

Felizmente, não preciso me preocupar com todo o campo. Não sabemos nada sobre minas terrestres não adjacentes a tags. Eu só estou interessado naqueles que estão na fronteira, o resto pode ser determinado por acidente.

Então eu posso calcular todas as opções para a localização das minas na fronteira, de acordo com os rótulos. Backtracking (backtracking) - uma boa técnica que permite classificar todas as combinações, mas também recuar rapidamente assim que determinarmos que um ramo não pode calcular.

O exemplo acima mostra dois locais possíveis de minas na fronteira. Combinando-os, entenderemos quais células são garantidas como vazias ou extraídas.

Eu também preciso rastrear o número total de minas. Assim, a localização realmente se parece com "5 min na fronteira, 5 min fora". Isso é importante porque, caso contrário, eu poderia ter criado muitas minas na fronteira (ou muito poucas!).

Portanto, tenho todas as opções. O que acontece quando um jogador decide abrir uma gaiola?

Escolha uma opção aleatória (que atenda às regras "cruéis, mas justas"). Isso determinará a localização das minas na fronteira.
Espalhe aleatoriamente os que ficam fora da fronteira.
Se houver uma mina na célula selecionada, o jogo acabou.
De outra forma:
1. Definir um novo rótulo para a célula identificada
2. Revele células adicionais se for 0
3. , ! .

Para campos pequenos, isso é normal. Normalmente existem apenas algumas combinações possíveis ... espere, o que é isso?

Ah não!

De alguma forma, consegui desbloquear 18 milhões de locais possíveis. Meu Firefox devora 12 gigabytes de memória e abrir uma célula leva meio minuto. Obviamente, preciso de um algoritmo melhor.

Alguém pode notar que o Campo Minado é um jogo completo de NP e , portanto, um tempo exponencialmente crescente não pode ser evitado. E, no caso geral, isso é verdade - haverá posições que levarão muito tempo para serem calculadas. Mas para uma pequena área isso funciona.

Não preciso me lembrar de todas as combinações. Eu nem preciso calcular todas as combinações. Tudo o que é necessário é uma maneira:

verifique se a célula é segura, perigosa ou vaga,
(, , ).

Em vez de experimentar as opções eu mesmo, vou usar o solucionador SAT . Essas são ferramentas que usam uma fórmula que consiste em variáveis lógicas e procuram um conjunto de valores que tornariam a fórmula verdadeira. Um método tão imaginário, mas bastante válido para nossa tarefa.

Uma classe de software mais poderosa são os solucionadores SMT que trabalham com uma gama mais ampla de valores e fórmulas, como lógica de primeira ordem (quantificadores), matrizes, números inteiros e assim por diante. Isso ajudará pelo menos a definir algumas equações para números inteiros. Mas preciso de algo que funcione no navegador. As pessoas conseguiram portar algumas ferramentas sofisticadas como o Z3Prover para o navegador, mas a versão WebAssembly pesa17 MB , e isso é demais.

Encontrei o MiniSat , um pequeno solucionador SAT que foi compilado para Javascript por Joel Galenson. O arquivo compilado ocupa apenas 200 kilobytes, então eu o uso.

Fórmulas CNF

Os solucionadores SAT trabalham com fórmulas normais conjuntivas ( CNFs ). A fórmula da CNF é "um AND de ORs", por exemplo:

(a | ~ b | ~ c) & (c | d ~ e) & f

você pode converter qualquer fórmula da lógica de sentenças (variáveis e, ou, não, implicação) em CNF, portanto é um formato universal.

Como usamos? Suponha que tenhamos um quadro: Se eu criar variáveis para células desconhecidas (no sentido horário: x1, x2, x3), elas terão que satisfazer as seguintes equações: Mas como expressar "a soma das variáveis é 2" no CNF? Encontrei um método que, como aprendi mais tarde, é chamado de "codificação binomial" e é a codificação mais simples. Você deve considerar todos os possíveis subconjuntos de variáveis. Por exemplo, para você precisar das seguintes fórmulas:

? ? 1
2 ? 1

1 + 2 + 3 = 2
2 + 3 = 1
2 + 3 = 1 ( )

x1 + x2 + x3 = 2

Para cada subconjunto de 2 variáveis, pelo menos uma é verdadeira. Isso garante que a quantidade seja maior que 1.
(x1 | x2) & (x1 | x3) & (x2 | x3)
Pelo menos uma variável é falsa. Isso garante que o valor seja menor que 3.
(~ x1 | ~ x2 | ~ x3)

Para x2 + x3 = 1mim, preciso de um conjunto semelhante de fórmulas:

Pelo menos uma das variáveis está correta: (x2 | x3)
Pelo menos uma das variáveis é falsa (~ x2 | ~ x3).

Ao combinar isso, recebo uma fórmula CNF com 6 pontos. No formato DIMACS padrão: Todas as linhas de posição terminam com 0 e a negação é marcada com menos. Se eu conectá-lo ao MiniSat (tente você mesmo), obtenho: Isso significa que o MiniSat encontrou uma solução em que x1 e x2 são verdadeiros e x3 são falsos. Eis como será o quadro: Todo o programa é um pouco mais complicado: essa é apenas uma solução, existe outra. Portanto, para descobrir se x1, x2, x3 podem ser verdadeiros (ou falsos), é necessário fazer mais solicitações. Eu preciso perguntar: “Dada a fórmula acima, assim como x1, isso é viável? Que tal a fórmula acima, bem como ~ x1 "?

SAT 1 2 -3

! ! 1
2 . 1

Codificação significa que eu preciso encontrar todas as combinações possíveis (por exemplo, todos os subconjuntos de 3) de um conjunto de variáveis. No entanto, para esta equação, haverá apenas 8 variáveis; portanto, a fórmula geralmente é pequena o suficiente para que o MiniSat possa resolvê-la rapidamente.

Rastreamento mínimo

Infelizmente, esta não é uma solução completa! Ainda preciso rastrear quantas minas restam. Algumas combinações são impossíveis, porque, caso contrário, você pode criar mais minas do que o permitido, e será impossível ganhar.

De fato, o caso oposto também é possível: se houver muito poucas minas, o jogo terminará, porque não haverá nada para colocar.

Portanto, preciso indicar na fórmula do SAT que "o número de minas não é menor que X e não é maior que Y". No começo, pensei que poderia usar o truque com todas as combinações. Infelizmente, não funciona muito bem com grandes números. Se houver, digamos, 20 células e 10 min, depois de conectar os números ao coeficiente binomial, descobrimos que o número de combinações já é de 6 dígitos!

Então eu descobri que existem muitas outras maneiras de codificar a soma de variáveis na fórmula SAT. Você precisa criar um esquema que combine as variáveis individuais. Veja, por exemplo, esta resposta no StackExchange ou nesta .

No final, percebi a ideia em um artigo intitulado "Código efetivo da CNF com restrições de cardinalidade booleana", escrito por Olivier Baillot e Yasin Bufhad. Vemos uma árvore que adiciona recursivamente números unários (ou classifica bits para que todos estejam no começo):

No final deste diagrama, você obterá um conjunto classificado de variáveis de "saída". Para confirmar que a soma não é menor que X, verifique se o primeiro X das variáveis resultantes é 1. Para afirmar que a soma não é maior que Y, verifique se o último N - Y das variáveis resultantes é 0.

Isso é muito melhor do que usar todas as combinações possíveis, no entanto, esse esquema ainda é irracional porque gera sentenças Ө (N ^ 2). Quando o número de células abertas é de cerca de 100, o jogo fica lento. Podemos otimizar ainda mais o jogo.
Reduzir solicitações

Ao estudar o problema, notei que posso reduzir o número de consultas ao solucionador. Eu queria determinar o status de todas as células (ou seja, para verificar se elas são perigosas, seguras ou não). Eu fiz isso usando um loop simples. Digamos que o quadro seja descrito pela fórmula F:

Decida F & ~ x1verificar se x1 pode ser 0
Decida F & x1verificar se x1 pode ser 1
Decida F & ~ x2 verificar se x2 pode ser 0
Decida F & x2verificar se x2 pode ser 1
Etc.

O que eu notei? Se eu conseguir uma solução para F & x1, ela também conterá os valores de todas as outras variáveis. Isso já responde a muitas outras perguntas: se a solução contém x2 = 0, não preciso perguntar se x2 pode ser 0, porque já sei disso. Isso me permite reduzir o número de solicitações em cerca de 2 a 5 vezes.

Armazenamento em cache

Isso não resolve o problema da enorme fórmula gerada pelo circuito de "contagem". Como eu disse, o número de sentenças é da ordem de N ^ 2. Em um quadro grande, a fórmula pode ter até 10.000 suposições.

Felizmente, na maioria das vezes sabemos o significado exato de muitas células. Se a célula estiver garantida vazia ou garantida, o valor nunca será alterado! Isso significa que podemos armazená-lo em cache e não incluí-lo na fórmula SAT. Depois de determinar o estado da célula, não será mais necessário incluí-lo no cálculo novamente. As células serão usadas desde que não estejam definidas.

Essa otimização é um pouco perigosa: não temos mais uma fórmula que confirme a exatidão de todo o quadro. Se tudo funcionar como planejado, isso não é um problema, mas pode complicar o rastreamento de erros.

Outro caso: jogar no exterior

Você pode clicar em qualquer lugar do mapa fora da fronteira entre a área aberta e a fechada do campo?

Inicialmente, pensei que era o mesmo que adivinhar: se não houver células seguras, você pode simplesmente clicar em qualquer lugar do campo. Mas alguns acham estranho que isso garanta a abertura de uma gaiola vazia.

Portanto, mudei o jogo para que um clique fora da borda seja sempre punido. Com exceção do início do jogo, é claro, porque todo o tabuleiro está "fora".

Mas acontece que há outro cenário: e se todos os campos de fronteira forem mortais? Você não tem escolha a não ser revelar outra coisa. Esta situação pode tornar o jogo intransitável desde o início. Então agora há mais uma exceção. Você pode jogar fora das fronteiras se:

3 . .
. . .
. . .

O campo não está aberto
As células minadas podem estar localizadas na borda (clicar do lado de fora deve ser seguro) ou
Deve haver bombas em todas as células na fronteira (você precisa clicar fora).

Atualização : a mudança acabou sendo controversa, pois a restrição é um tanto artificial. Eu adicionei uma opção que permitirá / proíbe jogar com essas condições.

É tudo

Você pode jogar Kaboom aqui . Tente ativar o modo de depuração: torna o jogo trivial, mas mostra bem como ele funciona.

Código fonte do Github . Ele não é muito bonito.

Você pode também estar interessado em um jogo semelhante de Simon Tatham, criador de PuTTY. Sua versão tem uma reviravolta diferente: é sempre solucionável sem especulações.

Jogue com sabedoria!

O que mais pode ser útil para ler no blog do Cloud4Y

→ Como o banco “quebrou”
→ Privacidade pessoal? Não, eles não ouviram
→ A Grande Teoria dos Flocos de Neve
→ Diagnóstico de conexões de rede em um roteador EDGE virtual
→Os vírus resistentes ao CRISPR constroem abrigos para proteger os genomas das enzimas que penetram no DNA.

Assine o nosso canal Telegram para não perder outro artigo! Escrevemos não mais do que duas vezes por semana e apenas a negócios. Lembramos que as startups podem receber 1 milhão de rublos. do Cloud4Y. Termos e condições para quem desejar - em nosso site: bit.ly/2sj6dPK