Démineur est un jeu simple avec des règles simples, mais certaines de ses configurations créent des difficultés intéressantes. Dans cet article, nous allons créer un solveur de démineur avec une complexité croissante, et réfléchir à la façon dont la dynamique du jeu change avec une augmentation progressive du niveau d'aide. Au final, nous développerons une nouvelle version du jeu avec un gameplay beaucoup plus intéressant.
Raisonnement local: zéro mines voisines
Dans le
jeu original , un mécanisme automatique est utilisé: lorsqu'un joueur ouvre une cellule, à côté de laquelle il n'y a pas de mines, le moteur du jeu ouvre toutes les cellules voisines. Cela ne menace pas le jeu, vous pouvez donc laisser l'ordinateur le faire en toute sécurité, et la situation elle-même est immédiatement claire pour le joueur et n'interfère pas avec le gameplay.
Ce raisonnement est complètement local: une seule information de cellule est prise en compte pour décider de la prochaine action.
Il est difficile de trouver une situation dans laquelle le jeu empirerait sans cette aide automatique. Essayez de jouer à un tel jeu pour avoir une idée de comment cela se passe sans ouvrir automatiquement les cellules [dans l'article d'origine, tous les exemples sont interactifs]
:
Considérations locales basées sur l'environnement
Il sera facile pour un nouveau joueur de comprendre que si le nombre de mines voisines, c'est-à-dire le nombre affiché dans la cellule, est égal au nombre de cellules voisines non découvertes, alors toutes ces cellules doivent être des mines, vous devez donc mettre des drapeaux dessus. De même, lorsque le nombre de mines voisines est égal au nombre de drapeaux voisins, les cellules voisines restantes non découvertes doivent être vides.
Dans ces règles, une cellule est prise en compte, ainsi que l'état des cellules voisines (ouvertes / vérifiées).
La mise en œuvre manuelle de ces règles peut être amusante. Si vous ajoutez une minuterie, le joueur commence à apprendre à les appliquer rapidement et avec précision. Cela transforme le Démineur
en un jeu de réaction . Que se passe-t-il si nous automatisons ces règles?
Une telle automatisation a un effet secondaire intéressant - cocher la case peut avoir des conséquences fatales instantanément.
Sinon, nous pouvons rencontrer des situations qui peuvent être divisées en trois catégories:
- Jeux entièrement résolus en appliquant des règles automatiques
- Situations compliquées nécessitant plus de cellules pour raisonner
- États du jeu dans lesquels il n'y a pas de voie logique à suivre - le joueur ne peut choisir que par hasard, éventuellement en tenant compte des probabilités.
La situation 1 semble belle, mais pas particulièrement intéressante si elle se présente trop souvent. De tels jeux seraient-ils meilleurs sans une solution automatique? Peut-être pas; ces jeux sont très simples même lorsqu'ils sont résolus manuellement, et le joueur n'est pas particulièrement intéressé à jouer à des jeux dans lesquels il n'y a pas de difficultés. Bien sûr, il y a toujours des difficultés dans le jeu de réaction: vous devez agir le plus rapidement possible.
La situation 2 me semble très attrayante: nous nous concentrons davantage sur la résolution de conditions logiques, en passant moins de temps sur une visée précise et en appuyant sur les boutons de droite. Cela rend Sapper plus comme un
puzzle actif .
La situation 3 détruit complètement tout le plaisir. Cependant, j'ai entendu dire que certaines personnes aiment jouer à des
jeux au hasard .
Est-il possible de se débarrasser de la situation 3?
Solution complète: raisonnement global
Pour la détection algorithmique de toutes les conditions logiques nécessaires à l'état du jeu, nous devons effectuer une recherche exhaustive de tous les états du jeu.
Le démineur s'est avéré être
une tâche NP-complète . Vous trouverez ci-dessous un exemple petit mais intéressant et illustratif de l'état du jeu, n'ayant qu'une seule solution logique, mais pour la trouver, vous devez prendre en compte l'état du jeu dans son ensemble:
Est-il possible de rechercher tout l'espace d'état du jeu? Combien de variations d'état de
s existe-t-il?
Étant donné:
w = largeur de champ
h = hauteur du champ
k = nombre de minutes
n = wAlors le nombre d'états possibles
s est
Pour les niveaux standard "Débutant", "Amateur" et "Professionnel" cela nous donne:
Nous comprenons qu'une approche naïve est totalement inappropriée ici. Voyons à quoi pourrait ressembler un algorithme naïf et découvrons s'il peut être optimisé en quelque chose qui fonctionne.
Algorithme naïf
La tâche de l'algorithme est de trouver toutes les conditions logiques nécessaires à l'état donné du champ. Il serait difficile de mettre en œuvre cela en examinant attentivement les solutions; l'ordinateur fait un bien meilleur travail en effectuant rapidement un tas d'actions stupides.
Que pouvons-nous faire de «stupides»: générer toutes les permutations possibles des positions des mines pour toutes les mines restantes. Si une telle permutation correspond à tous les nombres ouverts, alors ce sera la bonne solution au jeu. Ensuite, nous étudions toutes les permutations possibles, trouvons toutes les solutions possibles, mais nous ne savons toujours pas laquelle est correcte.
Si, dans toutes les solutions possibles, il y a quelque chose en commun, soit parmi les cellules ouvertes, soit parmi les cellules marquées comme des mines, alors nous comprenons que cette commune devrait faire partie de la bonne décision pour le domaine actuel. Et en fait: il est impossible de créer la bonne solution qui n'a pas de tels éléments correspondants, sinon nous les aurions découverts.
Ainsi, nous pouvons trouver toutes les conditions logiques nécessaires à l'état actuel du champ.
Cellules avec et sans restrictions
L'algorithme ci-dessus a un problème évident: le nombre d'états qu'il doit étudier. Mais toutes les cellules ne sont pas identiques. Les cellules non ouvertes à côté d'un nombre sont évidemment limitées à ce nombre. Nous appellerons ces cellules limitées. Les cellules restantes que nous appellerons illimitées.
Si nous implémentons l'algorithme ci-dessus, mais nous ne chercherons que dans l'espace des états des cellules restreintes, et nous reviendrons dès que nous briserons la restriction, alors dans de nombreux jeux, nous pouvons résoudre toutes les conditions logiques dans un délai raisonnable:
Dans le cas de cellules illimitées, nous ne pouvons pas savoir où se trouvent les mines et, logiquement, nous le savons immédiatement. Cela signifie que vous pouvez les exclure du calcul et ne considérer que l'emplacement des mines à côté des nombres ouverts.
Cependant, nous savons qu'un certain nombre de mines peuvent pénétrer dans de nombreuses cellules illimitées; s'il y a 6 min et 4 cellules restreintes, alors dans les cellules limitées il peut y avoir un maximum de 4 mines, c'est-à-dire qu'au moins 2 minutes doivent être dans des cellules illimitées. Selon la même logique, nous pouvons parfois déterminer que toutes les cellules illimitées doivent être vides ou toutes contenir des mines.
Dans le cas illustré ci-dessous, nous connaissons la position de toutes les mines, donc l'IA devrait être en mesure de comprendre que les cellules restantes ne sont pas occupées:
Dans le cas suivant, nous ne connaissons pas la position de toutes les mines, mais nous pouvons comprendre que la mine restante doit être placée dans l'une des deux cellules en haut à gauche. Cela signifie que la cellule restante dans le coin inférieur droit est libre:
Version aléatoire
Si nous exécutons automatiquement le solveur global, nous obtiendrons une version optimisée au hasard de Démineur:
Vous pouvez diviser les jeux de cette version en trois catégories:
- Jeux dans lesquels le joueur fait des choix arbitraires et gagne.
- Jeux dans lesquels le joueur fait des choix arbitraires et perd.
- Les jeux dans lesquels l'IA nécessite beaucoup de temps, et le joueur peut réellement utiliser le raisonnement.
Évidemment, c'est un jeu de hasard. Quel est l'attrait de tels jeux? En termes de logique, le jeu ci-dessus est similaire à ceci:
Mais quel jeu aléatoire est le meilleur? Il semble que le sens des autres jeux aléatoires réside dans l'existence d'une relation complexe entre les actions du joueur et gagner / perdre. Pour dessiner des numéros de loterie, on utilise des machines complexes qui ne sont pas pressées de sélectionner un numéro et de faire un spectacle complet en montrant ce numéro.
Peut-être qu'un grand champ qui est décidé automatiquement est un très bon jeu
avec un caractère aléatoire, étant donné que le joueur regarde l'ouverture progressive de toutes les cellules.
Pouvons-nous proposer un type de jeu différent?
Version déterministe
Nous avons maintenant une IA capable de déterminer toutes les étapes logiques à partir d'un état de jeu donné. Parfois, il ne pourra pas trouver d'étapes logiques. Dans de telles situations, le joueur doit deviner et il peut perdre s'il n'est pas chanceux.
Et si nous ajoutons une autre règle? Lorsque le jeu n'a aucune voie logique à suivre, nous pouvons demander de l'aide. Si l'IA accepte que le joueur ne puisse rien faire, alors il vient à son aide. Sinon, le joueur perd immédiatement. Cela peut être intéressant. De quel type d'aide s'agit-il? Vous devez peut-être ouvrir une cellule, quelle que soit la présence de mines:
Ainsi, nous nous sommes complètement débarrassés des situations dans lesquelles on pouvait perdre par hasard.
Cependant, il existe une exception: il existe toujours la possibilité de situations dégénérées dans lesquelles le solveur global ne peut pas terminer les calculs dans un délai raisonnable. Malheureusement, c'est le résultat inévitable que la tâche de démineur est terminée NP.
Comment le bouton «Demander de l'aide» affecte-t-il le gameplay? Cela conduit au fait que le jeu se concentre davantage sur la logique; Il s'agit de la version la plus "déroutante" de "Démineur". Quelqu'un pourrait penser que le jeu deviendra plus facile, mais en fait, cela devient plus compliqué. Maintenant, il n'y a aucune excuse pour les erreurs du joueur, et le bouton le punira s'il a raté quelque chose. Sans bouton, il est facile de conclure que vous avez épuisé toutes les possibilités logiques et la seule option pour le développement d'événements est d'essayer de deviner au hasard. Mais en raison de l'existence du bouton, le joueur doit avoir raison dans cette évaluation.
En conclusion
Après avoir implémenté le solveur Solveur "Démineur" complet, nous avons pu créer une variante du jeu, libre de sa malédiction: maintenant il est impossible de perdre du fait que vous devez choisir par hasard quand vous avez presque décidé du champ entier. Cette version ne diffère du jeu original que dans les moments où vous devez deviner au hasard, donc je peux supposer que c'est beaucoup plus amusant que le jeu original.
De plus, nous avons développé une version du jeu qui résout automatiquement les règles locales simples. La décision d'utiliser cette aide vous appartient. Il déplace le focus du jeu d'un clic mécanique à un gameplay plus déroutant. Dans le même temps, il n'est pas nécessaire d'utiliser l'amélioration du gameplay fournie par le bouton «Demander de l'aide».