Почему в задаче об Ангеле и Дьяволе (теория игр) побеждает Ангел?
Очевидно же, что Дьявол может построить стену вокруг Ангела (который привязан к стартовой позиции), нужно только строить стену так далеко, с запасом, на расстоянии больше чем к-ходов, что понадобились бы Ангелу для приближения к ней.
Тут проблема в математической записи или требованиям к "правильным доказательствам"? Потому что логически никаких проблем вроде нет (для меня и моего воображения, пусть даже если мы и имеем дело с бесконечностью).
Наверное всё дело в ограниченности математического синтаксиса?
Был бы рад если объясните в чём вообще сложность этой задачи и почему математики с 1982 не смогли закрыть вопрос.
p.s. У меня к сожалению нет математического бэкграунда. Есть только хорошее воображение и логика из программирования, так что рассуждаю конечно со своей колокольни.
> Если сила ангела равна 1, то дьявол имеет выигрышную стратегию.
В этом и вопрос. По мне так сила ангела может быть хоть 20, дьявол всё равно имеет преимущество, он лишь должен начать строить стену так "далеко", что даже с силой 20 ангел не успел к ней приблизиться до окончания строительства.
> так как ангел доберется до границы круга быстрее, чем дьявол постоит стену.
Почему?
> Что значит привязан к стартовой позиции?
Ну ангел же начинает откуда то своё движение, и при силе 20 может двигаться из этой точки куда угодно на 20 клеток. А дьявол при этом может начать портить клетки "вокруг" ангела, просто очеееень далеко. Пространство сетки то бесконечное. И он простроит стену и будет её сужать, пока не заберёт всё место выиграв.
ideological, я исходил из того, что дьявол будет строить стену ввиде круга, а длина окружности всетаки больше чем ее радиус, а радиус это растояние которое надо пройти ангелу.
TriKrista, Всё действительно так (с длиной окружности и радиусом). Но дьявол же не привязан к одному кругу и его траектории. Он может начать строить с какой-то стороны, а ангел выбираться в противоположную. Но потом дьявол начнёт строить стену ещё дальше уже в той стороне куда убегал ангел. И неоспоримое преимущество дьявола в том что его испорченные клетки "не сгорают" , направления "для вырывания" у ангела закончатся, ему придётся свернуть с прямой радиуса.
ideological, ангел(А) может тупо пойти на стену и обойти ее.
допустим дьявол(Д) начал строить стену на расстоянии nk, (k это сила), тоесть А может преодолеть это расстояние за n ходов, а Д сможет построить стену длиной n/k, c учетом того, что А может перепрыгивать стены, толщина которых меньше его силы, далее, в худшем случае, А надо потратить n/(2k^2) чтобы дойти до края стены, если Д не будет ее достраивать, но для него это не имеет смысла, так как он сможет построить только n/(2k^3) секций, тут можно на вскидку предположить, что А в любом случае дойдет до края. Тут Д лучше сразу строить новую стену, ну А опять ее обойдет, и так процесс будет продолжатся довольно долго, с учетом того, что для А это не лучшая стратегия.
Если А будет заведомо будет обходить стены, то для Д ситуация совсем печальная.
TriKrista, Ох. Вы правы, а я не достаточно подумал над этим. Спасибо что объяснили.
Но тогда действительно получается что фатальное преимущество у А при силе > 1. И с ним ничего не поделать. Так? Почему тогда не докажут что для Д победа не возможна, как ни крути?
ideological, Тут все зависит от стратегий игроков. Если А будет тупить, то Д может выиграть.
Тут, наверно, вопрос в том есть ли универсальная стратегия, при которой всегда выигрывает один из игроков. Но за подробностями проблематики лучше уже обращаться к математикам.