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

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

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

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

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

Основные стратегии и почему они не работают

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

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

История

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

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

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

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

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

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

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

Доказательные эскизы

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

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

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

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

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

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

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

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

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

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

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

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

$\forall i:|\gamma _{i}|\leq i$ где $|\gamma _{i}|$ длина i-го цикла.

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

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

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

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

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

Доказательство «Хранителя»

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

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

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

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

См. также

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

Ссылки

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

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

[conway1996-1] Джон Х. Конвей, Проблема ангела , в: Ричард Новаковски (редактор) «Игры без шансов» , том 29 публикации MSRI , страницы 3–12, 1996.

[B-2] Jump up to: Перейти обратно: ^а ^б Брайан Х. Боудич , «Игра ангелов в самолете», Комбин. Вероятно. Вычислить. 16(3):345-362, 2007.

[M-3] Jump up to: Перейти обратно: ^а ^б Андраш Мате, «Ангел власти 2 побеждает», Комбин. Вероятно. Вычислить. 16(3):363-374, 2007 г.

[K-4] О. Клостер, Решение проблемы ангела. Теоретическая информатика , вып. 389 (2007), вып. 1–2, стр. 152–161.

[5] Берлекамп, Элвин Р .; Конвей, Джон Х .; Гай, Ричард К. (1982), «Глава 19: Король и потребитель», Пути победы в ваших математических играх, Том 2: Игры в частности , Academic Press, стр. 607–634 .

[kutz2004-6] Jump up to: Перейти обратно: ^а ^б Мартин Куц, Проблема ангела, позиционные игры и корни орграфов, докторская диссертация FU Berlin, 2004 г.

[7] Б. Боллобас и И. Лидер, Ангел и дьявол в трех измерениях. Журнал комбинаторной теории, серия A. том. 113 (2006), вып. 1, стр. 176–184.

[8] Б. Боллобас и И. Лидер, Ангел и дьявол в трех измерениях. Журнал комбинаторной теории, серия A. том. 113 (2006), вып. 1, стр. 176–184.

[kutz2005-9] Мартин Куц, Ангел Конвея в трех измерениях, Теория. Комп. наук. 349(3):443–451, 2005.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]