Reduzierung des Speicher- und Suchaufwands in der Gitterbewegungskombinatorik ⇐ C#

[Anonymous]

Ich weiß, dass mein Titel nicht ganz klar ist, aber ich weiß nicht, wie ich ihn formulieren soll.
Beginnen wir mit einem 4 x 4-Raster; Irgendwann möchte ich es auf 8 x 8 erweitern oder so groß wie möglich, wenn 8 x 8 zu groß, aber nicht größer ist. Ich habe die Zellen beschriftet, damit es einfacher ist, darüber zu sprechen, und wir müssen irgendwo anfangen, also habe ich unsere Startposition in der 0. Zelle in Rot eingefügt. Ich konzentriere mich im Moment nur auf die 0. Zelle, aber Sie würden mit einer Liste aller einzelnen Zellen beginnen. Ich nenne diese Iteration 1.
Ein 4 x 4 großes Raster, beschriftete Zellen und ein roter Punkt in der ersten Zelle
Als nächstes I würde alle möglichen Positionen erhalten, die von hier aus besucht werden können. Ich habe Zellen, die die Startposition besuchen kann, grün markiert. Die Regel besagt, dass Sie sich nur nach oben, unten, links oder rechts bewegen können, aber Sie können sich um eine variable Distanz bewegen. Sie können beispielsweise eine Kachel nach rechts oder drei Kacheln nach rechts verschieben. Zurück zu diesem Beispiel könnten wir zu 1, 2, 3, 4, 8 und 12 gehen. (Ich würde dies für alle 16 möglichen Startpositionen wiederholen) Als Satz von Paaren wären sie (0, 1), (0, 2), ... , (0, 12). Dies ist die zweite Iteration.
Dasselbe Raster wie oben, aber die Zellen wurden aktualisiert, um Zellen widerzuspiegeln, die besucht werden können
Dann für jeden Paar, erhalte alle möglichen Drillinge. Im Beispiel verwende ich (0, 8). Sie wären also (0, 1, 8), (0, 2, 8), (0, 3, 8), (0, 4, 8), (0, 8, 9), (0, 8, 10 ), (0, 8, 11), (0, 8, 12)
Mögliche Positionen von (0, 8)
Und ich würde Wiederholen Sie diese Iterationen so lange, bis Es gibt keinen leeren Raum mehr.
Ich habe bereits ein Programm geschrieben, das dies kann. Es ist ziemlich trivial, aber es ist langsam und verbraucht viel Speicher. Ich hoffe, dass mir jemand einen Einblick in dieses Problem geben kann.
Code
Ich speichere die Positionen als Bitboards. Es verwendet eine Breitensuche, um alle Positionen zu ermitteln. Ich nehme ein paar Optimierungen vor, von denen ich mir nicht sicher bin, ob sie funktionieren, andere glaube ich, dass sie zu früh zu sehr bereinigt werden könnten, was dazu führen könnte, dass nicht alle Kombinationen gefunden werden.
internal class ValidPositionGenerator
{
// Used to store new bitboards we need to check
private readonly Queue bitBoards = new Queue();

// Used to store unique bitboards we have found
private readonly HashSet visited = [];

public ValidPositionGenerator(int maxTiles)
{

int i = 0;

// This corresponds to the first iteration
while (i < 64)
{
bitBoards.Enqueue(CanonicalizeBitboard((ulong)Math.Pow(2, i)));
i++;
}

GenerateValid(bitBoards, maxTiles);
}

private void GenerateValid(Queue bitBoards, int maxTiles)
{
int i = 0;
while (bitBoards.Count != 0)
{
ulong board = bitBoards.Dequeue();

if (visited.Contains(board))
{
continue;
}

if (BitOperations.PopCount(board) > maxTiles)
{
continue;
}

visited.Add(board);

GetNewPositions(board, bitBoards, visited);

i++;
}
}

private static void GetNewPositions(ulong board, Queue bitBoards, HashSet visited)
{
// Get the active bits from board
List indices = GetIndices(board);

int i;
ulong canonical;

// Loop over each one and attempt to add each one to the output
foreach (int index in indices)
{
(int, int) pair = GetXYPairFromIndex(index);
// Up
i = 1;
while (pair.Item2 - i > -1)
{
// Check if the next bit is already set: Optimization 1
if (Util.GetBitboardCell(board, pair.Item1, pair.Item2 - i) == true)
{
break;
}
// Optimization 2, 3, and 4 happens inside CanonicalizeBitboard()
canonical = CanonicalizeBitboard(SetBitboardBit(board, pair.Item1, pair.Item2 - i, true));
if (!visited.Contains(canonical))
{
bitBoards.Enqueue(canonical);
}
i++;
}
// I've removed the rest to keep the code shorter
// Left
// Right
// Down
}
}
}

private static List GetIndices(ulong board)
{
ulong temp = board;
List indices = new List();
int index = 0;
while (board > 0)
{
if ((board & 1) == 1)
{
indices.Add(index);
}
board >>= 1;
index++;
}
return indices;
}

