Лиса, Утка и озеро.

[Dmitriy40]

grizzly
Скажите пожалуйста величину $y$ принятия решения для $k=5{,}90143057$? У меня по формуле выше получается $y \approx 0{,}29331643$, это правильная цифра?

В таком случае утка из точки $(0;0{,}29331643)$ (лиса оставалась в точке $(0;-1)$) плывёт строго под углом 45° в точку $(-0{,}173496877;0{,}173496877)$, в этот момент лиса достигает угла квадрата $(1;-1)$,

UPD. Убил лишнее ошибочное, простите, координата $x$ неправильна.

[grizzly]

Dmitriy40 в сообщении #1289501 писал(а):

В таком случае утка из точки $(0;0{,}29331643)$ (лиса оставалась в точке $(0;-1)$) плывёт строго под углом 45° в точку $(-0{,}173496877;0{,}173496877)$

Проверьте, пожалуйста, арифметику. Расстояние между двумя процитированными точками больше чем 0,21. Если умножить даже на 5.7 -- это намного больше 1. То есть лиса забегает намного дальше угла. Да и зачем утке плыть к стороне через угол? Ведь 5.786 посчитано как раз исходя из оптимальной траектории утки из этой верхней точки к стороне по прямой (прямая под углом, см. формулы в предыдущих сообщениях).
(Я до вечера покидаю тему.)

[Dmitriy40]

grizzly в сообщении #1289505 писал(а):

Проверьте, пожалуйста, арифметику.

Да, точно, я ошибся с координатой $x$, зря приравнял её к $y$, она заметно меньше.

[wrest]

(Dmitriy40)

Я бы числа писал не в теге TeX, т.к. их тогда трудно копипастить в калькулятор или эксель или еще куда

[Dmitriy40]

Пожалуй я соглашусь с величиной $k \approx 5{,}786$ для озвученной стратегии лисы. Не вижу никакой более оптимальной траектории утки. Для квадратной фигуры смены стратегий лисы. Если же она не квадратная - надо думать (вероятно можно найти более выгодную начальную ситуацию для старта утки по прямой к берегу), но непонятно в чём выигрыш для лисы неквадратной формы.
К форме фигуры безопасности это отношения не имеет, лучше принять уже предложенное название фигуры принятия решения.

(wrest)

wrest в сообщении #1289508 писал(а):

Я бы числа писал не в теге TeX,

Да я бы с радостью, но ведь правилами же не одобряется, это не компьютерные тексты. Так что пожелание не ко мне, к модераторам.

[grizzly]

Кстати, тут рядом мелькает тема про математику в индустрии гемблинга. Интересно, если найти сколько-то оптимальную стратегию за лису на произвольном выпуклом центрально-симметричном озере, можно ли сделать головоломку, в которой игрок будет пошагово (шаг может длиться несколько секунд, пока нажата кнопка) играть за утку? А форма озера выбирать на старте случайно, например. Ну или по опции: "играть стандартную / случайную карту".

(Я никогда не видел игрушек на смарт-телефонах и мне сложно судить, насколько это там перспективно. Но с точки зрения "детской" головоломки не самая плохая идея, думаю, даже для компа, а не телефона. И не раскрученная ведь ещё.)

[worm2]

Мне не даёт покоя мысль об AlphaZero
Думаю, она бы легко справилась с любой геометрией.

[Dmitriy40]

Решил нарисовать границу области принятия решения, исходя из следующих условий: внутри области лиса отслеживает координату $x$ утки, на границе лисе должно быть одинаково бежать против часовой стрелки до северной точки встречи и до западной точки встречи, утка в обе точки встречи плывёт по горизонтальной или вертикальной прямой. Кривую рисовал лишь для области выше диагонали квадрата (т.е. 1/8 всей кривой), остальные части очевидно симметричны. Уравнение кривой (неявное): $(4-2x)/(1-y)=(6-x-y)/(1+x)$, упрощать лень, так хоть видны явно оба пути лисы. Вот что получилось (область от центра до красных кривых), более вертикальную часть добавил исходя из симметрии:

Серая кривая - диагональ квадрата, зеленая - прямая из северной точки границы в точку на диагонали (её наклон равен $0{,}36134$, что сильно больше $\tg(1/k) \approx 0{,}17726$). Координаты точек: $(0;0{,}29843788)$ и $(0{,}2192236;0{,}2192236)$.

На самом деле есть сомнения в верности всех точек кроме на осях координат и пожалуй на диагонали. Потому что отсутствует условие возврата лисы к отслеживанию координат утки. Если же его добавить, то вопрос каково оно. grizzly можете хотя бы словами его сформулировать? Какие пути лисы должны стать равными? Или где должна находиться утка после смены лисой стороны квадрата? Или лиса после старта обязательно (всегда, без всяких условий) добегает до угла и меняет сторону и лишь после этого может вернуться к отслеживанию координат утки если та внутри области принятия решения? Или даже не до угла, а до координаты $y$ утки и лишь потом если утка внутри области то начинает отслеживать её координату, если снаружи - то продолжает бежать (в ту же сторону, условие разворота очевидно не выполняется)? В последнем случае кажется вся кривая становится верной ...

[grizzly]

Dmitriy40 в сообщении #1289688 писал(а):

В последнем случае кажется вся кривая становится верной ...

