Como (quase) sempre ganhar no Campo Minado - Parte 1

Este post marca o início de uma série de postagens onde nosso objetivo será desenvolver algoritmos capazes de ganhar um jogo de campo minado, sem depender tanto da sorte. Nesta primeira parte, irei apresentar do que se trata o Campo Minado e uma modelagem que irá nos apresentar o fascinante mundo dos Constraint Satisfaction Problems(CSPs), e em especial, técnicas de Otimização Inteira.

Durante esta série, irei apresentar um pouco sobre a teoria dos CSPs e mostrar como aplicá-la para resolver outros jogos de puzzle - e, quando tivermos maturidade para isso - finalmente iremos implementar o que aprendemos no Campo Minado.

Sobre o Jogo

O Campo Minado trata-se de um jogo onde o jogador tem a difícil missão de revelar as células do tabuleiro sem cair numa mina. Cada célula pode ser revelada ao ser clicada, e caso seja uma bomba, o jogo acaba. Se, por outro lado, não houver uma bomba na célula escolhida, uma das duas coisas podem acontecer:

• Um número aparece, indicando a quantidade de bombas adjacentes a célula escolhida existem
• Nenhum número aparece na célula escolhida. Neste caso, a célula escolhida não possui bombas adjacentes e o jogo irá revelar todas as células vizinhas á escolhida de modo que todas as novas células reveladas contenham números

O jogo pode ter uma quantidade de linhas, colunas e bombas variadas, possibilitando que uma enorme quantidade de configurações existam.

Na prática, não é necessário que o jogador tente adivinhar exatamente todas as células seguras, já que, caso ele encontre uma célula sem bombas adjacentes, uma região pode ser revelada. Além disso, as informações sobre bombas adjacentes permitem inferir possíveis localizações de bombas, embora ainda seja necessário algum fator de sorte.

Como resolver

Antes de tentarmos realizar qualquer tipo de modelagem, vamos primeiro exibir um exemplo, e observar o tipo de raciocínio que naturalmente desenvolvemos para resolver este tipo de puzzle.
Para isso, suponha que tenhamos um tabuleiro 4x4, e que sabemos que há duas bombas no tabuleiro. Inicialmente, ele terá todas as suas células escondidas, desta forma:

O nosso primeiro movimento será tentar, na sorte, revelar algumas células. Se clicarmos na célula na linha 1 e coluna 1, ou seja, (1,1). Teríamos algo do tipo:

Apenas com um clique, conseguimos restringir a quantidade de células ocultas para a última linha, apenas. Note que agora, temos mais informação sobre o tabuleiro, e já é possível determinar onde estão as duas bombas:

Primeiro, vamos estruturar todas afirmações que sabemos que são verdadeiras:

1. Se existe uma bomba adjacente á (3,1), então deve ter uma bomba entre (4, 1); (4,2)
2. Se existem duas bombas adjacentes a (3,2), então, devem haver duas bombas entre (4,1);(4,2);(4,3)
3. Se existe uma bomba adjacente a (3,3), então, deve haver uma bomba entre (4,2);(4,3);(4,4)
4. Se existe uma bomba adjacente a (3, 4), então, deve haver uma bomba entre (4,3);(4,4)

• De (1) e (2), podemos inferir que se há apenas uma bomba entre (4, 1); (4,2) e duas entre (4,1);(4,2);(4,3), então é certo que há uma bomba em (4,3).
• Agora, sabemos de (3) que há uma bomba entre (4,2);(4,3);(4,4). Mas já concluímos que existe uma bomba em (4,3). Segue que (4,2) e (4,3) são células seguras.
• Finalmente, nos resta dizer que a última bomba só pode estar em (4,1), o que resolve o jogo.

Este tipo de argumento é bastante utilizado em demonstração de teoremas na matemática: Partimos de um conjunto de afirmações e desenvolvemos um argumento lógico que nos permite inferir onde estarão as bombas. Em alguns casos, mesmo com um argumento como este, ainda não somos capazes de encontrar soluções aparentes, ou apenas inferir que as bombas poderão estar num conjunto específico de células.

Mas por que este tipo de argumentação funciona, afinal?

A partir de uma configuração inicial, existem uma quantidade de soluções viáveis para o jogo, ou seja, existem uma quantidade indeterminada de lugares onde as bombas podem estar.
Ao adicionarmos afirmações sobre o tabuleiro, a partir das células que conseguimos revelar, estamos na verdade restringindo o conjunto de soluções viáveis para o tabuleiro.
A partir destas restrições podemos ou encontrar células seguras, ou até mesmo restringir o conjunto de solução a uma configuração em particular, como fizemos.

