Ist ein Tensor (multidimensionales Array) ein effektiver Speichertyp für die Baum-Lookahead-Daten?

Question

Ich untersuche einen Spielalgorithmus und denke darüber nach, wie ich es verbessern kann. Es gibt einen Vorausschau-Baum. Dies ist ein sehr häufiges Szenario, wie in Karten oder ähnlichen Spielen. Die Spielstrategie ist als Tensor (multidimensionales Array) implementiert. Die Anzahl der Dimensionen = Vorausschautiefe. Und jede Dimensionsgröße ist die MAX-mögliche Anzahl von Aktionen, die in dieser Tiefenebene des Baums verfügbar sind. Ein Knoten auf der gleichen Ebene kann nur zwei Aktionen zur Verfügung haben, und die anderen 10. Aber wir müssen eine Dimension der Größe 10 haben, wenn wir den Tensor verwenden. Außerdem müssen wir die andere Struktur mit Aktionen für alle Knoten speichern. Es gibt eine Menge von Operationen, die mit dieser Tensor-ähnlichen elementweisen Multiplikation, Addition usw. durchgeführt werden. Die Gesamtgröße dieses Tensors beträgt einige Gigabyte. Ist dieser Tensor eine gute Idee oder nicht in Bezug auf die Leistung? Kann ich die benutzerdefinierte Struktur verbessern? Die App ist extra leistungsschwer.

Answer 1

Das klingt nach Auswendiglernen der Spieltheorie.

Zum Glück haben wir nicht eine jede Ebene von vornherein zu dimensionieren, so etwas wie dies mit:

class Moves { 
    TheMove thisMove; // A2-A3 
    std::vector<Moves> positions; // all possible counter moves 
... add stuff 
}; 

Dies wird schrecklich in Größe explodiert, wie Sie erwähnten. Der Vorteil ist, dass Sie nicht neu berechnen müssen, wenn Sie die gesamte mögliche Menge an Moves im gesamten Spiel zugeordnet haben.

Wenn Sie nicht das gesamte Spiel zuordnen, müssen Sie jede Bewegung (x-1)/x des Baumes verwerfen und die Endknoten um eine Stufe erweitern.