Программирование, 2019, № 3, стр. 14-17

О решении проблемы шахматных 7-фигурных окончаний

В. Б. Захаров a*, М. Г. Мальковский a**, А. И. Мостяев a***

a Московский государственный университет имени М.В. Ломоносова Факультет вычислительной математики и кибернетики (ВМК)
119899 Москва, Ленинские горы, д. 1, стр. 8, Россия

* E-mail: victor@ldis.cs.msu.su
** E-mail: malk@cs.msu.su
*** E-mail: reistlin12@gmail.com

Поступила в редакцию 14.01.2019
После доработки 14.01.2019
Принята к публикации 17.01.2019

Полный текст (PDF)

Аннотация

В статье рассказывается о самых ярких достижениях в области шахматной информатики. Особо хочется отметить, что в годы работы Михаила Романовича Шуры-Буры ученые мехмата МГУ лидировали в этой области, и в 1973 г. программа Каисса выиграла чемпионат мира среди компьютеров. Позже лидерство было утрачено. Вернуть его удалось в 2012 году, когда ученые факультета ВМК МГУ построили на суперкомпьютере Ломоносов полную таблицу 7-фигурных окончаний и нашли самый длинный из известных матов – мат в 549 ходов.

1. ВВЕДЕНИЕ

Михаил Романович Шура-Бура страстно любил шахматы. Рядом с ним на мехмате МГУ работали ученые, создавшие программу Каисса, ставшую первым чемпионом мира среди шахматных программ. Сейчас уже трудно достоверно установить, какое лично участие принимал Михаил Романович в данных работах, но то, что он был к ним неравнодушен, не вызывает сомнений.

В этой статье мы постарались осветить наиболее известные исторические достижения в области компьютерных шахмат, показать их связь с развитием вычислительных систем, так как многие основоположники программирования, как и Михаил Романович, интересовались шахматами.

Также мы расскажем о последних достижениях сотрудников факультета ВМК МГУ, которые первые в мире, используя суперкомпьютер Ломоносов, построили полные таблицы 7 -фигурных шахматных окончаний. О сложности выполненной работы говорит тот факт, что даже в упакованном виде таблицы занимают 100 Тб данных.

2. ИСТОРИЧЕСКИЕ ИССЛЕДОВАНИЯ

Шахматы с давних времен рассматривались как одна из задач искусственного интеллекта. Простые правила создавали иллюзию, что задача может быть решена сравнительно небольшими усилиями. Вместе с тем, число возможных комбинаций делало невозможным решение задачи “в лоб” простым построением дерева перебора. Первый известный так называемый шахматный автомат (шахматный турок) был продемонстрирован в конце 18 века. И хотя секрет автомата был позднее раскрыт (в сложном механизме скрывался сильный шахматист), существование автомата способствовало популяризации шахмат.

Реальные компьютерные шахматы берут начало с работ Клода Шеннона и Алана Тьюринга. Клод Шеннон в 1950 году написал статью “Programming a computer for Playing Chess” [1], где оценил количество возможных шахматных партий в 10120. Он сравнил это число с числом атомов во Вселенной, оцениваемым как 1080. Из чего он предложил рассматривать не число партий, а число различных позиций 1043 (которое сравнимо с числом атомов на Земле – 1050). В статье Шеннона делается вывод, что полного решения шахматной задачи возможно, но трудноосуществимо практически. Заметим, что обе оценки Шеннона не претендуют на точность, а дают лишь качественное представление о порядках чисел.

Первый детальный шахматный алгоритм был предложен Аланом Тьюрингом. Но запустить его на самых первых компьютерах не удалось, слишком мала была их мощность. Алгоритм был проверен на модели, в которой группа людей действовала строго по алгоритму и вычисляла лучший ход. Хотя программа была разгромлена шахматистом-любителем на 29-м ходу, эксперимент доказал, что компьютер может делать осмысленные ходы, а некоторые использованные концепции, такие как генератор ходов, дерево перебора, оценочная функция, актуальны в шахматных программах и в настоящее время.

Большой толчок развитию игровых программ дал алгоритм альфа-бета отсечений (метод ветвей и границ), 1958 году. С его помощью программы стали “видеть” намного глубже. В течение многих лет шахматные программы совершенствовались, а 1974 году был проведен первый чемпионат мира среди компьютеров, который выиграла разработанная в МГУ программа “Каисса” [2]. Ее сила оценивалась вторым-третьим разрядом.

