🧤 🍀 🍺 Kaboom: un sapeur insolite 🚌 👨🏾‍🎓 🕴🏿

Enfant, je me suis assis au travail de mon père trois fois par semaine pendant une heure et demie. On m'a permis d'aller à un ordinateur, où du divertissement il n'y avait qu'un sapeur et Paint. J'étais fatigué de dessiner rapidement, mais le désir d'ouvrir tout le terrain et de ne pas exploser m'a motivé à chercher de nouvelles et nouvelles façons de jouer à ce jeu. Plusieurs années plus tard, je suis tombé accidentellement sur un article intéressant sur un clone d'un sapeur et je n'ai pas pu passer. Je vous suggère de vous familiariser avec cela. Il s'agit d'une histoire sur le développement de Kaboom, un clone du légendaire jeu de démineur avec son propre zeste.

Le démineur est apparu il y a assez longtemps selon les normes d'un jeu sur ordinateur. Mais il me semble que la plupart des gens se souviennent des jeux qui faisaient partie des versions antérieures de Windows. Je n'ai jamais été bon au démineur, mais je l'ai joué de temps en temps. Certaines personnes jouent plus sérieusement . Et pour ceux qui veulent se réconforter, je recommande de regarder Démineur - Le film .

Idée

Récemment, j'ai eu une idée: que faire si vous devez jouer au démineur contre un ordinateur plus sage?

En règle générale, l'emplacement des mines est déterminé au début du jeu (mais il y a quelques astuces ici - par exemple, vous ne pouvez donc pas perdre le premier clic). Mais que faire si l'emplacement des mines n'avait pas été déterminé à l'avance et que le jeu aurait pu choisir l'emplacement des mines après le début du jeu?

Ce serait assez cruel: si vous cliquez sur un carré qui peut contenir une mine, il la contiendra toujours! Ainsi, vous devez prouver à l'avance que le carré est sûr.

Dans l'image ci-dessus, dans les cellules marquées d'un point, il n'y a aucune mine garantie, et les cellules marquées d'un point d'exclamation sont garanties d'en contenir une. Les points d'interrogation signifient une incertitude: peut-être que si vous ouvrez plus de cellules, vous pouvez calculer si une mine y est cachée ou non.

Par contre, il y a des situations où vous devez deviner:

il y a une mine dans l'une des cellules inférieures. Mais dans lequel, il est impossible de comprendre. Vous devez en choisir un. Mais selon la condition dont je viens de parler, cela signifierait une mort certaine! Je voulais que le jeu soit brutal, mais maintenant il est évidemment en train de perdre.
Par conséquent, je changerai légèrement l'idée. Vous pouvez deviner, mais seulement s'il n'y a plus de cellules sûres. Ainsi, le jeu sera cruel, mais juste.

En d'autres termes:

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

Comment implémenter un tel jeu? Je pourrais essayer de calculer tous les champs possibles, mais ce n'est pas réaliste: même un petit champ de 10x10 signifie 2 ^ 100 possibilités. Ne sélectionner que ceux qui contiennent exactement N min n'aide pas.

Heureusement, je n'ai pas besoin de m'inquiéter pour tout le domaine. Nous ne savons rien des mines terrestres non adjacentes aux étiquettes. Je ne m'intéresse qu'à ceux qui sont à la frontière, le reste peut être déterminé tout à fait par accident.

Ensuite, je peux calculer toutes les options pour l'emplacement des mines à la frontière conformément aux étiquettes. Backtracking (backtracking) - une bonne technique qui vous permet de trier toutes les combinaisons, mais aussi de reculer rapidement dès que l'on détermine qu'une branche ne peut pas calculer.

Les deux emplacements possibles des mines à la frontière sont indiqués ci-dessus. En les combinant, nous comprendrons quelles cellules sont garanties d'être vides ou extraites.

J'ai également besoin de suivre le nombre total de mines. Ainsi, l'emplacement ressemble vraiment à «5 min à la frontière, 5 min à l'extérieur». C'est important car sinon j'aurais pu créer trop de mines à la frontière (ou trop peu!)

