Literatur zu Künstlicher Intelligenz

[Senior Sanchez]

Hi,

Das Thema ist ja sehr vielseitig und ich glaube man könnte ganze Bibliotheken mit Stoff dazu füllen, allerdings suche ich etwas bestimmtes, wobei ihr vllt helfen könnt.

Im genaueren geht es um eine Art Spiel (Teil eines Programmierwettbewerbs) bei dem man eine KI schreiben soll, die zum Teil in dreifacher Form eingesetzt wird. Das heißt, in einem Spielverlauf kommt meine KI dann dreimal zum Einsatz, in autonomer Form. Bei diesem Spiel gibt es natürlich auch Rahmenbedingungen und man tritt auch gegen andere Gegner an.

Die Frage ist jetzt, auf welchen Zweig der künstliche Intelligenz man sich dort stützen sollte?

KNNs fallen IMO raus, weil irgendwie keine Zeit für eine Lernphase da ist, dass stelle ich mir zu träge vor und in der Zeit macht der Gegner wohl zu viele Punkte.

Spielbäume, sofern man die überhaupt in den KI-Sektor zählen kann, fallen schonmal raus, weil viel zu wenig Gegnerkontakt erstmal anfangs da ist, da das Primärziel nicht ist, den Gegner zu ärgern, sondern eigene Aufgaben zu erfüllen.

Softwareagenten wären denke ich ganz passend, die passen genau in das gesuchte Raster, da auch die Zusammenarbeit der drei autonomen Individuen meiner KI von entscheidenem Vorteil sein kann. Nur wie arbeite ich mit Softwareagenten? Wie implementiere ich so etwas? Da habe ich bisher wenig konkretes gefunden.

Probabilistische Aussagen könnten auch hilfreich sein, aber denke ich nicht zum Hauptzweck.

Wie wird das in der Spieleindustrie gemacht und gibts dazu gute Literatur im Netz? Es gab auch mal nen ct Artikel dazu, nur finde ich ihn momentan leider nicht :(

PS: Sorry, wenn meine Erläuterungen zur eigentlichen Aufgabe etwas unscharf sind, allerdings könnten hier auch Konkurrenten mitlesen und man will ja nicht zuviel verraten ;)

Danke schonmal

[Coda]

Die Lernphase eines NN solltest du ja auch bevor du das Ding benützt machen :)

Aber NNs sind so ne Sache, für viele Dinge auch sehr ungeeignet. Ich weiß nur dass irgend nen Rally-Spiel die Gegner per NN fahren lässt.

[Senior Sanchez]

Naja, nur ist das Problem für das NN auch wieder, dass es unterschiedliche Umgebungen gibt. Sprich, beim Spiel muss auch auf die Umgebung geachtet werden, weil manche Dinge nicht durchlaufen werden können, sondern weil man dann drum herum gehen muss, mal ganz bildlich gesprochen.

Ich weiß somit nicht, ob die NNs vllt für so etwas zu wenig dynamisch sind.

Ich meine, für die Pfadfindung die sich da anbietet, da habe ich mir schon Gedanken gemacht.
Hauptsächlich gehts mir um die Kooperation meiner KIs und wie man auf unerwartete Situationen reagieren kann.

Daher denke ich ja auch, dass sich Agenten anbieten würden.

[Gast]

Die Frage ist jetzt, auf welchen Zweig der künstliche Intelligenz man sich dort stützen sollte?
Zuerst sollte man sich mal drüber klar werden, was sich vereinen lässt und was nicht.
Agenten in MAS können alles mögliche verwenden, auch Entscheidungsbäume und NNs. NNs sind garnichtmal so schlecht, wenn man sie richtig trainiert. Ein guter Ansatz um relativ schnell gute Ergebnisse zu bekommen, ist es, einen genetischen Algorithmus zum Training zu verwenden. Das Hauptproblem ist eher, dass man nicht versteht warum sie etwas machen. X-D

