Schach - Fehlerbeseitigung

[Danny92]

Ich habe im Anhang mein geschriebenes Schachprogramm angehängt. Leider funktioniert es nicht so ganz perfekt. Manchmal zieht die KI einen meiner Figuren, oder sie folgt nicht den Regeln. Zum Beispiel kam es vor, dass die KI hin und wieder das Schach nicht parierte.

Dass es nicht gerade effizient programmiert ist, kann ich mir aufgrund der Langsamkeit (Schwierigkeitsstufe höchstens auf 2 Züge vorraus) schon denken. Auch sind ein paar Einzelheiten, wie beispielsweise die Rochade oder die Bauernumwandlung, noch nicht programmiert. Ich sitze schon sehr lange nur an der KI und bekomme sie einfach nicht schnell, oder zumindest fehlerfrei, programmiert.

Ich würde mich freuen, wenn jemand den einen oder anderen Fehler darin erkennen und ihn mir mitteilen würde. Ich kann nämlich echt nichts mehr finden. Auch über hilfreiche Tipps freue ich mich!

Vielen Dank!

[freimatz]

Hallo,
habe nur kurz reingeschaut. Erster Tpp: dokumentiere mal alles. Da machst du es erstens anderne leichter den Code zu verstehen und zum anderen kommst du dann eher selber drauf was falsch läuft.

[TurboMagic]

Nutze dazu am besten xmldoc Kommentare. Vor einer Methoden Deklaration Strg-J daran s und summary auswählen. Enter und Kommentar schreiben. Mit der Maus dann über einen Aufruf der Methode fahren...
Gibt es auch als param und return

[Danny92]

Ja ich war noch nie ein großer Fan von Kommentaren, der Code ist ohnehin schon lange genug. Ich verstehe dass Kommentare zur Verständlichkeit beitragen mögen. Ich habe aber versucht, den Funktionen, Prozeduren und Variablen sprechende Namen zu geben, die eigentlich schon für sich sprechen. Also was die boolesche Funktion "IstSchach" macht oder was in vkoenigweisskoordinate vom Typ TPoint gespeichert ist, muss ich ja wohl nicht groß erläutern. Aber ich beantworte gerne jede unklare Frage.

Ich habe das Programm nochmal bearbeitet und bin auch schon viel weiter gekommen: Das Programm ist jetzt spielbar und die KI sollte keine Fehler mehr machen; Schach, Patt und Matt wird erkannt und en passant sollte ebenfalls funktionieren. Bauernumwandlung und Rochade muss ich immer noch implementieren. Mir ging es aber wie gesagt zunächst um die Fehlerbehebung, damit es überhaupt spielbar ist. Ob die KI auch als schwarz fehlerfrei arbeitet, habe ich noch nicht getestet.

Nun geht es mir nur noch um die Spielstärke und dann zuletzt noch um die Effizienz bzw. Schnelligkeit. Selbst bei acht vorausberechnenden Zügen (wo die KI hier schon (zu) lange rechnen muss) gewinnt man immer noch spielend leicht, was eigentlich gar nicht sein dürfte/sollte. Daraus schließe ich, dass in dem Quellcode, genauer gesagt im Alpha-Beta-Algorithmus (welcher für solche Spiele gängig ist) oder vielleicht auch in der Bewertungsfunktion, ein Fehler stecken muss. Und den zu finden, finde ich fast unmöglich in Anbetracht der Komplexität des Programms. Kann mir da irgendwer weiterhelfen?

Ansonsten macht es jetzt schon echt Spaß mit dem Programm rumzuspielen..

Danke.

[DieDolly]

Zitat:

Selbst bei acht vorausberechnenden Zügen (wo die KI hier schon (zu) lange rechnen muss)

Alles eine Frage der Codeeffizienz. Hier gibt es bestimmt Optimierungsmöglichkeiten (habe nicht in deinen Code reingeguckt).
Vielleicht hilft dir diese Seite https://www.chess.com/de/analysis

[Danny92]

Wie macht man denn zum Beispiel den Code effizient? Ich könnte u. a. ausschließlich Referenzparameter in den Methoden übergeben, um zeit-intensives Kopieren der Variablen zu sparen. Außerdem verwende ich mit Mergesort schon einen Sortieralgorithmus mit bester asymptotischer Laufzeit. Die Vorsortierung der Züge anhand ihrer Bewertungen wird ja beim Alpha-Beta-Algorithmus ohnehin empfohlen. Aber viel mehr weiß ich dann auch nichts effizienter zu machen...

Die Website ist echt interessant, aber ob mir das viel weiterhelfen wird...

[DieDolly]

Zitat:

Ich könnte u. a. ausschließlich Referenzparameter in den Methoden übergeben, um zeit-intensives Kopieren der Variablen zu sparen.

