Schach-KI mit neuronalen Netzen

[Ocram7]

Ich hatte mal vor, ein Schach-Programm zu entwickeln, dass ständig dazulernt und so immer stärker wird. Da kam ich dann natürlich schnell zu künstlichen neuronalen Netzen (Künstliches neuronales Netz ? Wikipedia).

Meine Idee war: Die KI speichert alle Stellungen eines Spiels. Wenn das Spiel zu Ende ist, wird jede Stellung mit einer Bewertung in die Datenbank eingetragen. Wenn sie dort schon steht, wird die Bewertung dort aktualisiert. Die Bewertung setzt sich zusammen aus Spielausgang (Sieg Weiß, Sieg Schwarz, Remis) und Zeitpunkt des Zuges. Bei einer Niederlage wird dann z.B. der 48. Zug schlechter gewertet als der 20.

Das hat auch ganz gut funktioniert. Es gibt da aber zwei Probleme:

1) Bei unbekannten Stellungen versagt das Programm komplett. Durch viel Training kann man natürlich erreichen, dass das Programm sehr viele Stellungen kennt.

2) Der Speicherbedarf ist sehr groß. In meiner Datenbank hatte ich später über 5 Mio. Einträge für die einzelnen Stellungen.

Deshalb ist dieser Ansatz wohl nicht so gut. Hättet ihr andere Ideen, wie man ein lernendes Schachprogramm (mit neuronalen Netzen) programmieren kann? Am besten wäre es natürlich, wenn das Programm mit Mustererkennung arbeitet, ich weiß nur nicht, wie.

Danke im Voraus!

PS: Diskussion in einem anderen Forum

[AndiE]

Hallo,

ich lann mir da nichts drunter vorstellen. Kannst du das genauer beschreiben, wie das Lernen funktioniert, und das Wissen abgespeichert wird?

[Ocram7]

Etwas genaues weiß ich ja auch nicht, deshalb frage ich ja. Aber ich hab ein paar Links, die müssten es relativ gut erklären:

Distributed Chess Project ? Rechenkraft

Neural Networks with Java: neural net overview

NeuralNetworkSolutions.com | Introduction to Neural Networks

Perzeptron ? Wikipedia

Mustererkennung ? Wikipedia

"Das Netz hat eine Eingabe"schnittstelle", nämlich eine Reihe von Knoten. Jeder dieser Knoten "berechnet" abhängig von seinen Eingangssignalen ein Ausgangssignal, das an alle Knoten der nächsten "Reihe" weitergegeben wird. Die letzte deiner (theoretisch beliebig vielen) Reihen ist dann das Ausgangssignal, das irgendetwas zu bedeuten haben soll. Deine Knoten "lernen", indem sie bei einer schlechten Bewertung des Ausgangssignals die Berechnung ihrer Knoten (leicht) ändern. Das hätte zur Folge, dass ein bestimmter Knoten (bei einer gleichbleibenden Eingangsbelegung) leicht variierte Werte an einen bestimmten Knoten der darunterliegenden Ebene geben würde."

"man hat mehrere schichten mit neuronen, wovon jede auf den input der davorliegenden reihe reagiert, den input irgendwie verarbeitet, und anschließend entsprechen dem ergebnis weitere neuronen anregt oder auch nicht.

führt das ergebnis nicht zum erfolg, geht man den weg zurück, und zieht den beteiligten neuronen eins über, und sie versuchen beim nächsten mal was anderes.

führt es zum erfolg, werden die verbindungen/berechnungsmethoden "stabiler", und halten mehr fehlschläge aus, bevor sie zerbrechen."

(Quelle: neuronales netzwerk in 3 sätzen)

Ich hoffe, das hilft dir/euch ein bisschen, zu verstehen, was ich meine.

[AndiE]

das lasse ich so nicht gelten. Du hast nach eigenen Angaben in deiner Datenbank über 5 Mio. Einträge. Wie kommen die da rein? Was enthalten die?

