Учебный проект шахматы и искусственный интеллект. Развитие искусственного интеллекта в шахматных программах. шахматный компьютерный интеллект алгоритм
Фото из открытых источников
Новый искусственный интеллект всего за 4 часа обучения стал лучшим шахматистом на Земле! (сайт)
А помните, какой фурор наделал в 1996 году шахматный суперкомпьютер «Deep Blue», выиграв первую партию у российского чемпиона Гарри Каспарова? Несмотря на то, что наш соотечественник все же одержал победу в этой игре, уже тогда стало понятно, что искусственный интеллект стремительно прогрессирует и когда-нибудь обаятельно станет наилучшим шахматистом, после чего людям будет бесполезно играть с программой. Оставался лишь вопрос, когда это произойдет.
Представители известной корпорации «Google» заявили, что это время, наконец-то, настало. По словам специалистов, разработанная ими нейросеть «AlphaZero» всего за 4 часа самообучения превратилась в самого виртуозного и безупречного шахматного игрока за всю историю этой игры. Сверхмощный искусственный интеллект обучался игре в шахматы, зная только ее правила. Поиграв 4 часа с самим собой, робот научился идеально играть, без труда победив шахматную программу «Stockfish», считавшуюся до этого самой совершенной. Компьютеры провели 100 партий - «AlphaZero» удалось выиграть 28 из них и свести вничью оставшиеся 72. Передовая нейросеть, имитирующая работу человеческого мозга, способна рисковать и даже использовать своеобразное подобие интуиции.
Мечтать о победе над искусственным интеллектом уже не приходится
Более ранние модели «AlphaZero» обучались игре, следя за живыми шахматистами. Разработчики предполагали, что это поможет искусственному интеллекту лучше понять стратегии игры. На самом же деле оказалось, что наблюдение за людьми только замедляет развитие программы. Когда нейросеть предоставили самой себе, ее способности взлетели до небес. Теперь инженеры «Google» думают над тем, как применить подобные технологии для реальной пользы человечеству, поскольку шахматная игра, даже самая виртуозная, не имеет прикладной цели.
В 1968 году известный Дэйвид Леви заключил пари, что в течение ближайшего десятилетия его не обыграет ни одна программа. Все это время гроссмейстер постоянно состязался с различные шахматными компьютерами и всякий раз выигрывал у них. В 1978 году он одержал победу над сильнейшей в то время программой «Chess 4.7», выиграв пари. К несчастью, в наши дни столь интересных поединков уже не будет - нам предстоит теперь узнавать только о том, как одна фантастическая нейросеть победила другую. Живые шахматисты о победе над такими монстрами не могут уже даже мечтать. И это только начало подобных побед ИИ над человеком…
Гришанин Е.А. Дурин С.В. Содержание 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
Думаю, не будут излишними некоторые объяснения насчет кода:
- 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. " (примечание: для тех, кто считает, что данная цитата принадлежит Кнуту, есть интересные дискусии
Матч проигран: компьютер против человека.
Креативное мышление, логика, опыт – качества, которые позволяли человеку лидировать в схватке «человек-машина». Казалось, эти преимущества всегда будут секретным оружием человека, и компьютер будет выполнять роль «догоняющего».
Но потребовалось совсем немного времени, чтобы искусственный интеллект догнал и навсегда превзошел человека во многих сферах, в том числе и в сфере интеллектуальных развлечений.
Искусственный интеллект обыграл человека: где и как
Кубик Рубика
Эта головоломка известна по всему миру. Миллионы людей стараются выполнить задание и собрать правильно кубик, а некоторые даже соревнуются в скорости сборки. Рекорд среди людей показал 14-летний Лукас Эттер из США, который разбирается с головоломкой за 4,904 секунды. Невероятно, не правда ли? Но этот результат удалось превзойти роботу, который создали два энтузиаста Джей Флэтлэнд и Пол Роуз: результат робота 1,047 сек.
Благодаря встроенным камерам, а их четыре, компьютер оценивает положение, и подбирает лучший алгоритм действий. В основе системы лежит формула Коцебы (сборка за 20 ходов). Едва ли кто-то из людей сможет собрать кубик Рубика быстрее, чем за 1 секунду.
0:1 в пользу искусственного разума.
«Отелло»
Пик популярности этой игры приходится на начало 70-х годов прошлого века. Суть игры заключается в размещении на игровом поле (8×8 клеток) фишек: необходимо фишками своего цвета перекрыть с двух сторон ряды фишек соперника, тогда фишки меняют цвет и переходят к оппоненту. Победа достается тому, кто занял большую площадь.
В 1980 году чемпионом мира по «Отелло» был Хироси Иноуе, и он с легкостью победил программу Moor со счетом 5:1.
Позже программы научились просчитывать ходы соперника (примерно на 25 ходов), и когда в 1997 году действующий чемпион мира Такеси Мураками сошелся в матче-реванше с системой Logistello, счет был сокрушительным 0:6 в пользу ПО.
Нарды
Своему преимуществу в нардах над человеком искусственный интеллект обязан чемпиону мира по шахматам по переписке (и такие есть) Хансу Берлинеру, который написал программу BKG 9.8. И в 1979 году программа оказалась сильнее чемпиона мира по игре в нарды Луиджи Виллу.
Считается, что в той партии компьютеру повезло (несколько раз выпадали хорошие кости), однако сразиться в повторном матче-реванше так никто больше не захотел, тем более что с того времени ПО было неоднократно усовершенствовано.
Шахматы
Шахматные системы начали разрабатывать еще в середине ХХ века, разработки принадлежали компании IBM. Но из-за того, что программа требовала серьезных и длительных расчетов эту затею пришлось отложить на 30 лет. В 1996 году против Гарри Каспарова был выставлен «шахматный мозг» — компьютер Deep Blue.
Матч закончился в пользу человека: 3 победы, 2 ничьи, 1 проигрыш. Спустя год матч повторили, и в этот раз Deep Blue оказался более подготовленным. Еще бы, система оценивала 200 млн. позиций в секунду. И хотя Гарри хотел позже отыграться, в IBM отказались, считая это бессмысленным.
Чекерс (разновидность шашек)
Марион Тинсли был чемпионом чекерс на протяжении всей карьеры. И когда в 1992 году он встретился с системой, разработанной в Альбертском университете (Канада), победа осталась за ним. Из 39 партий — 4 победы, 2 проигрыша и 33 ничьи.
Спустя 2 года состоялся реванш, но Тинсли снялся с соревнования из-за проблем со здоровьем (на момент отказа было 6 ничейных партий), и победа досталась системе. С того момента, искусственный интеллект стал намного сильнее: в 2007 году канадцы объявили о создании идеальной системы, и уже никто из людей не пытается превзойти его в чекерс.
Скрэббл
Триумф компьютеру в этой игре дался легко и в первом же туре: чемпион мира Дэвид Бойс был обыгран в 2006 году робо-соперником Quackle.
Кстати, эта программа доступна в Сети, и вы можете с ней помериться силами, и может вы принесете победу команде «Человек».
Го
Эта игра появилась в Древнем Китае больше двух тысяч лет назад, но, несмотря на такой продолжительный опыт в игре, человек все равно уступил. На площадке (19×19) два игрока располагают свои камни (черные/белые), кто наберет больше очков (считаются фишки составленные в линию), тот и победил. С одной стороны все просто, но интерес кроется в многообразии возможных вариантов и ходов.
Интересно было и разработчикам AlphaGo (создавалась под эгидой Google) — создать систему, которая способна просчитать тысячи вариантов. Сначала искусственный интеллект опробовал свои силы с другими ПО, и когда из 500 партий 499 были за AlphaGo, он взялся за трехкратного чемпиона Европы Фань Хуэя. У чемпиона не было шансов: 5:0.
TV
Любите отвечать на вопросы в телевикторинах? Разработчики робота Watson от компании IBM тоже не смогли удержаться, и в 2011 году Watson выступил в качестве участника интеллектуальной телевикторины «Jeopardy!». Несмотря на то, что его оппонентами были рекордсмены шоу — Брэд Руттер и Кен Дженнингс – победа досталась , а выигранный миллион долларов передан на благотворительность.
И хотя компьютер уже показал свое интеллектуальное и логическое превосходство над человеком, он продолжает развиваться. Так компания Alibaba Group и Microsoft (разработки велись параллельно) представили искусственный интеллект, который оказался сильнее человека в понимании прочитанной информации.
Тест Стэнфордского университета это больше 100 тысяч вопросов, которые основываются на пяти сотнях статей из библиотеки Википедии.
Лучший показатель у человека 82,304 балла, итог Alibaba – 82,44, нейронная сеть Microsoft – 82,605. результаты свидетельствуют о том, что искусственный разум способен с высокой точностью отвечать на любые вопросы, а значит, технологии могут быть использованы для обслуживания клиентов, пациентов, посетителей музеев и т.п.
Компьютерные игры также были покорены программой. Программа победила программу: кто бы мог подумать, что это будущее так близко? Популярная игра Quake III, где игроки – гладиаторы, очень популярна в киберспорте. Но лучшими здесь оказались не люди, а команда ботов DeepMind, созданная подразделением Google. И хотя бой проводился в урезанном варианте, по подсчетам с 73 % вариантностью бот победил бы в любом состязании.
Опасно или нет такое превосходство искусственного разума? Никто не может ответить точно. Да и в конечном счете не этот ответ будет ключевым, ведь главным остается не тот факт, что человек уступает компьютеру, а сможем ли мы использовать этот потенциал на собственное благо. Как мы видим искусственный интеллект обыгрывает человека и не оставляет никаких шансов на победу.
Рассмотрим некоторые базовые концепции, которые помогут нам создать простой искусственный интеллект, умеющий играть в шахматы:
- перемещение;
- оценка шахматной доски;
- минимакс;
- альфа-бета-отсечение.
На каждом шаге мы будем улучшать наш алгоритм с помощью одного из этих проверенных временем методов шахматного программирования. Вы увидите, как каждый из них влияет на стиль игры алгоритма.
Готовый алгоритм можно найти на GitHub .
Шаг 1. Генерация ходов и визуализация шахматной доски
Мы будем использовать библиотеки chess.js для генерации ходов и chessboard.js для визуализации доски. Библиотека для генерации ходов реализует все правила шахмат. Исходя из этого, мы можем рассчитать все ходы для данного состояния доски.
Визуализация функции генерации движения. Исходное положение используется как вход, а на выходе - все возможные ходы из этой позиции.
Использование этих библиотек поможет нам сосредоточиться только на самой интересной задаче - создании алгоритма, который находит лучший ход. Мы начнем с написания функции, которая возвращает случайный ход из всех возможных ходов:
Var calculateBestMove = function(game) { //Генерация всех ходов для данной позиции var newGameMoves = game.ugly_moves(); return newGameMoves; };
Хотя этот алгоритм не очень солидный шахматист, но это хорошая отправная точка, поскольку его уровня достаточно, чтобы сыграть с нами:
Черные играют случайными ходами
JSFiddle .
Шаг 2. Оценка доски
Теперь попробуем понять, какая из сторон сильнее в определенном положении. Самый простой способ добиться этого - посчитать относительную силу фигур на доске, используя следующую таблицу:
С помощью функции оценки мы можем создать алгоритм, который выбирает ход с наивысшей оценкой:
Var calculateBestMove = function (game) { var newGameMoves = game.ugly_moves(); var bestMove = null; //Используйте любое отрицательное число var bestValue = -9999; for (var i = 0; i < newGameMoves.length; i++) { var newGameMove = newGameMoves[i]; game.ugly_move(newGameMove); //Возьмите отрицательное число, поскольку ИИ играет черными var boardValue = -evaluateBoard(game.board()) game.undo(); if (boardValue > bestValue) { bestValue = boardValue; bestMove = newGameMove } } return bestMove; };
Единственным ощутимым улучшением является то, что теперь наш алгоритм съест фигуру, если это возможно:
Черные играют с помощью простой функции оценки
Посмотреть, что получилось на данном этапе, вы можете на JSFiddle .
Шаг 3. Дерево поиска и минимакс
Затем мы создадим дерево поиска, из которого алгоритм может выбрать лучший ход. Это делается с помощью алгоритма «минимакс».
Прим. перев. В одной из наших статей мы уже имели дело с - учились создавать ИИ, который невозможно обыграть в крестики-нолики.
В этом алгоритме рекурсивное дерево всех возможных ходов исследуется до заданной глубины, а позиция оценивается на «листьях» дерева.
После этого мы возвращаем либо наименьшее, либо наибольшее значение потомка в родительский узел, в зависимости от того, чей просчитывается ход (то есть мы стараемся минимизировать или максимизировать результат на каждом уровне).
Визуализация минимакса в искусственном положении. Лучший ход для белых - b2-c3, так мы можем гарантировать, что доберемся до позиции, где оценка равна -50
Var minimax = function (depth, game, isMaximisingPlayer) { if (depth === 0) { return -evaluateBoard(game.board()); } var newGameMoves = game.ugly_moves(); if (isMaximisingPlayer) { var bestMove = -9999; for (var i = 0; i < newGameMoves.length; i++) { game.ugly_move(newGameMoves[i]); bestMove = Math.max(bestMove, minimax(depth - 1, game, !isMaximisingPlayer)); game.undo(); } return bestMove; } else { var bestMove = 9999; for (var i = 0; i < newGameMoves.length; i++) { game.ugly_move(newGameMoves[i]); bestMove = Math.min(bestMove, minimax(depth - 1, game, !isMaximisingPlayer)); game.undo(); } return bestMove; } };
С минимаксом наш алгоритм начинает понимать основную тактику шахмат:
Минимакс с уровнем глубины 2
Посмотреть, что получилось на данном этапе, вы можете на JSFiddle .
Эффективность минимакса в значительной степени зависит от достижимой глубины поиска. Именно это мы улучшим на следующем шаге.
Шаг 4. Альфа-бета-отсечение
Позиции, которые нам не нужны, если используется альфа-бета-отсечение. Дерево посещается в описанном порядке.
С альфа-бета-отсечением мы получаем значительное улучшение минимакса, как показано в следующем примере:
Количество позиций, которые нужно оценить в случае поиска с глубиной 4 и начальной позицией, изображённой на картинке.
Посмотреть, что получилось на данном этапе, вы можете на JSFiddle .
Шаг 5. Улучшенная функция оценки
Первоначальная функция оценки довольно наивна, поскольку мы просто подсчитываем очки фигур, которые находятся на доске. Чтобы улучшить её, мы начнём учитывать положение фигур. Например, конь в центре доски «дороже», потому что он имеет больше доступных ходов и, следовательно, более активен, чем конь на краю доски.