In dieser Arbeit wird die Lösung von konkreten kombinatorischen Ein- und Mehrpersonenspielen (Brettspielen) durch Exploration der zugehörigen Spielzustandsräume behandelt. Dabei wird vor allem der Grafikprozessor (GPGPU - general purpose graphics processing unit) als Co-Prozessor eingesetzt, um die Berechnungen zu beschleunigen. In diesem Rahmen wird auch gezeigt, wie Hash- bzw. Rangfunktionen basierend auf Binomial- (für Einpersonen-Spiele) und Multinomialkoeffizienten (für Mehrpersonen-Spiele) gebildet werden können, die eine effiziente Speicherung von Spielzuständen und ggf. auch Informationen zu diesen sowie eine effiziente Übertragung von Spielzustandsmengen an die GPGPU ermöglichen. Konkret werden die Techniken auf die Spiele "Englisches Solitär", "Frösche und Kröten" und "Mühle" angewendet.
Inhaltsverzeichnis
1 Einleitung
1.1 Motivation und Hintergrund
1.2 Aufbau der Arbeit
2 Grundlagen
2.1 Spiele und Spieltheorie
2.2 Theoretische Grundlagen zum Hashing
2.2.1 Vorüberlegungen
2.2.2 Minimale perfekte Hashfunktionen
2.3 GPU-Grundlagen
2.3.1 Entwicklung der Grafikkarten
2.3.2 Architektur moderner Grafikprozessoren
2.3.3 NVIDIA CUDA™
2.3.4 ATI Stream™ und OpenCL
2.4 Breitensuche mit GPU-Unterstützung
3 Das Einpersonenspiel „Englisches Solitär“
3.1 Hashfunktion für Spielzustände
3.2 Lösen des Spiels
3.3 Implementierung und Resultate
4 Das Einpersonenspiel „Frösche und Kröten“
4.1 Hashfunktion für Spielzustände
4.2 Lösen des Spiels
4.3 Implementierung und Resultate
5 Das Zweipersonenspiel „Mühle“
5.1 Hashfunktion für Spielzustände
5.2 Lösen des Spiels
5.2.1 Bewertung von Spielzuständen
5.2.2 Retrogerade Analyse für Zug- und Sprungphase
5.2.3 Implementierung und Resultate für Zug- und Sprungphase
5.2.4 Klassifizierung von Zuständen der Setzphase
5.2.5 Implementierung und Resultate für die Setzphase
5.3 Ein optimaler Spieler
6 Fazit
Zielsetzung und thematische Schwerpunkte
Die Arbeit befasst sich mit der effizienten Lösung kombinatorischer Ein- und Mehrpersonenspiele unter Ausnutzung der massiven Parallelität von Grafikprozessoren (GPUs), wobei Hashfunktionen als zentrales Mittel zur effizienten Speicherverwaltung der Spielzustandsräume eingesetzt werden.
- Grundlagen der Spieltheorie und kombinatorische Optimierung
- Architektur und Programmierung moderner Grafikprozessoren (insb. NVIDIA CUDA)
- Konstruktion minimaler perfekter Hashfunktionen zur Zustandsabbildung
- Implementierung von Breitensuche-Algorithmen auf der GPU
- Fallstudien zu den Spielen Englisches Solitär, Frösche und Kröten sowie Mühle
Auszug aus dem Buch
1.1 Motivation und Hintergrund
Seit wenigen Jahren existiert der Trend, die GPU (Grafikprozessor) nicht mehr ausschließlich für die Bilderzeugung und -verarbeitung zu verwenden, sondern auch als Co-Prozessor zur Unterstützung der CPU (Hauptprozessor). Im Falle eines diesbezüglich geeigneten Grafikprozessors sprechen wir auch von einer GPGPU („General Purpose Graphics Processing Unit“).
Dieser Trend lässt sich durch die besondere Entwicklung der GPU in der jüngsten Vergangenheit erklären. Der auf dem Markt für Grafikkarten anhaltend starke Wettbewerbsdruck der letzten 10 bis 15 Jahre hat dazu geführt, dass sich Grafikprozessoren zu stark parallelisierten Systemen mit mehreren Hundert Prozessorkernen entwickelt haben. Der Grund für diese Entwicklung ist, dass im Rahmen der Bildverarbeitung für viele verschiedene Bildpunkte bzw. Texturen oftmals dieselben Arbeiten durchzuführen sind, so dass ein entsprechend parallelisierter Grafikprozessor diese Aufgaben wesentlich schneller durchführen kann, als Prozessor, der diese Informationen sequentiell verarbeitet.
Während für CPUs mit zwei, vier oder acht Prozessorkernen der Begriff Mehrkern-Prozessoren (Multicore) verwendet wird, spricht man bei GPUs aufgrund der großen Zahl der Recheneinheiten von Vielkern-Prozessoren (Manycore). Moderne GPUs eignen sich hervorragend für die Anwendung des Paradigmas der parallelen Programmierung.
Zusammenfassung der Kapitel
1 Einleitung: Einführung in die Nutzung von Grafikprozessoren für kombinatorische Problemstellungen und den Aufbau der Arbeit.
2 Grundlagen: Vermittlung der spieltheoretischen Basis, der mathematischen Grundlagen für perfekte Hashfunktionen sowie der technischen GPU-Architektur und Schnittstellen.
3 Das Einpersonenspiel „Englisches Solitär“: Anwendung von Hashing und Breitensuche zur effizienten Lösung dieses klassischen Halma-Spiels auf der GPU.
4 Das Einpersonenspiel „Frösche und Kröten“: Untersuchung und Implementierung einer Lösung mittels spezialisierter Hashfunktionen für die Zustände dieses Spiels.
5 Das Zweipersonenspiel „Mühle“: Komplexere Lösung eines Mehrpersonenspiels inklusive Bewertung von Spielzuständen und retrogerader Analyse.
6 Fazit: Zusammenfassende Bewertung der erreichten Beschleunigungen durch Hash-basierte GPU-Lösungsansätze und Ausblick auf weiterführende Methoden.
Schlüsselwörter
GPU, GPGPU, CUDA, Hashing, perfekte Hashfunktionen, kombinatorische Spiele, Breitensuche, Englisches Solitär, Frösche und Kröten, Mühle, Parallelisierung, Zustandsgraph, Manycore, Spieltheorie, Speicherverwaltung
Häufig gestellte Fragen
Worum geht es in dieser Diplomarbeit grundsätzlich?
Die Arbeit untersucht, wie kombinatorische Brettspiele durch den Einsatz moderner Grafikprozessoren effizienter gelöst werden können, indem der Spielzustandsraum durch Hashfunktionen kompakt im Speicher verwaltet wird.
Welche zentralen Themenfelder werden abgedeckt?
Die zentralen Felder sind die parallele Programmierung auf GPUs (NVIDIA CUDA), die theoretische Informatik im Bereich Hashing (perfekte Hashfunktionen) und die algorithmische Spieltheorie.
Was ist das primäre Ziel der Forschung?
Das Ziel ist die signifikante Beschleunigung der Suche nach Lösungen für kombinatorische Spiele, um Zustandsräume zu bewältigen, die auf CPUs sequentiell nur sehr langsam oder gar nicht berechenbar wären.
Welche wissenschaftlichen Methoden werden angewendet?
Es werden mathematische Partitionierungsverfahren für Zustandsräume, Hashing-Verfahren mittels Binomial- und Multinomialkoeffizienten sowie Breitensuche-Algorithmen für parallele Architekturen eingesetzt.
Was wird im Hauptteil der Arbeit behandelt?
Der Hauptteil gliedert sich in drei Fallstudien: das Einpersonenspiel Englisches Solitär, das Einpersonenspiel Frösche und Kröten sowie das anspruchsvolle Zweipersonenspiel Mühle.
Welche Keywords charakterisieren die Arbeit am besten?
GPU-Computing, perfekte Hashfunktionen, Zustandssuche, Parallelisierung und kombinatorische Optimierung.
Warum spielt die Wahl der Hashfunktion eine so wichtige Rolle?
Da der verfügbare Speicher auf einer Grafikkarte (VRAM) begrenzt ist, erlauben minimale perfekte Hashfunktionen eine äußerst speichereffiziente Verwaltung der Spielzustände.
Wie konnte das Spiel „Mühle“ effizient analysiert werden?
Durch eine Partitionierung des Zustandsraums in Abhängigkeit von den Stein-Farben (Multinomialkoeffizienten) und die Verwendung einer retrogeraden Analyse, um Gewinnzustände rückwärts zu berechnen.
Welchen Vorteil bietet die GPU gegenüber einer CPU für diese Aufgaben?
Die massive Anzahl an spezialisierten Recheneinheiten (Manycore-Architektur) ermöglicht es, Millionen von Spielzuständen parallel zu expandieren und zu verarbeiten, was zu einer Beschleunigung um Faktoren zwischen 13 und 18 führt.
- Citar trabajo
- Cengizhan Yücel (Autor), 2009, Lösung von Ein- und Mehrpersonenspielen auf der Grafikkarte mit perfekten Hashfunktionen, Múnich, GRIN Verlag, https://www.grin.com/document/231273
