Frage von snagnar, 46

Verlängern viele Methoden die Erstellzeit eines C++-Objektes?

Ich bin gerade dabei, ein Schach-KI in cpp zu programmieren und dabei wird ein Baum aus allen möglichen Zugkombinationen erstellt, momentan bei mir nur bis in die dritte Ebene. Bei jedem einzelnen Knoten wird ein Objekt der "node"-Klasse erzeugt, welches seinerseits ein Objekt "brett" erstellt. Beide Klassen haben einige Methoden, meist recht lange. Meine Frage ist, ob es die Zeit, die es braucht, ein solches Objekt zu erstellen, markant (und mit markant meine ich, dass es auch nur ein paar Millisekunden schneller geht, beim Erstellen von 1000 Knoten) verschnellert, wenn ich alle Methoden auslagere und nur über Referenz aufrufe oder ist dies eher verlangsamend?

Mit freundichen Grüßen und der Bitte um Hilfe, snagnar

Hilfreichste Antwort - ausgezeichnet vom Fragesteller
von PWolff, 28

Die Methoden sind nur ein einziges Mal im Speicher vorhanden, spielen also keinerlei Rolle bei der Erstellung einer weiteren Instanz, weder was die Zeit, noch was den Speicherbedarf betrifft.

Auslagern der Methoden erfordert möglicherweise bei jedem Aufruf eine zusätzliche Dereferenzierung, die jedesmal ein paar Nanosekunden kostet.

Allerdings kostet das Erstellen und Vernichten von Objekten generell etliches an Zeit. Deshalb macht man es bei zeitkritischen Anwendungen häufig so, dass man einen "Pool" von Instanzen erstellt, und nicht mehr benötigte Instanzen nicht vernichtet, sondern zur späteren Verwendung aufhebt. (Erfordert natürlich eine dedizierte Initialisierungsroutine anstelle des Konstruktors.) Und wenn der Pool nicht ausreicht, erstellt man gleich einen ganzen Bulk von Instanzen, dadurch wird der Speicher weniger "durchlöchert".

Kommentar von snagnar ,

Dass die Methoden nur einmal im Speicher vorhanden ist, erleichtert mir die Sache ungemein, vielen Dank für die Antwort.

Die Neustrukturierung des Speichermodells die du vorschlägst ist sehr interessant, ich werde mal versuchen, ob sich dies auch auf mein Programm übertragen lässt.

Kommentar von wolfgang1956 ,

Die Methoden sind nur ein einziges Mal im Speicher vorhanden, spielen also keinerlei Rolle bei der Erstellung einer weiteren Instanz, weder was die Zeit, noch was den Speicherbedarf betrifft.

Bezüglich der Rechenzeit ist das völliger Käse! Jeder Aufruf einer Methode kostet deren Rechenzeit. Wenn ich eine „kleine“ Methode erstelle, braucht die natürlich deutlich weniger Zeit als eine „große“ Methode. Wenn dann in einer solchen Methode auch noch Schleifen ablaufen, die 100.000 Mal durchlaufen werden, würde ich mir diesbezüglich Gedanken machen, diese Schleife auszulagern oder sehr sehr sehr kurz zu halten. Wenn dann die Schleifen verschachtelt sind, hat man sozusagen den zeitlichen Supergau.

Allerdings kostet das Erstellen und Vernichten von Objekten generell etliches an Zeit.

Falsch! Eine einzelne Instanz eines Objektes wird immer einmal erstellt und einmal vernichtet. Natürlich dauert das Erstellen der Instanzen länger wenn sie statt 10 Eigenschaften 100 Eigenschaften besitzen, die instanziiert werden sollen. Beim Löschen wird der Zeiger auf die Instanz und der von ihr belegte Speicher freigegeben. Das dürfte deutlich schneller gehen, als das Instanziieren von Objekten mit irgendwelchen Werten.

Natürlich kann man mit der Vernichtung von Objekten warten, bis man zu 100 % sicher ist, dass es nicht mehr gebraucht wird.

Antwort
von wolfgang1956, 22

