Учебный проект шахматы и искусственный интеллект. На пути к Deep Blue: пошаговое руководство по созданию простого ИИ для игры в шахматы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• перемещение;
• оценка шахматной доски;
• минимакс;
• альфа-бета-отсечение.

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

Готовый алгоритм можно найти на 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. Улучшенная функция оценки

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

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

Stockfish, который используют для домашней подготовки большинство игроков, победитель Чемпионата TCEC 2016 года и Чемпионата Chess.com среди компьютерных программ 2017 года, оказался явно слабее. В матче из 100 партий AlphaZero одержал 28 побед при 72 ничьих и ни разу не проиграл.

Кстати, AlphaZero потратил всего четыре часа на «изучение» шахмат. Простите, человеки, но вам за ним не угнаться.

Все верно - программисты AlphaZero, разрабатываемого DeepMind, подразделением Google, создали его на основе механизма «машинного обучения», точнее, «обучения с подкреплением». Проще говоря, AlphaZero не изучал шахматы в традиционном понимании. У него нет ни дебютной книги, ни эндшпильных таблиц, ни сложных алгоритмов для оценки силы центральных и фланговых пешек.

Его работу можно сравнить с роботом, который может использовать тысячи запчастей, но не знает принципа работы двигателя внутреннего сгорания, - он перебирает возможные комбинации, пока не построит Феррари, и для этого ему нужно меньше времени, чем занимает просмотр трилогии «Властелин колец». За четыре часа программа сыграла сама с собой множество партий, став своим собственным учителем.

Пока что команда программистов хранит молчание. Они не дали Chess.com комментариев, ссылаясь на то, что доклад «пока находится на рассмотрении», но здесь вы можете прочесть его полный текст. В исследовательскую группу входит Демис Хассабис, кандидат в мастера из Англии и соучредитель DeepMind (приобретен Google в 2014). Хассабис, принимавший участие в турнире тандемов ProBiz на открытии London Chess Classic, в настоящий момент находится на конференции Neural Information Processing Systems (Нейронные системы обработки информации) в Калифорнии, в качестве соавтора доклада на другую тему.

Зато с Chess.com охотно поделился своими суждениями шахматист, обладающий большим личным опытом игры против шахматных компьютеров. МГ Гарри Каспаров не удивлен, что компания DeepMind перешла от го к шахматам.

«Это заметное достижение, хотя оно и было ожидаемо после AlphaGo», - заявил он Chess.com. «Оно приближается к "типу-Б", человекоподобному подходу к шахматам, которым Клон Шеннон и Алан Тьюринг мечтали заменить сплошной перебор».

Подобно человеку, AlphaZero рассматривает меньше позиций, чем ее предшественницы. В отчете заявлено, что она оценивает «всего» 80 тысяч позиций в секунду в сравнении с 70 миллионами в секунду у Stockfish.

МГ Петер-Хайне Нильсен, многолетний секундант чемпиона мира МГ Магнуса Карлсена, открыл свое увлечение, сближающее его с президентом ФИДЕ: инопланетян. Он заявил Chess.com: «Прочитав доклад и, в особенности, просмотрев партии, я подумал: „Мне всегда было любопытно, что было бы, если бы более разумный вид высадился на нашей планете и показал нам свое искусство шахматной игры. Кажется, теперь я знаю, каково это“.

Мы также узнали, о значимости преимущества выступки, по крайней мере, для искусственного интеллекта. 25 из 28 побед AlphaZero одержал белыми (хотя результат +3=47-0 черными против Stockfish, чей рейтинг превышает 3400, также неплох).

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

Что бы вы сделали на месте не ведающего усталости существа, только что освоившего игру с 1400-летней историей? Взялись бы за другую. После матча со Stockfish программа AlphaZero потратила на „обучение“ всего два часа и победила „Elmo“, сильнейшего из компьютерных движков для игры в сёги.

Применение этой инновационной самообучающейся программы, разумеется, не ограничено играми.

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

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

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

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

«Я уверен, что сам Господь бог не набрал бы против Stockfish 75 процентов очков белыми без какой-либо форы», - прокомментировал он результат AlphaZero белыми: 25 побед и 25 ничьих.

МГ Ларри Кауфман, ведущий шахматный консультант движка Komodo, надеется увидеть, насколько хорошо работает новая программа на персональных компьютерах, не пользуясь вычислительными мощностями Google. Он также повторил высказанные Накамурой возражения по поводу того, что Stockfish играл без своих обычных дебютных знаний.

«Конечно, это почти невероятно», сказал он, - «да, я слышал о достижениях AlphaGo Zero в игре го и ожидал, что произойдет что-то подобное, учитывая, что в команде разработчиков есть шахматист Демис Хассабис. Однако, непонятно, сможет ли программа AlphaZero играть в шахматы на обычном компьютере, и насколько хорошо у нее это получится. Возможно, современное преобладание шахматных движков, использующих минимаксную функцию, близится к концу, но пока провозглашать это слишком рано. Стоит указать, что за время обучения AlphaZero де-факто создала собственную дебютную книгу, поэтому было бы справедливее использовать ее против движка с хорошей дебютной книгой».

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

"[Это] современный искусственный интеллект", - сказал гроссмейстер. «Он идет от чего-то вроде шахмат к проблемам, достойным нобелевских премий и даже большего. Думаю, нам повезло, что они решили потратить четыре часа на шахматы, но последствия этого открытия куда более значительны».

Разработанной инженерами Массачусетского технологического института. Фишер трижды поставил мат компьютеру и одержал безоговорочную победу. В своих письмах шахматист писал, что программы допускают «грубые ошибки», а сами компьютеры называл «бесполезными кусками железа».

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

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

