Просмотр кода страницы Задача об ангеле и дьяволе

'''Задача об ангеле и дьяволе''' — задача [[Теория игр|теории игр]], предложенная [[Конвей, Джон Хортон|Конвеем]] в 1982.'''<ref>{{книга
|ответственный=Richard Nowakowski
|автор=John H. Conway
|заглавие=Games of No Chance
|том=29
|издательство=MSRI Publications
|страницы=3-12
|год=1996}}
''[http://library.msri.org/books/Book29/files/conway.pdf The angel problem] {{Wayback|url=http://library.msri.org/books/Book29/files/conway.pdf |date=20200929142527 }}''</ref>.

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

===Правила игры===

[[Файл:Angel problem.svg|thumb|200px|Синяя линия окружает возможные положения ангела силы 3 на следующем ходу.]]

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

===Вопрос===

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

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

== История ==
Задача впервые опубликована в 1982 году в книге ''Winning Ways'' [[Берлекэмп, Элвин|Берлекампа]], [[Конвей, Джон Хортон|Конвея]] и [[Гай, Ричард Кеннет|Гая]]<ref>[[Берлекэмп, Элвин|Elwyn R. Berlekamp]], [[Конвей, Джон Хортон|John H. Conway]], and [[Гай, Ричард Кеннет|Richard K. Guy]], ''Winning Ways for your mathematical plays, volume 2: Games in Particular'', Academic Press, 1982.</ref> под названием «Ангел и поедатель квадратов».

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

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

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

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

* Если ангел всегда увеличивает расстояние от центральной клетки и дьявол может играть на одной плоскости, то ангел имеет выигрышную стратегию.
* Если ангел всегда увеличивает координаты и дьявол может играть только на двух плоскостях, то ангел имеет выигрышную стратегию.
* Ангел имеет выигрышную стратегию, если его сила равна 13 или выше.
* Если имеется бесконечное число дьяволов, и каждый играет на расстояниях <math>d_1 < d_2 < d_3 < \cdots</math>, то ангел всё же может выиграть, если будет иметь достаточно большую силу. (Под «игрой на расстоянии <math>d</math>» мы понимаем ограничение, при котором дьяволу не разрешено играть на меньшем расстоянии от начальной клетки).

Наконец, в 2006 году
(вскоре после выхода книги «Математические головоломки» [[Уинклер, Питер Манн|Питера Уинклер]], благодаря которой эта задача стала популярна) 
было представлено четыре независимых и почти одинаковых доказательства того, что ангел имеет выигрышную стратегию на плоской доске.
[http://homepages.warwick.ac.uk/~masgak/papers/bhb-angel.pdf Доказательство] {{не переведено 5|Боудич, Брайан|Боудича||Brian Bowditch}}<ref name="B">{{не переведено 5|Боудич, Брайан|Brian H. Bowditch||Brian Bowditch}}, ''The angel game in the plane'', Combin. Probab. Comput. 16(3):345-362, 2007.</ref> работает с ангелом силы 4, в то время как [https://web.archive.org/web/20160107125925/http://home.broadpark.no/~oddvark/angel/Angel.pdf доказательство] Оддвара Клостера и [http://homepages.warwick.ac.uk/~masibe/angel-mathe.pdf доказательство] Андре Мате<ref name="M">András Máthé, ''The angel of power 2 wins'', Combin. Probab. Comput. 16(3):363-374, 2007</ref> работают с ангелом силы 2. [http://www.cs.bu.edu/~gacs/papers/angel.pdf Доказательство] {{Wayback|url=http://www.cs.bu.edu/~gacs/papers/angel.pdf |date=20160304030433 }} Питера Гакса работает с куда большей силой. Доказательства Боудича и Мате были опубликованы в ''Combinatorics, Probability and Computing'' (редакторы {{не переведено 5|Болобас, Бела|Болобас||Béla Bollobás}} и {{не переведено 5|Лидер, Имре|Лидер||Imre Leader}}). Доказательство Клостера опубликовано в журнале ''Theoretical Computer Science''.

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

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

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

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

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

Это доказательство опубликовано {{не переведено 5|Лидер, Имре|Лидером||Imre Leader}} и {{не переведено 5|Болобас, Бела|Болобас||Béla Bollobás}} в 2006 году<ref>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</ref>. Похожее доказательство опубликовано Мартином Кутцем в 2005 году<ref>Martin Kutz, Conway’s Angel in three dimensions, ''Theoret. Comp. Sci.'' 349(3):443-451, 2005.</ref><ref>Martin Kutz, The Angel Problem, Positional Games, and Digraph Roots, [http://www.diss.fu-berlin.de/2004/250/ PhD Thesis] {{Wayback|url=http://www.diss.fu-berlin.de/2004/250/ |date=20071211223149 }} FU Berlin, 2004</ref>.

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

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

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

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

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

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

{{не переведено 5|Боудвич, Брайан|Боудвич||Brian Bowditch}} определяет<ref name="B"/> вариант (игра 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''-координату, а дьявол ограничен тремя плоскостями — неизвестно, имеет ли дьявол выигрышную стратегию.

== См. также ==
* [[Задача о водителе-убийце]], другая математическая игра, в которой медленный, но маневренный игрок пытается убежать от более быстрого, но менее маневренного врага.
* [[Теория гарантированного поиска]]

== Примечания ==
{{примечания}}

== Ссылки ==
* [http://www.msri.org/publications/books/Book29/files/conway.pdf The Angel problem by John H Conway]
* [https://web.archive.org/web/20080702081929/http://home.broadpark.no/~oddvark/angel/index.html Kloster’s Angel Problem site]

{{rq|checktranslate}}

[[Категория:Комбинаторная теория игр]]
[[Категория:Преследование-уклонение]]
[[Категория:Джон Конвей]]