Algorithme de résolution de jeu (Buttonia, variante de lights-out)

Question

Je cherche à créer une fonction de résolubilité pour un algorithme de jeu. Fondamentalement, une fonction qui renvoie vrai ou faux pour un jeu donné pour déterminer s'il est résoluble ou non.

Le jeu est Buttonia.com (qui n'implémente pas encore l'algorithme), un type de jeu de lumières. Fondamentalement, vous avez une grille de boutons, chacun desquels, lorsqu'il est pressé, changera l'état de certains de ses voisins. Actuellement, je génère une configuration de jeu aléatoire puis j'applique des heuristiques autant que possible. Le reste est décidé par une recherche de force brute.

Mon avancée jusqu'à présent a été de créer un système d'équations pour modéliser le jeu. Comme chaque bouton doit changer d'état un nombre impair de fois pour se retrouver dans un état bas, son équation serait la suivante :

bouton_A = 1 - (bouton_1 + bouton_2 + ... + bouton_X) % 2

Où bouton_1 à bouton_X sont les états des boutons ayant un effet sur bouton_A. Certains boutons peuvent être résolus immédiatement, s'ils ne dépendent pas des autres. Pour le reste, j'essaie une configuration jusqu'à ce que je rencontre un conflit et je reviens en arrière.

Actuellement, cet algorithme est pratique pour des configurations plus petites. Je l'ai testé à partir de jeux 3x3 jusqu'à des tailles de 10x10. Où 6x6 est presque une limite supérieure pour un jeu pratique.

Les équations réduisent énormément l'espace de recherche de la force brute, le rendant pratique. Il pourrait y avoir un moyen purement mathématique de résoudre le système d'équations.

---

Exemple de jeu 3x3 en ascii (de buttonia.com/?game=2964) :

||#
-o-
+#|

Légende :
o = affecte seulement soi-même
- = affecte les voisins de gauche et de droite
| = affecte les voisins du haut et du bas
+ = affecte les voisins de gauche, de droite, du haut et du bas
# = affecte tous les 8 voisins environnants

Solution, appuyez sur ces boutons : (0,0), (2,0), (1, 2), (0, 1), (1, 1), (2,1)

Équations pour ce jeu :

Bouton_0_0 = 1 - (0) % 2
Bouton_1_0 = 1 - (Bouton_2_0) % 2
Bouton_2_0 = 1 - (0) % 2
Bouton_0_1 = 1 - (Bouton_0_0 + Bouton_0_2 + Bouton_1_2) % 2
Bouton_1_1 = 1 - (Bouton_1_0 + Bouton_2_0 + Bouton_0_1 + Bouton_2_1 + Bouton_1_2) % 2
Bouton_2_1 = 1 - (Bouton_2_0 + Bouton_1_2 + Bouton_2_2) % 2
Bouton_0_2 = 1 - (Bouton_1_2) % 2
Bouton_1_2 = 1 - (Bouton_0_2) % 2
Bouton_2_2 = 1 - (Bouton_1_2) % 2

Solution potentielle :

Modifier les fonctions mathématiques pour éviter le besoin du modulo nous permet de déplacer les termes du côté gauche vers la droite, créant la configuration matricielle soignée dont nous avons besoin pour la méthode de Gauss. Ainsi, les deux premières équations se convertiraient respectivement en :

-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

Solution discutée ici : Élimination de Gauss avec des opérateurs personnalisés

De plus en plus proche. Presque prêt à afficher la solution complète : Inverse de réseaux binaires

Answer 1

Ceci est un système d'équations linéaires sur F₂, le corps contenant les deux éléments 0 et 1.

Vous pouvez le résoudre comme des équations linéaires normales, mais vous devez faire l'arithmétique modulo 2.

Édition : L'algèbre linéaire pour ce cas fonctionne exactement comme pour les nombres réels, sauf que vous devez remplacer les opérations :

• L'addition et la soustraction deviennent le OU exclusif, c'est-à-dire 0 + 0 = 0, 0 + 1 = 1, 1 + 1 = 0.

• La multiplication devient le ET : 0 * 0 = 0, 0 * 1 = 0, 1 * 1 = 1

• La division n'est possible que par un : 0 / 1 = 0, 1 / 1 = 1.

Tous les coefficients dans vos équations et les valeurs possibles des inconnues sont soit 0 soit 1.

Donc, le modulo n'est pas simplement ajouté à 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 soluble, vous obtiendrez une équation 0 = 1, ce qui n'est évidemment pas soluble.

Answer 2

Au lieu de commencer par un état aléatoire, pourquoi ne pas générer la position de départ en basculant des commutateurs aléatoires, c'est-à-dire travailler à rebours à partir d'un état résolu vers un état de départ. De cette façon, vous ne générez que des puzzles solubles.

