Bewertungsfunktion - Evaluation function

Eine Bewertungsfunktion , auch als heuristische Bewertungsfunktion oder statische Bewertungsfunktion bekannt , ist eine Funktion, die von spielenden Computerprogrammen verwendet wird, um den Wert oder die Güte einer Position (normalerweise an einem Blatt oder Endknoten) in einem Spielbaum zu schätzen. Ein Baum solcher Auswertungen ist normalerweise Teil eines Minimax oder eines verwandten Suchparadigmas, das einen bestimmten Knoten und seine Auswertung als Ergebnis der abwechselnden Auswahl des günstigsten Zugs für die Seite in Bewegung auf jeder Lage des Spielbaums zurückgibt. Der Wert ist ein quantisierter Skalar, oft in N- ten des Wertes einer Spielfigur wie einem Stein im Spiel oder einem Bauern im Schach. n kann Zehntel, Hundertstel oder ein anderer geeigneter Bruchteil sein.

Es wird angenommen, dass der Wert die relative Gewinnwahrscheinlichkeit darstellt, wenn der Spielbaum von diesem Knoten bis zum Ende des Spiels erweitert wurde. Die Funktion betrachtet nur die aktuelle Position (dh auf welchen Feldern sich die Teile befinden und in welcher Beziehung sie zueinander stehen) und berücksichtigt nicht den Verlauf der Position oder untersucht mögliche Bewegungen des Knotens vorwärts (daher statisch). Dies impliziert, dass für dynamische Positionen, in denen taktische Bedrohungen bestehen, die Bewertungsfunktion keine genaue Bewertung der Position ist. Diese Positionen werden als nicht ruhend bezeichnet . Sie erfordern mindestens eine begrenzte Art von Sucherweiterung, die als Ruhesuche bezeichnet wird , um Bedrohungen vor der Bewertung zu beheben. Einige von Bewertungsfunktionen zurückgegebene Werte sind eher absolut als heuristisch, wenn am Knoten ein Gewinn, Verlust oder Unentschieden auftritt.

Es gibt weder analytische oder theoretische Modelle für Bewertungsfunktionen für ungelöste Spiele, noch sind solche Funktionen vollständig ad-hoc. Die Zusammensetzung der Bewertungsfunktionen wird empirisch bestimmt, indem eine Kandidatenfunktion in einen Automaten eingefügt und dessen nachfolgende Leistung bewertet wird. Für einige Spiele wie Schach, Shogi und die allgemeine Zusammensetzung der Bewertungsfunktionen für sie gibt es inzwischen zahlreiche Belege.

Der allgemeine Ansatz zum Aufbau von Bewertungsfunktionen besteht in einer linearen Kombination verschiedener gewichteter Terme, die bestimmt werden, um den Wert einer Position zu beeinflussen. Jeder Begriff kann als aus Faktoren erster Ordnung (diejenigen, die nur vom Raum und einem Teil davon abhängen), Faktoren zweiter Ordnung (der Raum im Verhältnis zu anderen Räumen) und Faktoren n-ter Ordnung (Abhängigkeiten von der Geschichte von) zusammengesetzt werden die Position).

In der Bewertungsfunktion besteht eine komplexe Beziehung zwischen Suche und Wissen. Eine tiefere Suche bevorzugt weniger kurzfristige taktische Faktoren und subtilere Positionsmotive mit langem Horizont in der Bewertung. Es gibt auch einen Kompromiss zwischen der Wirksamkeit von codiertem Wissen und der Komplexität der Berechnung: Die Berechnung von detailliertem Wissen kann so lange dauern, dass die Leistung abnimmt, sodass Annäherungen an genaues Wissen häufig besser sind. Da die Bewertungsfunktion von der nominalen Suchtiefe sowie den bei der Suche verwendeten Erweiterungen und Reduzierungen abhängt, gibt es keine generische oder eigenständige Formulierung für eine Bewertungsfunktion. Eine Bewertungsfunktion, die in einer Anwendung gut funktioniert, muss normalerweise grundlegend angepasst werden, um in einer anderen Anwendung effektiv zu funktionieren.

Computergestützte Spiele mit Bewertungsfunktionen umfassen Schach , Go , Shogi (japanisches Schach), Othello , Hex und Dame . Einige Spiele wie Tic-Tac-Toe sind stark gelöst und erfordern keine Suche oder Bewertung, da ein diskreter Lösungsbaum verfügbar ist.

Im Schach

