"Richtige" Netzarchitektur für das Spiel KNIFFEL ?

Sie haben ein bestimmtes Projekt zu bearbeiten und wissen nicht, wie Sie an die Aufgabe heran gehen sollen? Sie sind sich nicht sicher, ob Ihr Netzentwurf zu Ihrem Problem passt oder ob es da Optimierungsmöglichkeiten gibt? Ist es überhaupt sinnvoll an Ihre Daten mit einem NN basierten Ansatz heranzugehen? Ist MemBrain das richtige Werkzeug für Ihr Problem und Ihre Infrastruktur?

Hier ist der richtige Platz für diese Art von Fragen.
just4phil
Posts: 30
Joined: Mon 24. Oct 2011, 21:20

"Richtige" Netzarchitektur für das Spiel KNIFFEL ?

Postby just4phil » Tue 25. Oct 2011, 20:49

HeyHo!

ich hatte schon vor ca. 3 jahren versucht das spiel kniffel mit einem NN auf basis von

membrain abzubilden. damals hatte lediglich die mustererkennung gut funktioniert. bei der

festlegung der zu spielenden strategie war das netz nicht besonders erfolgreich und

generalisierung hat erst recht nicht funktioniert. nun starte ich den 2. versuch, da ich der

meinung bin, dass KNIFFEL mit einem NN lösbar sein MUSS.

Ich habe das Spiel in Excel programmiert und kann dort beim spielen trainigsdaten erzeugen.

(allerdings wird man wohl viele daten benötigen, da die möglichen permutationen ja nicht

unerheblich sind.) auch kann ich später den pc "unattended" spielen lassen und dabei

statistiken über die spielstärke generieren. das würde später also zur bewertung der

NN-qualität von vorteil sein.

nun aber zum problem:
ich möchte dem netz folgende INPUTS übergeben:

w1 -> würfel 1 -> werte 1 bis 6
w2 -> würfel 2 -> werte 1 bis 6
w3 -> würfel 3 -> werte 1 bis 6
w4 -> würfel 4 -> werte 1 bis 6
w5 -> würfel 5 -> werte 1 bis 6

runde -> werte 1 bis 3

111 -> werte: -1 (feld spielbar) oder 0 (feld wurde gestrichen) oder 1 bis 5 (Punkte)
222 -> werte: -1 (feld spielbar) oder 0 (feld wurde gestrichen) oder 2 bis 10 (Punkte)
333 -> werte: -1 (feld spielbar) oder 0 (feld wurde gestrichen) oder 3 bis 15 (Punkte)
444 -> werte: -1 (feld spielbar) oder 0 (feld wurde gestrichen) oder 4 bis 20 (Punkte)
555 -> werte: -1 (feld spielbar) oder 0 (feld wurde gestrichen) oder 5 bis 25 (Punkte)
666 -> werte: -1 (feld spielbar) oder 0 (feld wurde gestrichen) oder 6 bis 30 (Punkte)
3erP -> werte: -1 (feld spielbar) oder 0 (feld nicht mehr spielbar)
4erP -> werte: -1 (feld spielbar) oder 0 (feld nicht mehr spielbar)
FH -> werte: -1 (feld spielbar) oder 0 (feld nicht mehr spielbar)
klS -> werte: -1 (feld spielbar) oder 0 (feld nicht mehr spielbar)
grS -> werte: -1 (feld spielbar) oder 0 (feld nicht mehr spielbar)
chance -> werte: -1 (feld spielbar) oder 0 (feld nicht mehr spielbar)
kniffel -> werte: -1 (feld spielbar) oder 0 (feld nicht mehr spielbar)

HINWEIS:
--------
bei 111 bis 666 wollte ich die Punkte übergeben, da diese darüber entscheiden, ob man den

BONUS (+35 Punkte) noch bekommen kann und dies für die strategie wichtig ist. ab dem

3er-Pasch (3erP) sind die punkte meines erachtens nicht mehr wichtig.

FRAGE:
======
was haltet Ihr davon?


OUTPUTS:
=========

strategie -> werte: 1 bis 13 (für die 13 strategien 111 bis kniffel)

setzen - es soll direkt gesetzt werden! -> werte: 0 oder 1

