Wie haben sich die Motoren seit Deep Blue verbessert?

16

Computerschach-Engines sind besser geworden, seit Deep Blue 1997 Kasparov besiegt hat.

Wurden die Algorithmen verbessert oder beruhten die Verbesserungen hauptsächlich darauf, dass dieselben Algorithmen dank schnellerer Hardware usw. schneller liefen?

Wenn erstere, sind diese algorithmischen Verbesserungen öffentlich?

Und wenn ja, welche Verbesserungen gab es? Wo kann ich darüber lesen?

MaxB
quelle
Wie ? Dramatisch.
Evargalo

Antworten:

8

Vielleicht können Sie einen Blick auf TalkChess werfen , ein Forum, das sich dem Computerschach widmet. Ich habe kürzlich einen Thread gefunden, der für Sie interessant sein könnte: Fortschritt in 30 Jahren in vier Intervallen von 7-8 Jahren

Einige Matches zwischen (ehemaligen) Top-Engines werden auf derselben Hardware gespielt . Der Test zeigt, dass in den letzten Jahren (2002-2017) der Gewinn hauptsächlich durch Software-Verbesserungen erzielt wurde. Im Test erzielte Stockfish (2017) gegen RobboLito (2009) beeindruckende 94/100, während RobboLito seinerseits Shredder (2002) mit 92/100 zerschlug.

Eine wichtige Bemerkung: Da Parallel Computing in den älteren Engines nicht implementiert ist, wurde der Test auf einem einzelnen Kern durchgeführt. Infolgedessen wird der Hardwaregewinn von parallelen Maschinen nicht gemessen. Andererseits könnte man argumentieren, dass paralleles Rechnen auch ein Softwaregewinn ist: Es ist nicht einfach, eine effiziente und gut skalierbare Parallelisierung für den Suchalgorithmus zu entwerfen und zu implementieren.

Die Stockfish- Engine ist Open Source, daher sind die algorithmischen Verbesserungen öffentlich. Viele Dokumentationen finden Sie unter https://chessprogramming.wikispaces.com

Maxwell86
quelle
Dies beantwortet seine Behauptung. Versuchen Sie das nächste Mal, die Frage zu beantworten.
Fred Knight
1
Nun, ich glaube, ich habe die Frage beantwortet: Der Gewinn wird hauptsächlich durch Algorithmusverbesserungen erzielt. Außerdem habe ich Daten gezeigt, die diese Behauptung stützen (siehe Link) und auf einen möglichen Mangel hingewiesen (keine Parallelisierung gemessen).
Maxwell86
3

Ich kann nicht für den Algorithmus sprechen, der für Deep Blue verwendet wird, aber ich werde versuchen, die Verbesserungen in der Schachprogrammierung zu erklären. Geschwindigkeit ist die größte Verbesserung. Deep Blue verwendete dedizierte Multiprozessor-Computer, so dass ein Vergleich nicht wirklich möglich ist.

https://chessprogramming.wikispaces.com/ ist eine großartige Quelle, aber schwer zu navigieren.

Es gibt 3 Hauptfunktionen, die optimiert wurden, um eine Schachengine zu verbessern: die Auswertungs-, Zuggenerierungs- und Suchfunktionen.

Die Evaluierung ist am schwierigsten zu programmieren, da es viele Ausnahmen von den Regeln gibt. Da der Festplattenspeicher immer billiger wird, können mit der Auswertungsfunktion mehr Ausnahmen ausgewertet werden.

Die Generierung von Zügen sowie das Durchführen und Aufheben von Zügen verbrauchen viel Speicher, da sie so oft durchgeführt werden müssen. Die gebräuchlichsten Generierungsfunktionen sind Mailbox, Bitboard, 0x88, 8x8, erweiterte Boards (10x10, 10x12) und ein vorbestimmtes Verschiebungsarray / eine vorgegebene Verschiebungstabelle (* Ich verwende eine indizierte Verschiebungstabelle). Derzeit ist die Meinung, dass Bitboards die schnelleren sind, und die Verwendung von Magic Bitboards beschleunigt dies um bis zu 30%. Dr. Robert Hyatt, Professor und Erfinder der Cratfy-Schach-Engine, behauptet, keine signifikante Geschwindigkeitssteigerung zu haben.

Die frühe Suchfunktion war die primitive Min-Max-Funktion. Grundsätzlich sollten Sie versuchen, die Punktzahl der Seite zu maximieren, um sich zu bewegen und die Punktzahl des Gegners zu minimieren. Alpha-Beta war die erste Verbesserung. Sie reduzierten die Anzahl der Züge, die anhand von Transpositionstabellen, Grenzwerten, Aspirationsfenstern und Verlaufsheuristiken durchsucht wurden. Dies sind Tiefensuchen. Es gibt auch die interne iterative Vertiefungssuche, bei der versucht wird, die "besten" Züge zu suchen, in der Hoffnung, dass sich die Suche nach anderen Zügen als erfolglos erweisen wird.

