Tic-Tac-Toe ist ein beliebtes Spiel zur Demonstration des Minimax-Algorithmus, durch den Agenten mithilfe spieltheoretischer Überlegungen intelligentes Verhalten zeigen können. Im Internet existieren diverse Implementierungen, um gegen einen Computer oder andere Personen zu spielen. Die interaktive App erlaubt, das Spiel mit KI-Unterstützung zu spielen. Die Farbkodierung entspricht Empfehlungen, welche Züge zu welchem Ergebnis führen, unter der Annahme, dass beide Spieler ideal spielen. Rote Felder erlauben X zu gewinnen, blaue Felder erlauben O zu gewinnen.
In Tic-Tac-Toe markieren zwei Spieler, X und O, das Spielfeld. Wer zuerst eine Reihe, Spalte oder Diagonale füllt, gewinnt das Spiel. Spiele dieser Art existieren seit tausenden Jahren. Das Spiel ist zwar einfach, aber hinreichend komplex, um einige Konzepte künstlicher Intelligenz zu veranschaulichen: In Tic-Tac-Toe existieren weniger als 9! Spielverläufe. Weil ein Teil der Spiele bereits nach weniger als neun aber mindestens fünf Zügen endet, sind ohne Berücksichtigung von Rotations- und Achsensymmetrien 255.168 unterschiedliche Spielverläufe möglich.
Mit dem Minimax-Algorithmus lassen sich die idealen Spielzüge für beide Spieler rekursiv berechnen. Der Algorithmus liefert das bestmögliche Ergebnis unter der Voraussetzung, dass beide Spieler rational spielen. Minimax ordnet den Blättern des Spielbaums einen Wert zu, z.B. +1 wenn X gewinnt, -1 wenn O gewinnt und 0 wenn das Spiel unentschieden endet. Um den besten Zug zu einem beliebiegen Zeitpunkt zu berechnen, werden die Werte der Blätter rekursiv zur Wurzel propagiert. Eine exemplarische Implementierung ist hier verfügbar. Der Minimax-Algorithmus ist ein Beispiel dafür, wie eine einfache Idee ein vergleichsweise komplexes Problem durch Rekursion lösen kann.