Zum Problem an sich. Gegeben ist eine Ausganggstellung. Sie ist das Anfangsneuron. Von ihr ausgehend können 20 Neuronen erregt werden, die die Zugmöglichkeiten darstellen. Sie führen zu 20 neuen Neuronen, die die Stellungen nach dem Zug darstellen. Nur die "Zug"-Neuronen können die Handlung beeinflussen. Gibt es ein Maximum, wird der Zug mit dem Maximum angewendet, ansonsten ein zufällig ausgewählter aus den darauf folgenden gleich bewerteten.

Angenommen die 64 Felder kennen die Figuren, die auf ihnen stehen. Da es möglich ist, dass 32 verschiedene Figuren auf einem Feld stehen, sind schon mal 2048 Eingangsknoten möglich. Diese wiederum führen zu N Stellungen. aus jeder dieser Stellungen ist wieder eine Endstellung berechenbar, für die es 64 x32 =2048 Möglichkeiten gibt. Das ist die Anzahl der Ausgabeknoten.

Eingangsknoten und Ausgabeknoten ergeben die Züge, so daß etwa 4 Millionen Züge möglich sind.

In obiger Rechnung ergibt das dann zu (64 über 32) = ganz viele Stellungen, die möglich sind.

Soweit mmeine Gedanken dazu.

[U-- °LoneWolf°]

zu 1) wenn das Programm bei unbekannten stellungen fehler verursacht wie sind die 5 Mio. den entstanden?

eventuell solltest du das Programm dann den rechnerschich besten zug machen lassen oder es einfach zufällig inene auswählen Da das Programm ja selbst lernen soll heist wenn stellung un bekannt mach zufalls zug mit figur x oder kontroliere bei welchem zug du zumindest keine figur verlierst

zu 2) naja ob bzw. wie die datenmenge verkleinert werden kann ist auch von deinem dazenmodel abhängig und das kenne wir ja nicht

[Ocram7]

Danke für eure Antworten!

Mein Programm funktionierte so: Bei einer unbekannten Stellung wurde ein Zufallszug gemacht, bei bekannten wurde eine Bewertung aus der Datenbank geholt.

Die Datenbank enthielt immer die Stellung (64-stellige Zeichenkette) und dazu eine Bewertung. Die Bewertung war ein Decimal-Wert. Je kleiner der Wert war, desto besser war der jeweilige Zug für Schwarz. Je höher der Wert, desto besser der Zug für Weiß. Wenn die weiße KI am Zug war, dann wurde z.B. ein Zug mit der Bewertung "5" genommen statt einem mit der Bewertung "-282".

Die Partie wurde so von KI gegen KI zu Ende gespielt. Wenn die Partie unentschieden endete, passierte nichts. Wenn Weiß gewonnen hat, wurden die Bewertungen zu allen Stellungen, die in dieser Partie vorkamen, vergrößert. Wenn Schwarz gewonnen hat, wurden sie verkleinert.

Bei diesem Modell braucht das Programm natürlich extrem viel Training, um stark zu werden. Am Ende des "Experiments" hatte ich dann 5 Millionen Einträge in der Datenbank, jeweils eine Stellung mit der entsprechenden Bewertung. Das Problem an diesem Modell war aber, dass es geschätzte 2,28*10^46 mögliche Stellungen gibt. Das wäre eine Zahl mit 47 Vorkommastellen. Ich hatte gerade mal 5 Mio. Stellungen, d.h. 7 Stellen vor dem Komma. So kommt man also nicht weiter.

Deshalb gefällt mir dein Ansatz viel besser, AndiE! Das ist genau das was ich meine mit einem neuronalen Netz. Mir ist aber erst mal nicht wichtig, wie viele Stellungen dann möglich wären bzw. wie viele Neuronen man bräuchte. Ich würde gerne wissen, wie man so ein neuronales Netz - wie du es beschrieben hast - für ein Schachprogramm erstellt.

