Источник
«Каисса» — одна из первых прикладных программ, которая показала результат лучше 99,9 % людей-профессионалов в мире. В 1974 году в Стокгольме прошёл знаменательный шахматный чемпионат: впервые в истории за звание чемпиона мира сражались не люди, а машины — 13 компьютерных программ из восьми стран.
Компьютеры в те годы были не чета нынешней мелочи: они были весом по нескольку тонн, а площадью с несколько квартир. Сами они в Стокгольм, конечно, не поехали: ходы делались дистанционно, по телефону.
Советский Союз на этом турнире представляла «Каисса» — программа, в судьбе которой переплелись атомная промышленность, битва с коллективным разумом читателей «Комсомольской правды» и шахматисты-любители.
Началась эта история в Институте теоретической и экспериментальной физики (ИТЭФ) — закрытом учреждении, принадлежавшем Министерству среднего машиностроения. И здесь стоит сказать, что среднее машиностроение — это не про такие тракторы, которые крупнее маленьких, но меньше тяжёлых. В Советском Союзе это министерство курировало атомную промышленность — как гражданскую, так и занимавшуюся производством ядерных зарядов.
Именно здесь в 60-х годах группа математиков создала одну из первых в СССР шахматных компьютерных программ, из которой в дальнейшем выросла «Каисса».
Кажется, что это звучит не очень по атомно-промышленному.
Но руководитель института, академик Абрам Алиханов, хорошо понимал: нельзя заваливать математиков одними только практическими задачами, они от этого просто выгорят или, чего доброго, уволятся. Поэтому он сквозь пальцы смотрел на то, что часть времени математики тратят на собственный проект.
Руководил лабораторией Александр Кронрод — один из основоположников отечественного программирования.
Вот он
Кронрод был уверен, что для создания полноценного ИИ мало научить программу быстро считать. Она должна решать логические задачи, анализировать ситуацию, выбирать из нескольких вариантов. То есть делать то, что мы привыкли считать человеческим. Идеальным полигоном для отработки таких навыков стали игры, ведь на их основе можно не только оценить уровень программы (победил я — я умнее, победила программа — она умнее), но и посмотреть, как она «думает» и принимает решения.
Сотрудники лаборатории написали программы для самых разных игр — от крестиков-ноликов до преферанса. Однако самой сложной и желанной целью были шахматы, ведь в них даже сами люди играют неидеально: допускают ошибки, экспериментируют, придумывают новые стратегии.
Оказалось, что придумать алгоритм, с помощью которого можно играть в шахматы, — это задача со звёздочкой.
И вот почему
Программы, играющие в игры, обычно использовали алгоритм Минимакс. Работает он, если очень коротко, так:
- Сначала программа просчитывает все возможные ходы до конца партии. В результате получается что-то типа дерева, где в начальной части — нынешняя позиция, а в конце — «листья»: все возможные исходы данной партии.
- Затем программа выбирает те исходы, которые её устраивают, например, в крестиках-ноликах это все варианты типа «я играю крестиками, и на поле есть три крестика в ряд». Этим «листьям» присваивается максимальный приоритет, а тем, в которых программа проигрывает («три нолика в ряд»), — минимальный.
- Между «листиком»-целью и стартовой позицией оказывается «дерево» из нескольких десятков или сотен развилок — это моменты, в которые программа или её оппонент по очереди делают ходы. Программа, понятное дело, стремится при этом прийти к цели, у которой максимальный приоритет, а минимальный, в свою очередь, интересует оппонента. Пользуясь этими правилами, программа может составить такую последовательность решений, которая приведёт её к победе. Ну или к ничьей, если победа невозможна.
В случае с шахматами эта идея ломается уже на первом этапе. Брутфорсить шахматы очень и очень вычислительно дорого. Если на первом ходу у вас 40 возможных действий (по два на каждую пешку и каждого коня), то уже к третьему количество вариантов возрастает до 15 миллионов. Поэтому нужно было либо заниматься селективным поиском «листьев», либо уменьшать неопределённость за счёт дебютных таблиц (в конце партии при меньшем числе фигур возможен и полный перебор), либо придумывать что-то ещё, например, случайное сэмплирование.
Рождение «Каиссы»
Советские математики решили искусственно ограничить область поиска программы: она рассчитывала варианты не до конца партии, а на несколько ходов вперёд. Для этого программу научили выбирать более или менее выгодные результаты, а также придумали систему оценки. Съел чужого коня — хорошо, потерял своего ферзя — плохо. В расчёт принимались не только стоимость отдельных фигур, но и их позиция — количество возможных ходов, которые можно сделать с той или иной клетки.
Программа ИТЭФ успешно научилась это делать и играла, по отзывам современников, на уровне шахматиста третьего разряда. Более того, в 1967 году она впервые в истории сразилась с другой программой — детищем американского Стэнфордского университета.
И победила со счётом 3:1.
Однако она обладала рядом недостатков, например, работала на относительно старой тёплой и ламповой ЭВМ М-20. На просчёт одного хода могло уйти два дня. Точнее, две ночи, потому что днём машина решала задачи среднего машиностроения.
Так выглядела М-20
Другой проблемой было то, что первую программу написали на машинном коде: это была последовательность нулей и единиц. Для машины это, само собой, было удобно, а для человека — не очень. К тому же в этом случае программа зависит от конкретной архитектуры процессора, поэтому перенос с одного компьютера на другой проблематичен. Из-за этого, когда в 70-х годах на основе старой программы создавали новую для недавно купленного ICL 4-70, её писали на ассемблере.
Потому что мнемоники ассемблера облегчают взаимопонимание.
Примерно такой
Правда, заниматься этим пришлось уже ученикам Александра Кронрода. Основной костяк авторов — это Владимир Арлазаров, Георгий Адельсон-Вельский, Анатолий Усков и Михаил Донской. Самого же учёного в 1968 году уволили за то, что он подписал открытое письмо в защиту коллеги, подвергшегося политическим репрессиям.
Вот эти ребята (Владимир Арлазаров, Анатолий Усков, Михаил Донской)
Команда лаборатории после этого перешла в Институт автоматики и телемеханики. Именно здесь в 1972 году родилась «Каисса». Программу назвали в честь придуманной в XVI веке греческой дриады, покровительницы шахмат.
Как думать быстрее, если ты медленный
Одной из главных проблем была низкая производительность компьютеров тех лет. Создатели «Каиссы» не могли модернизировать железо, поэтому решили пойти другим путём: они научили программу лучше и эффективнее думать. Для того чтобы ускорить процесс, использовали эвристику и альфа-бета-отсечение.
Когда компьютер проверял свои возможные ходы, он игнорировал все варианты действий, которые были менее выгодными, чем уже проверенные. То же самое, только со знаком минус, он делал при анализе возможных действий своего оппонента: если противник может безнаказанно забрать ферзя, то он, скорее всего, это и сделает.
Нет смысла тратить время на проверку всего «дерева» решений для других вариантов.
Ещё больше эффективности добавило применение эвристики нулевого хода. Её принцип заключается в том, что если в какой-то момент позиция игрока станет настолько хорошей, что он может без последствий пропустить следующий ход, то оппонент, очевидно, такого хода никогда не сделает.
Так что и его, и все проистекающие из него ходы также можно отсечь и не анализировать.
Кроме того, создатели «Каиссы» сделали несколько принципиальных нововведений. Так, они первыми придумали представлять доску в виде числа, ведь клеток на ней — 8x8, то есть 64 штуки. Значит, расположение фигур на доске можно представить в виде 64-значного числа. Точнее, в виде системы из нескольких таких чисел: для своих пешек, для вражеских, для своих коней, для короля и т. д.
А числа — это то, с чем компьютер справляется лучше всего, так что за счёт этого можно оптимизировать процесс.
Другое решение позволило уйти от стратегической слепоты, которая была бичом шахматных программ. В шахматах многое зависит от дебюта, от того, какие ходы будут сделаны в начале партии. И компьютер, который видел всего на несколько ходов вперёд, не мог понять, к чему в итоге приведут его действия. Обойти это ограничение удалось с помощью дебютной книги — небольшой базы данных, в которую было записано 10 тысяч возможных ходов начала партии. Пользуясь этими знаниями, своего рода коллективным опытом поколений живых шахматистов, компьютер избегал серьёзных ошибок на старте.
Михаил Донской, один из создателей «Каиссы», на чемпионате в Стокгольме
Последний козырь разработчики вытащили уже на том самом соревновании в Стокгольме.
Программа начинала анализировать ситуацию не в тот момент, когда к ней переходил ход, а в тот, когда его отдавала, и таким образом могла использовать не только своё время, но и те часы, когда над ответным ходом думал оппонент.
Просто, гениально и ничего незаконного: люди ведь тоже так делают!
Машина против человечества
Перед тем как побороться за мировое первенство, «Каисса» испытала свои силы на человеке. Точнее, на людях. Программа провела два матча с читателями газет: сначала — с «Уральским рабочим», а затем — с «Комсомольской правдой». Схема была простой: газета публикует ход программы, затем читатели в течение нескольких дней шлют свои варианты ответа. Редакция выбирает самый популярный, после чего его вводят в систему, «Каисса» делает новый ход, и всё повторяется.
Столкновение с человечеством на тот момент закончилось вничью: если у читателей «Уральского рабочего» программа выиграла, то более широкой аудитории «Комсомолки» проиграла.
Шли партии, прямо скажем, небыстро: один из иностранных фанатов шахмат успел даже выучить основы русского языка, чтобы следить за матчем в оригинале. Следил не он один: история получила широкую известность за границей и стала одной из причин, по которым советскую программу позвали на чемпионат в Стокгольме.
Сам чемпионат проходил по швейцарской системе: каждая программа играла с четырьмя противниками. В результате «Каисса» заняла первое место, победив во всех четырёх партиях американские программы Ostrich, CHAOS и Tech II, а также австрийскую Frantz. Правда, в число её оппонентов не попала другая программа-лидер — Chess 4, набравшая три очка. Поэтому после матча провели ещё одну — дополнительную — партию, которую лидеры закончили вничью.
«Каисса» ещё дважды участвовала в мировых чемпионатах, но «золота» больше не получила. В 1977 году в Торонто она заняла второе-третье места, а в 1980-м в Линце — 5-е –11-е. Причин у этого было две, и первая понятна: ICL 4-70 к тому времени устарел, а оппоненты переходили на более современные и мощные компьютеры. Кроме того, что немаловажно, в то время подобные чемпионаты воспринимались не как соревнование, а как конференция по обмену опытом.
Создатели компьютерных программ охотно делились с коллегами найденными решениями, и козыри «Каиссы», такие, как альфа-бета-отсечение, эвристические механизмы выбора наиболее удачного хода, представление доски в виде числа быстро пошли в народ. Вскоре эти решения стали стандартами для шахматных программ по всему миру, и многие используются до сих пор.
Владимир Арлазаров призадумался
Сами же создатели советского чемпиона постепенно охладели к мировым соревнованиям. По словам Владимира Арлазарова, со временем эти состязания коммерциализировались, и создатели программ начали секретить принципы их работы.
У советских математиков такой подход вызвал отторжение.
«Мы учёные. То, что мы сегодня придумали, завтра будут знать все. Иначе какие же мы учёные?» — сказал по этому поводу сам Арлазаров.
Комментарии (22)
ru_vlad
01.08.2024 08:36+1Странно, но не слова о Михаиле Моисеевиче Ботвиннике и его программе Пионер.
valergrad
01.08.2024 08:36+1А зачем?
Из уважения к шахматным достижениям Михаила Моисеевича, об этой неприятной странице его биографии лучше вспоминать пореже. К тому же это будет скорее на тему уголовного права, а не на тему шахматного программирования.
ignatfomenko
01.08.2024 08:36+3https://atimopheyev.narod.ru/AfterPIONEER/inPIONEERsFootsteps.ALL.HTM#Pioneer_Botvinnik тут можете почитать. Попытались там все по этой теме собрать.
valergrad
01.08.2024 08:36+13Если в одном предложении: группа людей свыше 20 лет "занималась" созданием шахматной программы, которая за все это время не сыграла ни одной партии. Для непрограммистов: это примерно как 20 лет "строить" дом на бумаге, и даже не выкопать яму для фундамента.
"Разработка" заключалась в том, что Ботвинник время от времени вспоминал, что он каждый месяц получает зарплату за разработку, придумывал замудренные методы, и пытался объяснить их математикам житейскими словами на русском языке, т.к. за 20 лет не удосужился выучить даже основы программирования чтобы говорить с ними на языке алгоритмов или нарисовать им блок-схему. Математики пытались что-то написать, но получалась, конечно, ерунда, после чего валили все друг на друга: математики на то, что у Ботвинника требования слишком абстрактны и непонятно как их перевести в код, а Ботвинник обвинял их в саботаже и в том, что они не делают то, что он им говорит.
Как только какой-то хитромудрый метод работал на какой-то знаменитой позиции ( на которой Ботвинник его и придумывал), тут же оказывалось что на другой позиции этот алгоритм предлагает полнейшую ерунду. После чего Ботвинник пропадал на несколько лет, а, появившись, предлагал какой-то другой метод, который чтобы реализовать, нужно было переписать все с нуля. После чего оказывалось что метод работает на второй позиции, но не работает на первой.
Разумеется, текучка среди математиков-программистов была существенная, хотя и не такая большая потому что на этой работе можно было годами ничего не делать.
Об уровне работ можно судить по дневниковой записи Ботвинника, в которой он простодушно рассказывает как спустя 10 лет "разработки" случайно выяснилось, что "Пионер" ходит конем с e5 на g5 и вообще делает считает возможными много и других невозможных ходов.
А про историю с этюдом Надареишвили мне даже и не хочется рассказывать, из уважения к Ботвиннику.
Rom77
01.08.2024 08:36Ботвинник не принимал участия в разработке Каиссы. Кроме того, статья слишком маленькая, чтобы упоминать об альтернативных попытках.
qiper
01.08.2024 08:36+2А числа — это то, с чем компьютер справляется лучше всего, так что за счёт этого можно оптимизировать процесс.
Компьютер только с числами и работает, по другому никак
Azimut99
01.08.2024 08:36+4Для справок:
Александр Кронрод - дядя, а Анатолий Усков - отец Ольги Усковой, которую уже прозвали "мать русских роботов".
valergrad
01.08.2024 08:36+11Спасибо за статью, интересно было почитать про организационную сторону дела и про людей!
К сожалению, все что касается примененных алгоритмов в Каиссе описано в стиле "ученый изнасиловал журналиста" и либо полностью неправильно либо сильно переврано.
Для тех кто если вдруг захочет почитать в чем действительно была суть использованных в Каиссе оптимизаций и идей, дам англоязычные названия тех из них, что применяются в шахматном программировании и поныне. По ним вы сможете найти подробную информацию и реализацию, например, в chessprogrammingwiki и других сайтах.
Alpha-beta pruning - альфа-бета отсечение. В силу очевидности идеи скорее всего использовалось всеми программами, т.е. не является фишкой авторов Каиссы.
То, сколько она дает мощи зависит от того насколько хорошо ты сортируешь ходы ( т.е. сильнейшие ходы просматриваешь первыми), и в силу этого ключевой фишкой стало killer moves, которое ниже.
Quiescence Search - форсированный поиск. А вот это вроде бы придумали именно в Каиссе, и именно эта вундервафля гарантировала им победу. Любой, кто сам разрабатывал шахматную программу знает, насколько резко эта фишка усиливает уровень игры, скорее всего ни одна другая фича в шахматном программировании не добавляет программе единомоментно столько "разумности".
Killer moves - "служба лучших ходов". Тоже вроде бы фишка авторов Каиссы, хотя могла быть и в других программах.
Null-move pruning - нулевой ход. Авторы Каиссы не использовали ее рекурсивно, так что скорее всего она дала очень мало. Как использовать null-move рекурсивно придумал только в конце 80х автор Fritz, тогда это и стало его киллер-фичей.
Opening books - скорее всего было у всех программ, хотя шахматная квалификация советских авторов, возможно, позволила создать книгу лучше по качеству ( но на этом уровне это, пожалуй, лишь косметическая прибавка в силе).
Всякие вещи вроде "представление позиции в виде числа" я даже комментировать не буду - все-таки автор статьи не программист.
Rom77
01.08.2024 08:36Quiescence Search - форсированный поиск. А вот это вроде бы придумали именно в Каиссе, и именно эта вундервафля гарантировала им победу.
Quiescence Search предложили ещё Тьюринг и Шеннон. В процессе разработки Каиссы это уже было стандартной техникой.
Killer moves - "служба лучших ходов". Тоже вроде бы фишка авторов Каиссы, хотя могла быть и в других программах.
Да. В 1965 году авторы Каиссы впервые использовали то, что позже они назовут "Службой лучших ходов." С начала 70-х, это в своем роде стал гибрид Killer moves и появившейся много лет спустя History Heuristic.
На западе начало Killer moves традиционно соотносят с работой Барбары Хаберман в конце 60-х и кое-кого ещё (об этом есть в книге Белла, но я уже подзабыл о ком там написано). Ввел в широкий оборот и "монетизировал" название "Киллеры" кажется Джим Джиллогли, со своей программой Tech в 1971 году.
Null-move pruning - нулевой ход. Авторы Каиссы не использовали ее рекурсивно, так что скорее всего она дала очень мало.
Нулевой ход - это отдельная история о том, что между идеей и её реализацией лежит много работы и часто много десятилетий, прежде чем люди найдут способ её эффективного использования.
Пожалуй, история нулевого хода требует отдельного сообщения. Напишу об этом позже.
Opening books - скорее всего было у всех программ, хотя шахматная квалификация советских авторов, возможно, позволила создать книгу лучше по качеству ( но на этом уровне это, пожалуй, лишь косметическая прибавка в силе).
Каиссе, к сожалению, дебютная книга бывало что и мешала. Например, как отмечали авторы программы, на чемпионате мира 1974 года Каисса часто выходила из дебютной книги на позиции, идеи которых не понимала, и почти всегда через несколько ходов оказывалась в неприятном положении. Например в дебютных ходах отдавалась пешка за инициативу, но когда Каисса приступала к игре, она не понимала, что владеет инициативой, но зато хорошо видела, что пешки у неё не хватает ).
ssj100
01.08.2024 08:36+1А если во время партии компьютер выкатило еррор, комп завис, или сгорел... что засчитывается ? техническое поражение или ничья?
представляю человека на телефоне поднимает трубку и ему говорят - комп сдох....
litos
01.08.2024 08:36+1Я думаю, что в "те времена" состочния всех регистров компьютера сохранялись и в случае если компьютер завис, то в ручном режиме программисты могли с того же места запустить программу, а явных лимитов по времени не было, играли просто до победы или явной ничьи
KivApple
01.08.2024 08:36+1Полагаю, программы должны позволять стартовать игру не только с начальной позиции, но и с заданной. Так что при зависаниях и ошибках можно перезапустить программу, задав ей позицию на доске на момент зависания. Более того, в статье указано, что программу и так не гоняли непрерывно, а по ночам, так что по-любому перезапуск был штатным режимом.
Rom77
01.08.2024 08:36+1В чемпионате мира 1974 года было выделено некоторое время на решение технических проблем (в последующих чемпионатах отменено). Сверх этого лимита всё решалось "за свой счет", то есть за время на обдумывание в партии. На перезагрузку программы часто требовалось разрешение соперника.
Вообще, Каисса в 1974 году прошла буквально по лезвию ножа, поскольку во всех четырех партиях чемпионата мира возникли технические проблемы.
В первой партии время Каиссы отсчитывалось по внутренним часам машины, по московскому времени. Когда наступила полночь и таймер обнулился, Каисса решила что ей добавили 24 часа и стала слишком долго думать. Но к счастью успела поставить мат в отведенное время.
Во второй партии соперник перепутал ходы. Авторы Каиссы согласились вернуть позицию до ошибки, для чего потребовалось вернуться на пару ходов назад. При откате ходов в Каиссе обнаружился баг, но к счастью соперник разрешил перезапустить программу.
В третьей партии соперники опять напутали ходы, но поскольку это выяснилось уже после игры, когда телефонное соединение было разорвано, а машина остановлена, то партия доигрывалась на следующий день. Если бы на следующее утро у Каиссы случился глюк, то ей бы засчитали поражение. Таково было решение судьи.
В четвертой партии Каисса зевнула вилку конем и в какие-то моменты соперник мог поставить мат в несколько ходов. По утверждению автора соперничающей программы, чтобы увидеть мат, той не хватило всего одного хода глубины.
.jpg){kind=link}
Rom77
01.08.2024 08:36+1«Каисса» — одна из первых прикладных программ, которая показала результат лучше 99,9 % людей-профессионалов в мире.
Что значит эта фраза? Если про силу игры, то играя на уровне 2-го спортивного разряда, Каисса уступала абсолютно всем шахматным профессионалам.
Ещё больше эффективности добавило применение эвристики нулевого хода. Её принцип заключается в том, что если в какой-то момент позиция игрока станет настолько хорошей, что он может без последствий пропустить следующий ход, то оппонент, очевидно, такого хода никогда не сделает.
Если ход игрока, то почему его должен (не)делать оппонент? Не могу понять такое выражение.
На самом деле принцип нулевого хода заключается в следующем:
Если сделать два хода подряд за себя, пропустив ход противника, и после этого выяснится, что позиция все равно плоха, то первый из ходов можно не рассматривать в нормальном режиме.
Пользуясь этими знаниями, своего рода коллективным опытом поколений живых шахматистов, компьютер избегал серьёзных ошибок на старте.
На чемпионате мира 1974 года Каисса поимела немало проблем в дебюте, отчасти из-за дебютной книги.
Программа провела два матча с читателями газет: сначала — с «Уральским рабочим», а затем — с «Комсомольской правдой».
С читателями газеты Уральский рабочий играла программа ИТЭФ в 1968 году. Впрочем, не суть важно, это все равно Каисса.
Столкновение с человечеством на тот момент закончилось вничью: если у читателей «Уральского рабочего» программа выиграла, то более широкой аудитории «Комсомолки» проиграла.
Читателям газеты Уральский рабочий программа ИТЭФ проиграла.
Причин у этого было две, и первая понятна: ICL 4-70 к тому времени устарел, а оппоненты переходили на более современные и мощные компьютеры.
В чемпионатах 1977 и 1980 годов Каисса играла на IBM 370/168, которая в 3-4 раза быстрее ICL, но впрочем тоже устарела.
козыри «Каиссы», такие, как альфа-бета-отсечение, эвристические механизмы выбора наиболее удачного хода, представление доски в виде числа быстро пошли в народ.
Альфа-бета отсечения к тому времени являлись общеизвестным методом.
ignatfomenko
На выходных если будет время, проведу свой чемпионат по шахматам. Накачаю программ шахматных + шахматы на приставках. Интересно какой будет результат.
guliverza
уже проводится - https://computerchess.org.uk/ccrl/4040/
valergrad
Если стокфиш будет среди участников - то победит он.
Если не будет - то ваш результат будет необъективен)
ignatfomenko
Да шуточный же он будет. Шахматы вроде даже на денди были. В общем проверить все аспекты.