KI

[Seamann]

Hallo an alle,

ich halte in unserem Informatikkurs ein Referat über künstliche Intelligenz.
Ist ja ein sehr interessantes Thema, aber doch arg theorielastig.

Jetzt wollt ich fragen, ob es die Möglichkeit gibt eine "kleine" KI (muss nicht viel können, nur um ein bisschen zu zeigen wie das in der Praxis aussehen kann) zu programmieren.
Hab schon gedacht vl was in richtung Tic Tac Toe gegen den Computer.
Das ganze soll das Referat nur ein bisschen "aufpeppen" und als Hinführung dienen. Ich erwart gar nicht dass ich da eine mords KI hinbekomme (weiß ja nicht was für ein Ausmaß sowas animmt)
Allerdings fehlt mir noch der Ansatz, um über das Programmieren nachzudenken (Wie genau funktioniert eine KI, vl ja sogar ein Beispiel ;-)).

Kennt jemand Lektüre wo man sich ein bisschen mehr in das Thema einlesen kann (im optimal Fall sogar gleich für Delphi) oder vl hat ja auch jemand hier eigene Erfahrungen die mir weiterhelfen könnten.

[Torpedo]

Das könnte dich interessieren:
http://de.wikipedia.org/wiki/Neuronales_Netz

Zu dem Thema gibt es auch hier in der DP einiges (auch Beispielprojekte)

[Codewalker]

Es gibt recht gute Beispiele für TicTacToe-KIs. Man kann auch eine "einfache" KI dafür über einen endlichen Automaten realisieren (Stichworte: DFA, endlicher deterministischer Automat). Wikipedia ist da zwar formal korrekt, aber für den Einstieg undankbar. Manche Unis bieten auch von Vorlesungen Videos (z.B. RWTH Aachen, http://videoag.fsmpi.rwth-aachen.de/?course=09ss-fosap . Leider scheinbar nicht alle öffentlich verfügbar).

[fkerber]

Hi!

KI ist ja nun ein äußerst weites Feld - in welche Richtung willst du denn konkret gehen?


Grüße, Frederic

[mleyen]

Man sollte sich ersteinmal fragen, wie man "künstliche Intelligenz" definiert.

Dabei kann man z.B. von fest definierten Aufgaben ausgehen, oder auch von 'lernenden' Fähigkeiten.
Z.B. das Neuronale Netz: Hier wird ein undefinierter Ausgangspunkt mehr und mehr beschrieben, bzw es wird gelernt, wie es etwas handzuhaben ist.

Andererseits sprechen viele von KI bei z.B. einem (wie in deinem Beispiel) TicTacToe-Bot.
Dieser Bot kann so programmiert werden, dass er genau ausrechnen kann, wo er hinklicken muss um am wahrscheinlichsten zu gewinnen, bzw. um nicht verlieren zu können.

Ich behaupte mal das es reicht, die 'fest definierte'-KI zu beschreiben.
Diese würde sich in deinem Fall für jedes freie Feld eine Priorität errechnen, wie sinnvoll es wäre dort das X zu setzen.
Der Bot entscheidet sich dann später für das Feld mit der höchsten Priorität.

[Seamann]

@Torpedo: naja, neuronales Netz wird doch eher was für den theoretischen teil sein.

@codewalker: super, werd ich mich morgen gleich mal in der richtung umschaun.

@fkerber: kommt drauf an was du meinst. theoretisch werd ich halt auf technik, momentaner stand, möglichkeiten, usw eingehen (bin erst am informieren...hab noch nix zusammengeschrieben, da das referat ja erst im dez oder so fällig ist). praktisch bin ich offen für alles. es sollte halt für mich (und meinen klassenkameraden) verständlich sein.
Im grunde will ich einfach auch ein bisschen was praktisches zeigen, weil nur 30 min gelaber über theorie is doch bissel langweilig (sowohl zu halten, als auch zum zuhören :-D)
Das mit dem tic tac Toe war nur ma son Gehirnfurz von mir, weil ich das halt grad programmiert habe. Also wenn du andere Ideen hast woran man eine Ki vorführen könnte...gerne ;-)