Für deinen Ansatz würde ein Perzeptron (hab oben einen Link dazu geschrieben) reichen, oder?

Datei:Ffw perzeptron.jpg ? Wikipedia

Die "Input"-Schicht hätte 64 Neuronen, also für jedes Feld eins. Die "Output"-Schicht wäre die neue Stellung bzw. der optimale Zug. Aber was müsste in die "Hidden"-Schicht? Die Züge, so wie du es meintest? Oder Kriterien, die die Stellung bewerten? Dann könnten z.B. die Dame und der König das Neuron "Matt-Drohung" anregen, was dann die Stellung bewertet, oder?

Habt ihr vielleicht noch Vorschläge, wie man die "Hidden"-Schicht aufbauen könnte? Es wäre toll, wenn ihr mir noch mal helfen könntet.

[U-- °LoneWolf°]

Naja ich würde es bei der in wikipedia gezeigten darstellung anders ausdrücken

INPUT ist die Aktuelle stellung

ZWI Ermitlung MöglicherZüge

ZWII besten zug auswählen

OUTPUT der zu Spielende zug

Denkbar währe hier auf N züge vorraus zu schauen aber das macht das ganze denke ich doch etwas Komplizierter.

...

ich hoffe mal das ich das richtig verstanden habe, finde das ein sau interesantes thema macht z.B. auch bei der wissensvernetzung bzw. beim wissensmanagemnt sehr viel sinn

...

[Ocram7]

Ja, du hast das alles richtig verstanden. Ich finde das Thema auch total interessant, leider aber auch sehr kompliziert. Das tolle daran ist ja, dass man "nur" ein Mal einen Algorithmus schreiben muss. Danach trainiert das Netz sich selbst, indem es durch Feedback (beim Schach: Sieg, Remis oder Niederlage) seine Gewichtungen an den einzelnen Knoten automatisch anpasst.

Damit kann man fast alles machen, z.B. auch Text-/Schrifterkennung.

Hier hab ich noch drei interessante Links gefunden:

Neuronale Netze - Eine Einführung - Grundlagen

Neuronale Netze

Neuronale Netze

Hier sind auch noch mathematische Dinge zum Perzeptron:

http://wwwuser.gwdg.de/~mherrma/v0/node7.html

http://wwwuser.gwdg.de/~mherrma/v0/node14.html

http://wwwuser.gwdg.de/~mherrma/v0/node8.html

Eine gute Lernregel scheint das hier zu sein:

http://www.neuronalesnetz.de/hebb.html

Das mit dem Vorausschauen braucht man ja wirklich nicht. Es wäre schon super, wenn das ohne funktioniert.

Also dein Aufbau ist wirklich gut. So müsste es dann wohl aussehen. Hat denn jemand Ideen, wie man das konkret umsetzen könnte? Ich kann ja nicht in meiner Programmiersprache schreiben "NeuronalesNetz.Create(Schach)" oder so.

Wie kann man so etwas in einer Programmiersprache schreiben (egal welche)? Hättet ihr vielleicht ein paar Vorschläge (Pseudo-Code)?

Bearbeitet 27. Januar 2009 von Ocram7

[U-- °LoneWolf°]

naja die frage ist zu erst welche sprache?

aus gründen der performance würde ich zu C++ tendieren...

wobei es hier wieder drauf ankommt wo du die daten ablegst z.B. denkbar aber vermutlich auf grund der datenmenge unbrauchbar währe ein xml

andererseits ließe sich sowas auch durch iene datenbank oder dateistruktur (achtung da der keine reine hirachi hat muss man so zusagen verknüpfungen setzen)aufbauen...

bei einer datenbank würde ich mir 3 tabellen anlegen

Figuren

Stellungsliste

und Stelungszuornung in der die bei input X möglichen stellungen gespeichert sind

...

was die programmierung angeht würde ich mich an der ebne genanten strucktur entlang hangel

eine klasse schachKI mit einer funktion getnextTurn( stellung)

dem entsprechend brauchst auch noch eine datenstrucktur stellung ... eine stellung kann mehrere volgestellungen und mehrere vorgängerstellungen (diese sind aber eher uninteresant) haben. eventuel ist es auch interresant alte spiele zu speichern .... um irgendwann einen weiteren analysepunkt zu erhalten den die am besten bewertetet stellung ist nciht immer die richtige ...

[U-- °LoneWolf°]

hi noch kurz ein kleiner link hier hat sich auch jemand mirt dem thema auseinander gesetzt.

Die anzahl der möglichen züge im Schach scheint nahezu grenzenlos...

[U-- °LoneWolf°]

noch eine ergänzung edit geht leider nicht

Die anzahl der möglichen züge im Schach scheint nahezu grenzenlos...

hab mir gerade mal den spass erlaubt das mit excel auf zu arbeiten

Mögliche Positionen der figuren währen demnach 4,97275E+53

allerdings muss man hier noch einige abzihen da die berechnung davon ausgeht das jede figur auf jedem feld stehen kann(z.b. einbauer kann auf maximal 56 feldern stehen)

achja und die berechnung bezieht auch figuren ein die nicht mehr auf dem spielfeld sind

[Ocram7]

Also als Programmiersprache kämen für mich Delphi und PHP in Frage. Mehr kann ich nicht.

Da PHP ja weniger geeignet ist, werde ich wohl Delphi nehmen. Aber weil die Anzahl der möglichen Stellungen eben so groß ist, würde ich lieber gar nichts von den Stellungen speichern. Das neuronale Netz soll einfach nur Gewichte haben, die das Programm speichert. Nach jeder Partie soll das Netz die Gewichte anpassen. Das wars dann auch schon mit Daten, die gespeichert werden sollen.

Jetzt weiß ich nur noch nicht, wie ich das neuronale Netz realisieren soll (den Aufbau haben wir ja schon geklärt) und wie die Gewichte angepasst werden sollen (Lernformel). Vielleicht hat da noch jemand Ideen zu?!

[U-- °LoneWolf°]

hm ok jetzt hats klick gemacht ...

dann ist es eventuel besser wenn jede figur einen inputknoten darstellt als information erhält diese die positionen aller anderen figuren daraus ergibt sich die möglichkeit die eigen position im verhältnis zu den anderen figuren zu betrachten

nehemn wir als beispiel einen einfachen bauern.

der bauer bekommt die information aller figuren. von seiner position z.B. B2

kann er grunssätzlich auf B3 und B4 oder je nach positioen der anderen figuren auf A3 oder C3. Diese möglichen Positionen stellen die nächste ebene dar so das eine figur lediglich die für sie möglichen knoten ansteuert. die knoten gewichten im dann auf mir ist der bauer + 0 - also gute neutral oder schlecht. wenn dieser process für alle figuren abgeschlossen ist bekommst du n positiv bewertet positionen für jede figur auf der nächten eben musst du nun diese gegen einader gewichten z.B.

bauer B2 auf B3 hat 0

bauer D2 auf C3 hat +

ergebit D2 auf C3.

ist nur so ein gedanke der mir gerade durch den kopf geschossen ist...

und welche möglichkeiten bestehen z.B. nicht ziehen ziehen auf 1-n (diese wrhalten dann je nach auswirkung die gewichtung )

[AndiE]

Hallo,

ich würde erst einmal die gesamt UML-Schiene durchgehen. Aus dem User-Case "Ziehen" wird eine Aktivität. Die hat mehrere Ausgänge mit unterschiedlichen Folgen :Das Spiel endet bei Sieg, Remis oder Niederlage; der Gegner ist dran bei Zug oder "Schach"

Ich habe zwar lange nicht mehr gespielt, aber so würde ich das sehen:

Die Aktivität selbst würde etwa so funktionieren:

Stellung auf Gefahr durch den Gegner bewerten - Stellung auf eigene Zugmöglichkeiten bewerten - Zugauswahl - Zugausgabe- Endstellung? -(nein) - Schach? -(nein) - Gegner zieht

bei : Endstellung?- (ja)- Partie auswerten- usw.

An diese Aktivität müssen drei Datenstrukturen andocken: Die aktuelle Stellung, die aktuelle Partie, und die gelernten Bewertungsdaten.

Da Schach ein Ziel hat, muß man die Figuren auch bewerten. der König ist zwar relativ ungefährlich (8 Felder), hat aber die höchste Zielquote. Die anderen Figuren reihen sich dann ein.

Bei den neuronalen Netzen müsstest du auch die Abarbeitung der Programmschritte auch in neuronalen Netzen abbilden.

Ich würde eine Klasse "Neuron" schreiben, die eine Sammlung enthält, in der die mit ihm verbundenen anderen Neuronen stehen, sowie die Wichtung des Einganges. Das "Neuron" kann den Ausgangswert des Neurons abfragen, mit dem sie verbunden ist. Es kann selbst seinen Ausgangswert berechnen. Der Schellwert und die Wichtungen sind einstellbar.

Wichtig wäre, dass aus logischen Gründen immer nur ein "Token" durch das Netz wandert, jeder Neuronausgang also mit genau einem Eingag verbinden ist.

Wie die Neuronen entstehen, vergehen, verknüpft und ausgewertet werden, das bestimmt dann das benutzte Bewertungsmodell.

[Ocram7]

OK, danke für eure Hilfe. Ich habe mich jetzt für einen Aufbau entschieden:

385 Input-Neuronen (6 für jedes Feld + 1 für "Wer ist am Zug")

4096 Output-Neuronen (64 Zielfelder pro Quellfeld)

Das einzige, was mir jetzt noch fehlt, ist die Lernfunktion. Ich möchte das ja mit Temporal Difference Learning umsetzen. Dazu habe ich auch drei Sachen gefunden:

Grafik 1

Grafik 2

Grafik 3

Leider verstehe ich das trotz dieser Hilfen noch nicht ganz. Könnt ihr mir da vielleicht helfen? Könnt ihr mir sagen, wie ich das programmieren könnte? Vielleicht in Pseudo-Code?

Danke im Voraus!

[Pentagon]

Hallo... ich bin Eröffnungsbuchautor vom Programm Zappa

https://netfiles.uiuc.edu/acozzie2/www/zappa/

Habe da so ein Paar nette Ideen, denke die könnten dir behilflich sein in dem Punkt.

Also um ein Datenstau zu vermeiden kannst du ja folgendes machen.

Nach dem verlassen des Eröffnungsbuches gibt es in der regel 3-5 gute Züge, aber den 6-8 sind die schon zweifelhaft ( das ist so die Fausformel ). Dann gibt es wiederum Stellungen wo nur 1-3 Züge möglich sind, und der 4 Zug schon eine gravierender fehler ist. Das selbe kannst du auch bei den erwartetten zügen genau so machen, also den Multiponder ausnutzen. Warum die vermeidlich schlechten züge die der Computer in der Regel so oder so nicht machen wird ( sollte hehe ) sinnlos berechnen. Der efeckt dieser Idee ist das du dadurch sehr sehr schnelle in die tiefe kommen wirst. Also meine Idee basiert darauf das man eben die anderen züge die schlecht sind erst garnicht weiter anschaut um so den Datenstau zu umgehen. Klar kann man da auch mal einen Damenopfer übersehen weil der zug anfangs durch geringe rechentiefe als schlechter befunden wird. Da ssollte man aber auch umgehen können in dem Man eine grundsuche einführt. Die frage ist dann ab welcher tiefe hatt man eine Stellung taktisch abgesichert, denke so 14 ply sollten reichen bei den heutigen Rechnern.

Bye Pentagon