Ich habe mich schon seit einiger Zeit für einen Computer-Schach-KI-Algorithmus (und hatte irgendwann die Möglichkeit, an einem zu arbeiten) wie Minimax interessiert , und als Kernkomponente dieser Algorithmen dient die sogenannte Bewertungsfunktion , um zu bestimmen, was ein ist Gute Board-Konfiguration und was ist eine schlechte .
Mit anderen Worten, wie stellen Sie bei einer Konfiguration Ihres Schachbretts fest, dass dies zu Ihrem Vorteil ist, und mit welchem Maß an Vertrauen?
Beispielsweise:
- Wenn Sie besitzen das Zentrum, das ist recht günstig.
- Wenn Sie mehr Teile als Ihr Gegner haben, ist dies ziemlich günstig.
- Wenn Sie Ihre Königin verloren haben, ist dies eher ungünstig.
- Wenn Sie einen Bauern haben, der kurz vor der Beförderung steht, ist dies günstig.
- ...
Daher möchte ich Sie um Rat fragen, wie Sie eine gute Bewertungsfunktion erstellen können, die auf Expertenwissen über das Schachspiel im Allgemeinen basiert. Und wenn möglich, ein Grad an Günstigkeit (sagen wir zwischen 1 ist sehr ungünstig, bis 100 ist extrem günstig).
Am Ende geht es darum, einen Algorithmus zu erstellen, der bis zu einer bestimmten Tiefe in den Baum der Möglichkeiten schaut und anhand dessen bewertet, welche Konfiguration für den nächsten Zug am günstigsten ist (unter Berücksichtigung mehrerer Züge in der Zukunft) ist günstig für den Spieler und nicht günstig für den Gegner. Aber ohne eine gute Bewertungsfunktion ist der Algorithmus nichts.
quelle
Antworten:
Hier ist ein guter Ausgangspunkt. Der Materialvergleich ist der Schlüssel (und einfach). Dann können Sie ihn so einstellen, dass Positionsaspekte wie offene Ränge / Dateien / Diagonalen, Bauernstruktur usw. berücksichtigt werden.
https://www.chessprogramming.org/Evaluation
quelle
Ich habe das Gefühl, dass ich bei dieser Antwort etwas spät dran bin, aber - ich bin auch dabei, einen Motor zu bauen. Der Quellcode ist in Python (das ist ziemlich einfach zu lesen, auch wenn Sie es nicht wissen) und steht hier zur Verfügung , wenn Sie es lesen möchten. Die Liste der aktuell aktiven 'Heuristiken' (zum Zeitpunkt der Veröffentlichung):
In einem dieser Punkte habe ich die "Phase" des Spiels erwähnt (z. B. Eröffnung, Midgame, Endgame), und wenn Sie dies in Ihre Engine aufnehmen möchten, werden Sie wahrscheinlich auf dasselbe Problem stoßen wie ich: Es gibt kein klare Linie zwischen diesen. Meine Funktion, die entscheidet, in welcher Phase sich das Spiel befindet, verwendet einige Dinge:
Diese Antwort war vielleicht lang, spät und nicht zum Thema gehörend, aber ich hoffe, sie war trotzdem hilfreich.
quelle
Zusammen mit der Antwort von @Eve Freeman würde ich vorschlagen, nachzuschlagen, wie die beste Computer-Engine der Welt, Stockfish, eine bestimmte Position bewertet. Da der Quellcode geöffnet ist, können Sie dies kostenlos tun. Ich denke, die Datei mit der Auswertungsfunktion, die Sie suchen, ist diese .
quelle
Überraschenderweise stellt sich heraus, dass eine Minimax-Engine ziemlich gut funktioniert, wenn die Bewertungsfunktion zufällig ist . Dies ist als Beale-Effekt bekannt und ergibt sich aus dem Prinzip, dass Positionen, die Ihnen mehr Optionen und Ihrem Gegner weniger Optionen bieten, im Allgemeinen günstig sind. Ein vernünftiger Weg, um zufällige Bewertungen konsistent und effizient zu generieren, besteht darin, einen Zobrist-Hash für die Position zu generieren (unter Verwendung von Koeffizienten, die zu Beginn des Spiels zufällig ausgewählt wurden) und die zufällige Bewertung direkt aus dem Hash abzuleiten.
Am anderen Ende der Skala führen AlphaZero und Leela eine äußerst differenzierte Bewertung jeder gesuchten Position unter Verwendung eines großen neuronalen Netzwerks durch . Es ist unpraktisch, menschlich zu beschreiben, welche Funktionen dieses Netzwerk effektiv implementiert, aber es ist zweifellos effektiver als die Bewertungsfunktion von Stockfish. Das AlphaZero-Forschungspapier zeigt, dass dieser Ansatz am besten mit der Monte-Carlo-Baumsuche und nicht mit Minimax funktioniert.
Wenn Sie andererseits eine Analyse-Engine entwickeln möchten, die menschlichen Spielern oder Kommentatoren hilft, die Nuancen einer Position zu verstehen, kann es sich lohnen, eine herkömmliche Bewertungsfunktion unter Verwendung etablierter Materialwerte und Positionstheorie zu implementieren . Ein gutes Beispiel ist Ed Schröders Inside Rebel , der die wichtigsten Konstruktionsmerkmale einer angesehenen Engine dokumentiert, die in mehreren Schachcomputern von Mephisto verwendet wird. Möglicherweise möchten Sie ein gewisses Maß an maschinellem Lernen verwenden, um die relative Bedeutung jedes Elements Ihrer Bewertungsfunktion zu bestimmen, und diese Elemente auch einzeln für die Darstellung in einer GUI aufteilen.
quelle
Ich denke, Schachprogrammierer verlassen sich beim Entwerfen ihrer Bewertungsfunktionen nicht auf das Wissen starker Schachspieler, sondern probieren verschiedene Elemente aus und testen sie dann in Spielen gegen andere Engines und entscheiden, was sie behalten möchten. Larry Kaufman spricht einiges über seine Ansichten über das Verständnis eines Menschen, aber es klingt so, als ob sowohl Rajlich als auch Dailey sehr ergebnisorientiert waren und Kaufmans Ideen nicht im großen Stil übernommen haben.
Ein Artikel, den ich interessant fand, war Zach Wegner, der die Bewertungsfunktionen von Rybka und Fruit verglich. Einer der Bereiche, in denen Rybka möglicherweise einen Fortschritt erzielt hat, war die Einbeziehung von Tabellen für Materialungleichgewichte, die auf bestimmten Kombinationen von Teilen basieren. Kaufman hat auch dazu einen Artikel geschrieben.
http://www.top-5000.nl/ZW_Rybka_Fruit.pdf http://danheisman.home.comcast.net/~danheisman/Articles/evaluation_of_material_imbalance.htm
quelle
Dieser Link ist meiner Meinung nach der beste Ausgangspunkt. Ich benutze dies als Ausgangspunkt für mein eigenes Schachprogramm und finde es einfach zu verstehen und auch nützlich.
https://chessprogramming.wikispaces.com/Simplified+evaluation+function
quelle
Kurz gesagt, der Standardansatz zum Einstellen der Parameter einer Schachmaschine lautet:
Wiederholen Sie dann die Schritte 3 und 4, bis Sie Ihr Leistungsziel erreicht haben.
Der übliche Ansatz besteht darin, ein Labor einzurichten, in dem Motoren bei Motorturnieren gegeneinander antreten. Es werden mehrere Spiele verwendet, bei denen die Engine beide Farben spielt. Die wichtigsten Turniere von Interesse umfassen das Ausführen einer Engine mit Parameterwertsatz A gegen dieselbe Engine mit Parameterwertsatz B.
Wie Sie wahrscheinlich erraten können, hängen die Ergebnisse dieses Ansatzes stark ab von:
Dieser Ansatz nimmt auch viel Zeit in Anspruch .
Ein neuerer (und innovativer) Ansatz wurde 2010 von Forschern entwickelt, die Techniken des genetischen Algorithmus verwendeten, um a) die Parameter zu spezifizieren und b) die Parameterwerte abzustimmen. Die Ermittler ließen zuerst eine Engine mit einem nominalen Startsatz von Parameterwerten gegen einen Satz von Großmeisterspielen laufen, um zu sehen, ob sie effektiv den "besten Zug" auswählen konnte. Der "beste Zug" wurde als der Zug definiert, den der Großmeister gemacht hat *. Wo immer dies fehlschlug, wurde aufgezeichnet. Dann wurde ein anderer Parameterwertsatz versucht und die relative Leistung gegenüber dem vorherigen Lauf bestimmt.
Dann wurde ein programmatischer Ansatz zur Kombination der Parameterwerte unter Verwendung des Genetischen Algorithmus-Überlebensprinzips der "Stärksten" versucht. Hier bedeutet "am besten" diejenige, die eine Ausgabe erzeugt, die dem Ideal am ehesten entspricht. (Es ist auch ein Wortspiel mit der statistischen Technik der Regression der "kleinsten Quadrate", einer Technik, mit der die Qualität der Approximation beurteilt wird.)
Erst nachdem Motorparameter gefunden wurden, die einen GM einigermaßen gut imitieren können, beginnt die eigentliche Phase des Motorturniers. In dieser Phase werden wieder verschiedene Parameterwertsätze gegeneinander ausgespielt, diesmal direkt . Techniken zur Verbesserung des genetischen Algorithmus werden angewendet, um sukzessive bessere Generationen des Motors zu erzeugen.
In diesem Forschungsprojekt wurden 36 Parameter verwendet, einschließlich aller Materialwerte der Stücke und vieler gängigerer strategischer Bewertungskriterien wie Rückwärtsbauern, schwache Quadrate, Läuferpaare usw. Die Forscher fügten jedoch einige neue Parameter hinzu, wie "Königsdruck", "Mobilitäts" -Werte für jede Art von Stück, Turm auf einer Datei neben dem König, Turm auf einer halboffenen Datei, Turm, der den König auf dem a angreift - / b- / g- / h-Datei, Trennung zwischen einem übergebenen Bauern und dem verteidigenden König und mehr.
Leider erläutern die Forscher nicht, wie sie auf diese Parametersuite gekommen sind und welche alternativen Parameter sie möglicherweise getestet und abgelehnt haben. Es wäre vernünftig anzunehmen, dass sie mit einem viel größeren Satz begannen und (durch Versuch und Irrtum) bestimmten, welche den größten Einfluss auf die Leistung hatten und welche entweder unbedeutend oder abgeleitet waren und daher fallengelassen werden konnten.
Wenn dies nützlich erscheint, finden Sie die Forschung hier .
* Eine Einschränkung bezüglich einer Phase des von den Forschern verwendeten Ansatzes ist angebracht. In seiner Einführung in das Verständnis von Schachzug für Zug wählte John Nunn "... hart umkämpfte Spiele zwischen starken Großmeistern ...", um seine Themen zu veranschaulichen. Dann fügt er hinzu:
Der Punkt, den Dr. Nunn anspricht, deutet darauf hin, dass der anfängliche Ansatz der Forscher, die Motorparameter so einzustellen, dass sie Großmeisterbewegungen imitieren müssen, möglicherweise fehlerhaft ist, weil das menschliche Spiel fehlerhaft ist . In der Tat ist es bekannt, dass Motoren bereits besser spielen als Menschen .
Daher wäre ein besserer Ansatz zum Einstellen der Anfangsparameter möglicherweise, einen neuen Motor mit einem überlegenen vorhandenen Motor abzugleichen .
quelle
Es gibt eine schöne Website unter:
Es gibt Ihnen eine Einführung in die Funktionsweise der Stockfish-Funktionen.
quelle