Ограничение оптимизирующих методов в играх с противником и без

    Эта статья короткое ответвление от цикла статьей по биовычислениям:
    От белков к РНК, Мат. критерии, Как уменьшить число поворотов цепи?, Как оценить ход сворачивания односпиральной РНК?

    В этих статьях задача сворачивания РНК представлена в новом свете — как задача теории игр. Но традиционно эта задача сейчас решается с применением различных стохастических оптимизирующих методов. А к ним относятся методы основанные на методе Монте-Карло, метод отжига, генетические алгоритмы, искусственные нейронные сети, Q-обучение, и все те которые представляют задачу как энергетическую поверхность в которой ищут экстремумы.

    Казалось бы сама физика велит использовать эти методы в таких задачах как сворачивание РНК/белков. Здесь мы посмотрим почему это сильно проблемно.



    Основная идея очень проста на самом деле. Давайте возьмем простейшую из игр с противником крестики-нолики, и построим энергетическую поверхность и её изменения при ходах игроков. На рисунке отображена в первом ряду энергетическая поверхность в начале игры, во втором ряду после хода крестиков в позицию 2 (позиции от 1 до 9, перечисляя слева на право, снизу вверх).



    Рисунок справа показывает 3-х мерную дискретную поверхность, которая образуется. По оси Y – отображается энергетическая оценка по методу Мини-Макс, по оси Z – позиция хода текущего игрока, а по оси X – позиция хода противника. Каждая точка на поверхности показывает, какие шансы у игрока противника в зависимости от сделанного хода игрока. Проекции этой поверхности – на рисунке по центру вид сбоку, а слева вид сверху.

    Мы видим, что ход в позицию 5 увеличивает шансы игрока (см. вид сбоку). Ход же в другие позиции не дает видимых преимуществ – площадь на виде сверху заполнена почти равномерно. Если же игрок поставит крестик в позицию 2, то энергетическая поверхность существенно изменится. Тогда, если нолик займет позицию 5, то наиболее опасная позиция для крестиков становится 8. Из вида сверху понятно, что если не будет разыгрываться центральная позиция 5, то шансы игроков уже не столь равномерны, как в начале игры. Так установка в позицию 1, 3, 5, 7 расширяет возможности ноликов, а 4 сильно снижает.


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

    Мне остается только спросить: что будут искать оптимизирующие алгоритмы, когда каждый новый ход так изменяет энергетическую поверхность, что она становится практически неповторяемой? Будет ли хоть малейшая оптимизация по сравнению с полным перебором?
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

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

      +2
      Краткость — сестра.
        0
        Оценочная функция — это число, а не поверхность. И в практических играх это число меняется довольно медленно. В случае же быстрых изменений в шахматах используют увеличение глубины просчета в этих направлениях (просчет форсированных вариантов). То, что каждый ход наилучшие ходы становятся другими, никакой проблемы не представляет.
          0
          Как это функция — число?
          0
          Вы привели пример игры где есть противник. А «кто» играет роль противника в ваших задачах (биовычисления)?
            0
            Из моей статьи

            Эта задача может быть определена как игра с природой — игра, в которой имеется только один игрок, причём исход ее зависит не только от его решений, но и от состояния “природы”, то есть не от сознательно противодействующего противника, но от объективной, невраждебной действительности.

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

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