HINWEIS: Meine Indextabelle. GNUChess und Jester verwenden beide ein Index-Array, um ihre Bewegungen zu generieren. Sie initialisieren den Motor, indem sie das Array mit möglichen Bewegungen füllen. Nehmen Sie die sechs Teile und berechnen Sie die erlaubten Züge, die von jedem Feld verfügbar sind. Also hatte jedes Stück ein [64] [8] Array. Ich nahm diese Idee und komprimierte sie in zwei Indizes und eine Tabelle. Die Tabelle enthält einen Wert, der angibt, ob die 16 Bewegungen möglich sind, ein Index enthält den Versatz der Bewegung und der andere enthält die Maske.

Offset [] = {-8, -1, 1, 8, -9, -7, 7, 9, -17, -15, -10, -6, 6, 10, 15, 17};

Maske [] = {1, 2, 4, 8, 16, 32, 64, 128, 256, ...};

Dann ist die Erzeugung einer Gleitbewegung so einfach wie das Nachschlagen der Gültigkeit der Maske in den zulässigen Offsets gegenüber dem Bewegungstisch.

Fred Knight
quelle
7
Ich versuche nicht auf Antworten zu antworten, aber das ist nur ... Alpha-Beta und Bitboards wurden LANG vor Deep Blue erfunden. Ich bin mir auch ziemlich sicher, dass Boardeval in keiner vernünftigen Engine auf HD zugreifen kann (die Latenz ist RIESIG). Viertens bin ich sehr skeptisch, dass die RAM-Größe einen echten Unterschied in Ihrer normalen Alpha-Beta-Suchimplementierung darstellt.
MaxB
Könnten Sie vielleicht einige Hyperlinks zu den von Ihnen diskutierten Konzepten hinzufügen? Als jemand, der sich für das Konzept interessiert, aber mit der Terminologie nicht vertraut ist, ist es schwer zu folgen, da ich nicht weiß, was ein Bitboard oder die Crafty-Chess-Engine ist.
Thunderforge
Ich dachte, dass ich klar war, dass ich nicht mit Deep Blue verglichen wurde, aber ich gab eine kurze Geschichte. Die Festplatte, auf die ich mich bezog, ist das Programm selbst. Jedes Mal, wenn ein neues Bewertungskonzept in eine Schachengine integriert wird, wird mehr Code und damit mehr HD-Speicherplatz benötigt.
Fred Knight
@Thunderforge, der eine Link, den ich gegeben habe, erklärt jeden Aspekt, den Sie jemals mit Schachprogrammierung beschäftigen könnten, aber ich gebe zu, dass es schwierig ist, zu navigieren. Ich habe gelernt, indem ich die Quellcodes anderer gelesen habe, aber der am meisten kommentierte ist Dr. Hyatts Crafty-Engine. Ich entscheide mich aus Platzgründen und aufgrund der Unterschiede zwischen Plattformen und Compilern, nicht zu umfassend zu sein. Wenn Sie nach dem Lesen der Wiki-Schachseite immer noch verwirrt sind, stellen Sie die Frage und ich bin sicher, dass viele eine bessere Antwort liefern werden.
Fred Knight
1
Every time that a new eval concept in included into a chess engine, more code, and therefore more HD space is required.Board-Evaluierungsfunktionen sind normalerweise so konzipiert, dass sie in den CPU-Cache passen. CPU-Cache << RAM << HD. Die HD-Größe macht keinen Unterschied.
MaxB
2

Wurden die Algorithmen verbessert?

Offensichtlich ja ein bisschen.

oder waren die verbesserungen hauptsächlich darauf zurückzuführen, dass dieselben algorithmen dank schnellerer hardware und software schneller liefen?

Minor nit: Wenn die Algorithmen besser wurden, wird die Software besser und es gibt kein "oder".

Das Mooresche Gesetz sagt uns, dass sich die Prozessorgeschwindigkeit ungefähr alle 18 Monate verdoppelt. Das heißt, es hat sich in 20 Jahren etwa 13 Mal verdoppelt. Das macht moderne Prozessoren irgendwo in der Region um das 8000-fache schneller. Die weitaus größte Verbesserung der Motorleistung ist auf schnellere Hardware zurückzuführen.

Wenn erstere, sind diese algorithmischen Verbesserungen öffentlich?

Und wenn ja, welche Verbesserungen gab es? Wo kann ich darüber lesen?

Nun, es war nicht das erstere, es war das letztere. Nichtsdestotrotz sind die Verbesserungen größtenteils Open Source und werden durch Herunterladen der Quellen für Engines wie Stockfish frei sichtbar . Vielleicht lohnt es sich auch, den allgemeinen Stockfish-Download-Link anzugeben, da der spezifische Quellcode-Link wahrscheinlich abläuft, wenn Version 9 herauskommt.

