История “Каиссы”
Подробности первого чемпионата мира среди шахматных программ в 1974 г. в Стокгольме
Михаил Донской
Сейчас уже трудно себе представить эру мэйнфреймов - больших компьютеров, каждый из которых занимал приличный зал. Но в начале 70-х это было последним писком. В те годы компьютеры только начали появляться в далеких от военных нужд областях. По непонятным причинам в это время в СССР были произведены “массовые” (пяток экземпляров) закупки компьютеров британской фирмы ICL (а не тогдашнего законодателя мод - фирмы IBM). Один из них попал в ИПУ, где группе Арлазарова пришлось быть первопроходцами пакетной многозадачной работы на компьютере. До этого программисты работали в кодах, которые отлаживались непосредственно за пультами, а тут пришлось пользоваться языками программирования. Именно пришлось, потому что многозадачный режим не допускал традиционного в то время ручного закрепления областей памяти за кусками программ и переменными. А сделать “плавающую” по памяти программу в кодах практически невозможно. Языки же программирования (Фортран и Ассемблер) казались насилием над творческой мыслью. В результате дорогая и мощная (по тем временам) техника почти все время простаивала. В основном ее загружали двумя задачами. Одна - расчет специалистами Института физики Земли возможности землетрясений, в результате чего было предсказано невероятное (с точки зрения сейсмологов) землетрясение в Румынии. Вторая - разработка шахматной программы на базе старой программы ИТЭФ.
Михаил Донской
К 1972 г. была сделана приличная шахматная программа и газета “Комсомольская правда” (тогда очень популярная) организовала матч этой программы с читателями. Потребовалось громкое название, и шахматный обозреватель “Комсомолки” А. Хенкин придумал слово “Каисса”. Регламент матча был прост. Каждая сторона играла одну партию белыми, а другую - черными. За неделю делался ход каждой стороной. Ходы читателей выбирались по числу голосов. “Каиссу” тоже никто не контролировал, но мы этим не пользовались.
В субботу выходила газета с очередной позицией, до вторника приходили письма, в четверг ночью “Каисса” просчитывала свои ответы. Матч занял почти год - с января по ноябрь - и закончился победой людей со счетом 1,5 на 0,5. Те, кто помнят жаркое лето 1972 г., могут позавидовать авторам “Каиссы”, проводившим пару дней в неделю в кондиционированном машинном зале - самом прохладном месте Москвы.
Матч привлек внимание всего мира (я знаю даже иностранца, выучившего кириллицу и немножко русский язык, чтобы быть в курсе игры), и нас пригласили участвовать в чемпионате мира 1974 г.
Начиная с 1972 г. в США и Канаде проходили ежегодные чемпионаты Северной Америки среди шахматных программ, организованные ACM. Матч “Каиссы” навел организаторов этих турниров на мысль провести чемпионат мира, организацию которого в рамках своего регулярного конгресса взяла на себя ИФИП.
Были “приглашены” 16 программ из разных европейских стран, Канады и США. О чемпионате было заявлено заранее. Он проходил в одном из лучших отелей Стокгольма. Билеты в концертный зал отеля, где сидели участники, продавались, и недешево. Впрочем, тогда Швеция была одной из самых богатых стран мира.
Естественно, притащить мэйнфреймы со всего мира в Стокгольм не представлялось возможным. Компьютеры-заменители тоже нашлись не для всех участников, поэтому основным средством связи был телефон (не Интернет, а обычный телефон). В машинных залах, где играли программы-участники, находились специальные представители ИФИП, в чью задачу входил контроль за тем, чтобы программисты не вмешивались в ход партий.
А в турнирном зале с телефонными трубками в руках сидели авторы программ. Регламент турнира требовал присутствия в зале именно автора программы (или одного из них, если их было несколько, как в нашем случае), а не представителя (а то вряд ли бы мне пришлось побывать в Стокгольме - представители у нас тогда были на все случаи жизни).
Основное отличие чемпионата программ от обычного шахматного турнира - дикий шум в зале. Во-первых, участники были вынуждены кричать в трубку. Я оказался счастливым исключением - связь с Москвой работала великолепно, потому что была организована по специальному совместному решению трех ведомств: Комитета по науке и технике, Министерства связи и еще одного Комитета. Впрочем, никакого секрета мои телефонные переговоры не представляли, потому что они по громкой связи транслировались в конференц-зал ИПУ, где собирались наши болельщики.
Дополнительный шум в турнирном зале создавали зрители, громко комментировавшие ходы участников (весьма далекие от идеала). Много новых русских слов услышал почтенный зал в эти четыре дня. Главный судья турнира - британец Дэвид Леви, шахматист и шахматный журналист - комментировал партии для зрителей. Дэвид хорошо представлял возможности шахматных программ и очень часто угадывал ходы.
Наконец, что было для меня самым главным, прямо за столиком переговаривались авторы программ. Пока программы думали над ходами, их авторы проводили весьма специфическую научную конференцию, ведь для многих это была первая встреча группы людей, подружившихся потом на долгие годы. Партии не откладывались, а игрались до конца (одна заняла не только вечер, но и всю ночь). Для участников в зале был открыт бар, где можно было не только выпить, но и поговорить обо всем на свете. Со мной общались, как с инопланетянином. Сведения о размере моей квартирной платы были восприняты как прямая пропаганда. (Потом, в Москве, у меня в гостях, один из участников турнира признал, что дороже за такую квартиру платить и не следует.)
Я выделялся из остальных участников не только своим социалистическим происхождением, но и еще двумя вещами. Я был, несмотря на всю силу советской шахматной школы, заведомо слабейшим шахматистом из всех авторов программ. Мое участие в обсуждении позиций быстро было признано излишним. Кроме того, я был единственным участником, претендовавшим на второе место в чемпионате (это - именно то, что я обещал компетентным людям в Москве), все же остальные претендовали только на первое. В результате все обернулось наоборот, именно “Каисса” заняла первое место. Мне была вручена для “Каиссы” золотая (в смысле из чистого золота) медаль чемпиона мира среди шахматных программ, сданная потом на хранение в ИПУ. В годы перестройки ее след затерялся в музеях различных шахматных клубов, куда она передавалась без согласия членов авторского коллектива.
С точки зрения силы шахматных программ первому чемпионату мира похвастать нечем. “Каисса” играла в силу слабого первого разряда, что сейчас не котируется даже среди программ для персональных компьютеров. Зато с научной точки зрения первый чемпионат был прорывом сразу по нескольким направлениям. Тонкие методы сокращения перебора (названные теми, кто их не смог понять, “грубой силой”), обдумывание хода параллельно с противником, дебютные справочные на основе баз данных, нетривиальные алгоритмы распределения времени на обдумывание - все это сейчас кажется очевидным, но всерьез после этого в алгоритмах продвинулась только одна группа Deep Blue, которая заслуженно победила в матче с Каспаровым.
Научная общественность адекватно отреагировала на чемпионаты мира среди шахматных программ. Игра в шахматы перестала считаться проблемой искусственного интеллекта, уступив место экспертным системам. В итоге сегодня в области искусственного интеллекта работает мало серьезных ученых. Дело в том, что уровень качества шахматных программ легко оценить объективно (в отличие от экспертной системы). Долгое время шахматные программы были полигоном для отработки методов принятия решений. А сейчас, когда нет ориентиров, очень трудно понять, работает метод или просто его автор умеет убедительно говорить.
Но трудные задачи никуда не делись и среди них много таких, где качество результата можно оценить объективно. Туда и двинулось большинство серьезных специалистов, ранее занимавшихся искусственным интеллектом. Особенно много их работает в области взаимодействия компьютера и человека (проще говоря, пользовательского интерфейса). Но это уже другая история.
Официальная справка
“Каисса” участвовала в первых трех чемпионатах мира среди шахматных программ (1974, 1977, 1980 гг.) и заняла соответственно первое, второе и четвертое места. Официально авторами “Каиссы” являются Г. Адельсон-Вельский, В. Арлазаров и М. Донской. Непосредственно над программой работали А. Битман, А. Бараев, А. Усков, А. Леман, М. Розенфельд.
Г. Адельсон-Вельский - один из первых советских программистов (вместе с А. Кронродом, А. Брудно, Г. Ландисом и др.). Занимался программами, связанными с ядерной физикой, в ИТЭФ, где придумал много алгоритмов, ставших классическими. Особо следует отметить равновесные бинарные деревья, которые во всем мире называются АВЛ-деревья по именам авторов - Адельсона-Вельского и Ландиса. После кратковременного преподавания в МГУ работал в ИПУ и ВНИИСИ над дискретными алгоритмами, сетевым планированием и искусственным интеллектом. Сейчас живет в Израиле и работает в “Технионе” над проблемами NP полных задач.
В. Арлазаров - создатель оригинальной советской СУБД ИНЕС, на базе которой было сделано много информационных систем разного уровня. Всю жизнь работал над программами распознавания. В настоящее время - Генеральный директор компании Cognitive Technologies, знаменитой своей OCR-системой Cuineform и системой “Евфрат”.
М. Донской - автор архивной системы ИНЕС, бывшей основой системной поддержки многих ВЦ на базе ЕС ЭВМ. В последнее время занимается проблемами пользовательского интерфейса. Сейчас - Генеральный директор фирмы ДИСКо (Donskoy Interactive Software Company), известной “ДИСКо-Командиром”, рядом продуктов для Интернета (“ДИСКо-Качалка” и др.).
С 14 по 20 июня этого года в г. Падерборне (ФРГ) пройдет очередной чемпионат мира среди шахматных программ. Как признание заслуг авторского коллектива “Каиссы” в развитии шахматного программирования на чемпионат, в качестве почетного гостя, приглашен М. Донской. Следует упомянуть, что почетными гостями чемпионатов мира в разные годы были К. Шеннон (автор теории информации), К. Томпсон (автор операционной системы Юникс), М. Ботвинник (многократный чемпион мира среди “белковых” шахматистов).
“Каисса”: хронология событий
М. Д.
1963 г. - начало работ над первой советской шахматной программой в Институте теоретической и экспериментальной физики (ИТЭФ) в лаборатории под руководством А. Кронрода. Первые авторы - Г. Адельсон-Вельский, В. Арлазаров, А. Битман, А. Животовский, А. Усков, А. Леман, М. Розенфельд.
1967 г. - первый международный матч шахматных программ. Состязались программа ИТЭФ и программа Стэнфордского университета (Пало-Альто, шт. Калифорния), сделанная под руководством Дж. Мак-Карти. Мак-Карти знаменит тем, что в 1952 г. на пляже в Сан-Диего вместе с А. Тюрингом придумал словосочетание “Искусственный интеллект”, и тем, что стал автором языка ЛИСП - первого языка программирования, созданного специально для задач по проблемам искусственного интеллекта.
Регламент матча - четыре партии. Со стороны Стэнфорда играла одна и та же версия, со стороны ИТЭФ - две, различавшиеся глубиной перебора. Ходы передавались по телеграфу раз в неделю (это в те-то времена из “ядерного” института!). Матч продолжался целый год и закончился со счетом 3:1 в пользу ИТЭФ.
1969 г. - письмо в поддержку несправедливо посаженного в психушку математика Есенина-Вольпина (сына поэта) среди прочих подписали А. Кронрод и Г. Адельсон-Вельский. В результате лаборатория была расформирована и основная ее часть под руководством В. Арлазарова, но без Кронрода, через некоторое время осела в Институте проблем управления.
1970 г. - механико-математический факультет МГУ окончила целая группа учеников Кронрода и Адельсона-Вельского, занимавшаяся в знаменитом семинаре по дискретным алгоритмам. Итоги семинара:
- Г. Адельсону-Вельскому было запрещено преподавать в МГУ;
- М. Кронрод сделал рекордный и неулучшаемый алгоритм сортировки;
- Е. Диниц и А. Карзанов перекроили теорию потоков в сетях;
- А. Карзанов создал качественно новую теорию линейного программирования;
- остальные участники семинара разработали ряд уникальных эффективных алгоритмов для решения классических дискретных задач;
- М. Донской начал работу над алгоритмами сокращения перебора в шахматной программе.
1972 г. - в ИПУ создана новая шахматная программа, сразу вступившая в матч по переписке с читателями газеты “Комсомольская правда”. С легкой руки журналистов “Комсомолки” программа получила имя “Каисса”. Результат матча - полтора на пол-очка в пользу читателей, что тогда было огромным успехом. “Каисса” получила мировую известность, что породило у Ассоциации вычислительной техники (ACM) идею провести чемпионат мира среди шахматных программ.
1974 г., 4 - 8 августа, Стокгольм - первый чемпионат мира среди шахматных программ. Участвовали 12 программ. Регламент - 4 тура по швейцарской системе. Получив 100%-ный результат, “Каисса” становится первым чемпионом мира. Но в ходе турнира ей не пришлось встретиться с сильнейшей американской программой того времени Chess 4.0. Состоялась показательная встреча, закончившаяся вничью и снявшая вопрос о справедливости победы “Каиссы”. Еще раз победу “Каиссы” подтвердил последовавший семинар, на котором были изложены уникальные методы, реализованные в “Каиссе”.
1977 г., июль - вся команда “Каиссы” (В. Арлазаров, Г. Адельсон-Вельский, М. Донской и др.) переходит из ИПУ в Институт системных исследований.
1977 г., 6 - 9 августа, Торонто - второй чемпионат среди шахматных программ. Chess 4.0 берет реванш и становится чемпионом мира. “Каисса” делит второе место с американской же программой Duchess.
1980 г., сентябрь - последнее выступление “Каиссы” на чемпионате мира. Результат - поделенные места с четвертого по седьмое. Отставание в используемой вычислительной базе делает бессмысленными дальнейшие выступления “Каиссы” на чемпионатах мира.