// Convert index to an x, y pair
private static (int, int) GetXYPairFromIndex(int index)
{
return (index % 8, index / 8);
}
}

Optimierung 1: Nicht noch einmal prüfen
Wenn wir beim Scannen nach neuen Positionen eine bereits aktive Position finden, können wir anhalten, weil wir es können Fahren Sie von dort fort, wenn wir dort ankommen. Im folgenden Beispiel bin ich auf (0, 2) und suche nach Bits rechts von 0. Wenn wir 2 erreichen, sehen wir, dass das Bit bereits aktiv ist, sodass wir anhalten können. Dann scannen wir weiter nach unten, links, bevor wir Bits um 2 scannen. Von hier aus scannen wir weiter nach rechts und erhalten alles, was wir übersehen haben. Ich habe noch nicht getestet, ob das tatsächlich etwas verbessert.
(0, 2)
Ich denke, eine mögliche Optimierung wäre die Erstellung eines weiteren Bitboards mit allen Orten, die wir währenddessen besucht haben Dies überprüfen und stoppen, wenn wir etwas finden, das bereits gefunden wurde. Denn sobald wir bei 2 angelangt sind, wird mit der Suche nach links in Richtung 0 begonnen, aber in dieser Richtung wurde bereits alles gefunden. Ich denke, ich kann dies mit der ersten Optimierung zusammenführen. Es scheint eine Erweiterung davon zu sein.
Optimierung 2: Keine Spiegelungen oder Rotationen speichern
Jede Kombination hat Symmetrie und ich brauche sie nicht Es. Ich muss nur einen davon behalten. Genau das macht die Methode canonicalizeBitboard. Es prüft es anhand von Rotationen und Reflexionen. Dadurch wird der Suchraum drastisch reduziert. Anstatt in der ersten Iteration 16 Möglichkeiten zu speichern, müssen wir nur 3 speichern: 0, 1 und 5.
Von 0, 1 oder 5 können Sie jede andere Zahl erhalten, indem Sie das Brett drehen oder umdrehen. 0 um 90 gedreht ergibt 3. 1 umgedreht ergibt 2.
Optimierung 3: Ähnliche Übersetzungen nicht speichern
Bedenken Sie die beiden Raster unten . Für mich sind sie im Wesentlichen dasselbe. Wenn ich also das Bitboard kanonisiere, verschiebe ich es auch so, dass es bündig mit der oberen linken Ecke abschließt.
Das ist im Grunde das Gleiche
Optimierung 4: Kondensiert
Die folgenden zwei Bitboards wurden berücksichtigt. Für meine Zwecke sind mir nur die einzigartigen Kombinationen der Bewegung nach oben, unten, links oder rechts wichtig. Wenn wir bei 0 beginnen, können wir uns in beiden nach rechts und unten bewegen, sodass sie für mich gleich sind und ich nur eines brauche. Allerdings bin ich mir nicht sicher, ob ich es vollständig entfernen kann. Ich denke, ich muss es immer noch behalten, wenn ich nach neuen Bitboards suche, aber ich brauche es nicht in meiner Ausgabe. Auch bei meinen anderen Optimierungen bin ich über diesen Punkt verwirrt. Ich denke, auch wenn ich sie nicht in meiner Ausgabe benötige, sollte ich sie dennoch überprüfen, da die neue Position, die ich von ihnen erhalten kann, möglicherweise einzigartig ist und nicht in ihrer komprimierten Version zu finden ist.
Ein Original-Bitboard und seine komprimierte Version Version
Fazit
Das sind alle Optimierungen, die mir im Moment einfallen, aber das Schreiben dieses Beitrags hat mich zum Nachdenken gebracht. Alles, was ich wirklich mache, ist, alle möglichen Kombinationen/Permutationen von oben, unten, links oder rechts zu finden, wobei die Summe von links und rechts der Größe der Breite des Bitboards entspricht – 1 und ähnlich mit oben und unten, aber mit vielleicht ein paar zusätzliche Regeln. Vielleicht gibt es eine Möglichkeit, anders darüber nachzudenken. Ich denke, es könnte eine Möglichkeit geben, es als eine Folge von oben, unten, links und rechts zu betrachten und das dann irgendwie auf ein kanonisches Bitboard abzubilden.
Was ich habe Bisher versucht
Ich habe meinen Code ausprobiert und er funktioniert. Ich frage mich nur, ob es einen besseren Weg gibt. Wenn ich den Konstruktor ValidPositionGenerator() aufrufe und 6 als Eingabe verwende, dauert es etwa 6 Sekunden und einen halben GB Speicher. Bei 7 dauert es etwa 2 Minuten und verbraucht 16 GB Speicher. Wenn ich es profiliere, explodiert die BitBoards-Warteschlange wie verrückt und das könnte durchaus unvermeidlich sein. Ich weiß, dass es 2^64 mögliche Bitboards gibt, aber ich hoffe, dass meine Regeln und Optimierungen das leichter handhabbar machen.