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?
Antworten:
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
quelle
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.
quelle
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.Offensichtlich ja ein bisschen.
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.
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.
quelle
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.hardware and softwareIch meinte Software wie bei der Implementierung des Algorithmus (ASM vs C ++), aber ich kann sehen, wie verwirrend es ist. Fest.Alles dreht sich um Algorithmen.
quelle
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
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 .
quelle