Wie „denken“ Schachengines?

Ich möchte wissen, wie Motoren so programmiert sind, dass sie Bewegungen finden. Ich bin sicher, dass sie zuerst die erzwungensten Linien wie Erfassungen und Schecks berechnen. Aber was ist mit subtilen, tiefen Positionsbewegungen? Sie scheinen sie auch sehr schnell zu finden (im Allgemeinen. Natürlich verpassen sie solche Bewegungen ab und zu). Wie sind sie programmiert, um nach ruhigen Bewegungen / Positionsideen zu suchen? Sie können nicht einfach jede Bewegung brutal erzwingen, da dies zu lange dauern würde. Es sollte also eine clevere Möglichkeit geben, schnell zu den besten Bewegungen zu gelangen. Ich bin daran interessiert, das zu wissen, weil ich denke, es würde den Spielern helfen, das Spielfeld auch in der realen Welt zu überdenken.

Im Allgemeinen verwenden Schach-Engines einen Entscheidungsbaum. Die Wurzel des Baums ist die aktuelle Position und hat einen untergeordneten Knoten für jede Position, die durch einen legalen Zug erstellt werden kann. Jeder dieser Knoten verfügt wiederum über einen untergeordneten Knoten für die Positionen, die durch einen legalen Wechsel von diesen erreicht werden können. Der Motor schiebt den Baum in eine Tiefe, die durch seine Fähigkeiten und die Zeit, die er zum "Nachdenken" benötigt, definiert ist. Positionen, die auf mehr als eine Weise erreicht werden können, werden einfach mit Querverweisen versehen, sodass sie nicht mehr als einmal berücksichtigt werden müssen. Sobald der Baum erstellt ist, analysiert der Computer die endgültigen Positionen im Baum anhand eines Satzes gewichteter Regeln und beginnt, diejenigen zu entfernen, die unerwünscht sind oder die der Gegner nicht erreichen kann. Der Baum wird auf diese Weise gefällt, bis nur noch eine Bewegung übrig ist und der Computer diese Bewegung ausführt.

http://www.chess.com/blog/zaifrun enthält Serien oder Artikel zum Erstellen einer Schachengine, wenn Sie einen tieferen Einblick in deren Funktionsweise erhalten möchten.

Sie stellen eine ziemlich komplexe Frage, aber es ist gut, auf die Grundlagen zurückzukommen. Es sind einige Konzepte zu berücksichtigen:

Auswertung

Wenn einem (echten) Spieler eine Position angezeigt wird und er gefragt wird, wer dieses Spiel gewinnt, wie entscheidet er dann? Höchstwahrscheinlich werden sie ein paar grundlegende Dinge prüfen, wie zum Beispiel: Materialunterschiede, der Grad, in dem Teile entwickelt wurden oder "gut" positioniert sind, doppelte / isolierte / verbundene / übergebene Bauern, (kontrollierte) offene Dateien, wie weit oben Das Brett, auf dem die Bauern stehen.

Wenn Sie müssten, könnten Sie nun einen systematischen Weg finden, um eine Positionsbewertung auf der Grundlage der obigen Angaben zu berechnen. Sie können beispielsweise festlegen, dass ein Bauer 1 Punkt wert ist und dass ein überholter Bauer 0,3 Punkte mehr wert ist. Einzelne oder doppelte Bauern sind möglicherweise etwas weniger wert. Wenn Sie alles zusammenzählen, erhalten Sie einen Schätzwert für die unmittelbare Position.

Dies wird als Auswertung bezeichnet , und im Grunde haben alle Schachprogramme eine Möglichkeit, Positionen zu bewerten (wobei neuartige KI-Schachengines ignoriert werden, die normalerweise sehr schwach sind).

Aber was ist mit subtilen, tiefen Positionsbewegungen?

Nun, wir haben die Oberfläche der Positionsbewertung kaum zerkratzt. Die tatsächliche Implementierung einer Bewertungsfunktion könnte vereinfachend sein, um zu ermöglichen, dass mehr Positionen pro Sekunde (wenn auch grob) oder komplexer bewertet werden, was zu weniger bewerteten Positionen führt, aber mit einem höheren Maß an Vertrauen. Es ist nicht ungewöhnlich, dass die Bewertungsfunktion Hunderte oder sogar Tausende separater Informationen berücksichtigt.

Suche

