Проблема ангела

Вопрос по комбинаторной теории игр

Синяя пунктирная область показывает, куда мог бы дотянуться ангел силы 3.

Задача ангела — это вопрос в комбинаторной теории игр, предложенный Джоном Хортоном Конвеем . Эту игру обычно называют игрой ангелов и дьяволов . ^[1] В игру играют два игрока, которых называют ангелом и дьяволом . Она играется на бесконечной шахматной доске (или, что эквивалентно, в точках двумерной решетки ). Ангел имеет силу k ( натуральное число 1 или выше), указанную до начала игры. Доска начинается пустой, а ангел находится на одной клетке. На каждом ходу ангел прыгает на другую пустую клетку, до которой можно добраться максимум за k ходов шахматного короля , то есть расстояние от начальной клетки не превышает k в норме бесконечности . Дьявол, в свой ход, может добавить блок на любую отдельную клетку, не содержащую ангела. Ангел может перепрыгивать через заблокированные клетки, но не может приземлиться на них. Дьявол побеждает, если ангел не может двигаться. Ангел побеждает, выживая неограниченное время.

Проблема ангела заключается в следующем: может ли ангел с достаточно большой силой победить?

Должна существовать выигрышная стратегия для одного из игроков. Если дьявол может заставить выиграть, то он может сделать это за конечное число ходов. Если дьявол не может заставить выиграть, то всегда есть действие, которое ангел может предпринять, чтобы избежать проигрыша, и выигрышная стратегия для него всегда состоит в выборе такого хода. Более абстрактно, «множество выплат» (т. е. множество всех ходов, в которых выигрывает ангел) является замкнутым множеством (в естественной топологии на множестве всех ходов), и известно, что такие игры определены . Конечно, для любой бесконечной игры, если у игрока 2 нет выигрышной стратегии, игрок 1 всегда может выбрать ход, который приведет к позиции, в которой у игрока 2 нет выигрышной стратегии, но в некоторых играх простая игра вечно не дает выигрыша игроку 1, поэтому могут существовать неопределенные игры.

Конвей предложил награду за общее решение этой проблемы (100 долларов за выигрышную стратегию для ангела достаточно высокой силы и 1000 долларов за доказательство того, что дьявол может победить независимо от силы ангела). Сначала прогресс был достигнут в более высоких измерениях. В конце 2006 года изначальная проблема была решена, когда появились независимые доказательства, показывающие, что ангел может победить. Боудич доказал, что 4-ангел (то есть ангел с силой k  = 4) может победить ^[2] , а Мате ^[3] и Клостер ^[4] дали доказательства того, что 2-ангел может победить.

История

Задача была впервые опубликована в 1982 году в книге « Winning Ways» Берлекэмпа, Конвея и Гая ^[5] под названием «ангел и пожиратель квадратов». В двух измерениях некоторые ранние частичные результаты включали:

• Если у ангела сила 1, у дьявола выигрышная стратегия (Конвей, 1982). (По мнению Конвея, этот результат на самом деле принадлежит Берлекэмпу .) Это можно прочитать в разделе 1.1 статьи Куца. ^[6]
• Если ангел никогда не уменьшает свою координату y, то у дьявола есть выигрышная стратегия (Конвей, 1982).
• Если ангел всегда увеличивает свое расстояние от источника, то у дьявола есть выигрышная стратегия (Конвей, 1996).

В трех измерениях было показано, что:

• Если ангел всегда увеличивает свою координату y, а дьявол может играть только в одной плоскости, то у ангела есть выигрышная стратегия. ^[7]
• Если ангел всегда увеличивает свою координату y, а дьявол может играть только в двух плоскостях, то у ангела есть выигрышная стратегия.
• У ангела есть выигрышная стратегия, если его сила 13 или больше.
• Если у нас есть бесконечное число дьяволов, каждый из которых играет на расстоянии , то ангел все равно может победить, если у него достаточно большая сила. (Под «игрой на расстоянии » мы подразумеваем, что дьяволу не разрешено играть на этом расстоянии от начала координат). ${\displaystyle d_{1}<d_{2}<d_{3}<\cdots }$ ${\displaystyle d}$

