|
|
|
|
|
|
|
|
| |
|
|
|
|
|
|
|
Не нашел подходящей темы для материалов, которые хотелось бы выложить на форуме. Поэтому пусть будет еще одна тема в разделе компьютерных шахмат.
Здесь можно обсудить вопросы не связанные с новостной повесткой, а в большей степени темы касающиеся работы самих шахматных программ. Не только их структуры, но и применения. Причем не обязательно движков, но и оболочек, обучающих курсов и всего остального.
Тем не менее тема создавалась не из общих соображений, а по вполне конкретной причине. Здесь мне хотелось бы разместить свою статью о принципах работы шахматных программ. Она планируется к выкладке на Хабре. Но решил поместить ее и здесь, в более шахматной среде. Планируется выкладывать ее на форуме с опережением на несколько дней, в порядке предварительного обсуждения.
Вопросы и комментарии приветствуются. Желательно только задавать их после выкладки очередной части текста, так как видимо его придется разбивать на несколько сообщений. Текст будет выкладываться начиная со следующего сообщения. |
|
|
| |
|
|
Шахматные программы I. Вступление
Наверное многие из вас помнят шахматные состязания людей против компьютеров, которые проводились еще относительно недавно. Обычная картина для того времени - на сцене, за шахматным столом, под светом софитов и вспышками фотокамер в своих креслах расположились два человека. Один из них - шахматный гроссмейстер, сосредоточенно смотрит на доску. Второй же - оператор, часто поглядывает на экран монитора, который установлен рядом. Многочисленные зрители затаив дыхание наблюдают за этим действом со стороны.
Но самые глубокие страсти кипят за кулисами. Там не находит себе места многочисленная команда шахматной машины. Их труды только что закончились и они вынуждены просто наблюдать. Здесь находится группа умудренных опытом гроссмейстеров, которые на протяжении многих недель вкладывали в машину как свои огромные знания, так и многовековой опыт всего человечества. Здесь же многочисленная команда программистов, которая помогала им в этом процессе. Наконец, все действо патронируется большой корпорацией, которая не поскупилась оплатить их труды и конечно же задействовала для игры огромные вычислительные мощности. Наконец-то все эти многомиллионные вливания помогут сокрушить человека.
Красочная картина... Но очень далекая от реальности |
|
|
| номер сообщения: 54-72-8226 |
|
|
|
|
*****
Наблюдая много лет за тем, как ломаются копья на многочисленных страницах интернета - в видео, чатах, на форумах или иных открытых обсуждениях, мне становится немного обидно за тех, обычно малоизвестных людей, чьи идеи являются истинным источником силы современных шахматных программ. К сожалению, труды, которые привели к созданию методов, а так же сами эти методы, усилившие шахматные программы до заоблачных высот, до сих пор неизвестны не только широкой публике, но по большей части даже небольшой группе энтузиастов компьютерных шахмат. О том как работают современные шахматные программы, какие методы первичны и делают программы настолько сильными, какие вторичны или совсем малополезны и хотелось бы обсудить в данном цикле статей. Мы коснемся всех основных подходов, которые лежат в основе игры тех шахматных монстров, что прописаны в памяти наших телефонов и компьютеров.
Но сначала небольшой дисклеймер. Автор не является программистом и хотя на то, чтобы досконально познакомиться с основными алгоритмами ушло немало времени, понятно что разработчики сильных шахматных программ обладают гораздо большими знаниями по своему профилю, особенно там где необходимо непосредственное обращение к коду.
Также хотелось бы предупредить, что в этом цикле статей мы не коснемся программ созданных по типу Альфа Зеро, то есть программ использующих перебор на основе метода Монте-Карло и оценку на базе больших сверточных/трансформерных моделей нейросетей глубокого обучения.
Не считая себя достаточно квалифицированным для подробного разбора таких программ, тем не менее полагаю, что некоторое общее обсуждение применяемых в них методов все-таки вполне возможно. Кроме того стоит упомянуть, что с момента появления Альфа Зеро уже прошло много времени и эта программа в значительной степени устарела. В настоящее время ее заменила программа Лила Чесс Зеро (Leela Chess Zero, Lc0), построенная на базе принципов Альфа Зеро. Но эта программа ушла довольно далеко от своего первоисточника, хотя и является ее идейным последователем. Так или иначе, сильнейшей в мире на текущий момент является программа Стокфиш (Stockfish), а она создана на классической базе. Именно программы такого типа мы и будем подразумевать при дальнейшем обсуждении. |
|
|
| номер сообщения: 54-72-8227 |
|
|
|
|
*****
Но прежде, чем приступить к разбору программ, хотелось бы отметить - что же не так в описании выше. В первую очередь, подавляющее большинство сильнейших шахматных программ своего времени разрабатывались командами из двух-трех, а нередко даже из одного человека. А в настоящее время главными являются групповые opensource-проекты Стокфиша, Лилы и недавно взлетевший проект Reckless, чьи участники работают на безвозмездной основе. На протяжении всей истории компьютерных шахмат по настоящему крупные компании подключались к разработке лишь дважды и вы их все прекрасно знаете. Это IBM и Гугл. По-видимому, такое происходило из-за того, что в данной отрасли вращается относительно мало денег и крупные корпорации вмешиваются только когда им светит явный, но кратковременный выигрыш, преимущественно медийно-финансового плана. Кроме того, улучшать программы не так-то просто и проблему нельзя только лишь завалить деньгами. В обоих случаях имелся конкретный план.
Еще одна проблема связана с самыми разнообразными слухами, циркулирующими в интернете, а они по сути являются отражением общественного мнения. Так, уже многие годы в сети периодически вспыхивают обсуждения, где люди пытаются разобраться, как же работают шахматные программы и почему они так сильны. Здесь укоренилось два основных мнения. Первое упирает на некие "базы", собранные или сгенерированные людьми. Или как вариант на некие "гроссмейстерские знания", заботливо заложенные в программу квалифицированными шахматистами.
Первым на таком подходе погорел Каспаров в известных матчах с Дип Блю. Он часто уходил на малоизвестные варианты, но оказалось что компьютер вполне разбирается даже в совсем неизвестных дебютных ответвлениях. Для Дип Блю хватило обычного счета, чтобы играть очень сильно. Эндшпильные базы тогда тоже почти не использовались, так как даже в конце партии на доске оставалось немало фигур, и поэтому компьютер обычно не добирался до использования баз.
Те, кто разбирал код сильных шахматных программ знает, что внутри кода нет никаких "гроссмейстерских знаний", как в виде неких "баз знаний", так и в виде большого набора отдельных шахматных правил. Конечно определенные правила внутри есть, но они в подавляющем большинстве не шахматного характера. Но даже и правила непосредственно относящиеся к шахматам далеко не высшего уровня. Обычно правила в переборе не связаны с шахматами вообще и в значительной степени универсальны. Например, код поиска ведущей шахматной программы Стокфиш практически без изменений используется в лучших программах таких игр как сеги и сянцы. Если китайские сянцы еще похожи на обычные шахматы, то японские сеги кардинально отличаются и тем не менее их разработчики находят, что код поиска Стокфиша все равно лучший.
Что же касается возможности подключения внешних баз, нетрудно убедиться, что кроме дебютных и эндшпильных, других не существует. Но как указано выше, первые мало чего дают практически, а до вторых редко доходит по количеству фигур на доске. Движок вполне справляется своим счетом.
Даже если не уклоняться от проторенных путей, дебютные знания в плане силы игры обычно дают не больше чем людям, то есть прибавку всего в несколько десятков пунктов рейтинга, и оказывают какое-то влияние только когда соперники относительно равны по уровню. А в настоящее время даже это незначительное преимущество сошло на нет, так как программы не делают в дебюте фатальных ошибок. То же касается и эндшпильных баз.
Таким образом, шахматисты высокой квалификации, в том числе и гроссмейстеры, оказали мало влияния на развитие шахматных программ, хотя нередко их и выдвигали на передний план. В то же время истинные разработчики - программисты, часто оказывались задвинуты в тень. Конечно некоторые шахматные знания невысокого уровня требовались для оценочной функции, но авторы сильнейших программ обычно обходились знаниями уровня собственного первого - второго шахматного разряда. А если в отдельных случаях нанимались высококвалифицированные шахматисты, то они ничем не могли помочь. Бывало, что некоторые авторы едва умели играть в шахматы, но это не мешало их программам подниматься на самый верх. |
|
|
| номер сообщения: 54-72-8228 |
|
|
|
|
Второе мнение, циркулирующее в широких кругах - ссылка на то, что компьютер "все посчитал", иногда чуть ли не до конца партии. Но как нетрудно заметить, почему-то у начинающих авторов шахматных программ, реализовавших только обычный перебор вариантов, движки играют не сильнее первого спортивного разряда, а временами и слабее, несмотря на мощные современные машины. То есть они даже слабее программ конца 70-х, запускавшихся на железе в тысячу раз медленнее. Как оказалось, "тупой перебор", о котором ведется столько разговоров, тупо не работает.
При том ветвлении, которое существует в шахматах, дерево простого перебора разрастается мгновенно, что не позволяет быстро набирать глубину и компьютер при таких условиях играет крайне слабо. Фактически полный перебор стопорится уже на глубине 5 - 6 полуходов (3 хода с обеих сторон) даже на самых скоростных машинах. Железо хоть и важно, но ни разу не решает вопрос.
Наконец, хотелось бы упомянуть вездесущие ныне нейросети. Теперь именно они стали новым "чудо-средством" и ключевым моментом всех объяснений. Разговоры о том, что практически только они и определяют силу игры шахматных программ ведутся с момента появления Альфа Зеро. Это отчасти верно в отношении программ созданных по ее типу. Но в программах собранных на классической базе, которые мы рассмотрим ниже, нейросети лишь одна из составляющих силы игры. Эти сети крайне малы по объему выполняемых в них вычислений, а потому на самом деле не особо "умны". В современных программах классические методы перебора все еще играют главную роль в формировании силы игры, хотя оценочная функция на базе нейросети уже может в чем-то с ними сравниться (но, откровенно говоря, сравнивать столь ортогональные направления довольно затруднительно). |
|
|
| номер сообщения: 54-72-8229 |
|
|
|
|
*****
Что ж, после такого длинного вступления, давайте обсудим реально важные составляющие шахматных программ.
Для силы игры шахматной программы в первую очередь важны три фактора. Это железо, оценка и поиск. Остальные факторы малозначимы или же являются элементами вспомогательного характера (но наверное не надо разъяснять, что даже малозначимая деталь, при недолжном исполнении, может загубить любую программу).
В силу обозначенных выше причин и несмотря на многочисленные рассуждения об обратном, наименее значимым среди них видится фактор железа.
Еще в 80-е годы было установлено (а предполагалось и ранее), что сила программ значительно растет с увеличением глубины, если перебор осуществляется без потерь или практически без потерь информации вследствие отсечений. Это верно и в наши дни - с увеличением времени на обдумывание, или же скорости центрального процессора, глубина увеличивается, а следовательно сила игры последовательно и существенно возрастает.
Тем не менее, как уже упоминалось выше, хотя глубина растет, дерево простого перебора растет еще быстрее. Так что фактор железа у нас на третьем месте. Помимо того, мощность железа, это в общем-то технический параметр. Поэтому мы не будем подробно останавливаться на нем, и в дальнейшем будем ссылаться на скорость железа только по необходимости.
Если же рассматривать факторы, которые непосредственно влияют на выбор хода, то можно сказать что программа состоит из двух частей - оценки позиции (Evaluation) и поиска по дереву вариантов (Search). Оценочная функция производит оценку качества позиции на основе количества и взаимного расположения фигур, без их передвижения. Результатом является число, которое используется поиском для отбора направлений для перебора. То есть для решения в каких ветках продлить, а в каких сократить или полностью прекратить перебор - это так называемые продления, сокращения и отсечения. Позиция из которой стартует перебор называется корневой (Root). Просчитываемые из корня ходы при переборе вариантов формируют своеобразное дерево, позиции в котором называются узлами (Node).
Оценку позиции на основе выделенных параметров долгие годы не удавалась существенно улучшить. Все простые и легко вычисляемые факторы были быстро найдены, а сложные либо имели ограниченную применимость, для специфических расстановок фигур, либо требовали больше ресурсов на вычисление, чем приносили выгоды, т.е. работали в минус и от них отказывались. Тем не менее уровень оценочной функции все-таки медленно рос, но она играла явно второстепенную роль в сравнении с наиболее значимым фактором шахматных программ - поиском по дереву вариантов.
Уровень оценочной функции резко поднялся после пришествия нейросетей - в программах на классической базе нейросеть заменила именно оценочную функцию. Но все равно нейросети у таких программ остаются еще маленькими и слабыми, поэтому и не так значимы как хотелось бы. Оценочную функцию мы подробно рассмотрим позже, а пока обратимся к самому важному - поиску.
Поиску по дереву вариантов, иначе говоря - перебору, обычно придается мало значения. Многие считают, что движок перебирает все возможные ходы на определенную глубину, может быть с некоторыми "оптимизациями", и больше ничего не делает. Немного парадоксально, что такому важному фактору шахматных программ уделяется так мало внимания в общественном сознании. Тем не менее именно перебору, или в более узком смысле - отсечениям, мы в первую очередь обязаны силой игры современных шахматных программ на классической базе.
Отбрасывая заведомо не лучшие ходы, поиск современных движков ограничивается просмотром в среднем только около 1 - 2 продолжения в каждой позиции дерева перебора, при 30 - 40 возможных. То есть программы используют крайне селективный перебор, почти без ветвлений, и потому, и только потому, достигают большой глубины. А уже по достижении большой глубины движок может досчитываться до конкретных последствий своих действий и даже при слабой оценочной функции находить сильные ходы.
Опять же, влияние прироста скорости железа на этом фоне выглядит тускло. К примеру, если бы мы увеличили скорость машины в 1000 раз, как скажем было в свое время у Дип Блю относительно современных ему ПК, то это ускорение останется постоянным, сколько бы позиций мы не просмотрели. Тогда как например только альфа-бета отсечения увеличивают скорость набора глубины в тысячу раз, когда рассмотрена 1000 позиций, в миллион раз после рассмотрения миллиона позиций, в миллиард раз после рассмотрения миллиарда позиций и т. д. То есть скорость растет вместе с перебором. Ни одно железо так не может. |
|
|
| номер сообщения: 54-72-8230 |
|
|
|
|
*****
Итак, мы установили, что на выбор ходов программой непосредственно влияют поиск по дереву вариантов и оценочная функция. Сначала попробуем в общих чертах понять как функционирует перебор.
Обход дерева вариантов грубо можно разделить на две части. Сначала выполняется основной перебор на определенную глубину для всех значимых ходов. По достижении заданной глубины перебора, он не прерывается, но в дерево теперь допускаются только форсированные ходы - в первую очередь взятия и иногда шахи.
Такой перебор называется Форсированный вариант (Quiescence Search, ФВ, QS). Он необходим, потому что нельзя заранее предугадать на какую глубину следует считать и поэтому обычный перебор на фиксированную (заданную) глубину может внезапно прекратиться на середине разменов. Слабая оценочная функция, в том числе слабая нейросетевая, не в состоянии по взаимному расположению фигур отличить реальное взятие, например ферзя, от его размена. Досчитав до заданной глубины программа будет полагать, что она приобрела ферзя, тогда как следующим ходом варианта произойдет ответное взятие, до которого перебор уже не досчитывает.
Поэтому по окончании основного перебора программа обязательно должна произвести все размены и досчитаться до "спокойной" (quiescence) позиции. Только тогда можно вызывать оценочную функцию и давать числовую оценку этой позиции. Quiescence Search - это важнейшая часть шахматной программы, которую предложили еще классики - Тьюринг и Шеннон.
Но мы сосредоточимся на основном переборе. Подробнее порядок обхода всего дерева, а также Quiescence Search мы рассмотрим позже.
В следующих частях мы поговорим об основных методах ограничения перебора, коснемся терминологии и некоторых второстепенных методов, поговорим об оценочной функции, а так же пробежимся по коду поиска Стокфиша - самой сильной шахматной программы в мире.
Продолжение следует... |
|
|
| номер сообщения: 54-72-8231 |
|
|
|
|
| Здесь заканчивается первая часть статьи. Остальные буду выкладывать позже. Ориентировочно с интервалом в два-три дня, если не будет каких-то затруднений. По крайней мере пока так планируется. |
|
|
| номер сообщения: 54-72-8232 |
|
|
|
|
Вообще да, я фактически везде встречаю то, о чём автор говорит (а, это Вы и есть. Оставлю для истории всё равно  ). Причём даже у гроссмейстеров, которые программами уже 20+ лет при подготовке пользуется.
И про таблицы, и про базы, и про "всё посчитали", а про то, что фактически главное, что улучшилось - это спекулятивное расширение алгоритма альфабета на чёрно-белые играх типа шахмат, никто и не говорит.
Тут вот есть очень в тему график - https://github.com/official-stockfish/Stockfish/wiki/Useful-data#branching-factor-of-stockfish , который показывает фактор ветвления в зависимости от версии и от глубины со стартовой (вроде бы) позиции. Если кому-то кажется, что разница 1,7 и 1,9 невелика, то вот можно напомнить, что (1,9/1,7) ^ 30 это 29, то есть стокфишу 10, чтобы дойти до глубины 30, понадобится приблизительно в 28 раз больше узлов, и чем дальше - тем больше эта разница.
Кстати, там же ещё есть данные про таблицы - https://github.com/official-stockfish/Stockfish/wiki/Useful-data#elo-gain-using-syzygy
К вопросу об их важности при реальной игре, даже до всяких нейросетей 6-фигурные таблицы были там 15 эло примерно. |
|
|
| номер сообщения: 54-72-8233 |
|
|
|
|
| Вообще в последний раз, когда я проверял, в районе вроде бы SF16, Quescence Search стоил чуть больше 150 эло (если при достижении глубины 0 просто возвращать статическую оценку вместо него). |
|
|
| номер сообщения: 54-72-8234 |
|
|
|
|
Один из авторов Дип Блю когда-то писал, что QS дает столько же, как и углубление на 4 полухода без QS. Правда с тех пор много воды утекло - современное понятие глубины стало уж очень специфическим.
Если в целом, измерение полезности каждого метода непростое занятие. Поиск современных программ настолько изощренный, что даже если отключишь один метод, то его "подстрахует" другой метод и объективного измерения не получится.
Для примера, допустим один патч дает 100 пунктов, при отдельном измерении, и другой тоже 100 пунктов. Но предположим отсекают они 95 % одних и тех же узлов. Тогда в сумме они дадут скорее всего только 105 пунктов. Если конечно не тестировать их один поверх другого.
Если же попытаться их "упростить", то по отдельности каждый из них даст лишь -5 пунктов регресса, поскольку при удалении одного из патчей его узлы сразу же "подхватывает" другой. Но если убрать оба, то регресс сразу возрастет до -105 пунктов. Такая вот забавная арифметика. |
|
|
| номер сообщения: 54-72-8235 |
|
|
|
|
Ну это понятно, с другой стороны, именно qsearch никто не страхует особо, то есть тут можно куда более прямо всё сделать.
Что имеется в виду - он же вызывается в самом начале функции search по условию
if (depth = 0)
return qsearch(от всего)
Если же это поменять на
if (depth = 0)
return evaluate(pos)
то никто и ничего не страхует.
Принципиальное отличие от эвристик отсечения разных в том, что тут идёт безусловное отсечение по достижению глубины 0, в то время как в эвристиках отсечения они идут одна за другой и действительно одна может страховать другую.
Ну есть ещё применения qsearch во всяких других местах, но они там единицы эло дают, да и когда я этот тест делал, был он только в razoring, ну а эта эвристика почти ничего не даёт сама по себе. |
|
|
| номер сообщения: 54-72-8236 |
|
|
|
|
Шахматные программы II. Отсечения
Самой важной частью шахматной программы, которая вносит основной вклад в силу игры, является направленный перебор. А самой главной частью направленного перебора являются отсечения и сокращения наиболее неперспективных ходов. Отбрасывая наименее важные ветви, программа вкладывает ресурсы машины в наиболее перспективные варианты. Чем больше отсекает программа, тем дальше она углубляется по дереву вариантов. И чем глубже она считает, тем сильнее играет.
Если бы программа считала до конца - до конечного результата в партии, то ей не потребовалась бы даже оценочная функция. Исторически, программы считали все глубже и глубже, и соответственно играли все лучше и лучше.
Здесь мы рассмотрим три наиболее значимых метода ограничения перебора вариантов. Они наиболее действенны, поскольку применяются по всей глубине дерева, хотя и срабатывают не в каждой позиции. Именно они приводят к наибольшему сокращению ветвления вариантов в дереве перебора, а значит и к наибольшему углублению.
Среди них наиболее важным являются Альфа-Бета отсечения (Alpha-Beta Pruning). Это метод отсечений без потерь, то есть он всегда выдает тот же ход и оценку позиции, что и полный перебор, независимо от качества оценочной функции, но делает это гораздо быстрее.
Двумя другими важными методами являются методы отсечений/сокращений с потерями информации. Такие методы обычно называют эвристиками. Один из них, это метод отсечений с помощью пропуска хода - иначе говоря, нулевой ход (Null Move Pruning), второй - метод сокращений на поздних ходах (Late Move Reductions, LMR).
В большинстве позиций отсечения начинаются с пробного перебора и попытки отсечь нулевым ходом, затем программа пытается отсечь альфа-бетой и если с ее помощью отсечь не получается, тогда подключается LMR и сокращает глубину перебора на оставшихся ходах.
Давайте рассмотрим эти методы более подробно. Ниже приведены схемы небольшого участка дерева перебора. Верхняя диаграмма предполагает позицию с которой начинается перебор вариантов или позицию где-то в глубине дерева, на локальном участке. Каждая линия, это один из возможных ходов в данной позиции, который перебирается на определенную (заданную) глубину. По ним ход за ходом получаются следующие позиции на бОльшую глубину, из которых генерируются следующие ходы и т. д.
Просчитаем на схеме ниже первый возможный ход в начальной позиции на заданную глубину и получим его оценку (например +5). Теперь перейдем к проверке второго возможного варианта. Но сначала попытаемся отсечь его с помощью нулевого хода. |
|
|
| номер сообщения: 54-72-8237 |
|
|
|
|
Общая очередность перебора будет следующая:
1. Principal Variation (PV)
Как уже написано выше, сначала смотрим основной вариант (PV). Это любая ветка в начале перебора или лучшая с предыдущего перебора, если таковой ранее проводился, но c добавлением полухода глубины. На схеме ниже она находится слева.
Допустим мы исследовали основной вариант и получили оценку +5. Теперь переходим к следующему варианту, который уже попытаемся отсечь.
2. Null Move Pruning
Используя метод нулевого хода попытаемся отсечь вторую ветку по-быстрому, до начала основного перебора. Для этого после первого хода варианта производим в ветке "нулевой" ход и далее пробный перебор с сокращенной глубиной. Иначе говоря сейчас в нижней позиции на схеме ход противника, но мы пропускаем его и снова ходим за себя. Мы нарушаем правила шахмат, но нам нужно лишь получить информацию об отсечении.
Главный принцип - если даже после двух наших ходов подряд, оценка все равно ниже чем у основного варианта (на схеме +3 меньше, чем +5), то такой вариант никуда не годится, поэтому сразу же отсекаем его.
Логика следующая - поскольку право хода обычно является преимуществом, то два хода подряд просто огромное преимущество. И если даже они не помогли, значит вариант плох и не достоин рассмотрения. Можно отсекать. Конечно, для случаев цугцванга есть специальные ограничения.
Если же мы напротив, получили оценку выше, чем у основного варианта (допустим +18), значит у хода есть некоторые перспективы. Мы отменяем нулевой ход и приступаем к основному перебору. Генерируем ходы из нижней позиции на схеме теперь уже по всем правилам шахмат. |
|
|
| номер сообщения: 54-72-8238 |
|
|
|
|
3. Ordering
Соответственно генерируются ответы соперника и производится их сортировка в порядке перспективности. По каким правилам - будет описано ниже.
4. Alpha-Beta Pruning
Теперь попытаемся снова отсечь, на этот раз альфа-бетой.
Схема альфа-бета отсечений, после неудачного применения нулевого хода (+18):
Смотрим на схеме ходы из нижней позиции. Сначала делаем первый ход по сортировке. Исследуем его на полную (то есть заданную) глубину.
Допустим, мы получили для первого рассмотренного хода оценку +2. Это предполагаемый ответ нашего соперника. Лучше чем на +2 в данном варианте мы уже не можем рассчитывать, поскольку здесь ход выбирает соперник, а на ответ с большей оценкой он не согласится. Отсекаем.
Действительно, мы предполагаем, что соперник не враг себе и выберет лучший ход для себя, а не для нас. То есть из всех ответов это будет ход с наименьшей оценкой. Если у других ответов оценка будет выше +2, то он их не выберет, а если ниже, то он их выберет, но тогда оценка станет еще меньше. В таком случае оценку выше +2 мы никак не получим. А это в свою очередь не устраивает уже нас, поскольку у нас в запасе есть основной вариант с оценкой +5, который мы и выберем. Значит никакие ответы в текущем варианте нас уже не устроят и нет смысла их рассматривать. Следовательно, в головной позиции схемы отсекаем второй вариант и переходим к следующему.
Если говорит технически, то +2 меньше чем +5, а значит у нас произошло отсечение по бете. Правда в реальных программах обычно используют инвертированную модель перебора и отсекают по превышении беты. Но здесь мы не будем на этом останавливаться.
Из схемы выше очевидно, что в первую очередь необходимо смотреть ответы, которые вызовут отсечение. Поэтому перебор следует начать с варианта, который принесет нам оценку ниже +5. Иначе перебор может затянуться. Конечно мы не можем заранее знать, какой ход принесет нам такую оценку, но можем попытаться хотя бы провести предварительную сортировку ходов на основании формальных признаков. Такая сортировка выполняется перед началом основного перебора по пункту 3.
В человеческих шахматах принцип альфа-бета отсечений тоже используется. В двух словах его логику можно описать так:
"Если в каком-то варианте мы сразу же наткнулись на сильный ответ противника, то вариант можно отбросить немедленно". То есть забраковать, не рассматривая остальные ответы. Действительно, какой смысл идти на плохой вариант? У оппонента тут есть как минимум один сильный ход и соответственно хорошая игра. Таким образом, человек может сильно экономить время на расчете подобных вариантов.
Но чтобы реализовать альфа-бету для машины, сперва надо бы определить что такое "сильный ответ" и как его найти "сразу". Первое понятно - мы просто сравниваем с оценкой основного варианта, и если она лучше, то немедленно отсекаем текущий вариант.
Второе сложнее. Человек сразу видит сильный ответ, а для машины нам придется предварительно отсортировать технически возможные ходы из позиции в порядке их выгоды для соперника. "Сильный ответ противника", это соответственно ход с наименьшей оценкой для нас. Но поскольку мы заранее не знаем какие будут оценки ходов не проводя перебора, то попробуем их оценить предварительно, на основании простых внешних признаков.
Итак, перед нами стоит задача начать перебор с ответа, оценка в котором предполагается быть меньше или равной +5. Тогда мы сможем отсечь вариант немедленно. Пусть не будет никаких лишних вычислений. Смотрим только простые признаки. Теперь вернемся к пункту 3 и рассмотрим методы сортировки. |
|
|
| номер сообщения: 54-72-8239 |
|
|
|
|
3. Ordering
Необходимо отсортировать ходы в порядке убывания их силы для соперника. Исторически сложился следующий порядок выборки ходов:
а) Сначала проверяем в хеш-таблицах, не просматривалась ли эта позиция ранее с требуемой или большей глубиной. Если такая позиция присутствует, то берем лучший ход для нее из таблицы.
Хеш-таблицы, или таблицы перестановок (Transposition table), это таблицы уже просматривавшихся ранее позиций с известной оценкой и лучшим ходом в них. По мере перебора в таблицу заносятся новые позиции, а старые удаляются по превышению выделенного объема оперативной памяти. Для хранения и поиска позиций используются хеш-ключи по методу Зобриста.
б) Смотрим "выгодные" взятия. То есть взятия с положительным материальным балансом, отсортированные по данному параметру. Взятия резко повышают оценку сопернику, иначе говоря "выгодность" хода, поэтому разумно предположить, что они будут отсекать в первую очередь.
Стандартные методы для данной процедуры - MVV/LVA или SEE.
MVV/LVA сортирует все возможные взятия в позиции по принципу соотношения ценности атакующей и атакуемой фигуры. В первую очередь смотрим взятие, где наименее сильная фигура бьет наиболее сильную, затем смотрим взятие с меньшей разницей и т. д.
SEE - сортировка взятий в позиции по соотношению числа и силы фигур нападающих и защищающих некоторое поле шахматной доски. То есть подсчет "выгодности" каждого размена отталкивается от общего числа нападений и защит на определенное поле. Это то же самое, что подсчет числа "боёв" на определенное поле у людей, которые ленятся считать размены перебором вариантов.
SEE - очень "ходовой" метод. Его используют во многих частях программы для разных целей. В старых программах его даже использовали вместо ФВ (QS), чтобы не тратить ресурсы и память для расчета разменов.
в) Смотрим тихие ходы. Сначала, это так называемые "Киллеры" (Killers), иначе говоря "убойные ходы" - ходы, которые недавно вызывали отсечение.
Логика заключается в том, что в похожих позициях обычно и отсекающие ходы одинаковые. Значит надо в первую очередь попробовать ходы недавно вызывавшие отсечение. Запоминаем два или три последних отсекавших тихих хода и рассматриваем их по принципу - самый последний отсекавший смотрим в первую очередь. По мере продвижения по дереву ряд киллеров обновляется новыми отсекавшими ходами, которые вытесняют наиболее старые. Для каждой глубины ведем отдельный список киллеров.
г) Смотрим тихие ходы в порядке статистики истории отсечений (History).
По мере перебора мы ведем статистику отсекавших ходов, но уже безотносительно подобия позиции. Ходы которые отсекают чаще и бОльшие ветки поднимаются в списке, а остальные соответственно опускаются. Будем вести таблицу таких отсечений и динамически ее обновлять. В современных программах таких таблиц несколько. Они ведутся в том числе и для взятий.
д) "Невыгодные" взятия и остальные ходы.
 |
