Geekly articles weekly

Wie spielt ein Computer Schach?


Hikaru Nakamura, der kürzlich einen Computer herausgefordert hat.

Ein Computer hat lange einen Mann im Schach geschlagen, jetzt können die stärksten Schachspieler nicht einmal einen alten Laptop schlagen. Jetzt werden Schach-Engines verwendet, um Spiele zu analysieren, nach neuen Optionen zu suchen und per Korrespondenz zu spielen.

Wenn Sie daran interessiert sind, wie die Schachengines angeordnet sind, sind Sie bei cat willkommen.

Einführung


Sobald ich mir sicher war, dass Schachprogramme (sie sind auch Motoren, aber dazu später mehr), denken Sie einfach an die große Anzahl der gespielten Spiele und finden Sie ihre aktuelle Position in ihnen und machen Sie den richtigen Zug. Meiner Meinung nach habe ich darüber in einem Buch gelesen.

Dies ist zweifellos eine sehr naive Meinung. Eine neue Position im Schach kann durch den zehnten Zug erreicht werden. Obwohl es im Schach weniger Positionen als im Los gibt , besteht der Baum der Züge nach 3 Zügen (ein Zug ist ein Zug von Weiß und Schwarz, ein halber Zug ist ein Zug von nur einer Seite) aus fast 120 Millionen Knoten. Darüber hinaus wird die Größe des Baumes nach 14 halben Zügen von der Ausgangsposition von Enthusiasten seit mehr als einem Jahr berücksichtigt , nachdem sie bisher um etwa ein Drittel fortgeschritten sind.

Ich dachte auch, dass Schachprogramme trotz der langjährigenSieg in einem Spiel des Weltmeisters, alle sind noch in Reichweite der best Leute. Dies ist auch nicht wahr.

In einem kürzlich durchgeführten Mensch-Maschine- Minispiel spielte Hikaru Nakamura , einer der stärksten Schachspieler der Welt, mit Komodo , einem der (zwei) stärksten Schachprogramme der Welt. Das Programm wurde auf einem 24-Kern-Xeon gestartet. Da die Leute nicht mehr gleichberechtigt mit einem Computer konkurrieren können, hat der Großmeister in jedem der vier Spiele einen Vorsprung:
  • Im ersten Spiel - ein Bauer und ein Zug: Der Computer spielte schwarz und ohne einen f7-Bauern
  • Im zweiten - nur ein Bauer: Der Computer spielte weiß ohne einen Bauern f2
  • In der dritten Qualität (der Unterschied zwischen einem Turm und einem leichten Stück wird auf ungefähr 2 Bauern geschätzt): ein weißer Computer ohne einen Turm, ein Mann ohne einen Ritter und einen Turm an seiner Stelle.
  • In den vierten - vier Zügen: Eine Person spielt mit Weiß und macht anstelle des ersten Zuges vier Züge, ohne die Mitte des Bretts zu überqueren.

Es gab gewisse Streitigkeiten bezüglich des Handicaps - zum Beispiel schwächt das Fehlen des f-Bauern den König etwas, aber nach dem Schlössern gibt es eine offene Linie zum Turm. Das Fehlen eines zentralen Bauern bietet wahrscheinlich einen größeren Vorteil. 4 Züge bieten einen guten Positionsvorteil, aber wenn Sie ein geschlossenes Debüt wie die altindische Abwehr spielen, ist dieser Vorteil nicht so schwer aufzuheben.

Zusätzlich wurden Spiele mit einer Kontrolle von 45 '+ 15' gespielt, d. H. 45 Minuten pro Spiel und 15 Sekunden Zugabejede Bewegung. Normalerweise bieten kürzere Steuerelemente dem Computer einen zusätzlichen Vorteil, während längere die Chancen einer Person geringfügig erhöhen. Selbst in Sekundenbruchteilen kann der Computer offen verlorene Züge fegen, während aufgrund des exponentiellen Wachstums des Variantenbaums jede nachfolgende Verbesserung der Analyse länger dauert.