Donc, j'ai toutes les options. Que se passe-t-il lorsqu'un joueur décide d'ouvrir une cage?

Choisissez une option aléatoire (qui satisfait aux règles «cruelles mais justes»). Cela permettra de déterminer l'emplacement des mines à la frontière.
Dispersez au hasard ceux qui restent à l'extérieur de la frontière.
S'il y a une mine dans la cellule sélectionnée, la partie est terminée.
Autrement:
1. Définir une nouvelle étiquette pour la cellule identifiée
2. Révéler des cellules supplémentaires s'il est égal à 0
3. , ! .

Pour les petits champs, c'est normal. Habituellement, il n'y a que quelques combinaisons possibles ... attendez, c'est quoi?

Oh non!

D'une manière ou d'une autre, j'ai réussi à débloquer 18 millions d'emplacements de mines possibles. Mon Firefox dévore 12 gigaoctets de mémoire et il faut une demi-minute pour ouvrir la cellule. Évidemment, j'ai besoin d'un meilleur algorithme.

Quelqu'un peut remarquer que Démineur est un jeu complet NP , et donc un temps qui augmente de façon exponentielle ne peut pas être évité. Et dans le cas général, cela est vrai - il y aura des positions qui prendront beaucoup de temps à calculer. Mais pour une petite zone, cela fonctionne.

Je n'ai pas besoin de me souvenir de toutes les combinaisons. Je n'ai même pas besoin de calculer toutes les combinaisons. Tout ce qui est nécessaire est un moyen:

vérifier si la cellule est sûre, dangereuse ou vague,
(, , ).

Au lieu d'essayer les options moi-même, je vais utiliser le solveur SAT . Ce sont des outils qui prennent une formule composée de variables logiques et recherchent un ensemble de valeurs qui rendraient la formule vraie. Une telle méthode imaginaire, mais tout à fait valable pour notre tâche.

Une classe de logiciels plus puissante est constituée par les solveurs SMT qui fonctionnent avec une plus large gamme de valeurs et de formules, telles que la logique du premier ordre (quantificateurs), les tableaux, les entiers, etc. Cela aidera au moins à définir certaines équations pour les entiers. Mais j'ai besoin de quelque chose qui fonctionne dans le navigateur. Les gens ont réussi à porter certains outils sophistiqués comme Z3Prover sur le navigateur, mais la version WebAssembly pèse17 Mo , et c'est trop.

J'ai trouvé MiniSat , un petit solveur SAT qui a été compilé pour Javascript par Joel Galenson. Le fichier compilé ne prend que 200 kilo-octets, donc je l'utilise.

Formules CNF

Les solveurs SAT fonctionnent avec des formules normales conjonctives ( CNF ). La formule de CNF est «un ET de OU», par exemple:

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

vous pouvez convertir n'importe quelle formule de logique de phrase (variables, et, ou non, implication) en CNF, c'est donc une sorte de format universel.

Comment l'utilisons-nous? Supposons que nous ayons un tableau: si je crée des variables pour des cellules inconnues (dans le sens horaire: x1, x2, x3), elles devront satisfaire les équations suivantes: Mais comment exprimer «la somme des variables est 2» en CNF? J'ai trouvé une méthode qui, comme je l'ai appris plus tard, est appelée «codage binomial» et est le codage le plus simple. Vous devez considérer tous les sous-ensembles possibles de variables. Par exemple, pour vous avez besoin des formules suivantes:

? ? 1
2 ? 1

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

x1 + x2 + x3 = 2

Pour chaque sous-ensemble de 2 variables, au moins une est vraie. Cela garantit que le montant est supérieur à 1.
(x1 | x2) & (x1 | x3) & (x2 | x3)
Au moins une variable est fausse. Cela garantit que le montant est inférieur à 3.
(~ x1 | ~ x2 | ~ x3)

Pour x2 + x3 = 1moi, j'ai besoin d'un ensemble similaire de formules:

Au moins une des variables est correcte: (x2 | x3)
Au moins une des variables est fausse (~ x2 | ~ x3).

En combinant cela, j'obtiens une formule CNF avec 6 points. Au format DIMACS standard: toutes les lignes de position se terminent par 0 et la négation est marquée d'un moins. Si je le connecte à MiniSat (essayez par vous-même), j'obtiens: Cela signifie que MiniSat a trouvé une solution où x1 et x2 sont vraies et x3 sont fausses. Voici à quoi ressemblera le tableau: L'ensemble du programme est un peu plus compliqué: ce n'est qu'une solution, il y en a une autre. Par conséquent, pour savoir si x1, x2, x3 peuvent être vrais (ou faux), vous devez effectuer plus de demandes. Je dois demander: «Étant donné la formule ci-dessus, ainsi que x1, est-ce possible? Que diriez-vous de la formule ci-dessus, ainsi que ~ x1 "?

SAT 1 2 -3

! ! 1
2 . 1

L'encodage signifie que je dois trouver toutes les combinaisons possibles (par exemple, tous les sous-ensembles de 3) d'un ensemble de variables. Cependant, pour cette équation, il n'y aura que 8 variables, donc la formule est généralement assez petite pour que MiniSat puisse la résoudre rapidement.

Suivi min

Malheureusement, ce n'est pas une solution complète! J'ai encore besoin de savoir combien il reste de mines. Certaines combinaisons sont impossibles, car sinon vous pouvez créer plus de mines que ce qui est autorisé, et il sera impossible de gagner.

En fait, le cas contraire est également possible: s'il y a trop peu de mines, le jeu se terminera, car il n'y aura rien à placer.

Par conséquent, je dois indiquer dans la formule SAT que «le nombre de mines n'est pas inférieur à X et pas supérieur à Y». Au début, je pensais pouvoir utiliser l'astuce avec toutes les combinaisons. Malheureusement, cela ne fonctionne pas trop bien avec de grands nombres. S'il y a, disons, 20 cellules et 10 min, alors après avoir connecté les nombres au coefficient binomial, nous découvrons que le nombre de combinaisons est déjà à 6 chiffres!

J'ai donc découvert qu'il existe de nombreuses autres façons de coder la somme des variables dans la formule SAT. Vous devez créer un schéma qui combinera les variables individuelles. Voir, par exemple, cette réponse sur StackExchange ou celle-ci .

Finalement, j'ai réalisé l'idée d'un article intitulé «Codage CNF efficace avec des contraintes de cardinalité booléennes», écrit par Olivier Baillot et Yasin Bufhad. Nous voyons un arbre qui ajoute récursivement des nombres unaires (ou trie les bits pour que tout le monde soit au début):

À la fin de ce diagramme, vous obtiendrez un ensemble trié de variables de «sortie». Pour confirmer que la somme n'est pas inférieure à X, vérifiez que les premiers X des variables résultantes sont 1. Pour affirmer que la somme n'est pas supérieure à Y, vérifiez que les derniers N - Y des variables résultantes sont 0.

C'est bien mieux que d'utiliser toutes les combinaisons possibles, cependant, ce schéma est toujours irrationnel car il génère des phrases Ө (N ^ 2). Lorsque le nombre de cellules ouvertes est d'environ 100, le jeu devient lent. Nous pouvons optimiser davantage le jeu.
Réduisez les demandes