Наконец, в 2006 году (вскоре после публикации книги Питера Винклера «Математические головоломки », которая помогла популяризировать задачу об ангеле) появились четыре независимых и почти одновременных доказательства того, что у ангела есть выигрышная стратегия в двух измерениях. Доказательство Брайана Боудича работает для 4-ангела, в то время как доказательство Оддвара Клостера и доказательство Андраша Мате работают для 2-ангела. Кроме того, у Питера Гача есть заявленное доказательство, заархивированное 04.03.2016 в Wayback Machine , которое требует гораздо более сильного ангела; детали довольно сложны и не были рассмотрены журналом на точность. Доказательства Боудича и Мате были опубликованы в Combinatorics, Probability and Computing . Доказательство Клостера было опубликовано в Theoretical Computer Science .

Дальнейшие нерешенные вопросы

В 3D, учитывая, что ангел всегда увеличивает свою координату y , а дьявол ограничен тремя плоскостями, неизвестно, есть ли у дьявола выигрышная стратегия.

Эскизы для проверки

Доказательство двух ангелов Клостера

Оддвар Клостер открыл конструктивный алгоритм решения задачи с 2-ангелом. Этот алгоритм довольно прост и также оптимален, поскольку, как отмечено выше, у дьявола есть выигрышная стратегия против 1-ангела.

Мы начинаем с рисования вертикальной линии сразу слева от начальной позиции ангела, вниз и вверх до . Эта линия представляет собой путь, по которому пойдет ангел, который будет обновляться после каждого хода дьявола, и разделяет квадраты доски на «левый набор» и «правый набор». Как только квадрат становится частью левого набора, он остается таковым до конца игры, и ангел не будет делать никаких дальнейших ходов ни в один из этих квадратов. Каждый раз, когда дьявол блокирует новый квадрат, мы ищем все возможные модификации пути таким образом, чтобы переместить один или несколько квадратов в правом наборе, которые дьявол заблокировал, в левый набор. Мы сделаем это только в том случае, если путь увеличится в длину не более чем на удвоенное количество заблокированных квадратов, перемещенных в левый набор. Из таких подходящих путей мы выбираем тот, который перемещает наибольшее количество заблокированных квадратов в левый набор. Затем ангел делает два шага по этому пути, сохраняя путь слева от себя при движении вперед (так что если бы дьявол не блокировал квадраты, ангел бы двигался на север бесконечно). Обратите внимание, что при движении по часовой стрелке вокруг угла ангел не сдвинется на один шаг, потому что два сегмента, касающиеся угла, имеют один и тот же квадрат справа. ${\displaystyle y=-\infty }$ ${\displaystyle y=\infty }$

Доказательство Мате с двумя ангелами

Мате ^[3] вводит доброго дьявола, который никогда не уничтожает клетку, которую ангел мог бы занять на предыдущем ходу. Когда ангел играет против доброго дьявола, он признает поражение, если дьяволу удается ограничить его конечной ограниченной областью доски (иначе ангел мог бы просто прыгать туда-сюда между двумя клетками и никогда не проигрывать). Доказательство Мате распадается на две части:

1. он показывает, что если ангел побеждает доброго дьявола, то ангел побеждает настоящего дьявола;
2. он дает четкую выигрышную стратегию для ангела против доброго дьявола.

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

Доказательство первой части — от противного, и, следовательно, доказательство Мате не дает немедленно явной выигрышной стратегии против настоящего дьявола. Однако Мате замечает, что его доказательство в принципе можно адаптировать, чтобы дать такую ​​явную стратегию.

Четырехангеловое доказательство Боудича

Брайан Боудич определяет ^[2] вариант (игру 2) оригинальной игры со следующими изменениями правил:

1. Ангел может вернуться на любую клетку, на которой он уже побывал, даже если дьявол впоследствии попытается помешать ему.
2. k-черт должен посетить клетку k раз, прежде чем она будет заблокирована.
3. Ангел перемещается на одну клетку вверх, вниз, влево или вправо (ход герцога).
4. Чтобы победить, ангел должен проложить окружной путь (определение дано ниже).

