3. KI - Speicherung von Wissen

KI - Speicherung von Wissen

  • F

    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.

    0
  • O

    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...

    0
  • F

    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.

    0
  • K

    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.

    0
  • R

    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 😕

    0
  • F

    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?

    0
  • O

    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.

    0
  • F

    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

    0
  • V

    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.

    0
  • Mod

    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.

    0
  • K

    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.

    0
  • V

    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?

    0
  • K

    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.

    0
  • O

    volkard schrieb:

    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.

    Interessanterweise ist dem nicht so. Wenn du in Zug 28 verlierst, dann weißt du dass die Aktion von Zug27->Zug28 nicht so wirklich gut war. Daraus kannst du auch Ableiten, dass es vielleicht nicht ganz so sinnvoll ist, im Zug 26 die Aktion zu nehmen, die auf den Zustand von Zug 27 führt. Und so läuft das die Markovkette zum Zug 1 zurück. Richtig ist, dass die Informationen natürlich immer weniger Aussagekraft haben, je weiter du zurück gehst, aber auch das wird von den Algorithmen beachtet. Von vielen, vor allen den älteren Algorithmen wie TD(lambda) oder Q-lernen ist bekannt, dass sie die optimale Lösung der Bellman Gleichung finden. Und die bellman Gleichung ist DAS theoretische Mittel um optimale Strategien zu finden.

    //edit noch ne Kleinigkeit: Natürlich ist das Ergebnis für Zug1 sehr verrauscht. Aber das Rauschen ist nicht Mittelwertsfrei! Spielt man also genug Spiele, erhält man den Mittelwert. und je höher der Mittelwert, desto höher ist die durchschnittliche Wahrscheinlichkeit, mit dem Zug zu gewinnen.

    Der RLerner hat keine Chance (7^-28==0), den Siegzug zu finden und müllt die Datenbank einfach nur mit Zufall voll.

    Der RL-Lerner hat gar keine Datenbank sondern eine Nutzenfunktion. Und eigentlich ist das Gegenteil der Fall. Nach relativ wenigen Spielen ist die KI so weit, dass sie einen Großteil aller möglichen Zustände des Spiels nicht mehr beachten braucht und konzentriert sich auf die lohnenswerten Spielzweige. Damit löst RL-Lernen das größte Problem der Brute-Force suchen: >80% aller Zustände sind normalerweise für ein Spiel nicht relevant, da die Spieler nicht daran interessiert sind, in diese Zustände zu kommen.

    Btw: letztens kam eine neue Go-Ki raus. Basierend auf Musterbasiertem-RL-Lernen. Hat Gnu-Go spontan ausgestochen 🙂

    Und 4-Gewinnt ist auch sicher nichts gegen Backgammon:
    www.inf.fu-berlin.de/lehre/SS04/19577-S/06_Back_Gammon.pdf

    0
  • ?

    Fischkopf2009 schrieb:

    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?

    in der tabelle werden doch anhand der vorherigen spiele die zuege bewertet, mehr machen die anderen "lernalgorithmen" auch nicht.

    ich sagte nur dass der suchraum bei tic tac toe sehr klein ist bzw die datenmenge, 512 eintraege, da koenntest du zufaellig ki vs ki spielen lassen und immer das resultat bewerten und haettest "lernen".

    0
  • O

    raps schrieb:

    ich sagte nur dass der suchraum bei tic tac toe sehr klein ist bzw die datenmenge, 512 eintraege, da koenntest du zufaellig ki vs ki spielen lassen und immer das resultat bewerten und haettest "lernen".

    Und das ist im Endeffekt das, was RL-Algorithmen machen...nur Trickreicher.

    0
  • V

    raps schrieb:

    in der tabelle werden doch anhand der vorherigen spiele die zuege bewertet, mehr machen die anderen "lernalgorithmen" auch nicht.

    je nach dem. gerne wird auch eine "funktion" gebaut, die sich die stellung anschaut und irgendwie verrechnet, zum beispiel "turm auf grundlinie"=10p, "dame auf e5"=1p und so weiter. klar, daß diese eumel wie maulwürfe spielen. bei ausgesuchten spielen, wo es nicht so wichtig ist, ob man jetzt auf e5 oder f5 steht, schlagen sie sich nicht schlecht. aber die machen eh keinen spaß. solche funktionen garantieren praktisch, daß kein optimales spiel geschieht. 🙂

    0
  • V

    raps schrieb:

    ich sagte nur dass der suchraum bei tic tac toe sehr klein ist bzw die datenmenge, 512 eintraege, da koenntest du zufaellig ki vs ki spielen lassen und immer das resultat bewerten und haettest "lernen".

    Könntest Du mir nochmal zeigen, wie Du auf 512 ints kommst?

    0
  • F

    volkard schrieb:

    raps schrieb:

    ich sagte nur dass der suchraum bei tic tac toe sehr klein ist bzw die datenmenge, 512 eintraege, da koenntest du zufaellig ki vs ki spielen lassen und immer das resultat bewerten und haettest "lernen".

    Könntest Du mir nochmal zeigen, wie Du auf 512 ints kommst?

    Hab ich auch nicht verstanden 😃

    0
  • R

    volkard schrieb:

    raps schrieb:

    ich sagte nur dass der suchraum bei tic tac toe sehr klein ist bzw die datenmenge, 512 eintraege, da koenntest du zufaellig ki vs ki spielen lassen und immer das resultat bewerten und haettest "lernen".

    Könntest Du mir nochmal zeigen, wie Du auf 512 ints kommst?

    aber gerne doch

    rapso schrieb:

    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?

    0
Anmelden zum Antworten