Nim-Spiel

Lösung von Abzählproblemen durch Rekursion

Als weitere Methode zur Lösung von Abzählproblemen wird die Rekursion vorgestellt. Dies geschieht am Beispiel eines Zahlenspiels, für das der vollständige Spielbaum entwickelt wird. Dieser wirkt zwar sehr unregelmäßig und kann mit den bekannten kombinatorischen Formeln nicht bewältigt werden, aber aufgrund seiner rekursiven Struktur lassen sich Abzählprobleme auf das Aufstellen der Rekursionsformel und der Behandlung des Basisfalls zurückführen.

Abzählprobleme Nim-Spiel Spielbaum Rekursion Zahlenspiel 3-5-11 Rekursionsformel Baum Rekursionsanfang

Ein Zahlenspiel zur Erläuterung des Monte Carlo Tree Search Algorithmus

Um die Vorgehensweise beim Monte-Carlo-Tree-Search-Algorithmus besser erklären zu können, wird zunächst ein einfaches Zahlenspiel vorgestellt und analysiert. Es handelt sich um eine Variation des Nim-Spiels, für das man eine einfache Gewinnstrategie angeben kann und bei dem mit dem Anfangswert bereits festgelegt ist, welcher Spieler den Gewinn erzwingen kann. Dies hat den Vorteil, dass man später besser nachvollziehen kann, wie der Monte-Carlo-Tree-Search-Algorithmus vorgeht.

Nim-Spiel Gewinnstrategie Monte-Carlo Restklasse Baumsuche Tree Search Zahlenspiel 3-5-11