Welches Paradigma für das Schreiben einer Schachengine?

9

Wenn Sie eine Schachspiel-Engine schreiben würden, welches Programmierparadigma würden Sie verwenden (OOP, Prozedur usw.) und warum sollten Sie es wählen? Mit Schach-Engine meine ich den Teil eines Programms, der das aktuelle Board auswertet und über den nächsten Zug des Computers entscheidet.

Ich frage, weil ich dachte, es könnte Spaß machen, eine Schachmaschine zu schreiben. Dann kam mir der Gedanke, dass ich es als Projekt zum Erlernen der funktionalen Programmierung verwenden könnte. Dann kam mir der Gedanke, dass einige Probleme für das Funktionsparadigma nicht gut geeignet sind. Dann kam mir der Gedanke, dass dies ein gutes Diskussionsfutter sein könnte.

Sack
quelle
1
Dies ist vergleichbar mit dem Schreiben eines C-Compilers von Grund auf neu. Ich würde das Rad nicht neu erfinden. Ich würde zuerst die vorhandenen studieren.
Job
10
@Job: Mein Ziel ist eher der Prozess als das Ergebnis. Selbst wenn ich am Ende eine sehr schlechte Engine habe, denke ich, dass es wertvoll sein könnte, das Problem zu analysieren und einen Weg zu finden, es anzugreifen, insbesondere wenn ich dabei einige neue Programmiermethoden gelernt habe.
stupsen
1
Viel Glück. Kein wirklicher Arbeitgeber wird Sie jemals bitten, einen von Grund auf neu zu entwickeln, aber während eines Interviews werden Sie möglicherweise gefragt, wie Sie das Problem angreifen würden.
Job
6
@Job Ein großer Teil des Programmierlebens besteht darin, Dinge zu codieren, nicht weil sie definitiv benötigt werden, sondern weil Sie es können.
1
@ Mark, wie wäre es, das Leben zu umarmen;) = Reisen, Sprachen, Theater, Poesie, im Freien usw.? Ich programmiere gerne, aber wenn ich es nicht per se mache, habe ich 1000 andere Dinge zu tun.
Job

Antworten:

7

Die Evaluierung ist meines Wissens kein parallelisierbares Problem, aber die Evaluierung verschiedener Ketten ist es. Daher würde ich sie definitiv schreiben, um mehrere Kerne und Multithreading zu verwenden.

Ob Sie funktional oder semi-funktional gehen, ist Geschmackssache. Persönlich würde ich OOP gehen und die Unterstützung für funktionale Programmierung und Parallelisierung verwenden, die zum Beispiel in C # existiert

Wenn ich eine Schachengine schreiben würde, würde ich versuchen, eine zu entwickeln, die wirklich über Schach "nachdenken" kann. Die Verwendung der Board-Bewertung, um alle möglichen Kombinationen brutal zu erzwingen, wurde zu Tode und sehr gut durchgeführt, aber es wurden keine großen Fortschritte bei der Entwicklung einer Denk- / Fuzzy-Schach-Engine erzielt. Das wäre eine Herausforderung! :) :)

Finden Sie einige Spiele mit wirklich kniffligem Positionsspiel und starken Bewegungen (sie sind markiert! Oder !!) und verwenden Sie sie, um Ihren Motor zu trainieren und zu testen.

Homde
quelle
2

Ich denke, es hängt von Ihren Zielen ab, die ich als streng didaktisch betrachte. Wenn Sie versuchen, ein wettbewerbsfähiges Produkt zu schreiben, möchten Sie maximale Effizienz bei den Evaluatoren der niedrigsten Ebene. Hier gibt es viele Möglichkeiten für Parallelität auf Bitebene. Auch viele Möglichkeiten für Hash-Tabellen. Auch Möglichkeiten, Parallelität zu nutzen. Dann möchten Sie auf den höheren Ebenen wahrscheinlich ein System, das gut für die KI ist, was wahrscheinlich eine funktionale Programmiersprache bedeutet. Offensichtlich möchten Sie nicht alle diese Dinge tun, ein oder zwei davon auswählen und sich damit zufrieden geben, dass Ihr Projekt nicht mit den besseren Programmen konkurrieren kann.

Omega Centauri
quelle
2

Ich habe das OOP-Paradigma in meiner Schach-Engine namens The Turk gewählt . Die erste Version meiner Schach-Engine wurde eher prozedural als OOP geschrieben. Dann fiel es mir aufgrund langer Codeblöcke und schlechten Designs so schwer, meine Schach-Engine zu verbessern.

Dies hängt davon ab, was Sie beim Schreiben der Schachengine erreichen möchten. Wenn Sie eine Schachengine erstellen möchten, die zu stark ist, ist dies in OOP-Sprachen aufgrund langsamer, später Bindungen sogar nicht möglich. Wenn Sie nur Programmieren lernen und Spaß haben möchten, indem Sie eine Schachengine schreiben, werden verwaltete Sprachen und OOP Ihr Freund sein. Ich kann Ihnen vorschlagen, C # zu wählen, da es auch möglich ist, eine Schach-Engine prozeduraler damit zu schreiben.

Frisches Blut
quelle
Wie bewertet es ELO-weise? Im Vergleich zu Crafty?
@ Thorbjørn Ravn Andersen - Crafty, eine der überlegenen Open-Source-Schach-Engines in C und von Dr. Robert M. Hyatt, der sein Leben in der Schachprogrammierung verbracht hat. Leider habe ich die Elo-Bewertung nicht getestet, da es vor dem Testen der Elo-Bewertung noch viele Dinge zu tun gibt. Derzeit werden nur die Stückwerte bewertet, sodass die Bewertung ziemlich schwach ist und ich noch nicht alle erforderlichen Algorithmen implementiert habe. Leider habe ich im Moment keine Zeit für dieses Projekt. Ich hoffe, dass es eines Tages möglich sein wird, damit fortzufahren.
Freshblood
Entschuldigung, ich dachte, es könnte tatsächlich spielen. Mein Fehler.
@ Thorbjørn Ravn Andersen - Ich habe dort einige Releases veröffentlicht und das neueste Repository-Änderungsset fertig zum Erstellen. Ich wollte nur sagen, dass es im Moment ziemlich schwach ist.
Freshblood
2

Ich habe ein einfaches Schachprogramm portiert, um die Forth-Sprache zu lernen. Es stellte sich heraus, dass es sehr gut zu diesem sehr wichtigen Problem passt, und ich habe viel gelernt. Der offene Stapel ermöglichte es mir, die Alpha-Beta-Suche auf einzigartige Weise zu implementieren, wodurch ich einen besseren Einblick in den Algorithmus erhielt.

Man würde denken, dass funktionale Programmierung für Schachprogramme großartig wäre, da die Kernalgorithmen (Alpha-Beta-Tiefensuche, Auswertung) rekursiv und funktional streng sind. Ein Schachprogramm lebt und stirbt jedoch von Effizienz und keine der aktuellen funktionalen Sprachen hat dieses Ziel. Die Top-100-Engines auf dem neuesten Stand der Technik verwenden alle zwingende Sprachen (hauptsächlich C / C ++, dann Delphi), um maximale Kontrolle über die Speichernutzung, Multithreading, den globalen Status und die Codegenerierung zu haben. Alle funktionalen Sprachen verwenden die dynamische Speicherzuweisung für Kerndatenstrukturen, was für ein Schachprogramm der Tod ist.

Ich würde immer noch gerne sehen, wie jemand versucht, mit einer funktionalen Sprache in die Top 100 der Schach-Engines einzudringen.

Ian Osgood
quelle