RNAFoldingAI/Реконструкция прошлого

Шаблон:TOC-Right

**Более точное название:***Реконструкция неизвестных состояний*.

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



При попытке реконструкции прошлого мы столкнемся с быстро увеличивающимся числом вариантов (траекторий), отвечающих нынешнему состоянию системы. Только один из них соответствует реальному течению событий. Если выбрать не его, а какой-то другой, то получится уже искаженная "версия" истории. На основании чего выбирается правильная траектория ("версия")? Информация, на которую мы можем опереться, - совокупность имеющихся конкретных фактов. Траектории, несовместимые с ними, отбрасываются. В результате при наличии достаточного количества надежных фактов останется одна траектория, определяющая единственную версию истории. Однако даже для недалекого прошлого траекторий может оказаться значительно больше, чем достоверных сведений, - тогда однозначная трактовка исторического процесса уже не может быть произведена.

[1]

## Планирование как реконструкция прошлого

Когда мы говорим о прогнозировании, то как правило имеем введу прогнозирование некой статистической (непрерывной) величины. Например, курса акций, доходов или расходов предприятия, кредитоспособность заёмщиков, длительность заболеваний, спрос на товары и т.п.

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

Когда же мы говорим о *прогнозировании событий в будущем* - речь идет о планировании. А вот понятия планирования в прошлом не бывает - это называется *реконструкцией прошлого*.

Поэтому **планирование** и **реконструкция прошлого** - это две близкие задачи отличающиеся только направленностью во времени. Кроме того, как будет показано ниже, время в ряде задач вообще может не иметь значения. И тогда в общем случае стоит вести разговор о восстановлении (реконструкции) состояний неизвестных элементов. Эти элементы - могут быть как активными субъектами (агентами), так и пассивными (объектами управления).

## РНК-тюнинг в сравнении с методом „Альфа-бета отсечения“

Как происходит поиск желаемого состояния в „Альфа-бета отсечении“ ? Здесь анализируется состояния, которые будут в будущем, скажем через **K** тактов времени (ходов). А затем производят реконструкцию прошлого, то есть от желаемого состояния возвращаются в настоящее. Таким образом, направление времени теряет абсолютность, весь вопрос в том какую выбрать точку отсчета. Эту точку отсчета назовем глубиной (уровнем) просмотра - **L**.

Но в „Альфа-бета отсечении“ анализируются практически все возможные состояния уровня **L**, за исключением тех ветвей, которые уже очевидно анализировать не нужно. При этом уровень **L-1** содержит в поддереве все варианты действий одного из элементов. Например, в игре в шахматы имеются 16 фигур, каждую из которых будем для общности называть элементом **E**.

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

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

И вот именно из такой логики и работает метод РНК-тюнинг. Определяется цель - два элемента **E1** и **E2** (в данном случае - нуклеотида) должны быть в определенном взаимном состоянии (образовать водородную связь). При этом успешность приближения к этому, оценивается близостью расстояния и малым углом между этими элементами. Таким образом, каждое состояние можно отнести к одной из **N** групп, нахождение в которых указывает близость (или отдаленность) к целевому состоянию.

За ход могут меняться расположение любых элементов, но даже если элементы **E1** и **E2** не двигались, движение других элементов способствует или отдаляет от их целевого положения. Так например, примем **N = 6**. Тогда при активном перемещении элементов **E1** и **E2** в самом лучшем случае,например, можно получить только варианты из группы №3 (а нужен вариант из группы №1). Поэтому очевидно, что нужно так же передвигать другие элементы. Но какие ?

Чтобы ответить на этот вопрос, нужно сделать ряд проверок. Чтобы отсечь те варианты которые мало пригодны, стоит начать с активных действий элементов **E1** и **E2**, например, как говорилось выше мы получили скажем 100 вариантов из группы №3. Все прочие варианты можно отсечь, и исходя из этих 100 вариантов, наугад попробовать переместить другую фигуру. Если перемещения получает варианты из группы №2 или выше, то действия таких элементов и нужно выбрать. В худшем случае они не должны уменьшать варианты из группы №3. Таким образом, шаг за шагом будут выполняться те действия которые приводят к цели, или увеличивают число вариантов (путей) ведущих к цели.

### Демонстрация отличий на игре крестики-нолики



Чтобы продемонстрировать отличия данных подходов, сыграем в игру крестики-нолики. Для простоты начнем из состояния изображенного на рисунке. Существует 8 вариантов позиций крестиков дающих выигрыш (занять одну из вертикалей (3), одну из горизонталей (3), одну из диагоналей (2) ). Введем 3 группы. В группу 3 попадают все варианты, где один крестик и 2 пустых позиции на пути к выигрышу. В группу 2 попадают все варианты, где 2 крестика рядом и 1 пустая позиция нужная для выигрыша. И в 1-ую группу попадают 3 крестика расположенные давая выигрыш, учитывая число образуемых вариантов.

Из имеющегося положения надо проанализировать 5 положений и решить куда поставить крестик. Ставя крестик в позицию 1 (позиции отсчитываем слева-направо, сверху-вниз) вы попадаем в состояние из группы 2: 2 крестика и пустая клетка. Аналогично в позициях 3, 7 и 9. А в позиции 6 попадаем в группу 3: 1 крестики и две пустые клетки. Таким образом, в группе 2 имеем 4 варианта.

Теперь проанализируем эти 4 варианта на следующем шаге. Из позиций 1 и 3 получаем по 2 варианта выигрыша, а из 7 и 9 по одному. Поэтому в группу один попадают позиции 1 и 3.

Заметим, что в таком подходе мы избавились от достаточно большого перебора. И главное, данный алгоритм легко распараллелить, в отличии от альфа-бета.

## Ссылки

- Компьютерное моделирование в истории
- Алгоритмы шахматных программ
- Развитие искусственного интеллекта в шахматных программах