Answer 3

Cela ressemble presque à un système d'équations linéaires (à l'exception du mod 2), donc vous pourriez être en mesure d'adapter l'une des techniques normales pour résoudre ceux-ci - par exemple, la réduction des lignes du système sous forme matricielle (wikipedia).

Answer 4

Comme il ne s'agit pas d'un problème limité dans le temps (enfin, en supposant que cela peut être fait en moins d'une journée), je choisirais probablement une recherche en largeur limitée en profondeur, en prenant chaque mouvement possible à un niveau, puis chaque mouvement qui suit chaque mouvement.

Cela sera lent, cependant il est presque garanti de trouver une réponse, s'il y en a une !

Answer 5

Suppose you built a system of equations and solved them as best you could, but some rows ended up with all 0's on the left hand side of the equation (I'm representing the equations as an augmented matrix) Suppose you tried to solve the system in the Z2 ring (which in practical terms for this particular example means that the only change is that 1+1=0, else everything remains the same... ergo the only operator we need is XOR) and ended up with the following matrix:

1001 1
0100 1
0011 0
0000 0

Comme vous pouvez le voir dans cet exemple, la 4ème ligne est toute en 0, ce qui signifie que nous n'avons pas de réponse pour cela. Cependant, pensez-y de cette manière : une ligne entièrement composée de 0 signifie que cette variable n'affecte pas la solution. C'est en réalité un choix de mots pauvre... cela signifie simplement qu'elles peuvent avoir n'importe quelle valeur (et nous avons de la chance ici, car toutes les valeurs signifient 1 ou 0, contrairement aux nombres réels... Donc cela signifie que nous avons 2 solutions pour ce système).

Voici pourquoi : ce que vous devez savoir à ce stade, c'est que la colonne de droite contient toujours une solution valide pour votre jeu. Prenons la première ligne par exemple. Elle dit que

button_0 + button_3 = 1

mais nous savons que le bouton 3 peut être n'importe quoi (puisque la ligne 3 est toute en 0). À ce stade, le bouton 3 est 0 (la colonne de droite sur la ligne 3 est 0 à ce stade) donc maintenant nous savons que cela signifie

button_0 + 0 = 1

nous savons donc que le bouton_0 est 1. Par conséquent, dans ce système, même si nous n'avons pas pu trouver directement le bouton_3, nous avons quand même une solution valide.

La matrice générée ci-dessus est suffisante pour vérifier la résolubilité. Si une ligne contient que des 0, cela revient essentiellement à dire que

rien = rien

ou, pour mieux visualiser pourquoi cela fonctionne,

0x = 0

ce qui est logique, le système est toujours valide. Si nous rencontrons cependant une ligne qui est toute en 0 sauf le bit de droite, c'est-à-dire

0000 1

cela reviendrait à dire

0x = 1

ce qui est impossible donc nous savons maintenant que le système ne peut pas être résolu, car nous ne pouvons pas résoudre une situation impossible comme celle-ci.

Par conséquent, en résumé, essayez de résoudre l'équation du mieux que vous pouvez, ne vous inquiétez pas si vous ne pouvez pas exactement trouver ce que sont certaines des variables, tant que vous n'atteignez jamais, à aucun moment, la ligne impossible que je viens de mentionner alors le jeu est solvable.

Mais que se passe-t-il si nous voulons la solution la plus courte au système? Ici, nous devrons examiner toutes les solutions possibles. Nous avons button_3 qui peut être n'importe quelle valeur, donc cela signifie que toute valeur de 1 dans la colonne 3 signifie que la ligne dans laquelle elle est trouvée est affectée par le bouton_3. Supposons que nous voulions vérifier si la solution en utilisant button_3 sera plus courte. Nous créons une autre matrice, mais nous réglons button_3 sur 1 maintenant (puisque nous avons établi plus tôt qu'il pouvait être n'importe quoi, et nous avions déjà un 0 dedans, donc maintenant nous vérifions pour 1). Nous obtenons maintenant la matrice suivante :

1001 1
0100 1
0011 0
0001 1

Nous la réduisons autant que possible et nous obtenons maintenant cette matrice :

1000 0
0100 1
0010 1
0001 1

C'est toujours une solution valide, cependant nous pouvons voir que la solution est plus longue (nécessitant 3, au lieu de 2 pressions de bouton) donc nous la rejetons. Nous devons faire cela pour chaque permutation en réglant les lignes que nous avons trouvées comme étant toutes en 0 à 1. Par conséquent, si nous avons x lignes qui étaient toutes en 0, alors le système a x^2 solutions, et nous devons toutes les vérifier.