Datenstrukturen richtig anlegen/laufzeitanalyse

[Ape50]

Hallo Leute,
ich hab mal eine Frage zur Laufzeitanalyse:
Was geht schneller? geg. sei int x

return x/Math.abs(x); oder

if(x>0)return 1;
return -1;

Dazu würde ich gerne verstehen, wie intern eine division stattfindet.

Hintergrund ist die programmierung eines schachcomputers. ich überlege grade wie ich meine strukturen am besten anlege. lieber eine figur aus einem int bestehen lassen oder aus zweien(farbe und "charakter").
evtl weiß ja jmd bescheid bzw kann mir ein paar tipps geben.

vielen Dank schonmal

 

[ARadauer]

ich denke dass die division auf jeden fall länger dauert

 

[Alex Unkreativ]

Eieiiei,
die Division wird länger dauern, aber das ist so was von egal! Selbst wenn die if-Abfrage fünf mal länger dauern würde, solltest du die nehmen. Wir haben nicht 1970 und du nur 640 Bit für deinen Schachcomputer. Auf der Ebene Optimierungen vorzunehmen, ist ein Fehler: Solche Rechenoperationen werden so schnell ausgeführt, dass sie gegenüber anderen Operationen nicht ins Gewicht fallen. Es ist deshalb egal, ob eine solche Methode genauso schnell oder 10x langsamer ist.
Was schwerer wiegt, ist die Erzeugung von Fehlern und schlechtem Code: Um zu verstehen, was du mit der Division bezwecken willst, braucht man einen Moment und es besteht die Gefahr, den Code misszuverstehen. Wenn nach dir Leute an dem Code arbeiten, werden sie mehr Zeit brauchen und fehlerhafteren Code schreiben.
Aber auch dein Code ist durch diesen Hack fehlerhafter: Was lifert die if-Abfrage zurück, wenn 0 als Eingabe kommt und was passiert bei der Division?

Deshalb als Goldene Regel: Programmiere so leserlich wie möglich und wenn es am Ende wirklich Performance-Probleme gibt, dann analysiere mit einem Profiler, wo du am besten ansetzen solltest und das werden sehr wahrscheinlich nie solche Stellen sein, sondern z. B. irgendwelche Collections mit Millionen Daten, irgendwelche schlecht formulierten SQL-Querys usw., die 10000x so viel Rechenzeit in Anspruch nehmen.

PS. Da du in einem Java-Forum gefragt hast: Üblicherweise werden Strukturen hier nicht in int codiert, sondern als Objekte. Das hieße konkret: Eine abstrakte Klasse namens Figur mit dem Attribut Farbe und einer abstrakten Methode move() von denen dann die Klassen Springer, Bauer, Turm etc erben.

 

[Ape50]

ok, also um auch komkret zu werden:
ich wollte diese move-methode in meine brettklasse verschieben, weil ich damit vermeiden kann jedem diesen kleiner feldern(also da, wo nur eine figur draufsteht) eine referenz auf das große brett mitgeben zu müssen. und dann reicht ein int bzw. sogar ein byte aus, um eine figur zu representieren.
deshalb kommt bei mir jetzt die frage auf,

wieviel platz kostet eine referenz?

 

[Alex Unkreativ]

Für eine Referenz kannst du vier Byte veranschlagen. Was ich nicht verstehe: Du hast 64 Felder und 32 Figuren. Warum machst du dir einen Kopf über den Platzverbrauch oder die Effizienz? Es wird sehr schwer werden, so schlechten Code zu produzieren, dass am Ende Effizienzprobleme auftreten. Du solltest lieber dein ganzes Augenmerk auf eine gute objektorientierte Struktur legen, denn die scheint mir noch nicht so weit gediehen.

Du willst eine move Methode in der Brettklasse haben, die für so unterschiedliche Figuren wie Bauer und Springer funktioniert? Oder du hast moveKnight(), movePawn(), ... Methoden in der Brett-Klasse? Das Brett hat aber mit der Bewegung der Figuren herzlich wenig zu tun. Deshalb ist das vom OO-Standpunkt aus gesehen, nicht sonderlich glücklich.

