Verteiltes Alpha-Beta-Beschneiden

Ich suche nach einem effizienten Algorithmus, mit dem ich den Minimax-Suchbaum für Schach mit Alpha-Beta-Bereinigung auf einer verteilten Architektur verarbeiten kann. Die Algorithmen, die ich gefunden habe (PVS, YBWC, DTS, siehe unten), sind alle ziemlich alt (1990 ist die neueste). Ich gehe davon aus, dass es seitdem viele wesentliche Fortschritte gegeben hat. Was ist der aktuelle Standard in diesem Bereich?

Bitte verweisen Sie mich auch auf die Erklärung eines Idioten zu DTS, da ich sie aus den Forschungsberichten, die ich gelesen habe, nicht verstehen kann.

Die oben genannten Algorithmen:

PVS: Prinzipielle Variationsaufteilung
YBWC: Junge Brüder warten Konzept
DTS: Dynamische Baumaufteilung

sind alle diskutiert hier .

algorithms distributed-systems board-games verdrahten
quelle

Vielleicht ist dies eine interessante Lektüre: chessbase.com/newsdetail.asp?newsid=8047

Alex ten Brink

Nun, dies ist ein Problem (Parallelisierung der Minimax-Suche oder einer ihrer Varianten), das besonders schwierig ist. In einem Artikel von Richard Korf mit dem Titel "Research Challenges in Combinatorial Search", der in diesem Jahr erscheinen soll, heißt es: "[...] Minimax-Suche mit Alpha-Beta-Prunning war notorisch schwierig zu parallelisieren". Ich bezweifle aufrichtig Es gibt einen Algorithmus, der es immer effizient macht ...

Carlos Linares López

Sollte ich mich für einen serialisierten Algorithmus entscheiden, wenn ich bedenke, dass ich nur ein sehr bescheidener Student der Informatik im 4. Semester bin, oder sollte ich versuchen, eine akzeptable sublineare Beschleunigung zu erwarten?

Entschuldigung für die Verzögerung meiner Antwort, die in meinem Posteingang völlig unbemerkt blieb. In der Tat würde ich erwarten, dass die endgültigen Einsparungen vollständig von der Verteilung der von Ihrer Bewertungsfunktion zugewiesenen Bewertungen auf die Blätter des Suchbaums abhängen. Im Allgemeinen gibt es keine Garantie dafür, dass ein verteilter Suchalgorithmus eine wesentlich bessere Leistung erzielt als ein serialisierter Alpha-Beta-Suchalgorithmus. Daher würde ich auf jeden Fall eine serialisierte Version davon nehmen und versuchen, so viele Verbesserungen wie möglich zu erzielen (Reihenfolge der Schritte, Umsetzungstabellen usw.)

Carlos Linares López

Ich hatte einige Erfolge mit paralleler Alpha-Beta (im Grunde wie auf der Wiki-Seite beschrieben, auf die Sie verlinkt haben).

Jeremy List

Antworten:

Ja, die Theorie hat sich aufgrund der Schachanalyseliteratur und der allgemeinen parallelen Programmiertechniken erheblich und etwas weiterentwickelt. Hier sind einige neuere Referenzen zum (Schach-) Alpha-Beta-Beschneiden über verteilte Cluster / Parallelität. Auch einige der frühen Literatur zu verteiltem Computerschach sind älter als viele grundlegende parallele Entwurfsmuster und können in diesem Rahmen konzeptualisiert werden.

Paralleler Alpha-Beta-Algorithmus auf der GPU / Strnad, Guid (2011)
Parallele Alpha-Beta-Suche auf Multiprozessoren mit gemeinsamem Speicher / Manohararajah (2001) 98pp!
Parallelisierung eines einfachen Schachprogramms / Greskamp, 2003
Paralleles Alpha-Beta-Beschneiden von Spielentscheidungsbäumen: Eine Schachimplementierung / Steele 1999
Ist es möglich, eine Minimax-Suche mit Alpha-Beta-Bereinigung parallel zu OpenMP durchzuführen? (Paketüberfluss)
Der DTS-Hochleistungsalgorithmus zur parallelen Baumsuche (Hyatt 1994)

Die Grundidee hinter DTS ist, dass Suchbäume basierend auf der Komplexität von Verschiebung / Layout auf Rechenknoten verteilt werden. Nicht genutzte Prozessoren, die "vorzeitig" fertig werden, können zusätzliche Arbeit leisten, die über eine anfängliche Zuweisung hinausgeht und anfänglich so gleichmäßig wie möglich verteilt werden kann, sich jedoch als ungleichmäßig herausstellt. Daher handelt es sich im Grunde genommen um eine Art "Load Balancing" - und "Producer / Consumer" -Warteschlange oder auch ähnlich wie bei der Auftragsplanung.

Dieser inaktive Prozessor sendet (unter Verwendung des gemeinsam genutzten Speichers) eine Rundsendung, dass er inaktiv ist, und ist verfügbar, um jedem anderen Prozessor zu helfen, die Suche in seinem Baum zu beenden. Die ausgelasteten Prozessoren erfassen die Daten zum "Status des Baums" und speichern sie im gemeinsam genutzten Speicher, damit der inaktive Prozessor sie prüfen kann. Dieser inaktive Prozessor analysiert diese Daten und entscheidet, welcher der beschäftigten Prozessoren (falls vorhanden) einen Baum zu haben scheint, der so kompliziert ist, dass es effizient wäre, bei der Suche zu helfen. Wenn eine solche Position gefunden wird, informiert der Leerlaufprozessor den Prozessor, der diesen Knoten besitzt, darüber und sie "schließen sich zusammen".

vzn
quelle