Как советская машина всех в шахматы обыграла
Источник
«Каисса» — одна из первых прикладных программ, которая показала результат лучше 99,9% людей-профессионалов в мире. В 1974 году в Стокгольме прошёл знаменательный шахматный чемпионат: впервые в истории за звание чемпиона мира сражались не люди, а машины — 13 компьютерных программ из восьми стран.
Компьютеры в те годы были не чета нынешней мелочи: они были весом по нескольку тонн, а площадью с несколько квартир. Сами они в Стокгольм, конечно, не поехали: ходы делались дистанционно, по телефону.
Советский Союз на этом турнире представляла «Каисса» — программа, в судьбе которой переплелись атомная промышленность, битва с коллективным разумом читателей «Комсомольской правды» и шахматисты-любители.
Началась эта история в Институте теоретической и экспериментальной физики (ИТЭФ) — закрытом учреждении, принадлежавшем Министерству среднего машиностроения. И здесь стоит сказать, что среднее машиностроение — это не про такие тракторы, которые крупнее маленьких, но меньше тяжёлых. В Советском Союзе это министерство курировало атомную промышленность — как гражданскую, так и занимавшуюся производством ядерных зарядов.
Именно здесь в 60-х годах группа математиков создала одну из первых в СССР шахматных компьютерных программ, из которой в дальнейшем выросла «Каисса».
Кажется, что это звучит не очень по атомно-промышленному.
Но руководитель института, академик Абрам Алиханов, хорошо понимал: нельзя заваливать математиков одними только практическими задачами, они от этого просто выгорят или, чего доброго, уволятся. Поэтому он сквозь пальцы смотрел на то, что часть времени математики тратят на собственный проект.
Руководил лабораторией Александр Кронрод — один из основоположников отечественного программирования.
Вот он
Кронрод был уверен, что для создания полноценного ИИ мало научить программу быстро считать. Она должна решать логические задачи, анализировать ситуацию, выбирать из нескольких вариантов. То есть делать то, что мы привыкли считать человеческим. Идеальным полигоном для отработки таких навыков стали игры, ведь на их основе можно не только оценить уровень программы (победил я — я умнее, победила программа — она умнее), но и посмотреть, как она «думает» и принимает решения.
Сотрудники лаборатории написали программы для самых разных игр — от крестиков-ноликов до преферанса. Однако самой сложной и желанной целью были шахматы, ведь в них даже сами люди играют неидеально: допускают ошибки, экспериментируют, придумывают новые стратегии.
Оказалось, что придумать алгоритм, с помощью которого можно играть в шахматы, — это задача со звёздочкой.
И вот почему
Программы, играющие в игры, обычно использовали алгоритм Минимакс. Работает он, если очень коротко, так:
- Сначала программа просчитывает все возможные ходы до конца партии. В результате получается что-то типа дерева, где в начальной части — нынешняя позиция, а в конце — «листья»: все возможные исходы данной партии.
- Затем программа выбирает те исходы, которые её устраивают, например, в крестиках-ноликах это все варианты типа «я играю крестиками, и на поле есть три крестика в ряд». Этим «листьям» присваивается максимальный приоритет, а тем, в которых программа проигрывает («три нолика в ряд»), — минимальный.
- Между «листиком»-целью и стартовой позицией оказывается «дерево» из нескольких десятков или сотен развилок — это моменты, в которые программа или её оппонент по очереди делают ходы. Программа, понятное дело, стремится при этом прийти к цели, у которой максимальный приоритет, а минимальный, в свою очередь, интересует оппонента. Пользуясь этими правилами, программа может составить такую последовательность решений, которая приведёт её к победе. Ну или к ничьей, если победа невозможна.
В случае с шахматами эта идея ломается уже на первом этапе. Брутфорсить шахматы очень и очень вычислительно дорого. Если на первом ходу у вас 40 возможных действий (по два на каждую пешку и каждого коня), то уже к третьему количество вариантов возрастает до 15 миллионов. Поэтому нужно было либо заниматься селективным поиском «листьев», либо уменьшать неопределённость за счёт дебютных таблиц (в конце партии при меньшем числе фигур возможен и полный перебор), либо придумывать что-то ещё, например, случайное сэмплирование.
Рождение «Каиссы»
Советские математики решили искусственно ограничить область поиска программы: она рассчитывала варианты не до конца партии, а на несколько ходов вперёд. Для этого программу научили выбирать более или менее выгодные результаты, а также придумали систему оценки. Съел чужого коня — хорошо, потерял своего ферзя — плохо. В расчёт принимались не только стоимость отдельных фигур, но и их позиция — количество возможных ходов, которые можно сделать с той или иной клетки.
Программа ИТЭФ успешно научилась это делать и играла, по отзывам современников, на уровне шахматиста третьего разряда. Более того, в 1967 году она впервые в истории сразилась с другой программой — детищем американского Стэнфордского университета.
И победила со счётом 3:1.
Однако она обладала рядом недостатков, например, работала на относительно старой тёплой и ламповой ЭВМ М-20. На просчёт одного хода могло уйти два дня. Точнее, две ночи, потому что днём машина решала задачи среднего машиностроения.
Так выглядела М-20
Другой проблемой было то, что первую программу написали на машинном коде: это была последовательность нулей и единиц. Для машины это, само собой, было удобно, а для человека — не очень. К тому же в этом случае программа зависит от конкретной архитектуры процессора, поэтому перенос с одного компьютера на другой проблематичен. Из-за этого, когда в 70-х годах на основе старой программы создавали новую для недавно купленного ICL 4–70, её писали на ассемблере.
Потому что мнемоники ассемблера облегчают взаимопонимание.
Примерно такой
Правда, заниматься этим пришлось уже ученикам Александра Кронрода. Основной костяк авторов — это Владимир Арлазаров, Георгий Адельсон-Вельский, Анатолий Усков и Михаил Донской. Самого же учёного в 1968 году уволили за то, что он подписал открытое письмо в защиту коллеги, подвергшегося политическим репрессиям.
Вот эти ребята (Владимир Арлазаров, Анатолий Усков, Михаил Донской)
Команда лаборатории после этого перешла в Институт автоматики и телемеханики. Именно здесь в 1972 году родилась «Каисса». Программу назвали в честь придуманной в XVI веке греческой дриады, покровительницы шахмат.
Как думать быстрее, если ты медленный
Одной из главных проблем была низкая производительность компьютеров тех лет. Создатели «Каиссы» не могли модернизировать железо, поэтому решили пойти другим путём: они научили программу лучше и эффективнее думать. Для того чтобы ускорить процесс, использовали эвристику и альфа-бета-отсечение.
Когда компьютер проверял свои возможные ходы, он игнорировал все варианты действий, которые были менее выгодными, чем уже проверенные. То же самое, только со знаком минус, он делал при анализе возможных действий своего оппонента: если противник может безнаказанно забрать ферзя, то он, скорее всего, это и сделает.
Нет смысла тратить время на проверку всего «дерева» решений для других вариантов.
Ещё больше эффективности добавило применение эвристики нулевого хода. Её принцип заключается в том, что если в какой-то момент позиция игрока станет настолько хорошей, что он может без последствий пропустить следующий ход, то оппонент, очевидно, такого хода никогда не сделает.
Так что и его, и все проистекающие из него ходы также можно отсечь и не анализировать.
Кроме того, создатели «Каиссы» сделали несколько принципиальных нововведений. Так, они первыми придумали представлять доску в виде числа, ведь клеток на ней — 8×8, то есть 64 штуки. Значит, расположение фигур на доске можно представить в виде 64-значного числа. Точнее, в виде системы из нескольких таких чисел: для своих пешек, для вражеских, для своих коней, для короля и т. д.
А числа — это то, с чем компьютер справляется лучше всего, так что за счёт этого можно оптимизировать процесс.
Другое решение позволило уйти от стратегической слепоты, которая была бичом шахматных программ. В шахматах многое зависит от дебюта, от того, какие ходы будут сделаны в начале партии. И компьютер, который видел всего на несколько ходов вперёд, не мог понять, к чему в итоге приведут его действия. Обойти это ограничение удалось с помощью дебютной книги — небольшой базы данных, в которую было записано 10 тысяч возможных ходов начала партии. Пользуясь этими знаниями, своего рода коллективным опытом поколений живых программистов, компьютер избегал серьёзных ошибок на старте.
Михаил Донской, один из создателей «Каиссы», на чемпионате в Стокгольме
Последний козырь разработчики вытащили уже на том самом соревновании в Стокгольме.
Программа начинала анализировать ситуацию не в тот момент, когда к ней переходил ход, а в тот, когда его отдавала, и таким образом могла использовать не только своё время, но и те часы, когда над ответным ходом думал оппонент.
Просто, гениально и ничего незаконного: люди ведь тоже так делают!
Машина против человечества
Перед тем как побороться за мировое первенство, «Каисса» испытала свои силы на человеке. Точнее, на людях. Программа провела два матча с читателями газет: сначала — с «Уральским рабочим», а затем — с «Комсомольской правдой». Схема была простой: газета публикует ход программы, затем читатели в течение нескольких дней шлют свои варианты ответа. Редакция выбирает самый популярный, после чего его вводят в систему, «Каисса» делает новый ход, и всё повторяется.
Столкновение с человечеством на тот момент закончилось вничью: если у читателей «Уральского рабочего» программа выиграла, то более широкой аудитории «Комсомолки» проиграла.
Шли партии, прямо скажем, небыстро: один из иностранных фанатов шахмат успел даже выучить основы русского языка, чтобы следить за матчем в оригинале. Следил не он один: история получила широкую известность за границей и стала одной из причин, по которым советскую программу позвали на чемпионат в Стокгольме.
Сам чемпионат проходил по швейцарской системе: каждая программа играла с четырьмя противниками. В результате «Каисса» заняла первое место, победив во всех четырёх партиях американские программы Ostrich, CHAOS и Tech II, а также австрийскую Frantz. Правда, в число её оппонентов не попала другая программа-лидер — Chess 4, набравшая три очка. Поэтому после матча провели ещё одну — дополнительную — партию, которую лидеры закончили вничью.
«Каисса» ещё дважды участвовала в мировых чемпионатах, но «золота» больше не получила. В 1977 году в Торонто она заняла второе-третье места, а в 1980-м в Линце — 5-е –11-е. Причин у этого было две, и первая понятна: ICL 4–70 к тому времени устарел, а оппоненты переходили на более современные и мощные компьютеры. Кроме того, что немаловажно, в то время подобные чемпионаты воспринимались не как соревнование, а как конференция по обмену опытом.
Создатели компьютерных программ охотно делились с коллегами найденными решениями, и козыри «Каиссы», такие, как альфа-бета-отсечение, эвристические механизмы выбора наиболее удачного хода, представление доски в виде числа быстро пошли в народ. Вскоре эти решения стали стандартами для шахматных программ по всему миру, и многие используются до сих пор.
Владимир Арлазаров призадумался
Сами же создатели советского чемпиона постепенно охладели к мировым соревнованиям. По словам Владимира Арлазарова, со временем эти состязания коммерциализировались, и создатели программ начали секретить принципы их работы.
У советских математиков такой подход вызвал отторжение.
«Мы учёные. То, что мы сегодня придумали, завтра будут знать все. Иначе какие же мы учёные?» — сказал по этому поводу сам Арлазаров.