@mleyen:

Zitat:

Diese würde sich in deinem Fall für jedes freie Feld eine Priorität errechnen, wie sinnvoll es wäre dort das X zu setzen.
Der Bot entscheidet sich dann später für das Feld mit der höchsten Priorität.

wie erechne ich wie sinnvoll es ist in ein feld zu setzen? spontan würde ich da mit IF´s vorgehen, aber da muss es doch noch eine andere alternative geben, oder?

[fkerber]

Hi!

Erstmal noch: Herzlich willkommen in der DP ;)


Ich denke, du hast meine Frage noch nicht ganz verstanden:
Das Problem ist (in meinen Augen): es gibt nicht "KI" als Thema, sondern KI ist ein Überbegriff der imho zu groß gewählt ist, um darüber ein sinnvolles Referat halten zu können. Du solltest dich daher meiner Meinung nach auf ein Gebiet der KI beschränken, um darüber dann ein ein spezielleres aber auch fundierteres Referat halten zu können. Als Anregung mal ein paar Themen, die man unter dem Begriff KI zusammenfassen kann: Bilderkennung, Bewegungserkennung in bewegten Bildern, Plangenerierung, neuronale Netze, Robotik, Baysian Networks, Vererbungsnetze, Graphensuche, Reason-Maintenance-Systeme...


Grüße, Frederic

[mleyen]

Zitat:

Zitat von Seamann

wie erechne ich wie sinnvoll es ist in ein feld zu setzen?

Das kann man auf verschiedenste Weisen angehen.
Ich habs damals in einem ähnlichem Fall wiefolgt gemacht:

Zuvor habe ich jegliche Aktion, auf die der Bot später prüfen soll, im voraus definiert.
Dabei habe ich jeglicher Aktion einen Prioritätsfaktor zugewiesen.
ZB "sterb ich im nächsten Zug, wenn ich in diesem Feld setze?" Falls ja, dann setzte Priorität = Minimum , oder "Wieviele Möglichkeiten zu gewinnen hab ich noch, nachdem ich in diesem Feld gesetzt habe?" Bei 3 setze Priorität+30 | etc etc...)

So hangel ich mich durch alle Möglichen Aktionen und Einflussfaktoren des Spiels durch.

Das beste aber an der Geschichte ist:
Ich kann dem Bot eine dynamisch starke K.I. einstellen.
Wie?
Bei zB einem perfektem Bot nimmt der immer das Feld mit der höchsten Priorität.
Bei einer mittelstarken KI, lässt der Bot zufällig eines der Felder zu, welches 17% weniger Priorität hat als das maximale Feld.

Das war jetzt wirklich nur ein ganz grober Aufbau meiner damaligen Vorgehensweise, und ich hoffe jetzt nicht den Thread in ein anderes Thema zu ziehen.

Btw: Herzlich willkommen in der DP. :dp:

[fkerber]

Hi!

Ein allgemeines Vorgehen wäre, sich eine Bewertungsfunktion zu überlegen, die in etwa folgendes macht:
Für eine gegebene Spielfeldsituation wird eine Zahl errechnet - je besser die Situation für einen selbst ist, desto größer ist die Zahl. Für das TicTacToe-Spiel kannst du dann jeweils die drei Felder, die beim nächsten Zug entstehen könnten, bewerten lassen und das mit der besten Bewertung nehmen.

Eine mögliche Bewertungsfunktion wäre z.B. die Anzahl Spalten + Anzahl Zeilen + Anzahl Diagonalen, in denen X noch gewinnen kann (die also nur X und frei enthalten) - (Anzahl Spalten + Anzahl Zeilen + Anzahl Diagonalen, in denen O noch gewinnen kann (die also nur O und frei enthalten)) - unter der Annahme, dass du selbst X bist.



Grüße, Frederic

[DP-Maintenance]

Dieses Thema wurde von "Luckie" von "Sonstige Fragen zu Delphi" nach "Programmieren allgemein" verschoben.
hat nichts mit Delphi direkt zu tun.

[Medium]

