Nimm-Spiel

Dieses Programm ist eine einfache KI, die das Nimm-Spiel spielt. Damit kann einfach gezeigt werden wie das Training einer KI funktioniert.

Regeln

Auf einen Haufen liegen zwölf Hölzchen. Zwei Spieler müssen abwechselnd ein bis drei Hölzchen vom Haufen nehmen. Der Spieler, der das letzte Hölzchen nimmt, hat verloren.

Optimale Strategie

Wenn man dran ist und nur ein Hölzchen hat, hat man verloren, da man es nehmen muss. Wenn also zwei bis vier Hölzchen hat, kann man immer so viele Hölzchen wegnehmen, dass der andere nur noch eins hat, sodass er verloren hat und man selbst gewonnen. Mit fünf Hölzchen hat man dann wieder verloren, da man so viel Hölzchen wegnehmen muss, dass der andere zwei bis vier hat.

Dieses Muster setzt sich weiter fort und kann zu folgender Regel verallgemeinert werden: Hat ein Spieler n Hölzchen, dann gibt es für seiner Gegner eine Gewinnstrategie genau dann, wenn n \bmod 4 = 1.

Daraus resultiert die optimale Strategie, mit der man versucht so viele Hölzchen wegzunehmen, dass noch n \bmod 4 = 1 da sind. Wenn das nicht geht, da man selbst n \bmod 4 = 1 Hölzchen hat, ist es egal, was man macht. Diese Strategie habe ich in der Funktion optimal_move umgesetzt.

KI-Implementierung

Für die Implementierung der KI habe ich die Programmiersprache Python gewählt, da ich mit ihr vertraut bin. Dabei fängt die KI immer mit dem ersten Zug an, da sie sonst gar nicht gewinnen kann.

Training und Evaluation habe ich mit allen Kombinationen aus der optimalen und zufälligen Strategie gemacht, da es erstens interessant ist, ob die KI auch von einem Gegner, der schlecht spielt, gut lernen kann. Zweitens hätte es auch vorkommen können, dass, wenn man mit der optimalen Strategie trainiert, die KI bei der Evaluation mit der zufälligen Strategie gar nicht so gut ist, weil der zufällige Gegner auch Züge macht, die die KI vorher noch nie gesehen hat.

Erste Version

Die erste Version der KI nimmt immer nur den letzten Zug, den sie gemacht hat raus, wenn sie verloren hat. Wenn sie keinen der Züge bevorzugt, dann wählt sie einfach einen zufälligen Zug aus. Mit dieser KI werden allerdings nur wenige Spiele gewonnen:

KI: erste Version trainiert mit random_move und evaluiert mit random_move
Die KI hat 70.078% der Spiele gewonnen.

KI: erste Version trainiert mit random_move und evaluiert mit optimal_move
Die KI hat 4.884% der Spiele gewonnen.

KI: erste Version trainiert mit optimal_move und evaluiert mit random_move
Die KI hat 70.192% der Spiele gewonnen.

KI: erste Version trainiert mit optimal_move und evaluiert mit optimal_move
Die KI hat 4.984999999999999% der Spiele gewonnen.

bessere KI

Die bessere Version erweitert ihr Wissen stückweise. Sie markiert auch wie die erste Version Züge, die unmittelbar verlieren als verlierend. Allerdings markiert sie zusätzlich, wenn alle Züge verlierend sind, auch den letzten Zug, den sie gemacht hat als verlierend. Diese KI schafft es alle Spiele zu gewinnen:

KI: optimale Version trainiert mit random_move und evaluiert mit random_move
Die KI hat 100.0% der Spiele gewonnen.

KI: optimale Version trainiert mit random_move und evaluiert mit optimal_move
Die KI hat 100.0% der Spiele gewonnen.

KI: optimale Version trainiert mit optimal_move und evaluiert mit random_move
Die KI hat 100.0% der Spiele gewonnen.

KI: optimale Version trainiert mit optimal_move und evaluiert mit optimal_move
Die KI hat 100.0% der Spiele gewonnen.