Wirklich zeitintensiv ist das nicht. komplexere Datentypen werden soweit ich weiß ohnehin referenziert und nicht kopiert.

Mit Optimierungen meinte eigentlich, besseren Code im Allgemeinen.

PS.: ich denke es würden dir wesentlich mehr Leute helfen, wenn dein Projekt ein vernünftiges Delphiprojekt (:thumb:) wäre und keines von Lazurus (:kotz:)
Die Emotes bitte nicht ernst nehmen.

[hanvas]

Zitat:

Zitat von Danny92 (Beitrag 1428502)

Wie macht man denn zum Beispiel den Code effizient? Ich könnte u. a. ausschließlich Referenzparameter in den Methoden übergeben, um zeit-intensives Kopieren der Variablen zu sparen.

Das bringt bei bestimmten Datentypen (zb. Arrays und Pascal - Strings) mehr Effizienz, aber nicht var sondern const verwenden.

Zitat:

Außerdem verwende ich mit Mergesort schon einen Sortieralgorithmus mit bester asymptotischer Laufzeit.

Ein besserer/effizienter/schnellerer Algorithmus, sofern es einen gibt ist sicher die beste Lösung. Dein Sortierverfahren ist ja nur ein Teil des Algos.

Falls es keinen besseren Algorithmus gibt fängt man an zu optimieren. Dabei würde ich Dir zunächst einen Profiler empfehlen um zu sehen wo es eigentlich hakt.

Oft fressen ein paar "kleine" Codeteile den größten Teil der Zeit.

Makros - also mit Inline deklarierte Methoden - sind für kurze Methoden oft eine gute Möglichkeit den Overhead der durch den Aufruf einer Methode erzeugt wird zu minimieren. Das macht aber nur Sinn wenn die Methode relativ klein ist und sehr häufig aufgerufen wird. Je öfter eine Methode / Prozedur / Funktion aufgerufen wird umso größer ist der Gewinn.

Man kann Laufzeit durch Speicher ersetzen.

Also soviel wie möglich im voraus berechnen. Nachschlage und Sprungtabellen erstellen usw.

Insbesondere dann wenn sich die Berechnungen in einer Schleife, oder im inneren von inneren von inneren (usw) Schleifen befinden. Jede Ebene die man Berechnungen nach oben bringt spart Rechenzeit. Dabei darf man, wenn es um Optimierung geht, auch nicht unbedingt Angst vor globalen Variablen haben.

Of werden am Anfang und Ende von Schleifen Initialisierungsarbeiten durchgeführt, also Speicher allokiert und freigegeben, Werte berechnet und Variablen initialisiert. Manchmal sind solche Initialisierungen ganz oder teilweise nur ein mal notwendig, werden aber dennoch jedesmal durchgeführt, manchmal kann man Variablen in Tabellen aufnehmen und auf diese zugreifen anstatt diese jedesmal in einer Schleife erneut zu berechnen. Im Zweifelsfall führt man einmal eine Schleife mit den Initialisierungsarbeiten (und gleichen Indexen) aus, und ein zweitesmal eine Art "Arbeitsschleife"

Wichtig ist, alles was man macht ausgiebig zu dokumentieren. Optimierter Code wird schnell unleserlich, weil man Stil zu Gunsten von Geschwindigkeit aufgibt. Diesen Nachteil sollte man durch ausgiebiges Dokumentieren ausgleichen. Variablennamen zu kürzen macht bei einer Compilersprache aber keinen Sinn.

Eine weitere Möglichkeit ist die parallele Verarbeitung. Wenn Du das vor hast, solltest Du deinen Code aber paralellisieren bevor Du dich daran machst ihn wie oben beschrieben zu optimieren. Bei paralellisierten Code ist Lesbarkeit zunächst oberstes Gebot.

hth

Ha-Joe

[Danny92]

Gibt es denn einen Profiler für Lazarus? Soweit ich was gefunden habe gibt es welche nur für Delphi.


Auf jeden Fall spielt er jetzt so gut wie einwandfrei. Alles sollte jetzt funktionieren! Nur an der Performance muss ich noch ein wenig arbeiten!

https://www.file-upload.net/download...chach.zip.html

Hier der Downloadlink zur zip, welcher wegen der enthaltenen project.exe größer war als 5 MB.8-)

[hanvas]

Zitat:

Zitat von Danny92 (Beitrag 1428607)

Gibt es denn einen Profiler für Lazarus? Soweit ich was gefunden habe gibt es welche nur für Delphi.

http://wiki.lazarus.freepascal.org/Profiling

http://wiki.freepascal.org/LazProfiler
http://wiki.lazarus.freepascal.org/FPProfiler
http://www.prodelphi.de/detailLinux.html

hth Ha-Joe