Zunächst ist es völlig ausreichend, wenn du das Brett als Objekt einmalig erstellst. In der spielerischen Praxis ist es doch ebenso, dass du deinem Gegner gegenüber sitzt und ihr nicht nach jeder Berechnung ein neues Brett aufstellst. Dies würde bezüglich des Brettes schon einmal die programmtechnische Erzeugung des Objektes „Brett pro Knoten“ ersparen.

Dann sollte man sich Methoden zur Stellungsbewertung einfallen lassen, die Zugmöglichkeiten einsparen. Beispielsweise denken Schachspieler nicht über Züge nach, die „offensichtlich“ Material (Figuren) einstellen. Dieser Denkansatz ist für routinierte Schachspieler völlig normal.

Solche Methoden erfordern natürlich völlig andere Denkansätze, als wenn man quasi feststellt, wo die einzelnen Figuren stehen und welche Zugmöglichkeiten haben sie in der gegebenen Stellung. Dieses Brute-Force-Denken benötigt sehr schnell sehr viel Speicher, weil nach einem „Halbzug“ ja sämtliche anderen Möglichkeiten – außer im Schlagfall – weiterhin vorhanden und mitzurechnen sind.

Natürlich brauchen komplexe Methoden auch entsprechend mehr Zeit.

Kommentar von snagnar ,

Die "brett"-Bezeichnung mag etwas irreführend gemeint sein, in einer früheren Version hatte diese Klasse auch tatsächlich ein mehr oder weniger exaktes "Bild" eines Brettes, sprich ein zweidimensionales Array aus Zellen-Objekten, von denen einige besetzt waren und auf ein "Figur"-Objekt verwiesen. Da dies allerdings extrem speicher- und rechenzeitintensiv war, enthält das "brett"-Objekt bei mir nur noch eine Liste mit allen Figuren sowie zwei unordered_maps, mit der einen kann man anhand der Position auf die Figuren zugreifen, bei der anderen sind für jede Position die Figuren aufgeführt, deren Zugverhalten durch dieses Feld beeinflusst wird, sollte dorthin oder von dort weg gezogen werden. Dadurch müssen nicht alle Figuren geupdatet werden, sondern nur die notwendigsten.

Einen Ansatz, der es erlaubt, gewisse Zweige nicht zu berechnen, kann ich hierbei leider wenn überhaupt nur eingeschränkt verfolgen, da die KI in näherer Zukunft darauf ausgelegt sein soll, nicht nur Schach sondern auch andere Spiele wie TickTackToe, Dame oder VierGewinnt. Daher versuche ich, Bezüge im Programm, die explizit nur für Schach sind, zu vermeiden. Letztlich sollen das Bewertungsschema, die Zugvalidierung und das Zugausführen am Anfang aus einer Datei geladen werden, und somit das Programm möglichst universell sein.

Kommentar von wolfgang1956 ,

Mir ist schon bewusst, dass „professionelle“ Schachprogramme wie Fritz, Shredder, Green Chess uvam. „ihre“ Lösungen besitzen. Für die Berechnung der Züge muss man wissen, welche Figur welcher Farbe auf welchem Feld steht. Dabei kann man dieses 2D-Array auch so gestalten, dass neben den beiden Feldkoordinaten auch noch die Figurenart (Bauer, Läufer …) und die Figurenfarbe gespeichert sind. Dem 2D-Array für die Felder des Brettes wird ein weiteres 2D-Array überlagert, das die Figuren und die Figurenfarbe anzeigt.

Bezüglich der Algorithmen zu bestimmten Zugfolgen muss ich hier wirklich passen. Auf jeden Fall ist es Unsinn, „jeden“ nach den Regeln erlaubten Zug berechnen zu wollen. Inzwischen hast du richtig erkannt, dass man dafür ggf. sehr sehr viel Speicher braucht.

Da denken auch menschliche Schachspieler völlig anders als ein Computer. Wenn ich optisch erkenne, dass der geplante Damenzug die Dame ersatzlos einstellt, denke ich über diese Züge nicht nach. Nur in dem außergewöhnlichen Fall, dass dieser Zug ein Matt erzwingen würde, stelle ich die Dame auf ein Feld, auf dem sie geschlagen werden kann. https://de.wikipedia.org/wiki/Ersticktes_Matt Dies wäre so ein Beispiel!

Keine passende Antwort gefunden?

Fragen Sie die Community