Также известны работы Михаила Ботвинника – 6-го чемпиона мира по шахматам. Он попытался отойти от построения дерева перебора и смоделировать мышление шахматиста. Но, к сожалению, многолетние исследования не позволили получить результаты, которые бы показали эффективность его подхода. Возможно исследования Ботвинника слишком сильно опередили время. В настоящее время компания Google смогла успешно применить методы машинного обучения и написать программу игры AlphaZero, работающую на основе нейронных сетей [3].

В 70-х годах начали активно проводиться исследования, позволяющие для некоторых классов позиций абсолютно точно дать ответ на вопрос, есть ли выигрыш, и если есть, то за сколько ходов. К таким позициям относятся малофигурные окончания, например, ферзь и король против ладьи и короля. При малом количестве фигур можно, как это ранее описал Клод Шеннон, анализировать не дерево перебора, а перебрать и запомнить все позиции, в которых одной из сторон поставлен мат. Затем можно найти все позиции, из которых одним ходом можно попасть в найденные ранее матовые позиции. Это позиции с матом в 1 ход. Далее метод (часто его называют ретроанализом) заключается в последовательном построении классов позиций, в которых мат ставится за 2 хода, 3 хода, и т.д. В конечном итоге информация абсолютно обо всех позициях заданного шахматного окончания заносится в таблицы. Используя указанные таблицы, шахматные программы играют в шахматных окончаниях (как иногда говорят) в силу Бога, то есть, совершенно безошибочно.

Первые таблицы рассчитал Кен Томпсон, известный также как разработчик системы Юникс и создатель языка Си. Начиная с 1970 до 2000 года, он создал сначала 4-фигурные таблицы, затем 5-фигурные и некоторые 6-фигурные.

Основная проблема создания таблиц заключается в большом объеме памяти, который требуется для их хранения. Каждая следующая размерность требует для хранения в 100 раз больший объем памяти. Соответственно растет и объем вычислений. Очевидно, что полное решение задачи игры в шахматы не смогут выполнить ни компьютеры текущего, ни ближайших поколений. Возможно через пару сотен лет на новых физических принципах, о которых мы сейчас не имеем даже близкого представления, удастся сделать компьютер с достаточным объемом памяти. Но в 21 веке можно добраться лишь до позиций, имеющих не более 12–13 фигур.

Работу Кена Томпсона продолжил Евгений Налимов (один из разработчиков системы программирования Microsoft Visual Studio). В 2005 г. им были построены полные 6-фигурные таблицы. После чего встал вопрос о создании 7-фигурных таблиц. Примерное время создания 7-фигурных таблиц оценивалось как 2017–2020 годы.

3. РЕАЛИЗАЦИЯ АЛГОРИТМА РЕТРОАНАЛИЗА ДЛЯ ВЫЧИСЛЕНИЯ ТАБЛИЦ НА СУПЕРКОМПЬЮТЕРЕ

В 2009 году в работу над 7-фигурными таблицами включилась группа сотрудников факультета ВМК МГУ [4]. Основная идея была в реализации метода ретроанализа на суперкомпьютере. Считалось, что алгоритм ретроанализа не применим для суперкомпьютеров, то есть для компьютеров без общей памяти. Главная проблема заключается в его синхронности. Чтобы получить оценку некоторой позиции, требуется выполнить все ходы из нее и узнать, в позиции каких классов она ведет, и после этого, если возможно, дать оценку позиции. Но так как оценки позиций хранятся на разных компьютерных узлах, то задержки обращений могут быть непомерно большими. Компьютерные узлы будут простаивать большую часть времени в ожидании получения оценок от других узлов.

Для решения задачи был использован механизм обратных ходов, позволивший реализовать асинхронный алгоритм. Упрощенно алгоритм можно описать так.

1. Первоначально для каждой позиции вычисляется и записывается число возможных по правилам ходов. Оценки позиций считаются неопределенными.

2. Отмечаются матовые позиции.

3. Из отмеченных позиций делаются обратные ходы в предшествующие позиции. В соответствующих предшествующих позициях модифицируется оценка и уменьшается количество возможных ходов.

4. Если число возможных ходов в позиции стало нулевым, то оценка позиции считается вычисленной. Позиция отмечается и для нее выполняется шаг 3.

5. Рано или поздно указанный процесс завершается, большая часть позиций получает свои оценки, а позиции, не получившие оценок, считаются ничейными.

Отметим, что в описании выше опущены многие важные моменты ретроанализа, такие как минорная и мажорная итерации, учет симметрий шахматной доски, отсечение невозможных позиций.

Достоинством асинхронного алгоритма является отсутствие ожидания ответа от других узлов. Вместе с тем, алгоритм требует умения генерировать обратные ходы, что по многим причинам на порядок усложняет программирование, и требует немного больше памяти, чем классический алгоритм минимакса.

