Гришанин Е.А. Дурин С.В. Содержание 1. Что такое искусственный интеллект? 2. О базах знаний. 3. Тестовые задания. Искусственный интеллект. В 60-х годах XX века появился новый раздел информатики, который получил название «Искусственный интеллект». В энциклопедическом словаре написано: «Интеллект (от лат. intellectus - познание, понимание, рассудок) - способность мышления, рационального познания». В полной мере эта способность свойственна лишь людям. Предметом изучения науки «Искусственный интеллект» является человеческое мышление. Ученые ищут ответ на вопрос: как человек мыслит? Цель этих исследований состоит в том, чтобы создать модель человеческого интеллекта и реализовать ее на компьютере. Несколько упрощенно, вышеназванная цель звучит так: - Научить машину мыслить. Приступая к решению какой-то проблемы, человек часто не имеет четкой программы действий. Эту программу он строит сам в ходе работы. Например, при игре в шахматы шахматист знает правила игры, имеет цель - выиграть партию. Его действия не запрограммированы заранее. Они зависят от действий соперника, от складывающейся позиции на доске, от сообразительности и личного опыта шахматиста. Существует много других видов человеческой деятельности, которые нельзя запрограммировать заранее. Например, сочинение музыки и стихов, доказательство теоремы, литературный перевод с иностранного языка, диагностика и лечение болезней и многое другое. Вам хорошо известно, что любую работу компьютер выполняет по программе. Программы пишут люди, а компьютер формально их выполняет. Разработчики систем искусственного интеллекта как раз и пытаются научить машину, подобно человеку, самостоятельно строить программу своих действий, исходя из условия задачи. Можно еще сказать так: ставится цель превращения компьютера из формального исполнителя в интеллектуального исполнителя. Формальный исполнитель данные программа Выполнение программы результаты Интеллектуальный исполнитель данные Построение программы Выполнение программы результаты Модель функционирования формального и интеллектуального исполнителя Любая система искусственного интеллекта работает в рамках какой-то определенной предметной области (медицинская диагностика, законодательство, математика, экономика и пр.). Подобно специалисту, компьютер должен обладать знаниями в данной области. Знания в конкретной предметной области,определенным образом формализованные и заложенные в память ЭВМ, называются компьютерной базой знаний. Например, вы хотите применить компьютер для решения задач по геометрии. Если в задачнике имеется 500 задач разного содержания, то при традиционном использовании компьютера придется написать 500 программ. Если же за эту проблему возьмется специалист по искусственному интеллекту, то он подойдет к ней совершенно иначе. Он заложит в компьютер знания геометрии (как закладывают в вас знания учителя). На основе этих знаний и с помощью специального алгоритма логических рассуждений компьютер решит любую из 500 задач. Для этого будет достаточно сообщить ему лишь условие задачи. Системы искусственного интеллекта работают на основе заложенных в них баз знаний. Каждый школьник знает, что для решения любой задачи мало помнить правила, законы, формулы, но еще нужно уметь мыслить, рассуждать, применять эти знания. Человеческое мышление основано на двух составляющих: запасе знаний и способности к логическим рассуждениям Отсюда вытекают две основные задачи при создании интеллектуальных систем на компьютере: - моделирование знаний (разработка методов формализации знаний для ввода их в компьютерную память в качестве базы знаний); - моделирование рассуждений (создание компьютерных программ, имитирующих логику человеческого мышления при решении разнообразных задач). Одним из видов систем искусственного интеллекта являются экспертные системы. Обычно словом «эксперт» называют человека, обладающего большими знаниями и опытом в определенной области. В компьютерные экспертные системы закладываются знания такого уровня. Назначение экспертных систем - консультации пользователя, помощь в принятии решений. Особенно важной становится такая помощь в экстремальных ситуациях, например в условиях технической аварии, экстренной операции, при управлении транспортными средствами. Компьютер не подвержен стрессам. Он быстро найдет оптимальное, безопасное решение и предложит его человеку. Однако окончательное решение принимает человек. Коротко о главном Искусственный интеллект (ИИ) - это раздел информатики. Предмет изучения ИИ - человеческое мышление; цель - создание интеллектуальных систем на компьютере. Примеры областей, в которых создаются системы искусственного интеллекта: шахматы и другие игры, сочинение стихов и музыки, перевод текстов с одного языка на другой, робототехника, криминалистика (идентификация отпечатков пальцев и пр.), медицинская диагностика. Системы искусственного интеллекта работают на основе заложенных в них знаний в определенной области. Модель знаний, заложенная в память ЭВМ, называется компьютерной базой знаний. Человеческое мышление основано на двух составляющих: запасе знаний и способности к логическим рассуждениям. В системах ИИ реализована модель рассуждений (человеческой логики). На основе базы знаний и модели рассуждений система ИИ сама программирует свою работу при решении любой задачи. Экспертная система - это система ИИ, заключающая в себе знания и опыт специалиста-эксперта в данной предметной области. Вот состав базы знаний «Родственники»: Факты: Лев - отец Андрея; Лев - отец Петра; Андрей - отец Алексея; Петр - отец Михаила; Петр - отец Дмитрия. Правила: всякий мужчина - сын своего отца; дедушка - отец отца; братья - сыновья одного отца; дядя - брат отца; племянник - сын брата; внук - сын сына. Исходя из данных фактов и правил, можно путем логических рассуждений установить все виды родственных связей между мужчинами этой семьи. Обратите внимание на две особенности базы знаний: - факты носят частный характер, а правила - общий (справедливы для любой семьи); - в БЗ включены только основополагающие факты. Действительно, достаточно знать, кто кому приходится отцом, чтобы, используя правила, определить другие родственные связи. На основе подобной базы знаний можно построить экспертную систему в области родственных отношений между мужчинами. Чтобы использовать ее по отношению к другой семье, достаточно заменить список фактов, а правила, естественно, останутся прежними. Сравнивая БД с БЗ приходим к выводу: база данных содержит только факты, база знаний - факты и правила. На главную О базах знаний. Вы уже знакомы с понятием «база данных». База данных (БД) - это информационная модель некоторой реальной системы в памяти компьютера. Выше было сказано, что база знаний (БЗ) - это модель знаний человека в определенной предметной области. Покажем разницу между БД и БЗ на конкретном примере. Рассмотрим этот вопрос на примере родственных связей между мужчинами одной семьи. Вот как они выглядят в графической форме родословного дерева: Лев Петр Андрей Михаил Дмитрий Алексей Родословное дерево Здесь линии обозначают связь между отцом (на верхнем уровне) и сыном (на нижнем уровне). Родственные связи Мужчина Лев Сыновья Отец Дедушка Братья Дяди Племян ники Не знаю Не знаю Внуки Андрей, Пётр Не знаю Не знаю Не знаю Андрей Алексей Лев Не знаю Пётр Не знаю Михаил Дмитрий нет Пётр Михаил, Дмитрий Лев Не знаю Андрей Не знаю Алексей нет Алексей Нет Андрей Лев нет нет Михаил Нет Пётр Лев Дмитрий Андрей нет нет Дмитрий Нет Пётр Лев Михаил нет нет нет Пётр Андрей Алексей Михаил Дмитрий В таблице 9.1 информация о родственных связях между этими же мужчинами представлена в развёрнутом виде. Используя СУБД реляционного типа, на основе этой таблицы нетрудно создать реляционную базу данных. Обращаясь к ней с запросами, можно определить, кто кому приходится отцом, дедушкой, братом. Данная таблица представляет собой информационную модель объекта «семья». Теперь перейдем к построению базы знаний. Предметной областью здесь являются родственные связи между мужчинами одной семьи. В искусственном интеллекте существуют различные виды моделей знаний. Мы рассмотрим только один из них, который называется логической моделью знаний. Этот подход используется в системе программирования ПРОЛОГ (о Прологе рассказывается во второй части книги). Согласно логической модели, база знаний состоит из фактов и правил. А теперь дадим общее определение понятиям «факт» и «правило». Факт - это сообщение (информация) о конкретном событии, о свойстве конкретного объекта, о его связи с другими объектами. Например, фактами являются следующие утверждения: - сосна - хвойное дерево; - Колумб открыл Америку в 1492 году; - плотность воды равна 1 г/см; - царь Соломон - сын царя Давида; - Лев Толстой - русский писатель. Правило - это утверждение, обладающее большей общностью, чем факт. Правила определяют одни понятия через другие, устанавливают взаимосвязь между различными свойствами объектов, формулируют законы природы или общества. База знаний - это совокупность основополагающих фактов и правил в определенной предметной области. С недавних пор появилась новая специальность «инженер по знаниям», задача которого - формализация знаний, разработка баз знаний и создание на их основе систем искусственного интеллекта. Рассмотренный нами пример очень простой. Здесь нетрудно догадаться о том, какие факты являются основополагающими, и сформулировать полный набор правил. В более сложных предметных областях эта задача много труднее. Часто решить ее по силам оказывается только крупному специалисту (эксперту) или коллективу специалистов, обладающих большими знаниями в данной области. Коротко о главном. Логическая модель знаний в определенной предметной области представляется базой знаний, составленной из фактов и правил. Факт - это информация о конкретном событии, о свойстве конкретного объекта, о его связи с другими объектами. Правила определяют одни понятия через другие, устанавливают взаимосвязь между различными свойствами объектов, формулируют законы природы или общества. База знаний включает" в себя лишь основополагающие факты для данной предметной области. На главную Тестовые задания 1. 2. 3. 4. Задание №1 Задание №2 Задание №3 Задание №4 Конец Когда возникла в информатике направление под названием «Искусственный интеллект»? A. В 50-х годах B. В 60-х годах C. В 70-х годах D. В 80-х годах Правильно Дальше Подумай Дальше Что такое база знаний? А. База знаний- это информация о конкретном событии, о свойстве конкретного объекта, о его связи с другими объектами. В. База знаний - это совокупность основополагающих фактов и правил в определенной предметной области С. База знаний - это D. База знаний- разработка утверждение, обладающее большей общностью, чем факт. методов формализации знаний для ввода их в компьютерную память в качестве базы знаний Что такое моделирование рассуждений? А. Создание компьютерных программ, В. Разработка методов имитирующих логику человеческого мышления при решение разнообразных задач. формализации знаний для ввода их в компьютерную паять в качестве базы знаний. С. Это модель знаний человека в D. Это алгоритм определённой предметной области. записанный на языке исполнителя. Что такое ФАКТ? А. Любой объект состоящий из B. Эта информация о составе и С. Сообщение о конкретном D. Это определённый порядок множества взаимосвязанных частей и структуре системы, представленная в графической существующие как единое целое. форме. событии и свойстве конкретного объекта, его связи с другими объектами. объединения элементов, составляющих систему.

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

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

