| alekhin | Date: Суббота, 14.02.2009, 05:59:30 | Message # 1 |
Авторитет
Группа: Чемпион месяца
Сообщения: 1118
Признак жизни: Offline
| «Каисса» – первый чемпион мира по шахматам среди компьютеров
Научить компьютер играть в шахматы — одна из самых интересных задач в сфере искусственного интеллекта. Она была поставлена уже на заре вычислительной техники, в конце 50-х годов. В шахматах существуют определенные уровни мастерства, степени качества игры, которые могут дать четкие критерии интеллектуального роста машины. Поэтому компьютерными шахматами активно занимались ученые умы во всем мире. Но шахматы — игра, соревнование, и чтобы продемонстрировать свои логические способности, компьютеру необходим непосредственный противник. В 1974 году впервые прошел чемпионат мира по шахматам не между людьми, а между компьютерными программами. Победителем этого состязания стала советская шахматная программа «Каисса».
«Каисса» (была такая богиня, покровительница шахмат) создавалась в Москве, в Институте проблем управления Академии наук. Возможностями ЭВМ играть в шахматы здесь всерьез заинтересовались еще в середине 60-х, и уже в 1967 году одна из разработанных нашими программистами систем играла с американской шахматной программой. В начале 70–х в мире накопилось такое количество шахматных разработок, что встал вопрос о создании ассоциации шахматного программирования. Такая ассоциация была образована при поддержке крупнейшей международной организации по информатике International Federation of Information Processing (IFIP). А первый чемпионат мира среди шахматных программ в 1974 году прошел в рамках очередного конгресса IFIP (такие конгрессы собирались раз в три года) в Стокгольме.
Надо помнить габариты тогдашних ЭВМ, на которых работали программы-участники. «Каисса», например, разрабатывалась на машине фирмы ICL, занимавшей в институте зал площадью примерно в 150 кв. метров. Размеры остальных претендентов, как правило, были не менее внушительны. Поэтому разместить непосредственно в Стокгольме удалось только две-три машины, а остальные участники чемпионата общались между собой по телефону (мы имеем в виду, конечно, разработчиков, а не компьютеры). В зале, где происходил конгресс, находились представители команд каждой страны, а к тем ЭВМ, на которых выполнялись шахматные программы, IFIP отправила своих наблюдателей. Они должны были лично удостовериться в том, что играет действительно машина.
Владимир Львович Арлазаров, один из основных разработчиков «Каиссы», рассказывает, что в течение четырех дней 16 участников чемпионата играли друг с другом по швейцарской системе. Каждая команда участвовала в четырех партиях, и победителем становилась программа, набравшая наибольшее число очков.
Победа советской шахматной программы была неожиданной. Все прочили лавры чемпиона американской разработке Chess 4, которую, как это умеют делать американцы, широко разрекламировали в преддверии первого мирового состязания. Создатели «Каиссы» не готовили программу специально к чемпионату. Как мы уже отмечали, шахматное программирование представлялось одной из наиболее интересных задач искусственного интеллекта, на которой лучше всего проверялись методы перебора. Как отмечает Владимир Арлазаров, сейчас ни одна шахматная программа не обходится без использования этих методов, но в те годы у такого «переборного» пути шахматного программирования было немало оппонентов. Разработчики «Каиссы» ставили перед собой сложную задачу — добиться результата как при очень глубоком переборе, но при этом суметь уложиться в конечное время. Победа на чемпионате по компьютерным шахматам свидетельствовала, что эту задачу удалось с успехом решить.
Можно было бы предположить, что шахматную программу должны писать никак не меньше чем кандидаты в мастера. Однако это было не так. В команде разработчиков программы-чемпиона, лидерами которой были Владимир Арлазаров, Михаил Донской и Георгий Адельсон-Вельский, большинство даже не имели разряда. В сочетании «шахматное программирование» на первом месте стоит именно программирование, и для создания эффективной шахматной программы нужны были классные профессионалы в этом деле. А у крупных шахматистов компьютерные шахматы, как правило, не вызывали большого интереса. Это была прежде всего научная задача, а чемпионат мира — научное мероприятие, на котором шло не только соревнование, но и интенсивный обмен идеями. Это потом, в 80-е, особенно с появлением персональной вычислительной техники, создание шахматных программ стало занятием сугубо коммерческим, а в научной сфере интерес к ней постепенно угасал. Коммерция была несовместима со свободным обменом научной информацией.
Надо отметить, что к 1974 году уровень ЭВМ как шахматных игроков был не очень высок.
Машина, победившая на первом компьютерном чемпионате, оценивалась как шахматист третьего разряда. Фактически это первый серьезный уровень, соответствующий игре нормального шахматиста, а не просто человека, знающего, как ходят фигуры. Успех программы в некоторой степени определялся и мощностью вычислительной машины. Участники чемпионата были вольны выбирать, на какой технике они представят свою шахматную разработку, потому оказывались не совсем в равных условиях. Однако накладывать какие-либо ограничения было невозможно — участие в чемпионате поддерживалось теми фирмами и организациями, в которых использовалась машина, либо теми, которые сами производили машины, и для них это была, конечно, прекрасная возможность прорекламировать свои разработки.
Наша команда должна была довольствоваться тем, что имела. И понимая, что делают программу не на самой мощной машине, разработчики стремились компенсировать отставание в быстродействии предельно тщательным подходом к программированию. Именно поэтому был выбран язык Ассемблер.
Конечно, победа «Каиссы» на мировом чемпионате по компьютерным шахматам не могла пройти незамеченной. В стране это событие было воспринято прежде всего как большой успех советской науки. О программе-чемпионе сразу заговорили, появились публикации в центральной прессе. Сам первый чемпионат получил большой резонанс в мире. Он наглядно продемонстрировал всем, что вычислительные машины могут самостоятельно решать такие сложные логические задачи, как игра в шахматы. Проигрыш русским подстегнул американцев, и после 1974 года в исследования по шахматному программированию стали делаться очень серьезные финансовые вложения. Фактически 1974 год положил начало новому, более серьезному этапу в развитии шахматного программирования. До середины 80-х чемпионаты мира по шахматам между вычислительными машинами проходили с той же регулярностью, что и конгрессы IFIP. Мы продолжали принимать в них участие, но с ростом коммерциализации компьютерных шахмат эта задача потеряла для наших разработчиков научный интерес. Кроме того, отставание советской вычислительной техники от западной, где уже появлялись специализированные шахматные машины, росло с угрожающей скоростью, и мы в конце концов потеряли возможность соревноваться на равных.
История “Каиссы”
Сейчас уже трудно себе представить эру мэйнфреймов — больших компьютеров, каждый из которых занимал приличный зал. Но в начале 70-х это было последним писком. В те годы компьютеры только начали появляться в далеких от военных нужд областях. По непонятным причинам в это время в СССР были произведены "массовые" (пяток экземпляров) закупки компьютеров британской фирмы ICL (а не тогдашнего законодателя мод — фирмы IBM). Один из них попал в ИПУ, где группе Арлазарова пришлось быть первопроходцами пакетной многозадачной работы на компьютере. До этого программисты работали в кодах, которые отлаживались непосредственно за пультами, а тут пришлось пользоваться языками программирования. Именно пришлось, потому что многозадачный режим не допускал традиционного в то время ручного закрепления областей памяти за кусками программ и переменными. А сделать "плавающую" по памяти программу в кодах практически невозможно. Языки же программирования (Фортран и Ассемблер) казались насилием над творческой мыслью. В результате дорогая и мощная (по тем временам) техника почти все время простаивала. В основном ее загружали двумя задачами. Одна — расчет специалистами Института физики Земли возможности землетрясений, в результате чего было предсказано невероятное (с точки зрения сейсмологов) землетрясение в Румынии. Вторая — разработка шахматной программы на базе старой программы ИТЭФ.
К 1972 г. была сделана приличная шахматная программа и газета "Комсомольская правда" (тогда очень популярная) организовала матч этой программы с читателями. Потребовалось громкое название, и шахматный обозреватель "Комсомолки" А. Хенкин придумал слово "Каисса". Регламент матча был прост. Каждая сторона играла одну партию белыми, а другую — черными. За неделю делался ход каждой стороной. Ходы читателей выбирались по числу голосов. "Каиссу" тоже никто не контролировал, но мы этим не пользовались.
В субботу выходила газета с очередной позицией, до вторника приходили письма, в четверг ночью "Каисса" просчитывала свои ответы. Матч занял почти год — с января по ноябрь — и закончился победой людей со счетом 1,5 на 0,5. Те, кто помнят жаркое лето 1972 г., могут позавидовать авторам "Каиссы", проводившим пару дней в неделю в кондиционированном машинном зале — самом прохладном месте Москвы.
Матч привлек внимание всего мира (я знаю даже иностранца, выучившего кириллицу и немножко русский язык, чтобы быть в курсе игры), и нас пригласили участвовать в чемпионате мира 1974 г.
Начиная с 1972 г. в США и Канаде проходили ежегодные чемпионаты Северной Америки среди шахматных программ, организованные ACM. Матч "Каиссы" навел организаторов этих турниров на мысль провести чемпионат мира, организацию которого в рамках своего регулярного конгресса взяла на себя ИФИП.
Были "приглашены" 16 программ из разных европейских стран, Канады и США. О чемпионате было заявлено заранее. Он проходил в одном из лучших отелей Стокгольма. Билеты в концертный зал отеля, где сидели участники, продавались, и недешево. Впрочем, тогда Швеция была одной из самых богатых стран мира.
Естественно, притащить мэйнфреймы со всего мира в Стокгольм не представлялось возможным. Компьютеры-заменители тоже нашлись не для всех участников, поэтому основным средством связи был телефон (не Интернет, а обычный телефон). В машинных залах, где играли программы-участники, находились специальные представители ИФИП, в чью задачу входил контроль за тем, чтобы программисты не вмешивались в ход партий.
А в турнирном зале с телефонными трубками в руках сидели авторы программ. Регламент турнира требовал присутствия в зале именно автора программы (или одного из них, если их было несколько, как в нашем случае), а не представителя (а то вряд ли бы мне пришлось побывать в Стокгольме — представители у нас тогда были на все случаи жизни).
"Каисса": хронология событий
1963 г. — начало работ над первой советской шахматной программой в Институте теоретической и экспериментальной физики (ИТЭФ) в лаборатории под руководством А. Кронрода. Первые авторы — Г. Адельсон-Вельский, В. Арлазаров, А. Битман, А. Животовский, А. Усков, А. Леман, М. Розенфельд.
1967 г. — первый международный матч шахматных программ. Состязались программа ИТЭФ и программа Стэнфордского университета (Пало-Альто, шт. Калифорния), сделанная под руководством Дж. Мак-Карти. Мак-Карти знаменит тем, что в 1952 г. на пляже в Сан-Диего вместе с А. Тюрингом придумал словосочетание "Искусственный интеллект", и тем, что стал автором языка ЛИСП — первого языка программирования, созданного специально для задач по проблемам искусственного интеллекта.
Регламент матча — четыре партии. Со стороны Стэнфорда играла одна и та же версия, со стороны ИТЭФ — две, различавшиеся глубиной перебора. Ходы передавались по телеграфу раз в неделю (это в те-то времена из "ядерного" института!). Матч продолжался целый год и закончился со счетом 3:1 в пользу ИТЭФ.
1969 г. — письмо в поддержку несправедливо посаженного в психушку математика Есенина-Вольпина (сына поэта) среди прочих подписали А. Кронрод и Г. Адельсон-Вельский. В результате лаборатория была расформирована и основная ее часть под руководством В. Арлазарова, но без Кронрода, через некоторое время осела в Инcтитуте проблем управления.
1970 г. — механико-математический факультет МГУ окончила целая группа учеников Кронрода и Адельсона-Вельского, занимавшаяся в знаменитом семинаре по дискретным алгоритмам. Итоги семинара:
Г. Адельсону-Вельскому было запрещено преподавать в МГУ;
М. Кронрод сделал рекордный и неулучшаемый алгоритм сортировки;
Е. Диниц и А. Карзанов перекроили теорию потоков в сетях;
А. Карзанов создал качественно новую теорию линейного программирования;
остальные участники семинара разработали ряд уникальных эффективных алгоритмов для решения классических дискретных задач;
М. Донской начал работу над алгоритмами сокращения перебора в шахматной программе.
1972 г. — в ИПУ создана новая шахматная программа, сразу вступившая в матч по переписке с читателями газеты "Комсомольская правда". С легкой руки журналистов "Комсомолки" программа получила имя "Каисса". Результат матча — полтора на пол-очка в пользу читателей, что тогда было огромным успехом. "Каисса" получила мировую известность, что породило у Ассоциации вычислительной техники (ACM) идею провести чемпионат мира среди шахматных программ.
1974 г., 4—8 августа, Стокгольм — первый чемпионат мира среди шахматных программ. Участвовали 12 программ. Регламент — 4 тура по швейцарской системе. Получив 100%-ный результат, "Каисса" становится первым чемпионом мира. Но в ходе турнира ей не пришлось встретиться с сильнейшей американской программой того времени Chess 4.0. Состоялась показательная встреча, закончившаяся вничью и снявшая вопрос о справедливости победы "Каиссы". Еще раз победу "Каиссы" подтвердил последовавший семинар, на котором были изложены уникальные методы, реализованные в "Каиссе".
1977 г., июль — вся команда "Каиссы" (В. Арлазаров, Г. Адельсон-Вельский, М. Донской и др.) переходит из ИПУ в Институт системных исследований.
1977 г., 6—9 августа, Торонто — второй чемпионат среди шахматных программ. Chess 4.0 берет реванш и становится чемпионом мира. "Каисса" делит второе место с американской же программой Duchess.
1980 г., сентябрь — последнее выступление "Каиссы" на чемпионате мира. Результат — поделенные места с четвертого по седьмое. Отставание в используемой вычислительной базе делает бессмысленными дальнейшие выступления "Каиссы" на чемпионатах мира.
Основное отличие чемпионата программ от обычного шахматного турнира — дикий шум в зале. Во-первых, участники были вынуждены кричать в трубку. Я оказался счастливым исключением — связь с Москвой работала великолепно, потому что была организована по специальному совместному решению трех ведомств: Комитета по науке и технике, Министерства связи и еще одного Комитета. Впрочем, никакого секрета мои телефонные переговоры не представляли, потому что они по громкой связи транслировались в конференц-зал ИПУ, где собирались наши болельщики.
Дополнительный шум в турнирном зале создавали зрители, громко комментировавшие ходы участников (весьма далекие от идеала). Много новых русских слов услышал почтенный зал в эти четыре дня. Главный судья турнира — британец Дэвид Леви, шахматист и шахматный журналист — комментировал партии для зрителей. Дэвид хорошо представлял возможности шахматных программ и очень часто угадывал ходы.
Наконец, что было для меня самым главным, прямо за столиком переговаривались авторы программ. Пока программы думали над ходами, их авторы проводили весьма специфическую научную конференцию, ведь для многих это была первая встреча группы людей, подружившихся потом на долгие годы. Партии не откладывались, а игрались до конца (одна заняла не только вечер, но и всю ночь). Для участников в зале был открыт бар, где можно было не только выпить, но и поговорить обо всем на свете. Со мной общались, как с инопланетянином. Сведения о размере моей квартирной платы были восприняты как прямая пропаганда. (Потом, в Москве, у меня в гостях, один из участников турнира признал, что дороже за такую квартиру платить и не следует.)
Я выделялся из остальных участников не только своим социалистическим происхождением, но и еще двумя вещами. Я был, несмотря на всю силу советской шахматной школы, заведомо слабейшим шахматистом из всех авторов программ. Мое участие в обсуждении позиций быстро было признано излишним. Кроме того, я был единственным участником, претендовавшим на второе место в чемпионате (это — именно то, что я обещал компетентным людям в Москве), все же остальные претендовали только на первое. В результате все обернулось наоборот, именно "Каисса" заняла первое место. Мне была вручена для "Каиссы" золотая (в смысле из чистого золота) медаль чемпиона мира среди шахматных программ, сданная потом на хранение в ИПУ. В годы перестройки ее след затерялся в музеях различных шахматных клубов, куда она передавалась без согласия членов авторского коллектива.
С точки зрения силы шахматных программ первому чемпионату мира похвастать нечем. "Каисса" играла в силу слабого первого разряда, что сейчас не котируется даже среди программ для персональных компьютеров. Зато с научной точки зрения первый чемпионат был прорывом сразу по нескольким направлениям. Тонкие методы сокращения перебора (названные теми, кто их не смог понять, "грубой силой"), обдумывание хода параллельно с противником, дебютные справочные на основе баз данных, нетривиальные алгоритмы распределения времени на обдумывание — все это сейчас кажется очевидным, но всерьез после этого в алгоритмах продвинулась только одна группа Deep Blue, которая заслуженно победила в матче с Каспаровым.
Научная общественность адекватно отреагировала на чемпионаты мира среди шахматных программ. Игра в шахматы перестала считаться проблемой искусственного интеллекта, уступив место экспертным системам. В итоге сегодня в области искусственного интеллекта работает мало серьезных ученых. Дело в том, что уровень качества шахматных программ легко оценить объективно (в отличие от экспертной системы). Долгое время шахматные программы были полигоном для отработки методов принятия решений. А сейчас, когда нет ориентиров, очень трудно понять, работает метод или просто его автор умеет убедительно говорить.
Но трудные задачи никуда не делись и среди них много таких, где качество результата можно оценить объективно. Туда и двинулось большинство серьезных специалистов, ранее занимавшихся искусственным интеллектом. Особенно много их работает в области взаимодействия компьютера и человека (проще говоря, пользовательского интерфейса). Но это уже другая история.
Источник
Шахматы учат быть обьективным.(А.Алехин)
|
| |
| |