Trotzdem gab es ein Handicap und die Person verlor im Match 2.5-1.5, nachdem sie die ersten 3 Spiele unentschieden gespielt und das vierte verloren hatte. Zur gleichen Zeit, ein schwacher GM zuversichtlich genug , um zu gewinnenmit einem Handicap von 2 Bauern. Folglich liegt der Vorteil der besten Programme gegenüber den besten Leuten im Moment irgendwo zwischen 1 und 2 Bauern des Handicaps. Natürlich ist diese Einschätzung sehr grob, aber für eine genaue Einschätzung ist es notwendig, mehrere tausend Spiele zwischen Personen und Programmen zu spielen, und kaum jemand wird dies tun. Bitte beachten Sie, dass die ELO-Bewertung, die häufig für Programme angegeben wird, nichts mit der Bewertung von Personen zu tun hat.

Was ist eine Schachmaschine?


Damit eine Person mit einem Computer Schach spielen kann und zusätzlich nach dem besten Zug sucht, benötigen Sie eine grafische Benutzeroberfläche. Glücklicherweise wurde eine universelle Schnittstelle für die Kommunikation zwischen der GUI und dem Schachprogramm selbst (Engine) erfunden (sogar zwei, Winboard und UCI , aber die meisten Engines verwenden UCI). So können sich Programmierer auf den Algorithmus des Schachspiels konzentrieren, ohne an die Schnittstelle zu denken. Die Kehrseite der Medaille ist, dass das Erstellen einer GUI viel langweiliger ist als das Schreiben einer Engine. Dann verlieren kostenlose GUIs spürbar an bezahlten. Im Gegensatz zu Motoren, bei denen der freie Stockfish mit dem bezahlten Komodo souverän um die erste Zeile der Wertung kämpft.

Wie spielen sie noch?


Wie funktioniert eine moderne Schachmaschine?

Vorstandspräsentation


Die Basis jeder Engine ist die Darstellung eines Schachbretts. Zunächst ist es notwendig, dem Computer alle Schachregeln zu „erklären“ und ihm die Möglichkeit zu geben, die Schachposition beizubehalten. Ohne dies ist es unmöglich, die Position zu bewerten und Bewegungen auszuführen.

Es gibt zwei Möglichkeiten, eine Darstellung einer Tafel zu speichern - nach Formen oder nach Zellen . Im ersten Fall speichern wir für jedes Stück seinen Platz auf der Tafel, im zweiten - im Gegenteil, für jede Zelle speichern wir, was dort ist. Jede Methode hat ihre Vor- und Nachteile, aber im Moment verwenden alle Top-Engines die gleiche Darstellung der Platine - Bitboards.

Bitboards


Glücklicherweise befinden sich 64 Zellen auf dem Schachbrett. Wenn wir also ein Bit für jede Zelle verwenden, können wir die gesamte Karte in einer 64-Bit-Ganzzahl speichern.
In einer Variablen speichern wir alle weißen Teile, in einer anderen - alle schwarzen und in 6 weiteren - jede Art von Figuren separat (eine weitere Option - 12 Bitboards für jede Farbe und jede Art von Figuren separat).

Was ist der Vorteil dieser Option?
Der erste ist die Erinnerung. Wie wir später erfahren, wird während der Analyse die Darstellung der Karte viele Male kopiert, und dementsprechend frisst sich der RAM weg. Bitboards sind eine der kompaktesten Schachbrettdarstellungen.
Zweitens Geschwindigkeit. Viele Berechnungen, zum Beispiel die Berechnung möglicher Bewegungen, laufen auf mehrere Bitoperationen hinaus. Aus diesem Grund beschleunigt beispielsweise die Verwendung des POPCNT-Befehls moderne Motoren um ~ 15%. Darüber hinaus wurden während der Existenz von Bitboards viele Algorithmen und Optimierungen erfunden, wie zum Beispiel „magische“ Bitboards .

Suche


Minimax


