Parallelisierung moderner Spielbaumsuchverfahren

Diplom-/Masterarbeit

In den vergangenen 3 Jahren konnten neuartige Spielbaumsuchverfahren erstaunliche Fortschritte gegenüber traditionellen Suchverfahren aufweisen. Während zur traditionellen Alpha-Beta Suche in den vergangenen Jahrzehnten diverse Arbeiten über Parallelisierungsansätze erschienen sind, wurde für die neuartige, auf einem Monte-Carlo Verfahren beruhende UCT-Spielbaumsuche noch sehr wenig Forschung betrieben.  

Die wohl prominenteste Anwendung des UCT-Algorithmus findet sich in diesen Tagen im Computer Go. Nachdem sich Computer im Schachspiel erfolgreich durchgesetzt haben, bildet das asiatische Brettspiel Go die aktuelle Herausforderung für Forschung im Bereich der künstlichen Intelligenz. Hier dominieren menschliche Spieler noch immer mit Abstand vor Computerprogrammen. Mit modernen Monte-Carlo Suchverfahren konnten in diesen Tagen neue Erfolge verzeichnet werden.

Im Rahmen der Arbeit sollen Konzepte zur Parallelisierung des UCT-Spielbaumsuchverfahrens für Cluster Rechensysteme erarbeitet werden. Die Evaluierung der Ergebnisse erfolgt durch die Implementierung eines parallelen UCT-Algorithmus für einen Cluster Rechner der Universität. Nach einer erfolgreichen Realisierung wird das entwickelte Verfahren in einem existierenden Go-Programm praktisch zum Einsatz kommen.

Art der Arbeit: 

• Einarbeiten in das Thema Monte Carlo Spielbaumsuche (20%)
• Entwurf eines Parallelisierungskonzeptes für Cluster (40%)
• Implementierung und Evaluation der Parallelisierung (40%)
  

Von Vorteil sind:

• Programmiererfahrung in C/C++
• Gutes mathematisches Verständnis (insb. Stochastik)
• MPI Kenntnisse
  

Kontakt/Betreuer:    

Bei Interesse oder weiteren Fragen wenden Sie sich bitte an Lars Schäfers.