Задача ангела

Задача ангела — это вопрос теории игр, предложенный Конвеем. Игру обычно называют игрой Ангела и Дьявола. Играют 2 игрока, называемые ангелом и дьяволом. Игра происходит на бесконечной шахматной доске (или, что то же самое, на точках двумерной решётки). Ангел имеет силу k (натуральное число 1 или больше), которая задаётся до начала игры. Игра начинается с пустой доски с ангелом, находящимся в центре. С каждым ходом ангел переходит на другую свободную клетку, которую можно достичь максимум за k ходов короля, то есть расстояние от начальной клетки не превосходит k в супремум-норме. Дьявол, в свою очередь, может добавить блокировку одного квадрата, не содержащего ангела. Ангел может перепрыгивать через заблокированные квадраты, но не может на них приземляться. Дьявол выигрывает, если ангел не может двигаться. Ангел выигрывает, если живёт бесконечно.

Задача ангела формулируется так: может ли ангел выиграть, если имеет достаточную силу?

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

Конвей объявил награду за общее решение задачи ($100 за выигрышную стратегию для ангела достаточной силы и $1000 за доказательство, что дьявол может выиграть независимо от силы ангела). Прогресс был сначала в больших измерениях. В 2006 году исходная задача решена, когда появились независимые доказательства, показывающие, что ангел может выиграть. Боудич доказал, что ангел силы 4 может выиграть, а Мате и Клостер дали доказательство, что ангел силы 2 может выиграть. Конвей не указал, кто получит приз, или все они получат по $100.

История

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

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

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

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

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

Наконец, в 2006 году, вскоре после публикации книги Петера Винклера Математические головоломки, в которой опубликована задача ангела, представлено 4 независимых и почти одинаковых доказательства, что ангел имеет выигрышную стратегию на плоской доске. [homepages.warwick.ac.uk/~masgak/papers/bhb-angel.pdf Доказательство] Боудича работает с ангелом силы 4, в то время как [home.broadpark.no/~oddvark/angel/Angel.pdf доказательство] Оддвара Клостера и [homepages.warwick.ac.uk/~masibe/angel-mathe.pdf доказательство] Андре Мате работают с ангелом силы 2. [www.cs.bu.edu/~gacs/papers/angel.pdf Доказательство] Петера Гакса работает с куда большей силой. Доказательства Боудича и Мате были опубликованы в Combinatorics, Probability and Computing (редакторы Болобас и Лидер). Доказательство Клостера опубликовано в журнале Theoretical Computer Science.

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

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

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

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

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

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

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

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

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

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

Доказательство Мате разбито на две части:

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

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

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

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

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

1. Ангел может вернуться на любую клетку, которую он уже посетил, даже если дьявол затем её пытался заблокировать.
2. k-дьявол должен посетить клетку k раз, прежде чем она будет заблокирована.
3. Ангел движется на одну клетку вверх/вниз/влево/вправо.
4. Для того, чтобы выиграть, ангел должен идти по круговому пути, описанному ниже.

Круговой путь — это путь <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> является полубесконечной дугой, ангел не вернётся на любую клетку, на которой он уже побывал, а потому путь будет выигрышным путём исходной игры.

См. также

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

Ссылки

• [www.msri.org/publications/books/Book29/files/conway.pdf The Angel problem by John H Conway]
• [home.broadpark.no/~oddvark/angel/index.html Kloster’s Angel Problem site]

Отрывок, характеризующий Задача ангела

Когда вышли в гостиную к кофе, старики сели вместе.
Князь Николай Андреич более оживился и высказал свой образ мыслей насчет предстоящей войны.
Он сказал, что войны наши с Бонапартом до тех пор будут несчастливы, пока мы будем искать союзов с немцами и будем соваться в европейские дела, в которые нас втянул Тильзитский мир. Нам ни за Австрию, ни против Австрии не надо было воевать. Наша политика вся на востоке, а в отношении Бонапарта одно – вооружение на границе и твердость в политике, и никогда он не посмеет переступить русскую границу, как в седьмом году.
– И где нам, князь, воевать с французами! – сказал граф Ростопчин. – Разве мы против наших учителей и богов можем ополчиться? Посмотрите на нашу молодежь, посмотрите на наших барынь. Наши боги – французы, наше царство небесное – Париж.
Он стал говорить громче, очевидно для того, чтобы его слышали все. – Костюмы французские, мысли французские, чувства французские! Вы вот Метивье в зашей выгнали, потому что он француз и негодяй, а наши барыни за ним ползком ползают. Вчера я на вечере был, так из пяти барынь три католички и, по разрешенью папы, в воскресенье по канве шьют. А сами чуть не голые сидят, как вывески торговых бань, с позволенья сказать. Эх, поглядишь на нашу молодежь, князь, взял бы старую дубину Петра Великого из кунсткамеры, да по русски бы обломал бока, вся бы дурь соскочила!
Все замолчали. Старый князь с улыбкой на лице смотрел на Ростопчина и одобрительно покачивал головой.
– Ну, прощайте, ваше сиятельство, не хворайте, – сказал Ростопчин, с свойственными ему быстрыми движениями поднимаясь и протягивая руку князю.
– Прощай, голубчик, – гусли, всегда заслушаюсь его! – сказал старый князь, удерживая его за руку и подставляя ему для поцелуя щеку. С Ростопчиным поднялись и другие.