Das Herzstück der meisten Schachmaschinen ist der Minimax-Suchalgorithmus oder dessen Modifikation von Nicht-Hamax. Kurz gesagt, wir gehen den Baum hinunter, bewerten die Blätter und gehen dann jedes Mal nach oben, indem wir den optimalen Zug für den aktuellen Spieler auswählen, die Punktzahl für einen (schwarz) minimieren und für den zweiten (weiß) maximieren. Daher der Name. Sobald wir in der Wurzel sind, erhalten wir eine Abfolge von Zügen, die für beide Spieler optimal ist. Der Unterschied zwischen Minimax und Nicht-Hamax besteht darin, dass wir im ersten Fall abwechselnd die Züge mit den maximalen und minimalen Bewertungen auswählen und im zweiten Fall stattdessen das Vorzeichen für alle Bewertungen ändern und immer das Maximum auswählen (wir haben verstanden, woher sie stammen). Weitere Details hier und hier .

Alpha Beta


Die erste Optimierung ist Alpha Beta . Die Idee von Alpha-Beta ist einfach - wenn ich bereits einen guten Zug habe, können Sie Züge abschneiden, die offensichtlich schlechter sind. Betrachten Sie das Beispiel im gruseligen Bild links. Angenommen, Spieler A hat zwei mögliche Züge - a3 und b3. Nach der Analyse des Verlaufs von a3 erhielt das Programm eine Punktzahl von +1,75. Das Programm begann mit der Auswertung von Zug b3 und stellte fest, dass Spieler B zwei Züge hat - a6 und a5. Bewertung von a6 +0.5. Da Spieler B einen Zug mit einer Mindestpunktzahl wählt, wählt er keinen Zug mit einer Punktzahl von mehr als 0,5, was bedeutet, dass die Schätzung von Zug b3 weniger als 0,5 beträgt und es keinen Sinn macht, dies zu berücksichtigen. Somit wird der verbleibende Teilbaum von b3 abgeschnitten.

Zum Ausschneiden speichern wir die oberen und unteren Grenzen - Alpha und Beta. Wenn während der Analyse ein Zug eine höhere Punktzahl als Beta erhält, wird der aktuelle Knoten abgeschnitten. Wenn die Punktzahl höher als Alpha ist, wird Alpha aktualisiert.

Knoten in Alpha Beta sind in 3 Kategorien unterteilt:
  1. PV-Knoten - Knoten, deren Auswertung in das Fenster fiel (zwischen Alpha und Beta). Die Wurzel und der Knoten ganz links sind immer Knoten dieses Typs.
  2. Cut-Nodes (oder Fail-High-Knoten ) - Knoten, bei denen ein Beta-Cut-Off aufgetreten ist.
  3. All-Nodes (oder Fail-Low-Nodes ) - Knoten, bei denen laut Bewertung keine Bewegung das Alpha überschritt.


Sortierbewegungen


Bei Verwendung von Alpha Beta wird die Reihenfolge der Bewegungen wichtig. Wenn wir den besten Zug zuerst setzen können, werden die verbleibenden Züge aufgrund von Beta-Cutoffs viel schneller analysiert.

Zusätzlich zur Verwendung des Hash und des besten Zugs aus der vorherigen Iteration gibt es verschiedene Techniken zum Sortieren von Zügen.

Für Erfassungen kann beispielsweise eine einfache heuristische MVV-LVA (Most Valuable Victim - Least Valuable Aggressor) verwendet werden . Wir sortieren alle Erfassungen in absteigender Reihenfolge nach dem Wert des „Opfers“, während wir im Inneren erneut in aufsteigender Reihenfolge nach dem Wert des „Angreifers“ sortieren. Offensichtlich ist es normalerweise rentabler, die Königin mit einem Bauern abzuholen, als umgekehrt.

Für "stille" Bewegungen wird die Methode der "Killer" -Züge verwendet - Bewegungen, die einen Beta-Cutoff verursacht haben. Diese Bewegungen werden normalerweise unmittelbar nach Bewegungen aus dem Hash und den Erfassungen überprüft.

