Themenliste in der Reihenfolge der Vortragstermine:

aktuelle Methoden der künstlichen Intelligenz für Spiele (Michael Winkelmann)

Abstract: Die künstliche Intelligenz für Computerspiele soll das Verhalten und das Treffen von Entscheidungen von nicht-menschlichen Gegenspielern simulieren und so eine möglichst menschenähnliche Intelligenz vortäuschen. Die künstliche Intelligenz für Computerspiele hat eine lange Geschichte. Bereits 1951 wurden Programme geschrieben, die Schach und Dame simulieren konnten. Zehn Jahre später konnten diese Programme sogar fortgeschrittenere Spieler besiegen. Seit 1997 sind die Algorithmen soweit fortgeschritten und die Rechenleistung von Computern so hoch, dass ein Mensch einem Computer beim Schach immer unterlegen ist. Bei anderen Brettspielen wie Go oder Backgammon oder bei Nicht-Spieler-Charakteren in aktuellen Videospielen ist die Forschung aber noch nicht soweit. So unterschiedlich und schwierig zu klassifizieren wie die Spiele selbst, sind es auch die für die Spiele-KI benutzten Techniken. So benötigen Brettspiele andere Verfahren als Ego-Shooter oder Echtzeit-Strategiespiele. Die wichtigsten Techniken sind unter anderem das Analysieren von Spielzügen (z.B. Alpha-Beta-Suche), die Wegfindung (z.B. Pathfinding) und das Reagieren und Anpassen auf Veränderungen der Umwelt (z.B. Multi-Agenten-Systeme). Es gibt auch viele Techniken, die von der Natur inspiert sind (z.B. Ant Colonies, neuronale Netze und genetische Algorithmen). Besonders hier wurde in den letzten Jahren viel Forschungsarbeit geleistet. Moderne Computerspiele kombinieren dabei immer mehrere dieser Verfahren, umso ein möglichst realistisches Interagieren der computergesteuerten Charaktere zu gewährleisten. Jedoch ist das Ende der Möglichkeiten noch lange nicht erreicht. Insbesondere aus dem Bereich des maschinellen Lernens und der Mustererkennung werden viele Erkenntnisse noch gar nicht in aktuellen kommerziellen Computerspiele eingesetzt. Mit steigender Rechenleistung wären in Zukunft Spiele denkbar, in denen die computergesteuerten Charaktere selbständig Problemlösungen entwickeln, Wissen lernen und anwenden und Gesichter und Sprache erkennen können. Damit würde die Vision einer starken KI der Wirklichkeit ein Stück näher kommen.

Alpha-Beta-Suche (Nils Lomnitz und Sebastian Menski)

Abstract: Die Alpha-Beta-Suche ist ein Algorithmus aus der Spieltheorie. Erfüllen Spiele bestimmte Voraussetzungen, z.B. falls sie nicht vom Zufall abhängig (Würfelspiele) sind oder nur unvollständige Informationen über die möglichen Züge des Gegners bieten (Kartenspiele), ist die Alpha-Beta-Suche eine effektive Methode, um für diese Spiele eine optimale Spielstrategie zu erstellen. Hierzu wird ein Spielbaum als partiell geordnete Menge der möglichen Züge von Spieler und Gegenspieler dargestellt. Anhand von Heuristiken lassen sich Aussagen über die Stärke von Zügen treffen. Die Fähigkeit eines Programms, geeignete Heuristiken für jede Spielsituation zu berechnen, ist eine der schwierigsten Teile der Implementierung und entscheidet maßgeblich über die Stärke der KI. Aufgrund des exponentiellen Wachstums mit der Suchtiefe gibt es zahlreiche Optimierungsverfahren für die Alpha-Beta-Suche. Es wird gezeigt, dass sich mit diesen Optimierungen bemerkenswerte Verbesserungen bezüglich der Effizienz und damit der Laufzeit erzielen lassen.

