Заключение

Применение методов искусственного интеллекта в переборных алгоритмах

Подведем окончательные итоги и еще раз взглянем на проделанную работу.

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

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

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

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

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

В качестве практической составляющей данной работы можно рассматривать проведенные исследования четырех разных систем проведения чемпионатов. Как уже отмечалось выше, от правильного выбора такой системы зависит производительность предложенного метода самообучения играющих программ. В последней главе этой работы сформулированы требования к процедуре отбора игроков, представлена удобная модель чемпионата, описана программная реализация этой модели, приведены и проанализированы результаты практических исследований. Среди исследованных круговой, олимпийской, олимпийской с матчами и швейцарской систем отмечена последняя, как наиболее выгодная в условиях поставленной задачи. Основными критериями предпочтения были ресурсоемкость (количество партий в чемпионате) и точность, которая в свою очередь определялась тремя численными оценками. Эти оценки таковы: частота победы сильнейшего, полная невязка и сумма номеров мест, занятых тремя лучшими игроками. Выбранная модель чемпионатов и ее реализация в системе Delphi 4 позволили провести серии чемпионатов по 100000-1000000 чемпионатов в каждой, что гарантировало высокую точность полученных статистических данных. На основе этих данных, а также рассчитанных показателей ресурсоемкости сделаны выводы о предпочтении, в целом отданном швейцарской системе, но не исключающем применения других при некоторых описанных наборах условий. Кроме того, отмечена возможность использования реализованной программы для получения дополнительных данных по системам отбора игроков в целях адаптации к требованиям реализуемого алгоритма самообучения.

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

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

А.В.Мосеев, underwood.narod.ru, 1999 год