Игры, в которые играют машины: о шахматных программах

В чем сходство компьютера и дрозофилы, что сложнее: го или шахматы, как Каспаров готовился к матчу с компьютером, в преддверии решающей партии между Сергеем Карякиным и Магнусом Карлсеном за звание чемпиона мира по шахматам выяснял Indicator.Ru.

Последние несколько недель большинство россиян с ажиотажем следит за событиями в мире спорта. Столь сильная волна спортивного азарта накрывает обычно либо в период проведения Олимпийских игр, либо Чемпионатов мира и Европы по футболу или Кубка мира по биатлону. На этот раз всеобщее внимание заслужило мировое первенство по шахматам. В поединке сошлись россиянин Сергей Карякин — претендент на звание чемпиона мира — и норвежец Магнус Карлсен, защищающий свой титул. Пока у игроков равное количество очков. Сегодня в 22 часа по московскому времени (игра состоится в Нью-Йорке) в тай-брейке определится лучший среди шахматистов.

Дрозофилы и С++

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

В Советском Союзе в начале 1960-х годов первую работу по созданию шахматной программы возглавлял математик Александр Кронрод. Позже он назвал компьютерные шахматы «дрозофилой искусственного интеллекта», подразумевая то, что эта игра как нельзя лучше походит для исследования машинного разума. Разработчикам компьютерных шахмат необходимо расписать все возможные «узлы», или, иначе, построить «деревья» шахматных ходов. Также требуется отдельно оценить позиции разных фигур, учесть дебюты и эндшпили, для которых создаются специальные базы данных. По мнению Сергея Маркова, разработчика программы SmartThink, самое сложное для шахматного программиста кроется в «отладке кода, так как современный шахматный движок – это десятки тысяч строк (в случае SmartThink чуть больше 40000), при этом в большинстве случаев при разработке используются такие языки как C и C++, часто со вставками на Assembler в борьбе за скорость работы».

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

Я хочу сыграть с тобой в игру

Немного освоившись в игре, ученик стал стремительно превосходить учителя, творенье – своего творца. Тогда человека охватил настоящий азарт: в 1968 году британский шахматист Дэвид Леви решил поспорить, что ни один компьютер не сможет его обыграть. Долгое время Леви действительно удавалось выходить победителем, но только до тех пор, пока в конце 1989 году он не проиграл DeepThought. Одолеть компьютер не всегда могли и всемирно известные гроссмейстеры. В начале 1990-х годов прошла серия блицев между человеком и компьютером. Тогда машинный интеллект по очереди выиграл у Гарри Каспарова, Бориса Гельфанда, Владимира Крамника. Позднее, в 1996 году, Каспарову ненадолго удалось взять реванш на турнире с мощнейшим суперкомпьютером DeepBlue (потомка того самого DeepThought), чтобы уже в следующем году уступить машине победу. Кстати, ради той игры компания IBM пошла на создание нового многопроцессорного компьютера. Проигрыш машине под конец тысячелетия тогда стал одним из символов наступления новой эры. В XXI веке практически все известные шахматные схватки между человеческим разумом и машинным, например, Крамник – DeepFritz, Каспаров – Junior, заканчиваются в лучшем случае ничьей.

Шай Бушинский из Хайфского университета, один из создателей шахматной программы Junior, рассказал корреспонденту Indicator.Ru, почему в 2003 году компьютер не смог победить Каспарова. «В самом начале матча у Каспарова были серьезные преимущества. После того самого случая с DeepBlue он долго и хорошо готовился, изучал игры Junior против гроссмейстеров и, что, возможно, самое важное, у него была предыдущая версия нашей программы и он мог играть, когда хотел. Он отлично усвоил, как начинать игру белыми. Я помню, как он мне рассказывал после матча, что знает Junior даже лучше, чем мы», – сообщил Бушинский.

ГОнка продолжается

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

Часто в качестве причины долгого отставания искусственного интеллекта от человека при игре в го называют то, что игра обладает большей комбинаторной сложностью (число возможных ходов в среднестатистической позиции в го больше, чем в шахматах). В го примерно 10¹⁷⁰ позиций и примерно 3³⁶¹ возможных партий (для стандартной доски 19х19 — прим. Indicator.Ru). В шахматах эти показатели, согласно американскому математику Клоду Шеннону, составляют примерно 10⁴³ и 10¹²⁰ соответственно. Но ведь эта сложность встает перед любым игроком в го, и перед человеком, в том числе. Почему же люди играли в го лучше? Думаю, что дело здесь в том, что для го сложнее придумать функцию для промежуточной оценки положения на доске – для правильной оценки позиции здесь нужно находить на доске сложные паттерны, в то время как в шахматах оценки материала, мобильности фигур, элементов пешечной структуры и атаки на короля обычно достаточно для того, чтобы оценить положение на доске. Неслучайно прогресс искусственного интеллекта при игре в го был связан с развитием сверхточных нейронных сетей, использование которых позволило значительно улучшить качество распознавания визуальных образов», – заключает Марков.

В марте этого года стало известно, что программа AlphaGo смогла обойти корейца Ли Седоля (9 профессиональный дан) со счетом по партиям 1-4.

Сможет или нет машина подтвердить свое преимущество перед человеком в интеллектуальных играх, покажет время. Так или иначе, но матчи все равно разыгрываются между людьми. Разработчики компьютерных шахмат не намерены сдаваться. «После игры 2003 года с Каспаровым мы решили немного улучшить программу, однако в следующем году Junior проиграла Сергею Карякину. Но с того момента наша программа всегда одерживала победы, и я думаю, она способна выиграть у любого человека», – считает Шай Бушинский.