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

Question

J'essaie de créer une fonction de solvabilité pour un algorithme de jeu. Fondamentalement, une fonction qui renvoie vrai ou faux pour un jeu donné peut être résolue ou non.

Il s’agit de Buttonia.com (qui n’implémente pas encore l’algorithme), un type de jeu très éclairé. En gros, vous avez une grille de boutons dont chacun, lorsqu'il est enfoncé, changera l'état de certains de ses voisins. Actuellement, je génère une configuration de jeu aléatoire, puis j'applique autant que possible des méthodes heuristiques. Le reste est décidé par recherche de force brute.

Mes progrès jusqu'à présent consistaient à 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 d'inactivité, l'équation serait la suivante:

button_A = 1 - (button_1 + button_2 + ... + button_X)% 2

Où bouton_1 à bouton_X sont les états des boutons ayant un effet sur le bouton_A. Certains boutons peuvent être résolus immédiatement s'ils ne dépendent pas d'autres. Pour le reste, j’essaie une configuration jusqu’à ce que j’aie un conflit, puis retourne.

Actuellement, cet algorithme est pratique pour les petites configurations de jeux. Je l'ai testé à partir de jeux 3x3 jusqu'à 10x10. Où 6x6 est proche d'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 (extrait de buttonia.com/?game=2964 ):

||#
-o-
+#|

Legend:
o = affect only self
- = affect left and right neighbors
| = affect above and below neighbors
+ = affect left, right, above and below neighbors
# = affect all 8 surrounding neighbors

Solution, appuyez sur ceux-ci: (0,0), (2,0), (1, 2), (0, 1), (1, 1), (2,1)

Équations pour ce jeu:

Button_0_0 = 1 - (0) % 2
Button_1_0 = 1 - (Button_2_0) % 2
Button_2_0 = 1 - (0) % 2
Button_0_1 = 1 - (Button_0_0 + Button_0_2 + Button_1_2) % 2
Button_1_1 = 1 - (Button_1_0 + Button_2_0 + Button_0_1 + Button_2_1 + Button_1_2) % 2
Button_2_1 = 1 - (Button_2_0 + Button_1_2 + Button_2_2) % 2
Button_0_2 = 1 - (Button_1_2) % 2
Button_1_2 = 1 - (Button_0_2) % 2
Button_2_2 = 1 - (Button_1_2) % 2

Solution potentielle:

Le fait de modifier les fonctions mathématiques pour éviter de recourir au module nous permet de déplacer les termes de gauche à droite, créant ainsi la configuration de matrice soignée dont nous avons besoin pour la méthode gaussienne. Ainsi, les deux premières équations seraient respectivement converties 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

A discuté de la solution ici: élimination gaussienne avec des opérateurs personnalisés

Se rapprocher. Presque prête à publier une solution complète: Inversion de réseaux binaires

Answer 1

C’est un système d’équations linéaires sur F ₂ , 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 l’arithmétique modulo 2.

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

• L'addition et la soustraction deviennent exclusives ou, c'est-à-dire 0 + 0 = 0, 0 + 1 = 1, 1 + 1 = 0.

• La multiplication devient 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 de vos équations et les valeurs possibles des inconnues sont 0 ou 1.

Le modulo n'est donc pas inséré à l'extérieur des équations comme vous l'avez écrit, il est implicite dans les opérations.

Si votre système d'équations ne peut pas être résolu, vous obtenez l'équation 0 = 1, ce qui est évidemment impossible à résoudre.

Answer 2

Au lieu de commencer avec un état aléatoire, pourquoi ne pas générer la position de départ en basculant des commutateurs aléatoires, c’est-à-dire revenir en arrière d’un état résolu à un état de départ. De cette façon, vous ne générez que des énigmes solubles.

Answer 3

Cela ressemble presque à un système d’équations linéaires (à l’exception du mod 2), vous pourrez donc peut-être adapter l’une des techniques habituelles pour résoudre ces problèmes, par exemple. réduction de ligne du système sous forme de matrice (wikipedia) .

Answer 4

Comme ce n’est pas un problème limité dans le temps (eh bien, en supposant que cela puisse être fait en moins d’une journée), j’irais probablement pour une recherche approfondie en profondeur, avec une profondeur limitée, prenant chaque mouvement possible à un niveau puis chaque mouvement qui suit chaque mouvement.

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

Answer 5

Supposons que vous ayez construit un système d'équations et que vous les ayez résolus de votre mieux, mais que certaines lignes se retrouvaient avec tous les 0 à gauche de l'équation (je représente les équations sous forme de matrice augmentée). Supposons que vous essayiez de résoudre le système dans l’anneau Z2 (ce qui signifie concrètement pour cet exemple particulier que le seul changement est que 1 + 1 = 0, sinon tout reste le même ... par conséquent, le seul opérateur dont nous avons besoin est XOR) et a fini avec la matrice suivante:

1001 1
0100 1
0011 0
0000 0

Comme vous pouvez le voir dans cet exemple, la 4ème ligne est composée de 0, ce qui signifie que nous n’avons pas de réponse. Cependant, pensez de cette façon: une ligne de 0 signifie que cette variable n’affecte pas la solution. C’est en fait un mauvais choix de mots ... cela signifie simplement qu’ils peuvent avoir n'importe quelle valeur (et nous avons de la chance ici, car toutes les valeurs signifient 1 ou 0, contrairement aux chiffres réels ... Cela signifie donc que nous avons 2 solutions pour ce système).

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

button_0 + button_3 = 1

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

button_0 + 0 = 1

nous savons donc que button_0 vaut 1. Par conséquent, dans ce système, même si nous ne pouvons pas trouver directement button_3, nous avons toujours une solution valable.

La matrice générée ci-dessus est suffisante pour vérifier la solvabilité. Si une ligne contient tous les 0, elle indique essentiellement que

nothing = nothing

ou, pour mieux comprendre pourquoi cela fonctionne,

0x = 0

ce qui a du sens, le système est toujours valide. Si toutefois nous rencontrons une ligne qui a tous les 0 sauf le bit le plus à droite, c.-à-d.

0000 1

ce serait dire

0x = 1

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

En résumé, essayez de résoudre l'équation du mieux que vous pouvez, ne vous inquiétez pas si vous ne pouvez pas savoir exactement quelles sont les variables, tant que vous ne rencontrez pas, à aucun moment, l'impossible. rangée que je viens de mentionner alors le jeu est soluble.

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 avoir n'importe quelle valeur, ce qui signifie que n'importe quel 1 dans la colonne 3 signifie que la ligne dans laquelle il se trouve est affectée par button_3. Supposons donc que nous voulions vérifier si la solution utilisant button_3 sera plus courte. Nous créons une autre matrice, mais définissons button_3 sur 1 maintenant (puisque nous avions établi précédemment que cela pouvait être n'importe quoi, et que nous avions déjà un 0, nous vérifions maintenant 1). Nous nous retrouvons maintenant avec la matrice suivante:

1001 1
0100 1
0011 0
0001 1

Nous réduisons cela autant que possible et finissons avec cette matrice:

1000 0
0100 1
0010 1
0001 1

Ceci est toujours une solution valable, mais nous pouvons voir que la solution est plus longue (nécessitant 3, au lieu d'appuyer sur 2 boutons) donc nous la rejetons. Nous devons faire cela pour chaque permutation de la définition des lignes trouvées comme étant égales à 0. Par conséquent, si nous avons x lignes qui étaient toutes égales à 0, le système a x ^ 2 solutions et nous devons toutes les vérifier. / p>