KI - Speicherung von Wissen
-
Hallo danke für deine schnelle Antwort. In diesem Beispiel hast du natürlich Recht. Aber wenn ich nun ein anderes Spiel oder Programm schreibe was mehr Datenmengen beinhaltet, wird es schon komplizierter. Außerdem muss bei jedem Zug ja nachgesehen werden ob es diese Kombination schon einmal gegeben hat und welches Resultat dabei entstanden ist.
-
Fischkopf2009 schrieb:
Ich bin gerade dabei mich mit künstlicher Intelligenz zu beschäftigen. Ich möchte zu beginn einfach ein kleines Tic Tac Toe Spiel programmieren. Dazu möchte ich auch einen KI - Gegener programmieren. Er soll aber von Spiel zu Spiel "lernen". Das bedeutet, wenn er einen Zug macht und im nächsten verliert, soll er bei gleicher Konstellation im nächsten Spiel nicht den gleichen Zug machen. Nun meine Frage wie schafft man es elegant diese Dinge zu speichern.
Wie wäre es mit reinforcement learning? Da kannst du neue Zustandsübergänge problemlos dynamisch speichern wenn sie auftreten und in der Explorationsphase einfach zufällig wählen. Da der Zustandsraum bei Tic Tac Toe so klein ist, ist auch sichergestellt das reinforcement learning eine gute Strategie findet.
-
Hm, hatte mit dem Thema noch nicht wirklich was am Hut, aber vielleicht mit Objektserialisierung. Du wirst ja eine Klasse haben (ich weiß jetzt nicht welche Programmiersprache du verwendest), die dein Spielfeld verwaltet und somit auch, die Position der O und X. Ist ein Spiel zuende, speicherst du dieses Feldobjekt ab. Später kannst du es dann auslesen und mit dem Inhalt dieses Objektes arbeiten. Ist kein großer Speicheraufwand und du musst nicht viel tuen, mit C# und .NET ist sowas z.B. recht einfach.
-
Wie wäre es mit reinforcement learning?
Haette ich auch empfohlen. Habe ich im Zusammenhang mit general game playing benutzt. Hier die Ausarbeitung. Normalerweise speichert man den Zustand und assoziert mit ihm einen Wert. Dieser Wert wird durch Simulation des Spiels gelernt. Spielt die KI dann wirklich, so wird der aktuelle Zustand genommen, moegliche Aktionen ausgerechnet, Aktionen auf Zustand angewandt und die Folgezustaende betrachtet. Es wird die Aktion ausgewaehlt, die den besten Folgezustand liefert. Falls der Folgezustand in der Lernphase noch nicht besucht wurde, so wird ein default-Wert damit assoziiert. Will man nicht den gesamten Spielzustand abspeichern, so kann man auch einen Hashwert benutzen. Was Vor- und Nachteile hat.
-
Fischkopf2009 schrieb:
einfach ein kleines Tic Tac Toe Spiel
Icematix schrieb:
Aber das wäre riesige Datenmengen.
9x9 = 81 Bytes, als Bitmap 11.
Nach einem Spiel mit sagen wir mal 20 Zügen sind das gerade mal 1.6kb bzw 220 Byte.
Gigantische Datenmengen ^^Ich packe, um die Zugriffszeiten zu senken. Ums Datensparen geht es kaum. Entweder man lernt vorsichtig, und dann hat man viel viel Zeit, bis die erste Terabyteplatte vollgelernt ist. Oder man versucht, jeden Scheiß zu lernen, dann braucht man bei TicTacToe aber vermutlich nicht mehr als
(Zugfolgen speichern) 9 != 362880 Mögliche Partien * 4Bit Bewertung = 177k
(Stellungen speichern) 9 Felder * 2Bit -> 2^18 *4Bit = 128k
aber bei Krachern wie Schach reichen auch 1000 Platten nicht, um ihn auch nur ein bißchen schlau zu kriegen.Weiteres hängt von der Sprache ab. Bei Lisp/Prolog läßt Du es die Sprache machen, bei C#/Java natürlich einen (XML-)Serialisierer.
Wenn Du tiefer einsteigen möchtest und zufällig C++ magst, sind vielleicht die Suchbegriffe Cuckoo-Hashing, Zobrist hashing und FileMapping anschauenswert, damit bekommst Du bei großen Datenmengen schonmal Faktor 100 gegenüber naiven Lösungen und kannst Dich besser auf die spannendere Hauptsache konzentrieren und mehr/bessere Experimente fahren.
-
Bei Tic-Tac-Toe kannst du auch noch die Symmetrie des Problems benutzen, um noch weniger Daten speichern zu müssen.
-
Im Übrigen würde ich bei Tic Tac Toe eher Zufall mit reinbringen als eine Engine zu bauen, die nach ein paar hundert Spielen nicht mehr geschlagen werden kann, im besten Fall unentschieden.
-
Icematix schrieb:
Im Übrigen würde ich bei Tic Tac Toe eher Zufall mit reinbringen als eine Engine zu bauen, die nach ein paar hundert Spielen nicht mehr geschlagen werden kann, im besten Fall unentschieden.
Guten Morgen. Es geht mir ja nicht darum ein tolles Spiel zu programmieren, sondern schon ein KI. Und das Ziel sollte sein, dass sie von Spiel zu Spiel lernt.
-
Ich würde auch Reinforcement learning empfehlen, um genau zu sein "Direct Policy Search". Vielleicht für Tic-Tac-Toe noch ein enig zu krass, aber wenn du mal was komplexeres machst ist das das mittel der Wahl. Speicherverbrauch wird dann vielleicht nen paar Bytes oder so sein, weil du nicht mehr jede Spielsituation lernen musst, sondern direkt eine Funktion berechnest die einfach immer die optimale Handlung (in der Theorie) wählt. Habe ich selbst schon bei einem Rennspiel(torcs) eingesetzt und klappt ziemlich gut(naja, überholen hat er nie hingekriegt
)Der beste Backgammon Spieler ist übrigens ein Computer. gelernt mit TD-lernen. Hat aber auch ca 1 Milliarde spiele gegen sich selbst gespielt... (um genau zu sein ist der so gut, dass die weltbesten menschlichen Spieler gegen ihn antreten um neue Züge zu lernen).
In überschaubaren Spielen kommt man aber noch sehr gut mit selbst geschriebenen Algorithmen klar. Momentan geht der Trend noch eher in Richtung, dass man die Grundfunktionalität von Hand schreibt und dann nur Parametertuning mit optimierungsverfahren macht.
In komplexen Spielen hat man wieder das Problem, eine richtige Repräsentation des Zustands für die KI zu finden, damit die das auch lernen kann...wir können halt keine 100 Neuronenlayer übereinander stapeln wie das Gehirn das tut, für uns sind 2 schon fast zu schwierig um die zu trainieren. Die funktionalität der unteren 98 Layer muss man also irgendwie slebst hinfriemeln...
-
Okay also fasse ich mal zusammen. Ich habe eine Klasse, die das Spielfeld verwaldet. Dazu gehören die Position von X und O, außerdem ermittelt die Klsase den nächsten Spieler und wertet den Zug aus. Also ob jemand gewonnen hat oder das Spiel noch offen bzw. unetenschienden steht. Aber nun zur KI. Die KI hat beim allerersten Starten noch kein Wissen. Daher wählt sie ein zufälliges Feld aus. Und nun noch eine Frage ist es sinnvoll jeden Spielzug zu speichern oder nur die Endposition mit einer Bewertung. Denn wenn die KI nun ( nach einiger Zeit) auf ein Muster trifft wird sie es ja nicht finden ( wenn man nur die Endpositio speichert). Daher würde ich jeden Spielzug speichern. Dann schaut die KI ob sie diese Kombination schon einmal gesehen hat und prüft wie das Spiel ausgegangen ist. Wenn die KI gewonnen hat, wird sie den gleichen Zug noch einmal machen. Ansonsten wird sie einen anderne zug versuchen. Ist diese Vorgehensweise sinnvoll.
-
knivil schrieb:
Normalerweise speichert man den Zustand und assoziert mit ihm einen Wert.
Der Wert ist eine Art Mittlung ueber alle gewonnen/verloren Spiele aus diesem Zustand heraus. So wird bei geprueft, wie das Spiel im Mittel ausgegangen ist. Gibt es aus diesem Zustand heraus einen klaren Gewinnweg, so wird er auch gelernt. Das schlaegt sich in den Werten der Folgezustaende nieder.
-
Fischkopf2009 schrieb:
...einfach ein kleines Tic Tac Toe Spiel ...Ich kann natürlich für jeden Zug mir das Feld (Array 9x9) speichern.
Hat Tic tac toe nicht 3x3, also 9 felder?
Aber das wäre riesige Datenmengen.
2^9, also 512 ints?
Außerdem muss man über eine Bewertungsfunktion nachdenken, so dass die KI mit bekommt ob ein Zug gut oder schlecht war. Hat jemand in der Richtung schon mal was gemacht und kann mir hier einen Tipp geben? Vielen Dank
gewonnen==gut->++
verloren==schlecht->--du kannst im stumpf-fall, beim spielen, fuer jedes feld, einfach alle noch freien positionen durchtesten und dann fuer jedes resultierende feld durch das array aus 512ints gehen und dir "das best" oder das "am wenigstens schlecht" bewertete raussuchen und diesen zug machen.
ich werde das gefuehl nicht los ich ubersehe was, was alle anderen sehen
-
rapso schrieb:
du kannst im stumpf-fall, beim spielen, fuer jedes feld, einfach alle noch freien positionen durchtesten und dann fuer jedes resultierende feld durch das array aus 512ints gehen und dir "das best" oder das "am wenigstens schlecht" bewertete raussuchen und diesen zug machen.
Aber ist das lernen. Wenn ich einfach immer den besten Zug mir errechne und nicht anhand von vorherigen ergebnisse ermittle?
-
rapso schrieb:
ich werde das gefuehl nicht los ich ubersehe was, was alle anderen sehen
Es gibt halt die Einschränkung das er etwas machn will, dass nicht nur bei Tic-Tac-Toe funktioniert. Und ne Spielbaumsuche ist halt schon bei Spielen wie 4-Gewinnt ätzend aufwendig.
-
otze schrieb:
rapso schrieb:
ich werde das gefuehl nicht los ich ubersehe was, was alle anderen sehen
Es gibt halt die Einschränkung das er etwas machn will, dass nicht nur bei Tic-Tac-Toe funktioniert. Und ne Spielbaumsuche ist halt schon bei Spielen wie 4-Gewinnt ätzend aufwendig.
Das sehe ich genau so. Ist denn mein oben beschirebenes Vorgehen so okay, oder gibt es da Verbesserungen
-
otze schrieb:
Und ne Spielbaumsuche ist halt schon bei Spielen wie 4-Gewinnt ätzend aufwendig.
RL ist noch blinder
. Viele Fehler um den 10. Zug rächen sich erst in Zug 38 oder 40. Über 28 Züge Blindheit hinweg kommt nur noch Rauschen an. Das kann man sich leicht verdeutlichen, wenn man sich vorstellt, daß es nur einen Weg über die 28 Züge gäbe, der zum Sieg führt. Der RLerner hat keine Chance (7^-28==0), den Siegzug zu finden und müllt die Datenbank einfach nur mit Zufall voll.
-
Eine Menge Spiele kann man mittlerweile trotz der "gewaltigen Datenmengen" schon per Brute-Force lösen. So gewaltig sind die dann nämlich häufig doch nicht, wenn man mal von Schach und Go absieht. Vier gewinnt wurde schon vor 12 Jahren gelöst. Damals mit satten 40.000 CPU-Stunden. Das ist heute zwar immer noch viel, aber man kann ja die Ergebnisse lesen und damit seine unschlagbare KI bauen.
Und man kann sich die Algorithmen angucken, mit denen diese Spiele gelöst wurden, wobei das in der Regel einfach Brute-Force ist.
-
RL hat sich damals bei 4-gewinnt sehr gut geschlagen. Kein menschlicher Spieler konnte gewinnen. Auch kann man nicht wirklich von KI bzw. Lernen sprechen, wenn man 28 Zuege im voraus berechnet. RL ist vor allem dann gut, wenn noch keine spezielle Strategie fuer ein gegebenes Spiel vorliegt (general game playing). Es ist auch anwendbar, wenn es mehrere Gegner gibt und alle gleichzeitig ziehen duerfen. Wobei abwechselnd Ziehen ein Spezialfall von gleichzeitig Ziehen ist.
-
knivil schrieb:
RL hat sich damals bei 4-gewinnt sehr gut geschlagen. Kein menschlicher Spieler konnte gewinnen.
Quelle? Hatten die menschlichen Spieler sowas wie http://homepages.cwi.nl/~tromp/c4.html gelesen oder waren es Anfänger?
-
General Game Playing Seminar 200x, keine Ahnung mehr. Selbst getestet. Nein, die menschlichen Spieler haben das nicht gelesen. Wenn du mit Anfaenger meinst, dass sie nicht die Expertenstrategie beherschten, dann waren es Anfaenger. Auch ist es wohl schwer solche Expertenregeln on-the-fly von einer KI ableiten zu lassen, wenn man nur eine Regelbeschreibung des Spiels gegeben hat. Die vorgegeben Zugzeit war 1 Minute. Auch lassen sich diese Regeln schwerlich auf andere Spiele uebertragen.