Brian Towers
quelle
2
That means it has doubled roughly 13 times in 20 years.Ich glaube, Sie zitieren Moores Gesetz falsch. Es sagt nichts über die Prozessorgeschwindigkeit. Tatsächlich hat es sich eine Weile nicht mehr verdoppelt.
MaxB
hardware and softwareIch meinte Software wie bei der Implementierung des Algorithmus (ASM vs C ++), aber ich kann sehen, wie verwirrend es ist. Fest.
MaxB
1
Er Moores Gesetz ist richtig, außer dass er den Satz "im nächsten Jahrzehnt" enthält. Dies wäre 1975 gewesen, und er hatte Recht.
Fred Knight
-1, weil die Antwort falsch ist - auf der gleichen Hardware zerschlagen die aktuellen Engines immer noch ehemals Top-Engines.
Allure
0

Alles dreht sich um Algorithmen.

Gegen einen menschlichen Schachspieler anzutreten, war zu dieser Zeit einer der leistungsstärksten Computer der Welt. Mit diesem Brute-Force-Computing-Ansatz konnte Deep Blue sechs bis acht Züge vor sich sehen. In einem hart umkämpften Wettbewerb besiegte die Maschine Kasparov schließlich um 3 1/2 Spiele zu 2 1/2.

Sechs Jahre später war Kasparov an einem weiteren Wettbewerb zwischen Mensch und Maschine beteiligt. Diesmal spielte er gegen Deep Blues Nachfolger Deep Junior. Das Ergebnis war eine Unentschieden-Serie bei drei Spielen. Der größte Unterschied bestand darin, dass Deep Junior auf einem Computer lief, der ungefähr ein Prozent der Rechenleistung von Deep Blue hatte. Die Schachspielalgorithmen hatten sich so weit verbessert, dass sie mit hundertmal weniger Rechenleistung praktisch dasselbe Ergebnis erzielten.

David Hambling
quelle
4
Willkommen beim Schach! Sie haben den Hauptteil Ihrer Antwort so geschrieben, als wäre es ein Zitat. Könnten Sie bitte eine Quelle angeben?
Glorfindel
0

Haftungsausschluss: kein Experte.

Die Algorithmen wurden besser und die besten Engines von heute, die 1995 lief (Deep Blue war 1999), schlagen Kasparov mit Leichtigkeit. Nach meinem Verständnis gibt es zwei Aspekte von Algorithmen:

Suchen . Wenn ich zum Beispiel deine Königin mit meiner Königin nehme, schaut ein menschlicher Gegner automatisch zuerst auf die Rückeroberung. Für einen Computer wird jedoch jede mögliche Antwort auf QxQ ausgewertet. Fast die ganze Zeit ist dies verschwendete Rechenleistung. Ein guter Suchalgorithmus reduziert all diese "Zweige", da sie sowieso irrelevant sind.

Der Standardsuchalgorithmus ist Alpha-Beta-Bereinigung und wurde in den frühesten Schachcomputern verwendet. Ich weiß nicht, ob Deep Blue Alpha-Beta-Schnitt verwendet hat, moderne Motoren jedoch nicht. Infolgedessen sind ihre Suchanfragen "unsicher" - sie können beispielsweise übersehen, dass ein anderer Zug als die Wiedereroberung der Königin das Spiel gewonnen hätte. Es ist jedoch selten, dass dies passiert, und im Gegenzug schieben sie ihre Tiefen sehr hoch. ("Tiefe" ist ein Fachbegriff für die Suchtiefe der Engine. Daher schlägt eine Engine, die bis zur Tiefe 30 sucht, wahrscheinlich eine Engine, die nur bis zur Tiefe 20 sucht, wobei alle anderen Faktoren gleich sind.)

Auswertung . Dies ist der andere Motorcode. Ist es bei einer bestimmten Position besser für Weiß, Schwarz oder Gleichgestelltes? Dies kann alle möglichen Funktionen beinhalten, z

  • Wenn eine Seite mehr Material / Platz hat, gibt es einen Bonus für die Auswertung.
  • Wenn Weiß einen fortgeschrittenen Ritter hat, der von einem Bauern unterstützt wird, gib Weiß einen Bonus für das Auswerten.
  • Wenn der König von Schwarz blockiert ist, gib Weiß einen Bonus für das Auswerten.
  • Wenn Weiß einen Turm auf dem 7. Rang hat, geben Sie Weiß einen Bonus für die Auswertung.
  • Wenn es sich um ein Endspiel handelt (und es gibt Algorithmen, um zu entscheiden, ob die Position ein Endspiel ist) und beide Seiten Bischöfe mit entgegengesetzten Farben haben, verhängen Sie eine Strafe für die Auswertung (dh drücken Sie sie in Richtung 0,00).

Die heutigen Motoren bewerten Positionen viel besser als Deep Blue.

Ob die Algorithmen öffentlich sind, Stockfish ist derzeit die stärkste Engine der Welt und Open Source. Sie können den Code selbst von Github herunterladen .

Locken
quelle