Hash-Tabellen oder Permutationstabellen


Trotz der enormen Größe des Baums sind viele Knoten darin identisch. Um dieselbe Position nicht zweimal zu analysieren, speichert der Computer die Ergebnisse der Analyse in einer Tabelle und prüft jedes Mal, ob bereits eine fertige Analyse dieser Position vorliegt. In der Regel speichert eine solche Tabelle den tatsächlichen Hash der Position, der Bewertung, des besten Zugs und des Bewertungsalters. Das Alter ist erforderlich, um alte Positionen beim Ausfüllen der Tabelle zu ersetzen.

Iterative Suche


Wie Sie wissen, benötigt minimax eine Bewertungsfunktion, wenn wir den gesamten Baum nicht vollständig analysieren können. Nachdem wir eine bestimmte Tiefe erreicht haben, stoppen wir die Suche, bewerten die Position und beginnen, auf den Baum zu klettern. Ein solches Verfahren erfordert jedoch eine vorbestimmte Tiefe und liefert keine qualitativ hochwertigen Zwischenergebnisse.

Die iterative Suche löst diese Probleme. Zuerst analysieren wir bis zu einer Tiefe von 1, dann bis zu einer Tiefe von 2 usw. Daher gehen wir jedes Mal etwas tiefer als beim letzten Mal, bis die Analyse gestoppt wird. Um die Größe des Suchbaums zu verringern, werden die Ergebnisse der letzten Iteration normalerweise verwendet, um absichtlich schlechte Bewegungen auf der aktuellen Iteration abzuschneiden. Diese Methode wird als Aspirationsfenster bezeichnet und ist universell einsetzbar.

Ruhesuche


Diese Methode soll den „Horizonteffekt“ bekämpfen. Nur die Suche in der richtigen Tiefe zu stoppen, kann sehr gefährlich sein. Stellen Sie sich vor, wir hielten mitten im Austausch von Königinnen an - das Weiß nahm die schwarze Königin, und im nächsten Schritt sollte das Schwarz Weiß auswählen. Aber im Moment auf dem Brett - Weiß hat eine zusätzliche Königin und eine statische Einschätzung wird grundsätzlich falsch sein.

Zu diesem Zweck überprüfen wir vor einer statischen Bewertung alle Erfassungen (manchmal sogar Prüfer) und gehen den Baum hinunter zu einer Position, an der es keine möglichen Erfassungen und Prüfer gibt. Wenn alle Erfassungen die Schätzung verschlechtern, geben wir natürlich die Schätzung der aktuellen Position zurück.

Selektive Suche


Die Idee einer selektiven Suche besteht darin, länger zu brauchen, um „interessante“ Schritte zu berücksichtigen, und weniger, um uninteressant zu sein. Verwenden Sie dazu Erweiterungen, die die Suchtiefe an bestimmten Positionen erhöhen, und Abkürzungen, die die Suchtiefe verringern.

Die Tiefe wird bei Eroberungen, Kontrolleuren, erhöht, wenn der Zug der einzige oder viel besser ist als die Alternativen oder wenn es einen übergebenen Bauern gibt.

Schneiden und Schneiden


Mit Schnitten und Schnitten ist alles viel interessanter. Sie können die Größe des Baumes erheblich reduzieren.

Kurz zum Ausschneiden:
  • - — , . , , . , , , , .
  • — , -. , , . (1-2).
  • — , , . . PV . .
  • Multi-Cut — M(, 6) C(, 3) Cut-node, .
  • null- — null- ( ) , . , , , , .


Abkürzungen werden verwendet, wenn wir nicht so sicher sind, dass die Bewegung schlecht ist, und sie daher nicht abschneiden, sondern einfach die Tiefe verringern. Zum Beispiel ist Rasieren eine Abkürzung, vorausgesetzt, die statische Schätzung der aktuellen Position ist kleiner als Alpha.

