Русская Википедия:Задача об ангеле и дьяволе
Задача об ангеле и дьяволе — задача теории игр, предложенная Конвеем в 1982.[1].
Формулировка
Правила игры
Играют два игрока, называемые ангелом и дьяволом. Игра происходит на бесконечной шахматной доске. Ангел имеет «силу» k (это натуральное число 1 или больше), которая задаётся до начала игры. В начале игры ангел стоит на одной из клеток. С каждым ходом ангел переходит на другую свободную клетку, которую можно достичь максимум за k ходов короля. Дьявол, в свою очередь, может заблокировать одну клетку на которой нет ангела. Ангел может перепрыгивать через заблокированные клетки, но не может на них приземляться. Дьявол выигрывает, если ангел не может двигаться. Ангел выигрывает, если живёт бесконечно.
Вопрос
Может ли ангел выиграть, если имеет достаточную силу?
Более точно, необходимо найти стратегию выигрыша для одного из игроков. Если дьявол может выиграть, он должен сделать это за конечное число ходов. Если дьявол выиграть не может, то всегда имеется действие, которое ангел может предпринять, чтобы избежать проигрыша и выигрышная стратегия заключается в выборе такого хода. То есть, множество ходов, приводящих к выигрышу ангела, замкнуто в естественной топологии на множестве всех ходов и известно, что такие игры являются детерминированными.
История
Задача впервые опубликована в 1982 году в книге Winning Ways Берлекампа, Конвея и Гая[2] под названием «Ангел и поедатель квадратов».
Конвей объявил награду за общее решение задачи ($100 за выигрышную стратегию для ангела достаточной силы и $1000 за доказательство, что дьявол может выиграть независимо от силы ангела).
Для двумерного случая приведём некоторые ранние результаты:
- Если сила ангела равна 1, то дьявол имеет выигрышную стратегию. (Согласно Конвею, этот результат принадлежит Элвину Берлекампу).
- Если ангел никогда не уменьшает координаты, то дьявол имеет выигрышную стратегию (Conway, 1982).
- Если ангел всегда увеличивает расстояние от центральной клетки, то дьявол имеет выигрышную стратегию (Conway, 1996).
Для трёхмерной доски, было доказано, что:
- Если ангел всегда увеличивает расстояние от центральной клетки и дьявол может играть на одной плоскости, то ангел имеет выигрышную стратегию.
- Если ангел всегда увеличивает координаты и дьявол может играть только на двух плоскостях, то ангел имеет выигрышную стратегию.
- Ангел имеет выигрышную стратегию, если его сила равна 13 или выше.
- Если имеется бесконечное число дьяволов, и каждый играет на расстояниях <math>d_1 < d_2 < d_3 < \cdots</math>, то ангел всё же может выиграть, если будет иметь достаточно большую силу. (Под «игрой на расстоянии <math>d</math>» мы понимаем ограничение, при котором дьяволу не разрешено играть на меньшем расстоянии от начальной клетки).
Наконец, в 2006 году (вскоре после выхода книги «Mathematical Puzzles» Питера Винклера, благодаря которой эта задача стала популярна) было представлено четыре независимых и почти одинаковых доказательства того, что ангел имеет выигрышную стратегию на плоской доске. Доказательство Шаблон:Не переведено 5[3] работает с ангелом силы 4, в то время как доказательство Оддвара Клостера и доказательство Андре Мате[4] работают с ангелом силы 2. Доказательство Шаблон:Wayback Питера Гакса работает с куда большей силой. Доказательства Боудича и Мате были опубликованы в Combinatorics, Probability and Computing (редакторы Шаблон:Не переведено 5 и Шаблон:Не переведено 5). Доказательство Клостера опубликовано в журнале Theoretical Computer Science.
Наброски доказательств
Доказательство «Охранник»
Доказательство, показывающее, что трёхмерная версия игры с ангелом достаточно большой силы имеет выигрышную стратегию, использует «охранников». Для любого куба любого размера имеется охранник, который наблюдает за кубом. Перед каждым ходом охранник решает, является ли куб, за которым он наблюдает, опасным, безопасным или почти безопасным. Определения «безопасный» и «почти безопасный» следует пояснить — это решение базируется чисто на плотности блокирующих точек в кубе и размере куба.
Если ход ангела заранее не определён, просто движемся вверх. Если некоторые кубы, которые ангел покидает, безопасны, то охраннику наибольшего куба предписывается обеспечить выход ангела из куба через одну из граней куба. Если охраннику предписано сопровождать ангела вовне к определённой грани, охранник делает это путём построения пути по безопасным подкубам. Охранникам в этих кубах предписывается сопровождать ангела по его подкубам. Путь ангела в подкубе не определён, пока ангел не попадёт в этот куб. Даже в этом случае путь определён грубо. Стратегия гарантирует, что дьявол не может выбрать место на пути ангела достаточно далеко и заблокировать его.
Можно доказать, что стратегия работает, поскольку время, которое нужно дьяволу, чтобы превратить безопасный куб на пути ангела в опасный, длиннее, чем время, за которое ангел достигает этот куб.
Это доказательство опубликовано Шаблон:Не переведено 5 и Шаблон:Не переведено 5 в 2006 году[5]. Похожее доказательство опубликовано Мартином Кутцем в 2005 году[6][7].
Доказательство Мате для ангела с силой 2
Мате[4] ввёл тактичного дьявола, никогда не разрушающего клетку, которую ангел занимал ранее. Если ангел играет против тактичного дьявола, принимается, что дьявол выигрывает, если ограничивает движение ангела в ограниченной области (в противном случае ангел просто прыгает взад-вперёд в двух клетках и никогда не проиграет!).
Мате дал явную выигрышную стратегию для ангела против тактичного дьявола и показал, что если ангел выигрывает у тактичного дьявола, то ангел выигрывает у настоящего дьявола.
В первой части ангел выигрывает у тактичного дьявола предполагая, что вся левая полуплоскость разрушена (вдобавок ко всем клеткам, разрушенным дьяволом), и трактуя разрушенные клетки как стены лабиринта, который обходят по правилу «левой руки». То есть, ангел держит левую руку на стене лабиринта и идёт вдоль стены. Можно доказать, что тактичный дьявол не может схватить ангела, принявшего такую стратегию.
Вторая часть доказывается от противного, а потому доказательство Мате не даёт немедленно выигрышной стратегии против действительного дьявола. Однако Мате замечает, что это доказательство, в принципе, может быть приспособлено для получения такой стратегии.
Доказательство Боудича для ангела с силой 4
Шаблон:Не переведено 5 определяет[3] вариант (игра 2) начальной игры со следующими изменениями правил:
- Ангел может вернуться на любую клетку, которую он уже посетил, даже если дьявол затем её пытался заблокировать.
- k-дьявол должен посетить клетку k раз, прежде чем она будет заблокирована.
- Ангел движется на одну клетку вверх/вниз/влево/вправо.
- Для того, чтобы выиграть, ангел должен идти по круговому пути, описанному ниже.
Круговой путь — это путь <math>\pi = \cup^{\infty}_{i=1} (\sigma_i \cup \gamma_i)</math>, где <math>\sigma = \cup^{\infty}_{i=1} \sigma_i</math> является полубесконечной дугой (самонепересекающийся путь с начальной точкой, но не имеющей конечной точки) и <math>{\gamma_i}</math> являются попарно несвязными петлями со следующими свойствами:
- <math>\forall i: |\gamma_i|\leq i</math> где <math>|\gamma_i|</math> — длина i-ой петли.
(Для полной определённости <math>\gamma_i</math> должна начинаться и кончаться в конечной точке <math>\sigma_i</math> и <math>\sigma_i</math> должна кончаться в начальной точке <math>\sigma_{i+1}</math>.)
Боудвич предполагает вариант (игра 1) игры c изменениями 2 и 3 и 5-дьяволом. Он показал, что выигрышная стратегия в этой игре даст выигрышную стратегию исходной игры для ангела силы 4. Он также показал, что ангел, играющий против 5-дьявола (игра 2) может достичь выигрыша с использованием довольно простого алгоритма.
Боудвич утверждает, что ангел с силой 4 может выиграть исходную версию игры, представив, что фантомный ангел играет против 5-дьявола в игре 2.
Ангел следует по возможному пути фантомного ангела, но избегает петель. Поскольку путь <math>\sigma</math> является полубесконечной дугой, ангел не вернётся на любую клетку, на которой он уже побывал, а потому путь будет выигрышным путём исходной игры.
Вариации и обобщения
- В трёхмерном пространстве при условии, что ангел всегда увеличивает y-координату, а дьявол ограничен тремя плоскостями — неизвестно, имеет ли дьявол выигрышную стратегию.
См. также
- Задача о водителе-убийце, другая математическая игра, в которой медленный, но маневренный игрок пытается убежать от более быстрого, но менее маневренного врага.
- Теория гарантированного поиска
Примечания
Ссылки
- ↑ Шаблон:Книга The angel problem Шаблон:Wayback
- ↑ Elwyn R. Berlekamp, John H. Conway, and Richard K. Guy, Winning Ways for your mathematical plays, volume 2: Games in Particular, Academic Press, 1982.
- ↑ 3,0 3,1 Шаблон:Не переведено 5, The angel game in the plane, Combin. Probab. Comput. 16(3):345-362, 2007.
- ↑ 4,0 4,1 András Máthé, The angel of power 2 wins, Combin. Probab. Comput. 16(3):363-374, 2007
- ↑ B. Bollobás and I. Leader, The angel and the devil in three dimensions. Journal of Combinatorial Theory. Series A. vol. 113 (2006), no. 1, pp. 176—184
- ↑ Martin Kutz, Conway’s Angel in three dimensions, Theoret. Comp. Sci. 349(3):443-451, 2005.
- ↑ Martin Kutz, The Angel Problem, Positional Games, and Digraph Roots, PhD Thesis Шаблон:Wayback FU Berlin, 2004