Softwareagenten wären denke ich ganz passend, die passen genau in das gesuchte Raster, da auch die Zusammenarbeit der drei autonomen Individuen meiner KI von entscheidenem Vorteil sein kann. Nur wie arbeite ich mit Softwareagenten? Wie implementiere ich so etwas? Da habe ich bisher wenig konkretes gefunden.
Dann hast du nicht wirklich gesucht. Aber bei MAS gibt es soviele Teilaspekte zu beachten, dass man sich leicht verrennen kann. Man kann es relativ einfach über Blackboardlösungen machen oder trennt alles Wissen und Agenten komplett und betreibt viel Kommunikation. Dann kannst du dir noch um die Organisation der Agenten Gedanken machen (Stichwort holonische MAS) etc..

[Senior Sanchez]

Hmm, ich meinte mit Implementierung jetzt ein Ansatz wie ich welche in einer allgemeinen Programmiersprache entwerfen kann.
Meistens basiert diese ganze Literatur auf irgendwelchen speziellen Libraries oder Sprachen, was eben ungünstig ist.

[Stone2001]

Literatur zu diesem Thema gibt es fast wie Sand am Meer. Leider bieten die wenigsten Bücher konkrete Implementierungen an (ich kenne gerade keins).

Der Klassiker ist wohl Artificial Intelligence: A Modern Approach von Russell und Norvig : http://www.amazon.de/Artificial-Intelligence-Modern-Approach-Second/dp/0130803022/sr=8-1/qid=1171373893/ref=sr_1_1/303-1204587-0129825?ie=UTF8&s=books-intl-de
Daneben ist noch das Buch von Tom Mitchell - Machine Learning : http://www.amazon.de/Machine-Learning-Mcgraw-Hill-International-Edit/dp/0071154671/sr=1-1/qid=1171374002/ref=sr_1_1/303-1204587-0129825?ie=UTF8&s=books-intl-de sehr gut.

Bei der Suche ist mir gerade dieses Buch http://www.amazon.de/Developers-Creating-Intelligent-Behavior-Games/dp/0596005555/sr=1-4/qid=1171373969/ref=sr_1_4/303-1204587-0129825?ie=UTF8&s=books-intl-de aufgefallen, ob es was taugt, kann ich aber nicht sagen, ich kenne es nicht.

Generell musst du deine KI auf dein Problem abstimmen. Kannst du dein Problem im Vorfeld mit einer endlichen Menge an Regeln definieren, dann würden sich Entscheidungsbäume empfehlen. Neuronale Netze lassen sich für fast alles "missbrauchen", wenn du allerdings noch nicht weißt, in welcher Umgebung deine KI später eingesetzt wird, sind NN aber ungeeignet.
Für Spiele in stark begrenzten Räumen z.B. Tic Tac Toe oder auch Backgammon hat sich Reinforcement Learning als sehr geeignet erwiesen. Bei Go dagegen haben NNs Vorteile.

[Senior Sanchez]

Dass es die Literatur dazu wie Sand am Meer gibt, habe ich ja schon selber bemerkt *g*

In vielen Literaturstücken wird meiner Meinung nach nur um den heißen Brei geredet ohne mal richtig zu Potte zu kommen. Klar gehört auch Theorie dazu, aber ständig nur tolle Eigenschaften zu bewerben ohne mal eine konkrete Implementierung auf den Tisch zu legen finde ich doch etwas arm.

Im Moment läufts bei mir auf einen Entscheidungsbaum hinaus.
Das Problem mit der Umgebung ist etwas verzwickter: Ansich kenne ich die Umgebung. Es ist immer ein Feld mit Zielpunkten. Allerdings gibt es eben verschiedene Levels, dass heißt die Umgebung ist unterschiedlich aufgebaut, Hindernisse sind im Weg, Ziele sind an unterschiedlichen Punkten und Gegner stehen auch im Weg, die sich bewegen und somit die ganze Umgebung dynamisch gestalten. Deshalb sind NNs da vielleicht ungeeignet, oder täusche ich mich da?
Was ist Reinforcement Learning genau? Wo liegen seine Stärken?

[Gast]