Monte Carlo Tree Search (Andrej Finsterbusch und Mario Rothe)

Abstract: During the last years, many games like chess, checkers and othello have been mastered by computer programs. The classical approach using alpha-beta-search is working well for these games. Other games, like go, which have a much higher branching factor seemed not to be playable by computer programs on a human master level. After the introduction of Monte Carlo Tree Search into the genre and many improvements to this algorithm like UCT, offline knowledge and others, computer programs became more powerful and recently achieved professional levels. In this paper we will show the approach of Monte Carlo Tree Search as well as improvements and extensions to it and give some results achieved by programs using this technique.

Ant Colony Systems (Kristian Eckstein und Markus Lampe)

Abstract: ACO bedient sich dem Phänomen der Schwarmintelligenz und insbesondere der Intelligenz des Ameisen Kollektivs. Ameisen leben in so genannten Kolonien, die ihrem Bedarf entsprechend ausgebaut sind. Um überleben zu können muss die Kolonie organisiert und strukturiert sein. Jedoch besitzen Ameisen nur sehr beschränkte kognitive Fähigkeiten und keine direkte Kommunikationsmöglichkeit durch Sprache, Augenkontakt oder Tastsinn. Stattdessen kommunizieren sie indirekt über Pheromone miteinander. Dabei handelt es sich um chemische Substanzen, die Ameisen zu bestimmten Aktivitäten veranlassen oder diese beeinflussen, wenn diese wahrgenommen werden. Trotzdem zeigt sich bei der Futtersuche eine erstaunliche Effizienz der Ameisen, da diese oft optimale Wege zum Futter finden. Dieses Verhalten veranlasste Marco Dorigo zur Entwicklung des Ant Systems (AS), welches das Verhalten der Ameisen nachahmt um auf Graphen basierende kombinatorische Optimierungsprobleme lösen zu können. Das AS wurde dann später zum Ant Colony System (ACS) weiterentwickelt und ist heute mit vielen weiteren Anpassungen unter dem Sammelbegriff ACO bekannt. Dabei werden die Eigenschaften von Metaheuristiken und lokaler Suche mit Multi-Agent Systemen im ACO vereinigt. In unserem Vortrag befassen Wir uns mit der Entstehung, Funktionsweise und den Eigenschaften der ACO und zeigen anschließend allgemeine Anwendungsmöglichkeiten auf TSP, Swarm Bots, Military Path Finding und dabei die besondere Eignung für dynamische Probleme. Anschließend zeigen Wir verschiedene Ansätze, um ACO auch in Spielen zu nutzen. Dabei geht es von der einfachen KI-Wegfindung in Atari Combat, über die Visualisierung von viel genutzten Wegen in Siedler IV, bis hin zur Nutzung von ACO zur Findung einer Sieg-Strategie in XXO und Schach. Beim Letzteren wird ACO genutzt um den Suchraum mit allen möglichen Spielzuständen möglichst effizient abzusuchen und so möglichst schnell eine gute Sieg-Strategie zu finden.

Proof Number Search (Helmar und Heiko)

Abstract: Proof-Number-Search ist ein Algorithmus zur Bestimmung effektiver Spielzüge in einem Spielbaum, der auf Boolscher Logik aufbaut. Mit Hilfe von Tiefensuche und Heuristiken wird der aktuell "beste" Spielknoten gefunden und expandiert und somit der Spielbaum weiter aufgespannt. Dabei gibt die Proof-Number eines Spielknoten immer an, wieviele Schritte noch nötig sind, um den Spielbaum bzw. Teilbaum zu beweisen, also eine Reihe von Spielzügen zu finden, die zum Sieg führen. Eingesetzt wird diese Suche meist in 2 Spieler Partien.

Path Finding (Matthias Dunkel und Jan Jantzen)