В грубом приближении для рассматриваемой стратегии это совпадает с моим пониманием. Я говорю о грубом приближении, потому что утке выгоднее плыть не вдоль осей, а под наклоном. Чтобы понять это, нужно или посмотреть сообщения worm2 выше в теме или просто посмотреть во сколько раз малый катет $a$ прямоугольного треугольника больше разности $c-b$ ($c$ -- гипотенуза, $b$ -- больший катет), если угол $\alpha $ (противолежащий к $a$) совсем небольшой (возьмите градусов 5, для примера).

Я не думаю, что 5.786 -- правильный ответ. Моё мнение -- мы рассматривали эту стратегию только потому, что с её помощью проще всего было опровергнуть старую парадигму. Мы ещё не рассматривали другой крайний случай -- когда на старте лиса находится в углу большого квадрата, а утка -- в центре. Стратегия лисы на старте такая: бежать к той границе квадрантов, к которой ближе утка. Интуитивно мне кажется, что эта стратегия лучше. Решать аналитически мне лень, но можем сыграть При движении утки по диагонали лиса какое-то время будет выжидать, затем бросится в любую сторону. Про точный момент я ещё не думал и про условие возврата в родной угол -- тоже. В любом случае стратегию нужно проверить, поскольку интуиция нас всех в этой теме уже подводила (кроме worm2, кажется).

[EUgeneUS]

grizzly в сообщении #1289739 писал(а):

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

worm2 в сообщении #1289443 писал(а):

Ну и в чём я мало уверен — так это в глобальной оптимальности середины стороны как стартовой точки для Лисы. Может оказаться, что где-то в другой точке она может достичь большего (но не в угле).

ИМХО:
Стратегия утки.
1. Плыть к берегу под углом, определяемым соотношением скоростей.
2. Если лиса бежит по короткой дуге, то плыть под этим углом к другому берегу.

Стратегия лисы:
1. Лиса может "дергаться", выбирая короткую дугу.
2. При этом фактически утка будет плыть по прямой к точке делящей периметр пополам (вместе с точкой, где находится лиса), а лиса оставаться на месте.
3. В какой-то момент времени лисе уже выгоднее бежать по длинной дуге. Определение этого момента и есть основной вопрос философии стратегии лисы.

Эти стратегии работают, когда утка находится в области, где в стратегии утки есть обе траектории к берегу.

[grizzly]

EUgeneUS в сообщении #1289753 писал(а):

...
Эти стратегии работают, когда утка находится в области, где в стратегии утки есть обе траектории к берегу.

Это как-то может помочь найти $k$?

Я могу предложить более простую ситуацию, чем крайний случай в углу. Пусть начальные условия, как на прошлых страницах: утка в центре, лиса на южном полюсе. Стратегия лисы: пока утка не вышла за маленький квадрат (воспользуюсь для простоты тем квадратом), лиса добивается, чтобы её удаление от южного полюса было ровно $|x|+|y|$, где $(x,y)$ -- текущие координаты утки. Как только утка покинула квадрат, лиса бежит к ближайшей к утке точке берега. Я надеюсь так получить 5.5, которые обещал Geen, а то и меньше.

[Dmitriy40]

Картинка красной кривой выше нифига неправильная: условие одинакового $k$ для путей на север и на запад релевантно лишь для оси $OY$ и даёт правильное $k$ в единственной точке.
Правильным условием будет равенство пути лисы против часовой стрелки из координат $(x;-1)$ в координаты $(-1;y)$ (западная точка встречи) пути утки туда же из координат утки $(x;y)$. Этому условию отвечает пара прямых $y=|x|(1-k)+6-k$, пересекающая ось $OX$ в точке $(\pm0{,}04455326;0)$ и диагональ квадрата в точке $(\pm0{,}0387516536;0{,}0387516536)$.
Картинка (область от центра до синих кривых):

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

grizzly в сообщении #1289739 писал(а):

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

Самое забавное что добавление наклона вообще никак не меняет красную кривую! Т.к. уравнение остаётся ровно тем же. Откуда получилось $k \approx 5{,}786$ я перестал понимать.

[grizzly]

Dmitriy40
Я, наверное, не очень честно участвую в этом обсуждении -- я пока думаю только на качественном уровне и не имею мотивации что-то считать, пока на качественном уровне, очевидно, нет решения. Сейчас я уверен, что стратегия в конце моего предыдущего сообщения даст намного лучшее решение (и она ещё явно не оптимальна). Зачем углубляться в расчёты проигрышных стратегий? (Нет, я не возражаю, просто объясняю, почему сам отлыниваю :)

[Dmitriy40]

В принципе, лисе можно смещаться в сторону аж на $kx$ при малом смещении утки $(x;y)$ внутри фигуры принятия решения - она точно успеет вернуться точно "под утку" (в координату $x$ утки). Это больше чем $|x|+|y|$. Т.е. можно построить фигуру исходя из такого смещения лисы вправо ... Прямые ещё прижмутся к оси. Вот картинка (более светлые синие прямые), уравнение $y=6-k(2|x|+1)$:

Вероятно это максимально допустимое смещение для лисы пока утка внутри фигуры. Если убежит ещё дальше у утки появится шанс вернуться на ось $OY$ раньше лисы - т.е. бонус. Бонус бонусом, но вот реализовать его утка не сможет. Выходит лиса может смещаться и дальше ...

[wrest]

grizzly в сообщении #1289792 писал(а):

Как только утка покинула квадрат, лиса бежит к ближайшей к утке точке берега.

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