Uma modelagem inicial

A partir disso, vamos tentar determinar uma modelagem pra este tipo de problema, e desenvolver um método que possa ser utilizado por computadores, baseado no raciocínio que desenvolvemos anteriormente. Para facilitar a comunicação, vamos fixar uma notação e algumas definições.

Definição: Tabuleiro de Campo Minado
Podemos pensar o Campo Minado como uma grade com $n$ linhas e $m$ colunas. Cada posição, localizada na linha $i$ e coluna $j$ , será representada por $a_{ij}$ . Dentro dessa grade, existe um conjunto especial $\mathbb{B}$ , chamado de Conjunto de Bombas, que contém exatamente $k$ elementos (desconhecidos a priori) — as temidas bombas.

Além disso, dado um tabuleiro de Campo Minado, vamos definir algumas operações:

• Número de bombas vizinhas:

  Para uma célula $a_{ij}$ , dizemos que

  $$ADJ(a_{ij}) = p$$

  onde $p$ é a quantidade de bombas que estão nas células adjacentes a $a_{ij}$ .

• Verificar se é bomba:

  Para uma célula $a_{ij}$ , dizemos que

  $$isBomb(a_{ij}) = \begin{cases} 1 &\text{se }a_{ij} &\text{é uma bomba} \\ 0 &\text{caso contrário} \end{cases}$$

Com este formalismo, podemos modelar as afirmações que tínhamos no exemplo anterior da seguinte forma sejam:

$$x_{1} = isBomb(a_{41}) \\ x_{2} = isBomb(a_{42}) \\ x_{3} = isBomb(a_{43}) \\ x_{4} = isBomb(a_{44}) \\\$$

Então:

$$\begin{cases} x_{1} + x_{2} = 1 &\text{(i)} \\ x_{3} + x_{4} = 1 &\text{(ii)} \\ x_{1} + x_{2} + x_{3} = 2 &\text{(iii)} \\ x_{2} + x_{3} + x_{4} = 1 &\text{(iv)} \\ \end{cases}$$

Tal sistema pode ser resolvido assim como qualquer outro, mas lembrando que uma particular variável pode apenas ser zero ou um:

De (i) temos: $x_1 + x_2 = 1$
e de (ii): $x_1 + x_2 + x_ 3 = 2$ .
Segue: $1 + x_3 = 2 \therefore x_3 = 1 (*)$

De (iv): $x_2 + x_3 + x_4 = 1$
De $(*)$ : $x_3 = 1$ , logo $x_2+x_4 + 1 = 1 \therefore x_2 = x_4 = 0$ $(**)$
Finalmente, de (i) $x_1 + x_2 = 1$ e de $(**)$ , $x_2 = 0$ , logo $x_1 = 1$
Portanto, vemos que as bombas estão em (4,1) e (4,3)

No sistema acima, falta adicionarmos uma restrição que também conhecemos:

$$\sum_{i=1}^{4}\sum_{j=1}^{4}isBomb(a_{ij}) = 2$$

Essa condição basicamente nos diz que o total de bombas no tabuleiro é igual a 2. Chamamos esta de Restrição Global
Muitas vezes, utilizamos esta restrição de forma indireta, mas ela sempre nos ajuda remover variáveis desnecessárias.

Conclusão

Como podemos ver, esta modelagem nos fornece uma forma algorítmica de reproduzir o raciocínio que aplicamos intuitivamente, mas agora de maneira formal e matemática. Ao escrever o problema como um sistema de equações (não lineares), podemos utilizar nosso conhecimento matemático para restringir o conjunto de soluções possíveis. Por exemplo, a partir da restrição global, identificamos conjuntos de células que podem conter bombas e outras que são certamente seguras. Conforme exploramos mais o tabuleiro, esse conjunto se torna cada vez mais restrito, aproximando-nos da solução exata.

Espero que este exemplo tenha mostrado como um problema aparentemente simples, como o Campo Minado, pode se tornar um estudo fascinante de lógica, matemática e algoritmos. No próximo post, vamos conectar essas ideias com CSPs (Constraint Satisfaction Problems) e mostrar como aplicá-las para resolver problemas de coloração de mapas — preparando você para pensar de forma estruturada, quase como um computador.