Княжна Марья, сидя в гостиной и слушая эти толки и пересуды стариков, ничего не понимала из того, что она слышала; она думала только о том, не замечают ли все гости враждебных отношений ее отца к ней. Она даже не заметила особенного внимания и любезностей, которые ей во всё время этого обеда оказывал Друбецкой, уже третий раз бывший в их доме.
Княжна Марья с рассеянным, вопросительным взглядом обратилась к Пьеру, который последний из гостей, с шляпой в руке и с улыбкой на лице, подошел к ней после того, как князь вышел, и они одни оставались в гостиной.
– Можно еще посидеть? – сказал он, своим толстым телом валясь в кресло подле княжны Марьи.
– Ах да, – сказала она. «Вы ничего не заметили?» сказал ее взгляд.
Пьер находился в приятном, после обеденном состоянии духа. Он глядел перед собою и тихо улыбался.
– Давно вы знаете этого молодого человека, княжна? – сказал он.
– Какого?
– Друбецкого?
– Нет, недавно…
– Что он вам нравится?
– Да, он приятный молодой человек… Отчего вы меня это спрашиваете? – сказала княжна Марья, продолжая думать о своем утреннем разговоре с отцом.
– Оттого, что я сделал наблюдение, – молодой человек обыкновенно из Петербурга приезжает в Москву в отпуск только с целью жениться на богатой невесте.
– Вы сделали это наблюденье! – сказала княжна Марья.
– Да, – продолжал Пьер с улыбкой, – и этот молодой человек теперь себя так держит, что, где есть богатые невесты, – там и он. Я как по книге читаю в нем. Он теперь в нерешительности, кого ему атаковать: вас или mademoiselle Жюли Карагин. Il est tres assidu aupres d'elle. [Он очень к ней внимателен.]
– Он ездит к ним?
– Да, очень часто. И знаете вы новую манеру ухаживать? – с веселой улыбкой сказал Пьер, видимо находясь в том веселом духе добродушной насмешки, за который он так часто в дневнике упрекал себя.
– Нет, – сказала княжна Марья.
– Теперь чтобы понравиться московским девицам – il faut etre melancolique. Et il est tres melancolique aupres de m lle Карагин, [надо быть меланхоличным. И он очень меланхоличен с m elle Карагин,] – сказал Пьер.
– Vraiment? [Право?] – сказала княжна Марья, глядя в доброе лицо Пьера и не переставая думать о своем горе. – «Мне бы легче было, думала она, ежели бы я решилась поверить кому нибудь всё, что я чувствую. И я бы желала именно Пьеру сказать всё. Он так добр и благороден. Мне бы легче стало. Он мне подал бы совет!»
– Пошли бы вы за него замуж? – спросил Пьер.
– Ах, Боже мой, граф, есть такие минуты, что я пошла бы за всякого, – вдруг неожиданно для самой себя, со слезами в голосе, сказала княжна Марья. – Ах, как тяжело бывает любить человека близкого и чувствовать, что… ничего (продолжала она дрожащим голосом), не можешь для него сделать кроме горя, когда знаешь, что не можешь этого переменить. Тогда одно – уйти, а куда мне уйти?…
– Что вы, что с вами, княжна?
Но княжна, не договорив, заплакала.
– Я не знаю, что со мной нынче. Не слушайте меня, забудьте, что я вам сказала.
Вся веселость Пьера исчезла. Он озабоченно расспрашивал княжну, просил ее высказать всё, поверить ему свое горе; но она только повторила, что просит его забыть то, что она сказала, что она не помнит, что она сказала, и что у нее нет горя, кроме того, которое он знает – горя о том, что женитьба князя Андрея угрожает поссорить отца с сыном.
– Слышали ли вы про Ростовых? – спросила она, чтобы переменить разговор. – Мне говорили, что они скоро будут. Andre я тоже жду каждый день. Я бы желала, чтоб они увиделись здесь.
– А как он смотрит теперь на это дело? – спросил Пьер, под он разумея старого князя. Княжна Марья покачала головой.
– Но что же делать? До года остается только несколько месяцев. И это не может быть. Я бы только желала избавить брата от первых минут. Я желала бы, чтобы они скорее приехали. Я надеюсь сойтись с нею. Вы их давно знаете, – сказала княжна Марья, – скажите мне, положа руку на сердце, всю истинную правду, что это за девушка и как вы находите ее? Но всю правду; потому что, вы понимаете, Андрей так много рискует, делая это против воли отца, что я бы желала знать…
Неясный инстинкт сказал Пьеру, что в этих оговорках и повторяемых просьбах сказать всю правду, выражалось недоброжелательство княжны Марьи к своей будущей невестке, что ей хотелось, чтобы Пьер не одобрил выбора князя Андрея; но Пьер сказал то, что он скорее чувствовал, чем думал.
– Я не знаю, как отвечать на ваш вопрос, – сказал он, покраснев, сам не зная от чего. – Я решительно не знаю, что это за девушка; я никак не могу анализировать ее. Она обворожительна. А отчего, я не знаю: вот всё, что можно про нее сказать. – Княжна Марья вздохнула и выражение ее лица сказало: «Да, я этого ожидала и боялась».
– Умна она? – спросила княжна Марья. Пьер задумался.
– Я думаю нет, – сказал он, – а впрочем да. Она не удостоивает быть умной… Да нет, она обворожительна, и больше ничего. – Княжна Марья опять неодобрительно покачала головой.
– Ах, я так желаю любить ее! Вы ей это скажите, ежели увидите ее прежде меня.
– Я слышал, что они на днях будут, – сказал Пьер.
Княжна Марья сообщила Пьеру свой план о том, как она, только что приедут Ростовы, сблизится с будущей невесткой и постарается приучить к ней старого князя.


