Spiellösungsalgorithmus (Buttonia, Lights-Out-Variante)

https://stackoverflow.com/questions/1211560

06-07-2019
|

Frage

Ich versuche, eine Lösbarkeit Funktion für ein Spiel Algorithmus zu erstellen. Im Grunde eine Funktion, die für ein bestimmtes Spiel wahr oder falsch gibt es, wenn auflösbar ist oder nicht.

Das Spiel ist Buttonia.com (die nicht den Algorithmus noch nicht implementiert), eine Art von Lights-Out-Spiel. Grundsätzlich Sie haben ein Raster von Tasten, von denen jede, wenn sie gedrückt wird, wird der Zustand der einige seiner Nachbarn ändern. Derzeit erstelle ich eine zufällige Spielkonfiguration und dann Heuristik anwenden, so weit wie möglich. Der Rest wird von Brute-Force-Methode entschieden.

Mein Fortschritt war bisher ein Gleichungssystem zu schaffen, das Spiel zu modellieren. Da jede Taste Zustand eine ungerade Anzahl von Zeiten ändern muss in einem heruntergefahrenen Zustand am Ende, es ist Gleichung sein würde:

button_A = 1 - (Schaltfläche_1 + Button_2 + ... + button_X)% 2

Wo Schaltfläche_1 durch button_X sind die Zustände der Tasten mit einer Wirkung auf button_A. Einige Tasten können sofort behoben werden, wenn sie nicht von anderen abhängig sind. Für den Rest, ich versuche, eine Konfiguration, bis ich einen Konflikt und dann wieder die Strecke.

Zur Zeit dieser Algorithmus ist für kleinere Konfigurationen von Spielen praktisch. Ich habe es von 3x3 Spielen getestet bis zu Größen von 10x10. Wo 6x6 ist in der Nähe einer oberen Grenze für die Praxis zu spielen.

Die Gleichungen enorm reduzieren den Suchraum von Brute-Force, es praktisch zu machen. Es könnte ein rein mathematischer Weg sein, um das System von Gleichungen zu lösen.

