Комбинаторная теория игр — это раздел математики и теоретической информатики , который обычно изучает последовательные игры с полной информацией . Исследования в основном ограничивались играми двух игроков , в которых есть позиция , которую игроки по очереди меняют определенными способами или ходами для достижения определенного условия выигрыша. Комбинаторная теория игр традиционно не изучала азартные игры или те, которые используют несовершенную или неполную информацию, отдавая предпочтение играм, которые предлагают полную информацию, в которых состояние игры и набор доступных ходов всегда известны обоим игрокам. [1] Однако по мере развития математических методов типы игр, которые можно математически проанализировать, расширяются, поэтому границы области постоянно меняются. [2] Ученые обычно определяют, что они подразумевают под «игрой» в начале статьи, и эти определения часто различаются, поскольку они специфичны для анализируемой игры и не предназначены для представления всего объема области.
Комбинаторные игры включают в себя такие известные игры, как шахматы , шашки и го , которые считаются нетривиальными, и крестики-нолики , которые считаются тривиальными в том смысле, что их «легко решить». Некоторые комбинаторные игры также могут иметь неограниченную игровую область, например бесконечные шахматы . В теории комбинаторных игр ходы в этих и других играх представлены в виде игрового дерева .
Комбинаторные игры также включают в себя однопользовательские комбинаторные головоломки, такие как судоку , и автоматы без игроков, такие как игра Конвея «Жизнь » (хотя в самом строгом определении можно сказать, что «игры» требуют более одного участника, отсюда и обозначения «головоломка» и «автоматы». [3] )
Теория игр в целом включает азартные игры, игры с несовершенным знанием и игры, в которых игроки могут ходить одновременно, и они, как правило, представляют собой реальные ситуации принятия решений.
Комбинаторная теория игр имеет иной акцент, чем «традиционная» или «экономическая» теория игр, которая изначально была разработана для изучения игр с простой комбинаторной структурой, но с элементами случайности (хотя она также рассматривает последовательные ходы, см. игру в развернутой форме ). По сути, комбинаторная теория игр внесла новые методы для анализа игровых деревьев, например, с использованием сюрреалистических чисел , которые являются подклассом всех игр с полной информацией для двух игроков. [3] Тип игр, изучаемых комбинаторной теорией игр, также представляет интерес для искусственного интеллекта , особенно для автоматизированного планирования и составления расписаний . В комбинаторной теории игр меньше внимания уделяется уточнению практических алгоритмов поиска (таких как эвристика альфа-бета-отсечения, включенная в большинство учебников по искусственному интеллекту), но больше внимания уделяется описательным теоретическим результатам (таким как меры сложности игры или доказательства существования оптимального решения без обязательного указания алгоритма, такие как аргумент о краже стратегии ).
Важным понятием в комбинаторной теории игр является понятие решенной игры . Например, крестики-нолики считаются решенной игрой, так как можно доказать, что любая игра приведет к ничьей, если оба игрока играют оптимально. Вывести аналогичные результаты для игр с богатыми комбинаторными структурами сложно. Например, в 2007 году было объявлено, что шашки были слабо решены — оптимальная игра обеих сторон также приводит к ничьей — но этот результат был доказательством с помощью компьютера . [4] Другие игры реального мира в основном слишком сложны, чтобы позволить полный анализ сегодня, хотя теория имела некоторые недавние успехи в анализе эндшпилей Го. Применение комбинаторной теории игр к позиции пытается определить оптимальную последовательность ходов для обоих игроков до конца игры, и тем самым обнаружить оптимальный ход в любой позиции. На практике этот процесс мучительно сложен, если только игра не очень проста.
Может быть полезно различать комбинаторные «математические игры», представляющие интерес в первую очередь для математиков и ученых для размышлений и решения, и комбинаторные «игры», представляющие интерес для широких слоев населения как форма развлечения и соревнования. [5] Однако ряд игр попадают в обе категории. Например, Nim — это игра, которая легла в основу комбинаторной теории игр, и одна из первых компьютерных игр. [6] Крестики-нолики до сих пор используются для обучения студентов -компьютерщиков основным принципам проектирования игрового ИИ . [7]
Теория комбинаторных игр возникла в связи с теорией беспристрастных игр , в которой любая игра, доступная одному игроку, должна быть доступна и другому. Одной из таких игр является Ним , которая может быть решена полностью. Ним — беспристрастная игра для двух игроков, и подчиняется условию нормальной игры , что означает, что игрок, который не может сделать ход, проигрывает. В 1930-х годах теорема Спрага–Гранди показала, что все беспристрастные игры эквивалентны кучам в Ниме, тем самым показав, что в играх, рассматриваемых на комбинаторном уровне, в которых важны подробные стратегии, а не только выигрыши, возможны крупные объединения.
В 1960-х годах Элвин Р. Берлекамп , Джон Х. Конвей и Ричард К. Гай совместно представили теорию партизанской игры , в которой требование, чтобы игра, доступная одному игроку, была доступна обоим, смягчено. Их результаты были опубликованы в их книге Winning Ways for your Mathematical Plays в 1982 году. Однако первой работой, опубликованной на эту тему, была книга Конвея 1976 года On Numbers and Games , также известная как ONAG, в которой была введена концепция сюрреалистических чисел и обобщение на игры. On Numbers and Games также была плодом сотрудничества Берлекампа, Конвея и Гая.
Комбинаторные игры обычно, по соглашению, приводятся в форму, в которой один игрок выигрывает, когда у другого не остается ходов. Легко преобразовать любую конечную игру только с двумя возможными результатами в эквивалентную, где применяется это соглашение. Одной из важнейших концепций в теории комбинаторных игр является концепция суммы двух игр, которая представляет собой игру, в которой каждый игрок может выбрать ход либо в одной игре, либо в другой в любой момент игры, и игрок выигрывает, когда у его противника не остается ходов ни в одной из игр. Такой способ объединения игр приводит к богатой и мощной математической структуре.
В своей книге «О числах и играх» Конвей утверждал , что источником вдохновения для теории партийных игр послужили его наблюдения за игрой в окончаниях го , которые часто можно разложить на суммы более простых окончаний, изолированных друг от друга в разных частях доски.
Вводный текст « Пути победы» знакомит нас с большим количеством игр, но в качестве мотивирующих примеров для вводной теории использовались следующие:
Классическая игра Го оказала влияние на раннюю комбинаторную теорию игр, и Берлекамп и Вольф впоследствии разработали теорию эндшпиля и температуры для нее (см. ссылки). Вооружившись этим, они смогли построить правдоподобные позиции эндшпиля Го, из которых они могли дать опытным игрокам Го выбор сторон, а затем победить их в любом случае.
Другая игра, изучаемая в контексте комбинаторной теории игр, — это шахматы . В 1953 году Алан Тьюринг писал об игре: «Если можно совершенно недвусмысленно объяснить на английском языке, при необходимости с помощью математических символов, как следует выполнять вычисления, то всегда можно запрограммировать любой цифровой компьютер для выполнения этих вычислений, при условии достаточной емкости памяти». [8] В статье 1950 года Клод Шеннон оценил нижнюю границу сложности дерева игры в шахматы как 10 120 , и сегодня это называется числом Шеннона . [9] Шахматы остаются нерешенными, хотя обширные исследования, включая работу с использованием суперкомпьютеров, создали шахматные таблицы окончаний , которые показывают результат идеальной игры для всех окончаний с семью фигурами или меньше. Бесконечные шахматы имеют даже большую комбинаторную сложность, чем шахматы (если только не изучаются только ограниченные окончания или составные позиции с небольшим количеством фигур).
Игра, в простейшем смысле, представляет собой список возможных «ходов», которые могут сделать два игрока, называемые левым и правым . Позиция игры, полученная в результате любого хода, может считаться другой игрой. Эта идея рассмотрения игр с точки зрения их возможных ходов в другие игры приводит к рекурсивному математическому определению игр, которое является стандартным в комбинаторной теории игр. В этом определении каждая игра имеет обозначение {L|R} . L — это множество игровых позиций, в которые может переместиться левый игрок, а R — это множество игровых позиций, в которые может переместиться правый игрок; каждая позиция в L и R определяется как игра с использованием той же нотации.
Используя в качестве примера Доминирование , обозначьте каждую из шестнадцати ячеек доски четыре на четыре буквой A1 для самого верхнего левого квадрата, C2 для третьей ячейки слева во втором ряду сверху и т. д. Мы используем, например, (D3, D4) для обозначения игровой позиции, в которой вертикальное домино было помещено в нижний правый угол. Затем начальную позицию можно описать в нотации комбинаторной теории игр как
В стандартной игре Cross-Cram игроки поочередно ходят, но это чередование неявно регулируется определениями комбинаторной теории игр, а не кодируется в игровых состояниях.
Вышеуказанная игра описывает сценарий, в котором у любого игрока остается только один ход, и если любой из игроков делает этот ход, этот игрок выигрывает. (Нерелевантный открытый квадрат C3 был опущен на схеме.) {|} в списке ходов каждого игрока (соответствующий единственному оставшемуся квадрату после хода) называется нулевой игрой и фактически может быть сокращенно обозначен как 0. В нулевой игре ни у одного из игроков нет допустимых ходов; таким образом, игрок, чья очередь наступает, когда наступает нулевая игра, автоматически проигрывает.
Тип игры на диаграмме выше также имеет простое название; он называется звездная игра , что также может быть сокращено ∗. В звездной игре единственный допустимый ход приводит к нулевой игре, что означает, что тот, чья очередь доходит до звездной игры, автоматически выигрывает.
Дополнительный тип игры, не встречающийся в Domineering, — это петлевая игра, в которой допустимый ход влево или вправо — это игра, которая затем может вернуться к первой игре. Checkers , например, становится петлевой, когда одна из фигур продвигается, так как тогда она может бесконечно циклически перемещаться между двумя или более полями. Игра, в которой нет таких ходов, называется loopfree .
Существуют также трансфинитные игры, в которых имеется бесконечно много позиций, то есть слева и справа имеются списки ходов, которые являются бесконечными, а не конечными.
Числа представляют количество свободных ходов или преимущество хода конкретного игрока. По соглашению положительные числа представляют преимущество для Left, а отрицательные числа представляют преимущество для Right. Они определяются рекурсивно, причем 0 является базовым случаем.
Нулевая игра — проигрыш для первого игрока.
Сумма числовых игр ведет себя как целые числа, например, 3 + −2 = 1.
Любое игровое число относится к классу сюрреалистических чисел .
Звезда , записанная как ∗ или {0|0}, означает победу первого игрока, поскольку любой из игроков должен (если он первый ходит в игре) сделать ход в нулевую игру и, следовательно, выиграть.
Игра ∗ не является ни положительной, ни отрицательной; она и все другие игры, в которых выигрывает первый игрок (независимо от того , на какой стороне он находится), называются нечеткими или смешанными с 0; символически мы записываем ∗ || 0.
Up , обозначаемый как ↑, — это позиция в комбинаторной теории игр. [10] В стандартной нотации ↑ = {0|∗}.
Up строго положительно (↑ > 0), но бесконечно мало . Up определено в разделе « Выигрышные способы для ваших математических игр» .
Down , обозначаемая как ↓, — это позиция в комбинаторной теории игр. [10] В стандартной нотации ↓ = {∗|0}.
Down строго отрицателен (↓ < 0), но бесконечно мал . Down определен в разделе « Выигрышные способы для ваших математических игр» .
Рассмотрим игру {1|−1}. Оба хода в этой игре являются преимуществом для игрока, который их делает; поэтому игра называется «горячей»; она больше любого числа, меньшего −1, меньше любого числа, большего 1, и нечеткой с любым числом между ними. Она записывается как ±1. Ее можно прибавлять к числам или умножать на положительные числа ожидаемым образом; например, 4 ± 1 = {5|3}.
Беспристрастная игра — это игра, в которой на каждой позиции игры оба игрока могут делать одни и те же ходы. Например, Ним беспристрастен, так как любой набор объектов, который может убрать один игрок, может убрать и другой. Однако доминирование не беспристрастно, так как один игрок размещает горизонтальные домино, а другой — вертикальные. Аналогично, Шашки не беспристрастны, так как игроки владеют разноцветными фишками. Для любого порядкового числа можно определить беспристрастную игру, обобщающую Ним, в которой на каждом ходу любой игрок может заменить число любым меньшим порядковым числом; игры, определенные таким образом, известны как нимберы . Теорема Спрага–Гранди утверждает, что каждая беспристрастная игра при нормальных правилах игры эквивалентна нимберу.
«Наименьшие» числа — самые простые и наименее соответствующие обычному порядку ординалов — это 0 и ∗.