Из названия следует, что в алгоритме проводится отсекание по каким-то двум параметрам - альфа и бета. Главная идея отсечения в том, что теперь мы будем держать интервал отсечений (нижняя и верхняя границы - альфа и бета соответственно - ваш К.О.) и оценки всех узлов, какие не попадают в интервал снизу мы рассматривать не будем (так как они не влияют на результат - это просто худшие ходы, чем уже найденный), а сам интервал будем сужать по мере нахождения лучших ходов. Хотя и альфа-бета отсечение намного лучше минимикса, все же время его работы тоже очень большое. Если принять, что в середине партии в одной стороны есть приблизительно 40 разных ходов, то время алгоритма можно оценить как O(40^P), где P - глубина дерева ходов. Конечно, при минимаксе может быть такая последовательность рассмотрения ходов, когда мы не будем делать никаких отсечений, тогда альфа-бета отсечение просто превратится в минимакс. В лучшем случае с помощью альфа-бета отсечения можно избежать проверки корня из числа всех ходов в минимаксе. Для того, чтоб избежать долгого времени работы (при такой О-большое сложности алгоритма), перебор в дереве делают на какую-то фиксированную величину и там проводят оценку узла. Вот эта оценка есть очень великое приближение к реальной оценке узла (то есть, перебора до конца дерева, а там результат - «выиграл, проиграл, ничья»). Насчет оценки узла есть просто кипа различных методик (можно прочесть в линках в конце статьи). Если кратко - то, естественно, подсчитываю материал игрока (согласно одной системе - целыми числами пешка - 100, конь и слон - 300, ладья - 500, ферзь - 900; согласно другой системе - действительными в частях от единицы) + позиция на доске данного игрока. Насчет позиции - то здесь начинается один из кошмаров написания шахмат, так как скорость работы проги будет в основном зависеть от оценочной функции и, если точнее, то от оценки позиции. Тут уже кто во что горазд. За спаренных тур игроку +, за прикрытость короля своими пешками +, за пешку возле другого конца доски + и т.д., а минусуют позицию висячие фигуры, открытый король и т.д. и т.п. - факторов можно написать кучу. Вот для оценки позиции в игре строится оценка позиции игрока, что делает ход, и от нее отнимается оценка соответствующей позиции противника. Как говорят, одна фотография иногда лучше тысячи слов, и, может, кусок кода на псевдо C# тоже будет лучше объяснений:

Enum CurentPlayer {Me, Opponent}; public int AlphaBetaPruning (int alpha, int beta, int depth, CurrentPlayer currentPlayer) { // value of current node int value; // count current node ++nodesSearched; // get opposite to currentPlayer CurrentPlayer opponentPlayer = GetOppositePlayerTo(currentPlayer); // generates all moves for player, which turn is to make move / /moves, generated by this method, are free of moves // after making which current player would be in check List moves = GenerateAllMovesForPlayer(currentPlayer); // loop through the moves foreach move in moves { MakeMove(move); ++ply; // If depth is still, continue to search deeper if (depth > 1) value = -AlphaBetaPruning (-beta, -alpha, depth - 1, opponentPlayer); else // If no depth left (leaf node), evalute that position value = EvaluatePlayerPosition(currentPlayer) - EvaluatePlayerPosition(opponentPlayer); RollBackLastMove(); --ply; if (value > alpha) { // This move is so good that caused a cutoff of rest tree if (value >= beta) return beta; alpha = value; } } if (moves.Count == 0) { // if no moves, than position is checkmate or if (IsInCheck(currentPlayer)) return (-MateValue + ply); else return 0; } return alpha; }

Думаю, не будут излишними некоторые объяснения насчет кода:

• GetOppositePlayerTo() просто меняет CurrentPlayer.Me на CurrentPlayer.Opponent і наоборот
• MakeMove() делает следующий ход из списка ходов
• ply - глобальная переменная (часть класса), которая держит в себе количество полуходов, сделанных на данной глубине

Пример использования метода:

{ ply = 0; nodesSearched = 0; int score = AlphaBetaPruning (-MateValue, MateValue, max_depth, CurrentPlayer.Me); }
где MateValue - достаточно большое число.
Параметр max_depth - максимальная глубина, на которую опустится алгоритм в дереве. Следует иметь в виду, что псевдокод чисто демонстративный, но вполне рабочий.

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

Во-первых, применяется очень известная эвристика «нулевой ход» . В спокойной позиции противнику дают сделать два хода вместо одного и после этого рассматривают дерево на глубину (depth-2), а не (depth-1). Если после оценки такого поддерева окажется, что у текущего игрока все равно есть преимущество, то нет смысла рассматривать поддерево далее, так как после своего следующего хода игрок только сделает свою позицию лучше. Так как перебор полиномиальный, то выигрыш в скорости ощутимый. Иногда бывает так, что противник выровняет свое преимущество, тогда надо рассматривать все поддерево до конца. Пустой ход надо делать не всегда (например, когда один из королей под шахом, в цугцванге или в ендшпиле).

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

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

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

Все было бы хорошо, если бы альфа-бета отсечение гарантировано давало бы лучший ответ. Даже учитывая долгое время на перебор. Но не тут то было. Проблема в том, что после перебора на фиксированную величину проводится оценка позиции и все, а, как оказалось, в некоторых игровых позициях нельзя прекращать перебор. После многих попыток выяснилось, что перебор можно прекращать только в спокойных позициях. Поэтому в основном переборе дописали дополнительный перебор, в котором рассматриваются только взятия, promotions и шахи (называется форсированный перебор ). Также заметили, что некоторый позиции с разменом в середине также надо рассматривать поглубже. Так появились идеи насчет extensions і reductions , то есть углублений и укорачиваний дерева перебора. Для углублений найболее подходящие позиции типа ендшпиля с пешками, ухода от шаха, размен фигуры в середине перебора и т.д. Для укорачиваний подходят «абсолютно спокойные» позиции. В советской программе Каисса форсированный перебор был немного особенным - там после взятия во время перебора сразу начинался форсированный и его глубина не ограничивалась (так как за некоторое время он сам себя исчерпает в спокойной позиции).

Как говорил Энтони Хоар : "Premature optimization is the root of all evil in programming. " (примечание: для тех, кто считает, что данная цитата принадлежит Кнуту, есть интересные дискусии

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

– Владимир Львович, а как пришли к мысли, что компьютер может решать интеллектуальные задачи?

– Когда выяснили, что компьютеры умеют не только вычислять, как это было придумано с самого начала, что за арифметическими действиями есть логическое действо, которое не только выполняет вспомогательные функции в деятельности вычислительных программ, но и с помощью которого можно решать самостоятельные задачи, то стало ясно: стоит попробовать положить на компьютер интеллектуальные задачи. Где-то с конца 40-х годов и до конца 50-х это активно обсуждалось, более того, ставились полу философские вопросы: а может, компьютеры будут умнее людей? И что тогда? И все на полном серьезе. Сейчас такие вопросы не ставят, все-таки 40 лет прошло. Тогда, на заре вычислительной техники, мы только осознали, что принципиально могут делать машины. Мы поняли, что человеческий мозг есть устройство, аналогичное вычислительной машине, и в тысячу, в миллион раз более мощное, но оно принципиально немножко отличается. Стало понятно, что, по крайней мере, большинство рациональных задач, которые решает человек, могут быть поставлены перед машиной. Следовательно, можно попробовать написать программы, которые эти задачи решают. Одну, две, тысячу... ведь человек тоже решает не бесконечное множество задач. И можно, так сказать, всю интеллектуальную деятельность человека запрограммировать.

– А почему все же решили обратиться к игре?

– Как я уже говорил, широко обсуждалось, может ли машина мыслить. Однако совершенно ясно, что если речь идет о программистах, о людях, которые имеют дело не с философией, а с реальным компьютером, то вопрос не в том, может ли машина принципиально что-то делать, а в поиске примеров того, где машины решают интеллектуальные задачи, причем такие, которые доступны и человеку в его интеллектуальной деятельности. Грань здесь, конечно, не четкая. Но понятно, что если человек множит 20­значные числа, то он при этом не имеет дело с глубоко интеллектуальной задачей, поскольку для ее выполнения очень легко найти тривиальный алгоритм, который известен каждому школьнику. А вот те задачи, где совершенно ясно, что никакого априорного алгоритма у человека нет, а он тем не менее хорошо их решает, мы и будем называть интеллектуальными. Первым претендентом на роль таких задач являются игры, по той простой причине, что, по крайней мере, правила четко сформулированы. Задача чрезвычайно трудная, а правила игры сформулировать легко, и тем самым легко определить и функции машины. С другой стороны, шахматы для человека трудная задача, что как-то никогда не обсуждалось и сейчас не обсуждается.

– А почему из игр выбрали все-таки шахматы? Может быть, традиция?

– Почему только шахматы? Пробовали и крестики­нолики, другие игры. Но у шахмат немало преимуществ перед другими играми. Если в простых играх машина обыгрывает человека, то это никого не удивляет. Шахматы - игра сложная, и победа компьютера здесь значима. Затем в шахматах, в отличие от ряда других игр, много дифференцируемых критериев качества, то есть можно определить: машина играет хорошо, машина играет лучше, лучше, лучше. Во многих других играх подобные градации установить очень трудно. В некоторых же из них машину либо обучают играть абсолютно точно, и тем самым сразу теряется всякий интерес к игре, либо она играет из рук вон плохо. А в шахматах, не абстрактных, а, так сказать, освоенных, уровней столько, что с их помощью можно определить класс игры машины.

– Итак, понятно, почему шахматы были одной из первых и важнейших задач искусственного интеллекта. А какие методы применялись для ее решения?

– С самого начала постепенно осваивалась методика решения задачи шахматной игры. В принципе, шахматы - игра конечная, и с математической строгостью можно доказать, что в любой позиции абстрактно существует наилучший ход для каждого из противников, а значит, и какой-то результат. Поэтому нужно описать алгоритм, в котором эта игра может быть рассчитана до конца. Единственный недостаток такого алгоритма состоит в том, что он требует много времени. И мы не приблизились к тем порядкам времени, которые нужны, чтобы рассчитать, скажем, шахматы до конца из начальной позиции. За прошедшие пятьдесят лет задача в смысле времени так и осталась бесконечно сложной. Ну, бесконечность минус десять - все равно бесконечность. Но если вам нужно время, скажем, 10 в 100-й степени лет, и вы ускорите машину, скажем, в 100 раз, и получите 10 в 98-й степени лет, то вам вряд ли от этого станет легче. Поэтому основной алгоритм - переборный, тривиальный: если я пойду так, то у противника есть столько-то возможностей. Варианты растут в геометрической прогрессии и образуют цепочки. Но количество позиций вообще конечно, и их на каждой цепочке не так уж много. Цепочки объединяются в деревья, которые опять же не бесконечны. Правда, растут они в геометрической прогрессии, и количество цепочек увеличивается. Так вот, встает важный вопрос: нужен ли полный, до самого конца, перебор - до всех матов, патов, троекратных повторений и прочих окончаний игры по шахматным правилам? Ведь если алгоритм ведет к позициям, которые не обязательны на этом дереве, то, возможно, все это дерево и не нужно рассматривать. Заметьте себе, что в диспозиции, где белые дают мат в один ход, можно построить такое же бесконечное дерево, но рассматривать-то его не нужно, а достаточно найти этот один-единственный ход. Может, такая же ситуация и в шахматах в целом? Вообще алгоритм перебора, перебора вариантов имеет отношение к такому количеству решаемых человеком задач, что, если бы мы умели его организовывать каким-нибудь уж очень оригинальным способом, то он был бы, в каком-то смысле, как бы изобретением колеса для человечества - одного из фундаментальнейших открытий. Так вот, перебор мог бы быть, а может, и является таковым - колесом искусственного интеллекта.

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

– Да, да. Эту задачу нужно было быстро и эффективно решать, и в шахматах довольно быстро пришли к следующей теоретической постановке вопроса: а давайте смотреть не бесконечное количество ходов, а лишь несколько ходов вперед. Скажем, посмотрим на 5 ходов вперед. Это очень много. Если вы любите шахматы и 5 ходов вам кажется мало, то давайте возьмем 10. И тогда машина на 10 ходов, на 20 полуходов вперед не будет ни в чем ошибаться и гарантирует, что через 10 ходов у вас фигур окажется не меньше. Ясно, что мы имеем дело с сильной играющей машиной. Так что дерево игры придется сократить и решать задачу в гораздо более ограниченном пространстве. Другой вопрос, что и это дерево стараются рассматривать не полностью, с помощью математических методов отсечения. Об одном из них я уже рассказывал: если есть мат в один ход, незачем просматривать остальные варианты. Другие алгоритмы имеют эвристический, не точный характер. В среднем они работают правильно, многие абсолютно точные, но могут и ошибаться. Например, мы можем перебирать не все ходы, а только взятие, и просчитывать их намного вперед, потому что взятий-то мало. Общая углубленность ходов невелика: больше тридцати двух фигур не съесть. Поэтому и длины цепочек небольшие и ветвлений мало. Конечно, ясно, что на одних только взятиях нельзя построить игру, должны быть какие-то позиционные соображения. Комбинация форсирующих (взятие, шах) и позиционных соображений, а также некоторой глубины перебора - основа всех существующих алгоритмов, и она особо не меняется. Другой вопрос: как отбирать те ходы, которые я буду рассматривать дальше? На основании ли только простых формальных критериев (взятие, шах) или же связывать эти ходы, как шахматисты любят говорить, планом, придумывать какие-то цепочки, которые обладают каким-то общим свойством? Во всяком случае, об этом написано очень много серьезных работ, имеющих практическое применение. Не зря созданием шахматных программ занимаются достаточно солидные фирмы.

– А когда появились первые шахматные программы?

– Реальные шахматные программы впервые появились где-то в конце 50-х годов в Америке, а потом где-то в начале 60-х годов - и у нас. Программы были очень слабые, потому что тогда были и предельно примитивные машины и не привычное еще к новизне наше мышление. Включились мы в это дело примерно в 1963 году. Тогда на наших отечественных машинах и были какие-то матчи. По-моему, в 1967 году был первый матч СССР - США. Он так назывался, хотя, конечно, проходил между двумя коллективами, а не странами. Это был матч между нашей программой, разработанной в Институте теоретической и экспериментальной физики, и программой Джона Маккарти, очень известного в компьютерном мире человека, одного из создателей языков программирования, который увлекался тогда шахматными программами. Ходы передавались по телеграфу, тогда ведь никаких сетей не было.

– И кто победил?

– Мы тогда выиграли 3:1. Играли 4 партии. Делался ход в день, поскольку у американцев были более мощные и глубокие программы, которые долго думали, а мы играли на разных вариантах программ, думающих и быстро, и медленно. Наш выигрыш был первым нашим достижением. Это направление стало постепенно развиваться и особенно активизировалось в 70-е годы. Примерно в 1974 году состоялся первый чемпионат мира среди шахматных программ в Стокгольме. Участвовало около восьми программ, в том числе и наших. И мы тогда тоже победили и стали первыми чемпионами мира. С тех пор чемпионаты мира проводятся регулярно, каждые 3 года. Мы в них участвовали еще 2 раза - в 1977 г. и в 1980 г. Лавров мы тогда не снискали, потому что в 1977 г. поделили 2-е и 3-е место (участвовало много шахматных программ, были даже региональные отборы), а в 1980 г. - 4-е и 5-е место. В общем, потихоньку откатывались. Дело в том, что к этому моменту был уже громадный прогресс в вычислительной технике, а мы все еще играли на компьютерах довольно устарелых. И к 1980 г. нам стало ясно, что соревноваться на тех машинах, на которых мы работаем, потеряло всякий смысл, да и вообще в России работы в области шахматных программ стали сходить на нет. Хотя и было довольно много интересных теоретических работ. Чуть позднее создали первую, пожалуй, программу, которая прошла по миру, она умела абсолютно точно разыгрывать сложный эндшпиль, т. е. ферзь и пешка против ферзя, или ладья и пешка против ладьи. Такие эндшпили программа просто до конца рассматривала, т. е. в любой позиции она давала идеально верный ход. Алгоритм был построен на немножко отличных от простого перебора принципах, на полном осмотре всего множества позиций. Ну, и потом в шахматах делали некоторые работы такого характера. А с практической игрой мы тогда распрощались, потому что разности в скоростях были уже в сотни раз. Но чемпионаты продолжались, и развитие шахматных программ продвинулось на совершенно новый уровень, как только все перешло на РС. В результате широкой коммерциализации, в шахматные программы стали вкладывать огромные деньги, сразу все засекретили. А раньше они принадлежали ученым, которые, если не заставить специально, не скрывают своих достижений, а, наоборот, пропагандируют их. В 1980 г. мы впервые почувствовали, что наступило время коммерческого программирования. Этот мир, конечно, своеобразен. Во-первых, потому что в него ведь вкладываются деньги, во-вторых, потому что из него извлекаются деньги. Хотя и существуют журналы по шахматным программам, но за последние 15 - 17 лет реальный обмен идеями сильно сошел на нет, потому что на PC они стали огромным бизнесом.

– Но ведь коммерция стимулирует развитие рынка шахматного ПО?

– Раньше компьютерные соревнования приурочивались к форумам вычислительной техники. Есть такая организация - МФИ (Международная федерация по информатике) и, обычно, к ее конгрессу приурочивались чемпионаты мира. Сейчас они стали абсолютно самостоятельными мероприятиями, достаточно престижными. Таких программ уже сотни и сотни. Сам уровень программирования и уровень наших знаний уже таков, что сделать простенькую шахматную программу не составляет ни малейшего труда. Это нормальная студенческая работа. Я ее как раз и поручаю какому-нибудь студенту. Обыграть шахматную программу стало, так сказать, расхожим местом.

– Но, как всегда, низший уровень упрощается, а высший усложняется?

– Вот именно. Поэтому последние программы, те, что сейчас побеждают, в частности, программа, которая победила Каспарова, стали намного сильнее. Глубина перебора значительно выросла и, конечно, это результат наших математических продвижений, а отчасти просто прогресса вычислительной техники. Ведь если раньше рассмотрение 1000 позиций в секунду считалось очень много, то сейчас в тех деревьях, о которых мы с вами уже говорили, рассматривается более миллиона позиций. А лишний миллион - это несколько уровней ходов при правильном отборе. А каждый уровень глубины перебора очень усиливает программу. Каждый уровень на ход вперед - это примерно разряд, и, скажем, глубина перебора в четыре хода - это третий разряд, в пять ходов - уже второй разряд. Когда мы достигаем уровня в 11–13 ходов - это мастерский уровень и дальше играть с машиной довольно сложно. Конечно, сейчас лидируют американцы, потому что умеют вкладывать большие деньги в такие вещи.

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

– В точности никто не скажет, потому что это предмет спекуляции. Были достаточно сильные программы с просто минимальными знаниями, сознательно минимальными, специально для того, чтобы посмотреть, что можно выжать из чистой математики. В какой-то момент это было связано с коммерциализацией и особенно с тем, что стали делать максимально сильные программы - не важно уже за счет чего. Но отчасти из-за того, что работа с заложенными знаниями - самостоятельная задача, то их стало очень много. Прежде всего был создан огромнейший справочник. Сейчас справочники - это сотни тысяч позиций. Затем очень много шахматного интеллекта вкладывают всегда в оценку позиций. Она сводится, конечно, и к игровому материалу, что тривиально, и к некоторым позиционным факторам. Так вот, позиционные факторы - чисто шахматный интеллект, который, конечно, программируется, но здесь его закладывается много и он все время совершенствуется. И чем больше факторов туда вкладывается, тем сильнее программа. В каком-то смысле умение оценить позицию и глубина перебора - вещи взаимозаменяемые. Если бы мы умели оценивать позицию гениально, то нам было бы достаточно попробовать все первые ходы. Это как крайний пример. Понятно, что лучшая оценка позиции соответственно больше влияет на глубину перебора. Таков второй, принципиальный метод. Существует довольно много программ, где шахматный интеллект закладывается в выбор самих рассматриваемых вариантов, то есть каких-то чисто шахматных соображений, каких-то планов. Таких соображений довольно много, что ограничивает круг перебора. Область их действия не очень широкая, и интеллектуально-шахматные специфические данные замедляют перебор. Кстати, именно за интеллектуальные вещи, когда-то очень сильно ратовал Ботвинник. Он был большим энтузиастом машинных шахмат и внес туда некоторые идеи. Хотя ему так и не удалось создать действующую программу, но тем не менее его авторитет был тогда очень высок. Так вот, он очень расстраивался, что, в общем, направление не такое "интеллектуальное", как ему хотелось бы, и в программы вкладывался очень ограниченный объем чисто шахматных знаний.

– А специализированные шахматные компьютеры? Они, видимо, действуют именно методом генерации?

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

– Есть ли средства для создания универсального мыслительного аппарата, в который можно было бы заложить базу знаний - неважно, шахматные позиции или что-нибудь еще, правила, по которым с этими знаниями надо работать - и получать от него адекватные результаты?

– Ясно, что в плане конструктивности, такая задача сегодня не решаема, не актуальна. Хотя многие интеллектуальные задачи сейчас решаются, такие, например, как распознавание текста. Вы можете положить в сканер листок с текстом и получить его на экране в Word. Он сам прочтется, каждая буковка распознается. Реально мы продвинулись во многих интеллектуальных задачах. Одни из них уже решены, другие решаются. В чем-то получается сравнительно лучше, нежели при участии человека, в чем-то пока еще хуже. Можно привести много примеров практических задач. Что касается универсального искусственного мыслительного механизма, то это, скорее, проблема философская, чем практическая. Ведь даже для такой простой игры, как шахматы, нам потребовалось 30 - 40 лет, чтобы фактически чего-то добиться. Всякая философия основывается на мнениях. Каждый думает, что он прав, а может, каждый прав по-своему. Например, я всю жизнь имел дело с искусственным интеллектом и полагаю, что мозг человека не более чем большая вычислительная машина, следовательно, нельзя сказать, что принципиально невозможно создать аналогичную ей. Вопрос в ее мощности, скоростных характеристиках, в наполнении ее знаниями. Ничего непостижимого здесь нет. Это моя личная точка зрения. Но существуют и другие мнения. Конечно, если мы признаем божественную природу человека, то тогда уже надо выбрать один из двух гносеологических вариантов. Либо да, мы имеем божественную природу, но она познаваема. В таком случае нам не удастся воспроизвести по-настоящему то, что сумел сделать Господь Бог, но, по крайней мере, мы сможем Его творения хотя бы частично воссоздать. Либо же мы стоим на позиции агностицизма, и тогда она непознаваема, и вопрос полностью снимается. Выходит, что некоторые задачи человеческий мозг решает - и тут ни у кого сомнений нет. Но догнать мозг мы не можем, потому что, с одной стороны, он создан Богом, а с другой - познать его мы не в состоянии. Все три позиции связаны с верой, поскольку в реальности-то необязательно познавать все функции мозга. Если мы сделаем машину, по мощности равную мозгу, то ей ни к чему думать так, как мозг. Она по-другому будет работать.

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

– Полно программ, которые специально нацелены на то, чтобы создавать понятия, абстрагирующиеся от существующего фактического материала. Такие программы хорошо работают. Другой вопрос, что человек умеет создавать эти понятия как бы по своим собственным законам, которые он сам себе придумывает. Все наши попытки перевести эти его законы на язык алгебры логики оказываются бесперспективными. У человека гораздо более мощный мыслительный механизм, который мы просто не знаем. Мы ничего не умеем делать "вообще". Мы создаем необходимые нам формулировки, но "выразить" их в точных машинных задачах не можем. К механическим задачам все сводится с трудом, и даже если сводится, то медленно. Наверное, мы пока не знаем более прямых путей к достижению цели. Заложить-то в компьютер можно все, что угодно. Вопрос в том, что человек способен манипулировать этими знаниями все время, но он еще не умеет заставить делать то же самое машину из-за ограниченного объема и скорости данных.

– Но, может быть, не имеет никакого смысла заставлять машину манипулировать знаниями?

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

– Владимир Львович, скажите, если бы сейчас снова была заря компьютерной техники, стоило бы заниматься шахматными программами? Действительно ли они настолько способствовали прогрессу?

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

Предмет, возраст учащихся

Информатика и ИКТ,10-11класс

Краткая аннотация проекта

Проект разработан в рамках дисциплины "Информатика и ИКТ" для обучающихся 10-11 класса

Вопросы, направляющие проект

Основополагающий вопрос

Может ли компьютер заменить человека?

Проблемные вопросы

1. Может ли ЭВМ сама ставить задачи и решать их?

2. Способен ли компьютер воспроизвести все действия и мысли человека?

3. Способна ли ЭВМ управлять человеком?

Учебные вопросы

1. Какие задачи решает компьютер?

2. Самообучается ли ЭВМ?

3. Могут ли автоматы заменить человека?

4. Искусственный интеллект=Интеллект человека?

5. Нужно ли руководить работой ЭВМ?

6. Возможно ли поставить робота "во главу стола"?

7. Умеет ли думать компьютер?

8. Возможно ли заменить человеческий мозг искусственным?

9. Готов ли человек поручить всю работу роботам?

План проведения проекта

Представление проблемной ситуации:

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

Работа над проектом:

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

Оформление результатов проектной деятельности:

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

Защита проекта, оппонирование, дискуссия:

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

По окончании работы:

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

Визитная карточка проекта

Публикация учителя

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

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

шахматный компьютерный интеллект алгоритм

• Введение

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

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

* существует объективный критерий сделанной работы - сила шахматной программы

* большая дифференцированность этого критерия представляет возможность постепенного усовершенствования программы.

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

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

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

Слабость игры компьютеров заключалась именно в злоупотреблении материалом и невозможности осуществить «абсолютный перебор» вариантов. В шахматных книгах 70-80-х годов можно встретить немалое количество образцово-показательных примеров игры людей с машинами, когда мастер или гроссмейстер выигрывал партию с помощью красивых жертв фигур и пешек. Секрет уже понятен: для человеческого интеллекта, в отличие от искусственного, было очевидным доминирование позиционных факторов над материальными именно в те моменты, когда осуществлялись жертвы материала.

Шли годы, с ростом быстродействия ЭВМ увеличивалась глубина расчета, и одновременно совершенствовались алгоритмы, улучшающие составление функций оценки позиций. И во второй половине 90-х годов компьютеры уже стали успешно соперничать с гроссмейстерами экстра-класса. Эпохальное для «шахматных кибернетиков» событие произошло в мае 1997 года. Созданный корпорацией IBM компьютер Deep Blue в матче из 6 партий победил самого Гарри Каспарова. Компьютер был оснащен специальным шахматным чипом, причем машина просматривала около 200 млн. позиций в секунду. Корпорация IBM для своего проекта привлекла многих гроссмейстеров, использовались последние достижения шахматной теории для создания как можно более совершенных алгоритмов. И вот, как уже отмечалось, в 90-е годы шахматные программы для настольных ПК стали теснить специализированные компьютеры.

С каждым месяцем сила шахматных программ и мощность компьютеров неумолимо увеличивается, опережая даже самые смелые предположения оптимистов. Еще лет 12-15 назад рассуждения на тему «Когда машина сможет обыгрывать гроссмейстера?» в основном сводились к вопросу «А способна ли она это сделать в принципе?». И если ответ «Сможет» все же удавалось получить, то время оценивалось в промежутке 15-25 лет.

Действительность же опровергла и эти прогнозы. Все случилось гораздо быстрее! Уже в середине 90-х обнаружилось, что синтез «игровая программа + компьютер» способен состязаться с гроссмейстером.

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

1. исследование существующих игровых алгоритмов применимых для игры шахматы

2. разработка алгоритма поведение компьютерного оппонента

3. определение параметров алгоритма поведение компьютерного оппонента

4. реализация программного обеспечения, что включает в себя реализацию игрового алгоритма и разработка графического интерфейса

5. сравнение разработанного программного обеспечения с существующими аналогами.

1 . История развития шахматных программ

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

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

* тип В - выполняет только выборочные расширение определенных строк, используя накопленные шахматные знания, чтобы подрезать неинтересные ветви

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

Через несколько лет этот компьютер ("MANIAC") сыграл с людьми: сильный шахматист одержал уверенную победу, а новичок проиграл за 23 хода.

В 1957 году на IBM704 (42 кГц, 7 Кбайт -память) был реализован тип В программы на полной доске, с участием всех фигур. Машина считала 4 полухода за 8 минут. Уровень игры - любительский.

В 1962 году Ньюэл, Саймон и Шоу открывают алгоритм, получивший название альфа-бета (alpha-beta), он давал результат не хуже, чем полный перебор, не исследуя все варианты. В нем не требовались никаких специальных шахматных знаний, и он мог быть применен для решения любой переборной задачи. Суть алгоритма в том, что в каждой строке игры, для белых и черных отслеживаются их максимальные результаты, и если в некоторой точке черные уже получили результат, сравнявшийся с максимумом белых, достигнутым до этого, то дальше передирать нет смысла. Когда перебор вернется в точку, где был достигнут максимум белых, результат, все равно, будет отвергнут.В основе всех современных шахматных программ лежит одна из усовершенствованных версий данного алгоритма.

Примерно до 1973 года все шахматные программы были типа В. Они главным образом основывались на генераторах правдоподобных перемещений, отсекая статической оценкой малоправдоподобные. С появлением более мощных процессоров программисты стали переключаться на тип А. Первыми были Teach и Chess4, это были программы «грубой силы», как только они достигали глубины 5 полуходов средней стадии игры, они начинали побеждать в соревнованиях с программами типа В.

В 1975 году Роберт Хьят начинает разрабатывать CrayBlitz, который долгое время был самой быстрой шахматной программой и в период с 1983 по 1989 гг. - мировым чемпионам среди шахматных программ. Он искал примерно 40-50 тыс. позиций в секунду (в 1983 году), что для своего времени было большим достижением.

В 1977 году Томпсон и Кондон из лаборатории Bell создают первый специализированный шахматный комрьютер. Основная идея была в реализации некоторых частей шахматной программы (генератора ходов, функции оценки позиции, детектора шахов и пр.) на аппаратном уровне, что избавляло от программных задержек в каждой позиции не дожидаясь увеличения мощности процессоров. Лучшие компьютеры того времени могли исследовать до 5 тысяч позиций в секунду, а машина Кена Томпсона, которую назвали Belle, обрабатывала 180 тысяч строк в секунду. Belle мог продумывать позиции на 8-9 полуходов вперед, что ставило его на уровень мастера. Он побеждал на многих компьютерных шахматных турнирах. Но несмотря на то, что специализированное железо на порядок быстрее, чем обычная машина, программа CrayBlitz на сверхсовременной тогда машине все равно играла лучше.

В 90-х года Ричард Лэнг, пишущий исключительно на ассемблере, сделал очень сильную программу выборочного поиска Genius. До сих пор эта программа стабильно держит 5-6 место на мировых компьютерных шахматных чемпионатах. Так же в 90-ы годы стали сильно развиваться шахматные алгоритмы, появилась эвристика пустого хода (NullMove), выборочное отсечение пограничных ветвей дерева перебора.

Отдельно стоит рассмотреть самую известную шахматную программу, шахматный супер компьютер - Deep Blue. В 1987 году Deep Blue начиналась как студенческая разработка - интересно было группе способных студентов попробовать свои силы, да и тема для диплома отличная. Прогресс технологии позволил сделать первую же версию процессоров (названную ChipTest) очень быстрыми. Последовала следующая, усовершенствованная версия, названная Deep Thought. В этот момент группу заметил маркетинговый департамент фирмы IBM и обратился к ней с предложением, от которого невозможно было отказаться. Результатом стали Deep Blue и Deep Blue II. Таким образом, Deep Blue II - это результат более чем 10 лет работы очень способной группы, в которой были как программисты/железячники, так и сильные гроссмейстеры. Финансировалась вся работа фирмой IBM, таким образом у группы были ресурсы, которые и не снились академическим организациям. Deep Blue II сделана на основе мощного сервера RS/6000 фирмы IBM. В сервере имеется 31 обычных процессора; один объявлен главным, ему подчиняются 30 остальных. К каждому «рабочему» процессору подключено 16 специализированных шахматных процессора, таким образом всего имеется 480 шахматных процессоров. Весь комплекс обрабатывал более миллиарда позиций в секунду.

11 мая 1997 года Deep Blue II одержал победу над чемпионом мира по шахматам Гарри Каспаровым в матче из 6 партий. После матча с чемпионом, Deep Blue был разобран.

Как видно, начиная с самых первых, и заканчивая самыми современными программами, шахматные программы строились на основе перебора возможных ходов, но были и попытки построить более "интеллектуальные" алгоритмы, отличные от переборного. Многие известные шахматисты пытались разработать такие алгоритмы, но результаты не удовлетворяли требованиям. К примеру Ботвинник М.М., будучи чемпионом мира и автором многочисленных работ по теории шахмат, более 20 лет занимался созданием шахматной программы, но программа так никогда и не заиграла.

Все переборные алгоритмы для поиска наилучшего хода строият дерево игры и по нему ищут лучший ход.

2. Общие понятия теории игр

2.1 Дерево возможных позиций

Пусть задано конечное ориентированное дерево G, множество В его вершин составлено из двух непересекающихся подмножеств B0 и B1 , а любой вершине p B , которая не является началом никакого звена этого дерева, поставлено в соответствие действительное число Oe(p) . Это определяет игру двух противников с полной информацией. Вершины ориентированного дерева G, принадлежащие подмножеству B0 , называются позициями с ходом белых, а принадлежащие подмножеству B1 - позициями с ходом черных; звенья этого дерева называются ходами белых или черных в зависимости от того, какому из подмножеств B0 или B1 принадлежит их начало. Если позиции p B поставлено в соответствие число Oe(p) , она называется заключительной, а Oe(p) называется статической оценкой этой позиции.

Ориентированное дерево G называется деревом игры.

Согласно определению для любой позиции p B существует единственный путь L{p0 > p1, p1 > p2 , ..., pk > p } с началом в корне p0 ориентированного дерева Г и концом в рассматриваемой позиции,такой путь называется партией, приводящей к позиции p .

Корень p0 дерева игры G является выделенной позицией. Это - позиция, предложенная программе, и задача состоит в том, чтобы найти в ней лучший ход. Для этого достаточно определить Oep0 и Oepi для всех позиций, которые получаются из p0 за один ход. Определения оценки начальной позиции p0 , выполняется схемой полного перебора, а в теории игр этот алгоритм называется алгоритмом negamax.

Сложность игрового дерева вычисляется по формуле: w^d, где w-среднее кол-во возможных ходов, а d-глубина дерева.

Рисунок 1 - Дерево возможных позиций

2.2 Принцип минимакса

Данный алгоритм осуществляется с помощью поиска в глубину. То есть для каждой не пройденной вершины необходимо найти все не пройденные смежные вершины и повторить поиск для них. Мы откатываемся на вершину последней глубины и рассчитываем очки выигрыша относительно первого игрока. Затем от родительского ему узла переходим на следующий дочерний узел (если есть) и рассчитываем там очки выигрыша. Если количество дочерних узлов закончилось, то ищем минимум очков выигрыша (если уровень родительского узла нечетный) либо максимум (если четный). Родительский узел обладает полученным очком выигрыша. Делаем аналогичный поиск, но учитывая уже, что родительский узел уже дочерний.

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

Рисунок 2 - Поиск в дереве алгоритмом минимакс

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

Этот алгоритм осуществляет полный перебор всех вариантов. Число рассмотренных позиций будет оцениваться как W в степени D, где W - примерное количество ходов в одной позиции, D - глубина просчета. Для шахмат W примерно равно 40, это значит, что считая на глубину 4, мы должны перебрать 40^4 = 2560 тыс. позиций, а для глубины 5 - 10240 тыс. позиций.

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

На рисунке 3 представлена блок-схема алгоритма минимакс по выбору лучшего хода, представленный алгоритм возвращает лучший ход по оценке, полученной при более глубоком анализе. Блок-схема алгоритма по поиску оценки в глубину представлена на рисунке 4.

Рисунок 3 - Блок-схема по выбору лучшего хода

Рисунок 4 - Блок-схема по поиску оценки в глубину

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

2.3 Метод отрицательного максимума (NegaMax)

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

Рисунок 5 - Метод отрицательного максимума

2.4 Статическая оценка позиции и основные требования к оценочной функции

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

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

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

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

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

* позиционная - показывает качество расположения фигур игрока

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

* отслеживание конца игры - в случаи выигрыша (взятие короля соперника), должна давать максимальную оценку, обычно + бесконечность, в случаи проигрыша (потери короля), должна возвращать минимальную оценку, обычно - бесконечность

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

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

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

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

Следовательно, оценочную функцию можно представить в следующем виде:

F(p) - оценочная функция по позиции р,

Коэффициент важности для i-ой характеристики,

I-ая характеристика позиции p.

2.5 Постановка задачи

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

По итогам дипломной работы необходимо:

ь реализовать исследуемые алгоритмы на языке программирования С#

ь реализовать их различные модификации, используя дополнительные модули

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

ь разработать удобный и интуитивно понятный интерфейс

3. Исследуемые алгоритмы и дополнения

3.1 Альфа-бета отсечение

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

Рисунок 6 - Алгоритм альфа-бета отсечения

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

Ключевая идея альфа - бета отсечения состоит в том, чтобы найти ход не обязательно лучший, но "достаточно хороший" для того, чтобы принять правильное решение.

На вход этого алгоритма подаются параметры alpha и beta, их называют окном перебора. Эти параметры отвечают за границы отсечения на первом уровне, при углублении в дерево игры, эти параметры изменяются. Алгоритм alpha-beta с параметрами alpha = + бесконечность и beta = - бесконечность (перебор с полным окном) дает результат точно такой же, как и алгоритм negamax, т.е полный перебор. На рисунке 7 представлена блок-схема алгоритма alpha-beta по подсчету оценки позиции в глубину.

Рисунок 7 - Блок-схема alpha-beta по поиску оценки в глубину

3.1.1 Пример стандартного отсечения

Рисунок 8 - Пример стандартного отсечения

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

3 .1.2 Пример углубленного отсечения

Рисунок 9 - Пример углубленного отсечения

Рассмотрим пример глубокого отсечения. В позиции А мы будем выбирать между ходами в позиции В и С. Значение В=15. Мы начинаем расчет С. В позиции Е один из узлов дал значение 5. В позиции Е выбор хода принадлежит сопернику, а значит итоговое значение Е будет от 5 и ниже. Если значение С окажется равным Е, то мы выберем вариант В, так как он более привлекательный. Следовательно нам не обязательно знать точное значение позиции Е, поэтому все остальные ветви выходящие из него обрезаются.

3 .2 Итерационное погружение (Iterated Deepening )

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

В общем случае, альфа-бета отсечение вызывается из вершины дерева на интервале (-?;+?). Однако используя итерационное погружение мы можем его поменять.

Предположим что Х - значение оптимального хода найденное на предидущей итерации, а числом Epsilon обозначим предполагаемую разницу в результатах между поиском на глубину D-1 и глубину D. Далее мы просто вызываем альфа-бета отсечение из вершины дерева с предполагаемым интервалом: alphabeta(D, x-epsilon, x+epsilon).

1. Значение вернется в интервале (x-epsilon, x+epsilon) - это корректное значение, мы можем его использовать.

2. Значение вернется вне интервала (x-epsilon, x+epsilon) необходимо повторить вычисление с измененным интервалом.

Даже если допустить, что метод альфа-бета отсечений не даст никакого выигрыша, общее увеличение времени анализа на самом деле окажется относительно небольшим. Действительно если предположить, что среднее число вариантов на каждом уровне равно D, а количество анализируемых уровней составляет p, то итеративный поиск до первого уровня, затем до второго и т.д. до уровня p, эквивалентен (без альфа-бета отсечений) просмотру D + + ...+ позиций.

Эта сумма равна, тогда как количество позиций, просматриваемых при обычном анализе, равно. Соотношение между этими двумя числами при больших p примерно равно и, следовательно, близко к 1 в случаях, когда D достаточно велико

Также при использование итеративного поиска можно ввести контроль времени, что позволит компьютеру в любой момент предложить удовлетворительное решение. Таким образом, если время на размышление ограничено 5 секундами, он рассмотрит все позиции до уровня 2, например, за 0.001 секунду, до уровня 3 - за 0.01 секунду, до уровня 4 - за 1 секунду, а затем, после начала анализа на уровне 5 будет вынужден прерваться из-за нехватки времени. Однако при этом у компьютера уже будет достаточно хорошее решение, найденное на уровне 4.

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

Несмотря на то, что некоторые ветки дерева придется проверять несколько раз этот метод дает достаточное количество отсечений.

3.3 Сортировка ходов

На результаты альфа-бета отсечения очень сильно влияет в каком порядке проверяются ходы. Рассмотрим это на примерах:

В первом случае проведем расчет рассортировав ходы «от худшего к лучшему»

Рисунок 10 - Альфа-бета отсечение с ходами «от худшего к лучшему»

Как видно из примера, не было отсечено ни одно ветви дерева.

Теперь отсортируем ходы «от лучшего к худшему»

Рисунок 11 - альфа-бета отсечение с ходами «от лучшего к худшему»

При оптимальных обстоятельствах перебор с альфа-бета отсечением должен просмотреть W^((D+1)/2) + W^(D/2) - 1 позицию. Это намного меньше чем минимакс.

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

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

Для остальных ходов алгоритм отдает предпочтение ходам с шахами и взятиями.

3 .4 Нега-Скаут (NegaScout)

NegaScout - надстройка над альфа бетой. Это направленный алгоритм поиска для вычисления минимаксного значения узла.

NegaScout -- самый популярный на сегодня алгоритм грубого усилия. Он чрезвычайно прост и дает некоторое (до 50%) ускорение, не внося никакой дополнительной погрешности в вычисление. Он очень хорошо сочетается с современными атрибутами шахматных программ -- хеш-таблицами.

У этого алгоритма есть преимущество в том, что он никогда не будет исследовать узлы которые могут быть отсечены альфа-бетой, однако некоторые ветки могут быть рассмотрены несколько раз.

Алгоритм NegaScout проверяет первый узел с полным окном (Alpha,Beta), считая этот вариант наилучшим. Следующие узлы он пытается отсечь перебором с нулевым окном, т.е. окном (Alpha , Alpha+1). Если результат счета улучшает альфа, то это означает что 1 узел не был лучшим, а этот узел нужно проверить с полным окном, однако вместо Alpha мы может взять полученное значение (Value,Beta). Код этого метода приведен ниже:

public int NegaScout(Cell[,] CopyBoard, int Depth, int FinalDepth, int Alpha, int Beta, int PossibleMoves, bool IsMy)

int Value = 0, MaxValue = -1000, leight = 0;

Cell[,] Board = new Cell;

Point[,] Moves = new Point;

Point Move = new Point;

FindMoves(Moves, ref leight, Board, true, true);

PossibleMoves = leight;

FindMoves(Moves, ref leight, Board, false, true);

PossibleMoves += leight;

if ((Depth == FinalDepth) || GameIsOver(Board, IsMy))

return Eval(Board, PossibleMoves);

return -1 * Eval(Board, PossibleMoves);

FindMoves(Moves, ref leight, Board, HaveRequiredMove(Board, IsMy), IsMy);

int a = Alpha, b = Beta;

for (int i = 0; i < leight; i++)

CopyMove(Move, Moves, i);

DoMove(Board, Move);

Value = -1 * NegaScout(Board, Depth + 1, FinalDepth, -1*b, -1 * a, PossibleMoves, !IsMy);

if (Value>a && Value0 && (Depth

a = -1 * NegaScout(Board, Depth + 1, FinalDepth, -1 * Beta, -1 * Value, PossibleMoves, !IsMy);

if (Value > a)

CopyPosition(Board, CopyBoard);

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

3 .5 Хеш-таблицы

3 .5 .1 Теория

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

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

Программа, использующая итеративное углубление и хэш-таблицы, часто выполняет все итерации от 1 до N в несколько раз быстрее, чем если бы она сразу начала итерацию N, т.к. с вероятностью 75% она всегда первым выбирает наилучший ход, а с вероятностью ~90% наилучший ход оказывается в числе первых трёх рассмотренных.

3 . 5 .2 Реализация

Хеширование является одним из самых мощных способов повышения производительности компьютера. Использование хеш таблиц является основным инструментом в программирование шахматных игр.

Хеш таблица - представляет из себя большую индексированную таблицу, в ячейках которых храниться следующая информация:

· 2 хеш индекса

· глубина просчета для этого хода

· оценка этого хода

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

Индекс должен наиболее отражать уникальную информации о ходе, чтобы максимально сократить количество коллизий

Хеш индекс должен быть простым для подсчета

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

Для подсчета индекса, была выбрана операции с некоторыми, случайно сгенерированными масками.

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

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

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

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

3.6 Использование библиотек дебютов

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

3 .7 Оценка позиции

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

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

Качество оценки определяется объемом знаний об игре, на основе которых позиции сопоставляется число. Добротность оценки прямо пропорциональна скорости работы и объему знаний. Как показывает 40-летняя практика создания программ с искусственным интеллектом, объем знаний оценочной функции обратно пропорционален её скорости.

Графически эта зависимость изображена на рисунке в виде семейства гипербол.

Рисунок 12 - Пример углубленного отсечения

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

Шахматны принято разделять на этапа: дебют - открытие партии, миттельшпиль - середина игры, эндшпиль - заключительная стадия. Для алгоритма решено разделить партии на 3 этапа по количеству фигур, оставшихся на доске у компьютерного игрока. Изначально на доске по 16 фигур у игроков. В таблице представлена зависимость этапа игры от количества оставшихся фигур:

Таблица 1 - Этапы игры

3 . 7 .1 Материальная оценка

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

3 . 7 . 2 Описание работы генетического алгоритма

Исходная задача кодируется таким образом, чтобы её решение могло быть представлено в виде вектора («хромосома»). Случайным образом создаётся некоторое количество начальных векторов («начальная популяция»). Они оцениваются с использованием «функции приспособленности», в результате чего каждому вектору присваивается определённое значение («приспособленность»), которое определяет вероятность выживания организма, представленного данным вектором.

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

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

Нахождение оптимального решения;

Исчерпание числа поколений, отпущенных на эволюцию;

Исчерпание времени, отпущенного на эволюцию .

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

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

Рисунок 13 - Пример углубленного отсечения

3 . 7 . 3 Этапы работы генетического алгоритма

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

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

Мутации - стохастическое изменение части особей (хромосом).

3 . 7 . 4 Определение весов фигур с помощью генетического алгоритма

В состав хромосомы генетического алгоритма входят веса шахматных фигур, за исключением короля.

Для задания начальной популяции значения хромосом задаются случайным образом в интервале , кроме весов пешки и ферзя, значения их весов фиксируются, пешка - 100, ферзь - 1000.

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

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

Берется случайным образом 2 родителя, выбирается случайно число, по которой хромосома разделится, схема показана на рисунке №14. В результате у каждого потомка будут черты как от первого так и от второго родителя.

Рисунок 14 - Пример углубленного отсечения

Мутации выполняется следующим образом: выбираются с некоторой вероятностью хромосомы, и у них, каждый «ген» меняется на случайное число в диапазоне [-50; 50], кроме значения статических оценок ферзя и пешки.

Для финальных значений полученные веса делятся на 100.

3 . 7 . 5 Суммарная оценка

При оценке позиции обращается внимание на 8 составляющих:

1. Материальные силы соперников

2. Количество полей под боем

3. Занятие ключевых полей

4. Проходные пешки

5. Сдвоенные пешки

6. Рокировка

7. Продвижение пешки

8. Пешечные цепи [*1]

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

Рисунок 15 - Ключевые поля

За занятие каждого из них даются дополнительные 4 очка.

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

Чем ближе пешка к последней для нее горизонтали, тем она ближе к превращению. За каждую пройденную вперед клетку к ценности пешки прибавляется 1.

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

4 . Разработка программ ы

4 .1 Требования к шахматному алгоритму

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

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

* модули программного обеспечения должны быть легкими в разработке и тестировании

* пользовательский интерфейс должен быть легким, легко настраиваемым и масштабируемым

4 .2 Виды шахматных алгоритмов

Большую часть современных программ можно разбить на 3 категории:

* Первая категория Fast searchers - идея состоит в том, что, упростив до предела оценочную функцию, и тщательно с оптимизировав всю программу в целом (что обычно достигается путём написания программы на ассемблере), можно довести количество позиций, рассматриваемых программой (nps - nodes per second) до астрономического числа, например, до 150-200k nps на P/200. То есть на каждую позицию программа тратит порядка одной-двух тысяч машинных команд. В это число входит делание хода из предыдущей позиции в эту, оценка позиции, генерация ходов из данной позиции, управляющая логика и т.д. На собственно оценочную функцию остаются вообще крохи - порядка сотни команд. Программы получаются безумно быстрыми и превосходно ведут себя в сложных тактических позициях, а также отлично решают комбинационные задачи, но имеют слабую позиционную игру

* Вторая категоря - knowledge-based программы. Тут все силы брошены на написание сложной оценочной функции. Учитывается и взаимодействие фигур друг с другом, и прикрытость короля, и контроль позиций, и чуть ли не фаза луны. В терминах nps программа работает в 10-100 раз медленнее, чем fast searches, но играет в хорошие позиционные шахматы. Точнее, хорошими эти шахматы являются только тогда, когда на доске нет глубокой тактики, или же контроль времени таков, что у программы есть достаточно времени, чтобы эту тактику просчитать.

4 .3 Контроль времени в шахматных алгоритмах

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

При расчете времени доступного на ход, надо исходить из двух параметров:

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

* время ожидание ответа компьютерного оппонента не должно быть слишком большим. За основу можно взять международные правила шахмат, в которых есть несколько видов партий: блиц - 15 минут на партия, быстрые - 60 минут на партию, классические - больше 60 минут на партию.

Исходя из требуемых параметров, решено время доступное для ходы перед началом каждого хода компьютера вычислять по следующей формуле:где: time - время на ход; full_game_time - общее время партии; avg_moves - среднее количество ходов игрока в партии; collect_time - дополнительно накопленное время; Д - небольшое сокращение времени, требуемое на дополнительные расчеты. Параметры общего времени партии и среднее количество ходов игрока в партии - два основных внешних параметры, изменяя которые можно менять силу игры. По статистике шахматного портала TheChess.ru, среднее количество ходов игроков за партию равно 30, по этому решено взять среднее количество ходов игрока в партии равному 30. Таким образом, из вне задается общее время партии. При разработке алгоритма поведения компьютерного оппонента (искусственного интеллекта) были использованы следующие алгоритмы:

* алгоритм итеративного поиска, с контролем времени

* алгоритм alpha-beta отсечения и Nega-Scout

* библиотеки дебютов

* хеш-таблицы

* для сортировке ходов использовались эвристики убийцы и истории.

4 .4 Разработанная программа

В программе на языке программирования С# были реализованы все вышеперечисленные алгоритмы и дополнения.

Скриншоты программы приведены ниже:

Рисунок 16- Выбор цвета

Рисунок 17 - Скриншот программы

Рисунок 18 - Скриншот программы

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

Во время игры совершенные ходы выводятся в табличке слева, так же игрок может сохранить историю в отдельный файл.

4 .5 Базовый цикл поиска лучшего хода

Главной задачей базового цикла поиска лучшего хода является нахождение и выполнение наилучшего хода компьютерного оппонента. Цикл использует библиотеки дебюта и итеративный поиск с контролем времени. На рисунке 12 представлен процесс поиска лучшего хода:

Рисунок 19 - Базовый цикл поиска лучшего хода

4 .6 Поиск лучшего хода первого уровня

Главной задачей работы алгоритма поиска лучшего хода первого уровня (ответа противника) является нахождение наилучшего хода оппонента на первом уровне. Алгоритм построен на алгоритма NegaScout, использующий оценивание в глубину, для определения оценки текущего хода. На рисунке 13 представлен процесс работы алгоритма:

Рисунок 20 - Поиск лучшего хода первого уровня

4 .7 Нахождение глубинной оценки хода

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

Рисунок 21 - Нахождение глубинной оценки хода

4.8 Прочие модели и диаграммы

Математическая модель программы выглядит следующим образом:

Рисунок 22 - Математическая модель

От абстрактного класса Figure сосздаются 7 классов наследников, описывающих действия и свойства фигур. Так же есть класс Еmpty, обозначающий что клетка пуста. Доска представляет собой массив из 64 элементов Figure, каждый из которых может становиться любым из классов-наследников. Ход в компьютере представляется в виде 4 цифр - координат (от 1 до 8) точки начала хода и координат точки конца хода. Ниже приведена диаграмма состояний для программы:

Рисунок 23 - Диаграмма состояний

5 . Экспериментальная оценка качества р еализов анных алгоритмов

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

5 .1 Оценка работы Альфа-Бета отсечения

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

Для оценки качества итогового алгоритма, экспериментально сравнивался данный алгоритм поиска с поиском по принципу минимакса.

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

Таблица 1 - Сравнение показателей алгоритма альфа-бета отсечения с алгоритмом минимакса.

Результаты экспериментов показывают, что альфа-бета отсечение намного лучше простого минимакс поиска.

5 .2 Оценка работы итерационного погружения и сортировки ходов

Для оценки качества алгоритма, экспериментально сравнивался данный алгоритм поиска с Альфа-Бета отсечением и просто Альфа-Бета отсечение.

Подобные документы

Описание правил игры "Морской бой". Особенности современных компьютеров и искусственного интеллекта. Создание общей блок-схемы программы, ее внешний вид. Необходимые переменные, процедуры и функции. Характеристика объектов, используемых в приложении.

курсовая работа , добавлен 05.11.2012


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

дипломная работа , добавлен 21.07.2013


Структурная диаграмма программного модуля. Разработка схемы программного модуля и пользовательского интерфейса. Реализация программного модуля: код программы; описание использованных операторов и функций. Вид пользовательской формы с заполненной матрицей.

курсовая работа , добавлен 01.09.2010


Исследование общих правил игры в шашки, инструкции пользователя и программиста. Характеристика основных алгоритмов, исполняющих задачи класса Life Widget. Оценка ходов компьютера и человека. Построение дерева поиска лучшего хода исходя из оценки функций.

контрольная работа , добавлен 20.12.2012


Основные стадии разработки, принципы тестирования и отладка программного модуля "VFS". Особенности проектирования на языке UML. Методы "грубой силы" и их применение при отладке программы. Вредные факторы, присутствующие на рабочем месте программиста.

дипломная работа , добавлен 07.03.2012


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

дипломная работа , добавлен 12.08.2017


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

контрольная работа , добавлен 07.12.2009


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

курсовая работа , добавлен 26.03.2009


Построение и анализ математической модели игры. Определение вероятности обнаружения кораблей при всевозможном их расположении и различных системах поиска. Разработка алгоритмов для работы искусственного интеллекта. Структура программы и ее компоненты.

курсовая работа , добавлен 22.12.2012


Понятие искусственного интеллекта как свойства автоматических систем брать на себя отдельные функции интеллекта человека. Экспертные системы в области медицины. Различные подходы к построению систем искусственного интеллекта. Создание нейронных сетей.