GTA-Place - Di 25.11.08 13:26
Titel: Faktorverbesserung bei KI

---

Hallo,

hier gibt es ja den sehr ausführlichen Thread mit alzaimar über Künstliche Intelligenz bei einem, ich glaube, Bauernspiel. Ich hatte das vor einiger Zeit mal übernommen und umgeschrieben, nun geht es aber ans Optimieren und da hab ich aus dem Thread nicht das herauslesen können, was ich brauche. Nehmen wir an, ich habe 5 verschiedene Faktoren. Ich lasse also Computer gegen Computer spielen, einmal mit den alten Faktoren, einmal mit neuen Faktoren. Gewinnen die neuen Faktoren, werden diese übernommen.

Wie aber generiere ich diese neuen Faktoren um auf ein Optimium zu kommen? Wenn es nur ein Faktor ist, bei Integer zwischen -50 und +50, so könnte man ja noch den Zufall zu Hilfe nehmen, dann wäre man nach spätestens 100 Durchgängen beim Optimum. Wie sieht das aber bei 5 Faktoren, beginnend bei 0, 0, 0, 0, 0?

Hat mir da einer einen Ansatz?

Grüße
GTA-Place

alzaimar - Di 25.11.08 13:59

---

Hiho, ja. Hab ich.

1. Such Dir einen Parameter (ein 'Gen') per Random aus.
2. Verändere dieses Gen um GRANDOM(X), wobei GRANDOM(X) eine Funktion ist, die einen zufälligen Wert im Interval [-X,X] zurückliefert, der aber innerhalb dieses Intervals wie eine Glockenkurve verteilt ist, d.h. kleine Werte kommen also viel häufiger vor, als große. Das simuliert die Mutation in der Natur, die in der Regel auch nur minimale Änderungen vornimmt, aber sehr selten eben extreme Sprünge macht, um z.B. aus einem lokalen Maximum herauszukommen.
[edit] das geht endlos so weiter. Evolution terminiert NIE

Wenn Du das Ziel objektiv definieren kannst, dann reicht diese Strategie. Bei Spielen kann man das nicht, aber man kann wenigstens sagen, das ein Mutant seinen Vater besiegt. Das heißt ja nicht, das der Mutant besser als ALLE Vorgänger ist.
Daher sollte man immer mal wieder einen Mutanten gegen seinen Urururururur....großvater antreten lassen (50-100 Generationen früher). Es kann sein (und kommt häufig vor), das der Mutant haushoch verliert, weil z.B. eine einzige Strategie optimiert wurde, die aber eben doch ziemlichr Schrott ist..

Ich würde nicht unbedingt nur 100 Werte für ein 'Gen' zulassen, sondern ruhig ein paar mehr.

Viel Spass.

GTA-Place - Di 25.11.08 14:16

---

Mal schnell nachgeguckt gehabt: So was wie Gausche Glockenkurve / Normalverteilung? Du sagst, das Gen wird um einen zufälligen Wert geändert. Heißt das also "Wert_neu = Wert_alt + Wert_zufall" oder "Wert_neu = Wert_zufall"? Danke :)

alzaimar - Di 25.11.08 14:20

---

Wert := Wert + Zufallswert; // Zufallswert kann eben < 0 sein (und ist es in 50% der Fälle)
Du könntest aber die 'Großen Mutationen' auch so programmieren, das dann selten zwei oder mehr Gene verändert werden.

Das ist ja kein starrer Algorithmus, experimentiere doch ein wenig herum. Ich glaub auch nicht, das meine Ideen supertoll waren. Vermutlich ist die Forschung da mittlerweile wesentlich weiter.

BenBE - Di 25.11.08 14:34

---

Schau Dir mal Schwarmverhalten an ;-) Du generierst dir eine ganze Reihe von KIs (mit unterschiedlichen Parametern) und schaust nach, welche KIs gegen welche gewinnen. Jetzt brauchst Du ein Bewertungskriterium (möglichst stetig, digital geht aber auch zur Not), und trägst nun im 6D-Raum (deine 5 Kriterien + 1 Wert-Domain) deine Nun generierst Du immer so neue Parameter, dass sich diese poentiell immer in Richtung der höheren Bewertungsmerkmale bewegen.

GTA-Place - Di 25.11.08 19:51

---

Ich hab jetzt mal alzaimars Theorie aufgegriffen und als Normalverteilung die Funktion: e^(-1/3*x²) und das ganze entweder positiv oder negativ. Das funktioniert schon gar nicht schlecht, aber woher weiß ich jetzt, ob dies geeignet ist? Wie groß soll das Intervall sein? Der Koeffizient vor x²?