1er - anzahl entnommener 1er würfel -> werte: 1 bis 5
2er - anzahl entnommener 2er würfel -> werte: 1 bis 5
3er - anzahl entnommener 3er würfel -> werte: 1 bis 5
4er - anzahl entnommener 4er würfel -> werte: 1 bis 5
5er - anzahl entnommener 5er würfel -> werte: 1 bis 5
6er - anzahl entnommener 6er würfel -> werte: 1 bis 5

HINWEISE:
---------
Bei den 1er bis 6er bin ich mir unsicher. sie geben an, welche würfel der spieler aus dem

würfelbecher entnimmt. dies KANN relevant sein, wenn aussergewöhnliche spielsituationen

autauchen. ansonsten kann man das aber auch konventionell implementieren und es wird wohl zu

98% sinnvolle ergebnisse erzielen. aber wenn das NN mit den vielen Outputs klarkommen würde,

dann wäre die angabe, welche würfel entnommen werden sollen, natürlich super.

zum output-neuron "setzen":
wenn zufällig im ersten oder zweiten wurf schon ein große straße oder fullhouse geworfen

wird, dann sollte das NN ggf. entscheiden, dass die punkte direkt gesetzt werden sollen, ohne

noch ein drittes mal zu würfeln.

FRAGE:
======
bei dem wichtigsten neuron "strategie" bin ich mir unsicher, ob man EIN neuron mit den werten

1 bis 13 nehmen sollte, oder besser 13 einzelne neuronen, die dann jeweils den wert 1 oder 0

ausgeben?

Was denkt Ihr?


UND NUN ZUR GRETCHENFRAGE:
--------------------------
Welche Netzarchitektur benötigt man zwischen input und output?
ich hatte damals einiges ausprobiert und jetzt auch schon wieder einige tests gemacht und bin

mir unschlüssig wieviele neuronen man in welcher konstellation benötigt, um das problem zu

lösen.....??

hier ein auszug aus den trainigsdaten:
http://freigabe.philweb.de/NN_Kniffel/2011-10-24_kniffel_NN_upload.xls

ich freue mich auf anregungen!!

ciao
phil

User avatar
Admin
Site Admin
Posts: 438
Joined: Sun 16. Nov 2008, 18:21

Re: "Richtige" Netzarchitektur für das Spiel KNIFFEL ?

Postby Admin » Tue 25. Oct 2011, 21:33

Hallo und herzlich willkommen im Forum!

Leider ist die Zeit heute Abend etwas knapp, ich werde versuchen, in den nächsten Tagen noch ein bisschen ausführlicher zu posten.

Im folgenden Thread geht es auch um eine Spielsimulation und ich denke, die Situation hier ist ähnlich:

http://www.membrain-nn.de/forum/viewtopic.php?f=5&t=223

Dort habe ich auf Reinforcement Learning (RL) als Strategie verwiesen und ich halte das im Hinblick auf eine funktionierende Implementierung für sehr ratsam (vielleicht sogar für unabdingbar).

Der prinzipielle Unterschied zum zunächst naheliegenden Ansatz, das Netz eine Aktion (= Strategie) wählen zu lassen, ist bei RL, das Netz die momentan verfügbaren Aktionen lediglich mit einem skalaren Wert bewerten zu lassen und dann die höchstwertige Strategie 'manuell', also per direkter Programmierung auszuwählen und auszuführen. Der Effekt der ausgeführten Aktion im Sinne von Belohnung oder Bestrafung fließt dann wieder in die Trainingsdaten für das neuronale Netz ein.

Der Output eines solchen NN besteht damit IMMER nur aus einem einzigen Neuron (= Wert der Aktion). Als Input muss man den momentanen Spielstatus und die zu bewertende Aktion anlegen.

Die grundsätzliche Kodierung dieser Elemente wie hier angedacht, erscheint mir erst einmal sinnvoll oder zumindest nicht unsinnig, später hoffentlich etwas mehr dazu.

Der große Reiz von RL ist, dass man zwei 'dumme' Spieler in rasender Geschwindigkeit gegeneinander spielen lassen kann und beide im Laufe dieser Duelle lernen, wie man gut Kniffel spielt. Es handelt sich also um echt emergentes Verhalten: Nicht der Programmierer teilt dem Netz mit, wie man Kniffel spielt, es lernt es von selbst!

