KI: Verstärkendes Lernen

Am Beispiel: Das Nim-Spiel

Das Nim-Spiel ist ein Spiel für zwei Personen, bei dem abwechselnd eine Anzahl von Gegenständen (zum Bespiel Streichhölzer oder Münzen), die zu Beginn auf dem Tisch liegen, weggenommen werden. Nennen wir die beiden Spieler Alice und Bob.

Das Spiel gibt es in verschiedenen Varianten; eine davon wollen wir auf der folgenden Seite näher untersuchen.

Eine andere Version werden wir dann auf der dritten Seite in ein Python-Programm umsetzen.

Hier siehst du 5 Münzen auf dem Tisch.

Spielregel:

Die beiden Spieler spielen abwechselnd. Wer an der Reihe ist, darf eine oder zwei Münzen nehmen. Derjenige Spieler, der die letzte Münze (oder die letzten Münzen) vom Tisch nimmt, hat verloren.

Zunächst schauen wir uns eine mögliche Spielrunde an. Alice und Bob spielen gegeneinander; Alice beginnt.

		Alice findet 5 Münzen vor. Sie nimmt eine Münze weg.
		Jetzt ist Bob an der Reihe; er sieht also auf dem Tisch noch 4 Münzen liegen.  Er beschließt, zwei Münzen zu nehmen.
		Alice sieht jetzt zwei Münzen und nimmt eine weg.
		Jetzt wird Bob verlieren. Er muss jetzt die letzte Münze vom Tisch nehmen.

Auftrag

Spiel das Spiel einige Male. Hast du eine Idee für eine Gewinnstrategie?

Der klassische Ansatz

Vielleicht kannst du jetzt eine Regel formulieren, wieviele Münzen man jeweils nehmen muss, um zu gewinnen. Genau das führt zu der herkömmlichen Art, ein Computerprogramm zu entwerfen, in dem diese Regeln eingebaut (implementiert) sind.

Man muss also das Spiel gut beherrschen, also ein Experte werden, und in der Lage sein, Regeln zu formulieren, die einem Spieler mitteilen, welcher Zug in einer bestimmten Situation vorteilhaft ist.

Eine solche Regel könnte dann z.B. lauten: 

Wenn du 4 Münzen vorfindest, solltest du 2 Münzen wegnehmen!

Aber ob diese Regel wirklich optimal ist? Wenn du ein wirklicher Experte bist, erkennst du, dass es nicht wirklich klug ist, diese Regel zu befolgen.

Auftrag

Begründe, wieso es nicht sinnvoll ist, zwei Münzen zu nehmen, wenn auf dem Tisch noch zwei Münzen liegen.

Regeln aufzustellen, die mir in jeder Situation sagen, wie viele Münzen man wegnehmen soll, ist offenbar schwierig.

Wir gehen jedoch einen anderen Weg, um solche Regeln zu finden.

Der Computer wird trainiert

Wir wollen jetzt im nächsten Schritt den Computer selber lernen lassen, das Spiel möglichst optimal zu spielen. Trainieren!