Работа №1

Задание: Построение графа

Работа является вводной. Её главная цель – освежить в памяти навыки построения деревьев и графов и работы с ними, поскольку две следующие работы в той или иной степени потребуют этих навыков в увеличенном объёме. Общие принципы построения и вывода на экран графов изучались вами в третьем семестре в курсе «Структуры и алгоритмы обработки данных на ЭВМ» и должны быть вам знакомы. С тех пор принципиально ничего не изменилось.

Работа №2

Задание: решение головоломки «Восьмёрки» с использованием поиска в пространстве состояний

Всем, конечно же, известна такая древняя интеллектуальная игра, как «Пятнашки». «Восьмёрки» - это аналог пятнашек, выполненный на поле размером не 4х4, а на поле размером 3х3. В рамках данной работы предлагается реализовать возможность решения «восьмёрок» с помощью простейшего и не слишком интеллектуального подхода – с помощью поиска решения в дереве пространства состояний.

Выполнение работы можно условно поделить на 3 этапа:

1. Построение полного дерева пространства состояний для «восьмёрок».

2. Нахождение текущей комбинации игрового поля в пространстве состояний с помощью поиска «в ширину» или поиска «в глубину».

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

Рассмотрим каждый из этапов немного подробнее.

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

В отличие от предыдущей работы, в данной конкретной задаче число потомков каждого узла будет максимум 4, как, например, при построении их из исходной комбинации. Каждый потомок некоторой вершины будет содержать возможные состояния игрового поля, в которые можно попасть, сделав ход из текущей вершины. Перед добавлением некоторого потомка в дерево пространства состояний необходимо убедиться, что там его ещё нет. В противном случае, дерево рискует получиться бесконечно большим. Из целевой комбинации можно сделать 4 различных хода: сдвинуть «8» вправо, «4» влево, «2» вниз или «6» вверх. Отобразив это в виде дерева, получим следующую картину:

Каждая из листовых вершин представленного дерева содержит состояние игрового поля, из которого можно сделать 3 различных хода, один из которых уже есть в представленном дереве: это корень дерева. По этой причине, каждый из представленных листовых узлов будет иметь не 3, а только 2 потомка. Продолжая построение дерева подобным образом, можно в итоге прийти к ситуации, когда ни из одной листовой вершины нет возможности сделать ход, который ещё не делали. При достижении подобной ситуации следует прийти к выводу, что дерево решений (пространство состояний игры «восьмёрки») построено, и его можно использовать.

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

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

В процессе выполнения работы возможно появление следующих проблем:

1. Построение дерева пространства состояний вызывает нехватку памяти. Если это произошло – введите в программу возможность строить не полное дерево, а дерево до какого-то конкретного уровня. Практика показывается, что, построив дерево хотя бы до уровня 8 или 9, вы легко сможете отладить весь остальной код.

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

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

Задание: реализация интеллектуального противника в игре «крестики-нолики» с использованием поиска в пространстве состояний

Задание аналогично предыдущему, с разницей лишь в том, что программа предназначена не просто для сбора головоломки, а для игры с человеком, который по своей природе враждебен. Для того чтобы компьютер мог ходить и наносить урон противнику , его действия должны быть на чём-то основаны. В данной работе основанием предлагается сделать дерево решений игры «крестики-нолики». Для простоты можно условиться, что первым всегда ходит человек. Таким образом, дерево решений программы следует начинать строить с того состояния игрового поля, в котором оно окажется после первого хода человека.

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

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

Время на выполнение работы – 3 занятия.

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

Задача состоит в том, чтобы собрать головоломку из некоторого произвольного состояния в целевое, указанное выше.

Смысл работы сводится к тому, чтобы из возможных вариантов каждого следующего хода выбрать наилучший. Сделать это нам (имеется в виду вам) поможет эвристическая функция следующего вида: f(n) = g(n) + h(n). В этой функции g(n) — фактическая длина пути от произвольного состояния n к начальному (то есть число ходов, которые необходимо сделать для того, чтобы прийти из начального состояния в состояние n), а h(n) — эвристическая оценка расстояния от состояния n к цели.

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

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

