Введение

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

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

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

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

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

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

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

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

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