Комбинаторная теория игр, также известная как CGT, является отраслью прикладной математики и теоретической информатики, которая изучает комбинаторные игры и отличается от "традиционной" или "экономической" теории игр. КГТ возникла в связи с теорией беспристрастных игр, в частности, игры для двух игроков Ним, с акцентом на "решение" определенных типов комбинаторных игр.
Игра должна отвечать нескольким условиям, чтобы быть комбинаториальной игрой. Вот эти:
- В игре должно быть как минимум два игрока.
- Игра должна быть последовательной (т.е. игроки чередуются).
- Игра должна содержать идеальную информацию (т.е. не должна быть скрыта информация, как в покере).
- Игра должна быть детерминистической (т.е. нешаблонной). Удача не является частью игры.
- Партия должна иметь определенное количество возможных ходов.
- В конце концов, игра должна закончиться.
- Игра должна заканчиваться, когда один игрок не может больше двигаться.
Теория комбинаторных игр во многом ограничивается изучением подмножества комбинаторных игр, в которых два игрока, конечные, имеют победителя и проигравшего (т.е. не заканчиваются вничью).
Эти комбинаторные игры могут быть представлены деревьями, каждой вершиной которых является игра, полученная в результате определенного хода из игры непосредственно под ним на дереве. Этим играм могут быть присвоены игровые значения. Поиск этих игровых значений представляет большой интерес для теоретиков CG, так же как и теоретическая концепция игрового дополнения. Сумма двух партий - это игра, в которой каждый игрок в свою очередь должен ходить только в одной из двух партий, оставляя другую в том виде, в котором она была.
Элвин Берлекамп, Джон Конвей и Ричард Гай - основатели теории. Они работали вместе в 1960-х годах. Их опубликованная работа называлась "Победные пути для ваших математических игр".