In vielen Literaturstücken wird meiner Meinung nach nur um den heißen Brei geredet ohne mal richtig zu Potte zu kommen. Klar gehört auch Theorie dazu, aber ständig nur tolle Eigenschaften zu bewerben ohne mal eine konkrete Implementierung auf den Tisch zu legen finde ich doch etwas arm.
Das hat immer mehrere Gründe haben. Man will entscheidendes Knowhow nicht in den Veröffentlichungen verschenken (wenn ein Zwischenschritt als "trivial" bezeichnet wird, ists oft sehr gefährlich), man kann davon ausgehen, dass die Leser fähig sind so etwas zu implementieren, oder man hat nur theoretisch rumphilosophiert.
Manchmal ists auch schon komplex genug überhaupt die Theorie zu beschreiben und die Implementierung ist so richtig übel (effektives Graph Planning zb) und wird deswegen nicht weiter beschrieben.

Im Moment läufts bei mir auf einen Entscheidungsbaum hinaus.
Das Problem mit der Umgebung ist etwas verzwickter: Ansich kenne ich die Umgebung. Es ist immer ein Feld mit Zielpunkten. Allerdings gibt es eben verschiedene Levels, dass heißt die Umgebung ist unterschiedlich aufgebaut, Hindernisse sind im Weg, Ziele sind an unterschiedlichen Punkten und Gegner stehen auch im Weg, die sich bewegen und somit die ganze Umgebung dynamisch gestalten.
Was besitzt du als Sensoren?
Deshalb sind NNs da vielleicht ungeeignet, oder täusche ich mich da?

NNs sind meistens gut, wenn man sie sie für Spezialfälle und lokale Entscheidungen nutzt. Für allgemeine Entscheidungen in Spielen sind sie meistens unbrauchbar. Aber könnte ja zB mit ner FSM zwischen verschiedenen NNs umschalten. Oder nutzt irgendwas Regelbasierendes, oder du baust ne Umgebungsanalyse mit nem Situationsmatching (das wiederrum vielleicht mit nem NN zur Klassifikation) oder ...
Es gibt viele Möglichkeiten. ;)

Was ist Reinforcement Learning genau? Wo liegen seine Stärken?
http://www.igi.tugraz.at/lehre/semD_ss99/gruppe3/node2.html

[Wanginator]

Ohne dein Problem konkret zu kennen, könnte man doch für die Wegfindung etwas à la A* benutzen und für die Strategie ein regelbasiertes Lernen (falls die zu treffenden Entscheidungen nicht alle klar disjunkt sind, wäre auch Fuzzy eine Möglichkeit). Für kurzfristige reaktive Verhalten würde ich ein reaktives Verhaltensmuster aufbauen. Aber ich denke, man könnte mehr dazu sagen, wenn die Problemstellung genauer bekannt wäre.

[Stone2001]

In vielen Literaturstücken wird meiner Meinung nach nur um den heißen Brei geredet ohne mal richtig zu Potte zu kommen. Klar gehört auch Theorie dazu, aber ständig nur tolle Eigenschaften zu bewerben ohne mal eine konkrete Implementierung auf den Tisch zu legen finde ich doch etwas arm.
Herzlich Willkommen in der Welt der Wissenschaft!
Das eigentlich Konzept ist meist wichtiger als die eigentliche Implementierung. Die Implementierung braucht man eigentlich nur, um ein paar Messungen zu machen und die Behauptung untermauern zu können, warum man besser ist als alle anderen. In Paper wird man nie mehr als Pseudocode finden, auch in entsprechenden Bücher wird es schwer konkreten Code zu finden. Man geht einfach davon aus, das der geneigte Leser selbständig in der Lage ist diese zu verstehen und zu implementieren. Außerdem könnte man denen ja weiterhelfen und gefährdet somit sein nächstes Paper.
Ich habe es auch schon erlebt, dass Beschreibungen von Algorithmen, die 1 zu 1 umgesetzt wurden nicht ausgereicht haben um die Messergebnisse des Papers zu reproduzieren. Auf Nachfrage hat der Author dann zugeben nicht alle Tuningmaßnahmen der Implementierung im Paper erwähnt zu haben, weil kein Platz mehr im Paper dafür vorhanden war. ;)

