Η συνδυαστική θεωρία παιγνίων, γνωστή και ως CGT, είναι ένας κλάδος των εφαρμοσμένων μαθηματικών και της θεωρητικής επιστήμης των υπολογιστών που μελετά τα συνδυαστικά παίγνια και διαφέρει από την "παραδοσιακή" ή "οικονομική" θεωρία παιγνίων. Η CGT προέκυψε σε σχέση με τη θεωρία των αμερόληπτων παιγνίων, ιδίως του παιγνίου Nim δύο παικτών, με έμφαση στην "επίλυση" ορισμένων τύπων συνδυαστικών παιγνίων.
Ένα παίγνιο πρέπει να πληροί διάφορες προϋποθέσεις για να είναι συνδυαστικό παίγνιο. Αυτές είναι οι εξής:
- Το παιχνίδι πρέπει να έχει τουλάχιστον δύο παίκτες.
- Το παιχνίδι πρέπει να είναι διαδοχικό (δηλαδή οι παίκτες εναλλάσσονται.)
- Το παίγνιο πρέπει να έχει τέλεια πληροφόρηση (δηλ. καμία πληροφορία δεν είναι κρυμμένη, όπως στο πόκερ).
- Το παιχνίδι πρέπει να είναι ντετερμινιστικό (δηλ. χωρίς πιθανότητες). Η τύχη δεν αποτελεί μέρος του παιχνιδιού.
- Το παιχνίδι πρέπει να έχει καθορισμένο αριθμό πιθανών κινήσεων.
- Το παιχνίδι πρέπει τελικά να τελειώσει.
- Το παιχνίδι πρέπει να τελειώσει όταν ένας παίκτης δεν μπορεί πλέον να κινηθεί.
Η Θεωρία Συνδυαστικών Παιγνίων περιορίζεται σε μεγάλο βαθμό στη μελέτη ενός υποσυνόλου συνδυαστικών παιγνίων που είναι δύο παικτών, πεπερασμένα και έχουν νικητή και ηττημένο (δηλαδή δεν καταλήγουν σε ισοπαλία).
Αυτά τα συνδυαστικά παίγνια μπορούν να αναπαρασταθούν με δέντρα, κάθε κορυφή των οποίων είναι το παίγνιο που προκύπτει από μια συγκεκριμένη κίνηση από το παίγνιο που βρίσκεται ακριβώς από κάτω της στο δέντρο. Σε αυτά τα παίγνια μπορούν να αποδοθούν τιμές παιγνίων. Η εύρεση αυτών των τιμών παιγνίων ενδιαφέρει πολύ τους θεωρητικούς CG, όπως και η θεωρητική έννοια της πρόσθεσης παιγνίων. Το άθροισμα δύο παιγνίων είναι το παίγνιο στο οποίο κάθε παίκτης στη σειρά του πρέπει να κινηθεί μόνο σε ένα από τα δύο παίγνια, αφήνοντας το άλλο ως έχει.
Οι Elwyn Berlekamp, John Conway και Richard Guy είναι οι θεμελιωτές της θεωρίας. Εργάστηκαν μαζί τη δεκαετία του 1960. Το δημοσιευμένο έργο τους ονομαζόταν Winning Ways for Your Mathematical Plays.
