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

Эта статья о теории комбинаторных игр. Чтобы узнать о теории, включающей азартные игры и игры с несовершенным знанием, см. Теорию игр .

Математики играют в Конане на семинаре по комбинаторной теории игр

Комбинаторная теория игр — это раздел математики и теоретической информатики , который обычно изучает последовательные игры с совершенной информацией . Исследование в основном ограничивалось играми которых для двух игроков, в игроки по очереди меняли определенные способы или ходы для достижения определенного условия победы. Комбинаторная теория игр традиционно не изучала азартные игры или игры, в которых используется несовершенная или неполная информация, отдавая предпочтение играм, предлагающим полную информацию , в которых состояние игры и набор доступных ходов всегда известны обоим игрокам. Однако по мере развития математических методов типы игр, которые можно анализировать математически, расширяются, поэтому границы этой области постоянно меняются. Ученые обычно определяют, что они подразумевают под «игрой», в начале статьи, и эти определения часто различаются, поскольку они специфичны для анализируемой игры и не предназначены для отражения всего объема этой области.

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

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

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

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

Важным понятием комбинаторной теории игр является понятие решенной игры . Например, игра «Крестики-нолики» считается решенной игрой, поскольку можно доказать, что любая игра закончится ничьей, если оба игрока играют оптимально. Получить аналогичные результаты для игр с богатой комбинаторной структурой сложно. Например, в 2007 году было объявлено, что шашки решены слабо — оптимальная игра обеих сторон также приводит к ничьей, — но этот результат был компьютерным доказательством . Другие игры реального мира в большинстве случаев слишком сложны, чтобы их можно было сегодня провести полный анализ, хотя в последнее время теория добилась некоторых успехов в анализе эндшпиля го. Применение комбинаторной теории игр к позиции пытается определить оптимальную последовательность ходов для обоих игроков до конца игры и тем самым обнаружить оптимальный ход в любой позиции. На практике этот процесс мучительно сложен, если только игра не очень проста.

Может быть полезно провести различие между комбинаторными «математическими играми», представляющими интерес в первую очередь для математиков и ученых, над которыми нужно размышлять и решать, и комбинаторными «играми», представляющими интерес для населения в целом как форма развлечения и соревнования. Однако ряд игр попадают в обе категории. Nim — это игровая игра, положившая начало комбинаторной теории игр, и одна из первых компьютеризированных игр. Например, Крестики-нолики до сих пор используются для обучения игрового ИИ основным принципам проектирования студентов информатике .

История

Комбинаторная теория игр возникла в связи с теорией беспристрастных игр , в которой любая игра, доступная одному игроку, должна быть доступна и другому. Одной из таких игр является Nim , которую можно решить полностью. Ним — это беспристрастная игра для двух игроков, в которой действуют обычные условия игры , что означает, что игрок, который не может двигаться, проигрывает. В 1930-х годах теорема Спрэга–Грунди показала, что все беспристрастные игры эквивалентны кучам в Ниме, показав тем самым, что крупные унификации возможны в играх, рассматриваемых на комбинаторном уровне, в которых важны детальные стратегии, а не только выигрыши.

В 1960-х годах Элвин Р. Берлекамп , Джон Х. Конвей и Ричард К. Гай совместно представили теорию партийной игры , в которой смягчено требование о том, чтобы игра, доступная одному игроку, была доступна обоим. Их результаты были опубликованы в книге « Пути к победе в математических играх» в 1982 году. Однако первой работой, опубликованной по этой теме, была книга Конвея 1976 года «О числах и играх» , также известная как ONAG, которая представила концепцию сюрреалистических чисел и ее обобщение. игры. Книга «О числах и играх» также стала плодом сотрудничества Берлекэмпа, Конвея и Гая.

Комбинаторные игры обычно имеют такую ​​форму, в которой один игрок выигрывает, когда у другого не остается ходов. Любую конечную игру, имеющую только два возможных результата, легко преобразовать в эквивалентную, в которой применяется это соглашение. Одной из наиболее важных концепций теории комбинаторных игр является концепция суммы двух игр, то есть игра, в которой каждый игрок может выбрать ход либо в одной игре, либо в другой в любой момент игры, и игрок выигрывает. когда его противник не имеет хода ни в одной игре. Такой способ объединения игр приводит к созданию богатой и мощной математической структуры.