Viele Grüße und wie gesagt: Hoffentlich bald noch etwas mehr dazu...
Thomas Jetter

just4phil
Posts: 30
Joined: Mon 24. Oct 2011, 21:20

Re: "Richtige" Netzarchitektur für das Spiel KNIFFEL ?

Postby just4phil » Wed 26. Oct 2011, 22:13

ok,

ich habe mal versucht das im ansatz umzusetzen.

ich habe in meinem NN den output "strategie" in einen input umgewandelt und einen neuen output "Wertigkeit" erstellt.
den output "Setzen" habe ich erstmal entfernt, da er mir in dieser konstellation als input nicht so sinnvoll erscheint.

http://freigabe.philweb.de/NN_Kniffel/2011-10-25_kn_RL-1.mbn

dann habe ich mal ein paar trainingsdaten erzeugt, da man ja wahrscheinlich etwas besser mit einem nicht total "dummen" netz starten kann.
hier habe ich jetzt folgenden ansatz reingebracht:
als wertigkeit werden einfach die punkte nach jedem zug herangezogen. dadurch hat man allerdings nur nach jedem dritten würfeln eine wertigkeit. das ist evtl ein problem?

http://freigabe.philweb.de/NN_Kniffel/2011-10-25_kniffel_NN_RL_-10_lesson.csv

darüber hinaus habe ich nun zu jedem zug protokolliert welche felder bereits gespielt wurden und diese strategien dann mit wertigkeit = -10 bewertet, um damit abzubilden, dass ein schon gespieltes feld auf keinen fall mehr vom NN als zu spielende strategie ausgewählt werden kann. ist das sinnvoll?

ciao
phil

User avatar
Admin
Site Admin
Posts: 438
Joined: Sun 16. Nov 2008, 18:21

Re: "Richtige" Netzarchitektur für das Spiel KNIFFEL ?

Postby Admin » Thu 27. Oct 2011, 17:58

just4phil wrote:hier habe ich jetzt folgenden ansatz reingebracht:
als wertigkeit werden einfach die punkte nach jedem zug herangezogen. dadurch hat man allerdings nur nach jedem dritten würfeln eine wertigkeit. das ist evtl ein problem?

Nein, das ist gar kein Problem und ich halte diesen Ansatz bei Kniffel für sehr sinnvoll.
Es ist sogar durchaus üblich, bei RL-Problemen erst ganz am Ende - also nach einem Spiel - einmalig ein Feedback zu geben (z.B. +1 für 'Gewonnen, -1 für 'Verloren' und '0' für 'Unentschieden'). Dieses Feedback pflanzt sich dann über viele Spiele hinweg in Richtung 'frühere Zustaände' fort. Das einmalige Feedback am Ende eines Spiels macht dann Sinn, wenn sich das Ziel des Spiels einzig nach 'gewonnen' oder 'verloren' richtet: In der Regel möchte und sollte man den Agenten nämlich nicht für Zwischenschritte belohnen, denn
1.) Könnte der Agent ganz andere Wege finden, die u.U. besser zum Ziel führen, als der 'belohnte' Weg
2.) Der Agent könnte fälschlicherweise erlernen, seine Belohnung nur aus dem Weg zu ziehen, egal ob er final gewinnt oder verliert.

Bei Kniffel ist das etwas anderes, denke ich, denn Kniffel ist durch seine Natur aus nicht auf einen Gegner angewiesen. Oder anders formuliert: Bei Kniffel richtet sich der Erfolg eines Spielers einzig und alleine nach der Punktzahl, die er auf seinem Weg erreicht. Diese ist von den Aktionen eventueller Gegner vollkommen unabhängig, man kann das Spiel sogar alleine Spielen und trotzdem bewerten. Und jeder (vollendete) Zug lässt sich klar mit einer Wertigkeit belegen.

Ich habe mir noch einige Gedanken zu der Codierung der Daten gemacht. Daraus werde ich aber einen separaten Post machen.

Viele Grüße
Thomas Jetter

User avatar
Admin
Site Admin
Posts: 438
Joined: Sun 16. Nov 2008, 18:21

Re: "Richtige" Netzarchitektur für das Spiel KNIFFEL ?

Postby Admin » Thu 27. Oct 2011, 18:24

