Программа «Пионер». Задача, которую не смог решить Михаил Ботвинник
Шестому чемпиону мира по шахматам Михаилу Ботвиннику (1911 — 1995) приходилось решать в своей жизни множество задач – как за шахматной доской, так и вне ее. Ему удалось договориться с Александром Алехиным о проведении матча на первенство мира, после его смерти выиграть матч-турнир пяти сильнейших гроссмейстеров и стать чемпионом мира. Он получил признание в научных кругах, сделав открытие, занесенное в реестр государственных изобретений СССР, и защитив докторскую диссертацию по электротехнике. Однако Михаил Ботвинник так и не смог решить до конца задачу, над которой он бился почти 40 лет: можно ли создать программу, моделирующую мышление гроссмейстера? Программа «Пионер» разрабатывалась для ответа на этот вопрос.
Часть I. Предыстория «Пионера» — идея «электронного гроссмейстера».
СПРАВКА – Биография М.М. Ботвинника
Михаил Моисеевич Ботвинник (17 августа 1911, пос. Куоккала под Санкт-Петербургом —5 мая 1995, Москва)—советский шахматист, шестой чемпион мира, специалист в области электротехники и шахматного программирования, доктор технических наук.
С шахматами Михаил Ботвинник познакомился довольно поздно — в 12 лет. Однако уже в 14 имел 1-ю категорию, выиграл в сеансе у чемпиона мира Капабланки, в 16 стал мастером. Победы в чемпионатах Ленинграда (1931-1932), чемпионатах СССР (1931, 1933) выдвинули Ботвинника в число сильнейших шахматистов страны. В 1936 году на турнире в английском городе Ноттингеме собрались: чемпион мира Эйве, три экс-чемпиона и четыре претендента на чемпионское звание — Боголюбов, Файн, Решевский, Флор. Ботвинник поделил с Капабланкой 1-2 места.
В 1948 году Ботвинник выиграл матч-турнир пяти сильнейших гроссмейстеров мира (каждый играл с каждым по 5 партий), и был объявлен 6-м чемпионом мира. В течение последующих 15 лет он сыграл 7 матчей за мировую шахматную корону, окончательно уступив ее в 1963 году 34-летнему Тиграну Петросяну.
Выступления в шахматных соревнованиях М.М. Ботвинник совмещал с занятиями наукой. В 1927 году он поступил на математико-механический факультет ЛГУ — там квота рабфаковцев не доходила до 95%, как в инженерных вузах. Высшую математику на матмехе преподавал Г.М. Фихтенгольц, автор знаменитого учебника, В феврале 1928 года Михаил перевелся на электротехнический факультет Ленинградского политехнического института, где он ранее успешно сдал вступительные экзамены.
В 1937 году была успешно защищена кандидатская диссертация. В своей работе Ботвинник впервые показал, что возможна устойчивая передача электрической энергии на большие расстояния, если у генераторов применить специальное регулирование. Через полтора месяца после окончания матча на первенство мира с Д. Бронштейном, 28.06.1951, была защищена и докторская диссертация, тема — «Регулирование возбуждения и статическая устойчивость синхронной машины». Впоследствии (1958) придуманное Ботвинником «сильное» регулирование генераторов переменного тока было внесено в реестр государственных изобретений СССР.
В конце 50-х годов Ботвинника увлекла новая идея — создание шахматной программы, алгоритм работы которой моделировал бы мышление гроссмейстера. Это позволило бы существенно уменьшить количество рассматриваемых вариантов по сравнению с методом «brute force» — полного перебора вариантов на определенную глубину. Над своей программой «Пионер» Ботвинник работал (вместе с меняющейся командой программистов) вплоть до 1990 года. Она не была закончена (хотя «научилась» решать довольные сложные этюды). Тем не менее, на основе созданных алгоритмов («шахматный метод решения переборных задач») удалось оптимизировать графики ремонта оборудования электростанций (программа «Пионер» версии 2.4) и решить задачу «межотраслевой баланс» планирования социалистической экономики (программа «Пионер» версии 4.1).
В середине 60-х годов в рамках спортобщества «Труд» М.М. Ботвинник организовал выездную школу для юных одаренных шахматистов, она просуществовала до марта 1988 года. Свои знания Михаил Моисеевич передал ставшим впоследствии чемпионами мира А. Карпову, Г. Каспарову, В. Крамнику, многим другим будущим мастерам и гроссмейстерам.
За достижения в области шахмат М.М. Ботвинник был награждён орденом Ленина (1957), орденом Октябрьской Революции (1981), орденом Трудового Красного Знамени (1961), орденом «Знак Почёта» (1936).
Идея универсальной программы
В 1950 году достоянием широкой аудитории стала статья [1] английского математика Алана Тьюринга (1912 – 1954) «Вычислительные машины и разум». В ней он попытался дать ответ на сакраментальный вопрос «Может ли машина мыслить?» с помощью простого теста, названного им «Игра в имитатацию», а позже «тестом Тьюринга».
В своей статье Тьюринг также привел часто встречающиеся возражения на возможность создания искусственного интеллекта (ИИ – термин придумал в 1955 году американец Джон Маккарти). Одно из них (четвертое) выглядело так:
Аргумент от сознания: Нейрохирург сэр Джеффри Джефферсон в речи, произнесенной по случаю награждения престижной медалью Листера в 1949 году, заявил: “Согласиться с тем, что машина так же разумна [как человек], мы сможем не раньше, чем она сможет написать сонет или сочинить концерт под влиянием своих мыслей и эмоций, а не из-за случайного выбора символов”.
Ответ Тьюринга репортеру из лондонского Times, казалось, был несколько легкомысленным, но тонким:
“Сравнение, возможно, не совсем справедливо, поскольку сонет, написанный машиной, лучше оценивать другой машине”.
Очень скоро, благодаря бурному развитию электронно-вычислительной техники в 1950-е годы, компьютерные программы стали решать задачи, которые совсем недавно казались прерогативой только человеческого мозга. Так, например, программа «Логик-теоретик», которую создали в 1957 году американцы А. Ньюэлл, Г. Саймон и К. Шоу, доказала все 52 теоремы из фундаментальной книги (трехтомника) Бертрана Рассела и Альфреда Уайтхеда «Основания математики». В 1959 году большую известность получили эксперименты советского математика и музыканта Рудольфа Загайнова, который «вдохновил» машину «Урал» на сочинение одноголосных пьес («Уральские напевы»).
В 1954 году в США были публично продемонстрированы опыты машинного перевода математических текстов с русского языка на английский. А в конце 50-х годов китайские математики и лингвисты вместе с советскими учеными представили первые результаты машинного перевода с русского на китайский, имеющий, как известно, не свойственный европейским языкам грамматический строй вкупе с иероглифической письменностью.
В конце 1950-х годов перед специалистами в области информатики логично стал вопрос: а можно ли создать такую программу, которой будет по силам решать проблемы из любой творческой области? Первую попытку в этом направлении сделал упомянутый выше коллектив из Аллена Ньюэлла, Герберта Саймона и Клиффорда Шоу. В 1959 году они продемонстрировали программу General Problem Solver, или GPS – «Универсальный решатель задач». Как писали ее создатели, программа GPS должна была «размышлять о целях и средствах достижения целей»: сначала искать, что надо решать, какой цели добиваться, а затем искать, как решать, какими средствами достичь намеченной цели. При этом в процессе решения общей задачи GPS искала подцели – промежуточные этапы, ведущие к решению задачи. Поиски оптимального решения программа делала лабиринтным путем, т.е. путем блуждания по цепочкам вариантов. В качестве примеров использования приводились доказательства теорем евклидовой геометрии и логики предикатов, а также решение шахматных задач.
Программа была основана на теоретической работе Саймона и Ньюэлла о логических машинах. Считается первой компьютерной программой, в которой предпринята стратегия разделения знаний о задачах (правила, которые подавались на вход программы) от стратегии решения задач (общий решающий движок). Решающий алгоритм был реализован на низкоуровневом языке программирования IPL. Именно с этой программы, по мнению ряда ученых, начался новый этап в развитии замечательной идеи о механическом усилителе человеческого разума – создании так называемого «искусственного интеллекта».
Статья Шеннона
Программа GPS действовала по эвристическому протоколу, т.е. примеряла свои действия к сложившейся ситуации. Как показали эксперименты, она попадала в те же тупики при решении задач, что и человек, выбирала аналогичные пути решения и подцели. На этой основе создатели GPS полагали, что их программа моделирует работу человеческого ума и может решать такие же по сложности задачи, что и человек. Действительно, программа успешно решила известную нам с детства задачу о волке, козе и капусте (в американском варианте – о миссионерах и людоедах), головоломку о ханойской башне, доказывала алгебраические и тригонометрические тождества, решила ряд производственных задач (например, по оптимизации перевода предприятия на выпуск новой продукции).
Однако позже, когда программе поручили играть в шахматы, выяснилось, что лабиринт возможных ходов на пути к победе – мату королю противника – она распутать не смогла: слишком оказался этот лабиринт велик, поиск по цепочке решения приводил к комбинаторному взрыву числа промежуточных шагов. Сильный шахматист же в этом лабиринте ориентируются свободно. Стало быть, есть какие-то правила действия, алгоритмы, пусть и не машинные, позволяющие опытному руководителю или шахматисту принимать правильные решения?
Для того, чтобы ответить на этот вопрос, нужно было придумать какой-нибудь всеобщий полигон для отработки возможных проблем при создании такого алгоритма – который был бы интересен и понятен всем специалистам в области ИИ. Такую площадку публично предложил еще в 1949 году американский математик, создатель теории информации Клод Шеннон (1916 — 2001). Позже он изложил свои идеи в статье [2] «Программирование компьютера для игры в шахматы», которая была опубликована в марте 1950 года.
Шеннон объяснил, почему считает шахматы столь хорошим тестовым полигоном.
Во-первых, проблема четко определена как с точки зрения допустимых операций (ходы), так и в плане конечной цели (мат). Во-вторых, целевая задача не столько проста, чтобы считаться примитивной, но и не слишком сложна для отыскания удовлетворительных решений. В-третьих, успех или неуспех в создании шахматной программы позволит по-новому взглянуть на природу мышления – как человеческого, так и компьютерного. И, в-четвертых, дискретная природа шахмат (ходы по очереди) хорошо вписывается в цифровую природу современных компьютеров.
Шахматы – «муха-дрозофила» искусственного интеллекта
Откуда же пошло сравнение роли шахмат в проблеме создания ИИ с ролью мухи-дрозофилы в решении проблем генетики?
А.С, Кронрод 
В СССР первая шахматная программа начала создаваться в «мозговом центре» ядерного проекта — Институте теоретической и экспериментальной физики (ИТЭФ), в лаборатории, которую в начале 50-х годов возглавил Александр Семенович Кронрод (1921 – 1986). Незадолго до этого он защитил в МГУ, минуя кандидатскую, докторскую диссертацию, которая, по существу, она стала основанием теории функций двух переменных. Однако вскоре молодой доктор решил уйти из «чистой» математики в прикладную сферу.
В 1950-х годах ядерщикам отдавались самые производительные ЭВМ. У сотрудников лаборатории Кронрода оставалось свободное от решения основных задач машинное время, и потому они нелегально «развлекались» интересными для них вещами – в частности, созданием шахматной программы. Александр Семенович их «прикрывал». Позже работы по этой внеплановой теме станут престижными — как возможность успешно соревноваться с американцами в интеллектуальной сфере.
Вот что не без юмора написал в своей книге [3] «Беседы о программировании» (написанной в 1964 году, но опубликованной лишь спустя 40 лет) А.C. Кронрод:
«После нашего фиаско с подкидным дураком встал вопрос о том, какую игру выбрать для генерального наступления. Котировались крестики-нолики, шашки и шахматы. Самое важное, казалось нам тогда,— иметь игру, общую в международном масштабе. Вроде того, как у генетиков избраны муха-дрозофила и кукуруза. Порешили, что наиболее подходящим с этой точки зрения объектом являются шахматы. Может быть, играли роль личные вкусы Адельсон-Вельского и Арлазарова. Нам с Усковым (на первых порах я тоже принимал кое-какое участие в этом деле) было все равно. И – несколько односторонне, поскольку мы не вели про это переговоров ни с кем, не только в Международном, но и в Союзном и даже в Московском масштабе – шахматы были признаны дрозофилой. Было это в 1960 году».
Несмотря на то, что из-за критики Кронродом отдельных руководителей его книга своевременно не была напечатана, выражение «шахматы – это «муха-дрозофила» искусственного интеллекта» стало достоянием журналистов, и вскоре превратилось в своего рода штамп.
А. Тьюринг и К. Шеннон – предвестники «электронного шахматиста»
В 1936 году выпускник Кембриджа (Великобритания) Алан Тьюринг придумал абстрактную вычислительную машину, которая формализовала определение алгоритма. Понятие алгоритма долгое время оставалось интуитивным, что мешало ответить на множество математических вопросов. Например, всякую ли задачу можно решить алгоритмически — или есть такие, которые можно решить только методом перебора? Как вообще понять, существует ли алгоритм для решения той или иной задачи? Описание «машины Тьюринга» позволило подступиться к этим проблемам.
Тьюринг с детства интересовался шахматами. Во время работы (1939 – 1945) в британском центре криптографии «Блетчли-Парк», где большой коллектив трудился над взломом кодов германской шифровальной машины «Энигма», он тесно общался с сотрудниками — шахматными мастерами Гарри Голомбеком, Хью Александером и Стюартом Мильнер-Барри. Гарри Голомбек впоследствии стал известным международным арбитром ФИДЕ и судил финальный матч за звание чемпиона мира между Ботвинником и Петросяном.
В 1951 году Алан Тьюринг и его коллега Дэвид Чамперноун создали алгоритм шахматной программы. В следующем году, не имея подходящего компьютера, на котором алгоритм мог быть воспроизведен, Тьюринг сыграл игру, в которой симулировал действия машины, делая по одному ходу в полчаса. Алгоритм анализировал игру на два хода вперед. Сохранилась запись 29-ходовой партии, в которой играющий по алгоритму Тьюринг проиграл своему коллеге Алику Гленни. В равной по материалу позиции алгоритм «зевнул» потерю ферзя: в положении на диаграмме он сделал ход 29.Фxd6?, на что последовало 29…Лd8. Позже при помощи своей «бумажной машины» Тьюринг выиграл партию у жены Чамперноуна.
Одновременно с Аланом Тьюрингом вопросом создания электронного шахматиста занимался другой великий математик – создатель теории информации американец Клод Шеннон (1916 – 2001). По утверждению Ботвинника (книга [4] «Шах XX веку»), Шеннон научился играть в шахматы только в 28 лет, т.е. в 1944 году. Шеннон совместно с Тьюрингом занимался разработкой шифров для переписки Черчилля и Рузвельта – во время пребывания английского математика в период с ноября 1942 года по март 1943 года в США. Как знать, может быть, в эти месяцы они говорили не только о криптографии, но и о шахматах.
В своей работе 1950 года [2] Шеннон подсчитал, что минимальное количество неповторяющихся шахматных партий составляет приблизительно 10120 (так называемое число Шеннона). В основу вычислений легло его предположение о том, что каждая игра длится в среднем 40 ходов и на каждом ходе игрок делает выбор в среднем из 30 вариантов. Для сравнения — количество атомов в наблюдаемой Вселенной составляет приблизительно 1080, т.е. в 1040 раз меньше.
Отсюда следует, что практически невозможно создать такой алгоритм, который бы вычислил наперед результат шахматной партии исходя из начальной позиции, если противники играют наилучшим образом. В шашках, к примеру, где различных вариантов гораздо меньше (порядка 1040 ), результат партии можно просчитать до конца (что окончательно было осуществлено в 2007 году): будет ничья. Т.е. шашечная программа, действующая по оптимальному алгоритму, сможет сыграть как минимум вничью с любым противником – как с «белковым», так и с «электронным». В каждой возможной позиции она знает, как играть сильнейшим образом.
Таким образом, построение алгоритма игры в шашки – задача точная, а в шахматы – неточная. Отсюда следует, что в шахматах точную цель – мат королю противника — изначально ставить для компьютерной программы нет никакого смысла: она не будет достигнута в силу ограничений по имеющимся ресурсам (быстродействие, оперативная память, время на обдумывание). Разработчикам шахматных программ, следовательно, необходимо было определиться, прежде всего, с неточной целью игры, и на ее основе вырабатывать дальнейшие стратегии.
100 гульденов за одно слово
В 1957 году Алексом Бернштейном была создана первая программа для игры на стандартной шахматной доске и при участии всех фигур. Разумеется, она играла очень слабо. Расчет вариантов делался всего на три полухода – возможности ЭВМ того времени не позволяли его вести на большую глубину. Тогда казалось нереальным, что компьютеры когда-нибудь смогут играть на уровне гроссмейстеров высокого класса, но все понимали, что это только начало противостояния «естественного» и «искусственного» разума.
В октябре 1958 года, после окончании шахматной Олимпиады в Мюнхене, Михаила Ботвинника попросил посетить Голландию Макс Эйве – доктор наук в области математики и пятый чемпион мира. Помимо встреч с любителями шахмат Ботвиннику предстояло выступить в телепередаче, посвященной ЭВМ. В ней принимали участие представители многих специальностей – математики, шахматисты, психологи, поэты. Михаилу Моисеевичу был задан всего один вопрос: «ЭВМ в будущем сможет хорошо играть в шахматы?» «Да», не задумываясь, ответил Ботвинник, и получил за участие в передаче 100 гульденов! Позже он напишет в книге «Шах XX веку»: «Никогда одно слово не приносило мне столь больших доходов».
И все же это короткое «телеинтервью» можно считать отправной точкой на пути шестого чемпиона мира к созданию «электронного гроссмейстера». Тогда ответ Ботвинника был продиктован интуицией. Однако позже он стал всё серьезнее задумываться над проблемой компьютерных шахмат, и в конце концов — уже в 1970-х – полностью переключился на ее решение.
Продолжение следует
Литература
- 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
