Optimistische verteilte Spielbaumsuche am Beispiel des Computerschachs

Viele einfache Ansätze zur Parallelisierung der Spielbaumsuche setzen noch Shared-Memory- Systeme voraus. Aber selbst ausgeklügelte Ansätze können in der Regel höchstens ein einzelnes Cluster-System ausnutzen. Eine Idee zur weiteren Erhöhung des Speedups der Spielbaumsuche bestand in der Vergangenheit darin, das Cluster-System auf der untersten Ebene mit speziell dafür ausgelegten Hardware-Komponenten zu erweitern. Zwei bekannte Beispiele sind das Field-Programmable-Gate-Array-(FPGA-)basierte HYDRA-System und IBM's DEEP BLUE, ein System, das geradezu legendären Ruhm erlangt hat. In dieser Arbeit wird ein umgekehrter Ansatz verfolgt, bei dem ein paralleles Schachprogramm, das auf einem einzelnen Cluster-System läuft, nicht auf unterster Ebene mit spezieller Hardware erweitert wird, sondern als so genannter Worker die Basiskomponente für einen weiteren, darüberliegenden Parallelisierungsansatz auf der Inter-Cluster-Ebene darstellt. Im Mittelpunkt der Untersuchung steht das eigene Optimistic-Pondering-Verfahren zur asynchronen verteilten Spielbaumsuche. Unter Wettkampfbedingungen nutzt es die Kenntnis über die nächsten erwarteten Antworten des Gegners aus, um mehrere Workers einer verteilten Umgebung mit einem spekulativen Vorausrechnen in der Art eines Fließbandprinzips zu beauftragen. Zusätzlich wird in der Kombination mit dem Young Brothers Wait Concept (YBWC) als untergeordnetem State-of-the-Art-Parallelisierungsverfahren auf Intra-Cluster-Ebene gezeigt, dass Optimistic Pondering auf Inter-Cluster-Ebene zu einem zweistufigen Ansatz erweitert werden kann, um die Rechenleistung geographisch getrennter Cluster-Systeme zur verteilten Spielbaumsuche auszunutzen. Als Ergebnis der prototypischen Realisierung wird das GRIDCHESS-System präsentiert. Die Praxistauglichkeit und Leistungsfähigkeit des GRIDCHESS-Systems und seiner Teilkomponenten werden anhand experimenteller Ergebnisse auf der Basis von Selfplay-Experimenten und erfolgreicher Teilnahmen an internationalen Turnieren, wie der International Paderborn Computer Chess Championship (IPCCC) oder der World Computer-Chess Championship (WCCC), gezeigt. Vor einem stochastischen Hintergrund wird ein mathematisches Modell für Optimistic Pondering vorgestellt, für das eine gute Übereinstimmung mit den experimentellen Ergebnissen gezeigt werden kann. Es wird davon ausgegangen, dass sich die Ergebnisse und Ideen der Arbeit auf andere Zwei-Personen-Nullsummenspiele mit vollständiger Information übertragen lassen, insbesondere auf Spiele, bei denen auch das konventionelle Vorausrechnen auf der Basis von Hauptvarianten bereits erfolgreich angewendet werden kann. Optimistic Pondering wird für solche Spiele besonders gut geeignet sein, für die sich die Folge der nächsten Züge noch besser "vorhersehen" lässt als für Schach.