Конвей заявил в книге «О числах и играх» , что вдохновение для теории партийных игр было основано на его наблюдениях за игрой в эндшпилях го , которые часто можно разложить на суммы более простых эндшпилей, изолированных друг от друга в разных частях доски.

Примеры

Во вступительном тексте « Пути к победе» представлено большое количество игр, но в качестве мотивирующих примеров для вводной теории использовались следующие:

• Синий-Красный Хакенбуш . На конечном уровне эта партийная комбинаторная игра позволяет создавать игры, значениями которых являются двоично-рациональные числа . На бесконечном уровне он позволяет построить все реальные значения, а также множество бесконечных, относящихся к классу сюрреалистических чисел .
• Blue–Red–Green Hackenbush — допускает дополнительные игровые значения, не являющиеся числами в традиционном понимании, например, звезда .
• Жабы и лягушки — допускают различные игровые значения. В отличие от большинства других игр, позиция легко представляется короткой строкой символов.
• Доминирование - Различные интересные игры, например горячие игры , появляются в качестве позиций в Доминировании, потому что иногда есть стимул двигаться, а иногда нет. игры Это позволяет обсуждать температуру .
• Ним – Беспристрастная игра . Это позволяет создавать нимберы . (Его также можно рассматривать как особый случай сине-красно-зеленого Хакенбуша, состоящий только из зеленого цвета.)

Классическая игра Го оказала влияние на раннюю комбинаторную теорию игр, а Берлекамп и Вульф впоследствии разработали для нее теорию эндшпиля и температуры (см. Ссылки). Вооружившись этим, они смогли построить правдоподобные позиции в эндшпиле го, из которых они могли бы дать опытным игрокам в го выбор сторон, а затем победить их в любом случае.

Другая игра, изучаемая в контексте комбинаторной теории игр, — это шахматы . В 1953 году Алан Тьюринг писал об игре: «Если можно совершенно недвусмысленно объяснить на английском языке, при необходимости с помощью математических символов, как следует производить вычисления, то всегда можно запрограммировать любой цифровой компьютер для выполнения таких вычислений». , при условии, что емкость хранилища достаточна». В статье 1950 года Клод Шеннон оценил нижнюю границу сложности дерева игры в шахматы в 10 ¹²⁰ , и сегодня это называется числом Шеннона . Шахматы остаются неразгаданными, хотя обширные исследования, в том числе работы с использованием суперкомпьютеров, позволили создать базы таблиц шахматных эндшпилей , которые показывают результат идеальной игры для всех эндшпилей с семью фигурами или меньше. Бесконечные шахматы имеют еще большую комбинаторную сложность, чем шахматы (если только не изучаются только ограниченные эндшпили или составные позиции с небольшим количеством фигур).

Обзор

Проще говоря, игра — это список возможных «ходов», которые могут сделать два игрока, называемые левым и правым . Игровая позиция, возникающая в результате любого хода, может считаться другой игрой. Эта идея рассмотрения игр с точки зрения их возможных переходов в другие игры приводит к рекурсивному математическому определению игр, которое является стандартным в комбинаторной теории игр. В этом определении каждая игра имеет обозначение {L|R} . L — набор игровых позиций, на которые может перейти левый игрок, а R — набор игровых позиций, на которые может перейти правый игрок; каждая позиция в L и R определяется как игра с использованием одних и тех же обозначений.

Используя в качестве примера «Доминирование» , пометьте каждую из шестнадцати ячеек доски размером четыре на четыре: A1 для самой верхней левой клетки, C2 для третьей клетки слева во втором ряду сверху и так далее. Мы используем, например, (D3, D4) для обозначения игровой позиции, в которой вертикальное домино находится в правом нижнем углу. Тогда начальную позицию можно описать в обозначениях комбинаторной теории игр как

$\{(\mathrm {A} 1,\mathrm {A} 2),(\mathrm {B} 1,\mathrm {B} 2),\dots |(\mathrm {A} 1,\mathrm {B} 1),(\mathrm {A} 2,\mathrm {B} 2),\dots \}.$