Ich würde es in etwa so angehen:
Du hast eine Hauptklasse Chessgame, die hat ein Chessboard Objekt, das hat wiederum 64 Square Objekte im 2 dimensionalen Array (hier könnte man überlegen, auf die Objekte zu verzichten, da ein Feld ja im Grunde keine Aufgabe hat, dann würde auch ein 2-dim int-Array reichen). Dann hast du wie schon angemerkt, eine abstrakte Klasse Figur und entsprechende Pawn, King etc. Objekte, die die abstrakte move Methode von Figur überschreiben. Dann brauch es noch ein Arbiter Objekt, das jeden Zug auf Korrektheit prüft (da dies von anderen Figuren abhängt, kann die Korrektheitsprüfung nicht (nur) auf Ebene der Figur stattfinden, weil man ihr sonst wirklich den gesamten Spielzustand übergeben müsste). Zudem hast du noch die Klasse Player. Das Chessgame Objekt führt jetzt all diese Objekte zusammen und koordiniert die Interaktion zwischen den einzelnen Objekten.

 

[Ape50]

also mein programm funktioniert schon, alles ist gut. aber ich möchte jetzt eben einen sehr guten computer schreiben. da schach ja noch lange nicht gelöst ist, denke ich, es ist durchaus wichtig auf laufzeiten und größen des programms zu achten, denn dadurch kann ich doch letztlich weiter in die zukunft gucken. also treten bei jedem chachcomputer heute platz oder effizienzprobleme auf, sonst wärs ja gelöst....
meine move-methode fragt ab, was für eine figur(wird durch einfaches int/byte charackterisiert) auf dem betrachteten square steht. und dann gibt sie eine linked list von squares oder int[](koordinaten) zurück.
meine sqares haben sehrwohl mehrere referenzen, z.b zeigen sie auf benachbarte figuren und auch sqares. das spart viel rechenzeit bei z.b der berechnung, ob nach einem zug schach ist, oder auch bei komplexeren bewertungsmethoden eines boards.
ich will mir nur grade ganz genau überlegen, wie und wie groß ich mein brett mache um eben sehr schnell bestimmte sachen ausrechnen zu können und diese dinge will ich dann natürlich auch möglichst effizient berechnen.

ich sehe irgendwie keinen sinn darin, figurklassen zu entwerfen, die dann auf mein ganzes brett zugreifen müssen, um zu wissen wie sie ziehen können. dann kann ich das doch gleich das brett machen lassen. wenn ein square weiß was auf ihm draufsteht reicht das doch. (klar wie immer zeit vs platz .....)

stellst du dir das so vor, dass z.b. die dame alle züge ausgibt, die sie auf einem leeren brett vom aktuellen standort zeihen könnte und dann geh ich im brett diese liste durch und lösche die züge, die nicht gehen? das ist ein ziemlich hoher aufwand, denke ich.

 

[Alex Unkreativ]

Das Problem mit dem Schachprogramme konfrontiert sind, ist das exponentielle Wachstum der möglichen Züge, das wirst du auch nicht durch eine besonders effiziente Implementierung überwinden können und auch keine wahrnehmbar bessere Laufzeit erhalten.

Ich frage mich halt, ob du nicht mit so einer unsauberen Implementierung nicht sehr schnell in Probleme läufst: Deckst du z. B. ab, ob eine große Rochade möglich ist und auch, wenn der Turm dann Schach bietet? Hier ist eine sauberes OO-Design eine große Hilfe, weil du auch solche Spezialfälle sauber einbauen kannst.

ich sehe irgendwie keinen sinn darin, figurklassen zu entwerfen, die dann auf mein ganzes brett zugreifen müssen, um zu wissen wie sie ziehen können. dann kann ich das doch gleich das brett machen lassen. wenn ein square weiß was auf ihm draufsteht reicht das doch. (klar wie immer zeit vs platz .....)