EDIT: Okay, ich habe mir mal die Glockenfunktion zeichnen lassen und hatte da natürlich einen Denkfehler drin. Ich habe diese jetzt auf 50 * e^(-1/30*x²) in einem Intervall von -15..+15. So erhalte ich, statt wie bisher Werte von 0-1, Werte von 0-50 und daher funktioniert das ganze deutlich besser. Siehe auch Anhang.

GTA-Place - Fr 28.11.08 15:23

---

Glockenfunktion in der Art war natürlich quatsch. Dadurch kamen ja große Werte häufiger als kleine. Abhilfe hat eine Funktion 3. Grades gebracht, die erst im letzten Moment bis auf +/-50 ansteigt/abfällt. Auch konnte ich das ganze nun auf meine KI übertragen. Noch bin ich allerdings skeptisch, ob das alles so ganz richtig funktioniert, denn Vektoren wie (-914, 51, 9, -89) kommen wir doch etwas utopisch vor :gruebel:

EDIT: Okay, ich denke ich weiß warum Vektor a immer weiter ansteigt. Die anderen Vektoren sind schon optimiert, da lässt sich nix mehr ändern. Die einzige Möglichkeit, dass der Computer gegen sich gewinnt ist also die Eröhung von Faktor a (eg Verniedrigung ins negative).

Martok - Fr 28.11.08 19:03

---

Dann sollte das Programm doch mal not-terminieren. Eigentlich ist dafür aber auch die Runde gegen n'te Vorfahren gut, um sowas rauszukanten.

Vermutlich haut dann aber was mit der Bewertungsfunktion nicht hin, sonst müsste eigentlich ein Zustand existieren der ein Maximum ist.

Oh und... BenBE hat Recht (mal wieder). Guck dir mal die Logik hinter Rosetta@home an, dort wird genauso vorgegangen. Im Endeffekt kann man sogar zugucken, wie die Accepted Solution immer weiter nach unten Links im Diagramm wandert und an bestimmten Orten unscharfe Felder bringt. Das sind die lokalen Optima. Hab grad keinen Job drin, sonst würd ich mal BildschirmSchießen ;)

GTA-Place - Fr 28.11.08 19:11

---

Ja die Bewertungsfunktion* war schrott, die hab ich grad mal komplett erneuert und eventuell muss ich noch das ein oder andere Bewertungskriterium einbauen. Ich guck mich jetzt aber mal Rosetta@home an, bzw. wie das in meinem Fall hilfreich sein könnte.


*Ich weiß nicht genau, welche du meinst: Die von der KI (Stellungsbewertung) oder die Bewertung, welche Faktoren besser sind.

Hidden - Fr 28.11.08 22:05

---

Hi :)

Bei Lernvorgängen unseres gehirns ist es so, dass die Abweichung in frühen Phasen sehr groß ist; später wird sie sehr klein.

Wir tasten uns also förmlich in immer kleiner werdenden Schritten an das Optimum heran. Das halte ich hier doch für relativ nützlich.

mfG,

GTA-Place - Sa 29.11.08 10:12

---

Ich habe mir gerade nochmal den Thread über die KI angeguckt und alzaimar hatte erwähnt, dass es in Math eine Zufalls-Funktion geben müsste, die nach der Gaußschen Verteilung arbeitet. Dem ist tatsächlich so, wobei Zahlen um Mean (= 0) häufiger kommen als andere. Dazu gibt es ja noch den 2. Parameter standard deviation. Ich könnte also mit einer großen Standard-Abweichung anfangen und da immer kleiner werden. Das würde den Effekt, den Hidden beschreibt, erzeugen.

GTA-Place - Do 04.12.08 16:15

---

Ich finde die Ursache nicht: Wenn ich mir bei der Evolution die Bewertung ausgeben lasse, die der Computer als die beste gefunden hat, dann ist das aus irgendeinem Grund immer abwechselnd positiv / negativ. Beispiel: Rot ist dran, Bewertung +54; Schwarz ist dran, Bewertung -54; Ich übergebe aber immer den richtigen Spieler und trotzdem dieses abwechselnde. Ist das normal?

EDIT: In Move.mScore steckt dann der selbe Wert.

BenBE - Do 04.12.08 16:58

---

Bei einem MinMax-Basierten Verfahren würd ich das mal als korrekt bewerten, schließlich ist für Player 2 es ganz schlecht, was für Player 1 ein Vorteil ist ;-)