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

grigorlukashenko

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

История развития автоматики и вычислительной техники странным образом связана с шахматами. В 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 лет, чтобы фактически чего-то добиться. Всякая философия основывается на мнениях. Каждый думает, что он прав, а может, каждый прав по-своему. Например, я всю жизнь имел дело с искусственным интеллектом и полагаю, что мозг человека не более чем большая вычислительная машина, следовательно, нельзя сказать, что принципиально невозможно создать аналогичную ей. Вопрос в ее мощности, скоростных характеристиках, в наполнении ее знаниями. Ничего непостижимого здесь нет. Это моя личная точка зрения. Но существуют и другие мнения. Конечно, если мы признаем божественную природу человека, то тогда уже надо выбрать один из двух гносеологических вариантов. Либо да, мы имеем божественную природу, но она познаваема. В таком случае нам не удастся воспроизвести по-настоящему то, что сумел сделать Господь Бог, но, по крайней мере, мы сможем Его творения хотя бы частично воссоздать. Либо же мы стоим на позиции агностицизма, и тогда она непознаваема, и вопрос полностью снимается. Выходит, что некоторые задачи человеческий мозг решает – и тут ни у кого сомнений нет. Но догнать мозг мы не можем, потому что, с одной стороны, он создан Богом, а с другой – познать его мы не в состоянии. Все три позиции связаны с верой, поскольку в реальности-то необязательно познавать все функции мозга. Если мы сделаем машину, по мощности равную мозгу, то ей ни к чему думать так, как мозг. Она по-другому будет работать.

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

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

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

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

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

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