Gerade Tic Tac Toe ist ein klassisches Beispiel für einen Minimax Baum, von dem es auch wieder unterschiedliche Ausprägungen gibt. TTT ist zudem simpel genug, um so einen Baum vollständig aufzubauen, weshalb es möglich ist einen "perfekten" KI Gegner zu bauen. Schach verwendet oft im Grunde einen ähnlichen Ansatz, ist aber viel zu komplex um den Baum ganz zu erstellen. Dort wird dann nur eine Hand voll Ebenen erzeugt, und dann braucht man erheblich komplexere Bewertungsfunktionen als "ich hab verloren" und "ich hab gewonnen", was bei einem vollständigen Baum ausreicht.

Ich muss sagen, dass das Thema für ein Schulreferat ein ganz schön üppiger Klopper ist, so es denn nicht grad an einem technischen Gymnasium im Info LK ist (selbst da noch grenzwertig). Falls du dabei bleiben willst, wäre es evtl. eine Möglichkeit den Schwerpunkt auf die Geschichte der KI zu legen, und evtl. eine Prise Automatentheorie. Das ist zwar eher trocken, aber KI ist nunmal weitgehend so. Mit einer Beispiel-KI würdest du von gaaanz hinten anfangen, und mindestens 5-7 weitere längere Referate an Theorie auslassen.

[Seamann]

jo, ich weiß dass ich mir mit dem Thema einen großen Brocken aufgeladen hab :D
aber ich hab halt was gesucht was mich selbst interessiert und zu Info passt.

Ich werd mich ma heut oder morgen an die KI für TTT setzen und dass ergebnis bekommt ihr dann natürlich als erste zu sehen
Vl mach ich auch mein referat größtenteils über den TTT Bot und mach noch bissel Ki geschichte hinterher (turing test usw)


Auf was ich sonst eingehen werde in der Theorie entscheid ich mal im laufe des Wochenendes^^

Ich bekomm mehr und mehr das Gefühl, dass ich mich da vl übernommen haben könnte...

[Torpedo]

Zitat:

Zitat von Seamann

Ich bekomm mehr und mehr das Gefühl, dass ich mich da vl übernommen haben könnte...

Lass einfach das meiste weg, das merkt eh keiner. ;)

Kannst ja am Anfang ein bisschen über Theorie reden: was ist KI, welche Arten von KI gibt es?
Dann Geschichte und am Ende erklärst du, wie eine KI für TicTacToe funktionieren könnte und zeigst dem Publikum deine Test-KI.

Das sollte eigentlich reichen.

[Seamann]

@torpedo: das ist denk ich die beste Idee


Aber ich hab jetzt folgendes Problem: Zuerst wollte ich dass ganze in einem Array versuchen. da die prioritäten speichern...

(1) es kommt ja oft vor dass die prioritäten von mehren feldern gleich sind
meine wären gewesen: 0 = feld von gegner
1 = eigenes feld
2 = chance auf eigene reihe
3 = chance von gegner auf reihe
4 = gegner kann gewinnen
5 = selber gewinnen
wo soll der Bot hinsetzen wenn z.b. 2 felder die priorität 3 haben?

(2) gibt es ja (laut wikipedia) ca. 250000 versch. Spielverläufe und die prioritäten verändern sich
ja. d.h. ich muss bei jedem zug dutzende möglichkeiten abfragen, damit die prioritäten stimmen oder geht dass auch anders?

(3)wie funktioniert das mit dem baum, bzw wie programier ich, dass das prog so einen baum erstellt? der ist ja sogar für
TTT schon recht groß (zumindest zu groß um ihn von hand zu zeichnen)

[himitsu]

Zitat:

wo soll der Bot hinsetzen wenn z.b. 2 felder die priorität 3 haben?

wozu gibt es denn den Zufallsgenerator

ich würde ihn dann aber auch so gestalten, daß er mit 'ner geringeren Wahrscheinlichkeit auch mal 'nen schlechteren Zug macht, damit reagiert er dann "menschlicher" und man hätte je nach Prioritätenverteilung auch mal 'ne Chance zum gewinnen.

[Medium]