Aufgrund der hochwertigen Sortierung von Bewegungen und Abschaltungen erreichen moderne Motoren einen Verzweigungskoeffizienten unter 2 . Aus diesem Grund bemerken sie leider manchmal keine nicht standardmäßigen Opfer und Kombinationen.

NegaScout und PVS


Zwei sehr ähnliche Techniken, die die Tatsache nutzen, dass sich der PV-Knoten, nachdem wir ihn gefunden haben (vorausgesetzt, unsere Bewegungen sind ziemlich gut sortiert), höchstwahrscheinlich nicht ändert, dh alle verbleibenden Knoten geben eine niedrigere Bewertung als Alpha zurück. Anstatt mit einem Fenster von Alpha bis Beta zu suchen, suchen wir daher mit einem Fenster von Alpha bis Alpha + 1, wodurch wir die Suche beschleunigen können. Wenn wir in einem Knoten Beta-Clipping erhalten, muss dies natürlich bereits durch eine normale Suche neu bewertet werden.

Der Unterschied zwischen den beiden Methoden liegt nur im Wortlaut - sie wurden ungefähr zur gleichen Zeit, aber unabhängig voneinander entwickelt und sind daher unter verschiedenen Namen bekannt.

Parallele Suche


Die Parallelisierung von Alpha Beta ist ein separates großes Thema. Ich werde es kurz durchgehen, und wen interessiert das schon? Schauen Sie sich die parallele Alpha-Beta-Suche auf Multiprozessoren mit gemeinsamem Speicher an . Die Schwierigkeit besteht darin, dass bei einer parallelen Suche viele Cut-Knoten analysiert werden, bevor ein anderer Thread eine Gegenargumentation findet (installiert eine Beta), während bei einer sequentiellen Suche mit guter Sortierung viele dieser Knoten abgeschnitten würden.

Lazy SMP


Ein sehr einfacher Algorithmus. Wir starten einfach alle Threads gleichzeitig mit derselben Suche. Die Kommunikation erfolgt über eine Hash-Tabelle. Lazy SMP war überraschend effektiv, so dass der Top-End-Stockfish mit YBW darauf umstieg. Einige glauben zwar, dass die Verbesserung auf eine schlechte Implementierung von YBWC und zu aggressives Clipping zurückzuführen ist und nicht auf den Vorteil von Lazy SMP.

Young Brothers Wait Concept (YBWC)


Der erste Knoten (älterer Bruder) sollte vollständig analysiert werden, wonach eine parallele Analyse der verbleibenden Knoten (jüngere Brüder) gestartet wird. Die Idee ist dieselbe, der erste Schritt verbessert entweder das Alpha erheblich oder ermöglicht es Ihnen sogar, alle anderen Knoten abzuschneiden.

Dynamische Baumaufteilung (DTS)


Schneller und komplexer Algorithmus. Ein wenig über die Geschwindigkeit: Die Suchgeschwindigkeit wird durch ttd (Zeit bis zur Tiefe) gemessen, dh die Zeit, während der die Suche eine bestimmte Tiefe erreicht. Dieser Indikator kann normalerweise verwendet werden, um die Arbeit verschiedener Versionen eines Motors oder eines Motors zu vergleichen, der mit einer unterschiedlichen Anzahl von Kernen läuft (obwohl Komodo beispielsweise die Breite des Baums erhöht, wenn mehr Kerne verfügbar sind). Zusätzlich zeigt die Engine während des Betriebs die Suchgeschwindigkeit in nps (Knoten pro Sekunde) an. Diese Metrik ist viel beliebter, erlaubt aber nicht einmal dem Motor, sich mit sich selbst zu vergleichen. Lazy SMP, bei dem es keine Synchronisation gibt, erhöht die NPS fast linear, aber aufgrund der großen Menge an unnötiger Arbeit ist seine ttd nicht so beeindruckend. Während sich für DTS nps und ttd fast gleich ändern .

Um ehrlich zu sein, konnte ich diesen Algorithmus, der trotz seiner hohen Effizienz buchstäblich in zwei Motoren verwendet wird, immer noch nicht vollständig herausfinden. Für wen es sehr interessant ist, folgen Sie dem Link oben.