Bevor ich meine Überlegungen zur Codierung kundtue, möchte ich hierzu noch etwas anmerken:
just4phil wrote:darüber hinaus habe ich nun zu jedem zug protokolliert welche felder bereits gespielt wurden und diese strategien dann mit wertigkeit = -10 bewertet, um damit abzubilden, dass ein schon gespieltes feld auf keinen fall mehr vom NN als zu spielende strategie ausgewählt werden kann. ist das sinnvoll?

Das geht wesentlich einfacher und zielführender:
RL benötigt eine übergeordnete Programmlogik, die das Netz über die Wertigkeit der zur Auswahl stehenden Aktionen in einem bestimmten Zustand befragt und dann die höchstwertige Aktion auswählt und durchführt. Der Satz sagt es eigentlich schon: Man befragt das Netz nur zu den möglichen Aktionen, die unmöglichen (z.B. weil Feld gestrichen oder weil sich ein Full-House nicht in das Feld für einen Vierer-Pasch eintreagen lässt), filtert man über die Programmlogik heraus.

Beantwortet das die Frage?

Viele Grüße
Thomas Jetter

User avatar
Admin
Site Admin
Posts: 438
Joined: Sun 16. Nov 2008, 18:21

Re: "Richtige" Netzarchitektur für das Spiel KNIFFEL ?

Postby Admin » Thu 27. Oct 2011, 19:39

Unabhängig von der Frage 'Input' oder 'Output' möchte ich zur Codierung der Daten eine prinzipielle Vorüberlegung vorausschicken:

Wenn verschiedene Werte eines logischen Merkmals keinen Größenbezug 'kleiner als' oder 'größer als' aufweisen, dann sollte man sie nicht in ein einziges Neuron packen, sondern als 'binäre' Information auf mehrere Neuronen aufteilen.

Ein Zwischending sind hier Würfelaugen: Hier gibt es zwar ein 'größer' und ein 'kleiner'. Wichtiger für Kniffel sind aber logische Kombinationen aus Würfelsymbolen (z.B. Sammeln von Einern, Zweiern, Straßen, Päsche, Full-House...). Aus diesem Grund würde ich auch hier dazu tendieren, die angezeigte Augenzahl eines Würfels nicht in ein einziges Neuron zu packen.

Konkret würde ich vorschlagen:

1.) Codierung momentaner Wurf (immer bestehend aus den Augenzahlen der fünf Würfel)
a) Würfel nicht durchnummerieren, sondern dem Netz nach gezeigter Augenzahl sortiert vorlegen: Es ist irrelevant, welches Würfelexemplar eine bestimmte Augenzahl zeigt, einzig wichtig ist die gezeigte Augenzahl. Anders formuliert: Ein Full-House aus 3 x 5 und 2 x 3 hat immer die selbe Bedeutung, egal welche der Würfel welche der genannten Zahlen zeigen. Deshalb sollte ein solches Full-House aus Sicht des Netzes immer gleich aussehen. Das sortierte Anlegen der Würfelaugen reduziert also die Anzahl der praktisch vorkommenden möglichen Permutationen aus Sicht des Netzes, bei gleicher eingehender Informationsmenge.
b) Jeden der fünf 'sortierten Würfelplätze' mit sechs Neuronen ausstatten. Der Wurf als Ganzes besteht damit also aus 5 * 6 = 30 Neuronen

2.) Codierung der zu füllenden Datenfelder
Hier würde ich für jedes Feld zwei Neuronen anlegen:
a) Spielbarkeit: 0 = Nicht mehr spielbar, 1 = spielbar
b) Wert: 0 Wenn gestrichen, sonst erzielter Feldwert
Ich würde also auch bei den Päschen, Straßen etc. einen Wert als Status mit angeben. Er könnte für die weitere Strategie wichtig sein. Da bin ich mir zwar nicht 100 % sicher, ich würde es aber RL überlassen, aus der Information etwas zu machen oder auch nicht.

