Optimierung beim Speichern
-
Hallo
Ich kann es a priori nicht abschätzen, welche der beiden Versionen schneller sein wird. Folgender Aufbau ist der elementare Teil von 4 Zuggeneratoren innerhalb einer Schachengine. Der Zeitkonsum dieser Algorithmen ist prozentual relativ hoch. Daher sind auch solche Überlegungen zur Optimierung durchaus sinnvoll.
Ich würde vermuten Version B lässt sich vom Compiler besser optimieren. Aber ich weiss es nicht, und der Aufbau eines Experimentes würde 2-3 Tage dauern.
Version A
... // generate queen moves pieces = queen_bitboard(me); while (pieces != 0) { from = find_first_bit_and_clear(pieces); moves = queen_attack_bitboard(from, blocker_bb) & squares; while (moves != 0) { move_list[i++] = make_move(from, find_first_bit_and_clear(moves)); } } ...Version B
... // generate queen moves pieces = queen_bitboard(me); while (pieces != 0) { from = find_first_bit_and_clear(pieces); moves = queen_attack_bitboard(from, blocker_bb) & squares; while (moves != 0) { *move_list++ = make_move(from, find_first_bit_and_clear(moves)); } } ...Danke schonmal für eure Tipps
-
der operator[] bei zeiger[i] ist kostenlos, das zaubert der prozessor mit viel hardware.
daher kann man ruhig (unsigned) integers laufen lassen statt zeigern. was konkret besser ist, kann ich hier nicht abschätzen. manchmal erlaubt die integerlauferei eine feste obergrenze oder sowas und man braucht mit integercode ein register weniger. das dankt einem dann der compiler.
*movelist++= sieht mir danach aus, als wäre es supi, weil das dann nur dewr eine zeiger ist und der macht auch nie was anderes als der reinschreibzeiger zu sein. klingt nach einem register weniger als movelist UND i.
-
Änderung einbauen, Assemblerausgabe von A und B vergleichen, höchstwahrscheinlich feststellen, dass A und B identisch rauskommen
-
Tim schrieb:
Änderung einbauen, Assemblerausgabe von A und B vergleichen, höchstwahrscheinlich feststellen, dass A und B identisch rauskommen
Auch meine Vermutung. Eventuell lässt sich in den Funktionen noch etwas mehr optimieren (vorzeitiges return, etc.).
-
Tomahawk schrieb:
Der Zeitkonsum dieser Algorithmen ist prozentual relativ hoch.
Wieviel denn konkret?
Mit solchen Mikrooptimierungen wirst du die Spielstärke im Allgemeinen nur wenig steigern können. Wenn der Zuggenerator halbwegs schnell ist, solltest du dich eher damit befassen, die guten Züge vor den schlechten durchzurechnen. Das bringt viel mehr (weil es die exponentielle Minimax-Laufzeit in Angriff nimmt).
Wenn der Generator trotzdem optimiert werden soll, ein paar Fragen:
Berechnest du das Bitboard jedesmal neu?
Ist die Funktion für alle Richtungen zuständig oder nur für eine?
Wie viele Berechnungen kann der Generator im Voraus machen, damit er später nur noch nachschlagen muss?
-
mngbd schrieb:
Tomahawk schrieb:
Der Zeitkonsum dieser Algorithmen ist prozentual relativ hoch.
Wieviel denn konkret?
Er hat sich solche Mühe gegeben, daß mal keiner daran rummeckert, daß er eine konkrete Speed-Frage hat.
-
mngbd schrieb:
Tomahawk schrieb:
Der Zeitkonsum dieser Algorithmen ist prozentual relativ hoch.
Wieviel denn konkret?
Mit solchen Mikrooptimierungen wirst du die Spielstärke im Allgemeinen nur wenig steigern können. Wenn der Zuggenerator halbwegs schnell ist, solltest du dich eher damit befassen, die guten Züge vor den schlechten durchzurechnen. Das bringt viel mehr (weil es die exponentielle Minimax-Laufzeit in Angriff nimmt).
Wenn der Generator trotzdem optimiert werden soll, ein paar Fragen:
Berechnest du das Bitboard jedesmal neu?
Ist die Funktion für alle Richtungen zuständig oder nur für eine?
Wie viele Berechnungen kann der Generator im Voraus machen, damit er später nur noch nachschlagen muss?
Naja, die Summe der Microoptimierungen macht es doch, oder!?
Der Zuggenerator ist schon halbwegs schnell, aber wegen der von dir erwähnten Problematik der Zugsortierung, muss ich neue Generatoren bauen. Wenn ich dies schon tun muss, möchte ich zusätzlich auch einige Microoptimierungen einfliessen lassen.
Ist zwar etwas Off Topic:
Nein, die Bitboards Look-Up-Tables werden einmal initialisiert und anschliessend über einen perfect Hashalgorithmus ausgelesen. Und ja, es werden auf einen Schlag alle Richtungen ausgelesen (auch die der Gleitfiguren).
Kann bei Interesse den ganzen Algorithmus hier posten, auch wenn es dann eher ins Forum für Programmierung von Spielen gehört.
-
Tomahawk schrieb:
Naja, die Summe der Microoptimierungen macht es doch, oder!?
Der Zuggenerator ist schon halbwegs schnell, aber wegen der von dir erwähnten Problematik der Zugsortierung, muss ich neue Generatoren bauen. Wenn ich dies schon tun muss, möchte ich zusätzlich auch einige Microoptimierungen einfliessen lassen.
Das ist eine Möglichkeit: dem Generator eine implizite Heuristik einbauen, so dass man hoffen kann, dass die guten Züge zuerst kommen. Was sich immer zumindest ein wenig auszahlt, ist, zuerst die schlagenden Züge und die Figurenzüge zu generieren, und dann den Rest.
Aber ein guter Suchalgorithmus ist das allerwichtigste. Das habe ich oben eher trocken ausgedrückt: wenn du den Generator um 30% schneller machst, und unter der Annahme, dass die halbe Laufzeit für das Generieren draufgeht, wird das Programm dann um 15% schneller sein. In dem Sinn macht die Summe der Mikrooptimierungen was aus.
Wenn dein Ziel aber ist, 1 ply weiter in die Zukunft zu schauen, werden in der letzten Baumebene noch jeweils ca. 35 Züge möglich sein, die alle evaluiert werden müssen. Wenn du bis dahin 35 * 35 Züge evaluiert hast, muss du nun 35 * 35 * 35 Züge evaluieren, das macht 3500% Mehraufwand. Davon kannst du 15% wegnehmen, die die Generator-Optimierung ergeben hat, dann sind es immer noch 3000%. Das ist so ziemlich der worst case, aber das Problem sollte klar werden: die Güte des Generators geht linear in die Spielstärke ein, aber die Güte der Suchfunktion exponentiell (von der Suchtiefe aus gesehen).
Ich mache das deshalb so: zuerst lasse ich mir die Züge generieren, dann sortiere ich sie nach ihrer geschätzten Stärke. Die Stärke eines Zuges schätze ich, indem ich eine kleine Suche mit 2 bis 4 ply Tiefe mache, unter Umständen mit einem eingeschränkten Suchfenster. 2 ply Tiefe kann ich zum Beispiel ohne merklichen Zeitverlust durchsuchen. Dafür habe ich dann eine viel bessere Sortierung der Züge, und das macht sich dadurch bezahlt, dass mir ganze Äste des Baumes wegfallen, weil sie zu schlechteren Zügen gehören. Für spätere tiefere Suchen kann ich die Ergebnisse auch in einer Tabelle speichern, aber auch das macht gar nicht so viel aus, weil die letzte Ebene am meisten Zweige hat, und die bessere Sortierung das exponentielle Anwachsen gedämpft hat.
Tomahawk schrieb:
Ist zwar etwas Off Topic:
Nein, die Bitboards Look-Up-Tables werden einmal initialisiert und anschliessend über einen perfect Hashalgorithmus ausgelesen. Und ja, es werden auf einen Schlag alle Richtungen ausgelesen (auch die der Gleitfiguren).
Bei meiner Engine mache ich jede der 4 Gleit-Richtungen separat. Da habe ich für eine Richtung 64 mögliche Ausgangsfelder, und höchstens 256 verschiedene Konstellationen auf dieser Geraden. Die berechne ich im Voraus und lege sie nach Feld und Konstellation ab. Mit passend rotierten Bitboards kann ich die Konstellation mit ein paar billigen Bitoperationen ausrechnen. Bis jetzt glaube ich, dass das völlig ausreichend ist.
Tomahawk schrieb:
Kann bei Interesse den ganzen Algorithmus hier posten, auch wenn es dann eher ins Forum für Programmierung von Spielen gehört.
Würde mich interessieren. Wenn möglich, würde ich mir das ganze Ding gerne ansehen. Das Spiele-Forum geht eher in die Grafik-Richtung, RudP wäre auch nicht schlecht, aber egal, man kann ja Links machen.
-
Tomahawk schrieb:
Aber ich weiss es nicht, und der Aufbau eines Experimentes würde 2-3 Tage dauern.
Du meintest wohl 2 - 3 Minuten? Ich hab' ein paar Compiler mit einem reduzierten Bsp. gefüttert, die meiste Zeit ging für's Starten der VMs drauf.
Version B war auch da schneller, wo ich es nicht unbedingt erwartet hätte - identischen ASM- Code hat übrigens kein Compiler erzeugt (hätte mich auch gewundert).
Wunder darfst Du nicht erwarten, aber ein paar Prozent (bis so knapp zweistellig) sind drin.
Hoffe, das hilft Dir ...
-
pointercrash() schrieb:
Tomahawk schrieb:
Aber ich weiss es nicht, und der Aufbau eines Experimentes würde 2-3 Tage dauern.
Du meintest wohl 2 - 3 Minuten? Ich hab' ein paar Compiler mit einem reduzierten Bsp. gefüttert, die meiste Zeit ging für's Starten der VMs drauf.
Version B war auch da schneller, wo ich es nicht unbedingt erwartet hätte - identischen ASM- Code hat übrigens kein Compiler erzeugt (hätte mich auch gewundert).
Wunder darfst Du nicht erwarten, aber ein paar Prozent (bis so knapp zweistellig) sind drin.
Hoffe, das hilft Dir ...Ähnliche Test habe ich auch schon gemacht. Da waren die Messungen zu ungenau für eine definitive Festlegung. Muss es fein säuberlich implementieren und dann vergleichen. Anders werde ich keine Aussage treffen können. Trotzdem danke !
Ergebnisse folgen...
-
Die Implementierung war relativ aufwendig.
Kann jetzt aber aussagekräftige Ergebnisse liefern:
Version B ist etwas schneller. Das liegt aber auch daran, dass die entsprechenden Sortieralgorithmen für die Schachzüge ebenfalls auf Pointerebene ablaufen, und diese konsumieren mehr Rechenzeit als die Zuggeneratoren selbst.
Eine quantitative Aussage ist schwer. Schätze mal dass die Generatoren für sich genommen weniger als 20% schneller geworden sind. Am Ende bleiben bei Brute-Force Rekursionen noch 10% übrig.
Grüsse