Bewertung


Wir haben also die notwendige Tiefe erreicht, haben nach Ruhe gesucht und müssen schließlich die statische Position bewerten.

Der Computer wertet die Position in Bauern aus: +1,0 bedeutet, dass Weiß einen Vorteil von 1 Bauern hat, -0,5 bedeutet, dass Schwarz einen Vorteil von einem halben Bauern hat. Die Matte wird auf 300 Bauern geschätzt, und die Position, in der die Anzahl der Züge zur Matte x bekannt ist, liegt bei (300-0,01x) Bauern. +299,85 bedeutet, dass sich Weiß in 15 Zügen paart. In diesem Fall arbeitet das Programm selbst normalerweise mit ganzen Schätzungen in Tausendfüßlern (1/100 Bauern).

Welche Parameter berücksichtigt der Computer bei der Bewertung einer Position?

Material und Mobilität


Das Einfachste. Die Königin besteht aus 9-12 Bauern, der Turm aus 5-6, der Ritter und der Bischof aus 2,5-4 und der Bauer aus einem Bauern. Im Allgemeinen ist Material eine würdige Heuristik zur Bewertung einer Position, und jeder Positionsvorteil verwandelt sich am Ende normalerweise in einen materiellen.

Mobilität wird als einfach angesehen - die Anzahl der möglichen Bewegungen in der aktuellen Position. Je mehr von ihnen, desto mobiler ist die Armee des Spielers.

Formpositionstabellen


Der Ritter in der Ecke des Bretts ist normalerweise schlecht, Bauern, die näher am feindlichen Rücken liegen, werden wertvoller und so weiter. Für jede Figur wird abhängig von ihrer Position auf dem Brett eine Tabelle mit Boni und Strafen erstellt.

Bauernstruktur


  • Doppelbauern - zwei Bauern in derselben Vertikalen. Oft ist es schwierig, sie mit anderen Bauern zu schützen, es wird als Schwäche angesehen.
  • — , . , .
  • — , . ,
  • — , . , .



Alle oben genannten Parameter wirken sich je nach Spielphase auf unterschiedliche Weise auf die Bewertung des Spiels aus. In der Eröffnung macht der übergebene Bauer keinen Sinn, aber im Endspiel musst du den König in die Mitte des Bretts bringen und dich nicht hinter den Bauern verstecken.

Daher haben viele Motoren eine separate Bewertung für das Endspiel und für das Debüt. Sie bewerten die Phase des Spiels in Abhängigkeit von dem auf dem Brett verbleibenden Material und berücksichtigen dementsprechend die Bewertung - je näher am Ende des Spiels, desto weniger wird die Eröffnungspunktzahl beeinflusst und desto mehr ist das Endspiel.

Andere


Zusätzlich zu diesen grundlegenden Faktoren können die Motoren der Bewertung einige andere Faktoren hinzufügen - zum Beispiel die Sicherheit des Königs, verschlossene Teile, Bauerninseln, die Kontrolle über das Zentrum usw.

Genaue Bewertung oder Schnellsuche?


Traditioneller Streit: Ist effektiver, bewertet die Position genau oder erzielt eine größere Suchtiefe. Die Erfahrung hat gezeigt, dass zu "schwere" Bewertungsfunktionen unwirksam sind. Andererseits führt eine detailliertere Bewertung unter Berücksichtigung von mehr Faktoren normalerweise zu einem „schöneren“ und „aggressiveren“ Spiel.

Debütbücher und Endgame-Tabellen


Debütbücher


Zu Beginn des Computerschachs spielten Programme ihr Debüt sehr schwach. Das Debüt erfordert oft strategische Entscheidungen, die sich auf das gesamte Spiel auswirken. Andererseits war die Eröffnungstheorie bei Menschen gut entwickelt, die Eröffnung wurde wiederholt analysiert und aus dem Gedächtnis gespielt. So wurde ein ähnlicher "Speicher" für Computer erstellt. Ausgehend von der Ausgangsposition wurde ein Zugbaum erstellt und jeder Zug ausgewertet. Während des Spiels wählte die Engine mit einer bestimmten Wahrscheinlichkeit einfach einen der „guten“ Züge.

