76 lines
3.4 KiB
Markdown
76 lines
3.4 KiB
Markdown
# 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.
|
|
```
|