Abstract: Eine der größten Herausvorderungen beim Design einer Künstlichen Intelligenz in Computerspielen ist eine realistische Agenetenbewegung. Strategien zur Wegfindung bilden meistens den Kern eines Bewegungssystems. Der Vortrag befasst sich mit verschiedenen Methoden zur Wegfindung, die in modernen Computerspielen Anwendung finden. Dabei werden verschieden Möglichkeiten zur Anpassung einer virtuellen Welt an die Wegfindung, traditionelle auf einem Graphenansatz beruhende Algorithmen, deren Mängel und einige Modernere Ansätze vorgestellt.

Neuronale Netze (René Gutschmidt und Florian Brinkmeyer)

Abstract: Im Rahmen meines Vortrags stelle ich wesentliche theoretische Grundlagen im Zusammenhang mit künstlichen neuronalen Netzen dar. Diese werden als ein Gebilde aus in bestimmter Weise miteinander gekoppelten künstlichen Neuronen beschrieben, wobei sowohl die Art der Vernetzung als auch die Funktionsweise der künstlichen Neuronen, deren Verhalten durch einfache mathematische Funktionen beschrieben werden kann, näher thematisiert wird. Des Weiteren wird auf verschiedene Methoden zum Training neuronaler Netze eingegangen, wobei insbesondere Verfahren erläutert werden, die auf einer Modifikation der Verbindungsgewichte beruhen. Ich werde deutlich machen, inwiefern der Einsatzzweck Einschränkungen bezüglich den anwendbaren Lernmethoden mit sich bringt. Darüber hinaus werden verschiedene Typen neuronaler Netze beschrieben und die jeweiligen Vor- und Nachteile einer bestimmten Architektur erläutert. Zum Schluss wird kurz auf die Anwendungsbereiche für neuronale Netze eingegangen, wobei deren Einsatz in Computerspielen das Thema des nächsten Vortrags ist.

Neuronale Netze sind für die KI für Spiele bei Backgammon sehr erfolgreich, bei anderen Spielen, wie z.B. Schach oder Dame, aber weniger erfolgreich. Am Beispiel von Backgammon wird die Verwendung Neuronaler Netze für die KI in Spielen für die beiden gängigsten Lernstrategien Temporal Difference und Co-Evolution erklärt. Auch die Gründe, warum Neuronale Netze bei Backgammon so gut funktionieren und bei anderen Spielen nicht, werden erklärt.

Game Theory and Multiagent Systems (Thomas Popp, Alexander Blödorn und Richard Karuseit)

Abstract: Im Folgenden werden Multiagentensysteme und die Spieltheorie skizziert. Zu Beginn werden Multiagenten vorgestellt, deren historische Entwicklung und ein Beispiel, welches mit Hilfe der Multiagentensysteme zu simulieren wäre. Im Anschluss werden die Eigenschaften der Agenten erklärt und die Möglichkeiten beschrieben, die diesen zur Kommunikation zur Verfügung stehen. Anschließend wird eine Übersicht über die verschiedenen Agententypen geboten. Die Spieltheorie, ihre geschichtliche Entwicklung und ihre Anwendungsgebiete werden umrissen und einige Grundbegriffe der Spieltheorie erklärt. Die verschiedenen Darstellungsformen der Spieltheorie und die möglichen Spieltypen werden an Beispielen illutriert und anschließend tiefer in die Spieltheorie und die entsprechenden Strategien eingetaucht. Es wird auf den Begriff der Dominanz von Strategien, den Unterschied zwischen reinen und gemischten Strategien, sowie auf Nash-Gleichgewichte und Algorithmen zu deren Ermittlung – in reinen und in gemischten Strategien - eingegangen. So zum Beispiel auf den Minimax-Algorithmus.

Opponent Modelling (Oliver Matheis, Holger Jost und Alexandra Strekalova)