Beispiel 3x3 Spiel in ascii (von 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

Lösung, drücken Sie diese: (0,0), (2,0), (1, 2), (0, 1), (1, 1), (2,1)

Die Gleichungen für dieses Spiel:

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

Mögliche Lösung:

Ändern die mathematischen Funktionen, um die Notwendigkeit zu vermeiden, für das Modul uns die Bedingungen auf der linken Seite nach rechts bewegen läßt, die ordentlich Matrix Setup schaffen wir für das Gauß-Verfahren benötigen. So sind die ersten beiden Gleichungen würde jeweils konvertieren:

-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

Diskutiert Lösung hier: Gaußsche Eliminations mit benutzerdefinierten Operatoren

Näher. Fast fertig vollständige Lösung zu schreiben: Invertierung binäre Netzwerk

Lösung

Dies ist ein System von linearen Gleichungen über F ₂, das Feld die beiden Elemente 0 und 1 enthält.

Sie können es lösen wie normale lineare Gleichungen, aber Sie haben die Arithmetik modulo 2 zu tun.

Edit: Lineare Algebra für diesen Fall funktioniert genau wie für reelle Zahlen, mit der Ausnahme, dass Sie, um die Vorgänge zu ersetzen:

Addition und Subtraktion wurden Exklusiv-ODER, das heißt 0 + 0 = 0, 0 + 1 = 1, 1 + 1 = 0 ist.
Die Multiplikation wird UND: 0 * 0 = 0, 0 * 1 = 0, 1 * 1 = 1
Abteilung ist nur möglich durch eine. 0/1 = 0, 1/1 = 1

Alle Koeffizienten in Ihren Gleichungen und die möglichen Werte der Unbekannten sind entweder 0 oder 1 ist.

So ist die Modulo auf der Außenseite der Gleichungen nicht geschlagen ist, wie Sie geschrieben haben, es ist implizit in den Operationen.

Wenn Sie Ihr System von Gleichungen nicht auflösbar ist, dass Sie eine Gleichung 0 = 1 erhalten werden, was natürlich nicht auflösbar ist.

Andere Tipps

Statt mit einem zufälligen Zustand des Startens, warum nicht die Startposition durch gelegentlichen Umdrehen Schalter, d.h. arbeitet rückwärts von einem gelösten Zustand zu einem Ausgangszustand. Auf diese Weise kann nur lösbares Rätsel generieren.

Dies fast wie ein System von linearen Gleichungen sieht (mit Ausnahme der mod 2), so könnten Sie in der Lage sein, eine der normalen Techniken anzupassen diejenigen für die Lösung - z.B. Reihenreduktion des Systems in Form einer Matrix (wikipedia) .

Da dies kein zeitlich begrenztes Problem ist (na ja, vorausgesetzt, es kann in weniger als einen Tag durchgeführt werden), würde ich für eine Tiefe begrenzte Breitensuche geht wahrscheinlich, jede mögliche Bewegung auf einer Ebene und dann jede Bewegung, die von jeder Bewegung folgt auf.

Es wird langsam sein, aber es ist fast garantiert eine Antwort zu finden, wenn es einen gibt!

Angenommen, Sie ein Gleichungssystem aufgebaut und gelöst, sie so gut es euch geht, aber einige Zeilen mit allen 0en auf der linken Seite der Gleichung am Ende (ich bin, die die Gleichungen als erweiterte Matrix) Angenommen, Sie das System in der Z2-Ring zu lösen versucht (die in der Praxis für dieses Beispiel bedeutet, dass die einzige Änderung ist, dass 1 + 1 = 0, sonst alles gleich bleibt ... ergo der einzige Betreiber wir brauchen, ist XOR) und endete mit der folgenden Matrix:

Wie Sie in diesem Beispiel sehen können, ist die vierte Zeile alle 0, was bedeutet, dass wir keine Antwort für sie bekommen haben. auf diese Weise halten sie jedoch: eine Reihe aller 0 bedeutet, dass diese Variable nicht die Lösung nicht beeinträchtigt. Das ist eigentlich eine schlechte Wahl der Worte ... es bedeutet nur, dass sie einen beliebigen Wert haben kann (und wir sind hier im Glück, da alle Werte bedeutet 1 oder 0 ist, anders als in realen Zahlen ... Dies bedeutet also, dass wir 2 Lösungen für dieses System).

Hier ist der Grund: Was Sie wissen müssen, ist an dieser Stelle, dass die Spalte ganz rechts noch eine gültige Lösung für Ihr Spiel enthält. Lassen Sie sich die erste Zeile zum Beispiel. Er sagt, dass

button_0 + button_3 = 1

, aber wir wissen, dass die Taste 3 kann alles sein (da der Linie 3 alle 0s). An diesem Punkt der Taste 3 0 (die Spalte ganz rechts in der Zeile 3 0 an dieser Stelle), so wissen wir jetzt es bedeutet

button_0 + 0 = 1

, so dass wir für eine Tatsache wissen, dass Button_0 ist 1. Daher wird in diesem System, auch wenn wir button_3 herausfinden, nicht direkt konnten wir noch eine gültige Lösung haben.

Die Matrix oben erzeugte genug für Lösbarkeit zu überprüfen. Wenn eine Zeile alle 0s enthält dann ist es im Wesentlichen sagen, dass

nothing = nothing

oder, besser zu visualisieren, warum das funktioniert,

0x = 0

, die Sinn macht, ist das System immer noch gültig. Wenn wir jedoch eine Reihe auftreten, die alle 0s ist außer das Bit ganz rechts, d.

0000 1

das würde sagen

0x = 1

die daher unmöglich ist, wir wissen jetzt, dass das System nicht gelöst werden, da wir eine unmögliche Situation wie diese nicht lösen können.

Deshalb in aller Kürze, versuchen, die Gleichung zu lösen, so gut Sie können, keine Sorge, wenn Sie nicht genau herausfinden können, was einige der Variablen sind, solange man nicht begegnen, an jedem Punkt, das Unmögliche Zeile ich gerade erwähnte dann das Spiel auflösbar ist.

Aber was ist, wenn wir die kürzeste Lösung für das System wollen? Hier werden wir alle möglichen Lösungen zu prüfen haben. Wir haben button_3 dass jeder Wert sein kann, so dass bedeutet, dass jede 1 in Spalte 3 bedeutet, dass die Zeile, in der es gefunden wird, durch button_3 betroffen ist. Also nehmen wir überprüfen wollen, ob die Lösung button_3 mit kürzer sein wird. Wir schaffen eine andere Matrix, sondern setzen button_3 bis 1 jetzt (da wir früher festgestellt, dass es etwas sein könnte, und wir hatten schon ein 0 drin, jetzt prüfen wir für 1). Wir haben jetzt mit der folgenden Matrix am Ende:

Wir verringern, dass so viel wie wir können und jetzt mit dieser Matrix am Ende:

Dies ist immer noch eine gültige Lösung, jedoch können wir sehen, dass die Lösung nicht länger (3 erfordert, anstelle von 2-Taste drückt) damit wir es verwerfen. Wir haben dies die Reihen der Einstellung für jede Permutation tun wir wie alle 0s bis 1. Daher gefunden, wenn wir x Reihen haben, die alle 0s waren, dann hat das System x ^ 2 Lösungen, und wir haben alle von ihnen zu überprüfen.

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow