Künstliche Intelligenz

[Samuel72]

Hallo zusammen,

das Thema künstliche Intelligenz interessiert mich momentan.

Meine konkrete Aufgabe ist dabei: Der Computer soll im Schachspiel mit Turm und König gegen König matt setzen.

Mit folgendem Ansatz habe ich das sogar hinbekommen:
Weise jeder Stellung einen Wert zu:
Matt ist ein sehr hoher Wert;
Patt oder wenn mein Turm geschlagen wird ist ein sehr niedriger Wert.
Ansonsten ist der Wert umso höher, je näher der gegnerische König in der Ecke ist
und je näher mein König am gegnerischen König dran ist.

Nun muss ich nur noch zwei Züge tief alle Möglichkeiten durchspielen und dann (mit der Minimax-Methode) denjenigen Zug auswählen, der den höchsten Wert erzwingt.

Aber hier kommt nun meine Frage:
Wie bekomme ich es hin, dass der Computer selber lernt, welche Stellung einen höheren Wert hat,
dass er also lernt, dass er seinen Turm nicht schlagen lassen darf,
dass er mich nur am Rand matt setzen kann und mich deswegen an den Rand drängen muss,
dass er dafür Turm und König braucht?

Ich bin kein Informatiker sondern absoluter Autodidakt.
Für Hinweise, in welcher Richtung ich nach einer Lösung suchen kann (evtl. ein gutes Buch...) wäre ich dankbar.

 

[Tobse]

Wenn es um KI geht, ist der Ansatz, den lernenden Computer mit König und Turm gegen einen logisch vorgehenden König spielen zu lassen. Nach sehr vielen Spielen hast du dann empirische Daten, mit denen du ein neuronales Netz füttern kannst. Der Computerspieler weiss dann aus Erfahrung, welcher Spielzug in welcher Situation der beste ist, weil er alle/viele der Möglichen Ergebnisse kennt.
Das ist die Art, auf die unser Gehirn funktioniert (wobei unser Gehirn auf die selbe Weise die Regeln lernt und damit Züge im vorraus abschätzen kann).

Der weniger KI-Mäßige Ansatz ist, dass der Computer selbst keine Intelligenz besitzt sondern nur einen guten Algorithmus ausführt. Wenn du also ein paar Regeln hast, nach welchen Turm und König vorgehen können, um den König auf jeden Fall zu schlagen, musst du sie nur ein eine Programmiersprache übersetzen und fertig. Ändern sich die Regeln kann der Computer sich dann aber nicht selbst anpassen, weil die ganzen Regeln und Logiken ja in der Programmierung stecken.

 

[CSHW89]

Eine andere Möglichkeit, die allerdings auch nichts mit ki zu tun hat, ist eine Endspieldatenbank zu benutzen oder selbst zu programmieren. Dazu erstellt man alle Stellungen auf dem Schachbrett die bereits Schachmatt sind. Dann schaut man sich alle möglichen "Rückwärts-Züge" an und speichert bei jeder Stellung den Zug, der zum Matt führt. Das macht man solange, bis man alle Stellungen einmal betrachtet hat. Am Ende hat man für jede Stellung den bestmöglichen Zug und am schnellsten zum Matt zu kommen.

 

[Samuel72]

Hallo zusammen,

vielen Dank für die Antworten.
Wie gesagt, ich habe bereits eine funktionierende Lösung programmiert.
Mir geht es darum, anhand dieses Beispiels etwas über KI zu lernen.
Da scheint mir der Hinweis auf neuronale Netze am vielversprechendsten.
Allerdings weiß ich über neuronale Netze nur, dass sie oft im Zusammenhang mit KI genannt werden.

Also konkret:
Ich habe jetzt den Computer 1000 Spiele durchspielen lassen, wobei beide Spieler rein zufällig ziehen.
Abbruchbedingungen waren: Matt, Patt oder mehr als 1000 Züge
Ergebnis:
>1000: 987 mal
Matt: 11 mal
Patt: 2 mal
Gedauert hat das Ganze 27 Sekunden.

Wie muss ich nun vorgehen, um ein neuronales Netz zu erstellen und dieses mit den Daten zu füttern...
Gibt es da vielleicht ein gutes Buch, das mir weiterhilft?

 

[javampir]

gegen einen logisch vorgehenden König

vorsicht, das habe ich anders verstanden, du meinst:

beide Spieler rein zufällig

ich denke, das das nicht der richtige ansatz ist. ansonsten kenne ich mich aber auch nicht mit neuronalen netzen aus.

 

[Tobse]

Also das Ziel ist ja, dass der Spieler mit Turm und König empirisch lernt, wie er den König besiegen kann. Ob der König logisch oder zufällig spielt ist dafür erstmal zweitrangig, wobei erstere Methode fehlerhafte Ergebnisse liefern kann, wenn die Spiellogik des Königs nicht korrekt ist und letztere Methode mehr durchläufe benötigt, um den selben Lerneffekt zu erzielen.

@TE:
Das Neuronale Netz kann auf viele Verschiedene Wege funktionieren. Es geht im ersten Schritt darum, die kombinationen aus Spielsituation und darauf folgenden Spielzügen zu finden, die für das Ergebnis wichtig sind.
Beispiel:
Es gibt jetzt eine Situation S, auf die der KI-Spieler mit vielen verschiedene Reaktionen R reagieren kann. Das Neuronale Netz muss jetzt, über viele wiederholungen, lernen, welche Reaktion R auf S zuträglich, neutral oder gegenläufig dem Matt-Setzen des Königs sind.
Ein Simpler Ansatz dafür ist z.B. dashier: https://de.wikipedia.org/wiki/Ameisenalgorithmus (wobei das jetzt nicht direkt mit einem Neuronalen Netz umgesetzt werden muss).

 

[Dukel]

Evtl. findest du in diesem Artikel etwas brauchbares:
http://www.golem.de/news/deep-learning-maschinen-die-wie-menschen-lernen-1510-116468.html

 

[Samuel72]

Vielen Dank für die Anregungen.

Ich bin jetzt folgendermaßen vorgegangen:

Ich habe eine Map<Stellung, Zug>.

Ein Spiel läuft so ab: (Der Computer ist schwarz)
Weiß zieht zufällig
Schwarz zieht den Zug aus der Map (sofern vorhanden), ansonsten zufällig.
das Spiel wird wiederholt, bis eine Ende-Bedingung eintritt: Matt, Patt oder >100 Züge.

Ist das Spiel gewonnen, wird zu jeder durchlaufenen Stellung der jeweils gemachte Zug in die Map eingetragen.
Ist das Spiel nicht gewonnen, wird zu jeder durchlaufenen Stellung der jeweils gemachte Zug aus der Map gelöscht.

Dieses Verfahren habe ich noch verfeinert:
Wenn eine Stellung (mit Zug) in die Map eingetragen werden soll, die schon vorhanden ist, bekommt dieser Eintrag Gewichtungsfaktor +1.
Anstelle eine Stellung (mit Zug) zu löschen, wird der Gewichtungsfaktor um eins reduziert; erst wenn dieser Null ist, wird der Eintrag gelöscht.

Auf diese Weise habe ich schon nach 500000 durchlaufenen Stellungen eine Gewinn-Quote von 90% - ziemlich cool!

 

[Tobse]

Ich gratuliere und du hast es erstaunlich simpel gelöst ich hätte da wieder zwanzig Probleme erfunden, dies nicht gibt...
viel spaß weiterhin mit der Thematik!

 

[Samuel72]

Danke, Tobse, für das schöne Lob.
Allerdings bin ich nicht ganz so zufrieden.
Die Turm-Strategie stagniert auf 90% Erfolg.

Ich habe mal probiert, mit Springer und Läufer matt zu setzen.
Das Ergebnis ist ernüchternd:
Beide Spieler wählen zufällig einen aus den möglichen Zügen aus.
Abbruchbedingungen sind: Matt, Patt, >100 Züge und Figur geschlagen.
Das Ergebnis nach 2Mio Spielen:
124 x Matt
12494 x Patt
136866 x über 100 Züge
1850516 x Figur geschlagen.

Da brauche ich erst gar nicht anfangen, den Computer lernen zu lassen, da es einfach zu wenige Erfolge sind. (Und mit vier Figuren sind es auch erheblich mehr mögliche Stellungen.)
Natürlich könnte ich dem Computer sagen, dass er seine Figuren nicht schlagen lassen darf - aber genau solche Sachen sollte er ja eigentlich lernen.

Ich glaube, eine große Schwierigkeit ist eben, dass man nicht davon ausgehen kann, dass der Gegner logisch = vorhersagbar zieht, sondern einen zufälligen Zug annehmen muss, was dann zu einer unheimlich großen Verzweigung führt.

 

[Tobse]

Ich würde mal versuchen, deine Definition von Stellung zu abstrahieren. Die gleiche anordnung der 3-4 Spielfiguren kann ja in verschiedenen Positionen auf dem Feld auftreten, was aber nicht zwangsläufig bedeutet, dass das optimale Verhalten in jeder dieser Stellungen anders ist.

Bleiben die 90% erfolg auch, wenn du mit den Lern-Daten von vorn zu messen beginnst?

 

[Samuel72]

Hallo Tobse,

was die Turm-Strategie anbelangt, so meine ich nun zu wissen, wo der Fehler lag:
Die Verfeinerung bewirkt zwar eine erhebliche Steigerung der Lern-Geschwindigkeit, aber dadurch können sich falsch gelernte Züge leider verfestigen, z.B.:
Schwarz: Kg4, Tf8; Weiß: Kg2
Schwarz zieht Tf2+.
Nun hat Weiß drei Möglichkeiten: Kxf2, Kg1 und Kh1.
Wenn man davon ausgeht, dass Schwarz nach Kg1 und Kh1 korrekt matt setzt, so bedeutet das, dass der Gewichtungsfaktor des falschen Zuges Tf2+ zweimal erhöht und einmal reduziert wird.
Die Lösung ist denkbar simpel: Ich reduziere den Gewichtungsfaktor um einen Wert, der anfangs 1 ist, aber dann umso höher wird, je höher die Erfolgsquote ist.
Auf diese Weise bin ich nun (nach ca. 2h Rechenzeit und 3Mio Durchläufen) auf ca. 98.5% Erfolg.

Was das Läufer-Springer-Problem anbelangt, so glaube ich nicht, dass die Zufall-Methode zum Erfolg führen kann. Wie gesagt: 124 Matt auf 2 Mio Spiele - und (ohne mir das jetzt angeschaut zu haben) ich fürchte, die allermeisten der 124 Matts sind auch noch falsche Matts, d.h. der weiße König läuft (etwa in der falschen Ecke oder gar am Rand) in ein Matt hinein, obwohl er auch leicht einen anderen Zug hätte machen können.

 

[klauskarambulut]

Lass doch auch den gegnerischen König lernen, dann kannst du gegen einen intelligenten Gegner testen anstatt nur gegen Zufallszüge.

 

[Samuel72]

Hallo klauskarambulut,

ich habe deinen Vorschlag ausprobiert - es bewirkt tatsächlich eine Verbesserung: 24 Matt auf 120000 Spiele. Allerdings hat mein Computer drei Stunden dafür gebraucht. Ich glaube nicht, dass ich auf diese Weise zu einer Lösung komme.

Ich habe nun meinen ursprünglichen Ansatz wieder aufgegriffen,
jeder Stellung einen Wert zuzuweisen und dann so zu ziehen, dass man den höchsten Wert erzwingt (wobei Stellungs-Wiederholungen vermieden werden).
Ich bekomme es nun auch hin, mit Läufer und Springer matt zu setzen. (Aber das hat halt leider wenig mit KI zu tun).