Комбинаторната теория на игрите, известна също като CGT, е клон на приложната математика и теоретичната информатика, който изучава комбинаторните игри и се различава от "традиционната" или "икономическата" теория на игрите. КГТ възниква във връзка с теорията на безпристрастните игри, по-специално играта на Ним за двама играчи, като основната цел е "решаването" на определени видове комбинаторни игри — намиране на алгоритми и правила, които определят кой играч може да спечели при оптимална игра.

Критерии за комбинаторна игра

Една игра трябва да отговаря на няколко условия, за да бъде комбинаторна игра. Това са:

  1. Играта трябва да има поне двама играчи.
  2. Играта трябва да е последователна (играчите се редуват при правене на ходове).
  3. Играта трябва да е с перфектна информация (да няма скрита информация или неизвестни елементи като в покера).
  4. Играта трябва да е детерминистична (без елемент на шанс или случайни събития). Късметът не е част от играта.
  5. Има ограничен (краен) брой възможни ходове от всяка позиция.
  6. Играта трябва да приключи след краен брой ходове (да няма безкрайни цикли при правилна игра).
  7. Терминален резултат: играта приключва, когато един от играчите не може да направи ход — тогава се определя победител и губещ според договореното правило (например при "normal play" побеждава последният, който е направил ход).

Основни понятия и класификация

В рамките на КГТ най-често разграничават два основни типа игри:

  • Безпристрастни (impartial) игри — възможните ходове зависят само от текущата позиция, а не от това кой е на ход. За тези игри важен инструмент е теоремата на Sprague–Grundy, която придава на всяка позиция число (grundy-число или nimber). При сумата на безпристрастни игри се използва операцията XOR (битово изключващо ИЛИ) върху тези стойности: позицията е печеливша за следващия играч точно тогава, когато XOR на grundy-числата е различно от нула — това е фундаменталният пример е играта Ним.
  • Пристрастни (partizan) игри — ходовете, достъпни за левия и десния играч могат да се различават. За тези игри се развива по-обща теория на стойностите (сюрреални числа, "hot" и "cold" игри, инфинитезимали и др.), въведена от Джон Конуей и сътрудници.

Представяне, стойности и суми от игри

Комбинаторните игри често се представят чрез дървета на разгръщане: всеки връх от дървото е позиция, а дъщерните върхове са позиции, получени чрез възможни ходове. На тези позиции могат да се присвоят игрови стойности, които описват кои играчи имат печеливша стратегия.

Сборът (дизюнктивната сума) на две или повече игри е фундаментална операция: в сумата всеки ход на играч се прави в точно една от съставните игри, като останалите се запазват. Изследването на сумите е ключово за разбирането на сложни позиции, тъй като много реални игри се разлагат на независими компоненти.

Стратегии и резултатни класове

За крайни безпристрастни игри има просто разграничение между две основни класови резултати:

  • P-позииции (Previous player win) — позициите, от които играчът, чийто ход е "предходният" (т.е. опонентът), има печеливша стратегия; следващият играч губи при оптимална игра.
  • N-позиции (Next player win) — позициите, от които следващият играч има печеливша стратегия.

За безпристрастни игри тези класове се определят ефективно чрез Grundy-числата; за пристрастни игри е необходимо по-фино разглеждане на стойностите и понякога се използват алгебрични конструкции (сюрреални числа и др.).

Примери и приложения

Класически примери, разглеждани в КГТ, включват:

  • Ним — купчина(и) камъни; ход: премахваш произволен брой камъни от една купчина. Оптималната стратегия се дава от XOR на големините на купчините (Sprague–Grundy теория).
  • Kayles, Hackenbush, Domineering и други пъзел-игри — дават богати примери както за безпристрастни, така и за пристрастни ситуации с интересни стойности.

Практически приложения на КГТ включват анализ на възможности в игри и пъзели, алгоритми за стратегии в изкуствен интелект, както и теоретични връзки с комбинаторика и теория на числата. От гледна точка на изчислителната сложност, много задачи свързани с обобщени (многоходови или неограничени) варианти на комбинаторни игри са трудни за решаване — често PSPACE-пълни или NP-трудни.

Ограничения и вариации

Комбинаторната теория на игрите обикновено се ограничава до двама играчи и крайни позиции без равенство (т.е. с ясно определен победител и губещ при нормална игра). Съществуват важни вариации: например misère-условие (последният, който направи ход, губи) променя правилата за оценка и прави някои стандартни техники (като Sprague–Grundy) неподходящи или изискващи модификация.

Основатели на теорията са Елуин Берлекамп, Джон Конуей и Ричард Гай. Те работят заедно през 60-те години на миналия век. Публикуваният им труд се нарича Печеливши начини за вашите математически игри — класическо изследване, което систематизира много от идеите и методите в комбинаторната теория на игрите.