Введение

Проблема ангела — это вопрос в теории комбинаторных игр, предложенный Джоном Хортоном Конвеем. Игра обычно называется игрой ангелов и демонов. В эту игру играют два игрока: ангел и демон. Игра ведётся на бесконечной шахматной доске (или, что эквивалентно, на точках двумерной решётки). Ангел обладает силой *k* (натуральное число, равное 1 или больше), которая определяется до начала игры. Доска начинается пустой, и ангел находится на одном поле. На каждом ходу ангел перемещается на другое пустое поле, до которого можно добраться не более чем за *k* ходов шахматного короля, то есть расстояние от начального поля не превышает *k* в бесконечной метрике. Демон, в свою очередь, может установить блок на любом поле, не занятом ангелом. Ангел может перепрыгивать через заблокированные поля, но не может приземляться на них. Демон побеждает, если ангел не может сделать ход. Ангел побеждает, если сможет продолжать игру бесконечно. Задача состоит в том, может ли ангел с достаточно большой силой победить? Должна существовать выигрышная стратегия для одного из игроков. Если демон может принудить к победе, он может сделать это за конечное число ходов. Если демон не может принудить к победе, то всегда есть ход, который ангел может сделать, чтобы избежать проигрыша, и его выигрышная стратегия всегда заключается в выборе такого хода. Более абстрактно, «множество выигрышей» (то есть множество всех партий, в которых побеждает ангел) является замкнутым множеством (в естественной топологии на множестве всех партий), и известно, что такие игры определены. Разумеется, в любой бесконечной игре, если у второго игрока нет выигрышной стратегии, первый игрок всегда может выбрать ход, который приводит к позиции, где у второго игрока нет выигрышной стратегии, но в некоторых играх просто бесконечное продолжение игры не даёт победы первому игроку, поэтому могут существовать неопределённые игры. Конвей предложил вознаграждение за общее решение этой проблемы (100 долларов за выигрышную стратегию для ангела с достаточно большой силой и 1000 долларов за доказательство того, что демон может победить независимо от силы ангела). Первые успехи были достигнуты в пространствах более высокой размерности. В конце 2006 года исходная проблема была решена, когда появились независимые доказательства, показывающие, что ангел может победить. Боудитч доказал, что ангел с силой 4 (то есть с *k* = 4) может выиграть, а Мате и Клостер предоставили доказательства того, что ангел с силой 2 может выиграть.

Основные стратегии и почему они не работают

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

Другие нерешенные вопросы

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

Клостер - доказательство двух ангелов

Оддвар Клостер открыл конструктивный алгоритм решения задачи с 2 ангелами. Этот алгоритм довольно прост и также оптимален, поскольку, как отмечалось выше, дьявол имеет выигрышную стратегию против 1 ангела. Мы начинаем с того, что проводим вертикальную линию непосредственно слева от начальной позиции ангела, вниз и вверх. Эта линия представляет путь, по которому пойдет ангел, который будет обновляться после каждого хода дьявола, и разделяет квадраты доски на "левое множество" и "правое множество". Как только квадрат становится частью левого множества, он останется там до конца игры, и ангел не будет совершать никаких дальнейших ходов на эти квадраты. Каждый раз, когда дьявол блокирует новый квадрат, мы ищем все возможные модификации пути, чтобы переместить один или несколько квадратов из правого множества, заблокированных дьяволом, в левое множество. Мы сделаем это только в том случае, если длина пути увеличится не более чем в два раза по сравнению с количеством заблокированных квадратов, перемещенных в левое множество. Из таких подходящих путей мы выбираем тот, который перемещает наибольшее количество заблокированных квадратов в левое множество. Затем ангел делает два шага вдоль этого пути, удерживая путь слева от себя при движении вперед (так что, если бы дьявол не блокировал квадраты, ангел двигался бы бесконечно на север). Обратите внимание, что при движении по часовой стрелке вокруг угла ангел не делает хода, потому что два сегмента, касающиеся угла, имеют один и тот же квадрат справа от них.

Мате - доказательство двух ангелов

Мате Существенно схожее доказательство было опубликовано Мартином Куцем в 2005 году.