Die müssen nicht auf das ganze Brett zugreifen, die müssen ihren Standort kennen und daraus ermitteln sie die für sie erreichbaren Felder. Dieses Wissen "gehört" ihnen und sollte in den Figuren-Objekten gekapselt sein. Die erreichbaren Felder geben sie dann nach außen und dort entscheidet die Player-Klasse unter Berücksichtigung der Schiedsrichter-Klasse welcher Zug von allen Figuren möglich ist und welcher der Beste ist.

stellst du dir das so vor, dass z.b. die dame alle züge ausgibt, die sie auf einem leeren brett vom aktuellen standort zeihen könnte und dann geh ich im brett diese liste durch und lösche die züge, die nicht gehen? das ist ein ziemlich hoher aufwand, denke ich.

Ja, so in etwa. Die Frage ist, wie willst du es sonst machen? Bestimmte Zugmöglichkeiten unberücksichtigt lassen? Du musst doch im Grunde alle Möglichkeiten aufzählen und irgendwie checken, ob sie funktionieren oder nicht. Natürlich kannst du aufhören, wenn Läufer auf H8 steht und direkt einen Bauern vor der Nase hat, dann musst du nicht noch checken, ob er A1 erreichen kann, aber mehr an Optimierungspotential sehe ich nicht. Da die Anzahl an möglichen Zügen in einem Schritt sehr gering ist, stellt das aber auch kein Effizienzproblem dar.
Wie gesagt, das Dilemma aller Schachprogramme ist das exponentielle Wachstum, also dass du nach 20 Zügen geraten 2^80 Möglichkeiten hast, wie die Figuren angeordnet sein können. Deshalb gibt es hier auch nichts zu lösen oder durch Programmiertricks das Programm so effizient zu machen, wie es die Entwickler von Shredder&co nicht können. Es gibt eine Grenze, die durch die Komplexität des Spiels selbst bestimmt ist. Der Trick von Shredder&co besteht darin, bestimmte sehr aussichtsreiche Strategien weiter vorauszuberechnen und dafür wenig erfolgsversprechende zu ignorieren. Quasi Depth First Search statt BFS. Auch wenn ihnen dabei eine Partie wie die Byrne vs. Fischer entgehen würde, weil sie nie ein Damenopfer weiterberechnen würden.

 

[Ape50]

also nochmal, mein programm kann alles, ich kann gegen einen computer spielen, der garnich so blöd ist, wenn ich überlege, gewinne ich aber....
ich will jetzt einfach-weil ichs interessant finde- ein programm schreiben, was mich locker schlägt.

