КОМПЬЮТЕРНЫЕ
ШАХМАТЫ
Северин
Денис Валерьевич
Студент 1-го курса
институт
прикладной математики и компьютерных наук
ФГБОУ
ВО «Тульский государственный университет»
Россия, г. Тула
Аннотация.
В статье рассматриваются самые яркие достижения в области шахматной
информатики.
Ключевые слова: компьютерные
шахматы, ретроградный анализ, суперкомпьютер
Введение
В этой статье рассматриваются
наиболее известные исторические достижения в области компьютерных шахмат,
подчеркнув при этом связь между ними и развитием вычислительных систем. Также
сообщается о последних достижениях исследователей факультета вычислительной
математики и кибернетики (ВМК) МГУ, которые первыми в мире создали полные
настольные базы шахматных семифигурных окончаний на
суперкомпьютере имени Ломоносова. Сложность этой работы иллюстрируется тем
фактом, что даже в сжатом виде для табличных баз требуется 100 ТБ дискового
пространства.
История
Шахматы долгое время
считались одной из проблем искусственного интеллекта. Их простые правила
создали иллюзию того, что проблемы могут быть решены относительно небольшими
усилиями. Между тем, число возможных комбинаций сделало невозможным решение
этой проблемы путем простого создания дерева поиска. Первая известная «шахматная»
машина была представлена в конце 18 века. Несмотря на то, что
секрет машины был впоследствии раскрыт (в механизме был спрятан сильный
шахматист), само его существование способствовало популяризации шахмат.
Актуальные шахматные
программы основаны на работах Клода Шеннона и Алана Тьюринга. В 1950 году
Шеннон написал статью «Программирование компьютера для игры в шахматы» [3], где
он оценил число возможных шахматных партий в 10120. Он сравнил это
число с числом атомов во Вселенной, оцененным в 1080. Основываясь на
этом, он предложил рассмотреть количество различных позиций 1043, а
не число партий. В этой статье Шеннон пришел к выводу, что полное решение
шахматной проблемы возможно, но сложно реализовать на практике.
Первый реальный шахматный
алгоритм был предложен Тьюрингом. Однако он не смог работать на самых первых
компьютерах из-за их низкой вычислительной мощности. Алгоритм был проверен на
модели, в которой группа людей действовала строго в соответствии с алгоритмом,
чтобы найти лучший ход. Несмотря на то, что на 29-м ходу программа была
побеждена шахматистом-любителем, эксперимент доказал, что компьютер может
делать осмысленные ходы. Некоторые из концепций, использованных в этом
эксперименте (например, генератор ходов, дерево поиска и функция оценки),
по-прежнему актуальны для шахматных программ.
Большой толчок развитию
игровых программ дал алгоритм альфа-бета отсечения (метод ветвей и границ),
предложенный Ричардом Беллманом в 1958 году. Он помог программам «видеть»
гораздо дальше. С тех пор шахматные программы совершенствовались на протяжении
многих лет. В 1974 году состоялся первый чемпионат мира по компьютерным
шахматам. Он был выигран по программе Kaissa, разработанной
выпускниками МГУ [1]; ее шахматный ранг соответствовал продвинутому клубному
игроку.
Также следует отметить
работы Михаила Ботвинника, шестого чемпиона мира по шахматам. Вместо того,
чтобы генерировать деревья поиска, он попытался смоделировать мышление
шахматиста. К сожалению, его долгосрочные исследования не дали никаких
результатов, которые доказали бы эффективность его подхода. Возможно,
исследования Ботвинника опередили свое время. В настоящее время Google успешно применил методы машинного обучения для
разработки программы AlphaZero на основе нейронных
сетей [2].
В 1970-х годах начались
активные исследования, направленные на то, чтобы дать точный ответ на вопрос,
есть ли победа на позициях определенных классов, и если да, то сколько ходов потребуется.
Эти позиции характеризуют финальные игры с небольшим количеством фигур,
например, королева и король против ладьи и короля. Для небольшого количества
фигур вместо анализа деревьев поиска, как Шеннон описал это ранее,
предпочтительнее искать и запоминать все позиции, в которых одним из игроков
был поставлен мат. Затем, все позиции, из которых могут быть достигнуты ранее
определенные контрольные позиции за один ход. Это позиции с матами за один ход.
Затем метод (который часто называют ретроградным анализом) последовательно
генерирует классы позиций с матами в два хода, три хода и так далее. Наконец,
информация о всех возможных позициях в конкретном эндшпиле вводится в таблицу.
Первые таблицы основаны
Кеном Томпсоном. В период с 1970 по 2000 год он последовательно создал
4-элементные, 5-элементные и некоторые из 6-элементных баз. Основная проблема
при создании табличных баз заключается в большом объеме необходимого хранилища.
Каждое последующее измерение требует в 100 раз больше емкости. Количество
вычислений растет соответственно. Очевидно, что ни имеющиеся в настоящее время
компьютеры, ни компьютеры следующих нескольких поколений не смогут полностью
решить шахматную проблему. Возможно, через пару сотен лет, удастся построить
компьютер на новых физических принципах с достаточным объемом памяти.
Реализация алгоритма
ретроградного анализа генерации таблицы на суперкомпьютере
В 2009 году
исследовательская группа с факультета CMC МГУ присоединилась к работе по
созданию 7-элементных табличных баз. Основная идея заключалась в реализации
ретроградного анализа на суперкомпьютере. В целом считалось, что ретроградный
анализ не может быть адаптирован к суперкомпьютерам, то есть к компьютерам без
общей памяти, главным образом из-за ее синхронизации. Чтобы оценить
определенную позицию, нужно сделать все ходы из нее, а также определить классы
позиций, к которым она ведет; затем, если это возможно, можно оценить позицию. Однако,
поскольку оценки позиций хранятся в разных вычислительных узлах, задержка
передачи данных может быть чрезвычайно высокой. Вычислительные узлы большую
часть времени простаивают, ожидая оценок от других узлов. Для решения этой
проблемы использовался механизм обратного хода, что позволило реализовать
асинхронный алгоритм. Ниже приведен упрощенный вариант алгоритма:
1. Для
каждой позиции рассчитайте и сохраните количество возможных ходов (оценки
позиций предполагаются неизвестными).
2. Отметьте
положения матов.
3. Из
отмеченных позиций сделайте обратные ходы к предыдущим позициям. В
соответствующих предыдущих позициях обновите оценку и уменьшите число возможных
ходов.
4. Если
число возможных ходов для определенной позиции становится равным нулю, то эта
позиция считается оценочной. Отметьте эту позицию и перейдите к шагу 3.
5. В
конце концов процесс завершается, и большинство позиций получают свои оценки;
позиции без оценок считаются ничьими.
Следует
отметить, что эта упрощенная версия алгоритма не включает в себя многие важные
аспекты ретроградного анализа, такие как второстепенные и большие итерации,
симметрии шахматной доски и отсечение невозможных позиций. Преимущество
асинхронного алгоритма состоит в том, что нет необходимости ждать оценок от
других узлов. В то же время алгоритм предполагает генерацию обратных ходов, что
значительно усложняет программирование и требует немного больше памяти.
Несмотря на то, что первая программа, реализованная на суперкомпьютере Blue Gene в 2009 году,
подтвердила работоспособность и эффективность алгоритма, емкости доступных
устройств хранения было недостаточно для создания 7-элементных таблиц. В 2012
году программа была перенесена на суперкомпьютер Lomonosov,
и в течение нескольких месяцев были вычислены все 7-элементные таблицы. В
результате был обнаружен самый длинный теоретический мат в 549 ходов: король,
дама и пешка против короля, ладьи, слона и коня. Первые 400 ходов, сделанные
программой, казались совершенно бессмысленными, как будто компьютер случайным
образом перемещал фигуры. Многие движения, сделанные компьютером, являются
единственными ходами, чтобы выиграть; любая альтернатива пропускает победу.
Даже после сжатия одним
из самых популярных и эффективных алгоритмов (LZMA) общий размер таблиц
составил 140 ТБ. Именно поэтому последующая работа была направлена
на улучшение степени сжатия, а также на предоставление доступа к
таблицам с персональных устройств. В результате размер сжатых данных был
уменьшен со 140 до 96 ТБ. Для этой цели были использованы алгоритм
восстановления сжатия и метод недетерминированных значений. Этот метод позволил
легко вычисляемым значениям быть замененными значениями, наиболее подходящими
для сжатия.
Поскольку обычный
пользователь не может позволить себе массив хранения объемом 100 ТБ, был создан
веб-сайт и разработаны программы для персональных компьютеров и смартфонов Android для обеспечения онлайн-доступа к настольным базам.
Заключение
В настоящее время интерес
к шахматам как направлению искусственного интеллекта заметно снизился. Сегодня
даже чемпионы мира среди людей не имеют шансов против игры в шахматы на обычном
компьютере. Таблицы шахматных окончаний позволяют программе без проблем выигрывать
партии, шахматные деревья предоставляют информацию обо всех играх в шахматы
(что гарантирует минимальное количество ошибок), а алгоритмы поиска анализируют
позиции в середине игры на 15–25 ходов вперед.
Список
использованной литературы:
1.
Машина играет в шахматы / Г.М. Адельсон-Вельский,
В.Л. Арлазаров, А.Р. Битман, М.В. Донской. - М.: Наука,
1983. – 207 с.
2.
A
general reinforcement learning algorithm that masters chess, shogi, and go
through self-play/ D. Silver, T. Hubert, J. Schrittwieser
et al. // Science. - 2018. - № 362(6419). - С. 1140-1144.
3.
Shannon,
C.E. Programming a computer for playing chess/ C.E. Shannon // Philos. Mag.. - 1950. - № 41(314). - С. 256-275.
Сведения
об авторе:
Северин
Денис Валерьевич – студент 1-го курса института прикладной
математики и компьютерных наук ФГБОУ ВО «Тульский государственный университет».
COMPUTER CHESS
Severin
D.V.
Abstract. This article considers the most significant
achievements in the field of chess informatics.
Keywords: computer chess, retrograde analysis, supercomputer
References:
1.
The
machine plays chess / G.M. Adel’son-Vel’skii, V.L. Arlazarov, A.R. Bitman, M.V. Donskoi. - M.: The
science,1983. – 207 p.
2.
A general reinforcement learning algorithm
that masters chess, shogi, and go through self-play/ D. Silver, T. Hubert, J. Schrittwieser et al. //
Science. - 2018. - № 362(6419). - p. 1140-1144.
3.
Shannon,
C.E. Programming a computer for playing chess // Philos. Mag..
- 1950. - № 41(314). - p. 256-275.