В стандартной игре Cross-Cram игроки чередуют ходы, но это чередование неявно обрабатывается определениями комбинаторной теории игр, а не закодировано в игровых состояниях.

$\{(\mathrm {A} 1,\mathrm {A} 2)|(\mathrm {A} 1,\mathrm {B} 1)\}=\{\{|\}|\{|\}\}.$

В приведенной выше игре описан сценарий, в котором у любого игрока остается только один ход, и если любой из игроков делает этот ход, он побеждает. (Нерелевантный открытый квадрат в C3 был исключен из диаграммы.) Символ {|} в списке ходов каждого игрока (соответствующий единственному оставшемуся квадрату после хода) называется нулевой игрой и фактически может обозначаться сокращенно 0. В нулевая игра, ни у одного игрока нет допустимых ходов; таким образом, игрок, чья очередь настала, когда появляется нулевая игра, автоматически проигрывает.

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

Дополнительный тип игры, которого нет в «Доминировании», — это зацикленная игра, в которой правильный ход влево или вправо — это игра, которая затем может вернуться к первой игре. Шашки , например, становятся зацикленными, когда одна из фигур продвигается, так как тогда она может бесконечно переключаться между двумя или более клетками. Игра, не обладающая такими ходами, называется безцикловой .

Сокращения игр

Числа

Числа обозначают количество свободных ходов или преимущество хода конкретного игрока. По соглашению положительные числа представляют преимущество для левых, а отрицательные числа представляют преимущество для правых. Они определяются рекурсивно, где 0 является базовым случаем.

0 = {|}

1 = {0|}, 2 = {1|}, 3 = {2|}

−1 = {|0}, −2 = {|−1}, −3 = {|−2}

Нулевая игра – это проигрыш первого игрока.

Сумма числовых игр ведет себя как целые числа, например 3 + −2 = 1.

Звезда

Звезда , записанная как * или {0|0}, означает победу первого игрока, поскольку любой игрок должен (если первым сделать ход в игре) перейти к нулевой игре и, следовательно, выиграть.

∗ + ∗ = 0, потому что первый игрок должен превратить одну копию ∗ в 0, а затем другому игроку придется также превратить другую копию ∗ в 0; в этот момент первый игрок проиграет, поскольку 0 + 0 не допускает ходов.

Игра* не является ни положительной, ни отрицательной; эта и все другие игры, в которых выигрывает первый игрок (независимо от того, на какой стороне он находится), называются нечеткими с 0 или спутанными с 0; символически мы пишем ∗ || 0.

Вверх

Up , обозначаемый как ↑, — это позиция в комбинаторной теории игр. В стандартных обозначениях ↑ = {0|∗}.

−↑ знак равно ↓ ( вниз )

Up строго положительное (↑ > 0), но бесконечно малое . Up определяется в разделе «Пути к победе в математических играх» .

Вниз

Вниз , записываемый как ↓, — это позиция в комбинаторной теории игр. В стандартных обозначениях ↓ = {∗|0}.

−↓ знак равно ↑ ( вверх )

Вниз строго отрицательное (↓ <0), но бесконечно малое . Даун определяется в разделе «Пути к победе в математических играх» .

«Горячие» игры

Рассмотрим игру {1|−1}. Оба хода в этой игре дают преимущество игроку, который их делает; поэтому игру называют «горячей»; оно больше любого числа меньше -1, меньше любого числа больше 1 и нечетко с любым промежуточным числом. Записывается как ±1. Его можно добавлять к числам или умножать на положительные числа ожидаемым образом; например, 4 ± 1 = {5|3}.

Нимберс

Беспристрастная игра — это игра, в которой в любой позиции игры оба игрока могут делать одни и те же ходы. Например, Ним беспристрастен, поскольку любой набор объектов, который может удалить один игрок, может быть удален и другим. Однако доминирование не является беспристрастным, поскольку один игрок раскладывает костяшки по горизонтали, а другой – по вертикали. Точно так же шашки не беспристрастны, поскольку у игроков есть фигуры разного цвета. Для любого порядкового числа можно определить беспристрастную игру, обобщающую Ним, в которой на каждом ходу любой игрок может заменить это число любым меньшим порядковым числом; игры, определенные таким образом, известны как нимберы . Теорема Спрэга -Грунди утверждает, что каждая беспристрастная игра эквивалентна нимберу.