Bewertungsfunktionen im Schach bestehen aus einem Materialbilanzbegriff, der die Bewertung dominiert, sowie einer Reihe von Positionsbegriffen, die normalerweise nicht mehr als den Wert eines Bauern betragen. In einigen Positionen können die Positionsbegriffe jedoch viel größer werden, z. B. wenn ein Schachmatt unmittelbar bevorsteht . Eine Bewertungsfunktion codiert implizit auch den Wert des Bewegungsrechts, der von einem kleinen Bruchteil eines Bauern bis zum Gewinn oder Verlust variieren kann. Im Endspiel ist es möglich, Positionen zu konstruieren, bei denen jeder, der sich bewegt, gewinnt, obwohl die Position ansonsten im Gleichgewicht ist. Es ist auch möglich, Positionen zu konstruieren, an denen jeder, der sich bewegen muss, verliert ( Zugzwang ).

Eine Bewertungsfunktion für Schach könnte die Form annehmen

c ₁ * Material + c ₂ * Mobilität + c ₃ * Königssicherheit + c ₄ * Mittelkontrolle + c ₅ * Bauernstruktur + c ₆ * Königstropismus + ...

Jeder der Begriffe ist ein Gewicht multipliziert mit einem Differenzfaktor: dem Wert des Materials von Weiß oder der Positionsbewertung minus dem von Schwarz. Die Materialbewertung wird erhalten, indem jedem Stück ein Wert in Bauerneinheiten zugewiesen wird. Die herkömmlichen Werte sind: Königin = 9, Turm = 5; Ritter oder Bischof = 3; Bauer = 1; Dem König wird ein beliebig großer Wert zugewiesen, der normalerweise größer ist als der Gesamtwert aller anderen Stücke. Nicht nur der absolute Wert des Materials, sondern auch das Verhältnis zwischen weißem und schwarzem Material spielt eine Rolle: Das Opfer eines Bauern in der Öffnung kann einen Positionsvorteil bringen (das Materialverhältnis wird kaum beeinflusst), sondern auch das Plus eines Bauern in einem König und Das Spiel am Bauernende reicht normalerweise aus, um zu gewinnen (das Materialverhältnis ist groß). Dieses Verhältnis wird normalerweise als Umtauschbonus gemäß der Faustregel implementiert: "Handelsstücke, aber keine Bauern, wenn sie vorne sind, und umgekehrt, wenn sie hinten sind." Die Mobilitätsbewertung ist die Anzahl der legalen Züge, die einem Spieler zur Verfügung stehen, oder alternativ die Summe der Anzahl der Felder, die von jedem Teil angegriffen oder verteidigt werden, einschließlich der Felder, die von befreundeten oder gegnerischen Teilen belegt werden. Eine effektive Mobilität oder die Anzahl der "sicheren" Räume, in die sich ein Teil bewegen kann, kann ebenfalls berücksichtigt werden. Die effektive Mobilität von Königinnen ist oft sehr gering, obwohl die Anzahl ihrer legalen Umzüge recht hoch sein kann. Die Königssicherheitsbewertung besteht aus einer Reihe von Boni und Strafen, die für den Standort des Königs und die Konfiguration von Bauern und Figuren neben oder vor dem König sowie für gegnerische Figuren, die sich auf Feldern um den König befinden, bewertet werden. Die Steuerung des Zentrums wird daraus abgeleitet, wie viele Bauern und Figuren die vier zentralen Felder und manchmal die 12 Felder des erweiterten Zentrums belegen oder tragen. Die Bauernstruktur besteht aus einer Reihe von Strafen und Boni für verschiedene Stärken und Schwächen der Bauernstruktur, z. B. Strafen für doppelte und isolierte Bauern. Königstropismus ist ein Bonus für die Nähe (oder Strafe für die Entfernung) bestimmter Teile, insbesondere Königinnen und Ritter, zum gegnerischen König.

Die Gewichte c1 usw. sind nicht unbedingt konstant - es handelt sich um Anwendungskoeffizienten, die je nach Spielphase (Eröffnung, mittleres Spiel, Endspiel), Spielsteinen (z. B. Anwesenheit oder Abwesenheit von Königinnen) und anderen Merkmalen des Spiels variieren können Position oder Strategie oder Pläne auf hoher Ebene (z. B. Teile, die auf Feldern um den gegnerischen König stehen, höher gewichten, wenn es sich bei dem Plan um einen Königsangriff handelt).