Zu 1: Wenn du es so machst, hast du im Grunde eine "KI" die ohne jede Implikationen, nur auf Basis des gerade aktuellen Spielfeldes entscheidet. Das wäre gleich einem Minimax-Baum mit nur einem Knoten, und die gesamte "Intelligenz" würde ausschließlich in der Bewertungsfunktion stecken. Das wäre vergleichsweise arg unintelligent.

Zu 3: Woran hapert es genau? Weisst du nicht wie man generell eine Baumstruktur aufbaut, oder ist's was spezielleres? Im ersteren Fall würde ich je nach Deadline schon fast davon abraten überhaupt eine Implementierung anzustreben, da dann vermutlich noch mehr dabei nötige und hilfreiche Basics fehlen könnten.
So als Maßstab: Ich hab genau dieses (TTT mit Minimax) im 3. Semester Informatik an der FH gebaut, obwohl an sich nur simpleste (und potthäßliche) Logik ála if-Abfrage-Ketten erwartet war (was man mir erst nachher sagte...). War allerdings auch die Programmierkurs VL, nicht die KI. Bei KI sind wir erst ganz am Ende in den letzten 2-3 Übungsstunden an eine tatsächliche Implementierung gegangen, der ganze Rest war Theorie.

Du solltest also durchaus schon recht Sattelfest mit Begriffen wie Baum (+traversieren), Objekte, Referenzen, Rekursion usw. sein um nicht zu viel Zeit in das Erlernen der Grundlagen für die eigentliche KI stecken zu müssen. Wenn du noch mächtig Zeit hast wäre das wiederum eine prima Sache um sich viele zentrale Dinge in der Programmierwelt vertraut zu machen! Letztlich hängt die Entscheidung also von deinem aktuellen Kenntnisstand und der verfügbaren Zeit ab. (Und um's offen zu sagen: Wenn dein Stand auf dem Durchschnitt eines Info-Schülers der nicht oder kaum in seiner Freizeit programmiert ist, dann ist das beileibe nicht ausreichend um sowas mittelfristig fertig zu bekommen, und noch viel wichtiger: In Gänze zu durchblicken! Versteh mich nicht falsch, ich will keinen runter machen oder einen Ich-Bin-So-Toll-Trip fahren. Das ist meine ehrliche Einschätzung, vor allem als Ex-Info-Schüler ;))

[Seamann]

@medium die deadline wäre mitte dezember und ich bin aufm niveau von nem info schüler (vl au bissel drüber, ohne mich jetzt selbst loben zu wollen), aber dafür sehr neugierig :D und lernfähig

und mal ganz abgesehen das das mein referat wird, ich will mich mit dem thema ja au persönlich beschäftigen, d.h. die zeit es zu lernen hab ich...auch wenns über die deadline vom referat rausgeht

mag vl doofe frage sein: hat ttreeview was mit den büumen hier zu tun? dann wüsst ich wenigstens mal in welche richtugn ich suchen und lernen muss

[Medium]

Ja dann aufi! Nicht das langweiligste Thema, vor allem wenn man nach und nach merkt, dass man irgendwie keine Schnitte mehr gegen seinen PC sieht :mrgreen:

Bliebe aber noch die Frage offen, von wo aus es los geht. Also z.B.: Weisst du prinzipiell was eine Klasse und ein Objekt sind? Und weitergehend: Hast du schonmal eine verkettete Liste "in der Hand gehabt"? Was habt ihr im Unterricht so ca. schon mal programmiert?

[Seamann]

objekt kenn ich, unter verketter liste kann ich mir jetzt so nix vorstellen (aber indemfall eher nicht)
bei klasse weiß ich net was du meinst. wenn du meinst dass ein Buton ein Objekt von der Klasse TButon ist dann ja...

Programmiert in Info und Privat (was mir so einfällt):
-temprechner bei dem man celsuius, kelvin, fahrenheit und reaumur entsprechend umrechen konnte
-tic tac toe für 2 spieler (also dass was ich will nur halt ohne Ki)
-listen + laden u. speichern von dateien/listen
-einen BMI rechner