• Оптимальная игра в 2048 с помощью марковского процесса принятия решений

    • Перевод

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

    В этом посте мы используем математический аппарат под названием «марковский процесс принятия решений» для нахождения доказуемо оптимальных стратегий игры 2048 для полей размером 2x2 и 3x3, а также на доске 4x4 вплоть до тайла 64. Например, вот оптимальный игрок в игру 2x2 до тайла 32:

    GIF

    Случайное начальное число (random seed) определяет случайную последовательность тайлов, добавляемых игрой на поле. «Стратегия» игрока задаётся таблицей, называемой алгоритмом (policy). Она сообщает нам, в каком направлении нужно сдвигать тайлы в любой возможной конфигурации поля. В этом посте мы рассмотрим способ создания алгоритма, оптимального в том смысле, что он максимизирует шансы игрока на получение тайла 32.

    Оказывается, что в игре 2x2 до тайла 32 очень сложно выиграть — даже если играть оптимально, игрок выигрывает только примерно в 8% случаев, то есть игра оказывается не особо интересной. Качественно игры 2x2 сильно отличаются от игр 4x4, но они всё равно полезны для знакомства с основными принципами.

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

    Однако мы можем найти оптимальный алгоритм для укороченной игры 4x4 до тайла 64, и, к счастью, мы увидим, что оптимальная игра на полях 3x3 качественно выглядит похожей на некоторые успешные стратегии полной игры.

    Код (исследовательского качества), на котором основана эта статья, выложен в открытый доступ.
    Читать дальше →
    • +30
    • 9,6k
    • 6
  • Квантовая телепортация на языке Q#

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

    Это вторая статья из серии о квантовом программировании. Предполагается, что читатель уже знаком с первой частью.

    Читать дальше →
  • Обзор материалов по машинному обучению № 3 (16 — 23 апреля 2018 года)

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

      image
      Читать дальше →
    • Измерение уровня жидкости в топливном баке ракеты



        Введение


        Топливо из резервуара окислителя и резервуара горючего поступает в камеру сгорания ракетного двигателя. Синхронная подача топлива в заданной пропорции обеспечивает эффективную работу ракетного двигателя.

        Эффективная работа зависит от точного измерения уровня топлива в баке. Для этой цели топливный бак имеет систему управления топливом. Система представляет собой вертикальный измерительный канал с датчиками внутри канала для фиксации свободного уровня жидкости в канале [1]:


        Рисунок. Схема топливного бака. 1- резервуар, 2- топливо, 3- измерительный канал, Po — давление газа, — уровень жидкости в канале, H — уровень жидкости в баке, r,x — координатные оси.

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

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

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

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

        Далее рассмотрим, как можно определить методическую погрешность от первой проблемы и уменьшить погрешность измерения от второй.
        Читать дальше →
      • Самые страшные ошибки, которые допускают DS. Встреча в офисе Авито 24 апреля

          Привет! На следующей неделе, во вторник, 24 апреля, приглашаем специалистов по Data Science на митап, который мы организуем вместе с AI Community и AI Today. Будем говорить о самых страшных ошибках, которые допускают DS. Подробно обсудим CRISP-DM и Tips&Tricks, которые можно использовать в работе. Вы услышите доклады Ивана Гуза, Игоря Слинько и Станислава Гафарова. Регистрируйтесь на встречу и приглашайте коллег. Под катом — тезисы выступлений, ссылки на регистрацию и видеотрансляцию митапа.


          Читать дальше →
          • +19
          • 5,8k
          • 2
        • Пространство состояний в задачах проектирования систем оптимального управления


            Введение


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

            Состоянию системы соответствует точка в определённом евклидовом пространстве, а поведение системы во времени характеризуется траекторией, описываемой этой точкой.

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

            Целью данной публикации является рассмотрение решения задач проектирования систем оптимального управления методом описания пространства состояний с использованием программных средств Python.
            Читать дальше →
          • Ой, у вас баннер убежал!

            Ну. И что?
            Реклама
          • Новое доказательство теоремы о многочлене

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

              Пусть $f(x)$ — бесконечно много раз дифференцируемая действительная функция, причем для каждой точки $x\in R$ найдется натуральное $n$ такое, что $f^{(n)}(x)=0$. Тогда $f(x)$ многочлен.

              Доказательство


              Нам понадобится теорема Бэра о системе замкнутых множеств:

              1. Пусть $H$ и $F_{1},F_{2},...,F_{n},...$ замкнутые подмножества прямой, причем $H \neq \varnothing$ и $H\subset \bigcup \limits_{n} F_{n}$. Тогда в $H$ найдется точка, которая содержится в одном из $F_{n}$ вместе со своей окрестностью. Более точно, найдется точка $x\in H$, натуральное $n$ и $\varepsilon >0$ такие, что $(x-\varepsilon;x+\varepsilon)\cap H \subset F_{n}$.

              Действительно (от противного), выберем точку $x_{1} \in H$ и окружим ее окрестностью $\Delta_{1}=(x-\varepsilon_{1};x+\varepsilon_{1})$, где $\varepsilon_{1}<1$. Мы предположили, что утверждение теоремы Бэра не верно. Значит $\Delta_{1} \cap H \not \subset F_{1}$. Выберем в $\Delta_{1} \cap H$ точку $x_{2}\notin F_{1}$. Окружим $x_{2}$ интервалом $\Delta_{2}=(x_{2}-\varepsilon_{2};x_{2}+\varepsilon_{2})$ таким, что концы этого интервала — точки $x_{2}-\varepsilon_{2}$ и $x_{2}+\varepsilon_{2}$ лежат в $\Delta_{1}$, а $\varepsilon_{2}<\frac{1}{2}$. По предположению $\Delta_{2}\cap H\notin F_{2}$. Это позволяет выбрать в $\Delta_{2} \cap H$ некоторую точку $x_{3} \notin F_{2},...$ Продолжая процесс, мы построим вложенную стягивающуюся последовательность интервалов $\Delta_{1}\supset \Delta_{2}\supset ...$ Ясно, что

              $x_{1}-\varepsilon_{1}< x_{2}-\varepsilon_{2}<...<x_{n}-\varepsilon_{n}...$, (1)
              $x_{1}+\varepsilon_{1}>x_{2}+\varepsilon_{2}>...>x_{n}+\varepsilon_{n}...$ (2)

              Так как каждый промежуток $\Delta_{i}\cap H\neq \varnothing$, то $\lim _{i\to \infty}(x_{i}-\varepsilon_{i})=\lim_{i\to\infty} (x_{i}+\varepsilon_{i})=y, y\in H$, а из (1) и (2) следует, что $y\in \Delta_{i}$ для каждого $i$. Таким образом мы нашли точку $y \in H$, но не лежащую ни в одном из множеств
              $F_{i} \phantom{1} (i=1,2,...)$.
              Скажем, что точка на действительной прямой правильная, если в некоторой окрестности этой точки функция $f(x)$ — многочлен. Множество всех правильных точек обозначим символом $E$. Множество $E'$, дополнительное к $E$ обозначим через $F$ и назовем множеством неправильных точек. (Будем говорить, что если $x\in F$, то $x$ — неправильная точка).
              Читать дальше →
              • +15
              • 6,3k
              • 9
            • Основы квантовых вычислений: чистые и смешанные состояния

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

              Читать дальше →
              • +17
              • 6,6k
              • 9
            • Неисчислимое: в поисках конечного числа



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

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

                В XX в. стала отчетливо проступать другая проблема. С бесконечностью мы можем разобраться при помощи одного символа (∞), но что делать с числами, которые меньше бесконечности, но при этом невообразимо огромны?

                Мы вплотную подошли к числам, едва уступающим «уроборосу», но при этом все еще имеющим теоретическое и практическое значение. Вы, вероятно, могли слышать о числе Грэма, которое является верхней границей для решения определенной проблемы в теории Рамсея. Спустя 88 лет после появления теоремы Рамсея математики готовы отбросить старые методы и пойти еще дальше.

                Добро пожаловать в кроличью нору без дна.
                Читать дальше →
              • Моделирование системы управления самолётом



                  Здравствуйте!


                  В предыдущей статье [1] мы рассмотрели некоторые особенности применения библиотеки Python Control Systems Library для проектирования систем управления. Однако, в последнее время широко используется проектирование систем управления с помощью переменных состояния, что значительно упрощает расчёты.

                  Поэтому, в данной статье на примере системы управления из публикации [2] мы рассмотрим упрощённую модель автопилота с использованием переменных состояния и функций tf, ss библиотеки Control.

                  Физические основы работы автопилота и системы уравнений полёта


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

                  Рассмотрим работу автопилота, который контролирует высоту воздушного судна. Основные координатные оси и силы, действующие на самолет, показаны на рисунке, приведенном ниже.


                  Читать дальше →
                Самое читаемое