Abstract: Opponent Modeling ist ein Ansatz aus dem Bereich der künstlichen Intelligenz, der sich mit Simulation des gegnerischen Verhaltens in Spielen beschäftigt. Bei Spielen, für die dem Agenten keine vollständigen Informationen vorliegen, ist es wichtig, ein Modell des Gegenspielers zu erzeugen und seine Schwächen auszunutzen. Ziel dieses Vortrags ist, den Begriff des Opponent Modeling zu erklären, sowie verschiedene Herangehensweisen, Methoden und Anwendungsbeispiele zu präsentieren. Als Beispiel für mögliche Methoden werden statistischer Ansatz, Neuronale Netze und Naives Bayes näher betrachtet. Diese Methoden werden für Simulation des Gegners in RoShambo?, Poker und Roboterfußball eingesetzt.

Rational Learning (Bayesian Learning) (Franziska John, Stephan Juchatz und Florian Seele)

Abstract: Lernen nach Bayes kann grob als die Änderung des Wissen auf Basis von Erfahrung beschrieben werden. Der Bayes'sche Ansatz kombiniert eine vorherige subjektive Meinung mit neuen Informationen um eine verbesserte Meinung zu entwickeln. Dieser Vorgang kann beliebig oft wiederholt werden, wobei die überarbeitete Meinung die vorherige wird, sobald neue Daten hinzukommen. Die entscheidende Eigenschaft von Bayes'schen Methoden ist die Benutzung von Wahrscheinlickeiten um unbekannte Parameter zu bestimmen. Dieses Prinzip kann ebenfalls auf Spiele angewendet werden. Denn auch hier kann man die Wahrscheinlichkeiten nutzen um ein möglichst gutes Spielergebnis zu erreichen. Wenn nun jeder Spieler immer seinen besten Zug wählt, kann sich ein Gleichgewicht zwischen den Zügen entwickeln, so dass kein Spieler einen Vorteil erhält, sollte er von seiner Strategie abweichen. Dieses Gleichgewicht nennt man Nash-Gleichgewicht.

Datenstrukturen (Tobias Moebert und Stefan Keil)

Abstract: Datenstrukturen sind das essentielle Grundgerüst eines jeden KI-Algorithmus. Die große Zahl an Suchanfragen ist ohne eine effiziente Datenstruktur nicht in annehmbarer Zeit durchführbar. Dabei ist umso bemerkenswerter, dass diese Strukturen in ihrer Grundform schon in den 70er Jahren entwickelt wurden und noch bis heute in vielen Algorithmen Verwendung finden. In dieser Arbeit sollen verschiedene Datenstrukturen, namentlich Boardrepresentationen, Hash-Tabellen und Eröffnungsbücher in ihrer Funktionsweise vorgestellt und ihre Vor- und Nachteile hinsichtlich der Anwendung in Spielen mit künstlicher Intelligenz beleuchtet werden.

General Game Playing (Henning Pundrich)

Abstract: Seit Anbeginn der Zivilisation haben Brettspiele die intellektuellen Fähigkeiten der Menschen herausgefordert. Die Art von natürlicher Intelligenz, die in diesen Spielen gefordert wird, ist im Gegensatz zu physischen Spielen, wie Ballsportarten, einfach formal zu beschreiben. Sie stellt so ein attraktives Studienobjekt für das Forschungsgebiet der künstlichen Intelligenz dar [Russel und Norvig 2004]. Im Folgenden wird die Entwicklung von den ersten „künstlichen Spielern“ (sog. Spielagenten) bis hin zum jungen Forschungszweig des General Game Playing (universelle Spielprogramme) aufgezeigt. Der Vortrag befasst sich mit der Entwicklung des General Game Playing. Hier werden Methoden zur Verwirklichung eines solchen Players vorgestellt und der Grundaufbau eines Players beschrieben. Des Weiteren erfolgt ein kurzer Einblick in die Weltmeisterschaft des GGP und die Verwendung solcher Verfahren außerhalb des Spielesektors.