3.) Codierung der Aktionen
a) Ein Neuron für 'Setzen' ( = 0) oder 'Nochmal würfeln' ( = 1)
b) Für jedes Datenfeld aus 2. ein weiteres Neuron, das auf 1 gesetzt wird, wenn das Wurfergebnis auf dieses Feld gesetzt werden soll. Diese Neuronen zeigen also das gewählte Setzfeld an, wenn das Neuron aus a) mit 0 (= Setzen) belegt ist. Ansonsten sind diese Neuronen immer 0.
c) Für jeden 'sortierten Würfelplatz' ein weiteres Neuron, das auf 1 gesetzt wird, wenn dieser Würfel zurück in den Becher soll (also auch nur wenn das Neuron aus a) mit 1 (= Nochmal würfeln) belegt ist.
d) Ein Neuron, das 'Streichen' bedeutet. Wird immer in Zusammenhang mit einem der Neuronen aus b) verwendet, das anzeigt, welches Feld als Kandidat zur Streichung ausgewählt werden soll.

Ich hoffe, ich habe nichts vergessen?

Doch, ich habe etwas vergessen:
4.) Codierung 'Nummer aktueller Wurf': Hier bin ich mir nicht schlüssig, ob man ein Neuron (Werte 0 bis 2) oder mehrere Neuronen nehmen soll. Ich würde fast zu drei Neuronen tendieren oder auch zu zwei Neuronen, die binärcodiert die Wurfnummer abbilden können (0/0, 0/1, 1/0)

Das sind natürlich auch nur Vorschläge, die meinem 'Bauchgefühl' entspringen. Sicherheit können nur Experimente bringen ;-)

Viele Grüße und viel Erfolg!
Thomas Jetter

just4phil
Posts: 30
Joined: Mon 24. Oct 2011, 21:20

Re: "Richtige" Netzarchitektur für das Spiel KNIFFEL ?

Postby just4phil » Thu 27. Oct 2011, 21:44

Danke!
das hilft mir schon mal weiter.
es macht die sache auf jeden fall sehr komplex, aber ich kann mir gut vorstellen, dass ein NN mit vielen binären neuronen mehr anfangen kann als mit einem 1-bis-13-neuron.
(die würfel habe ich übrigens schon seit 3 jahren in sortierter folge in den trainingsdaten, um das permutationsproblem zu umgehen ;)

Die Frage ist für mich noch: sollte man das RL-Netz vor-trainieren, oder lässt man es wirklich komplett "dumm" ?
wenn ich es vortrainiere, dann brauche ich sinnvolle ausgangswerte in form von wahrscheinlichkeiten und erwartungswerten. da bin ich grad dran, aber das ist komplizierter als man so denkt. man kann da meines erachtens nicht einfach irgendwelche %-wahrscheinlichkeiten für einen kniffel o.ä. nehmen, sondern das hängt stark vom wurf und von der runde ab....aber evtl. reichen ja auch schon ein paar "anhaltspunkte" damit das NN bei den ersten lernversuchen nicht völlig im dunkeln tappt?

spannend wird dann auch, wie ich das RL-netz später belohne oder bestrafe. das ist dann ja nochmal ein anderes thema. aber evtl. nimmt man da dann einfach die erzielte gesamtpunktzahl oder die abweichung +/- vom stat. erwarteten mittelwert (bei kniffel: 245,87 punkte).
aber das ist ein problem, mit dem ich mich dann beschäftige, wenn ich soweit bin ;)

ciao
phil

just4phil
Posts: 30
Joined: Mon 24. Oct 2011, 21:20

Re: "Richtige" Netzarchitektur für das Spiel KNIFFEL ?

Postby just4phil » Fri 28. Oct 2011, 10:13

Admin wrote:1.) Codierung momentaner Wurf (immer bestehend aus den Augenzahlen der fünf Würfel)
a) Netz nach gezeigter Augenzahl sortiert vorlegen

ok

Admin wrote:b) Jeden der fünf 'sortierten Würfelplätze' mit sechs Neuronen ausstatten. Der Wurf als Ganzes besteht damit also aus 5 * 6 = 30 Neuronen

ok

Admin wrote:2.) Codierung der zu füllenden Datenfelder
Hier würde ich für jedes Feld zwei Neuronen anlegen:
a) Spielbarkeit: 0 = Nicht mehr spielbar, 1 = spielbar

ok

Admin wrote:b) Wert: 0 Wenn gestrichen, sonst erzielter Feldwert

ok, aber: wenn bei 2.a spielbarkeit = 1, dann steht hier bei 2.b trotzdem eine 0, oder kann man Neuronen auch einen „leeren“ wert übergeben (also 0: wenn gestrichen oder noch spielbar)