Ich habe speziell etwas von dem oben Genannten ausgelassen, woran die meisten echten Spieler sofort denken werden - gibt es eine Möglichkeit, das Spiel für beide Seiten sofort zu gewinnen? Irgendwelche Kumpels oder "hängende" Teile sichtbar? Obwohl es einfach ist, dies zu trivialisieren, ist es alles andere als trivial.

Was bedeutet es für einen Spieler, volles Vertrauen in eine Kombination zu haben? Am Ende läuft es darauf hinaus, alle Optionen berechnet zu haben. Echte Spieler werden dies normalerweise nicht tun (mit Ausnahme von trivialen oder sehr erzwungenen Spielern). Meistens werden wir nur eine Handvoll Optionen in Betracht ziehen und andere ausschließen, die "nicht konstruktiv" zu sein scheinen oder offensichtlich zu einem Verlust führen . Wir machen bei dieser Berechnung häufig Fehler, z. B. stellen wir möglicherweise fest, dass durch eine Änderung der Zugreihenfolge die Bedrohungen verflogen sind usw. Um sich einer Kombination völlig sicher zu sein, müssen Sie unter der Annahme jeder einzelnen tatsächlich bis zu ihrem Abschluss rechnen Der Spieler stellt nur den bestmöglichen Zug zur Verfügung (dies wird als "min / max" bezeichnet).

Angesichts der Tatsache, dass Schach über einen viel größeren Suchraum verfügt (hier wird von "allen möglichen Zügen in der Zukunft" gesprochen), als dies mit einem Computer möglich ist, müssen Kompromisse eingegangen werden. Genauso wie der Mensch kann der Computer aufgrund bestimmter Kriterien entscheiden, ganze Gedankengänge außer Acht zu lassen. Dies ist als Heuristik bekannt . Es ist erwähnenswert, dass Sie sich einer Kombination nur dann wirklich sicher sein können, wenn Sie sie brutal einsetzen. Eine komplexe Auswertungsfunktion kann jedoch häufig das Vorhandensein von Bedrohungen erkennen (z. B. könnten wir Gabeln, Spießgelegenheiten usw. zählen, um eine Suche in diese Richtung zu leiten ).

Obwohl Computer extrem schnell sind, sind es letztendlich die Heuristiken, die es ihnen ermöglichen, so tief zu rechnen. Sie werden jedoch überrascht sein, wie tief die modernen Motoren vollständig kalkulieren. In der Regel sind es sogar in schnellen Spielen mehr als drei Züge.

Fazit / alles verbinden

Zusammenfassend lässt sich sagen, dass in Bewertungsfunktionen eine Menge Intelligenz eingebaut ist (dh sie berücksichtigen mehr Dinge als ein durchschnittlicher menschlicher Spieler). Heuristiken ermöglichen es dem Computer, Gedankenlinien zu bereinigen, von denen er entscheidet, dass sie wahrscheinlich nicht gut enden werden. und Computer sind extrem, extrem schnell. Addiere sie und sie sind ziemlich schwer zu schlagen.

Ich stimme den Antworten zu.

Ich erinnere mich, dass GM Roman Dzindzichashvili darüber sprach, in einem von Romans Laborvideos , ich erinnere mich nicht, welches Video es war (wenn jemand die Details kennt, bitte bearbeite meine Antwort).

Roman sagte, der Entwickler von Fritz Engine sei sein Freund. Also testete Roman Fritz, um zu sehen, wie gut es war, und der Entwickler sagte Roman, damit Fritz komplexe Entscheidungen treffen könne (z. B. Materialien gegen Positionsvorteile opfern), müssten sie den Wert der Stücke ändern, wie z. B. das Programm erzählen dass ein schlechter Bischof 1 Punkt wert ist, ein Bischof auf einer offenen Diagonale 7 Punkte wert ist, Ritter 5 Punkte in engen Positionen wert sind ...

Ich kenne nicht die genauen Zahlen für jedes Stück, aber so funktioniert es, und jetzt hat Ihr Motor kein Problem mehr, einen schlechten Bischof oder was auch immer zu opfern, wenn Sie ihm den Wert jedes Stücks in jeder Position mitteilen können.

BEARBEITEN

Siehe auch Das Schach-Programmier-Wiki .

Es ist für Computer einfach unmöglich, tief genug zu schauen (25 Lagen und mehr) und jede mögliche Bewegung zu überprüfen.