|
|
| номер сообщения: 54-72-8240 |
|
|
|
|
*****
Теперь представим, что мы отсортировали ходы, посмотрели первый ответ соперника и отсечения альфа-бетой не произошло. Допустим оценка первого хода в схеме выше была не +2, а +7. Это больше беты, а значит отсечения нет - надо смотреть следующие ответы. Здесь, для ходов с номером по сортировке >1 возможен еще один способ сокращения перебора. Он называется LMR.
5. Late Move Reductions (LMR)
Выше мы предположили, что после рассмотрения первого ответа соперника получена оценка +7. Давайте обновим схему:
Суть метода в том, что при нормальной сортировке, оценки ходов после первого будут только расти, а значит соперник их все равно не выберет. Поэтому мы можем сэкономить и рассмотреть их с сокращенной глубиной. Причем, чем выше номер хода по сортировке, тем сильнее мы можем подрезать ветку. Если же вдруг какой-то ход покажет неожиданно низкую оценку, то его всегда можно пересчитать на полную глубину.
Иначе говоря, с оценкой +7 первый ход по сортировке не вызывает отсечения. Нужно смотреть следующие по номеру ходы (ответы). При идеальной сортировке их оценки после перебора должны быть ещё выше, а значит отсечения снова не состоятся. Сопернику такие ответы тоже не нужны - оценка растет для нас, а значит для него эти варианты только хуже. Выбор хода за ним, и он просто не будет так ходить. И выберет первый ход с оценкой +7, а потому мы также должны ожидать именно такой ответ.
Казалось бы, тогда и не нужно смотреть остальные ходы, если они никому не нужны. Но сортировка у нас простейшая - явно не идеальная. Поэтому смотреть ходы после первого нам все-таки придется. Вдруг на одном из них получим оценку ниже +7 и тогда лучший для соперника вариант изменится? Или даже получим оценку ниже +5 (бета) и отсечение все же произойдет?
Здесь возможен компромисс. Поскольку сортировка у нас более-менее справляется, то ходы с оценкой ниже +7 будут редко появляться в переборе, а значит давайте смотреть ходы после первого с меньшей глубиной. И чем больше номер хода по сортировке, тем с меньшей глубиной его можно рассматривать, поскольку вероятность, что он выйдет на первую линию уменьшается. То есть, если ход, который идет вторым номером разумно "подрезать" совсем чуть-чуть, то глубину каждого следующего хода будем сокращать все больше и больше. В этом суть метода Late Move Reductions (LMR) - сокращения на поздних ходах.
Но если какой-то ход все-таки покажет неожиданно низкую оценку, то его нетрудно пересчитать с полной глубиной. Как показывает практика, сокращать глубину на всех поздних ходах и изредка производить повторные переборы на полную глубину гораздо выгоднее, чем считать все подряд.
Итак, если сортировка хороша, то по мере просмотра ходов их переборная оценка должна подниматься (+9, +12, +11). Но если оценка для какого-то из поздних ходов неожиданно упадет, то скорее всего мы напортачили с сортировкой. Если оценка очередного хода будет ниже оценки лучшего ответа соперника (+7) или даже беты (+5, т.е. хуже основного варианта), то мы производим перерасчет такого хода уже с полной глубиной.
Если перерасчет подтвердит понижение оценки, то значит у нас поменялся лучший ответ соперника. Может даже произойдет отсечение, если оценка будет ниже беты. А если нет, то значит случилась ложная тревога - перебор с сокращенной глубиной давал некорректную оценку. Если нет отсечения по бете, то продолжаем смотреть оставшиеся ходы с сокращенной глубиной, не исключено, что для какого-то из них оценка снова обвалится.
*****
Подведем итоги. Рассматривая в совокупности все три метода отсечений, мы можем увидеть, что отсечения или сокращения происходят чуть ли не в любом случае, практически всегда. Не тем, так другим способом.
Данные методы определяют силу игры современных шахматных программ. Резко сокращая перебор, программы резко наращивают глубину. Видят далеко, учитывают все последствия, тем самым сильно повышая качество игры.
Следует предупредить, что описание методов выше идет в терминах минимакса. А в реальных программах, у любого мало-мальски сильного движка реализована схема негамакса. То есть все рассуждения реализованы с инверсией. Логика не меняется, но берется с противоположным знаком. Поэтому, например отсечения в программах происходят по превышению беты. В IV части мы обсудим это подробнее. В целом, суть перебора остается прежней, а написанное выше все же полагаю проще для понимания.
В следующей части мы перейдем от локального рассмотрения методов на отдельных узлах, к обсуждению их полезности в более широком контексте всего дерева перебора. Если кому-то не очень интересно дальнейшее погружение в тонкости организации перебора, он может прочитать сокращенную версию этой статьи, сразу перейдя к обсуждению оценочной функции в V части, а оттуда к заключению в последней части.
Продолжение следует... |
|
|
| номер сообщения: 54-72-8241 |
|
|
|
|
Ну вообще, конечно, методов отсечений существенно больше
А так ну я не знаю, отсечения непосредственно в цикле поиска дают в сумме примерно в 3 раза, чем тот же NMP. |
|
|
| номер сообщения: 54-72-8242 |
|
|
|
|
Vizvezdenec: Ну вообще, конечно, методов отсечений существенно больше
А так ну я не знаю, отсечения непосредственно в цикле поиска дают в сумме примерно в 3 раза, чем тот же NMP. |
Об остальных отсечениях расскажу, когда дойдем до описания кода Стокфиша. А пока только самое важное. В цикле находятся альфа-бета и LMR. Вдвоем они очень сильны. Плюс остальные методы.
Все указанные выше методы дают наибольшее сокращение бренчинг-фактора, а значит в итоге приводят к наибольшему углублению. В историческом контексте NMP черезвычайно важен. По большей части именно его заслуга, что ветвление в программах на протяжении 90-х - первой половины 00-х сократилось с примерно 5,5 до 3,5. Но об этом в следующей части статьи. |
|
|
| номер сообщения: 54-72-8243 |
|
|
| |
|
|
|
|
|
|
|
| Copyright chesspro.ru 2004-2026 гг. |
|
|
|