[

Deckst du z. B. ab, ob eine große Rochade möglich ist und auch, wenn der Turm dann Schach bietet?

also meine brettklasse merkt sich welche rochaden noch möglich sind(genauso hat sie einen enpassant-merker) aber was meinst du mit "wenn der turm schachsagt"?

Die müssen nicht auf das ganze Brett zugreifen, die müssen ihren Standort kennen und daraus ermitteln sie die für sie erreichbaren Felder

aber welche felder für sie erreichbar sind, hängt doch vom brett ab.

Ja, so in etwa. Die Frage ist, wie willst du es sonst machen? Bestimmte Zugmöglichkeiten unberücksichtigt lassen?

ich lasse keine möglichen züge unberücksichtigt, aber wenn man z.b. grade im schach steht, muss ich mir nicht angucken, wie eine figur ziehen kann, die am schach sein nichts ändert, wenn der zug dann nachher sowieso aus der liste der möglichen züge wieder rausgenommen werden muss.

das Dilemma aller Schachprogramme ist das exponentielle Wachstum

das ist mir klar, aber grade deshalb sollten doch methoden, die man dann eben 2^80 mal ausführt, optimal sein. denn die haben doch einen entscheidenden anteil daran, wie lange er rechnen muss.

Quasi Depth First Search statt BFS

das sagt mir beides nichts...kannst du das kurz erläutern, was damit gemeint ist?

 

[Alex Unkreativ]

Zitat:
Deckst du z. B. ab, ob eine große Rochade möglich ist und auch, wenn der Turm dann Schach bietet?
also meine brettklasse merkt sich welche rochaden noch möglich sind(genauso hat sie einen enpassant-merker) aber was meinst du mit "wenn der turm schachsagt"?

Wenn du eine Rochade machst, kann es vorkommen, dass der Turm danach dem anderen König Schach bietet. Was ich damit im Grunde nur sagen möchte: Es können recht komplexe Situationen entstehen und deshalb ist eine gute Programm-Struktur so relevant, weil ab einer gewissen Komplexitätsstufe rächen sich solche schnellen Hacks. Aber wenn dein Programm gut funktioniert, dann müssen wir das ja nicht mehr ausdiskutieren.

Zitat:
Die müssen nicht auf das ganze Brett zugreifen, die müssen ihren Standort kennen und daraus ermitteln sie die für sie erreichbaren Felder
aber welche felder für sie erreichbar sind, hängt doch vom brett ab.

Ich meine damit: Der Bewegungsradius gehört zur Figur, dass ein Turm nur gerade gezogen werden kann, ist sein Wissen, ob nach seinem Zug ein konsistenter Zustand erreicht wurde, ist das Wissen des Bretts oder der Schiedsrichter-Klasse.
Jetzt kodierst du das Spezialwissen der Figuren alles in der Brett-Klasse, wenn es jetzt nicht um Schach ginge, sondern um ein anderes Szenario und du müsstest eine Figur hinzufügen, müsstest du bei deinem Vorgehen die zentrale Brettklasse ändern und im worst case das ganze Programm an vielen Stellen anpassen und ändern. In meinem Szenario würdest du einfach eine neue Figurklasse hinzufügen, die genau ihren Bereich abdeckt und müsstest an dem Programm sonst im Grunde nichts ändern.

Ja, so in etwa. Die Frage ist, wie willst du es sonst machen? Bestimmte Zugmöglichkeiten unberücksichtigt lassen?
ich lasse keine möglichen züge unberücksichtigt, aber wenn man z.b. grade im schach steht, muss ich mir nicht angucken, wie eine figur ziehen kann, die am schach sein nichts ändert, wenn der zug dann nachher sowieso aus der liste der möglichen züge wieder rausgenommen werden muss.

Ja, aber das sind ja wirklich seltene Spezialfälle. Du musst ja aber schon irgendwie für jede Figur feststellen, dass sie an dem Schach nichts ändern kann. Ich sehe noch nicht so genau, dass das viel effizienter ist.

das Dilemma aller Schachprogramme ist das exponentielle Wachstum
das ist mir klar, aber grade deshalb sollten doch methoden, die man dann eben 2^80 mal ausführt, optimal sein. denn die haben doch einen entscheidenden anteil daran, wie lange er rechnen muss.

Der Clou am exponentiellen Wachstum ist halt, dass du eine Methode eben nicht 2^80 mal ausführen kannst, es sei denn, du überredest Google dir deren Rechenkapazitäten zu geben. Nehmen wir an, du hättest einmal ein sauber in Java codiertes Programm und ein in Assembler hoch effizient gecodetes Programm. Du würdest mit dem Java Programm vielleicht 13 Züge im Voraus berechnen und mit dem Maschinencode-Programm 14 Züge. Die Anzahl der Züge wächst so stark, dass es nicht so sehr auf das letzte Quentchen Effizienz ankommt.

Quasi Depth First Search statt BFS
das sagt mir beides nichts...kannst du das kurz erläutern, was damit gemeint ist?

DFS bedeutet, dass man erst in die Tiefe sucht, bis man am Ende anlangt oder bei einem Abbruchkriterium und Breitensuche (BFS) bedeutet, dass man parallel an jeder Stelle um eins weitergeht. Wenn du BFS anwendest und alle Züge checkst, auch wenn du z. B. sofort die Dame opferst und dennoch diese Weg weiterverfolgst, dann bleiben keine Ressourcen, um die erfolgsversprechenden Varianten in viel tiefere Bereiche zu berechnen. Anderseits verbaust du dir auch kreative Lösungen, wie sie Bobby Fischer in der zitierten Partie gefunden hat. So eine Lösung würde ein Computer wahrscheinlich nicht finden.

 

[Ape50]

ok,
auf jeden fall erstmal vielen vielen dank für deine gedanken!

ich nehme auf jeden fall mit nicht so streng mit meiner struktur zu sein. versuche zwar, da wo es ohne probleme geht, meine strukturen möglichst klein zu halten, merke mir dafür aber erstmal relativ viel, um ohne züge wirklich zu ziehen, weiter denken zu können.
ein paar sachen schieb ich erstmal nach hinten, da du auf jeden fall recht hast mit dem exp-wachstum des schachbaums...selbst wenn ich alle meine einfachen methoden 20 mal schneller mache, kann ich nur eine tiefe weiter rechnen....

nochmal zu den figuren...ich habe mich entschlossen bei meiner struktur zu bleiben, vor allem weil ich mit meiner auch von squares, auf der keine dame steht, mir alle damenzüge geben lassen kann. sicherlich hast du recht, ich kann nicht einfach so auf ein 10 figuren-schach oder vergleichbare spielchen wechseln, aber dafür muss ich dann eben ein anderes board schreiben, nehm ich in kauf.

ich hab mir mal ne boardvergleich-klasse geschrieben, die randomzüge zieht und alle möglichen züge auf verschiedenen boards vergleicht. die zieht dann einfach gegen sich selbst vor sich hin und wenn unstimmigkeiten auftreten, bricht es ab, so kann ich mir ziemlich sicher sein, dass meine boards die regeln wirklich richtig beherschen(dass beide den gleichen fehler haben, halte ich für unwarscheinlich)

wie ich meinen baum aufbaue, weiß ich noch nicht wirklich. ich habe zwar einige ideen, aber wie ich sie verwirklichen kann, wird sich dann zeigen. werd mir mal noch ein bisschen über dfs und bfs durchlesen und mich inspirieren lassen....

viele grüße
ape

 

[Lonsdaleit]

Zu deinem Schachcomputer nochmal einige Denkanstäße:

Es sind weniger einzelne Rechenoperationen das Problem, sondern eher die große Anzahl an möglichen Stellungen je mehr Züge der Computer vorrausberechnen soll. Du solltest dir also eher Gedanken darüber machen, an welchen Stellen du den Baum stutzen kannst und somit dafür sorgen möglichst viele der (sowieso nicht in Frage kommenden Stellungen) zu eliminieren.

Wenn du ein Computer willst der dich schlägt, arbeite an der Bewertung von den Stellungen. Welche Kriterien verwendest du hier? Wie sind die Kriterien gewichtet? Eine gute Möglichkeit ist hier auch, den Computer die Gewichtung der Kriterien anpassen zu lassen, je nach dem was zu gewonnen und was zu verlorenen Spielen führt.

Ich weiß nicht, wie du deinen Schachcomputer programmiert hast - ich selbst sitze auch gerade an der Implementierung eines Schachcomputers - die Theorie/Algorithmik hatte ich vor einigen Jahren mal als Thema für einen Fachvortrag meines Studiums. Damals war allerdings keine Programmierung vorgesehen - das hole ich jetzt aus Interesse nach.

Jedenfalls solltest du alle möglichen Stellungen in n Zügen berechnen, diese gewichten/analysieren und dann dem Baum entlang die zu ziehende Stellung anhand der Bewertung weitergeben - je nach dem welcher Spieler am Zug ist, die beste oder schlechteste bewertete Stellung.
Und hier ist genau der Punkt an dem du Rechenzeit einsparen solltest - die Anzahl der zu analysierenden Stellungen.

lg
Lonsdaleit