KI - Speicherung von Wissen
-
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.
-
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
-
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".
-
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.
-
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.
-
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?
-
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
-
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?
-
rapso schrieb:
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?
Jedes Feld hat aber 3 mögliche Zustände, nicht 2.
-
rapso schrieb:
aber gerne doch
Die Frage war wie, nicht wo.
Ich würde mal frech behaupten, ein Tic Tac Toe-Spielfeld in maximal 9 ints speichern zu können, und alle Spielsituationen in 49302 ints. Aber ich habe es vielleicht einfach nicht kapiert.
