Das Spiel
Tic-Tac-Toe ist ein sehr beliebtes Spiel für zwei Spieler, X und O, die abwechselnd die Leerzeichen in einem 3×3-Raster markieren. Der Spieler, dem es gelingt, drei seiner Markierungen in einer vertikalen, horizontalen oder diagonalen Reihe zu platzieren, gewinnt das Spiel.,
Mathematische Eigenschaften
Aus mathematischer Sicht hat das Spiel zwei sehr wichtige Eigenschaften:
Eigenschaft 1:
Das Spiel gibt zu, dass der Spieler, der diese optimale Strategie verwendet, gewinnt oder zieht, aber nicht verliert.
Eigenschaft 2:
Die Anzahl der möglichen Übereinstimmungen ist relativ gering.
Zu Beginn kann der erste Spieler eines der 9 Leerzeichen markieren. In der folgenden Runde kann der zweite Spieler eines der verbleibenden 8 Felder markieren und so weiter., Das Spiel wird fortgesetzt, bis alle Felder markiert sind oder einer der Spieler gewinnt.
Es ist dann leicht zu verstehen, dass die Gesamtzahl der verschiedenen Übereinstimmungen niedriger ist als:
987….1 = 9! = 362880
Das ist eine relativ kleine Zahl für einen computer.
Der Algorithmus
Aus den Eigenschaften 1 und 2 folgt, dass ein praktischer und allgemeiner Algorithmus zum Gewinnen / Zeichnen des Spiels darin besteht, die Alpha-Beta-Suche zu verwenden.,
In jeder Runde wertet der Algorithmus alle möglichen Folgen jeder Bewegung aus (möglich aufgrund von Eigenschaft 2) und wählt diejenige aus, die einen Sieg oder ein Unentschieden sicherstellt (möglich aufgrund von Eigenschaft 1).
Ein KI-Spieler, der jede Bewegung mit dem Alpha Beta-Suchalgorithmus auswählt, wird niemals verlieren. Um das Spiel realistischer zu machen, ist es schön, einen stochastischen Faktor einzuführen, sodass sich der KI-Spieler jedes Mal mit einer vordefinierten Wahrscheinlichkeit zufällig bewegt, anstatt dem Alpha-Beta-Algorithmus zu folgen., Dies wird das Spiel realistischer machen, da es den KI-Spieler menschlicher macht und manchmal verliert.