Бобби Фишер после победы над компьютером. Фото: Getty Images

Похоже, что люди питают какую-то врожденную любовь к интеллектуальным играм. Когда в 1649 году короля Англии Карла I приговорили к смерти, он взял с собой на казнь две вещи - библию и набор шахмат. Известный художник XX века Марсель Дюшан на пике своей карьеры внезапно уехал в Аргентину и начал заниматься вырезанием шахматных фигур из дерева, да и в целом увлекся шахматами. В XIX веке в Японии произошла загадочная история, связанная с игрой го. По легенде духи подсказали одному знаменитому игроку три блестящих хода. В результате он смог победить, а его противник после партии упал на пол, захлебнулся кровью и умер.

Компьютеры далеки от всей этой мистики, но всего за пару десятков лет они изучили интеллектуальные игры глубже, чем человечество за тысячелетия. В 2014 году компания приобрела фирму DeepMind за $400 миллионов для «проведения самого необычного и сложного исследования, конечной целью которого является разгадка сущности интеллекта». В частности ученые хотели научить компьютер играть в го. Эта игра значительно сложнее шахмат. В 1985 году один тайваньский промышленный магнат сказал, что заплатит $1,4 миллиона за программу, которая сможет победить лучшего игрока в го. В 1997 году магнат умер, а спустя три года у его предложения истек срок действия - никто так и не смог забрать приз.

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

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

Что касается шахмат, то человечество потеряло пальму первенства в них еще за 20 лет до этих событий, когда шахматист Гарри Каспаров проиграл суперкомпьютеру IBM Deep Blue. Шахматы и го - не единственные игры, которым пытаются обучить ИИ. Компьютер пробовали научить шашкам , коротким нардам , реверси , покеру и многим другим настольным играм. И человеческий интеллект уже не может сравниться в них с искусственным. Отчасти это произошло из-за развития технологий. Например, еще в 1997 году компьютер Deep Blue занимал 259-е место в списке самых быстрых суперкомпьютеров в мире и мог выполнять около 11 миллиардов операций в секунду. Сейчас же благодаря современным алгоритмам даже ваш смартфон способен победить Каспарова.

Гарри Каспаров против компьютера Deep Blue. Слева один из инженеров IBM Сюн Фэйсюн. Фото: Getty Images

Такие достижения ИИ вызвали у людей вполне человеческие эмоции: печаль, угнетенность и отчаяние. После того как Ли Седоль потерпел поражение от AlphaGo, он пережил экзистенциальный кризис. «Я усомнился в человеческой изобретательности, - признался он после матча. - Я засомневался, являются ли все ходы в го, которые я знаю, правильными». По словам одного из очевидцев, после поражения Ли выглядел так, будто бы ему было «физически плохо». Каспаров чувствовал себя после проигрыша компьютеру не лучше. Когда он вернулся в отель, он просто разделся, лег в постель и смотрел в потолок.

«Компьютер настолько глубоко анализирует некоторые позиции, что играет, как бог», - сказал Каспаров.

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

Фото из открытых источников

Новый искусственный интеллект всего за 4 часа обучения стал лучшим шахматистом на Земле! (сайт)

А помните, какой фурор наделал в 1996 году шахматный суперкомпьютер «Deep Blue», выиграв первую партию у российского чемпиона Гарри Каспарова? Несмотря на то, что наш соотечественник все же одержал победу в этой игре, уже тогда стало понятно, что искусственный интеллект стремительно прогрессирует и когда-нибудь обаятельно станет наилучшим шахматистом, после чего людям будет бесполезно играть с программой. Оставался лишь вопрос, когда это произойдет.

Представители известной корпорации «Google» заявили, что это время, наконец-то, настало. По словам специалистов, разработанная ими нейросеть «AlphaZero» всего за 4 часа самообучения превратилась в самого виртуозного и безупречного шахматного игрока за всю историю этой игры. Сверхмощный искусственный интеллект обучался игре в шахматы, зная только ее правила. Поиграв 4 часа с самим собой, робот научился идеально играть, без труда победив шахматную программу «Stockfish», считавшуюся до этого самой совершенной. Компьютеры провели 100 партий - «AlphaZero» удалось выиграть 28 из них и свести вничью оставшиеся 72. Передовая нейросеть, имитирующая работу человеческого мозга, способна рисковать и даже использовать своеобразное подобие интуиции.

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

Более ранние модели «AlphaZero» обучались игре, следя за живыми шахматистами. Разработчики предполагали, что это поможет искусственному интеллекту лучше понять стратегии игры. На самом же деле оказалось, что наблюдение за людьми только замедляет развитие программы. Когда нейросеть предоставили самой себе, ее способности взлетели до небес. Теперь инженеры «Google» думают над тем, как применить подобные технологии для реальной пользы человечеству, поскольку шахматная игра, даже самая виртуозная, не имеет прикладной цели.

В 1968 году известный Дэйвид Леви заключил пари, что в течение ближайшего десятилетия его не обыграет ни одна программа. Все это время гроссмейстер постоянно состязался с различные шахматными компьютерами и всякий раз выигрывал у них. В 1978 году он одержал победу над сильнейшей в то время программой «Chess 4.7», выиграв пари. К несчастью, в наши дни столь интересных поединков уже не будет - нам предстоит теперь узнавать только о том, как одна фантастическая нейросеть победила другую. Живые шахматисты о победе над такими монстрами не могут уже даже мечтать. И это только начало подобных побед ИИ над человеком…