Итак, мы подробно рассмотрели в статье, как работают важнейшие составляющие реальной шахматной программы по отдельности и вместе. Пора подвести некоторые итоги, сделать выводы, и попытаться оценить будущие перспективы.

< К предыдущей части

Если попробовать измерить прогресс каждой важной составляющей движка по отдельности, за всю историю компьютерных шахмат, то можно предложить следующие, приблизительные (!) цифры:

• поиск по дереву вариантов (направленный перебор), начиная с полного перебора ~2000 пунктов;

• рукописная оценочная функция, считая от оценки только по материалу ~ 700 — 1000 пунктов;

• нейросетевая оценочная функция на базе NNUE, плюсом к ручной ~ 300 — 400 пунктов;

• железо, считая от машин 1960-х, производительностью до 1 млн. опер/сек ~ 1000 пунктов.

Прибавки от использования дебютных книг и эндшпильных баз можно считать незначительными и оценить их соответственно как 80 и 20 пунктов в прошлом, и около нуля сейчас.

Эти цифры приводятся только для ориентировки, чтобы было понятно «что почем». Хотя указанные составляющие сами по себе и малосвязаны, но они все‑таки влияют друг на друга. Их нельзя использовать слишком прямолинейно и уж тем более механически складывать между собой. Для самостоятельной проверки данных вводных рекомендую обратиться к программе, которая предлагалась в конце IV части и ранним версиям Стокфиша.

История компьютерных шахмат и соответственно совершенствования методов, началась в 50-е годы с попыток построить селективный перебор типа Б по Шеннону, с мощными отсечениями на базе шахматных принципов и мудрёной оценочной функцией.

Но шахматные программы «категории Б» так и не взлетели. Шахматные знания в виде определенных шахматных правил не получалось вносить, потому что в игре слишком много исключений из таких правил, а обобщения часто не применимы в конкретных ситуациях. В то же время одна — две серьезные ошибки обычно решают исход партии. Внесение изощренных знаний в оценочную функцию, тоже не приводило к улучшениям по причинам уже озвученным выше.

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

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

Хуже всего, что даже если постепенно совершенствовать надежность каждого хода, допустим до 90% (что само по себе большой прогресс) то в процессе партии, делая ход за ходом, программа все равно свои одну‑две ошибки найдет и, так или иначе, проиграет. Таким образом в ранние годы никак не получалось добиться прогресса разработки, как бы ни старались авторы подобных «умных» программ. Но это отдельная и очень поучительная история.

Зато с середины 70-х (а кое‑где и раньше) вперед продвинулись шахматные программы с так называемым перебором «на полную ширину». То есть программы отсекающие как правило без потерь, в основном альфа‑бетой.

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

Эффективность современных методов отсечений, помимо того что они реально полезны, подкрепляется сокращенным перебором. Когда‑то резкое разрастание дерева с глубиной считалось препятствием. Но современные программы сумели обернуть это препятствие в свою пользу. Ведь верно и обратное — небольшое сокращение глубины перебора резко уменьшает число рассматриваемых позиций и соответственно требуемый вычислительный ресурс. В то же время надежность остается на уровне и потому в совокупности с хорошим методом, например нулевым ходом, обеспечит качество и надежность, аналогичное перебору на большую глубину.

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

Здесь неизбежно возникает вопрос — ну и к чему все это? Зачем еще больше улучшать шахматные программы, если уровень человека уже давно и намного превзойден? Какова цель этих усилий?

Но, честно сказать, уровень человека оказался довольно невысок. Это в прошлые времена он виделся как сияющая и недостижимая вершина. В наши дни для многих история компьютерных шахмат начинается уже с поражения Каспарова от Дип Блю. А для некоторых даже с появления программы Рыбка. А если кто и вспоминает что было до нее, то либо редко, либо очень кратко.

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

На самом деле можно поставить перед собой более достижимую задачу. Можно ли решить шахматы в практическом смысле? Если бы можно было разыграть из какой‑либо позиции партию и получить результат совпадающий с ее «решением» хотя бы в 95% случаев, то на практике это нас бы вполне устроило.

