Задача об ангеле и дьяволе

Задача об ангеле и дьяволе — задача теории игр, предложенная Конвеем в 1982..

Формулировка

Правила игры

Играют два игрока, называемые ангелом и дьяволом. Игра происходит на бесконечной шахматной доске. Ангел имеет «силу» k (это натуральное число 1 или больше), которая задаётся до начала игры. В начале игры ангел стоит на одной из клеток. С каждым ходом ангел переходит на другую свободную клетку, которую можно достичь максимум за k ходов короля. Дьявол, в свою очередь, может заблокировать одну клетку на которой нет ангела. Ангел может перепрыгивать через заблокированные клетки, но не может на них приземляться. Дьявол выигрывает, если ангел не может двигаться. Ангел выигрывает, если живёт бесконечно.

Вопрос

Может ли ангел выиграть, если имеет достаточную силу?

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

История

Задача впервые опубликована в 1982 году в книге Winning Ways Берлекампа, Конвея и Гая под названием «Ангел и поедатель квадратов».

Конвей объявил награду за общее решение задачи ($100 за выигрышную стратегию для ангела достаточной силы и $1000 за доказательство, что дьявол может выиграть независимо от силы ангела).

Для двумерного случая приведём некоторые ранние результаты:

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

Для трёхмерной доски, было доказано, что:

• Если ангел всегда увеличивает расстояние от центральной клетки и дьявол может играть на одной плоскости, то ангел имеет выигрышную стратегию.
• Если ангел всегда увеличивает координаты и дьявол может играть только на двух плоскостях, то ангел имеет выигрышную стратегию.
• Ангел имеет выигрышную стратегию, если его сила равна 13 или выше.
• Если имеется бесконечное число дьяволов, и каждый играет на расстояниях d 1 < d 2 < d 3 < ⋯ {displaystyle d_{1}<d_{2}<d_{3}<cdots } , то ангел всё же может выиграть, если будет иметь достаточно большую силу. (Под «игрой на расстоянии d {displaystyle d} » мы понимаем ограничение, при котором дьяволу не разрешено играть на меньшем расстоянии от начальной клетки).

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

Наброски доказательств

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

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

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

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

Это доказательство опубликовано Лидером и Болобас в 2006 году. Похожее доказательство опубликовано Мартином Кутцем в 2005 году.

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

Мате ввёл тактичного дьявола, никогда не разрушающего клетку, которую ангел занимал ранее. Если ангел играет против тактичного дьявола, принимается, что дьявол выигрывает, если ограничивает движение ангела в ограниченной области (в противном случае ангел просто прыгает взад-вперёд в двух клетках и никогда не проиграет!).

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

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

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

Доказательство Боудича для ангела с силой 4

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

Круговой путь — это путь π = ∪ i = 1 ∞ ( σ i ∪ γ i ) {displaystyle pi =cup _{i=1}^{infty }(sigma _{i}cup gamma _{i})} , где σ = ∪ i = 1 ∞ σ i {displaystyle sigma =cup _{i=1}^{infty }sigma _{i}} является полубесконечной дугой (самонепересекающийся путь с начальной точкой, но не имеющей конечной точки) и γ i {displaystyle {gamma _{i}}} являются попарно несвязными петлями со следующими свойствами:

• ∀ i : | γ i | ≤ i {displaystyle forall i:|gamma _{i}|leq i} где | γ i | {displaystyle |gamma _{i}|} — длина i-ой петли.

(Для полной определённости γ i {displaystyle gamma _{i}} должна начинаться и кончаться в конечной точке σ i {displaystyle sigma _{i}} и σ i {displaystyle sigma _{i}} должна кончаться в начальной точке σ i + 1 {displaystyle sigma _{i+1}} .)

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

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

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

Вариации и обобщения

• В трёхмерном пространстве при условии, что ангел всегда увеличивает y-координату, а дьявол ограничен тремя плоскостями — неизвестно, имеет ли дьявол выигрышную стратегию.