Самые «маленькие» числа – самые простые и наименьшие при обычном порядке ординалов – это 0 и ∗.

См. также

• Альфа-бета-обрезка , оптимизированный алгоритм поиска в дереве игры.
• Обратная индукция , рассуждение в обратном направлении от конечной ситуации.
• Охлаждение и нагрев (комбинаторная теория игр) , различные преобразования игр, делающие их более поддающимися теории.
• Игра на соединение — тип игры, в которой игроки пытаются установить связи.
• Tablebase эндшпиля — база данных, в которой указано, как играть в эндшпили.
• Expectiminimax Tree — адаптация минимаксного дерева игры к играм с элементом случайности.
• Игра развернутой формы , дерево игры, обогащенное выигрышами и информацией, доступной игрокам.
• Классификация игр , статья, в которой обсуждаются способы классификации игр.
• Сложность игры — статья, описывающая способы измерения сложности игр.
• Игра Гранди — математическая игра, в которой разбиваются кучи предметов.
• Мультиагентная система — разновидность компьютерной системы для решения сложных задач.
• Позиционная игра — тип игры, в которой игроки претендуют на ранее невостребованные позиции.
• Решение шахмат
• Чеканка Сильвера — математическая игра по выбору целых положительных чисел, которые не являются суммой неотрицательных кратных ранее выбранных целых чисел.
• Игра Витхоффа — математическая игра, в которой нужно брать предметы из одной или двух стопок.
• Топологическая игра — разновидность математической игры, в которую играют в топологическом пространстве.
• Цугцванг , вынужденный играть, когда это невыгодно

Ссылки

• Альберт, Майкл Х .; Новаковски, Ричард Дж.; Вулф, Дэвид (2007). Уроки игры: введение в комбинаторную теорию игр . АК Питерс Лтд. ISBN  978-1-56881-277-9 .
• Бек, Йожеф (2008). Комбинаторные игры: теория крестиков-ноликов . Издательство Кембриджского университета. ISBN  978-0-521-46100-9 .
• Берлекамп, Э .; Конвей, Дж. Х. ; Гай, Р. (1982). Пути выигрыша в математических играх : Игры в целом . Академическая пресса. ISBN  0-12-091101-9 . 2-е изд., AK Peters Ltd (2001–2004), ISBN   1-56881-130-6 , ISBN   1-56881-142-X
• Берлекамп, Э.; Конвей, Дж. Х.; Гай, Р. (1982). Пути выигрыша в математических играх: в частности, в играх . Академическая пресса. ISBN  0-12-091102-7 . 2-е изд., AK Peters Ltd (2001–2004), ISBN   1-56881-143-8 , ISBN   1-56881-144-6 .
• Берлекамп, Элвин ; Вулф, Дэвид (1997). Математический ход: охлаждение достигает последней точки . АК Питерс Лтд. ISBN  1-56881-032-6 .
• Беверсдорф, Йорг (2021). Удача, логика и белая ложь: математика игр (2-е изд.). АК Петерс/CRC Press. дои : 10.1201/9781003092872 . ISBN  978-1-003-09287-2 . См. особенно разделы 21–26.
• Конвей, Джон Хортон (1976). О числах и играх . Академическая пресса. ISBN  0-12-186350-6 . 2-е изд., AK Peters Ltd (2001), ISBN   1-56881-127-6 .
• Роберт А. Хирн; Эрик Д. Демейн (2009). Игры, головоломки и вычисления . АК Петерс, ООО ISBN  978-1-56881-322-6 .

Внешние ссылки

• Список ссылок по комбинаторной теории игр на домашней странице Дэвида Эппштейна
• Введение в игры и числа Конвея Дирка Шлейхера и Майкла Столла.
• Краткое изложение терминов комбинационной теории игр Билла Спайта
• Семинар по комбинаторной теории игр, Международная исследовательская станция Банф, июнь 2005 г.