Comments 30
На выходных если будет время, проведу свой чемпионат по шахматам. Накачаю программ шахматных + шахматы на приставках. Интересно какой будет результат.
уже проводится - https://computerchess.org.uk/ccrl/4040/
Если стокфиш будет среди участников - то победит он.
Если не будет - то ваш результат будет необъективен)
Странно, но не слова о Михаиле Моисеевиче Ботвиннике и его программе Пионер.
А зачем?
Из уважения к шахматным достижениям Михаила Моисеевича, об этой неприятной странице его биографии лучше вспоминать пореже. К тому же это будет скорее на тему уголовного права, а не на тему шахматного программирования.
https://atimopheyev.narod.ru/AfterPIONEER/inPIONEERsFootsteps.ALL.HTM#Pioneer_Botvinnik тут можете почитать. Попытались там все по этой теме собрать.
Если в одном предложении: группа людей свыше 20 лет "занималась" созданием шахматной программы, которая за все это время не сыграла ни одной партии. Для непрограммистов: это примерно как 20 лет "строить" дом на бумаге, и даже не выкопать яму для фундамента.
"Разработка" заключалась в том, что Ботвинник время от времени вспоминал, что он каждый месяц получает зарплату за разработку, придумывал замудренные методы, и пытался объяснить их математикам житейскими словами на русском языке, т.к. за 20 лет не удосужился выучить даже основы программирования чтобы говорить с ними на языке алгоритмов или нарисовать им блок-схему. Математики пытались что-то написать, но получалась, конечно, ерунда, после чего валили все друг на друга: математики на то, что у Ботвинника требования слишком абстрактны и непонятно как их перевести в код, а Ботвинник обвинял их в саботаже и в том, что они не делают то, что он им говорит.
Как только какой-то хитромудрый метод работал на какой-то знаменитой позиции ( на которой Ботвинник его и придумывал), тут же оказывалось что на другой позиции этот алгоритм предлагает полнейшую ерунду. После чего Ботвинник пропадал на несколько лет, а, появившись, предлагал какой-то другой метод, который чтобы реализовать, нужно было переписать все с нуля. После чего оказывалось что метод работает на второй позиции, но не работает на первой.
Разумеется, текучка среди математиков-программистов была существенная, хотя и не такая большая потому что на этой работе можно было годами ничего не делать.
Об уровне работ можно судить по дневниковой записи Ботвинника, в которой он простодушно рассказывает как спустя 10 лет "разработки" случайно выяснилось, что "Пионер" ходит конем с e5 на g5 и вообще делает считает возможными много и других невозможных ходов.
А про историю с этюдом Надареишвили мне даже и не хочется рассказывать, из уважения к Ботвиннику.
Ботвинник не принимал участия в разработке Каиссы. Кроме того, статья слишком маленькая, чтобы упоминать об альтернативных попытках.
Интервью Владимира Арлазарова, рекомендую.
А числа — это то, с чем компьютер справляется лучше всего, так что за счёт этого можно оптимизировать процесс.
Компьютер только с числами и работает, по другому никак
Для справок:
Александр Кронрод - дядя, а Анатолий Усков - отец Ольги Усковой, которую уже прозвали "мать русских роботов".
Спасибо за статью, интересно было почитать про организационную сторону дела и про людей!
К сожалению, все что касается примененных алгоритмов в Каиссе описано в стиле "ученый изнасиловал журналиста" и либо полностью неправильно либо сильно переврано.
Для тех кто если вдруг захочет почитать в чем действительно была суть использованных в Каиссе оптимизаций и идей, дам англоязычные названия тех из них, что применяются в шахматном программировании и поныне. По ним вы сможете найти подробную информацию и реализацию, например, в chessprogrammingwiki и других сайтах.
Alpha-beta pruning - альфа-бета отсечение. В силу очевидности идеи скорее всего использовалось всеми программами, т.е. не является фишкой авторов Каиссы.
То, сколько она дает мощи зависит от того насколько хорошо ты сортируешь ходы ( т.е. сильнейшие ходы просматриваешь первыми), и в силу этого ключевой фишкой стало killer moves, которое ниже.
Quiescence Search - форсированный поиск. А вот это вроде бы придумали именно в Каиссе, и именно эта вундервафля гарантировала им победу. Любой, кто сам разрабатывал шахматную программу знает, насколько резко эта фишка усиливает уровень игры, скорее всего ни одна другая фича в шахматном программировании не добавляет программе единомоментно столько "разумности".
Killer moves - "служба лучших ходов". Тоже вроде бы фишка авторов Каиссы, хотя могла быть и в других программах.
Null-move pruning - нулевой ход. Авторы Каиссы не использовали ее рекурсивно, так что скорее всего она дала очень мало. Как использовать null-move рекурсивно придумал только в конце 80х автор Fritz, тогда это и стало его киллер-фичей.
Opening books - скорее всего было у всех программ, хотя шахматная квалификация советских авторов, возможно, позволила создать книгу лучше по качеству ( но на этом уровне это, пожалуй, лишь косметическая прибавка в силе).
Всякие вещи вроде "представление позиции в виде числа" я даже комментировать не буду - все-таки автор статьи не программист.
Quiescence Search - форсированный поиск. А вот это вроде бы придумали именно в Каиссе, и именно эта вундервафля гарантировала им победу.
Quiescence Search предложили ещё Тьюринг и Шеннон. В процессе разработки Каиссы это уже было стандартной техникой.
Killer moves - "служба лучших ходов". Тоже вроде бы фишка авторов Каиссы, хотя могла быть и в других программах.
Да. В 1965 году авторы Каиссы впервые использовали то, что позже они назовут "Службой лучших ходов." С начала 70-х, это в своем роде стал гибрид Killer moves и появившейся много лет спустя History Heuristic.
На западе начало Killer moves традиционно соотносят с работой Барбары Хаберман в конце 60-х и кое-кого ещё (об этом есть в книге Белла, но я уже подзабыл о ком там написано). Ввел в широкий оборот и "монетизировал" название "Киллеры" кажется Джим Джиллогли, со своей программой Tech в 1971 году.
Null-move pruning - нулевой ход. Авторы Каиссы не использовали ее рекурсивно, так что скорее всего она дала очень мало.
Нулевой ход - это отдельная история о том, что между идеей и её реализацией лежит много работы и часто много десятилетий, прежде чем люди найдут способ её эффективного использования.
Пожалуй, история нулевого хода требует отдельного сообщения. Напишу об этом позже.
Opening books - скорее всего было у всех программ, хотя шахматная квалификация советских авторов, возможно, позволила создать книгу лучше по качеству ( но на этом уровне это, пожалуй, лишь косметическая прибавка в силе).
Каиссе, к сожалению, дебютная книга бывало что и мешала. Например, как отмечали авторы программы, на чемпионате мира 1974 года Каисса часто выходила из дебютной книги на позиции, идеи которых не понимала, и почти всегда через несколько ходов оказывалась в неприятном положении. Например в дебютных ходах отдавалась пешка за инициативу, но когда Каисса приступала к игре, она не понимала, что владеет инициативой, но зато хорошо видела, что пешки у неё не хватает ).
Null-move pruning - нулевой ход. Авторы Каиссы не использовали ее рекурсивно, так что скорее всего она дала очень мало. Как использовать null-move рекурсивно придумал только в конце 80х автор Fritz, тогда это и стало его киллер-фичей.
Авторы программы ИТЭФ (Каиссы) придумали и реализовали принцип нулевого хода в 1964-65 годах. Но в тот момент сам принцип понимался иначе и его реализация была далека от той, что сложилась в 90-е годы, когда он начал приносить несомненную пользу.
В первую очередь, изначально принцип нулевого хода был как бы инвертирован относительно нынешней реализации и предполагал не отсечение заведомо худших ходов, как сейчас, а наоборот занимался отбором перспективных ходов, то есть тех ходов, которые требуют обязательного рассмотрения. В настоящее время такая реализация принципа нулевого хода похожа на так называемый "Детектор угроз". Логика следующая:
"Если мы пропустили ход противника и таким образом сделали за себя два хода подряд, и при этом что-либо материально выиграли, то значит нам не хватает всего одного темпа для материальных приобретений. Значит ход перспективный и его следует включить в основное дерево перебора." Программу с таким принципом авторы называли "активной" и она запускалась отдельно.
С возобновлением работ над Каиссой в 1971 году, авторы стали использовать и инвертированный подход, то есть тот же, что используют и сейчас - отсечение заведомо бесперспективных ходов. Логика следующая - "Право хода обычно заметное преимущество в шахматах, а если бы можно было сделать два хода подряд, то мы бы получили огромное преимущество. Но если попробовать действительно сделать за себя два хода подряд, а оценка позиции после этого всё равно останется низкой, значит вариант откровенно плох и его можно отсечь.
Тем не менее авторами Каиссы так и не было найдено, в каком месте программы использовать нулевой ход. Они его ограниченно использовали при сортировке, в Futility и Razoring, в методе аналогий, но не перед основным перебором, где метод так эффективно используется в настоящее время. То есть метод использовался, но место в программе, где его наиболее эффективно применить, ещё было неизвестно.
На протяжении 70-80-х годов метод был как минимум не безвестен, но никому не удавалось так приладить его к существующему коду, чтобы его эффективность стала очевидной.
В конце 80-х нужное место было наконец найдено и получены достоверные тестовые результаты о полезности данного подхода. Об этом в частности писал в своей статье Мюррей Кемпбелл (один из будущих авторов Дип Блю), где приводил конкретные результаты. Упоминал о том же Роберт Хьятт, один из авторов программы Крей Блитц.
Но в то время методу нулевого хода было ещё далеко до той эффективности, которую он имеет сейчас. Сокращение перебора выполнялось только на один ход, а сам метод не был рекурсивным.
На протяжении 90-х информация о новом подходе постепенно распространялась все больше, а реализация метода становилось все лучше, и с середины 90-х нулевой ход вошел в "джентельменский набор" методов всех лучших программ того времени. Теперь сокращение (reduction) глубины выполнялось на три хода (ply), метод стал рекурсивным, появилась верификация, а так же некоторые другие оптимизации.
Именно появление нулевого хода по большей части ответственно за то, что программы на персональных компьютерах смогли сравниться в силе с вычислительными монстрами "старой школы", вроде Дип Блю, у которого не было нулевого хода, а так же с лучшими людьми. С нулевым ходом дерево перебора стало более узким и глубоким, что позволило без больших потерь смотреть позицию гораздо глубже и соответственно играть сильнее.
А если во время партии компьютер выкатило еррор, комп завис, или сгорел... что засчитывается ? техническое поражение или ничья?
представляю человека на телефоне поднимает трубку и ему говорят - комп сдох....
нет, перезванивают запасному компьютеру: "-Анатолий Евгеньевич, не подскажите тут ход, очень надо для дела"
Я думаю, что в "те времена" состочния всех регистров компьютера сохранялись и в случае если компьютер завис, то в ручном режиме программисты могли с того же места запустить программу, а явных лимитов по времени не было, играли просто до победы или явной ничьи
Полагаю, программы должны позволять стартовать игру не только с начальной позиции, но и с заданной. Так что при зависаниях и ошибках можно перезапустить программу, задав ей позицию на доске на момент зависания. Более того, в статье указано, что программу и так не гоняли непрерывно, а по ночам, так что по-любому перезапуск был штатным режимом.
В чемпионате мира 1974 года было выделено некоторое время на решение технических проблем (в последующих чемпионатах отменено). Сверх этого лимита всё решалось "за свой счет", то есть за время на обдумывание в партии. На перезагрузку программы часто требовалось разрешение соперника.
Вообще, Каисса в 1974 году прошла буквально по лезвию ножа, поскольку во всех четырех партиях чемпионата мира возникли технические проблемы.
В первой партии время Каиссы отсчитывалось по внутренним часам машины, по московскому времени. Когда наступила полночь и таймер обнулился, Каисса решила что ей добавили 24 часа и стала слишком долго думать. Но к счастью успела поставить мат в отведенное время.
Во второй партии соперник перепутал ходы. Авторы Каиссы согласились вернуть позицию до ошибки, для чего потребовалось вернуться на пару ходов назад. При откате ходов в Каиссе обнаружился баг, но к счастью соперник разрешил перезапустить программу.
В третьей партии соперники опять напутали ходы, но поскольку это выяснилось уже после игры, когда телефонное соединение было разорвано, а машина остановлена, то партия доигрывалась на следующий день. Если бы на следующее утро у Каиссы случился глюк, то ей бы засчитали поражение. Таково было решение судьи.
В четвертой партии Каисса зевнула вилку конем и в какие-то моменты соперник мог поставить мат в несколько ходов. По утверждению автора соперничающей программы, чтобы увидеть мат, той не хватило всего одного хода глубины.
«Каисса» — одна из первых прикладных программ, которая показала результат лучше 99,9 % людей-профессионалов в мире.
Что значит эта фраза? Если про силу игры, то играя на уровне 2-го спортивного разряда, Каисса уступала абсолютно всем шахматным профессионалам.
Ещё больше эффективности добавило применение эвристики нулевого хода. Её принцип заключается в том, что если в какой-то момент позиция игрока станет настолько хорошей, что он может без последствий пропустить следующий ход, то оппонент, очевидно, такого хода никогда не сделает.
Если ход игрока, то почему его должен (не)делать оппонент? Не могу понять такое выражение.
На самом деле принцип нулевого хода заключается в следующем:
Если сделать два хода подряд за себя, пропустив ход противника, и после этого выяснится, что позиция все равно плоха, то первый из ходов можно не рассматривать в нормальном режиме.
Пользуясь этими знаниями, своего рода коллективным опытом поколений живых шахматистов, компьютер избегал серьёзных ошибок на старте.
На чемпионате мира 1974 года Каисса поимела немало проблем в дебюте, отчасти из-за дебютной книги.
Программа провела два матча с читателями газет: сначала — с «Уральским рабочим», а затем — с «Комсомольской правдой».
С читателями газеты Уральский рабочий играла программа ИТЭФ в 1968 году. Впрочем, не суть важно, это все равно Каисса.
Столкновение с человечеством на тот момент закончилось вничью: если у читателей «Уральского рабочего» программа выиграла, то более широкой аудитории «Комсомолки» проиграла.
Читателям газеты Уральский рабочий программа ИТЭФ проиграла.
Причин у этого было две, и первая понятна: ICL 4-70 к тому времени устарел, а оппоненты переходили на более современные и мощные компьютеры.
В чемпионатах 1977 и 1980 годов Каисса играла на IBM 370/168, которая в 3-4 раза быстрее ICL, но впрочем тоже устарела.
козыри «Каиссы», такие, как альфа-бета-отсечение, эвристические механизмы выбора наиболее удачного хода, представление доски в виде числа быстро пошли в народ.
Альфа-бета отсечения к тому времени являлись общеизвестным методом.
Грубая ошибка в названии.
В Стокгольме играли вовсе не на советской машине, а на британской ICL System 4/70 (архитектура IBM/360)
https://ruchess.ru/persons_of_day/vladimir_arlazarov_pd/
https://www.osp.ru/cw/2000/09/3545
https://www.itweek.ru/themes/detail.php?ID=51235
Первую программу написали на машинном коде: это была последовательность нулей и единиц.
На ассемблере она была написана все же. Вот листинг. Слева ассемблер, справа машкод
У них не было транслятора ассемблера, трансляцию выполняли лаборанты. Но тем не менее.
Можно ли выложить диссертацию Арлазарова целиком?
Диссертация Арлазарова, посвященная шахматной программе ИТЭФ, целиком. Плюс автореферат. (Папка на google drive).
Также для полноты картины выкладываю диссертацию Донского, основного программиста уже Каиссы.
Как советская машина всех в шахматы обыграла