Проблема ангела - Angel problem

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

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

Проблема ангелов: может ли ангел с достаточно высокой силой победить?

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

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

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

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

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

История

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

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

В трех измерениях было показано, что:^{[нужна цитата ]}

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

Наконец, в 2006 г. (вскоре после публикации Питер Винклер книга Математические головоломки, что помогло популяризировать проблему ангелов) появилось четыре независимых и почти одновременных доказательства того, что ангел имеет выигрышную стратегию в двух измерениях.Брайан Боудитч доказательство работает на 4-го ангела, в то время как Одвар Клостер доказательство и Андраша Мате доказательство работа на 2 ангела. Петер Гач с доказательство работает только для гораздо большей постоянной. Доказательства Боудитча и Мате опубликованы в Комбинаторика, теория вероятностей и вычисления. Доказательство Клостера опубликовано в Теоретическая информатика.

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

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

Контрольные эскизы

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

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

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

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

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

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

Мате^[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}$ куда ${\displaystyle |\gamma _{i}|}$ - длина i-го цикла.

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

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

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

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

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

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

Рекомендации

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

внешняя ссылка

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