Но не слишком ли это фантастические ожидания? Насколько далеко от нас подобное решение? Как узнать, совпадает ли оно с идеальным, ведь никаких 32-фигурных таблиц «окончаний» нет, и не предвидится? Такое «решение шахмат» тоже кажется малореальным, но на самом деле оно уже где‑то просматривается, и в современных технических условиях не так уж невозможно, как кажется.

Здесь можно предложить кое‑какие признаки, указывающие на возможный итог розыгрыша позиции. Начать с того, что на самом деле мы фактически знаем итог всех относительно сбалансированных позиций, включая начальную. Это ничья. То же самое можно сказать и про так называемые «выигранные позиции», оценка которых не вызывает сомнений. Это победа одной из сторон.

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

В настоящее время остается только решить так называемые позиции «на два результата». Пласт таких позиций все еще огромен. Как узнать какое же истинное решение у каждой такой позиции?

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

Обычно чтобы обеспечить равные условия, данные позиции разыгрываются шахматными программами дважды, со сменой цвета. Если в каком‑либо наборе таких позиций ничейность в парах партий превысит 90 — 95% процентов случаев, то мы можем утверждать, что решение шахмат, по крайней мере в нашем определении, уже где‑то не за горами. Иначе говоря, количество результатов 1,5 — 0,5 в парах партий должно быть меньше 5%.

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

Конечно сравнение результатов матчей старых и матчей новых программ обязательно должно производиться в тех же самых условиях контроля времени и набора позиций, поскольку эти стартовые условия сильно влияют на ничейность пар. Ускорение контроля и извлечение части позиций из набора может серьезно понизить процент ничейности.

К сожалению, а может быть к счастью, в настоящее время на практике процент ничьих в наборах стартовых позиций «на два результата» достигает всего 60 — 70% и относительно идеальный результат все еще кажется недостижимым. Кроме того, если по мере совершенствования программ извлекать из подобного набора позиции, которые будут склоняться к победной или ничейной оценке, то такой процент можно поддерживать еще долго. По крайней мере, пока большая часть позиций не перейдут в статус определенных.

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

Между тем, намечаются кое‑какие технические тенденции, которые в итоге могут привести к искомому «практическому решению».

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

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

Далее помогли оупенсорс и краудфандинг сообщества компьютерных шахмат, с которого стартовал проект Стокфиш в 2011-м. Они оказались сильнее креативных и материальных ресурсов частных коммерческих разработчиков (как уже упоминалось во вступлении, крупные компании видимо не особо привлекала емкость шахматного рынка, а только его потенциал общественной значимости).

Также некоторый вклад внесло определение действенного метода тюнинга параметров поиска — SPSA. И конечно широкое распространение метода распараллеливания LasySMP в 2014 — 2015 годах решило одну из ключевых проблем компьютерных шахмат.

Процесс постепенных улучшений поиска в движках продолжается и в наши дни. Все идеи в современных проектах проверяются на оселке опыта на тестовых платформах по типу OpenBench для шахмат.

Что же можно ожидать в будущем? Какие пути совершенствования программ, помимо эволюционного прогресса поиска, просматриваются уже сейчас?

Начиная с 2017 года, новое видение перспектив оценки позиции и архитектуры всей шахматной программы предложили нейросети глубокого обучения Альфа Зеро и Лилы. А с 2020-го, в более практическом смысле для программ на классической базе, прорыв принесло появление неглубоких полносвязных сетей NNUE. Даже несмотря на свой относительно небольшой размер они позволили обычным программам шагнуть вперед. Но такие сети по‑прежнему гораздо слабее сравнительно сетей Альфа Зеро и даже младших сетей Лилы.

Вынужденные использовать относительно слабые вычислительные возможности векторов современных центральных процессоров, сети NNUE производят обычно только около 200 тысяч математических операций для вычисления оценки отдельной позиции. В то же время сеть Альфа Зеро производила 1,5 миллиарда вычислений на позицию, используя TPU, а крупнейшая сеть Лилы производит их как минимум еще на порядок больше на тензорных ядрах современных видеокарт. Естественно, сама по себе оценка позиции из таких сетей в разы лучше.