Was ist Reinforcement Learning genau? Wo liegen seine Stärken?
Genau kann ich dir das nicht mehr sagen, dafür liegt es zulange zurück und ich habe mich nicht ausführlich mit RF befasst, aber bei den Spielen hat RF Vorteile, da man das Bestrafungs bzw. Belohnungssystem direkt an den Erfolg koppeln kann. Zudem läßt es sich mit vielen weiteren Verfahren (NN, Fuzzy, Entscheidungsbäume,...) kombinieren und dadurch kann man auch in anderen Bereichen recht ordentliche Ergebnisse erreichen.

[Senior Sanchez]

Die Wegfindung wird über A* laufen, das steht schon fest.
Die genaue Problemstellung möchte ich hier nicht posten, einerseits wegen der Konkurrenz, andererseits will ich auch nicht, dass hier allgemein zuviel verraten wird. Das fände ich unfair.

@Stone
In der Literatur in der ich bisher nachgeschaut habe, war nicht mal Pseudo-Code vorhanden. Das würde mir ja schon locker reichen. Eben etwas mehr in die Tiefe gehen, würde mir schon reichen, aber scheinbar wars einfach die falsche Literatur.

Ich schaue mal weiter was sich findet.

[micki]

Hmm, ich meinte mit Implementierung jetzt ein Ansatz wie ich welche in einer allgemeinen Programmiersprache entwerfen kann.
Meistens basiert diese ganze Literatur auf irgendwelchen speziellen Libraries oder Sprachen, was eben ungünstig ist.

am besten ist ein mathematischer ansatz, jedenfalls mach ich das immer so.

du hast ja eingaenge, dann verknuepfungen von neuronen und ausgaenge

eingang -> vector
neuronen -> matrix
ausgang -> vector

beispiel:

n 1bit-eingangswerte (z.b. werte eines OCR), 26 ausganzwerte (je buchstabe)

Vector(n ) * Neuronenmatrix -> Ausgangsvector

beim simplen trainieren
weisst du den eingangsvector, weisst du den ausgangvector -> matrix errechnen/bestimmen

du kannst mehrere matrizen aufaddieren

wenn du glueck hast, kannst du nun einen eingangsvector*matrix rechnen und bekommst einen ausgansvektor, wo der eintrag mit dem hoechsten wert den buchstaben bestimmt.


wenn du pech hast "weiss" das neurale netz (die matrix) nicht genug oder du hast versucht zuviel reinzustecken (ueberlastung) und es kommt nur noch rauschen raus.



das ist natuerlich nur so ein grober anfang, war sicherlich nur kapitel 1 in irgend nem buch das ich las, aber grundsaetzlich ist es von vorteil wenn man vectoren und matrizen benutzt.

zum einen kann man sich einmal so ein tool schreiben, das man sehr einfach per text-script steuert (matrizen und vectoren parsen ist simpel ;) ) und zum anderen kann man das auch schoen trivial einprogrammieren und durchschauen, statt mal im debugger sich durch netze von pointern durchzukaempfen (falls man einen OOP ansatz waehlt).


hoffe ich konnte ein wenig helfen :)

[ScottManDeath]

Solche neuronalen Netze kann man z.B. mit dem LVQ (Learning Vector Quantization) trainieren ...

[Gast]

In der Literatur in der ich bisher nachgeschaut habe, war nicht mal Pseudo-Code vorhanden. Das würde mir ja schon locker reichen. Eben etwas mehr in die Tiefe gehen, würde mir schon reichen, aber scheinbar wars einfach die falsche Literatur.
Such mal bei Amazon bei den englischen Büchern nach "ai game".
Die Bücher, die du dann findest, haben fast immer Beispielcode...

[Senior Sanchez]

Danke für die Postings.
@micki, du beschreibst ja im grunde einfach ne lineare Abbildung, was bei Perzeptronen ja auch gut passt.

Ich suche aber halt auch andere Sachen über KI, nicht nur über KNNs.

[micki]

Danke für die Postings.
@micki, du beschreibst ja im grunde einfach ne lineare Abbildung, was bei Perzeptronen ja auch gut passt.

Ich suche aber halt auch andere Sachen über KI, nicht nur über KNNs.
nur fuer den fall dass du das nicht schon lange kennst: http://www.gameai.com/ :)

ansonsten empfehle ich dir ebenfalls dir (englische)buecher zur game-AI zu besorgen.