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

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

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

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

Наконец, в 2006 году (вскоре после публикации книги Питера Винклера « Математические головоломки» , которая способствовала популяризации проблемы ангелов) появилось четыре независимых и почти одновременных доказательства того, что ангел имеет выигрышную стратегию в двух измерениях.Брайан Bowditch в доказательстве работает для 4-ангела, в то время как Oddvar KLOSTER в доказательстве и András Mathe в доказательстве работы на 2-ангел. Петер Gács «s доказательство работает только для гораздо большей постоянная. Доказательства Боудитча и Мате опубликованы в журнале Combinatorics, Probability and Computing . Доказательство Клостера опубликовано в « Теоретической информатике»..

Другие нерешенные вопросы [ править ]

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

Эскизы доказательств [ править ]

Доказательство "Хранителя" [ править ]

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

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

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

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

Доказательство двух ангелов Мате [ править ]

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

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

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

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

Доказательство 4-х ангелов Боудитча [ править ]

Брайан Боудич определяет ^[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-дьяволом. Затем он показывает, что выигрышная стратегия в этой игре приведет к выигрышной стратегии в нашей исходной игре для четырех ангелов. Затем он показывает, что ангел, играющий в пятерку дьявола (игра 2), может добиться победы, используя довольно простой алгоритм.

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

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

См. Также [ править ]

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

Ссылки [ править ]

Внешние ссылки [ править ]

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