Головоломка Арнольда: от комбинаторной геометрии к браузерной игрушке

    Представьте игру, в которой выполняются простые правила:

    1. На плоскости проведены несколько линий, каждая пара линий пересекается в одной точке.

    2. Линии разбивают плоскость на области, раскрашенные в шахматном порядке.

    3. Вы можете перестраивать разбиение, «схлопывая» и «выворачивая» треугольники.

    4. Ваша цель – получить максимально возможное количество темных областей.

    Я уже запрограммировал браузерную игрушку по этим правилам. В простейшем случае 5 линий процесс игры выглядит так:

    Пример прохождения уровня из 5 линий
    Пример прохождения уровня из 5 линий

    Пользовательский опыт

    При небольшом количестве линий решить головоломку можно случайным перебором. Нужно помнить, что иногда надо «пожертвовать» счетом (количеством темных областей), так как не всегда есть «прямая дорога» к цели, на которой счет только увеличивается.

    Я довольно быстро «прошел» все уровни до 19 линий. 21 линию (на скриншоте в начале) собрал часа за полтора. Правда, я знал, что существует вращательно-симметричная конфигурация (поворот на 120° переводит ее в себя), и специально делал ее симметричной. 23 линии пытался собрать дважды, и оба раза не получилось набрать последнее очко.

    С увеличением уровня сложность игры растет не только количественно (нужно дольше идти к цели), но и качественно: приходится придумывать новые приемы и подходы, так как старых становится недостаточно.

    По ощущениям игра похожа на паззл, каждый кусочек которого подходит к любому другому кусочку, но общая картина из них всё никак не складывается.

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

    Математическая основа

    Эта головоломка навеяна одной из задач из сборника «Задачи Арнольда» (В. И. Арнольд, № 1983-4, изд. Фазис, 2000):

    На плоскости проведены N прямых. Найти максимальную разность между числом черных и белых областей шахматной раскраски дополнения.

    Это открытая математическая проблема. Она является частным случаем 16-й проблемы Гильберта для многочленов специального вида – произведения линейных сомножителей ax+by+c.

    Таким образом, переворачивая треугольники в игрушке, вы на самом деле решаете в частном случае задачу Арнольда! :)

    Для преобразования конфигураций в головоломке именно схлопывание треугольников выбрано не случайно. Оказывается, с помощью таких схлопываний можно перевести произвольную конфигурацию в любую другую конфигурацию. Действительно, линии на плоскости, описанные в правилах, называются конфигурацией (псевдо)прямых. Они представляют элемент из группы кос. Суть теоремы Артина об образующих группы кос как раз и состоит в возможности перевода конфигураций друг в друга последовательностью преобразований треугольников.

    Также задача Арнольда тесно связана с задачей о треугольниках Кобона.

    Как я написал выше, задача Арнольда для произвольного количества прямых не решена. Вместе со мной Денис Уткин и Сергей Белёв потратили немало времени на попытки решения. Результаты нашего исследования – в многостраничном pdf-отчете. Я хочу выразить благодарность Денису и Сергею за совместный интерес, без которого в конечном итоге не появилась бы эта головоломка. Бонус для внимательных читателей: в отчете есть примеры конфигураций, на которых достигается цель головоломки.

    Вычислительная модель игры

    В основе визуализации – математическое моделирование некоторой «механической» системы. В этой системе массивные точки соединены ломаными линиями, отталкиваются друг от друга, испытывают сопротивление среды. В узлах ломаных – распрямляющие «пружинки». Концы ломаных прибиты внешними зафиксированными точками. Для расчетов движения точек по законам механики применяется метод Рунге – Кутты четвертого порядка с оценкой ошибок и плавающим шагом. Преподаватели вычматов были бы довольны :) Код, как обычно, открыт на гитхабе.

    На этом пока всё. Могу подробнее рассказать о процессе разработки игрушки и о нашем исследовании задачи Арнольда, включая десятки тысяч часов процессорного времени, потраченного на поиск оптимальных конфигураций оптимизированным перебором. Пишите в комментариях, интересны ли эти вопросы.

    Средняя зарплата в IT

    110 000 ₽/мес.
    Средняя зарплата по всем IT-специализациям на основании 8 763 анкет, за 2-ое пол. 2020 года Узнать свою зарплату
    Реклама
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее

    Комментарии 14

      +4
      Вот за что я люблю веб-разработку — можно сделать приложение и легко поделиться им с окружающими. А окружающим, в свою очередь легко запустить и поработать с приложением.
        +7
        Полистал я книжку Арнольда… Вот я вроде физико-технический факультет закончил и матподготовка была хорошая у меня, но блин…

        У него ещё в 2004 вышла книжка «Задачи для детей от 5 до 15 лет» — надо с неё начать, что ли.
          +4

          У нас были похожие ощущения, когда мы студентами листали эту книжку. И когда наткнулись на задачу с понятным условием, решили попробовать свои силы :)

            +1
            Ну это же не учебные задачи, а исследовательские, для настоящей научной работы в чистой математике. Каждая — как минимум тема дипломной работы (это как минимум), то есть требует основательного погружения и работы, при имеющемся общем математическом образовании.
            +1
            Очень интересная головоломка получилась. Браво. Цвета правда путают, странно как-то меняются. И интересно почему нету четного количества линий.
              +2

              Спасибо.


              Цвета помогают понять, где в текущей конфигурации потенциальные места для улучшения.
              Если подумать, как максимизировать количество темных областей, становится понятно, что темные области должны быть треугольниками. Поэтому я закрасил темные не-треугольники синим цветом. Кроме того, светлых треугольников не должно существовать, так как их сразу же можно превратить в темные треугольники с повышением счета. Светлые треугольники могут существовать только в середине какой-то многоходовой комбинации. Чтобы такие комбинации проще было делать, я подсвечиваю светлые треугольники желтым.

                +1

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


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


                Примерно то же можно сказать в терминах проективной плоскости. Если рассматривать задачу на проективной плоскости, то к конфигурации с нечетным количеством линий надо добавить бесконечно удаленную прямую, чтобы шахматная раскраска была согласованной. В четном случае ничего добавлять не надо. И тогда становится понятно, что четный и нечетный случаи тесно связаны между собой.


                С учетом этой связи я запрограммировал более простой случай.

                +1
                Исправить бы опечатку
                центрально-симметричная конфигурация (поворот на 120° переводит ее в себя)
                  0

                  Спасибо, исправил. Конечно, речь о вращательной симметрии C3, а не о центральной симметрии.

                  +1
                  Охрененно!
                  Только вопрос, а медленное движение линий в разные стороны когда не взаимодействуешь с ними это баг или фича?
                    0

                    Особенность способа реализации, скажем так. Специально не задумывал. Моделируемая механическая система переходит к состоянию равновесия, и из-за отталкивания точек в узлах ломаных может расширяться.

                    0
                    Очень интересно. Но простите немного брюзжания: оно вот вообще никак не может функционировать без установки кук? Или это просто уже модно.
                      0

                      А где вы увидели установку кук?


                      Приложение сохраняет конфигурацию на каждом уровне в LocalStorage по понятным причинам. Я даже об этом упоминать не стал: сегодня это само собой разумеется. Сравните, например, с оригинальной браузерной версией 2048, там сделано так же.

                        0
                        1. На самом деле не совсем понятным. Зачем их сохранять если страница не перезагружается, да и никакого прогресса, как я понял, там нет. Кстати у меня LS, вроде, был запрещен. Хотя в новой фоксе настроек доступа к нему не нашел, так что возможно всё уже не так, как на самом деле :/
                        2. Собственно на счёт именно кук не уверен. В новой фоксе привычного плагина нет. Тут вопрос к тому, как uMatrix это отрабатывает. Если в нём запретить куки (приравнивает ли он LS к печенькам?) — сайт отрубается полностью, как будто отключены скрипты. Что вообще никак не очевидно. И в любом случае по логике он должен прекрасно работать и без них. Ну не сохранил прогресс, это уже проблемы юзера.

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

                    Самое читаемое