Seitdem sind die Debütbücher gewachsen, viele Debüts werden bis zum Endspiel mit Computern analysiert. Es besteht keine Notwendigkeit für sie, starke Motoren haben gelernt, das Debüt zu spielen, aber sie verlassen die Hauptlinien ziemlich schnell.

Endgame-Tabellen


Zurück zur Einführung. Denken Sie an die Idee, viele Positionen im Speicher zu speichern und die richtige auszuwählen. Da ist sie. Für eine kleine Anzahl (bis zu 7) von Zahlen werden alle vorhandenen Positionen berechnet. Das heißt, in diesen Positionen beginnt der Computer perfekt zu spielen und gewinnt mit der minimalen Anzahl von Zügen. Minus ist die Größe und Zeit der Generierung. Die Erstellung dieser Tabellen half beim Studium von Endspielen.

Tabellengenerierung


Wir generieren alle möglichen (unter Berücksichtigung der Symmetrie) Positionen mit einer bestimmten Menge von Formen. Unter ihnen finden und bezeichnen wir alle Positionen, an denen die Matte steht. Beim nächsten Durchgang bezeichnen wir alle Positionen, an denen Sie mit einer Matte Positionen einnehmen können - an diesen Positionen wird eine Matte in einer Runde platziert. Somit finden wir alle Positionen mit einem Partner 2,3,4, 549 Züge. In allen nicht markierten Positionen - ein Unentschieden.

Nalimov-Tabellen


Die ersten Endgame-Tabellen wurden bereits 1998 veröffentlicht. Für jede Position werden das Ergebnis des Spiels und die Anzahl der Züge auf die Matte mit einem idealen Spiel gespeichert. Die Größe aller sechsstelligen Endungen beträgt 1,2 Terabyte.

Lomonosov-Tabellen


Im Jahr 2012 wurden alle siebenstelligen Endungen (außer 6 gegenüber 1) auf dem Supercomputer Lomonosov an der Moskauer Staatsuniversität gezählt . Diese Basen sind nur für Geld erhältlich und dies sind die einzigen vorhandenen vollständigen siebenstelligen Endgame-Tabellen.

Syzygy


Der De-facto-Standard. Diese Basen sind viel kompakter als die Nalimov-Basen. Sie bestehen aus zwei Teilen - WDL (Win Draw Lose) und DTZ (Distance to Zeroing). WDL-Datenbanken sind für die Verwendung während der Suche vorgesehen. Sobald der Baumknoten in der Tabelle gefunden wurde, haben wir das genaue Ergebnis des Spiels an dieser Position. DTZ sind für die Verwendung in der Wurzel vorgesehen - sie speichern die Anzahl der Züge in einem aufhebenden Zähler der Züge (Zug durch Bauer oder Gefangennahme). Somit sind WDL-Basen für die Analyse ausreichend, und DTZ-Basen können bei der Analyse von Endspielen nützlich sein. Syzygy ist viel kleiner - 68 Gigabyte für sechsstellige WDL und 83 für DTZ. Es gibt keine siebenstelligen Basen, da für ihre Generierung ungefähr Terabyte RAM erforderlich sind.

Verwenden Sie


Endgame-Tabellen werden hauptsächlich zur Analyse verwendet, die Steigerung der Stärke der Game-Engines ist gering - 20-30 Punkte ELO . Da die Suchtiefe moderner Suchmaschinen jedoch sehr groß sein kann, treten beim Debüt immer noch Abfragen zu Endspielbasen aus dem Suchbaum auf.

Andere interessante


Giraffe oder neuronale Netze spielen Schach