Admin wrote:3.) Codierung der Aktionen
a) Ein Neuron für 'Setzen' ( = 0) oder 'Nochmal würfeln' ( = 1)

ok, ich hätte es hier umgekehrt gemacht, aber das ist dem Netz wahrscheinlich völlig egal?
Hier habe ich allerdings bedenken, da ich dann ja immer 2 zustände abfragen muss:
Wertigkeit von strategie x in kombination mit setzen = 0
Und
Wertigkeit von strategie x in kombination mit setzen = 1

Macht das sinn, oder sollte man die frage, ob gesetzt werden soll, besser aus dem netz rausnehmen und in die übergeordnete programmlogik verlagern?
Hier ist die Abfrage noch machbar. Schlimmer wird es doch wahrscheinlich mit den zu entnehmenden Würfeln!? (s. 3.c)

Admin wrote:b) Für jedes Datenfeld aus 2. ein weiteres Neuron, das auf 1 gesetzt wird, wenn das Wurfergebnis auf dieses Feld gesetzt werden soll. Diese Neuronen zeigen also das gewählte Setzfeld an, wenn das Neuron aus a) mit 0 (= Setzen) belegt ist. Ansonsten sind diese Neuronen immer 0.

ok

Admin wrote:c) Für jeden 'sortierten Würfelplatz' ein weiteres Neuron, das auf 1 gesetzt wird, wenn dieser Würfel zurück in den Becher soll (also auch nur wenn das Neuron aus a) mit 1 (= Nochmal würfeln) belegt ist.

Ok, aber ist das nicht ein großes problem!? -> das bedeutet doch, dass ich in der übergeordneten programmlogik sehr viele permutationen abfragen muss, um diejenige mit der höchsten Wertigkeit zu finden:
Wertigkeit von strategie x in kombination mit würfel 1 = rein oder raus

Kombiniert mit dem neuron „setzen“ wird das ja ein exponentieller aufwand!!?
(oder bin ich jetzt total auf dem holzweg??)
Wenn mein einwand korrekt ist, dann sollte man das lieber mit der übergeordneten programmlogik lösen?

Admin wrote:d) Ein Neuron, das 'Streichen' bedeutet. Wird immer in Zusammenhang mit einem der Neuronen aus b) verwendet, das anzeigt, welches Feld als Kandidat zur Streichung ausgewählt werden soll.

Hm,.. ist das nicht überflüssig? „Streichen“ ist doch eigentlich nichts anderes, als das „Setzen“ von 0 punkten.

Admin wrote:4.) Codierung 'Nummer aktueller Wurf': Hier bin ich mir nicht schlüssig, ob man ein Neuron (Werte 0 bis 2) oder mehrere Neuronen nehmen soll. Ich würde fast zu drei Neuronen tendieren oder auch zu zwei Neuronen, die binärcodiert die Wurfnummer abbilden können (0/0, 0/1, 1/0)

Ok, entscheide mich für 3 Neuronen, aber wie kodiert man das am besten: Beispiel Runde 3: 0 – 0 – 1 oder 1 – 1 – 1 ?
(also pro gespielte Runde bleibt die 1 stehen oder nur das Bit für die aktuelle Runde setzen?)

ciao
phil

User avatar
Admin
Site Admin
Posts: 438
Joined: Sun 16. Nov 2008, 18:21

Re: "Richtige" Netzarchitektur für das Spiel KNIFFEL ?

Postby Admin » Fri 28. Oct 2011, 12:14

just4phil wrote:Die Frage ist für mich noch: sollte man das RL-Netz vor-trainieren, oder lässt man es wirklich komplett "dumm" ?

Ich würde keine händisch erzeugten Daten vorab in das System reinstecken? Warum nicht ganz dumm anfangen, um so besser kann man sehen, wie sich der Agent verbessert. Außerdem könnte man durch suboptimale Vorgaben einen optimalen Lernprozess vereiteln.

Ganz wichtig ist bei RL folgendes Verständnis:
Wenn eine Aktion a im Zustand s getätigt wurde, dann erreicht der Agent als Reaktion darauf einen Zustand s' und erhält die Belohnung (den 'reward') r.

