Комбинаторная теория игр

Комбинаторная теория игр, также известная как CGT, является отраслью прикладной математики и теоретической информатики, которая изучает комбинаторные игры и отличается от "традиционной" или "экономической" теории игр. КГТ возникла в связи с теорией беспристрастных игр, в частности, игры для двух игроков Ним, с акцентом на "решение" определенных типов комбинаторных игр.

Игра должна отвечать нескольким условиям, чтобы быть комбинаториальной игрой. Вот эти:

В игре должно быть как минимум два игрока.
Игра должна быть последовательной (т.е. игроки чередуются).
Игра должна содержать идеальную информацию (т.е. не должна быть скрыта информация, как в покере).
Игра должна быть детерминистической (т.е. нешаблонной). Удача не является частью игры.
Партия должна иметь определенное количество возможных ходов.
В конце концов, игра должна закончиться.
Игра должна заканчиваться, когда один игрок не может больше двигаться.

Теория комбинаторных игр во многом ограничивается изучением подмножества комбинаторных игр, в которых два игрока, конечные, имеют победителя и проигравшего (т.е. не заканчиваются вничью).

Эти комбинаторные игры могут быть представлены деревьями, каждой вершиной которых является игра, полученная в результате определенного хода из игры непосредственно под ним на дереве. Этим играм могут быть присвоены игровые значения. Поиск этих игровых значений представляет большой интерес для теоретиков CG, так же как и теоретическая концепция игрового дополнения. Сумма двух партий - это игра, в которой каждый игрок в свою очередь должен ходить только в одной из двух партий, оставляя другую в том виде, в котором она была.

Элвин Берлекамп, Джон Конвей и Ричард Гай - основатели теории. Они работали вместе в 1960-х годах. Их опубликованная работа называлась "Победные пути для ваших математических игр".

Определения

В теории есть два игрока, которые называются левый и правый. Игра - это то, что позволяет левым и правым делать ходы в другие игры. Например, в шахматной игре есть обычная стартовая установка. Можно, однако, считать, что шахматная партия после первого хода - это другая партия, с другой установкой. Поэтому каждая позиция также называется партией.

Игры имеют нотацию {L|R}. L {\displaystyle L} $L$ - это игры, в которые может перейти левый игрок. R {\displaystyle R} $R$ - игры, в которые может перейти правый игрок. Если вы знаете шахматную нотацию, то обычная шахматная установка - это игра.

{ a 3 , a 4 , N a 3 , b 3 , b 4 , c 3 , c 4 , N c 3 , ... } | a 6 , a 5 , N a 6 , b 6 , b 5 , c 6 , c 5 , N c 6 , ... } {\displaystyle {a3,a4,Na3,b3,b4,c3,c4,Nc3,\dots |a6,a5,Na6,b6,b5,c6,c5,Nc6,\dots }} $\{a3,a4,Na3,b3,b4,c3,c4,Nc3,\dots |a6,a5,Na6,b6,b5,c6,c5,Nc6,\dots \}$

Точки "..." означают, что есть много ходов, поэтому не все показаны.

Шахматы очень сложные. Лучше подумать о более легких играх. Ним, например, намного проще думать. В Ним так играют:

Там ноль или больше кучи прилавков.
На одном ходу игрок может взять столько жетонов из одной кучки, сколько он хочет.
Игрок, который не может сделать ход, проигрывает.

Самая простая игра Nim начинается без жетонов! В таком случае ни один из игроков не может двигаться. Это показано как {|}. Обе стороны пусты, потому что ни один из игроков не может двигаться. Игрок, который первым пойдет, не может двигаться, и поэтому проиграет. В CGT часто пишут {|} как символ 0 (ноль).

Следующая самая простая игра имеет только одну кучу, с одним жетоном. Если левый игрок идет первым, то этот игрок должен взять контратаку, уйдя вправо без ходов ({|}, или 0). Если вместо этого первым идет правый игрок, то больше не будет ходов на левый. Таким образом, и левый, и правый могут сделать ход на 0. Это показано как {{|}|{|}}, или {0|0}. Первый игрок, сделавший ход, выиграет. Игры, равные {0|0}, очень важны. Они написаны символом * (звезда).

Вопросы и ответы

В: Что такое комбинаторная теория игр?

О: Комбинаторная теория игр (КТГ) - это отрасль прикладной математики и теоретической информатики, которая изучает комбинаторные игры и отличается от "традиционной" или "экономической" теории игр.

В: Каким условиям должна удовлетворять игра, чтобы считаться комбинаторной игрой?

О: Чтобы игра считалась комбинаторной, в ней должно быть не менее двух игроков, она должна быть последовательной (т.е. игроки чередуются), она должна иметь совершенную информацию (т.е. никакая информация не скрыта), она должна быть детерминированной (т.е. не случайной), удача не может быть частью игры, должно быть определенное количество возможных ходов, игра должна в конечном итоге закончиться, и игра должна закончиться, когда один из игроков больше не может двигаться.

В: Каким типам игр посвящена комбинаторная теория игр?

О: Комбинаторная теория игр фокусируется в основном на конечных играх для двух игроков, в которых есть победители и проигравшие (т.е. они не заканчиваются вничью).

В: Как представлены эти типы игр?

О: Эти типы игр могут быть представлены в виде деревьев, каждая вершина которых представляет собой результирующую игру от определенного хода, сделанного непосредственно под ней на дереве.

В: Каковы некоторые цели теоретиков КУ?

О: Некоторые цели теоретиков КУ включают поиск значений для этих типов игр, а также понимание концепции "добавления игры", которая включает в себя то, что каждый игрок делает только один ход в двух разных играх, оставляя другую игру неизменной во время своего хода.

В: Кто основал CGT?

О: Элвин Берлекамп, Джон Конвей и Ричард Гай являются основателями CGT в своей работе под названием "Выигрышные способы для Ваших математических игр", опубликованной в 1960-х годах.