Хотя первая программа, реализованная на суперкомпьютере Blue Gene в 2009 г., доказала работоспособность и хорошую эффективность алгоритма, размеры дисковых накопителей не позволяли начать вычисления 7-фигурных таблиц. В 2012 г. удалось перенести программу на суперкомпьютер Ломоносов и в течение нескольких месяцев рассчитать все 7-фигурные таблицы [5]. В результате был найден самый длинный теоретический мат в 549 ходов – в окончании король, ферзь и пешка против короля, ладьи, слона и коня (см. рис. 1 ).

Рис 1.

13-й чемпион мира по шахматам Гарри Каспаров, посмотрев на данную позицию и ее решение, заметил, что первые 400 ходов программы кажутся совершенно бессмысленными, компьютер как бы хаотично передвигает фигуры и только после этого становится заметной стесненность черных фигур. Тем не менее даже через 400 ходов человеку не под силу понять, как можно поставить мат в данном окончании. Многие ходы компьютера являются единственно возможными для достижения выигрыша, любая альтернатива упускает выигрыш.

Общий объем таблиц даже после сжатия одним из самых популярных и эффективных алгоритмов LZMA составил 140 Тб. Поэтому дальнейшая работа была связана с решением проблемы более эффективного сжатия и с обеспечением доступа к таблицам с персональных устройств.

В результате объем сжатых данных был уменьшен со 140 Тб до 96 Тб. Для этого был использован алгоритм сжатия RE-PAIR и техника недоопределенных значений [6]. Данная техника позволяет заменять значения, которые можно легко вычислить, на значения, наиболее удобные для сжатия.

Так как в настоящее время для обычного пользователя не представляется возможным иметь дисковый массив размером 100 Тб, то был создан веб-сайт и написаны программы для персональных компьютеров и Андроид-смартфонов, позволяющие осуществлять доступ к таблицам онлайн.

Отметим, что на данный момент интерес к шахматам как к направлению искусственного интеллекта заметно ослаб. На текущий момент даже чемпионы мира по шахматам среди людей не имеют никаких шансов в игре против программы, запущенной на обычном компьютере. Таблицы шахматных окончаний позволяют безошибочно играть в эндшпиле, дебютные деревья хранят информацию обо всех сыгранных шахматных партиях, что обеспечивает игру в дебюте с минимумом ошибок, а переборные алгоритмы анализируют позиции в середине партии на 15–25 и ходов вперед.

4. ЗАКЛЮЧЕНИЕ

Результат проведенных работ:

1) Разработан новый алгоритм ретроанализа для игр двух партнеров с пошаговой стратегией, пригодный для работы на компьютерах, не имеющих общей памяти.

2) Разработаны алгоритмы эффективной компрессии данных без потерь, основанные на достроении информации при декомпрессии. Благодаря этому удается повысить степень сжатия на 30%.

3) Созданы таблицы шахматных окончаний, содержащие точную оценку количества ходов до мата для любой позиции с 7 и менее фигурами на доске.

4) Обеспечен онлайн-доступ к указанным таблицам.

Список литературы

  1. Shannon C.E. Programming a computer for playing chess. Philosophical Magazine. 1950. V. 41. № 314. P. 256–275.

  2. Адельсон-Вельский Г.М., Арлазаров В.Л., Битман А.Р., Донской М.В. Машина играет в шахматы. Изд-во: М.: Наука, 1983 г. 208 с.

  3. Silver D., Hubert T., Schrittwieser J., Antonoglou I., Lai M., Guez A., Lanctot M., Sifre L., Kumaran D., Graepel T., Lillicrap T., Simonyan K., Hassabis D. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science. 2018. V. 362. № 6419. P. 1140–1144.

  4. Захаров В.Б., Махнычев В.С. Алгоритм ретроанализа в суперкомпьютерных системах на примере задачи игры в шахматы // Программные системы и инструменты. Тематический сборник / Под ред. Л. Королев, Л.С. Корухова, В.А. Костенко. Т. 11. Программные системы и инструменты. Изд. отделения ф-та ВМК МГУ Москва. 2010. С. 45–52.

  5. Захаров В.Б., Махнычев В.С. Создание таблиц шахматных 7-фигурных окончаний на суперкомпьютере Ломоносов // Суперкомпьютеры. 2013. № 15. С. 34–37

  6. Zakharov V. B., Mal’kovskii M.G., Shchukin Y.V. Compression of underdetermined data in a 7-piece chess table // Moscow University Computational Mathematics and Cybernetics. 2016. V. 40. № 1. P. 47–52.

Дополнительные материалы отсутствуют.