Der Fokus und damit die relevanten Begriffe und Gewichte der Bewertungsfunktion unterscheiden sich je nach Spielphase. In der Eröffnung sind die dominierenden Überlegungen die Entwicklung der Nebenstücke, die Sicherheit von Burgen und Königen sowie die Kontrolle über das Zentrum. Strafen werden normalerweise für unbebaute Teile und verzögerte Rochade verhängt. Bei Endspielen sind entweder die Bauernförderung oder die Paarung mit den Figuren die dominierenden Überlegungen. In Paarungssituationen sind die relevanten Faktoren die Entfernung des Zielkönigs vom Rand oder der Ecke des Bretts sowie die Nähe des Königs und der Paarungsstücke zum gegnerischen König. Für Königs- und Bauernendspiele sind die Nähe der Könige zu den Bauern, die Weiterentwicklung der Bauern und die Kontrolle der Königinnenfelder die relevanten Faktoren.

Die Gleichung ist ein konzeptionelles Modell. In einer bestimmten Implementierung kann jeder zusammengesetzte Pseudo-Term durch eine Handvoll bis möglicherweise Hunderte von einzelnen Termen dargestellt werden, von denen jeder sein eigenes Gewicht oder seinen eigenen berechneten Wert hat. Zum Beispiel kann die Bauernstruktur Begriffe für isolierte, doppelte, rückwärts, fortgeschritten, übergeben, geschützt, verbunden, verbunden, Löcher, halboffene und offene Dateien, Bauernmehrheiten, Phalanxen und viele andere Formationen enthalten. Andere spezielle Faktoren, die häufig berücksichtigt werden, sind: Entwicklung der Nebenstücke, Türme auf offenen Akten oder des siebten Ranges, doppelte Türme, Außenpostenritter (Ritter an zentralen Orten, die von einem Bauern geschützt werden und nicht von einem gegnerischen Bauern angegriffen werden), Besitz des Bischofspaares, Bischöfe auf den langen Diagonalen, Teile, die Räume um den gegnerischen König besetzen oder tragen, und Beweglichkeit der Könige (Könige sollten nicht „beengt“ sein und daher einem Partner in Bewegung unterliegen). Einige Begriffe, wie die Sicherheit des Königs in einem Endspiel mit wenigen Teilen, können und sollten je nach Kontext ignoriert werden.

Die Begriffe, aus denen einige Faktoren bestehen, wie z. B. die Sicherheit des Königs, werden nicht linear kombiniert. Eine Schwäche der Sicherheit des Königs, wie eine offene Datei neben dem König, kann beispielsweise mit 1/4 Bauer bestraft werden, zwei Schwächen müssen jedoch möglicherweise bestraft werden ein oder sogar zwei volle Bauern und drei Schwächen pro Stück, ein Turm oder sogar mehr, weil Schachmatt eine wahrscheinliche Möglichkeit wird. Faktoren, die mit dem Vorrücken und der Beförderung von Bauern zusammenhängen, werden ebenfalls nicht linear kombiniert.

Die typischen Bauernmultiplikatorwerte, die den Figuren zugewiesen werden, sind ebenfalls nicht konstant, sondern hängen vom Kontext ab: Unentwickelte Figuren sind weitaus weniger wert als Stücke mit eingeschränkter Mobilität aus irgendeinem Grund: Bischöfe, die von ihren eigenen Bauern eingesperrt werden ("der böse Bischof") ;; Ritter verlieren an Wert, wenn die Position von Stücken befreit wird und Bischöfe und Türme an Wert gewinnen; Königinnen sind wesentlich mehr wert, wenn der gegnerische König nicht vor Schecks geschützt ist.

Bewertungsfunktionen enthalten normalerweise Dutzende bis Hunderte von einzelnen Begriffen, und die Bewertung einer Position reicht normalerweise von plus oder minus einem kleinen Bruchteil eines Bauern. Größere Bewertungen deuten auf ein materielles Ungleichgewicht hin oder darauf, dass ein Materialgewinn normalerweise unmittelbar bevorsteht. Sehr umfangreiche Bewertungen können darauf hinweisen, dass Schachmatt unmittelbar bevorsteht.

In der Praxis werden effektive Bewertungsfunktionen nicht durch Erweitern der Liste der bewerteten Parameter, sondern durch sorgfältiges Einstellen der Gewichte relativ zueinander eines bescheidenen Satzes von Parametern wie den oben beschriebenen erzeugt. Zu diesem Zweck werden beispielhafte Positionen aus Meisterspielen verwendet und die Wirksamkeit der Bewertungsfunktion anhand des Prozentsatzes der ausgewählten Züge gemessen, die mit den Entscheidungen der Meister übereinstimmen.

Stück-quadratische Tische