Женитьба на богатой невесте в Петербурге не удалась Борису и он с этой же целью приехал в Москву. В Москве Борис находился в нерешительности между двумя самыми богатыми невестами – Жюли и княжной Марьей. Хотя княжна Марья, несмотря на свою некрасивость, и казалась ему привлекательнее Жюли, ему почему то неловко было ухаживать за Болконской. В последнее свое свиданье с ней, в именины старого князя, на все его попытки заговорить с ней о чувствах, она отвечала ему невпопад и очевидно не слушала его.
Жюли, напротив, хотя и особенным, одной ей свойственным способом, но охотно принимала его ухаживанье.
Жюли было 27 лет. После смерти своих братьев, она стала очень богата. Она была теперь совершенно некрасива; но думала, что она не только так же хороша, но еще гораздо больше привлекательна, чем была прежде. В этом заблуждении поддерживало ее то, что во первых она стала очень богатой невестой, а во вторых то, что чем старее она становилась, тем она была безопаснее для мужчин, тем свободнее было мужчинам обращаться с нею и, не принимая на себя никаких обязательств, пользоваться ее ужинами, вечерами и оживленным обществом, собиравшимся у нее. Мужчина, который десять лет назад побоялся бы ездить каждый день в дом, где была 17 ти летняя барышня, чтобы не компрометировать ее и не связать себя, теперь ездил к ней смело каждый день и обращался с ней не как с барышней невестой, а как с знакомой, не имеющей пола.
Дом Карагиных был в эту зиму в Москве самым приятным и гостеприимным домом. Кроме званых вечеров и обедов, каждый день у Карагиных собиралось большое общество, в особенности мужчин, ужинающих в 12 м часу ночи и засиживающихся до 3 го часу. Не было бала, гулянья, театра, который бы пропускала Жюли. Туалеты ее были всегда самые модные. Но, несмотря на это, Жюли казалась разочарована во всем, говорила всякому, что она не верит ни в дружбу, ни в любовь, ни в какие радости жизни, и ожидает успокоения только там . Она усвоила себе тон девушки, понесшей великое разочарованье, девушки, как будто потерявшей любимого человека или жестоко обманутой им. Хотя ничего подобного с ней не случилось, на нее смотрели, как на такую, и сама она даже верила, что она много пострадала в жизни. Эта меланхолия, не мешавшая ей веселиться, не мешала бывавшим у нее молодым людям приятно проводить время. Каждый гость, приезжая к ним, отдавал свой долг меланхолическому настроению хозяйки и потом занимался и светскими разговорами, и танцами, и умственными играми, и турнирами буриме, которые были в моде у Карагиных. Только некоторые молодые люди, в числе которых был и Борис, более углублялись в меланхолическое настроение Жюли, и с этими молодыми людьми она имела более продолжительные и уединенные разговоры о тщете всего мирского, и им открывала свои альбомы, исписанные грустными изображениями, изречениями и стихами.