Из рисунка видно, что состояние a является начальным, а состояние m — конечным (целевым). Для удобства, каждому состоянию соответствует буква, а рядом с каждым состоянием написано посчитанное значение функции f, соответствующее текущему состоянию. Напротив каждого уровня дерева написано значение функции g(n), где n — номер хода, а следовательно и номер уровня дерева. Чем больше уровень, тем больше значение функции g(n). Обратите внимание, что при подсчёте значения функции h(n) считается только количество фишек не на своих местах. Пустое поле фишкой не считается! Например, для состояния i не на своих местах находятся фишки 1, 2, 7 и 8, поэтому значение функции h(i) будет равно 4, значение функции g(i) равно 3, а значение функции f(i) равно h(i) + g(i) = 4 + 3 = 7.

Жадный алгоритм предоставляет возможность отказаться от использования так нелюбимых студентами графов и вместо них использовать 2 списка, которые при использовании жадного алгоритма по традиции называют open и closed. Список open содержит те состояния игрового поля, которые предстоит рассмотреть для нахождения целевого решения, а список closed содержит уже рассмотренные состояния.

Изначально список open содержит лишь состояние «a», а список closed пуст. Для удобства и лучшего понимания того, что происходит, рядом с именем состояния будем писать значение оценочной функции для этого состояния. Элементы списка open должны быть упорядочены по возрастанию в соответствии со значением оценочной функции.

Итак, изначально у нас следующая картина:

open = [a4]; closed = [ ]

Состояние a в списке open не является целевым, поэтому извлекаем его из списка, меняем на те состояния, которые получаются из «a», а само состояние «a» помещаем в список уже рассмотренных состояний closed. Из состояния «a» можно получить 3 новых состояния: «b», «c» и «d». После проделанных действий содержимое списков open и closed будет следующим:

open = [c4, b6, d6]; closed = [a4]

Состояние «c» имеет наименьшее значение оценочной функции, не является целевым, значит, выигрышное состояние надо искать от него. Перемещаем его из списка open в список closed, а в список open добавляем те состояния, которые получаются из состояния «c», получаем следующие значения в списках open и closed:

open = [e5, f5, b6, d6, g6]; closed = [a4, c4]

Действуя аналогичным образом дальше, последовательно получаем следующие состояния списков open и closed:

open = [e5, f5, b6, d6, g6]; closed = [a4, c4]

open = [f5, h6, b6, d6, g6, i7]; closed = [a4, c4, e5]

open = [j5, h6, b6, d6, g6, k7, i7]; closed = [a4, c4, e5, f5]

open = [l5, h6, b6, d6, g6, k7, i7]; closed = [a4, c4, e5, f5, j5]

open = [m5, h6, b6, d6, g6, n7, k7, i7]; closed = [a4, c4, e5, f5, j5, l5]

После достижения последнего из приведённых состояний видно, что состояние «m» — целевое, а значит, задача решена. Решением будет путь, находящийся в списке closed. Обратите внимание, что использовать его просто в том виде в каком он есть не представляется возможным, поскольку нет возможности за один ход попасть, например, из комбинации «e» в комбинацию «f». Однако в комбинацию «f» можно попасть из комбинации «с», вернуться в которую из «е» можно, сделав один ход назад по списку closed.

Ваша задача — распространить этот метод (при желании) на поле размером 4 x 4 и в процессе работы со списками отображать перемещения фишек на экране для максимальной наглядности.

Задание: реализация интеллектуального противника в любой игре для двух участников с использованием процедуры минимакса

О том, что такое минимакс – всем должно быть известно из курса лекций. В качестве альтернативы к предыдущему варианту третьей лабораторной работы предлагается использовать процедуру минимакса для реализации противника в любой интеллектуальной игре на двух или более человек (например, в игре «крестики-нолики»).

Время на выполнение работы – 3 занятия.

Работа №4:

Задание: распознавание формата файла по содержимому с помощью простейшей искусственной нейронной сети

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

В рамках работы предлагается построить нейронную сеть, состоящую из одного нейрона и обучить её решать какую-либо простейшую задачу. В качестве такой задачи предлагается определение типа файла по его содержимому. Таким образом, перед началом работы, вам необходимо выбрать для себя один тип файла, который вы хотите распознать, заготовить чем больше тем лучше различных файлов выбранного типа и файлов типа, отличного от выбранного (например, если вы хотите распознавать, является файл файлом в формате «pdf» или нет, вам потребуется около 40 файлов в формате «pdf» и около 40 файлов не в формате «pdf»).

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

В рамках работы требуется создать один нейрон с 256 входами и обучить его.

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