Einige von Ihnen haben vielleicht von einer Schach-Engine in neuronalen Netzen gehört, die das IM-Niveau erreicht hat (was, wie wir in der Einleitung verstanden haben, für die Engine nicht so cool ist). Es wurde von Matthew Lai auf Bitbucket geschrieben und veröffentlicht , der leider aufgehört hat, daran zu arbeiten, weil er bei Google DeepMind angefangen hat .

Optimierungsparameter


Das Hinzufügen einer neuen Funktion zum Motor ist nicht schwierig, aber wie kann ich überprüfen, ob eine Verstärkung erzielt wurde? Die einfachste Möglichkeit besteht darin, mehrere Spiele zwischen der alten und der neuen Version zu spielen und zu sehen, wer gewinnt. Wenn die Verbesserung jedoch gering ist und normalerweise nach dem Hinzufügen aller Hauptfunktionen erfolgt, sollten mehrere tausend Spiele vorhanden sein, da sonst keine Zuverlässigkeit besteht.

Stockfisch


Es gibt viele Leute, die an dieser Engine arbeiten, und jede ihrer Ideen muss überprüft werden. Mit der aktuellen Stärke des Motors erhöht sich jede Verbesserung um einige Bewertungspunkte, aber am Ende wird ein stetiges Wachstum von mehreren zehn Punkten pro Jahr erzielt.

Ihre Lösung ist typisch für Open Source - Freiwillige geben ihre Kraft, um Hunderttausende von Spielen auf ihnen zu fahren.

CLOP


Ein Programm , das Parameter durch lineare Regression optimiert und dabei die Ergebnisse von Engine-Spielen mit unterschiedlichen Parametern verwendet. Von den Minuspunkten - eine sehr begrenzte Aufgabengröße: Um hundert Parameter zu optimieren (eine völlig ausreichende Anzahl für den Motor), ist es zumindest für eine angemessene Zeit nicht möglich.

Texels Stimmung


Löst das Problem der vorherigen Methode. Wir nehmen eine große Anzahl von Positionen ein (der Autor bot 9 Millionen Positionen aus 64.000 Spielen an, ich nahm 8 Millionen aus fast 200.000), für jede speichern wir das Ergebnis des Spiels (Weiß gewann 1, Unentschieden 0,5, besiegte 0). Jetzt minimieren wir den Fehler, der die Summe der Quadrate der Differenz des Ergebnisses und des Sigmas der Schätzung ist. Die Methode ist effektiv und beliebt, funktioniert jedoch nicht bei allen Motoren.

Stockfisch-Tuning


Eine andere Technik vom Anführer. Wir nehmen einen Parameter gleich x und vergleichen (in mehreren Zehntausenden von Losen) die Engine mit einem Parameter gleich x-Sigma und x + Sigma. Wenn der Motor mit einem großen Parameter gewonnen hat, bewegen Sie ihn ein wenig nach oben, andernfalls ein wenig nach unten, und wiederholen Sie den Vorgang.

Motorwettbewerbe


Von allen durchgeführten Wettbewerbstests möchte ich TCEC separat unterscheiden . Es unterscheidet sich von allen anderen durch seine leistungsstarke Hardware, sorgfältige Auswahl der Öffnungen und lange Kontrolle. Im letzten Finale wurden 100 Spiele auf 2 x Intel Xeon E5-2690v3 mit 256 Gigabyte RAM mit 180 '+ 30 "Kontrolle gespielt. Unter solchen Bedingungen war die Anzahl der Draws riesig und nur 11 Spiele waren effektiv.

Fazit


In diesem langen Artikel habe ich kurz über die Struktur von Schachmotoren gesprochen. Viele Details wurden nicht bekannt gegeben, ich wusste einfach nichts oder vergaß zu sagen. Wenn Sie Fragen haben, schreiben Sie diese in die Kommentare. Darüber hinaus werde ich Sie auf zwei Ressourcen hinweisen, die Ihnen wahrscheinlich aufgefallen sind, wenn Sie alle im Artikel verteilten Links sorgfältig geöffnet haben:

Source: https://habr.com/ru/post/de390821/

More articles:


All Articles