Künstliche Intelligenz

Dominik Bortis, Don Frick, Thomas Killer

Word Dokument

 

Einführung

Allgemeines:

Künstliche Intelligenz, oder auch einfach KI genannt, ist eine Kombination von Wissenschaft, Physiologie und Philosophie. Die Künstliche Intelligenz ist ein sehr breites Thema, dass aus vielen verschiedenen Teilgebieten besteht. Doch die Gemeinsamkeit, welche die einzelnen Teile verbindet, ist die Erschaffung der Maschine, die denken kann. Aber Intelligenz ist ein Begriff der für sehr viel stehen kann. Deshalb geben wir hier ein paar Definitionen und versuchen dann daraus zu schliessen, was KI ist und was die Maschine können muss um intelligent zu sein.

Definitionen:

Unten stehen acht Definitionen, welche die KI beschreiben, aber nicht alle das Gleiche aussagen. Die Definitionen in der oberen Hälfte befassen sich mit dem Denkprozess und dem Denken allgemein, während es sich bei den Unteren um das Verhalten handelt.

Ebenfalls sind die linke und rechte Seite von einander verschieden. Die linke Seite soll denken und handeln wie der Mensch, wobei die rechte Seite eher das Ideal der Intelligenz darstellt, nämlich die Rationalität.

 

"The exciting new effort to make computers think… machines with minds, in the full and literal sense"

(Haugeland, 1985)

"The automation of activities that we associate with human thinking, activities such as decision-making, problem solving, learning…"

(Bellman1978)

 

"The study of mental faculties through the use of computational models"

(Charniak and McDermott, 1985)

"The study of the computations that make it possible to perceive, reason and act"

(Winston, 1992)

 

 

 

 

"The art of creating machines that perform functions that require intelligence when performed by people"

(Kurzweil, 1990)

"The study of how to make computers do things at which, at the moment, people are better"

(Rich and Knight, 1991)

"A field of study that seeks to explain and emulate intelligent behavior in terms of computational processes"

(Schalkoff, 1990)

"The branch of computer science that is concerned with the automation of intelligent behavior"

(Luger and Stubblefield, 1993)

 

Diese acht Definitionen geben uns also vier verschiedene mögliche Auffassungen der Künstlichen Intelligenz:

 

Systeme, die menschlich denken

 

Systeme, die rational denken

 

Systeme, die menschlich handeln

 

Systeme, die rational handeln

 

Doch was heisst das eigentlich?

Wir wollen hier noch ein bisschen tiefer auf die verschiedenen Begriffe eingehen.

Menschlich handeln : Der Turing Test:

Der Turing Test, entwickelt 1950 von Alan Turing, soll entscheiden ob eine Maschine intelligent ist oder nicht. Sein Gedanke war: wenn der Mensch nicht mehr unterscheiden kann ob er mit einem Menschen oder einer Maschine spricht, so ist die Maschine intelligent.

Also die Maschine ist intelligent, falls sie sich verhält wie ein Mensch.

Damit der Computer den Test bestehen kann, muss er folgende Eigenschaften besitzen:

Sinnvolle Satze und korrekte Grammatik in Englisch oder sonst einer Sprache

Schon gespeicherte Informationen und Speicherung während dem Prozess

Die gespeicherten Informationen brauchen um Fragen zu beantworten und Schlussfolgerungen zu ziehen.

Der Turing Test verlangt jedoch keine physikalischen Interaktionen zwischen dem Benutzer und dem Computer, weil die Physik zur Intelligenz nichts beiträgt.

Menschlich denken:

Wenn wir sagen, dass ein gegebenes Programm denkt wie ein Mensch, dann müssen wir zuerst das Denken des Menschen, oder besser die Art des Denkens

herausfinden. Dies können wir indem wir versuchen unsere Gedanken wahrzunehmen und schauen, wie wir zu diesen Gedanken gelangen.

Eine andere Möglichkeit dies herauszufinden, wären psychologische Tests.

Also ein Computer denkt menschlich, wenn nicht nur der In- und Output gleich sind wie beim Menschen, sondern auch der Prozess und die Art des Denkens.

Newell und Simon versuchten, mit dem von ihnen entwickelten Programm The General Problem Solver nicht unbedingt die richtige Lösung zu finden, sondern sie wollten ein Programm, das auf die gleichen Weise denkt wie der Mensch.