Nun wird die sogenannte Q-Function (die Funktion, die einem Zustand-Wertepaar einen Wert zuordnet) angepasst und zwar für das Wertepaar a|s: Dies geschieht auf Basis von zwei Komponenten:
1.) Erhaltener reward r nach dem Ausführen von a in s
2.) Geschätzter Maximalwert, der beim Ausführen einer potentiellen nächsten Aktion a' vom neuen Zustand s' aus erzielt werden kann: Qmax(s')

Nr. 1 ist einfach, das könnte bei Kniffel die erreichte Punktzahl nach einer jeden Aktion sein (0 bei Aktion = Nochmal würfeln oder Streichen, erzielter Feldwert bei Aktion = Setzen. Man könnte für das Streichen alternativ auch eine negative, konstante Belohnung anwenden).

Nr. 2 hat es ein bisschen in sich: Man sucht sich von allen möglichen Aktionen a' im neuen Zustand s' die Aktion mit der maximalen Wertigkeit heraus. Diese Wertigkeit Qmax(s') ist die erwähnte Komponente Nr. 2. Das bedeutet, man muss das Netz im Zustand s' zu allen dort möglichen Aktionen a' befragen und dadurch das Maximum der Q-Function herausfinden.

Nun wird die Q-Function für das Wertepaar s/a so angepasst, dass sie weiter in Richtung (Komponente 1 + Komponente 2) rückt.
Bei Einsatz eines neuronalen Netzes zur Abbildung der Q-Function bedeutet das, dass man ein neues Trainingsmuster erzeugt, das als Input s|a hat und als Output r + gamma * Qmax(s').

Somit überträgt sich die Wertigkeit eines Zustands sukkzessive zurück auf seinen jeweiligen Vorgänger. Deshalb funktioniert RL auch wenn eine Belohnung/Bestrafung nur ab und zu erfolgt (im Grenzfall nur am Ende jedes Spiels).

gamma ist dabei zwischen 0 und 1 zu wählen. Bei Werten in der Gegend von 0 richtet sich der Agent vorwiegend nach kurzfristiger, auf die direkte Aktion erhaltene Belohnung. Werte gegen 1 erzeugen einen weitsichtigeren Agenten, der eher auf zukünftige Belohnungen hinarbeitet.

Für ein vollständiges Bild ist außerdem noch sehr wichtig, dass zu Anfang (solange der Agent noch sehr dumm ist), nicht immer die höchstwertige Aktion ausgeführt werden soll, sondern mit einer gewissen Wahrscheinlichkeit die Auswahl der auszuführenden Aktion per Zufall geschehen muss. Das führt dazu, dass der Agent 'experimentiert' oder 'herumprobiert'. Man nennt das im RL-Jargon 'Exploration'. Nur so erarbeitet sich der Agent neue Wege, die seine Q-Function an die Realität anpassen. Je besser der Agent wird, um so seltener sollte die Zufallsauswahl benutzt und stattdessen die maximalwertige Aktion ausgeführt werden ('Exploitation').

In einem zweiten Post dann noch etwas mehr zu den Codierungsfragen...

Viele Grüße
Thomas Jetter

User avatar
Admin
Site Admin
Posts: 438
Joined: Sun 16. Nov 2008, 18:21

Re: "Richtige" Netzarchitektur für das Spiel KNIFFEL ?

Postby Admin » Fri 28. Oct 2011, 12:14

just4phil wrote: Admin hat geschrieben:3.) Codierung der Aktionen
a) Ein Neuron für 'Setzen' ( = 0) oder 'Nochmal würfeln' ( = 1)


ok, ich hätte es hier umgekehrt gemacht, aber das ist dem Netz wahrscheinlich völlig egal?

Ja, wie rum ist natürlich völlig egal.

just4phil wrote:Hier habe ich allerdings bedenken, da ich dann ja immer 2 zustände abfragen muss:
Wertigkeit von strategie x in kombination mit setzen = 0
Und
Wertigkeit von strategie x in kombination mit setzen = 1


Ich glaube, der Begriff 'Strategie' macht hier Probleme, weil er als Netzinput so nicht existiert. Vielleicht sollten wir von diesem Wort etwas etwas abrücken und uns auf das beschränken, was das Netz als Bewertungsgrundlage hat: Einen Zustand s und eine Aktion a.

Zustand:
- erzielte Ergebnisfeldwerte
- Belegtzustand von Erbegnisfeldern
- Momentaner Wurf (Augenzahlen der fünf Würfel)
- Momentane Wurfnummer

Mögliche Aktionen:
- Nochmal würfeln in Kombination mit einer Würfelauswahl (hier gibt es einige Permutationen)
- Setzen in Kombination mit einem der Ergebnisfelder (so viele Permutationen wie es mit dem momentanen Wurf kompatible, nicht belegte Ergebnisfelder gibt)
- Streichen in Kombination mit einem der Ergebnisfelder (so viele Permutationen wie es mit dem momentanen Wurf inkompatible, nicht belegte Ergebnisfelder gibt)

Wie man sieht, benötigt man zur Ermittlung der Wertigkeit der Aktion 'Nochmal würfeln' kein Ergebnisfeld. Die Ergebnisfeldauswahlneuronen (zum Setzen bzw. Streichen) werden alle konventionsgemäß auf 0 gesetzt, wenn es um die Bewertung von 'Nochmal würfeln' geht.

just4phil wrote: Admin hat geschrieben:b) Für jedes Datenfeld aus 2. ein weiteres Neuron, das auf 1 gesetzt wird, wenn das Wurfergebnis auf dieses Feld gesetzt werden soll. Diese Neuronen zeigen also das gewählte Setzfeld an, wenn das Neuron aus a) mit 0 (= Setzen) belegt ist. Ansonsten sind diese Neuronen immer 0.


