Der folgende Code erstellt eine unendliche Struktur und erstellt gleichzeitig einen Cache für alle Teilbäume, sodass keine doppelten Teilbäume erstellt werden. Die Begründung für die Eliminierung von doppelten Teilbäumen kommt von der Anwendung, um Bäume von schachähnlichen Spielen zu kennzeichnen: Man kann oft im selben Spielzustand landen, indem man einfach die Reihenfolge von zwei Zügen ändert. Im Verlauf des Spiels sollten nicht mehr zugängliche Zustände nicht mehr Speicher beanspruchen. Ich dachte, ich könnte dieses Problem mit schwachen Zeigern lösen. Leider bringt uns die Verwendung von schwachen Zeigern in die IO Monade und dies scheint genug / alle Faulheit zerstört zu haben, so dass dieser Code nicht mehr endet.
Meine Frage lautet also: Ist es möglich, einen faulen (Spielzustands-) Baum ohne doppelte Teilbäume effizient zu erzeugen (und ohne Speicherverlust)?
%Vor%Meine Frage lautet also: Ist es möglich, einen faulen (Spielzustands-) Baum ohne doppelte Teilbäume effizient zu erzeugen (und ohne Speicherverlust)?
Nein. Im Wesentlichen verwenden Sie Transpositionstabellen , um Ihre Baumsuchfunktion zu protokollieren (zB negascout ). Das Problem ist, dass Spiele eine exponentielle Anzahl von Zuständen haben und eine Transponiertabelle, die alle Umsetzungen des Zustandsraums speichert, nicht ausführbar ist. Du hast einfach nicht so viel Speicher.
Zum Beispiel hat Schach eine Zustandsraum-Kompexität von 10 ^ 47 . Das ist mehrere Größenordnungen größer als der gesamte Computerspeicher auf der ganzen Welt. Natürlich können Sie diese Menge reduzieren, indem Sie keine Reflexionen speichern (Chess hat 8 Reflection Symmetries ). Darüber hinaus wären viele dieser Transpositionen aufgrund der Beschneidung des Spielbaums nicht erreichbar. Der Zustandsraum ist jedoch so hartnäckig, dass Sie immer noch nicht jede Transposition speichern könnten.
Was die meisten Programme normalerweise tun, ist die Verwendung einer Transpositionstabelle mit einer festen Größe. Wenn zwei Transpositionen auf denselben Wert getastet werden, verwenden sie Ersatzschema , um zu entscheiden, welcher Eintrag aufbewahrt und welcher gelöscht wird. Dies ist ein Kompromiss, da Sie den Wert beibehalten, der Ihrer Meinung nach am effizientesten ist (d. H. Am häufigsten besucht oder näher am Stammknoten), auf Kosten der anderen Transposition. Der Punkt ist, dass es unmöglich ist, einen Spielbaum zu generieren, der keine doppelten Teilbäume hat, es sei denn, du bist aus einer ausreichend fortgeschrittenen außerirdischen Zivilisation.
Tags und Links haskell functional-programming tree weak-references infinite