Программа «Пионер». Часть II. Алгоритм Ботвинника.1958-1972
Продолжение. Начало статьи здесь
В 1972 году алгоритм Ботвинника лег в основу проекта «Пионер». Так началось воплощение мечты Михаила Моисеевича о создании электронного гроссмейстера.
В 1958 году чемпион мира по шахматам Михаил Ботвинник поставил перед собой фантастическую (если вспомнить возможности ЭВМ того времени) задачу: создать программу, которая бы играла в шахматы, как гроссмейстер, т.е. не перебирала бы все возможные ходы в позиции, а строила логичное для человека дерево вариантов, в котором, в то же время, не отброшены парадоксальные, сильные ходы. Как знать, возможно, он хотел таким образом обессмертить собственный алгоритм мышления… 14 лет ушло на формализацию задачи и ее описание на языке структурных схем. В 1972 году алгоритм Ботвинника стал основой для создания программы «Пионер».
Можно ли создать «электронного гроссмейстера»?
В ноябре 1960 года, по окончании шахматной Олимпиады в Лейпциге, Михаила Ботвинника попросили выступить в Берлинском университете имени Гумбольдта с лекцией. Тема ее была обозначена как машинная игра в шахматы. С момента телеинтервью в голландском Хильверсуме (о котором рассказано в части I данной статьи) прошло два года. Времени поразмышлять над темой «компьютерные шахматы» было достаточно. Ботвинник делился своими соображениями с друзьями, и потому приглашение из университета Гумбольдта его не удивило. Лекция прошла с большим успехом. Так начался реальный, зафиксированный в некоем манифесте, путь чемпиона мира к разработке программы «Пионер».
В январе 1961 года в сокращенном виде текст лекции был напечатан в газете «Комсомольская правда» под названием «Люди и машины за шахматной доской», затем уже в полном виде — в журнале «Шахматы в СССР», 1961, № 3. Статья была переведена на другие языки и не раз публиковалась за рубежом. Русскую версию можно найти в сборнике «Возможное и невозможное в кибернетике», 1963. По мнению Ботвинника (в книге [8], изданной в 1979 году, с. 151), основные положения статьи не потеряли актуальности и в последующие годы.
Текст статьи [5] можно разбить на две логические части. В первой М.М. Ботвинник рассматривает отношение людей к шахматной игре. Несмотря на то, что он всегда фундаментально, на научной основе подходил к подготовке к шахматным соревнованиям, Михаил Моисеевич отрицал, что шахматы являются наукой, поскольку наука обязательно должна изучать законы природы, общества или мышления, а шахматы – всего лишь исторически сложившаяся условная схема. В давние времена шахматы были только игрой, но постепенно стали появляться партии, от которых понимающая публика начала получать эстетическое наслаждение. Поэтому можно сказать, что шахматист играет в шахматы, но создает произведение искусства, если его партия живет долго. Т.е. шахматы всегда игра (слово «спорт» Ботвинник не употребляет), которая иногда становится искусством.
Во второй части Ботвинник рассматривает особенности мышления шахматного мастера за доской. Он утверждает, что из-за ограниченных возможностей техники практически невозможно создать «машину-сверхшахматиста», которая бы не ошибалась (т.е. умела находить лучший ход в любой позиции). Однако можно создать программу, моделирующую мышление сильного шахматиста. Пусть она тоже ошибается, «как простые смертные гроссмейстеры», но вычислений потребуется в миллионы раз меньше, и потому задача создания «электронного гроссмейстера» станет практически разрешимой даже при существующем уровне техники.
Выбор из трех стратегий
Клод Шеннон в своей знаменитой статье [2], опубликованной в 1950 году, свел алгоритм шахматной игры к выбору наилучшего хода в конкретной позиции, поскольку точно определить, является ли позиция выигрышной или же ничейной при сильнейшей игре противника (т.е. рассчитать точный путь к мату или к ничьей) в большинстве случаев технически невозможно.
Для нахождения сильнейшего хода Шенноном были предложены две стратегии. В своей книге [4] «Шах XX веку» Ботвинник излагает их суть следующим образом:
1. Полный перебор всех ходов в пределах усеченного дерева вариантов (Стратегия А). 2. Выборочный перебор по аналогии с игрой шахматного мастера (Стратегия B).
Позже Шеннон высказал мысль о том, что машины могут играть в игры, одновременно самообучаясь (Стратегия C). Для решения задачи поиска выхода из лабиринта в 1950 году он построил «умную электромеханическую мышку», получившую имя Тесей — в честь героя древнегреческого мифа, нашедшего выход из лабиринта и поборовшего Минотавра. Мышь могла научиться прокладывать себе путь через лабиринт к медному куску «сыра» без посторонней (на первый взгляд) помощи. Фактически «мозг» мыши был заключен в наборе схем на вакуумных лампах, которые находились под полом лабиринта. «Тесей» стал одной из самых ранних попыток создания самообучающихся машин.
Идеи Шеннона, связанные с самообучением компьютерных программ, сразу начали находить практическое воплощение. Самым значительным достижением в 50-х – начале 60-х годов была шашечная программа Артура Сэмюэля, разработка которой велась 12 лет. В процессе самообучения программа могла менять коэффициенты (веса) оценочной функции, которая учитывала до 30 признаков позиции. Реализованная для компьютера IBM 704, программа Сэмюэля летом 1962 года выиграла у бывшего чемпиона по шашкам штата Кентукки.
Однако успешно перенести свой опыт на программирование шахматной игры у А. Сэмюэля не получилось. Глубина расчета вариантов в шашечной программе могла достигать 20 полуходов, что обеспечивало ее игру на уровне мастера. Достичь такой же глубины расчета в шахматах оказалось невозможным из-за экспоненциального роста числа вариантов. К тому же функциональная неоднородность шахматных фигур, их резко меняющиеся («конъюнктурные», по выражению Ботвинника) стоимости в определенных позициях исключали построение оценочной функции, аналогичной шашечной.
Несмотря на «шахматную» неудачу Сэмюэля, Ботвинник, тем не менее, с большим уважением относился к идее увеличения игровой силы программ за счет их самообучения. Он даже связывал с самообучением возникновение в будущем у компьютеров сознания ([7], c. 27). Тем не менее, он признал для себя невозможность использования стратегии С, о чем так написал в книге [6] «Алгоритм игры в шахматы» :
Что же требуется для составления хорошей программы с самообучением, пока что сказать трудно. Вероятно, кроме знания правил игры, ходов, требуется знание науки о самообучении машин, которая пока что лишь едва-едва намечается. В дальнейшем будем иметь в виду только игру машины по законченной программе (без самообучения).
Таким образом, для реализации своих идей Ботвиннику пришлось выбирать между стратегиями А и B. Выбор в пользу второй из них Михаил Моисеевич сделал для себя сразу и однозначно, поскольку лишь следуя ей, по его мнению, можно создать программу, играющую в силу гроссмейстера.
Метод «брут форс»
С идеями Шеннона, высказанными им в статье [2], Ботвинник долгое время был знаком лишь понаслышке – о них ему рассказывали друзья. Он не спешил прочитать эту статью из некоторого снобизма, поскольку был уверен, что шахматист-любитель не способен познать мышление шахматного мастера ([8], с. 156). Собственно, Шеннон и не выдвигал никаких идей по реализации стратегии B, справедливо предполагая возникновение огромных программистских трудностей. Его выбор был целиком на стороне стратегии А, алгоритмически гораздо более простой. Позже она была названа американскими разработчиками методом «brute forсе» – грубой силы. Имелось в виду, что полный перебор позиций, связанный с этим методом, есть аналогия с грубой силой животного, которой противопоставляются изощренные человеческие приемы.
В 1965 году Шеннон прилетел в Москву на празднование 70-летия изобретения радио А.С. Поповым. По его просьбе была организована встреча с ним М.М. Ботвинника, статью которого «Люди и машины за шахматной доской» американский ученый читал. Встреча великих людей произошла в гостинице «Украина». Переводчиком вызвался быть Лютфи Алескерзаде (1921 — 2017), известный в научном мире как Лютфи Заде – логик, основатель теории нечетких множеств. В детстве он учился в Баку в русской школе, позже через Иран перебрался в США.
Шеннон обсудил с Ботвинником проблему создания искусственного шахматиста. В своих рассказах о той знаменательной встрече Михаил Моисеевич умалчивает, задавал ли его собеседник вопрос о прочтении им статьи [2]. В завершение очного знакомства они сыграли партию в шахматы, текст которой гроссмейстер восстановил по памяти и подарил «любителю» в качестве сувенира.
Пионерскую статью Шеннона Ботвинник все-таки изучил — это произошло в 1966 году, когда он начал работу над книгой «Алгоритм игры в шахматы». Из статьи Шеннона Ботвинник вынес для себя полезную идею о том, что мастер использует в своей игре прошлый опыт, помогающий ему делать выбор в позиции, которую невозможно просчитать до конца. До этого Ботвинник полагал, что «электронный гроссмейстер» должен находить лучший ход в любой оригинальной позиции без всякого опыта. Эта идея Шеннона широко используется в современных шахматных программах: без использования дебютных баз и баз окончаний им невозможно показать сильную игру.
Алгоритмы игры в шахматы
В книге [6] Ботвинником была сделана попытка описать мышление шахматного мастера во время игры и формализовать ее на основе таких понятий, как «неточная цель игры», «траектория», «зона», «горизонт», «математическое отображение позиции». Построенный алгоритм впоследствии предполагалось использовать для оптимальной отбраковки веток дерева перебора — без потери сильных, поначалу кажущихся даже странными, продолжений.
Алгоритм игры по Шеннону
На странице 20 книги [6] Ботвинник приводит описание алгоритма, используемого в методе «брут форс». Поскольку оно очень важно для понимания работы шахматных программ, приведу его целиком.
Перебираются все возможности (ходы) и составляется так называемое дерево с ветвями равной длины, иначе говоря, все варианты перебираемых ходов имеют заданную дальность расчета. Когда заданная дальность расчета достигается, перебор заканчивается. Тогда в конце каждого варианта (окончания ветви дерева) подсчитывается особая оценочная «весовая» функция, выражаемая числом. Сопоставляя эти числа, можно выбрать в данной позиции наилучший ход.
Это описание необходимо дополнить важным замечанием. Вычисляемый по методу «брут форс» максимум оценочной функции всегда будет приходиться на вариант, в котором противник делал слабейшие ходы. В реальности сильный игрок никогда не станет совершать ход в надежде на «зевок» противника, если видит, что в результате такого своего хода он может попасть в худшее положение.
Так, например, играть белыми на «детский мат» можно только с начинающими в расчете на их невнимательность. В игре с сильным противником после 1. e4 e5 2. Cc4 Kc6 вывод ферзя на h5 (3. Фh5? , диаграмма 1) — в надежде на мат 4. Ф:f7x после ошибочного хода черных 3… Кf6 оказывается потерей темпа.
После правильного ответа 3… g6 белый ферзь должен вернуться на свое исходное поле d1 (4. Фd1). Попытка продолжить игру на «детский мат» путем 4. Фf3 практически форсированно ставит белых в критическое положение. Может последовать: 4… f5! 5. ef Kd4 6. Фd1 d5 7. Cb3 C:f5 8. c3 Фg5 (здесь уже выход ферзя на атакующую позицию позиционно обоснован) 9. g3 Kxb3 10. Фxb3 0-0-0 11. Ka3 (угрожая «выпрямиться» путем 12. d4) 11…Cd3 (диаграмма 2) с огромным позиционным перевесом черных. Белые зажаты на первых трех горизонталях, им, как говорят, «тяжело дышать».
Минимаксная процедура
Опытный игрок всегда рассчитывает варианты, пытаясь на каждый свой ход найти сильнейший ответ противника, и так по всей цепочке варианта. Математики говорят, что он таким образом реализует минимаксную процедуру: пытается достичь максимального значения оценочной функции при том условии, что противник каждым своим ответом будет добиваться получения минимального значения этой функции.
Мне кажется вполне логичным, что выход на минимаксное значение оценочной функции является неточной целью игры для программы, реализующей стратегию А. Однако М.М. Ботвинник на с.21 книги [6] почему-то пишет следующее:
«Таким образом, математическая цель шахматной игры по Шеннону – это число (значение весовой функции)».
С точки зрения логики такая трактовка алгоритма Шеннона представляется бессмыслицей: целью может быть, к примеру, выход на максимальное значение функции в результате каких-либо действий, но не какое-то конкретное число.
Ответственный редактор книги [6] Н.А. Криницкий в предисловии к ней рассказывает о сути процедуры минимакса при выборе лучшего хода. Сам Ботвинник об этой важной для понимания алгоритма Шеннона процедуре почему-то умалчивает. Описание ее он дает много позже – например, в выпущенной в 1979 году книге «От шахматиста к машине» [8].
Более верную трактовку неточной цели игры по Шеннону Ботвинник приводит в книге [7] «О кибернетической цели игры» , вышедшей в 1975 году, с. 26:
«Известно, что по Шеннону цель шахматной игры (что, в общем, и определяет оценку позиции и выбор хода) – это максимизация линейной функции подвижности фигур, владения центром доски, пешечной структуры, безопасности позиции короля, материального соотношения сил сторон и т.д.»
Очевидно, что здесь говорится о максимизации оценочной функции. Эта трактовка была бы совсем правильной, если бы в конце была добавлена фраза «с учетом того, что противоположная сторона будет играть сильнейшим образом».
Таким образом, выбор хода при расчете методом «брут форс» характеризуется следующими особенностями:
- Осуществляется полный перебор вариантов на фиксированную, наперед заданную для всех ветвей дерева вариантов глубину;
- Лучший ход выбирается после проведения минимаксной процедуры оценочной функции на концах вариантов.
В середине 1950-х годов метод «брут форс» был дополнен процедурой «альфа-бета отсечения» (англ. Alpha-Beta pruning), в модификациях нескольких авторов. Эта процедура позволила существенно сократить количество узлов, участвующих в процедуре минимакса. Суть альфа-бета отсечения заключается в досрочном прекращении расчета по ветви дерева поиска, если было найдено, что для этой ветви значение оценочной функции в любом случае хуже, чем вычисленное для предыдущей ветви.
К примеру, если программа видит, что после некоторого своего хода она получает мат в два хода (оценочная функции достигнет минимального значения), то она сразу будет стараться найти другой, лучший ход, отбрасывая (не просчитывая) ветви с более слабыми ответами противника.
По какой-то причине в своей книге [6] Ботвинник считает, что программы, использующие метод альфа-бета отсечения, реализуют стратегию B. На странице 21 он пишет о первом в истории соревновании компьютерных программ, ходы в котором передавались при помощи телеграфа:
«Матч из 4 партий, проводившийся в 1966 – 1967 гг. межу машинными программами Института теоретической и экспериментальной физики в Москве и Университета в Станфорде, подвел как бы итог работам математиков, начатым Шенноном в 1950 г. Московская программа в основном соответствовала первому принципу Шеннона, к тому же использовалась маломощная машина. Американская программа соответствовала второму принципу Шеннона – более совершенному, а машина была весьма мощной. И что же? Американцы потерпели фиаско. Суть дела в том, что реализация первого принципа достаточно проста, а как реализовать второй принцип – было неведомо! Конкретное решение, примененное американским математиком Маккарти, оказалось неудачным. Правило отбрасывания ходов было составлено так, что вместе с водой машина выплескивала и ребенка».
Речь здесь идет о разработанной группой математиков под руководством А.С. Кронрода программе-предшественнице знаменитой «Каиссы», о которой говорилось в первой части данной статьи. Она со счетом 3:1 (две победы при двух ничьих) обыграла американскую программу — разработку Джона Маккарти и его аспиранта Алана Котока. Профессор Джон Маккарти, придумавший термин «искусственный интеллект» и язык LISP, был автором одной из версий процедуры альфа-бета отсечения под названием «аппроксимация». В остальном программа Стэнфордского университета полностью следовала стратегии А, или, в формулировке Ботвинника, первому принципу Шеннона. С отнесением алгоритма этой программы ко второму принципу Шеннона Михаил Моисеевич ошибся.
Все современные (не самообучающиеся) программы также следуют стратегии А. Если с водой эти программы и выплескивают ребенка, т.е. отбрасывают самый сильный ход в позиции, то, благодаря быстродействию компьютеров, это происходит на такой глубине расчета, которая практически недостижима для «белковых» шахматистов – они обрывают цепочку вариантов еще раньше.
Алгоритм Ботвинника
М.М. Ботвинник в работе [6] критикует рекомендации Шеннона, считая, что предложенный им алгоритм далеко не оптимален. Тем не менее, когда сравниваешь описания алгоритмов Шеннона и Ботвинника, понимаешь, что претензии можно предъявить не только к первому.
Любой программист знает, что чем длиннее код программы, тем больше в нем содержится ошибок и тем сложнее программу отлаживать. Уже на уровне описания алгоритмов становится видна существенная разница в сложности реализаций стратегий А и B.
Описание алгоритма стратегии А занимает всего лишь одну страницу. Описанию своего алгоритма (с примерами) Ботвинник посвящает главы II и III книги [6] – всего 35 страниц. В них полно математических формул, для понимания которых требуется определенная подготовка. Достаточно сказать, что для вычисления полной стоимости фигуры (в ней учитывается ее средняя стоимость и возможности ее нападений на фигуры противника) Ботвиннику потребовалось введение комплексных чисел (с. 37).
Подробное описание алгоритма шахматной игры по Ботвиннику не входит в задачу данной статьи. Желающие могут самостоятельно ознакомиться с ним по книгам [6], [7], [8]. Укажу лишь на основные идеи этого алгоритма.
В основе алгоритма Ботвинника лежит, по его признанию, сформулированный еще Капабланкой принцип: «Шахматы – это материал и контроль полей». Для формализации этого принципа Ботвинник вводит понятие «обобщенного размена» (с. 29):
Это такой размен, где меняются (в общем случае) ценности как материальные, так и позиционные («невидимые», конъюнктурные). Цель обобщенного размена – относительный выигрыш этих материальных либо позиционных (конъюнктурных) ценностей. Других целей нет и не может быть. В конечном итоге в шахматах этот обобщенный размен должен привести к выигрышу бесконечно большой материальной ценности (к мату).
Игру шахматного мастера Ботвинник рассматривает как трехуровневую систему управления. Первый уровень образуют фигуры, у каждой из которых есть свои «мишени» — вражеские фигуры и пешки. Второй уровень – это сложные зоны игры, состоящие из зон нападения, зон отступления и зон контроля. Третий уровень – это так называемое «математическое отображение позиции» (МО) — совокупность сложных зон с глубиной расчета, определяемой текущим (позиционным) и предельным горизонтами.
Предельный горизонт зависит в основном от характеристик компьютера (его памяти и быстродействия). Позиционный горизонт меняется в зависимости от сложности позиции. Он может увеличиваться по мере перехода борьбы из миттельшпиля в эндшпиль, и в этом его отличие от дальности расчета, фиксированной по определению, в алгоритме Шеннона. При формировании МО отсеивается огромное количество бессмысленных вариантов. Окончание перебора вариантов в пределах позиционного горизонта и принятие решения (выбор наилучшего хода) осуществляется на основе выполнения неравенств, приведенных на с. 43 (за белых) и с. 44 (за черных). В них используются числовые оценки параметров, включенных в «обобщенный размен».
От алгоритма к программе «Пионер»
Когда алгоритм создания «электронного гроссмейстера» на уровне блок-схем и формул был завершен, настала пора задуматься о его реализации в виде компьютерной программы. По своему образованию М.М. Ботвинник не был программистом. Но он понимал, что, даже освоив программистское ремесло, ему одному будет не справиться с задачей кодирования алгоритма – нужен коллектив талантливых единомышленников.
С целью пропаганды своих идей Михаил Моисеевич принес рукопись статьи «Алгоритм игры в шахматы» гроссмейстеру Владимиру Симагину, редактору «Бюллетеня Центрального шахматного клуба СССР». После публикации ее «в порядке обсуждения» 13 мая 1966 года состоялась публичная дискуссия, в ходе которой Михаилу Моисеевичу пришлось выслушать немало критических замечаний. Из выступлений Г.М. Адельсон-Вельского и М.Р. Шуры-Буры, имевших опыт разработки шахматных программ, Ботвинник узнал, что никто еще прежде не смог научить ЭВМ находить траектории передвижения фигур на доске. Поскольку человек решает эту проблему с легкостью, Ботвинник ранее не придавал ей особого значения. После дискуссии за две недели напряженных размышлений ему удалось разработать алгоритм формирования траекторий – с помощью массивов 15×15.
После этого, переработав рукопись, Ботвинник обратился в издательство «Наука» с предложением издать книгу, в которой описан его алгоритм шахматной игры. При поддержке главного математика ГВЦ Госплана Николая Андреевича Криницкого (1914 — 1993), написавшего к книге предисловие, и академика К.В. Островитянова книга «Алгоритм игры в шахматы» в 1968 году вышла в свет. Переведенная на английский, она была издана в Нью-Йорке в 1971 году и получила за рубежом одобрительные отзывы.
Узнав о них от крупного американского специалиста по принятию решений Германа Кана, ответственный сотрудник Государственного комитета по науке и технике (ГКНТ) В.И. Максименко счел, что престиж страны требует реализации идей Ботвинника на практике. В январе 1972 года академик А.И. Берг подписал три письма – в ГКНТ, Министерство энергетики (в которое входил ВНИИ Электроэнергетики, где М.М. Ботвинник руководил лабораторией) и ГВЦ Госплана СССР с просьбой открыть научную тему по работе над программой и выделить машинное время. Согласие трех ведомств было получено. Осталось набрать команду программистов и приступить к созданию программы, впоследствии названной «Пионер».
Литература
- Turing A. Computing Machinery and Intelligence // The Mind, V. 59 (1950), P. 433-460.
- Shannon C. Programming a Computer for Playing Chess // Philosophical Magazine, Ser.7, Vol. 41, No. 314. March 1950.
- Кронрод А.С. Беседы о программировании. М.: УРСС, 2004.
- Ботвинник М.М. Шах XX веку. М.: Зебра Е, 2010
- Ботвинник М.М. Люди и машины за шахматной доской //Сборник «Возможное и невозможное в кибернетике». М.: Изд-во Академии наук СССР, 1963
- Ботвинник М.М. Алгоритм игры в шахматы. М.: Наука, 1968
- Ботвинник М.М. О кибернетической цели игры. М.: Советское радио, 1975
- Ботвинник М.М. От шахматиста к машине. М.: Физкультура и спорт, 1979
Окончание следует
Перейти к части III