Eine wichtige Technik bei der Bewertung seit mindestens den frühen neunziger Jahren ist die Verwendung von Stückquadrattabellen (auch Stückwerttabellen genannt) zur Bewertung. Jede Tabelle besteht aus 64 Werten, die den Quadraten des Schachbretts entsprechen. Für jede Art von Stück gibt es einen separaten Tisch: König, Königin, Ritter, Bischof, Turm, Bauer. Es gibt einen separaten (umgedrehten) Satz von Tischen für die gegenüberliegenden Teile. Die Werte in den Tabellen sind Boni / Strafen für die Position jedes Stücks auf jedem Feld. Die Werte codieren eine Zusammenstellung vieler subtiler Faktoren, die analytisch schwer zu quantifizieren sind. Grundtische können aus Prinzipien der Entwicklung, der Steuerung des Zentrums, der Sicherheit des Königs usw. erstellt werden. In Programmen auf Master-Ebene und darüber hinaus werden die Tische aus einer Zusammensetzung von Positionen erstellt, die die Teile in Master-Spielen einnehmen, angepasst an die Anwendung. Zum Beispiel werden Ritter in Meisterspielen selten am linken und rechten Rand des Bretts gefunden, so dass man den Feldern des Ritter-Quadrat-Tisches einen Strafwert zuweisen kann, der proportional dazu ist, wie selten ein Ritter in Meisterspielen dort gefunden wird. Es gibt oft zwei Sätze von Tischen: einen für die Eröffnung und einen für das Endspiel; Positionen des Mittelspiels werden zwischen den beiden interpoliert. Autoren von Schachprogrammen neigen dazu, die Zusammensetzung ihrer quadratischen Tische sowie die Methoden, mit denen sie erstellt wurden, geheim zu halten, da viel Zeit, Mühe, Test- und Spielerfahrung in die Erstellung und sorgfältige Abstimmung investiert werden bietet einen Wettbewerbsvorteil.

Auswertung bei der Monte-Carlo-Baumsuche

Schachmaschinen wie Leela Chess Zero haben ein wesentlich anderes Such- und Bewertungsparadigma als das herkömmliche Alphabet / Minimax-Schema mit Blattknotenbewertung. Bei der Monte-Carlo-Baumsuche wird der Suchraum aller Variationen eines Knotens durch Ausrollen oder Spielen des Spiels bis zum Ende durch abwechselndes Auswählen eines zufälligen Zugs für jede Seite abgetastet. Das Ergebnis, gewinnen, verlieren oder unentschieden, wird auf dem Startknoten gesichert. Der ausgewählte Zug ist derjenige, der zu einer Position mit der größten Anzahl von Gewinnen oder der höchsten durchschnittlichen Punktzahl führt, obwohl dem Zug keine bestimmte Spiellinie zugeordnet ist. Eine analoge Situation ist der Prozentsatz der Gewinne / Unentschieden / Verluste, die für verschiedene Eröffnungen in Masterspielen angesammelt wurden. Wenn man eine Eröffnung wählt, wählt man meistens diejenigen mit dem größten Prozentsatz an Gewinnen oder dem größten Prozentsatz an Gewinnen + Unentschieden. Und ähnlich für jede Variation innerhalb der Eröffnung, wenn Statistiken verfügbar sind. Die Schwäche eines solchen Schemas besteht darin, dass die stärkste (n) Spiellinie (n) für jede Seite möglicherweise nicht Teil dieser Öffnung ist - es kann sich um enge Möglichkeiten in einer Öffnung handeln, die ansonsten schwach ist.

Die "Bewertung" in Monte-Carlo-Implementierungen ist also eher eine Gewinnwahrscheinlichkeit als eine numerische Bewertung einer Position.

In Go

Die Bewertungsfunktionen in Go berücksichtigen sowohl das kontrollierte Territorium als auch den Einfluss von Steinen, die Anzahl der Gefangenen sowie das Leben und Sterben von Gruppen im Vorstand.

Siehe auch

Verweise

Shannon, Claude, 1950, "Programmieren eines Computers zum Schachspielen", Philosophical Magazine, Ser.7, Vol. 41, Nr. 314.
Slate, D und Atkin, L., 1983, "Chess 4.5, das Schachprogramm der Northwestern University" in Chess Skill in Man and Machine 2nd Ed., S. 93–100. Springer-Verlag, New York, NY.
Ebeling, Carl, 1987, All the Right Moves: Eine VLSI-Architektur für Schach (ACM Distinguished Dissertation), S. 56–86. MIT Press, Cambridge, MA
Stockfish Bewertungsleitfaden, [1]

Externe Links

Languages

In other projects