А ведь всего несколько сантиметров отделяет классические программы от мощных вычислительных ресурсов матричных умножителей на современных GPU. Если бы не большая задержка передачи данных на видеокарту...

Но именно слабость нейросети NNUE оставляет нам надежду на огромный потенциал ее дальнейшего усовершенствования. Кроме эволюционных изменений в поиске, вполне возможны поистине революционные изменения во второй важной части шахматных программ на классической базе — в оценке. И на то в настоящее время появляются технические предпосылки.

Появление встроенных матричных вычислителей NPU в массовых моделях центральных процессоров с производительностью от 50 TOPS и выше, позволит резко увеличить возможные объемы вычислений на единицу времени непосредственно в CPU. При, можно надеяться, небольшой latency. Или все‑таки реально уменьшение величины задержки передачи данных на различные внешние ускорители? По крайней мере на этот параметр сейчас обратили внимание производители соответствующего железа, в связи с резким ростом популярности мультиагентных систем.

Таким образом, уже существуют готовые процессорные архитектуры, которые позволят резко увеличить производительность CPU. Если/как только, они станут мейнстримом, мечты об идеальных шахматах могут реализоваться.

В свою очередь увеличение вычислительных возможностей позволит нарастить размеры нейросетей шахматных программ на классической базе до относительно нормальных размеров. А с ними резко подтянется и их общий уровень силы оценки, при сохранении скорости перебора таких программ. Можно надеяться, что уровень поднимется даже до более‑менее сопоставимого с качеством оценки позиции младших нейросетей Лилы.

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

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

Помимо всего прочего, при переходе на более глубокую сеть напрашивается использование выхода policy, который пока не применим на архитектуре NNUE, но с успехом используется Альфа Зеро и Лилой. Этот выход нейросети, кроме той оценки позиции, которую производит выход value, дополнительно дает ходы‑кандидаты с оценкой их «перспективности».

Такие ходы можно с пользой применить при сортировке в классических программах вместо (а лучше вместе с) History. Так же их можно применить при распараллеливании для «отлавливания» ходов‑кандидатов на ветках преждевременно отсеченных основным перебором, что крайне важно в современных условиях. Это дает альтернативный взгляд на ходы‑кандидаты на рано отсекаемых побочных вариантах, чем занимается пока только History и, непроизвольно, несинхронизированная выборка потоков (см. соображения по распараллеливанию в VI части статьи).

Между тем, мы так и не коснулись методов используемых Альфа Зеро и ее последователями. А все, что написано в данной статье, ни в одном месте не подходит для объяснения принципов работы таких архитектур. Поэтому тем, кто все же интересуется этой постепенно уходящей в прошлое программой, придется разбираться отдельно. Благо в интернете можно найти подробные блок‑схемы, разъясняющие принцип ее работы.

Программа Лила (Leela Chess Zero, Lc0) значительно улучшила принципы работы Альфа Зеро и усилила всю систему, но желающих последовать ее примеру в топе программ по‑прежнему очень немного. Пожалуй что, можно назвать еще программу Ceres, и все. Программисты движков, которые врываются в топ в настоящее время, предпочитают отталкиваться от классической базы.

Хотя у программ на базе Альфа Зеро наблюдается некоторый прогресс, тем не менее он вовсе не такой как хотелось бы. Так, в последнее время Лила начала отставать от Стокфиша и других движков. Старые организационные и технические проблемы разработки по‑прежнему требуют разрешения. А потому перспективы всех подобных программ выглядят достаточно туманно.

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

Если вернуться обратно к перспективам обычных движков, то следует напротив, несколько поумерить пыл. Конечно, обозначенные выше варианты развития событий выглядят действительно интересно. Но следует все же иметь в виду некоторые моменты. Все те многообещающие возможности совсем не обязательно реализуются в ближайшем будущем, пусть они и напрашиваются. И вовсе не обязательно дадут реально полезный и применимый выход, хотя это и выглядит возможным.

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

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

• Вся статья в Pdf