Наверное многие из вас помнят шахматные состязания людей против компьютеров, которые проводились еще относительно недавно. Обычная картина для того времени - на сцене, за шахматным столом, под светом софитов и вспышками фотокамер в своих креслах расположились два человека. Один из них - шахматный гроссмейстер, сосредоточенно смотрит на доску. Второй же - оператор, часто поглядывает на экран монитора, который установлен рядом. Многочисленные зрители затаив дыхание наблюдают за этим действом со стороны.
Но самые глубокие страсти кипят за кулисами. Там не находит себе места многочисленная команда шахматной машины. Их труды только что закончились и они вынуждены просто наблюдать. Здесь находится группа умудренных опытом гроссмейстеров, которые на протяжении многих недель вкладывали в машину как свои огромные знания, так и многовековой опыт всего человечества. Здесь же многочисленная команда программистов, которая помогала им в этом процессе. Наконец, все действо патронируется большой корпорацией, которая не поскупилась оплатить их труды и конечно же задействовала для игры огромные вычислительные мощности. Наконец-то все эти многомиллионные вливания помогут сокрушить человека.
Красочная картина... Но очень далекая от реальности
*****
Наблюдая много лет за тем, как ломаются копья на многочисленных страницах интернета - в видео, чатах, на форумах или иных открытых обсуждениях, мне становится немного обидно за тех, обычно малоизвестных людей, чьи идеи являются истинным источником силы современных шахматных программ. К сожалению, труды, которые привели к созданию методов, а так же сами эти методы, усилившие шахматные программы до заоблачных высот, до сих пор неизвестны не только широкой публике, но по большей части даже небольшой группе энтузиастов компьютерных шахмат. О том как работают современные шахматные программы, какие методы первичны и делают программы настолько сильными, какие вторичны или совсем малополезны и хотелось бы обсудить в данном цикле статей. Мы коснемся всех основных подходов, которые лежат в основе игры тех шахматных монстров, что прописаны в памяти наших телефонов и компьютеров.
Но сначала небольшой дисклеймер. Автор не является программистом и хотя на то, чтобы досконально познакомиться с основными алгоритмами ушло немало времени, понятно что разработчики сильных шахматных программ обладают гораздо большими знаниями по своему профилю, особенно там где необходимо непосредственное обращение к коду.
Также хотелось бы предупредить, что в этом цикле статей мы не коснемся программ созданных по типу Альфа Зеро, то есть программ использующих перебор на основе метода Монте-Карло и оценку на базе больших сверточных/трансформерных моделей нейросетей глубокого обучения.
Не считая себя достаточно квалифицированным для подробного разбора таких программ, тем не менее полагаю, что некоторое общее обсуждение применяемых в них методов все-таки вполне возможно. Кроме того стоит упомянуть, что с момента появления Альфа Зеро уже прошло много времени и эта программа в значительной степени устарела. В настоящее время ее заменила программа Лила Чесс Зеро (Leela Chess Zero, Lc0), построенная на базе принципов Альфа Зеро. Но эта программа ушла довольно далеко от своего первоисточника, хотя и является ее идейным последователем. Так или иначе, сильнейшей в мире на текущий момент является программа Стокфиш (Stockfish), а она создана на классической базе. Именно программы такого типа мы и будем подразумевать при дальнейшем обсуждении.
*****
Но прежде, чем приступить к разбору программ, хотелось бы отметить - что же не так в описании выше. В первую очередь, подавляющее большинство сильнейших шахматных программ своего времени разрабатывались командами из двух-трех, а нередко даже из одного человека. А в настоящее время главными являются групповые opensource-проекты Стокфиша, Лилы и недавно взлетевший проект Reckless, чьи участники работают на безвозмездной основе. На протяжении всей истории компьютерных шахмат по настоящему крупные компании подключались к разработке лишь дважды и вы их все прекрасно знаете. Это IBM и Гугл. По-видимому, такое происходило из-за того, что в данной отрасли вращается относительно мало денег и крупные корпорации вмешиваются только когда им светит явный, но кратковременный выигрыш, преимущественно медийно-финансового плана. Кроме того, улучшать программы не так-то просто и проблему нельзя только лишь завалить деньгами. В обоих случаях имелся конкретный план.
Еще одна проблема связана с самыми разнообразными слухами, циркулирующими в интернете, а они по сути являются отражением общественного мнения. Так, уже многие годы в сети периодически вспыхивают обсуждения, где люди пытаются разобраться, как же работают шахматные программы и почему они так сильны. Здесь укоренилось два основных мнения. Первое упирает на некие "базы", собранные или сгенерированные людьми. Или как вариант на некие "гроссмейстерские знания", заботливо заложенные в программу квалифицированными шахматистами.
Первым на таком подходе погорел Каспаров в известных матчах с Дип Блю. Он часто уходил на малоизвестные варианты, но оказалось что компьютер вполне разбирается даже в совсем неизвестных дебютных ответвлениях. Для Дип Блю хватило обычного счета, чтобы играть очень сильно. Эндшпильные базы тогда тоже почти не использовались, так как даже в конце партии на доске оставалось немало фигур, и поэтому компьютер обычно не добирался до использования баз.
Те, кто разбирал код сильных шахматных программ знает, что внутри кода нет никаких "гроссмейстерских знаний", как в виде неких "баз знаний", так и в виде большого набора отдельных шахматных правил. Конечно определенные правила внутри есть, но они в подавляющем большинстве не шахматного характера. Но даже и правила непосредственно относящиеся к шахматам далеко не высшего уровня. Обычно правила в переборе не связаны с шахматами вообще и в значительной степени универсальны. Например, код поиска ведущей шахматной программы Стокфиш практически без изменений используется в лучших программах таких игр как сеги и сянцы. Если китайские сянцы еще похожи на обычные шахматы, то японские сеги кардинально отличаются и тем не менее их разработчики находят, что код поиска Стокфиша все равно лучший.
Что же касается возможности подключения внешних баз, нетрудно убедиться, что кроме дебютных и эндшпильных, других не существует. Но как указано выше, первые мало чего дают практически, а до вторых редко доходит по количеству фигур на доске. Движок вполне справляется своим счетом.
Даже если не уклоняться от проторенных путей, дебютные знания в плане силы игры обычно дают не больше чем людям, то есть прибавку всего в несколько десятков пунктов рейтинга, и оказывают какое-то влияние только когда соперники относительно равны по уровню. А в настоящее время даже это незначительное преимущество сошло на нет, так как программы не делают в дебюте фатальных ошибок. То же касается и эндшпильных баз.
Таким образом, шахматисты высокой квалификации, в том числе и гроссмейстеры, оказали мало влияния на развитие шахматных программ, хотя нередко их и выдвигали на передний план. В то же время истинные разработчики - программисты, часто оказывались задвинуты в тень. Конечно некоторые шахматные знания невысокого уровня требовались для оценочной функции, но авторы сильнейших программ обычно обходились знаниями уровня собственного первого - второго шахматного разряда. А если в отдельных случаях нанимались высококвалифицированные шахматисты, то они ничем не могли помочь. Бывало, что некоторые авторы едва умели играть в шахматы, но это не мешало их программам подниматься на самый верх.
Второе мнение, циркулирующее в широких кругах - ссылка на то, что компьютер "все посчитал", иногда чуть ли не до конца партии. Но как нетрудно заметить, почему-то у начинающих авторов шахматных программ, реализовавших только обычный перебор вариантов, движки играют не сильнее первого спортивного разряда, а временами и слабее, несмотря на мощные современные машины. То есть они даже слабее программ конца 70-х, запускавшихся на железе в тысячу раз медленнее. Как оказалось, "тупой перебор", о котором ведется столько разговоров, тупо не работает.
При том ветвлении, которое существует в шахматах, дерево простого перебора разрастается мгновенно, что не позволяет быстро набирать глубину и компьютер при таких условиях играет крайне слабо. Фактически полный перебор стопорится уже на глубине 5 - 6 полуходов (3 хода с обеих сторон) даже на самых скоростных машинах. Железо хоть и важно, но ни разу не решает вопрос.
Наконец, хотелось бы упомянуть вездесущие ныне нейросети. Теперь именно они стали новым "чудо-средством" и ключевым моментом всех объяснений. Разговоры о том, что практически только они и определяют силу игры шахматных программ ведутся с момента появления Альфа Зеро. Это отчасти верно в отношении программ созданных по ее типу. Но в программах собранных на классической базе, которые мы рассмотрим ниже, нейросети лишь одна из составляющих силы игры. Эти сети крайне малы по объему выполняемых в них вычислений, а потому на самом деле не особо "умны". В современных программах классические методы перебора все еще играют главную роль в формировании силы игры, хотя оценочная функция на базе нейросети уже может в чем-то с ними сравниться (но, откровенно говоря, сравнивать столь ортогональные направления довольно затруднительно).
*****
Что ж, после такого длинного вступления, давайте обсудим реально важные составляющие шахматных программ.
Для силы игры шахматной программы в первую очередь важны три фактора. Это железо, оценка и поиск. Остальные факторы малозначимы или же являются элементами вспомогательного характера (но наверное не надо разъяснять, что даже малозначимая деталь, при недолжном исполнении, может загубить любую программу).
В силу обозначенных выше причин и несмотря на многочисленные рассуждения об обратном, наименее значимым среди них видится фактор железа.
Еще в 80-е годы было установлено (а предполагалось и ранее), что сила программ значительно растет с увеличением глубины, если перебор осуществляется без потерь или практически без потерь информации вследствие отсечений. Это верно и в наши дни - с увеличением времени на обдумывание, или же скорости центрального процессора, глубина увеличивается, а следовательно сила игры последовательно и существенно возрастает.
Тем не менее, как уже упоминалось выше, хотя глубина растет, дерево простого перебора растет еще быстрее. Так что фактор железа у нас на третьем месте. Помимо того, мощность железа, это в общем-то технический параметр. Поэтому мы не будем подробно останавливаться на нем, и в дальнейшем будем ссылаться на скорость железа только по необходимости.
Если же рассматривать факторы, которые непосредственно влияют на выбор хода, то можно сказать что программа состоит из двух частей - оценки позиции (Evaluation) и поиска по дереву вариантов (Search). Оценочная функция производит оценку качества позиции на основе количества и взаимного расположения фигур, без их передвижения. Результатом является число, которое используется поиском для отбора направлений для перебора. То есть для решения в каких ветках продлить, а в каких сократить или полностью прекратить перебор - это так называемые продления, сокращения и отсечения. Позиция из которой стартует перебор называется корневой (Root). Просчитываемые из корня ходы при переборе вариантов формируют своеобразное дерево, позиции в котором называются узлами (Node).
Оценку позиции на основе выделенных параметров долгие годы не удавалась существенно улучшить. Все простые и легко вычисляемые факторы были быстро найдены, а сложные либо имели ограниченную применимость, для специфических расстановок фигур, либо требовали больше ресурсов на вычисление, чем приносили выгоды, т.е. работали в минус и от них отказывались. Тем не менее уровень оценочной функции все-таки медленно рос, но она играла явно второстепенную роль в сравнении с наиболее значимым фактором шахматных программ - поиском по дереву вариантов.
Уровень оценочной функции резко поднялся после пришествия нейросетей - в программах на классической базе нейросеть заменила именно оценочную функцию. Но все равно нейросети у таких программ остаются еще маленькими и слабыми, поэтому и не так значимы как хотелось бы. Оценочную функцию мы подробно рассмотрим позже, а пока обратимся к самому важному - поиску.
Поиску по дереву вариантов, иначе говоря - перебору, обычно придается мало значения. Многие считают, что движок перебирает все возможные ходы на определенную глубину, может быть с некоторыми "оптимизациями", и больше ничего не делает. Немного парадоксально, что такому важному фактору шахматных программ уделяется так мало внимания в общественном сознании. Тем не менее именно перебору, или в более узком смысле - отсечениям, мы в первую очередь обязаны силой игры современных шахматных программ на классической базе.
Отбрасывая заведомо не лучшие ходы, поиск современных движков ограничивается просмотром в среднем только около 1 - 2 продолжения в каждой позиции дерева перебора, при 30 - 40 возможных. То есть программы используют крайне селективный перебор, почти без ветвлений, и потому, и только потому, достигают большой глубины. А уже по достижении большой глубины движок может досчитываться до конкретных последствий своих действий и даже при слабой оценочной функции находить сильные ходы.
Опять же, влияние прироста скорости железа на этом фоне выглядит тускло. К примеру, если бы мы увеличили скорость машины в 1000 раз, как скажем было в свое время у Дип Блю относительно современных ему ПК, то это ускорение останется постоянным, сколько бы позиций мы не просмотрели. Тогда как например только альфа-бета отсечения увеличивают скорость набора глубины в тысячу раз, когда рассмотрена 1000 позиций, в миллион раз после рассмотрения миллиона позиций, в миллиард раз после рассмотрения миллиарда позиций и т. д. То есть скорость растет вместе с перебором. Ни одно железо так не может.
*****
Итак, мы установили, что на выбор ходов программой непосредственно влияют поиск по дереву вариантов и оценочная функция. Сначала попробуем в общих чертах понять как функционирует перебор.
Обход дерева вариантов грубо можно разделить на две части. Сначала выполняется основной перебор на определенную глубину для всех значимых ходов. По достижении заданной глубины перебора, он не прерывается, но в дерево теперь допускаются только форсированные ходы - в первую очередь взятия и иногда шахи.
Такой перебор называется Форсированный вариант (Quiescence Search, ФВ, QS). Он необходим, потому что нельзя заранее предугадать на какую глубину следует считать и поэтому обычный перебор на фиксированную (заданную) глубину может внезапно прекратиться на середине разменов. Слабая оценочная функция, в том числе слабая нейросетевая, не в состоянии по взаимному расположению фигур отличить реальное взятие, например ферзя, от его размена. Досчитав до заданной глубины программа будет полагать, что она приобрела ферзя, тогда как следующим ходом варианта произойдет ответное взятие, до которого перебор уже не досчитывает.
Поэтому по окончании основного перебора программа обязательно должна произвести все размены и досчитаться до "спокойной" (quiescence) позиции. Только тогда можно вызывать оценочную функцию и давать числовую оценку этой позиции. Quiescence Search - это важнейшая часть шахматной программы, которую предложили еще классики - Тьюринг и Шеннон.
Но мы сосредоточимся на основном переборе. Подробнее порядок обхода всего дерева, а также Quiescence Search мы рассмотрим позже.
В следующих частях мы поговорим об основных методах ограничения перебора, коснемся терминологии и некоторых второстепенных методов, поговорим об оценочной функции, а так же пробежимся по коду поиска Стокфиша - самой сильной шахматной программы в мире.
Продолжение следует...