En étudiant le problème, j'ai remarqué que je pouvais réduire le nombre de requêtes au solveur. Je voulais déterminer l'état de toutes les cellules (c'est-à-dire vérifier si elles sont garanties dangereuses, sûres ou non). Je l'ai fait en utilisant une simple boucle. Disons que la planche est décrite par la formule F:

Décidez F & ~ x1de vérifier si x1 peut être 0
Décidez F & x1de vérifier si x1 peut être 1
Décidez F & ~ x2 de vérifier si x2 peut être égal à 0
Décidez F & x2de vérifier si x2 peut être 1
Etc.

Qu'est-ce que j'ai remarqué? Si j'obtiens une solution pour F & ~ x1, elle contiendra également les valeurs de toutes les autres variables. Cela répond déjà à de nombreuses autres questions: si la solution contient x2 = 0, je n'ai pas besoin de demander si x2 peut être 0, car je le sais déjà. Cela me permet de réduire le nombre de demandes d'environ 2 à 5 fois.

Mise en cache

Cela ne résout pas le problème de l'énorme formule générée par le circuit de "comptage". Comme je l'ai dit, le nombre de phrases est de l'ordre de N ^ 2. Sur un grand tableau, la formule peut aller jusqu'à 10 000 hypothèses.

Heureusement, la plupart du temps, nous connaissons la signification exacte de nombreuses cellules. Si la cellule est garantie vide ou remplie garantie, la valeur ne changera jamais! Cela signifie que nous pouvons le mettre en cache et ne pas l'inclure dans la formule SAT. Une fois que nous aurons déterminé l'état de la cellule, nous n'aurons plus besoin de l'inclure à nouveau dans le calcul. Les cellules seront utilisées tant qu'elles ne sont pas définies.

Cette optimisation est légèrement dangereuse: nous n'avons plus de formule confirmant l'exactitude de l'ensemble de la planche. Si tout le reste fonctionne comme prévu, ce n'est pas un problème, mais cela peut compliquer le suivi des erreurs.

Un autre cas: jouer à l'étranger

Êtes-vous autorisé à cliquer n'importe où sur la carte en dehors de la frontière entre la zone ouverte et non ouverte du champ?

Au départ, je pensais que c'était la même chose que de deviner: s'il n'y a pas de cellules sûres, vous pouvez simplement cliquer n'importe où sur le champ. Mais certains trouvent étrange que cela garantisse l'ouverture d'une cage vide.

J'ai donc changé le jeu pour qu'un clic hors de la frontière soit toujours puni. À l'exception du début du jeu, bien sûr, car alors tout le plateau est «à l'extérieur».

Mais il s'avère qu'il existe un autre scénario: que faire si tous les champs frontaliers sont mortels? Vous n'avez pas d'autre choix que de révéler autre chose. Cette situation peut rendre le jeu infranchissable dès le départ. Alors maintenant, il y a encore une exception. Vous êtes autorisé à jouer en dehors des frontières si:

3 . .
. . .
. . .

Le champ n'est pas ouvert
Les cellules minées peuvent être situées à la frontière (cliquer sur l'extérieur devrait être sûr), ou
Il doit y avoir des bombes dans toutes les cellules de la frontière (il faut cliquer à l'extérieur).

Mise à jour : Le changement s'est avéré controversé, car la restriction est quelque peu artificielle. J'ai ajouté un interrupteur qui permettra / interdira de jouer avec ces conditions.

C'est tout

Vous pouvez jouer à Kaboom ici . Essayez d'activer le mode de débogage: cela rend le jeu trivial, mais il montre bien comment cela fonctionne.

Code source Github . Il n'est pas très beau.

Vous pourriez également être intéressé par un jeu similaire de Simon Tatham, créateur de PuTTY. Sa version a une tournure différente: il est toujours résoluble sans spéculation.

Jouez sagement!

Quoi d'autre peut être utile à lire sur le blog Cloud4Y

→ Comment la banque s'est «cassée»
→ Confidentialité personnelle? Non, ils n'ont pas entendu
→ La grande théorie des flocons de neige
→ Diagnostic des connexions réseau sur un routeur EDGE virtuel
→Les virus résistants aux CRISPR construisent des abris pour protéger les génomes des enzymes pénétrant l'ADN.

Abonnez-vous à notre chaîne Telegram pour ne manquer aucun autre article! Nous écrivons pas plus de deux fois par semaine et uniquement pour affaires. Nous vous rappelons que les startups peuvent obtenir 1 million de roubles. de Cloud4Y. Conditions générales pour ceux qui le souhaitent - sur notre site Web: bit.ly/2sj6dPK