J'essaie de créer une fonction de solvabilité pour un algorithme de jeu. Fondamentalement, une fonction qui renvoie true ou false pour un jeu donné, il est satisfait ou non.
Le jeu est ButNIA.com (ce qui ne met pas encore en œuvre l'algorithme pour le moment), un type de jeu de lumière. Fondamentalement, vous avez une grille de boutons, chacune desquelles, lorsque vous appuyez, changera l'état de certains de ses voisins. Actuellement, je génère une configuration de jeu aléatoire puis appliquez des heuristiques autant que possible. Le reste est décidé par la recherche de force brute. P>
Mes progrès jusqu'à présent consistaient à créer un système d'équations pour modéliser le jeu. Comme chaque bouton doit modifier l'état un nombre impair de fois-ci pour se retrouver dans un état de bas, son équation serait la suivante: p>
bouton_a = 1 - (bouton_1 + bouton_2 + ... + bouton_x)% 2 P>
où Button_1 via Button_x sont les états des boutons avec un effet sur Button_a. Certains boutons peuvent être immédiatement résolus, s'ils ne dépendent pas des autres. Pour le reste, j'essaie une configuration jusqu'à ce que je reçois un conflit puis une piste de retour. P>
Cet algorithme est pratique pour les plus petites configurations de jeux. Je l'ai testé à partir de 3x3 jeux jusqu'à la taille de 10x10. Où 6x6 est proche d'une limite supérieure pour une lecture pratique. P>
Les équations ont énormément réduit l'espace de recherche de la force brute, ce qui le rend pratique. Il pourrait y avoir une manière purement mathématique de résoudre le système d'équations. P>
échantillon 3x3 jeu en ASCII (de BONIA.COM/?GAME=2964 ): P>
-1 = -1*B00 + 0*B10 + 0*B20 + 0*B01 + 0*B11 + 0*B21 + 0*B02 + 0*B12 + 0*B22 -1 = 0*B00 + -1*B10 + -1*B20 + 0*B01 + 0*B11 + 0*B21 + 0*B02 + 0*B12 + 0*B22
5 Réponses :
Au lieu de commencer par un état aléatoire, pourquoi ne pas générer la position de départ en retournant des commutateurs aléatoires, c'est-à-dire des travaux à l'envers d'un état résolu à un état de départ. De cette façon, vous ne produisez que des énigmes solvables.
Par état aléatoire, je veux dire jeu aléatoire. L'état de départ est toujours tous des boutons, avec l'état cible toujours tous les boutons. Étant donné que les états sont symétriques, cela ne fait pas de différence si vous commencez avec tout ou vers le bas. La solution est toujours une carte un peu (carte marche / arrêt) dont les boutons doivent être enfoncés et qui ne le font pas.
Je vois, alors vous essayez simplement de déterminer si une grille donnée NXM est satisfaite?
Oui. Comme cela se produit, mon algorithme de solvabilité actuel renvoie également la solution. Fondamentalement, je veux m'assurer que je ne présente que des jeux solvables au joueur.
Il s'agit d'un système d'équations linéaires sur F 2 , le champ contenant les deux éléments 0 et 1.
Vous pouvez le résoudre comme des équations linéaires normales, mais vous devez faire le modulo arithmétique 2.
EDIT:
L'algèbre linéaire pour cette affaire fonctionne exactement comme pour les nombres réels, sauf que vous devez remplacer les opérations:
Addition et soustraction deviennent exclusives ou, I.e. 0 + 0 = 0, 0 + 1 = 1, 1 + 1 = 0.
multiplication devient et: 0 * 0 = 0, 0 * 1 = 0, 1 * 1 = 1
division n'est possible que par un: 0/1 = 0, 1/1 = 1.
Tous les coefficients de vos équations et les valeurs possibles des inconnues sont 0 ou 1.
Pour que le modulo ne soit pas giflé à l'extérieur des équations comme vous l'avez écrit, il est implicite dans les opérations.
Si votre système d'équations n'est pas résoluble, vous obtiendrez une équation 0 = 1, qui n'est évidemment pas solvable.
Le modulo est exactement ce qui m'a jeté. Comment puis-je les résoudre malgré le modulo? Surtout s'ils ne sont peut-être pas satisfables!
Hmmmm ... Je pensais que le Théorème du Rester chinois était l'outil nécessaire pour le résoudre, mais je l'examine, je me rends compte qu'il s'agit d'un problème différent (mes cours de mathématiques discrets sont un peu rouillés maintenant: -s)
Vous n'avez besoin que du théorème restant chinois pour calculer des inverse dans des champs finis plus importants, dans ce cas, il est trivial.
On dirait que cela pourrait le faire. Je vais mettre en œuvre l'algorithme d'équation simultanée (toute recommandation?) Et accepter probablement cette réponse si cela fonctionne!
@starBlue: J'aurais pensé que l'utilisation la plus courante du Théorème de Rester chinois était informatique des diviseurs dans un champ infini, c'est-à-dire le domaine des entiers
Comme il ne s'agit pas d'un problème limité sur le temps (bien, en supposant que cela puisse être fait en moins d'une journée), je voudrais probablement passer une recherche d'une première largeur peu limitée, prenant chaque mouvement possible sur un niveau, puis chaque mouvement qui suit de chaque mouvement.
Ce sera lent, mais il est presque garanti de trouver une réponse, s'il y en a un!
Il est solvable. J'ai même des statistiques détaillées dessus. Ma mise en œuvre actuelle peut trouver un 6x6 solvable en moyenne d'environ 400 ms avec une heure maximale de 1300 ms en JavaScript sous Chrome 3. Le problème est que l'algorithme ne va pas bien évoluer les configurations de jeu plus grandes. Une solution vraiment arithmétique très bien pourrait-elle!
Assez juste, si vous avez l'intention de rendre l'espace de recherche beaucoup plus grand, il ne sera pas bien amplifié, convenu. Réponse effectivement rétractée =]
De plus, il est fortement contraint, car je dois résoudre ce problème chaque fois qu'un joueur veut jouer un nouveau jeu, alors qu'ils attendent. Et cela pourrait arriver dans des périphériques de ressources limités, tels qu'un téléphone mobile.
Un 10x10 prend plus de 15 secondes à résoudre avec la mise en œuvre actuelle, ce qui, à mon avis, est un peu trop long pour des raisons de convivialité.
Est-ce vraiment un problème cependant? Pourquoi ne pas construire une énorme bibliothèque de puzzles solvables connues au côté serveur, et juste les parcourir? Si vous les remettez au hasard au hasard, la bibliothèque est suffisamment grande, vous avez efficacement mémoré la tâche du solveur. Cela éviterait le besoin entièrement d'un solveur à exécuter en JavaScript au côté du client.
Oh, j'avais l'impression que les Jeux n'ont changé que par jour, mon mal! D'accord avec IRE, les puzzles pré-résolues auraient un sens, vous pouvez accumuler rapidement une bibliothèque si cela ne prend que 15 ans pour résoudre un et les stocker est trivial, si vous stockez dans une sorte de format matriciel.
Le site Web a été construit longtemps avant d'avoir eu l'idée des équations simultanées. Nous avions prévu d'utiliser un algorithme de vote communautaire pour éliminer les "mauvais" jeux. C'est horrible bien sûr et je veux le solveur. Même pour l'utilisation de l'application de téléphonie mobile, l'algorithme actuel est fonctionnel, car les jeux de plus de 6x6 peuvent être trop difficiles à jouer. Je n'ai jamais joué un plus grand puis 6x6. C'est la plupart des questions théoriques.
Cela ressemble presque à un système d'équations linéaires (à l'exception du MOD 2), vous pourrez peut-être adapter l'une des techniques normales pour résoudre ceux-ci - par exemple. Réduction de la ligne du système de matrice forme (Wikipedia) .
Merci je vais regarder dans ceux-ci. Le problème est le module! Je peux peut-être l'éliminer en quelque sorte, mais je ne sais pas comment.
Supposons que vous ayez construit un système d'équations et les résolu de mieux que vous puissiez, mais certaines lignes se sont retrouvées avec tous les 0 sur le côté gauche de l'équation (je représente les équations comme une matrice augmentée) Supposons que vous ayez essayé de résoudre le système dans la bague Z2 (qui, en termes pratiques pour cet exemple particulier, signifie que le seul changement est que 1 + 1 = 0, sinon tout reste le même ... Ergo Le seul opérateur dont nous avons besoin est XOR) Et fini par la matrice suivante:
1000 0 0100 1 0010 1 0001 1
Suis je pense que celui qui pense que l'adresse sonne comme un site de porno? =]
Je parierais que certains perl gourou pouvaient sortir avec une expression régulière qui résout le problème XD
En toute honnêteté, ce jeu est assez amusant, mais vous avez besoin d'un peu de texte d'explication au sommet, il m'a fallu une minute ou pour savoir ce que je devais faire! = D
Eh bien, cela sera remplacé bientôt, avec celui qui ne montre que des jeux solvables. L'algorithme de solvabilité fonctionne et est pratique. Ceci est une question théorique quant à la manière dont je peux le résoudre "correctement", sans chercher.