Окружной путь — это путь, где — полубесконечная дуга (несамопересекающийся путь с начальной точкой, но без конечной точки) и — попарно непересекающиеся петли со следующим свойством: ${\displaystyle \pi =\cup _{i=1}^{\infty }(\sigma _{i}\cup \gamma _{i})}$ ${\displaystyle \sigma =\cup _{i=1}^{\infty }\sigma _{i}}$ ${\displaystyle {\gamma _{i}}}$

• ${\displaystyle \forall i:|\gamma _{i}|\leq i}$где - длина i-го контура. ${\displaystyle |\gamma _{i}|}$

(Чтобы быть хорошо определенным, он должен начинаться и заканчиваться в конечной точке и заканчиваться в начальной точке .) ${\displaystyle \gamma _{i}}$ ${\displaystyle \sigma _{i}}$ ${\displaystyle \sigma _{i}}$ ${\displaystyle \sigma _{i+1}}$

Боудич рассматривает вариант (игра 1) игры с изменениями 2 и 3 с 5-дьяволом. Затем он показывает, что выигрышная стратегия в этой игре даст выигрышную стратегию в нашей исходной игре для 4-ангела. Затем он продолжает показывать, что ангел, играющий с 5-дьяволом (игра 2), может добиться победы, используя довольно простой алгоритм.

Боудич утверждает, что 4-ангел может выиграть в оригинальной версии игры, представив себе призрачного ангела, играющего с 5-дьяволом во 2-й игре.

Ангел следует по пути, по которому шел бы фантом, но избегая петель. Следовательно, поскольку путь представляет собой полубесконечную дугу, ангел не возвращается ни на одну клетку, на которой он уже был, и поэтому этот путь является выигрышным даже в оригинальной игре. ${\displaystyle \sigma }$

3D-версия проблемы

Доказательство "Гардиан"

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

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

Эффективность этой стратегии доказана, поскольку дьяволу требуется больше времени, чтобы превратить безопасный куб на пути ангела в небезопасный куб, чем время, необходимое ангелу, чтобы добраться до этого куба.

Это доказательство было опубликовано Имре Лидером и Белой Боллобашем в 2006 году. ^[8] По сути похожее доказательство было опубликовано Мартином Кутцем в 2005 году. ^{[6] [9]}

Смотрите также

• Задача о шофере-убийце — еще одна математическая игра, в которой сильный и маневренный противник сталкивается с весьма изобретательным, но менее сильным противником.
• Преследование-уклонение , похожее семейство задач.
• демон Максвелла
• демон Лапласа

Ссылки

1. Джон Х. Конвей, Проблема ангела , в: Ричард Новаковски (редактор) Игры без шансов , том 29 MSRI Publications , страницы 3–12, 1996.
2. Брайан Х. Боудич , «Игра ангела в плоскости», Комбин. вероятност. вычисления 16(3):345-362, 2007.
3. Андраш Мате, «Ангел силы 2 побеждает», Комбин. Вероятно. Вычислить. 16(3):363-374, 2007 г.
4. О. Клостер, Решение проблемы ангела. Теоретическая информатика , т. 389 (2007), № 1-2, стр. 152–161
5. Берлекамп, Элвин Р .; Конвей, Джон Х.; Гай , Ричард К. (1982), «Глава 19: Король и потребитель», Выигрышные пути для ваших математических игр, Том 2: Игры в частности , Academic Press, стр. 607–634.
6. Мартин Куц, Проблема ангелов, позиционные игры и корни орграфов, докторская диссертация Свободный университет Берлин, 2004
7. Б. Боллобас и И. Лидер, Ангел и дьявол в трех измерениях. Журнал комбинаторной теории, Серия A. т. 113 (2006), № 1, стр. 176–184
8. Б. Боллобас и И. Лидер, Ангел и дьявол в трех измерениях. Журнал комбинаторной теории, Серия A. т. 113 (2006), № 1, стр. 176–184
9. Мартин Куц, Ангел Конвея в трех измерениях, Theoret. Comp. Sci. 349(3):443–451, 2005.

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

• Проблема Ангела Джона Х. Конвея
• Сайт проблем Клостера Ангела