ok

Admin hat geschrieben:c) Für jeden 'sortierten Würfelplatz' ein weiteres Neuron, das auf 1 gesetzt wird, wenn dieser Würfel zurück in den Becher soll (also auch nur wenn das Neuron aus a) mit 1 (= Nochmal würfeln) belegt ist.


Ok, aber ist das nicht ein großes problem!? -> das bedeutet doch, dass ich in der übergeordneten programmlogik sehr viele permutationen abfragen muss, um diejenige mit der höchsten Wertigkeit zu finden:
Wertigkeit von strategie x in kombination mit würfel 1 = rein oder raus

Kombiniert mit dem neuron „setzen“ wird das ja ein exponentieller aufwand!!?
(oder bin ich jetzt total auf dem holzweg??)
Wenn mein einwand korrekt ist, dann sollte man das lieber mit der übergeordneten programmlogik lösen?


Wie oben dargestellt, wird die 'Strategie' (besser finde ich 'Ergebnisfeld') in Kombination mit der 'Nochmal würfeln' Bewertung nicht benötigt.
just4phil wrote: Admin hat geschrieben:d) Ein Neuron, das 'Streichen' bedeutet. Wird immer in Zusammenhang mit einem der Neuronen aus b) verwendet, das anzeigt, welches Feld als Kandidat zur Streichung ausgewählt werden soll.


Hm,.. ist das nicht überflüssig? „Streichen“ ist doch eigentlich nichts anderes, als das „Setzen“ von 0 punkten.

Das ist prinzipiell richtig, ich würde aber auf keinen Fall Aktionen und Zustand in den selben Neuronen vermischen. Ein Neuron sollte immer exakt einer Bedeutung zugewisen sein: Entweder repräsentiert es immer einen Aspekt des Zustands oder immer einen Aspekt einer Aktion. Die zu setzende '0' lässt sich ja momentan nirgends abbilden: Das Würfelbild ist Teil des Zustands und sollte nicht im Zuge eines Aktionsaspekts auf 0 gesetzt werden. Der enthaltene Wert eines Ergebnisfeldes ist ebenfalls Teil des Zustands un nicht einer Aktion. Also würde ich ein 'Streichen'-Neuron einführen, das in Kombination mit einer Ergebnisfeldauswahl eine Aktion repräsentiert.

just4phil wrote:Ok, entscheide mich für 3 Neuronen, aber wie kodiert man das am besten: Beispiel Runde 3: 0 – 0 – 1 oder 1 – 1 – 1 ?
(also pro gespielte Runde bleibt die 1 stehen oder nur das Bit für die aktuelle Runde setzen?)

Ich denke, dass das egal ist.

Viele Grüße
Thomas Jetter


Return to “Hilfe zu konkreten Projekten”