Rational denken:

Der griechische Philosoph Aristoteles war einer der Ersten, der sich mit dem „richtigen Denken" befasste. Sein bekannter Syllogismus, der aus korrekten Premissen korrekte Schlussfolgerung ergibt, stellt ein Beispiel des rationalen Denkens dar. Diese Art zu denken basiert auf der Logik. Zum Beispiel:

Sokrates ist ein Mensch.

Alle Menschen sind sterblich.

Sokrates ist sterblich.

 

Rational handeln:

Das rationale Handeln kann man genau gleich verstehen wie das rationale Denken.

Man versucht aus einer bestimmten Lage oder Ausgangssituation durch logischen Aufbau des Handelns und Schlussfolgern dem Ziel Schritt für Schritt näher zu kommen.

Geschichte

Die Zeit des Computers:

Durch die Erfindung des elektronischen Computers, entwickelt in den USA und in Deutschland, wurde jeder Aspekt von Speicherung und Verarbeitung von Informationen revolutioniert.

Der erste Computer benötigte grosse separate Räume, voll von Drähten, die klimatisiert werden mussten.

1949 erleichterte der stored programm computer das Implementieren von Programmen und die Fortschritte in der Computertheorie führten zur Informatik und dadurch zum Beginn der Künstlichen Intelligenz.

Der Beginn der Künstlichen Intelligenz:

Obwohl der Computer die benötigten Technologien für die Verwirklichung der Künstlichen Intelligenz erst in den frühen Fünfzigern ermöglichte, wurden schon vorher Überlegungen an der Verbindung zwischen dem menschlichen Gehirn beziehungsweise der menschlichen Intelligenz und der Maschine angestellt.

Norbert Wiener war einer der ersten Amerikaner, die am Prinzip der Rückkopplungstheorie arbeiteten.

Das vertrauteste Beispiel ist das des Thermostats.

Der Thermostat regelt die Temperatur der Umgebung, indem er die momentane Temperatur misst und je nachdem, ob die Temperatur über oder unter dem Sollwert liegt die Heizung zu- oder aufdreht.

Was war so interessant an Wieners Entdeckung?

Er zeigte, dass das intelligente Verhalten auf dem Prinzip der Rückkopplung basiert und dies wiederum von Computern simuliert werden konnte.

1955 entwickelten Newell und Simon The Logic Theorist, das von vielen als erstes Programm der Künstlichen Intelligenz betrachtet wurde. Das Programm stellte das Problem in einem Baum dar und verfolgte dann den richtigen Ast der zur Lösung des Problems führte.

John McCarthy, der als Vater der Künstlichen Intelligenz gilt, organisierte 1956 die Dartmouth Konferenz in Vermont.

Es wurden Experten und Spezialisten der KI eingeladen um sich Gedanken zur intelligenten Maschine und der KI zu machen.

Der Begriff der Künstlichen Intelligenz wurde hier erstmals verwendet.

Die Dartmouth Konferenz war eigentlich kein spezieller Erfolg, doch sie brachte endlich die Gründer der KI zusammen und legte so den Grundstein der KI.

 

Wissenserweiterung:

In den nächsten 7 Jahren nach der Konferenz begann die KI aufzublühen.

Obwohl das Gebiet der KI noch nicht richtig definiert war, kamen schon erste Ideen auf. Im MIT und am Carnegie Mellon entwickelten sich erste KI-Centers, an denen Programmen zur effizienten Problemlösung entwickelt wurden indem die Suche über den Baum (The Logic Theorist) verbessert wurde.

1957 wurde der General Problem Solver ,entwickelt von Newell und Simon, erstmals getestet. Das Programm arbeitete nach dem von Wiener entwickelten Prinzip der Rückkopplung. (Wie oben erwähnt: menschlich denken)

Während immer mehr Programme entwickelt wurden, war McCarthy an einem eigenen Programm beschäftigt.

1958 veröffentlichte er seine neue Software, nämlich die Sprache LISP, die noch heute verwendet wird.

1963 erhielt das MIT 2.2 Millionen Dollar vom Departement für Verteidigung der USA um den "Vorsprung" in der Technologie vor der Sowjetunion zu sichern.

Vielzahl von Programme:

In den folgenden Jahren der Entwicklung entstanden viele verschiedene Programme. In den späten 60’ern erschienen, um nur einige zu nennen, z.B. ein Mathematikprogramm STUDENT, das algebraische Probleme löst, ein Sprachprogramm SIR, welches einfache englische Sätze bilden kann oder ELIAS, ein Programm das wie ein Psychiater versucht ein Gespräch aufzubauen .

Ein weiterer Fortschritt in den 70’ern war die Erfindung vom Expert-System. Das Expert-System berechnet die Wahrscheinlichkeit einer Lösung unter bestimmten Voraussetzungen.

 

 

Zum Beispiel:

Das System kann den Marktverlauf auf die nächsten 10 Jahre berechnen, ermöglicht es dem Mediziner eine Diagnose zu erstellen oder verrät den Minenarbeitern an welchem Ort die Minerale vergraben sind.

Während den 80’ern nahm die Entwicklung der KI immer stärker zu. 1986 wurden in den USA Hard- und Software basierend auf Künstlicher Intelligenz im Wert von 425 Millionen Dollar verkauft.

Vor allem grosse Firmen, wie DuPont, General Motors und Boeing waren daran interessiert.

Der Übergang vom Labor zum täglichen Leben:

Der Einfluss der Computertechnologie, inklusive KI, war mächtig spürbar. Früher wurden die Computers nur in Labors für Forschungszwecke verwendet. Doch durch den Personal Computer verbreitete sich die Technologie auch bei den normalen Bürgern.

Die KI wurde immer mehr verbreitet, auch in privaten Firmen. Diese 150 Firmen arbeiteten mit 700 Forschern an der KI und investierten 1 Billion Dollar in interne KI Groups.

Die 80’er waren jedoch für die KI-Industrie nicht besonders gut. 1986-87 nahm das Interesse an der KI ab und die Industrie verlor fast bis zu einer halben Billion Dollar.

Eine andere Enttäuschung war das Projekt smart truck, das vom amerikanischen Verteidigungsministerium finanziert wurde. Das Ziel des Projektes war es einen Roboter zu entwickeln, der Kriege simulieren konnte .

1989 wurde das Projekt vom Pentagon nicht mehr weiter verfolgt.

Nach dieser Entmutigung kam langsam wieder Interesse auf. In Japan wurden neue Technologien entwickelt.

Z.B. Fuzzy logic, ein Programm, das fähig ist unter gewissen Bedingungen Entscheidungen zu treffen.

Aber auch neurale Netzwerke wurden wieder interessant um die Künstliche Intelligenz zu erreichen.

Test der KI:

Das Militär setzte z. B. Hardware basierend auf KI im Golfkrieg ein (Raketensysteme).

Zudem konnte die KI auch in die Haushalte vordringen (Stimmenerkennung, Camcorder und vor allem Spiele).

 

 

PPS Sommersemester 2001: „Theorie und virtual reality"

 

Darf ich vorstellen, das Hamachi:

Dieses Java-Applet ist eine Tamagotchi-Variante. Im Gegensatz zu ihren berühmten Geschwistern ist hier jedoch ein Hamster das zu umsorgende Objekt. Das Handling gestaltet sich recht simpel:

Auswahl Zeit ausführen

 

Was ist ein Tamagotchi?

Tamagotchi ist ein sogenanntes "virtual reality creature". Es wurde ende 1996 in Japan auf den Markt gebracht. Mehrere Varianten sind seither produziert worden. Wer sich speziell dafür interessiert kann sich auf der schweizer Tamagotchi-Page unter http://www.tamagotchi.ch/ mit Informationen versorgen.

 

Was bedeutet eigentlich Tamagotchi?

