Опыт по сапёру

Два способа применения МГА схемы к решению задачи открытия поля в сапёре
(игра поставляемая в комплекте с большинством операционных систем)

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

Итак что же дано, если ничего не известно?

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

На первоначальном этапе поиска решения планируется определить какие действия приводят к изменению сенсорной картины. Для этого вполне можно использовать ГА. Допустим этот этап пройден и обнаружено, что над клетками можно совершать 3 действия: открыть, поставить мину, двойной щелчок (открыть прилегающие клетки в случае достаточного числа мин вокруг). Обнаружить последнее действие не так то просто (я через пол года обнаружил), однако решить задачу можно и без него. Помимо поиска действий, приводящих к изменению на экране, можно также выделить минимальный изменяемый участок сенсорной картины (клетку), и определить все свойственные этому участку состояния. Напомню, что в сапёре довольно ограниченное количество этих состояний, 11 штук: 9 цифр, закрытое поле, мина. Отмечу, что этот этап не требует даже понимания того, что изображено в клетке мина или цифра (и если цифра, то какая).

Итак все необходимые компоненты для запуска ГА, нацеленного непосредственно на поиск решения, есть. Вполне логично, раз уж мы моделируем работу ЦНС, искать решение в виде стимул — реакция. Стимулом является в данном случае изменение сенсорной картины, или состояния одной или определённого числа клеток. Реакцией можно считать одно из 3-х указанных ранее действий. Если точнее, то действие, которое нужно совершить над клеткой, зависит от текущего состояния клеток на поле, а точнее окружающих её клеток, но это обстоятельство можно обнаружить уже в процессе работы ГА. Задачу можно разделить на две части: поиск шаблонов, то есть совокупности клеток на поле, от которых зависит текущее состояние клетки. Поиск значений клеток шаблона, при которых над данной клеткой можно совершать действие не опасаясь закончить игру. Для того чтобы выполнить действие при появлении нужного шаблона в сенсорной картине можно использовать упрощённый нейрон. Его входными сигналами будет состояние клеток шаблона, а выходным сигналом будет действие, направленное на изменение состояния соответствующей клетки. В случае появления соответствующего сигнала, нейрон будет возбуждаться и пускать сигнал по аксону, в результате чего действие будет автоматически выполняться. Среди популяций такого рода нейронов и будет вести отбор ГА. Конечные результаты этого отбора можно предугадать исходя из знания эвристического решения. Например:

А в более общем случае:

Где * - это не открытое поле.

Показаны шаблоны для постановки мины в нижнем левом не открытом углу.

Для шаблона:

можно смело открывать все не открытые поля.

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

Каковы же особенности подобного подхода к поиску решений?

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

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

Можно также попытаться подобрать двухслойную нейронную схему, где второй слой будет реализовывать работу ГА по отбору полезных нейронов первого уровня, принцип действия которых описан ранее. Я не знаю насколько широко применяются нейронные сети для решения подобного рода формализованных задач, однако решение нейронной сетью такой задачи, при отсутствии начальных представлений о ней будет важным прецедентом их применения. Важно упомянуть следующее свойство уже отлаженной нейронной сети первого нейронного слоя. Количество тактов её работы, требуемое для полного открытия поля в сапере, логарифмически зависит от числа клеток на поле. Для систем с линейной архитектурой, нужно число тактов порядка квадрата числа клеток.

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

Полезно использовать уже открытое поле для того, чтобы существенно ускорить процесс поиска решения. Ведь в открытом поле присутствует большое число полезных шаблонов. Даже если брать из открытого поля  шаблоны с произвольным расположением клеток в качестве начальной популяции для ГА, то это сильно повысит скорость его сходимости. Таким образом, можно говорить об успешности для МГА «обучения по прецедентам», то есть по примерам правильных решений, что также свойственно естественному интеллекту.

Теперь представим второй вариант решения сапёра. В этом случае будет использоваться ГА с условием, а в качестве условия будут использоваться правила игры.  Это подразумевает, что все возможные действия и состояния клетки, как и само понятие клетки, известны заранее. Само условие - количество мин вокруг каждой открытой клетки соответствует цифре в ней указанной.

ГА с условием будет работать следующим образом. Для каждой клетки есть три варианта действий. Если действие противоречит правилам игры, то оно автоматом отбрасывается. Для тех клеток где остаётся одно действие оно автоматически выполняется, а в остальных ничего не делается. Теперь нужно выяснить, каким образом будет проверяться выполнение правил игры. Просто будет проводится мысленный эксперимент, то есть будет «виртуально» выполнятся одно из действий и для всех соседних клеток проверяться условие выполнения правил игры. Таким образом, ГА с условием сразу работает, как вполне эффективный алгоритм, который сможет часть полей открыть полностью.

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

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

Для рассмотренного примера применения ГА с условием применяется необычный приём для проверки наличия противоречия с правилами игры, являющийся упрощённым вариантом мысленного эксперимента. Предполагается что действие совершено, и проверяется к каким последствиям это приводит, в данном конкретном случае проверяется соответствие правилам. Исходя из опыта самонаблюдения, могу сказать, что подобного рода мысленные эксперименты являются неизменным свойством естественного интеллекта. А в математике есть отдельные термины, применяемые к такого рода мысленным экспериментам: приведение к противоречию, или доказательство от противного.  И ещё пример на эту тему:

Известный немецкий алгебраист Эрнст Эдуард Куммер (1810–1893) очень плохо умел считать в уме. Если при чтении лекции ему надо было выполнить простенький расчет, он обычно прибегал к помощи студентов.

Однажды ему надо было умножить 7 на 9. Он начал вслух рассуждать:

— Гм... это не может быть 61, потому что 61 — простое число. Это не может быть и 65, потому что 65 делится на 5. 67 — тоже простое число, а 69 — явно слишком много. Остается только 63...

(Цит. по книге: Kutzler B. B. Mathematikerwitze & Mathematikwitze. 2006; перевод Ю. Фролова.)

Приём «мысленного эксперимента», применяемый для сапёра в данном случае, можно усовершенствовать. Для этого после предположительного действия, нужно открыть   несколько окрестных клеток (всё это «в уме») и проверить, не возникнет-ли противоречия после этого в клетках, расположенных рядом с модифицированными во время мысленного эксперимента. Такой подход является элементом реально применяемой сознательной (моей например) тактики открытия сапёра.

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

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

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