Möglich macht dies die sogenannte Alpha-Beta-Bereinigung , bei der menschenähnliche (aber weitaus bessere) Computer nur den vielversprechenden Fortsetzungen folgen.

Sie bewerten die Positionen ständig (basierend auf einigen vorkodierten Regeln, Wertschätzung von Material, Königssicherheit, Aktivität, Bauernstrukturen usw.) und untersuchen Variationen, die sie anscheinend zur besten Position führen.

Es ist immer noch nah an der Magie, wie sie es schaffen, Millionen dieser Positionen in einer Sekunde effizient genug zu bewerten.

Zusammenfassend kann man sagen, dass sie nicht alle Züge betrachten können, wenn sie strategisches Schach spielen, aber sie können sehr schnell anständige Züge betrachten. Das Problem liegt immer noch in den sehr langfristigen Plänen und dem Horizont, bis zu dem sie sehen können, aber daran wird gearbeitet (Rybka analysiert viel langsamer, spielt aber viel mehr Positionsschach, während Houdini romantisch ist und mehr Züge berechnet) und aggressiver spielen). Sogar Computer haben ihre eigenen Stile!

Alpha-Beta-Bereinigung bedeutet einfach, dass Sie, wenn Sie eine Linie finden, die sich als schlecht für Sie herausstellt, aufhören, diesen Kandidatenzug zu betrachten, und stattdessen andere ausprobieren. Es ist eine Art Rückwärtsschnitt, das heißt, Sie werden nie einen guten Zug verpassen. Im Gegensatz dazu basiert das Beschneiden in Vorwärtsrichtung mehr auf Vermutungen. Sinnloses Beschneiden, Reduzieren verspäteter Züge und Rasieren sind Arten des Vorwärtsbeschneidens, und alle beruhen auf dem Gefühl des Programmierers, welche Art von Zügen in Betracht gezogen werden sollten. Ein Programm, das viel vorwärts schneidet, kann zwar überraschende Opfer verpassen, die zur Paarung führen, aber andererseits werden viele wirklich schlechte Bewegungen eliminiert, und es kann auch genauer untersucht werden, welche Bewegungen von ihm bevorzugt werden.

Die meisten Suchmaschinen durchsuchen die ersten Züge in voller Tiefe und prüfen dabei alle Möglichkeiten. Wenn kein Zug hoch ausfällt (dh deutlich schlechter erscheint als ein Zug, den Sie bereits in Betracht gezogen haben), erweitern Sie die Suche nur ein bisschen mehr. Im Allgemeinen erkunden Sie jede Zeile weiter, bis Sie eine Ruheposition erreicht haben (ohne Überprüfungen, Erfassungen, Gefährdungen durch Gefährten usw.), und führen dann Ihre Bewertung durch. Leise Bewegungen werden möglicherweise nicht berücksichtigt, wenn sie sich tief im Suchbaum befinden. Sobald Sie jedoch diese tatsächliche Position im Spiel erreicht haben, werden alle Bewegungen von der Engine sowohl leise als auch scharf betrachtet. Sie können dies tatsächlich manchmal an der Motorleistung erkennen, wenn ein Motor plötzlich eine Bewegung bevorzugt, die er nicht in Betracht gezogen hat.

Motoren rechnen so schnell, dass es für sie nicht so wichtig ist, zu überlegen, welche Bewegung sie zuerst betrachten, aber für den Menschen ist dies eine Schlüsselfrage. Jonathan Tisdall versucht, dies in seinem Buch "Improve Your Chess Now" zu beantworten. Wenn Sie angegriffen werden, schlägt er vor, dass Sie zuerst die heftigsten Bewegungen betrachten. Wenn Sie verteidigen, schauen Sie zuerst auf die schwierigsten Linien. Er zitiert auch positionelle Faustregeln (z. B. Zentralisierung, Koordination), wenn er entscheidet, welche Schritte zuerst zu betrachten sind.

Andere Bücher, die relevant sein könnten, sind Emmanuel Neimanns Invisible Chess Moves und Charles Hertans Forcing Chess Moves. Beide argumentieren, dass es wichtig ist, unwahrscheinliche oder überraschende Bewegungen in scharfen Positionen zu berücksichtigen. Hertan spricht sogar über die Entwicklung von "Computeraugen" für solche Taktiken.