«Каиссе» 50: история советской компьютерной программы, победившей в чемпионате мира по шахматам
Откуда вышла «Каисса»
История «Каиссы» начинается в 1960-е годы в Институте теоретической и экспериментальной физики (ИТЭФ). К тому моменту кибернетика вышла из опала, перестав считаться лженаукой, а среди ученых сформировалось представление о том, что машины потенциально способны не только производить расчеты, но и решать более комплексные задачи. В том числе и думать. Хоть термин «искусственный интеллект» появился еще в 50-е годы, но в СССР эту область называли «эвристическим программированием». У нее было несколько направлений, одно из них - игры.
Программы писались для разных игр — от преферанса до крестиков-ноликов, — но особое внимание уделялось шахматам. У них, во-первых, было много дифференцируемых критериев качества: машина играет на уровне третьего разряда, гроссмейстера и так далее, соответственно, можно было объективно оценить, какие результаты она выдает. Во-вторых, в шахматных играх применяется механизм перебора ходов, который, в свою очередь, мог быть использован в других областях. Так что нет ничего удивительного в том, что на протяжении долгого времени шахматные программы были своего рода полигоном для отработки методов принятия решений.
Так что специалисты не столько занимались играми, сколько «тренировали» машины решать невычислительные задачи. По современным меркам успехи ученых были достаточно скромными — исследователям мешали как ограниченность памяти компьютеров, так и собственное не до конца сформировавшееся понимание того, в каком направлении должна вестись работа. Однако уже тогда, в 60-е годы, они предполагали, что через два или три десятилетия машина сможет обыграть чемпиона мира по шахматам.
Лаборатория ИИ и матч со Стэнфордом
В обязанности математической лаборатории в ИТЭФа входили обсчет физических измерений и моделирование разных физических процессов по заказу физиков. Однако заведовавший ей Александр Кронрод, помимо математики, увлекался также вычислительными машинами, и благодаря его стараниям в институте появился семинар, фактически ставший лабораторией искусственного интеллекта. Там решали задачи компьютерного распознавания, писали алгоритмы для игр и многое другое. Программа, ставшая предшественницей «Каиссы», была создана в 1966 году. Через год ей предстояло сразиться с разработкой американских ученых.
Одним из инициаторов матча между ИТЭФом и Стэнфордским университетом стал Джон Маккарти — автор термина «искусственный интеллект» и создатель языка программирования Lisp. Он несколько раз бывал в Москве, встречался с советскими учеными и даже ходил к ним в гости. В один из приездов Маккарти разработчики договорились устроить состязание между компьютерными программами для обмена опытом. Абрам Алиханов, директор ИТЭФ, положительно отнесся к этой идее и дал на нее добро. Политическую сторону игр никто особо всерьез не рассматривал, так что все согласования проходили без особых проблем.
Матч из четырех партий растянулся почти на год. Играли на собственных вычислительных машинах, а ходы передавались по телеграфу. Днем сотрудники ИТЭФ загружали в компьютеры задачи физиков, а ночью те просчитывали шахматные партии. Иногда на один ход уходило по две ночи. Впрочем, никакой спешки не было, и к тому же у исследователей имелись свои задачи, помимо шахмат. Игра завершилась со счетом 3:1 в пользу советской программы.
Хоть в первую очередь обе стороны ставили чисто научные цели, но радость от победы никто не отменял. К тому же она была серьезным аргументов для руководства Института теоретической и экспериментальной физики продолжить разработку шахматных программ. Американцы, несмотря на поражение, тоже смогли извлечь пользу из матча. А именно — получить дополнительное финансирование, уведомив начальство о том, что есть область, где США отстают от СССР.
Рождение шахматной программы
В 1968 году в результате скандала, связанного с подписанием рядом ученых письма в защиту Александра Есенина-Вольпина, коллектив математической лаборатории перешел в Институт автоматики и телемеханики, который вскоре был переименован в Институт проблем управления. Там начальство смотрело на разработки в области компьютерных шахмат достаточно косо. Все-таки ИПУ РАН занимался созданием систем управления предприятиями, а тут какие-то «игры». Но тем не менее ученым позволили продолжить то, чем они занимались на прежнем месте работы.
Правда, при переходе в другой институт практически весь старший состав математической лаборатории ИТЭФ был «растерян» — кто-то ушел в другое место, кого-то не могли принять в самом ИПУ РАН. Но пришла подмога от младшего поколения. В 60-х годах Александр Кронрод разработал программу занятий математикой для московской Седьмой школы. К 1968-му некоторые ее выпускники заканчивали институты, и часть из них удалось переманить в математическую лабораторию, в частности Михаила Донского - будущего разработчика «Каиссы».
В ИПУ РАН сотрудники математической лаборатории получили в свое распоряжение английскую машину ICL 4-70 — до этого в ИТЭФ они пользовались М-20. Из-за перехода на новое более мощное «железо» им пришлось переписать программу с кодов машины на ассемблер совершенно с другой архитектурой. Фактически получилась новая программа, впоследствии названная в честь вымышленной богини шахмат. Годом ее «рождения» стал 1971.
Ключевую роль в создании «Каиссы» сыграли Владимир Арлазаров, Михаил Донской и Георгий Адельсон-Вельский. Помимо них, над программой работали также Александр Битман, Александр Бараев, Анатолий Усков, Андрей Леман и Марианна Розенфельд. Были еще и другие разработчики, которые не писали «Каиссу» непосредственно, но работали над шахматной программой по периметру, тем самым внося вклад в общее дело.
К слову сказать, среди ученых, занимавшихся «Каиссой», в шахматы играли в основном на любительском уровне. Исключениями были Александр Битман, бывший мастером спорта по шахматам, и Владимир Арлазаров, игравший на уровне первого разряда и ставший потом кандидатом в мастера. Однако отсутствие шахматных «скилов» не мешало разработчиков и отчасти соответствовало их позиции свести к минимуму использование шахматных знаний в алгоритмах программы.
«Каисса» против читателей газет
Вскоре после создания «Каиссе» предстояло испытать свои навыки в игре с читателями «Уральского рабочего» и «Комсомольской правды». Инициаторами состязаний выступили редакторы газет, и разработчики увидели в их предложении возможность протестировать программу.
Оба матча были устроены одинаково. Газеты публиковали информацию о ходе партии, и в течение недели читатели присылали в редакции письма, где указывали, какой фигурой и куда стоит пойти. Из всех вариантов выбирался тот, который чаще всего упоминался в почтовых отправлениях, и он объявлялся следующим ходом читателей газеты. Ученые, получив эти данные, вбивали их в машину, и она за выходные подсчитывала следующий ход. Обе игры шли около года.
Если матч с «Уральским рабочим» «Каисса» выиграла (и разработчики даже получили от читателей в качестве сувенира кусок камня), то «Комсомольской правде» проиграла со счетом 1,5 на 0,5. Как признавали ученые, их программа играла в силу третьего разряда и имела немало слабых мест. Например, ее можно было легко переиграть, если перейти в эндшпиль — машины могли считать только на три-четыре хода вперед, что не подходило для заключительной части партии, где необходимо продумать стратегию игры до самого конца. Впрочем, разработчики не расстраивались из-за поражения, и полученные знания помогли им впоследствии улучшить программу. К тому же именно во время матча с «комсомолкой» «Каисса» получила свое название. Его придумал шахматный обозреватель Хенкин.
Помимо читателей газет, к программам присматривались и опытные шахматисты. Например, Михаил Ботвинник, шестой чемпион мира в истории шахмат и «патриарх советской шахматной школы», занимался также научной деятельностью и даже написал книгу «Алгоритм игры в шахматы». Он обсуждал с создателями «Каиссы» возможность поработать вместе и позже с двумя программистами пытался написать программу «Пионер». Или Леонид Бронштейн — во время матча в Таллине он отложил партию и обратился к разработчикам, чтобы они выслали расчеты возможных исходов игры. Как уверял шахматист, полученные данные помогли ему одержать победу в том турнире.
WCCC — 1974 — Стокгольм
К 1970-м годам, помимо СССР и США, компьютерными шахматами занимались также в Канаде, Британии, Норвегии и других странах. Учитывая возросшее число подобных программ, Международная федерация по обработке информации (ИФИП) решила устроить состязание между ними. Чемпионат мира по шахматам среди компьютерных программ (WCCC) был назначен на 1974 год, а в качестве места проведения был выбран отель Birger Jarl в Стокгольме. Участниками стали 13 программ из 8 стран.
К чемпионату «Каисса» была значительно улучшена. В частности, она получила алгоритм альфа‑бета отсечения позиции, начала использовать побитовое представление доски, научилась проводить анализ партии во время хода противника и тому подобное. Правда, в Стокгольме должна была играть также разработанная сотрудниками Северо-Западная университета Chess 4.0. Эта программа считалась крайне мощной по своим временам, и до WCCC 1974 она успела несколько раз победить на Северо-Американском чемпионате по шахматам среди компьютерных программ. Многие думали, что победа в чемпионате мира достанется именно Chess 4.0, и разработчики ИПУ РАН тоже сомневались, что «Каисса» сможет тягаться с таким конкурентом. С другой стороны, на стороне советских ученых была сильная школа программирования, которая позволяла отчасти нивелировать недостатки вычислительной техники.
Чемпионат длился с 4 по 8 августа. Учитывая габариты ЭВМ, в зале, где проходил турнир, удалось разместить всего пару «участников», а остальные «играли» у себя дома и передавали ходы по телефону. От каждой команды в Стокгольм был направлен свой представитель (от ИПУ РАН присутствовал Михаил Донской), а к тем машинам, на которых выполнялись шахматные программы, ИФИП отправила своих наблюдателей — те должны были удостовериться, что играет сама программа, а не человек за нее. Как позже вспоминал Михаил Донской, во время матчей, пока программы думали над следующими ходами, их авторы имели возможность пообщаться друг с другом и в том числе обменяться опытом разработки компьютерных шахмат. Родившаяся из этих обсуждений дружба впоследствии длилась долгие годы.
«Каисса», выиграв во всех 4 партиях и набрав 4 очка, стала первым чемпионом мира по шахматам среди компьютерных программ. Некоторые организаторы выражали недовольство тем, что «богиня шахмат» и Chess 4.0, лучшие программы турнира, не сыграли друг с другом. Потому после чемпионата был организован дополнительный матч между ними, закончившийся ничьей.
Советский ИИ — тогда и сегодня
WCCC 1974 получил большой резонанс в мире. В СССР победа «Каиссы» была воспринята как большой успех советской науки и публикации о ней появились в центральной печати. В США после проигрыша русским начали интенсивнее вкладываться в исследования по шахматному программированию. И в целом прошедшее состязание показало всей мировой общественности, что вычислительные машины способны не только производить различные расчеты, но и самостоятельно решать сложные логические задачи, будь то игра в шахматы.
«Каисса» играла еще на втором и третьем чемпионатах мира, но там уже не занимала первые места. К началу 80-х годов отставание советской вычислительной техники от западной становилось все более серьезным, и ученые уже не могли на равных соревноваться с иностранными разработками. Да и сами создатели «Каиссы» постепенно перестали заниматься шахматным программам. Сказались и коммерциализация этой области (и как следствие — утрата научного интереса у разработчиков), и появление новых задач, которым надо было уделять время.
Триумф «Каиссы» на играх 1974 года стал первой победой советского ИИ на международной арене. И, кажется, последней. Но это только в играх. В других областях у советских ученых тоже были значимые достижения, и некоторые из написанных ими алгоритмов вошли во все учебники по математике, будь то АВЛ-дерево или «алгоритм четырех русских».