Der Name kommt aus dem Japanischen. „Tamago" bedeutet soviel wie „Ei". Tamagotchi setzt sich aus „Tamago" und „watch" (=> Verkleinerungsform „watchi") zusammen. Dies ist etwa mit „Tamago-Uhr" zu übersetzen.

 

Lebt ein Tamagotchi?

Es handelt sich bei diesem Spielzeug um eine Simulation eines Tieres. Es ist jedoch keine Form von virtuellem Leben oder gar künstlicher Intelligenz, wie die Begriffe heut zu Tage benutzt werden. Jedoch wird damit auf eindrückliche Weise gezeigt, wie schnell wir uns darauf einlassen, einem Programm Intelligenz oder Lebenszüge abzukaufen.

 

Wie funktioniert denn nun ein Tamagotchi?

Ich habe die Funktionsweise der Tamagotchi-Variante „Hamachi" („Hamster"-„watchi") analysiert. In wie weit sie dem tatsächlichen orginalen Tamagotchi entspricht, kann ich nicht genau sagen, da der Tamagotchi Source-code nicht freigegeben ist.

Das Hamatchi basiert auf nicht, wie man vielleicht meinen könnte, auf Zufallselementen. Durch die mit der Zeit zunehmenden Komplexität ist es schlichtweg unmöglich alle Variablen zu überblicken. Das hat einen Eindruck von Zufälligkeit oder sogar Leben, bzw. Intelligenz zur Folge.

Hamachi

Wie genau dieses simulierte Lebewesen funktioniert will ich im Folgenden Zeigen:

Die Hauptklasse ist „Hamachi.class" sie managed so zu sagen die gesammten Aktionen. Das Tierchen orientiert sich an der Uhrzeit. Nach einer gewissen Zeit verspürt es Hunger, will spielen, will schlafen, etc. Wird ihm zur richtigen Zeit gegeben, wonach es verlangt (innerhalb 200-4000ms), so steigt je nach dem die Lebenserwartung. Doch sie ist beschränkt auf ein Maximum (MaxAge = 24 /*months*/).

Das folgende Diagramm ist nicht die vollständige Darstellung des Programms. Einige Methoden habe ich aus Übersichtsgründen zusammengefasst. Wen der exakte Aufbau interessiert, kann sich den Source-Code unter http://nmsf.sscc.ru/neuro/g_help.html downloaden.

 

Programmaufbau:





handleDeath

 



 

 

 

 

 

Links:

Infos über Tamagotchi:

http://www.wakuwaku.ne.jp/jun/tama/index2.html

http://www.tamagotchi.ch/

Software zum Thema (unteranderem Hamatchi Source-Code):

http://nmsf.sscc.ru/neuro/g_help.html

Online Tamagotchi (Shockwave-plugin notwendig):

http://www.jitterbug.com/gvt/index.shtml

Tamagotchi Paodie:

http://www.gothic.net/~luvcraft/tamagothi/tamagothi.html

 

Andere Anwendungsgebiete:

Die Künstliche Intelligenz in Spielen hat, als Untergebiet der KI-Forschung im Allgemeinen, viele verschiedene Anwendungsgebiete und stark verwandte Forschungsbereiche. Obwohl die meisten Spielprogramme sich nicht mit echter „Intelligenz" abgeben, sondern nur den Schein wahren wollen, gibt es doch einige Projekte die flexibel genug sind um in mehreren Gebieten eingesetzt zu werden.

Viele Computerspiele enthalten Simulationen von komplexen Gegebenheiten. Eines der bekanntesten Beispiele dazu ist wohl die Sim- Reihe von Maxis. Diese Spiele simulieren auf einer ernstzunehmenden Ebene ökologische, ökonomische und soziale Zustände und sind professionellen Simulationsprogrammen, wie sie z.B. in Wall Street eingesetzt werden, nicht unähnlich.

Einige der neueren Simulationen wie The Sims und Creatures, die sich auf eine kleinere Ebene konzentrieren, sind eng mit dem Thema „Artificial Life" verbunden. Forschung in diesem Gebiet beschäftigt sich damit, grundlegende Eigenschaften von Lebewesen in künstlichen Systemen nachzuahmen. Dies kann in chemischen, mechanischen oder auch elektronischen Medien geschehen; Computerprogramme haben aber in diesem Gebiet eine besonders lange und faszinierende Geschichte. Von Programmen wie The Game of Life und Tierra bis zu den oben erwähnten Neuerscheinungen ist alles zu haben.

Ein eng verwandtes Forschungsgebiet ist natürlich die Robotik, da sich im Spieldesign sehr ähnliche Aufgaben stellen wie beim Entwurf einer möglichst autonomen und eventuell sogar lernfähigen Maschine. Die Entwickler von Creatures haben zum Beispiel mit dem Ministry of Defence (UK) zusammengearbeitet, um ein Steuerungssystem für unbemannte Flugzeuge zu entwickeln. Viele Methoden der Spielprogrammierung können direkt auf die Programmierung eines Roboters übertragen werden, was zu interessanten Überschneidungen geführt hat: MindRover von CogniToy erlaubt es dem Spieler, auf dem Computer einen Roboter zu programmieren und anschliessend in einer virtuellen Umgebung zu testen.

Genetische Algorithmen, Neuronale Netze und Lernfähigkeit:

Eines der höchsten Ziele der KI-Entwicklung ist sicher die Erschaffung eines lernfähigen Programms. Neuronale Netze sind wohl das beste Mittel dazu und befinden sich heutzutage in aller Munde, aber viele haben zu ihrem Leidwesen herausgefunden, dass man sie nicht mit gleichbleibendem Erfolg auf beliebige Probleme anwenden kann. Die Entwickling von KI in Spielen gehört, wie man nun weiss, zu den weniger geeigneten Anwendungen.

Es ist natürlich möglich, Programme mit Spielbäumen (s.u.) mit neuronalen Netzen zu trainieren; aber sogar in diesen Fällen erweist es sich als vorteilhafter, die altbewährten Algorithmen einzusetzen und deren Parameter mit den bekannten Methoden festzulegen. Wenn ein Spiel aber nicht mittels eines Spielbaumes analysiert werden kann, wird der Einsatz von neuronalen Netzen extrem schwierig; da die meisten Spielsysteme keine Ähnlichkeit zu schon bekannten Systemen haben, hat man keinen Zugriff auf Musterspiele oder bekannte Strategien, mit denen man das Netz trainieren könnte. Andererseits entwickeln Netze, die nur gegen sich selbst spielen, meistens kritische Schwächen gegen Strategien die im Verlauf des Trainings nie auftauchen.

Schliesslich muss noch erwähnt werden, dass neuronale Netze ziemlich schwierig einzusetzen sind und viel Rechenzeit brauchen, wenn man sie korrekt ausnutzen will. Einige Entwickler haben eine Kombination von neuronalen und herkömmlichen Methoden benutzt, aber bis jetzt ist es den wenigsten gelungen ein grösseres Projekt auf die Beine zu bringen, das mit Netzen arbeitet. In den letzten Jahren haben sich die meisten Programmierer entschieden sich mit den herkömmlichen Methoden zufriedenzugeben, da diese viel einfacher sind und den heutigen Anforderungen immer noch genügen. Es gibt natürlich Ausnahmen: Spiele wie Creatures setzen mit grossem Erfolg genetische Algorithmen ein. Artificial Life - Techniken werden hingegen häufiger benutzt; Zielorientierte Agenten und Gruppenverhalten (s.u.) tauchen inzwischen in vielen Spielen auf und zeigen verblüffend naturnahes Verhalten.

Programmierpraxis:

Wie sieht nun die Arbeit eines Programmierers aus, der die künstliche Intelligenz in einem Spiel implementieren muss? Wir werden den Gedankenprozess anhand eines wichtigen Beispiels erläutern und dabei einige der wichtigsten Probleme betrachten, die sich beim Schreiben eines solchen Programms stellen.

Wie bereits erwähnt wurde, benutzen praktisch keine Spiele die heutzutage geschrieben werden neuronale Netze oder genetische Algorithmen, und nur die wenigsten haben Eigenschaften, die man mit „Artificial Life" vergleichen kann. In den meisten Fälle reichen herkömmliche Finite State Machines vollständig aus, um das Verhalten von Einheiten innerhalb einer Spielwelt zu modellieren. So einfach ihr Konzept auch sein mag, die Möglichkeiten von FSMs sind noch lange nicht ausgeschöpft worden, und man kann sie mit etwas Arbeit zu erstaunlichen Resultaten bewegen.

Ein paar häufig benutzte Techniken seien hier nur beiläufig erwähnt, da sie mit dem aktuellen Thema recht wenig zu tun haben; In vielen Fällen werden sogenannte Skripts eingesetzt, eine genau vorgeplante Abfolge von Ereignissen, die von einem bestimmten Trigger ausgelöst werden. Oft kommt es auch vor, dass das Programm ohne das Wissen des Spielers die Regeln des Spiels bricht (z.B. eine Einheit augenblicklich von einem Ort zu einem anderen bewegt), um den Anschein von Künstlicher Intelligenz zu erzeugen. Diese Methoden sind sehr einfach einzusetzen und können grossen Eindruck machen, sind aber von der Implementierung her nicht besonders interessant.

Zunächst eine Liste von grundlegenden Stichworten:

Ein Agent ist eine Einheit in der Spielwelt die Eigenschaften besitzt, die nicht direkt von der Aussenwelt gesteuert werden; sie kann also auf unterschiedliche Weisen auf verschiedene Ereignisse oder Zustände reagieren. Der Avatar eines Menschlichen Spielers in der Welt ist auch ein Agent!

Simple Reflex Agents sind im Grunde genommen Finite State Machines, die also auf jede Eingabe, verbunden mit ihrem inneren Zustand, eine vorgegebene Reaktion haben; diese kann unter Umständen auch einfach „keine Reaktion" sein. Ein solcher Agent sollte einen Grundzustand haben, also einen Zustand in dem er verbleibt bis der erste Stimulus eintrifft. Viele dieser FSMs setzen heutzutage Fuzzy Logic ein, eine Methode die es ihnen erlaubt, die Übergänge zwischen zwei Zuständen zu sehen; man nennt die Angehörigen dieser Untergruppe auch FuSMs (Fuzzy State Logic Machines). So kann eine Einheit, die im Kampf nur leicht verwundet wurde, ihre Aggressivität allmählich zurückstufen anstatt von einem Moment auf den nächsten die Flucht zu ergreifen.

Decision Trees (Entscheidungsbäume) können benutzt werden, um FSMs etwas zu vereinfachen; wenn Entscheidungen in Unterklassen (z.B. offensiv und defensiv) aufgeteilt werden, kann man etwas Rechenzeit sparen und Zufallselemente einführen, ohne dass der Agent anfängt komplett unrealistische Entscheidungen zu treffen.

Goal-Based Agents haben gegebene Ziele, die sie erreichen möchten. So will sich zum Beispiel ein solcher Agent vom Ort A nach B bewegen um dann dort eine bestimmte Aktion durchzuführe; ein Simple Reflex Agent wäre dazu nicht fähig. Die Ziele eines Goal-Based Agents können verschiedene Prioritäten haben.

Utility-Based Agents haben auch Ziele, geben sich aber unter Umständen mit einer Teillösung zufrieden. Wenn ein Ziel nicht erreichbar ist beschäftigen sie sich mit einem anderen, oder versuchen zumindest, ihre Situation zu verbessern. Dies verlangt natürlich, dass nicht nur zwischen „Erfolg" und „Misserfolg" unterschieden wird, sondern dass eine ganze Skala von Zwischenwerten eingeführt wird, und dass Aufgaben in Teilaufgaben unterteilt werden (e.g. Wenn das Ziel in Punkt B nicht erreichbar ist, gibt es einen Punkt C, der mich möglichst nahe zu B bringt?).

Wenn nun viele dieser Agenten kooperieren müssen, wird oft eine Hierarchie von Agenten eingeführt; auf der untersten Ebene befinden sich die einzelnen Agenten, meist FSMs, die im Spiel als Figuren sichtbar sind. Auf der nächsthöheren Ebene findet man unsichtbare strategische Agenten, die die Bewegungen von ganzen Gruppen von FSMs kontrollieren. Auf der Obersten Eben befindet sich schliesslich ein Agent, der den Überblick über die ganze Situation behält und die grossen Entscheidungen trifft. Auf diese Art und Weise kann man u.a. die Kommunikation zwischen befreundeten Agenten modellieren, ohne jedem Agenten einzeln Sprech- und Aufnahmefähigkeiten zu verpassen.

Eine Alternative zu den obigen Methoden sind die Spielbäume. Diese lassen sich allerdings nur in Spielen einsetzten die nicht vom Zufall abhängig sind, die endlich viele Zugmöglichkeiten bieten, in denen beide Spieler jederzeit die ganze Situation überblicken können und die eindeutige Gewinnsituationen besitzen. Die Wurzel eines solchen Spielbaums steht für die aktuelle Situation; der Baum wird bis zu einer vorgegebenen Tiefe durchlaufen. Die untersten Knoten werden mittels heuristischer Bewertungsverfahren beurteilt, was es dem Programm schliesslich erlaubt, aus all den möglichen Zügen den besten auszuwählen. Spielbäume sind ein beliebtes Forschungsobjekt; man kann die Suchzeit mit vielen Optimierungsmethoden (alpha-beta pruning, negascout etc.) verkürzen, kritische Situationen näher untersuchen und schlechte Situationen von vornherein ignorieren.

Programme, die mit Spielbäumen arbeiten, werden meistens für Brettspiele eingesetzt; Deep Blue ist wahrscheinlich das berühmteste Beispiel. Wegen der vielen Einschränkungen die ich anfangs erwähnt habe, benutzt man sie in der heutigen Spielentwicklung recht selten.

Nun zum versprochenen Beispiel: Wir werden in aller Kürze die Grundlagen eines der bekanntesten aller KI-Algorithmen, des A* Pathfinding Algorithmus, und einige seiner Optimierungen betrachten, um ein Gefühl dafür zu bekommen, wie schwierig diese scheinbar einfache Aufgabe sein kann: Wie bringt man es einem Agenten bei, sich von einem Ort zu einem anderen zu bewegen?

Ein kurzer Pseudocode, der den Algorithmus beschreibt:

Die Methode setzt voraus, dass das gesamte Gebiet in (quadratische) Felder aufgeteilt ist, die entweder betretbar oder nicht betretbar sind. Gegeben seien die Anfangsposition und das Ziel. Es wird eine Liste names „offen" erzeugt, die anfangs die aktuelle Position des Agenten enthält. Jedes Element dieser Liste enthält auch eine heuristisch bestimmte Abschätzung der Entfernung vom Ziel (z.B. Abstand in Luftlinie)

Dieser Algorithmus ist sehr einfach, besitzt aber viele Unschönheiten. Der Agent wird sich zum Beispiel nicht auf einer geraden Linie auf das Ziel zubewegen, sondern in Diagonalen und Horizontalen durch die Felder wandern. Kurven werden nicht auf realistische Weise umfahren, da sich der Agent auf der Stelle drehen kann. Dazu kommt, dass der Agent in dieser Simulation offenbar keine Ausdehnung hat: er kann sich zwischen zwei diagonal benachbarte unbetretbare Blöcke drücken, ohne dass der Algorithmus etwas merkt.

Bisher haben wir einen einzelnen Agenten und ein einfaches Spielfeld betrachtet. Was ist aber, wenn es mehr Terrainarten gibt? Wie bringt man es einem Agenten bei, sich vorzugsweise auf einer Strasse zu bewegen? Was ist, wenn verschiedene Terraintypen verschieden schnelle Fortbewegung bedeuten? Wie behandelt man eine Situation mit mehreren Agenten um Zusammenstösse zu vermeiden oder in Formation zu bleiben? Was ist, wenn Anfangs- und Endposition eine Ausrichtung haben müssen? Und um das Ganze noch weiter zu verkomplizieren, kann man den Spass natürlich auch in die dritte Dimension verlegen.

Die Problematik ist offenbar bei weitem nicht so einfach, wie sie anfänglich aussieht; weitere Informationen befinden sich im Link im Anhang. Das Pathfinding-Problem ist in praktisch jedem Spiel vorhanden, aber es ist bis heute noch nie auf zufriedenstellende Weise gelöst worden.

Was ist aber, wenn man ein Problem trotz allen Schwierigkeiten lösen kann? Ein nicht zu unterschätzender Faktor ist der Schwierigkeitsgrad des Spiels. Bei kommerziellen Produkten darf die KI auch nicht zu gut sein, da die Spieler ansonsten sehr schnell frustriert werden. Die einfache Lösung wäre, ab und zu eine zufällige Entscheidung einfliessen zu lassen damit der Mensch auch eine Chance hat. Die wahre Kunst besteht aber darin, sich auch die Fehler sorgfältig auszusuchen, damit das Spiel so interessant wie möglich bleibt. Schliesslich geht es uns bei den meisten Spielen nicht um den Realismus, sondern vor allem um den Spass.

 

Informationsquellen und empfohlene Links:

Vorschläge für eine Spielentwicklungmethologie:

http://sites.uol.com.br/vascog/design/

Newsgruppen zum Thema:

comp.ai.*

Versuche, Lernfähigkeit in Spielprogramme einzubauen:

http://satirist.org/learn-game/

Allgemeine Spiel-KI Seite mit Codebeispielen:

http://www.gameai.com

Sammlung von Artikeln über KI, von Spielprogrammierern geschrieben (darunter ausführliche Beschreibung des A* mit Optimierungsvorschlägen):

http://www.gamasutra.com/features/index_ai.htm