Die kombinatorische Spieltheorie, auch als CGT bekannt, ist ein Zweig der angewandten Mathematik und der theoretischen Informatik, der sich mit kombinatorischen Spielen befasst und sich von der "traditionellen" oder "ökonomischen" Spieltheorie unterscheidet. CGT entstand im Zusammenhang mit der Theorie der unparteiischen Spiele, insbesondere dem Zwei-Spieler-Spiel von Nim, mit dem Schwerpunkt auf dem "Lösen" bestimmter Arten von kombinatorischen Spielen.

Ein Spiel muss mehrere Bedingungen erfüllen, um ein kombinatorisches Spiel zu sein. Diese sind:

  1. Das Spiel muss mindestens zwei Spieler haben.
  2. Das Spiel muss sequentiell ablaufen (d.h. die Spieler wechseln sich ab.)
  3. Das Spiel muss über perfekte Informationen verfügen (d.h. es dürfen keine Informationen versteckt sein, wie beim Poker).
  4. Das Spiel muss deterministisch (d.h. chancenlos) sein. Glück ist nicht Teil des Spiels.
  5. Die Partie muss eine bestimmte Anzahl von möglichen Zügen haben.
  6. Das Spiel muss irgendwann enden.
  7. Das Spiel muss beendet werden, wenn ein Spieler nicht mehr ziehen kann.

Die kombinatorische Spieltheorie beschränkt sich weitgehend auf die Untersuchung einer Teilmenge von kombinatorischen Spielen, die zwei Spieler haben, endlich sind und einen Gewinner und einen Verlierer haben (d.h. nicht unentschieden enden).

Diese kombinatorischen Partien können durch Bäume dargestellt werden, von denen jeder Scheitelpunkt die Partie ist, die sich aus einem bestimmten Zug aus der Partie direkt unter dem Baum ergibt. Diesen Partien können Spielwerte zugeordnet werden. Das Auffinden dieser Spielwerte ist für CG-Theoretiker von großem Interesse, ebenso wie das theoretische Konzept der Partieaddition. Die Summe von zwei Partien ist die Partie, in der jeder Spieler an seinem Zug nur in einer der beiden Partien ziehen muss, während die andere unverändert bleibt.

Elwyn Berlekamp, John Conway und Richard Guy sind die Begründer der Theorie. Sie arbeiteten in den 1960er Jahren zusammen. Ihre veröffentlichte Arbeit wurde Winning Ways for Your Mathematical Plays genannt.