что такое сантипешки в шахматах
Lichess
Почему Lichess называется Lichess?
Lichess — это комбинация live/light/libre и chess. Живые, легковесные и свободные шахматы. Lichess произносится личес. Прослушайте это в исполнении диктора.
Живые, потому что можно играть партии и смотреть игры в реальном времени 24/7. Легковесные и свободные, потому что разрабатываются на принципах свободного программного обеспечения и не завалены проприетарным хламом, как коммерческие проекты.
То же относится к исходному коду Lichess, lila, что означает li[chess in sca]la, основная часть Lichess написана на Scala, интуитивно понятном языке программирования.
Как я могу внести свой вклад в Lichess?
Lichess существует на пожертвования игроков и разрабатывается командой волонтёров.
Вы можете узнать о том, как стать покровителем (и изучить отчёт о тратах). Если вы хотите помочь Lichess, пожертвовав свои знания и время, есть и другие способы помочь.
Есть ли другие сайты, основанные на Lichess?
Да, это так. Многие сайты вдохновились Lichess и используют наш Исходный код, API и Архив партий.
Честная игра
Если оказалось, что я проиграл жулику, мне вернут рейтинг?
Через минуту после того, как жулик был обнаружен, 40 рейтинговых игр, в которых он одержал победу за последние 3 дня, подлежат рассмотрению. Если вы были его соперником в этих играх, и ваш собственный рейтинг считается надёжным, вы можете рассчитывать на возмещение рейтинга. Возмещение может быть ограничено различными условиями, такими как ваш максимальный рейтинг и изменение рейтинга после нечестных игр.
Например, если ваш рейтинг значительно вырос после таких игр, вы можете не получить возмещения, или получить лишь часть. В любом случае, возмещение не может превышать 150 очков рейтинга.
Что происходит с игроками, который выходят из игры, не сдаваясь при этом?
Если ваш соперник часто прерывает или покидает игру, он временно блокируется, при этом признак блокировки видит только он сам. Если после окончания блокировки он продолжает вести себя так же, он опять блокируется, но уже на более длительный срок. В дальнейшем его учётная запись может быть полностью заблокирована.
Могу ли я стать модератором?
Мы не принимаем заявки на просьбу стать модератором. Если мы видим, что кто-то, по нашему мнению, может стать хорошим модератором, мы сами с ним связываемся напрямую.
Игра по переписке отличается от обычной игры?
В Lichess основное отличие в правилах для игры по переписке заключается в том, что доступна книга дебютов. Использование компьютерных программ запрещено и может привести к блокировке за жульничество. Несмотря на то, что международной ассоциацией игры по переписке ICCF помощь компьютерных программ разрешена, на Lichess это не так.
Описание игры
Как определяется тип игры: пуля, блиц и т. д., в зависимости от контроля времени?
Контроль времени влияет на общее ожидаемое время на партию, равное (начальное время) + 40 × (добавка)
Например, время партии с контролем 5+3 равно 5 × 60 + 40 × 3 = 420 секунд.
Отсталая Пешка: 5 идей, которые нужно знать
Дата публикации: 2017-06-16
Одним из важных элементов стратегической борьбы является понимание базовых пешечных структур и идеи, которые можно применить в таких типовых позициях. Ранее мы обсуждали большую часть пешечных образований, которые могут появиться во время игры. Сегодня мы рассмотрим отсталые пешки.
Прежде всего, давайте определимся, что такое отсталая пешка?
Иногда отсталая пешка может появиться сразу в дебюте. Одним из наиболее распространённых примеров будет Сицилианская Защита, где после стратегического e7-e5, Черные получают отсталую пешку на d6.
Черные охотно создают слабость в своем лагере, чтобы захватить центральные поля. Они будут пытаться минимизировать присутствие слабой пешки, с помощью размещения на центральных полях фигур и сдерживания активности Белых. Конечно, план Белых заключается в том, чтобы попытаться избежать этого и атаковать пешку d6.
Примечание: Чтобы развить позиционное понимание позиции, необходимо самому разыгрывать ходы в партиях GM, и понимать, зачем они сделаны. Только побывав в «шкуре» сильного игрока, Вы сможете понять с какими проблемами он сталкивался в партии и это усилит Ваш шахматный уровень. Данные методы применяются в нашем обучающем курсе.
Вот несколько идей, которые следует помнить в таких позициях:
Зная основные идеи при таких пешечных структурах, давайте посмотрим несколько партий гроссмейстеров. Первый пример показывает, как нужно создавать слабости в лагере противника. Пожертвовав пешку, Белые получили несколько преимуществ, которые оказались решающими: слабая отсталая пешка d6, сильное центральное поле d5 для коня и контроль по черным полям.
Вторая игра показывает, что нужно делать, после получения стратегического преимущества. Когда соперник находиться в пассивной защите, нужно искать подходящий момент, чтобы создать новые слабости. В нашем случае, вместо того, чтобы сосредоточиться на выигрыше отсталой пешки, Белые решают начать мощную атаку на королевском фланге.
Последняя игра нашей статьи была сыграна в 2008 год, между гроссмейстерами Виши Анандом и Петром Леко. Этот пример показывает, как нужно играть, когда у вас есть отсталая пешка. Данная структура получилась из Сицилианской Защиты, варианта Свешникова, где Черные рано проводят е5, образуя отсталую пешку на d6.
Если брать во внимание базовые стратегические принципы, то можно сказать, что у черных хуже, т.к. у них есть слабость. Однако, Черные активно играют на обоих флангах, что компенсирует этот недостаток.
Мы можем сделать вывод, что отсталая пешка обычно является слабостью, но в конечном итоге, все зависит от характера позиции. При анализе позиции, следует иметь в виду не только пешечную структуру, но и активность фигур, которая может сказать решающее слово.
Как я программировал шахматную партию против брата
Это история о том, как я попытался выиграть у брата партию в шахматы. Всего лишь гребаную одну игру. Что в этом особенного? Хорош ли я в шахматах? Вовсе нет. Научился ли я чему-то в процессе игры? Тоже нет. Может, это история о путешествии ради путешествия, а не цели? Не совсем. Получил ли я хотя бы удовольствие от этого? Не уверен.
Это история о моей попытке соригинальничать в одной из самых изученных в мире игр, используя опыт разработки ПО там, где это, быть может, и не нужно.
Несмотря на свою абсолютную бестолковость в шахматах и полную бесполезность этой статьи для тех, кто стремится улучшить свою игру, я все равно считаю, что стоило поделиться оригинальным способом применения к задаче инженерных принципов. Добился ли я успеха? Об этом вы узнаете в конце.
Почему я вообще связался с шахматами
Во время пандемии 2020 года мой брат, как и многие другие люди, увлекся онлайн-шахматами. Поиграв пару месяцев, он начал очень вдохновленно рассуждать об этой игре и бросать вызов другим членам семьи. На вызов ответил наш отец (хоть и потерпел цифровое фиаско), я же не поддавался. Одним из сдерживающих факторов было мое нежелание погружаться в потенциально очень времязатратное хобби. Об этой игре я знал достаточно для понимания того, что становление даже игроком среднего уровня требует провести за ней сотни если не тысячи часов. Хотя признаю, что при этом меня также не вдохновляла идея проигрывать брату, который на тот момент сыграл уже не одну сотню партий. Я же – ни одной.
И все же однажды на его вызов я поддался. Стоит ли говорить, что проигрыш был разгромным. Я знал правила и основы игры, так как немного играл еще в детстве, но с навыками брата это ни в коей мере сопоставить было нельзя. В последствии, просматривая анализ игры на chess.com, я увидел, что мое тактическое отставание ход за ходом только росло, пока не достигло оценки в +9 (что равно потере ладьи, слона и пешки против отсутствия потерь противника). В тот момент, утратив всяческую надежду, я сдался. Подобная ситуация повторялась на протяжении еще пары партий, когда я понял – с этим нужно что-то делать.
Первым моим решением было углубиться в изучение игры.
Попытка первая: изучение
Моя первая попытка улучшить качество игры состояла в очевидном: обратиться к Reddit и YouTube за рекомендациями других обучающихся. В перерывах между уроками от GM Naroditsky, чтением и решением задачек на Lichess я также сыграл несколько игр со случайными соперниками по интернету. Несмотря на все это мой рейтинг оставался низким (1300 – 1400 Rapid на Lichess).
После еще пары партий против брата на меня снизошло, что шансов победить у меня нет. Я продолжал следовать все тем же приемам развития (играл, изучал техники и смотрел видео), но уделял этому намного меньше времени, чем брат. На тот момент он уже играл сотни партий в месяц, я же не более 10. Такими темпами мое отставание росло все больше и больше.
Тогда-то я и осознал очень важный нюанс: меня не особо интересовала сама игра, и, по сути, совершенствоваться в ней я не хотел. Основной целью для меня было всего лишь победить одного человека – моего брата.
Попытка вторая: изучение противника
Шахматная партия в общем делится на три фазы: дебют, миттельшпиль и эндшпиль. После изучения некоторых базовых матовых шаблонов перейти на стадии эндшпиля от весомого преимущества к победе обычно «легко», так что первым вопросом для меня стало получение этого преимущества.
На стадии миттельшпиля преимущество обычно достигается за счет развертывания долгосрочной стратегии и применения тактики. Стратегию можно совершенствовать чтением и изучением принципов игры (мне это нравится), а тактика вырабатывается только через решение задач (что мне особенно не нравится). Поэтому я понимал, что в тактических навыках буду однозначно отставать, учитывая, что мой брат решал на chess.com около 20 таких задач ежедневно. Для меня это был недостижимый предел. Таким образом, оставалась всего одна возможность: получать преимущество на стадии дебюта.
Теория по фазе дебюта просто огромна. При этом она требует запоминания длинных последовательностей и вариаций ходов, а также возможные ответов оппонента. Новичкам не обязательно запоминать много, но некоторая ознакомленность с наиболее типичными дебютами может принести немалую пользу (по крайней мере мне так сказали).
Тогда я решил просмотреть несколько случайных игр брата и попробовать понять используемые им дебюты. Я также изучил на Lichess дебюты «Итальянская партия» и Сицилианская защита, постаравшись запомнить их основные принципы. Помимо этого, я просмотрел кучу видео на YouTube.
Очевидно, что мой брат уже проделывал все это до меня (причем лучше), так что, естественно, я снова проиграл. Не говоря уже о том, что запоминание бессмысленных (по крайней мере для меня) открывающих ходов вызывает лишь скуку и утомляет. Все это никак не доставляло мне удовольствия. Еще одна проблема состояла в том, что, когда мой противник начинал отклоняться от прописанных в книге ходов, я абсолютно не знал, как реагировать, потому что просто не понимал формирующиеся позиции.
Пришло время снова отступить и задуматься. Тогда я осознал, что на деле старался не победить брата, а улучшить свою игру против оппонентов, которые отыгрывали те же его дебюты в совершенстве. Мог ли я действовать более направленно? Мог ли вместо этого подготовиться именно против слабых мест брата? Очевидно, что такой подход сработал бы только против него, но это вполне соответствовало моей цели.
Попытка третья: программирование
Теперь моя задача обрела иную форму: найти позиции на выходе из дебюта, которые мой брат (далее PlayerX) с наибольшей вероятностью достигнет, оказавшись при этом в невыгодном положении. Учтите, что никто из нас не является экспертом в игре, и что игроки нашего уровня играют не очень аккуратно.
Единственный способ противостоять хорошему игроку – это в точности следовать ходам из книги, потому что тогда вы по крайней мере знаете, что противник не сделает какой-либо ход, получив преимущество. Однако ситуация меняется, когда вы играете против игрока клубного уровня. Вы можете идти на риски (т.е. временно оказываться в невыгодном положении), если знаете, что противник вряд ли сможет на это правильно среагировать, в связи с чем окажется в затруднительном положении.
У меня также был список из более, чем 500 игр, которые брат сыграл на chess.com. А так как я программист, то естественным подходом для меня стало решить эту задачу инженерным путем.
Я начал скачивать сыгранные им партии с помощью API chess.com и разделять их на игры белыми и черными. Далее я сосредоточился на партиях, где брат играл за черных, потому что чувствовал, что имею больше шансов направить игру в нужное мне русло при игре за белых.
Далее я сформулировал задачу так: «Учитывая все позиции, которые видел PlayerX, какие из них по завершению дебюта скорее всего окажутся для него наименее выгодными?».
На этот раз задача была четко определена, и работа пошла уже в знакомой мне области. Я решил провести анализ в Python, а именно в блокноте Jupyter, потому что цели создавать переиспользуемый инструмент у меня не было, и нужно было лишь изучить доступные данные для нахождения одного решения.
Оказалось, что в Python уже есть отличные библиотеки для работы с шахматами: python-chess (генерация ходов, оценка и визуализация) и python stockfish (привязки для оценки шахматной позиции с помощью известного шахматного движка Stockfish).
Я преобразовал задачу в граф таким образом: узел – это частная шахматная позиция (описанная в нотации FEN). Ребро связывает два узла при том, что целевая позиция оказывается достижима из исходной путем допустимого хода. Для всех игр есть один одинаковый стартовый узел: начальная позиция.
Затем я построил граф всех партий, сыгранных PlayerX за черных, дополнительно обозначив каждое ребро количеством раз, которое был совершен соответствующий ход.
В итоге получился взвешенный направленный граф (не дерево, потому что позицию можно получить различной последовательностью ходов) типа такого (синтетического, потому что реальный бы просто сюда не уместился):
Здесь начальная позиция обозначена квадратным узлом, цвет указывает, чей в этой позиции ход: белых или черных.
Я также хотел получить оценку каждой позиции в плане преимущества белых, для чего использовал Stockfish. Учитывая, что процесс оценки тысяч позиций требует времени, я решил выполнить его отдельно и создал объект JSON, сопоставляющий каждую уникальную позицию FEN с ее оценкой Stockfish.
Оценка преимущества возвращалась в сантипешках или как «мат в X ходов», где положительное число означает преимущество белых, а отрицательное преимущество черных:
100 сантипешек означают преимущество перед оппонентом в одну пешку, а 300 в одну легкую фигуру вроде слона. Однако стоит обратить внимание, что Stockfish присваивает фигурам значение в зависимости от их позиции, значит вполне возможно иметь преимущество в 1000 сантипешек даже при равнозначном количестве фигур на доске.
Мне нужно было отобразить эту оценку во что-то более удобное для обработки, например в числа между 0 и 1. Для этого я навскидку решил, что преимущество в 300+ будет отображаться в 1.0, а отставание в 300+ в 0. Помимо этого, любой мат в X ходов (даже если X равен 20) будет 1 или 0.
Теперь вся информация была не месте, и мне оставалось найти узлы графа (т.е. позиции), в которых черные находились в проигрышном положении, а также наиболее подходящие для их достижения последовательности ходов. Нужно было взвесить ребра таким образом, чтобы стало возможным легко вычислять вероятность достижения конкретной позиции. Я рассуждал так:
В Python это будет выглядеть так:
Логарифмирование вероятности выбора ребра даст отрицательное число, потому что вероятность находится между 0 и 1. При этом не стоит беспокоиться о случае, когда вероятность равна нулю (в результате чего логарифмирование бы дало минус бесконечность), поскольку каждое ребро графа было пройдено не менее одного раза. Чем меньше вероятность, тем более отрицательным получится логарифм, значит инвертирование его знака даст то, что нам нужно, так как:
Вооружившись этой идеей, можно вычислить кратчайший путь между стартовым узлом и всеми другими узлами, используя алгоритм Дейкстры. В результате получится сопоставление между каждым узлом и кратчайшим путем до стартовой позиции, представляющее наиболее вероятную ведущую к ней последовательность ходов.
В этот момент я произвольно выбрал минимальное значение преимущества и упорядочил пути по вероятности. Первые несколько путей представляли для меня наибольший шанс выйти из дебюта с преимуществом перед PlayerX.
Доработки
Что я выяснил? Среди выданных этим алгоритмом позиций была следующая (ход белых):
Как видите, черные находятся в очень неловком положении (+8.9 согласно Stockfish), потому что g6, последний ход черных, был ошибкой. Белые продолжат, забирая пешку с e5 и ладью. На этом партия для черных практически закончена, так как спасать им придется коня, пешку на h7 и слона. Еще один результат алгоритма был таким (ход белых):
Здесь мы видим мат в один ход (детский мат).
Проблема в том, что эти ошибки PlayerX совершал только несколько раз в своих первых партиях и больше не повторял. Ранние атаки ферзем обычно делают только неопытные игроки, и эффективны они только против игроков того же уровня. Выйдя из разряда начинающих, PlayerX уже долгое время не совершал этих ошибок, потому что более грамотные противники так не ходят. Я знал, что такой дебют использовать не получится, поскольку PlayerX умел против него защищаться.
Еще одна проблема была связана с последовательностями ходов, которые происходили только раз, но из типичных позиций. Вероятность их заключительной позиции оказывалась такой же, что и вероятность последней типичной позиции, потому что каждое ребро имело вероятность 1.0 (учитывая, что другие возможности не разыгрывались). В примере ниже можно проследовать по ребрам 7 и 6 (наиболее распространенная позиция на втором ходу), а затем по одному из ребер с 1-ми. Далее все последующие ходы будут сыграны только раз (потому что данная позиция сложилась только в одном матче), в результате чего каждый ход будет иметь вероятность 1.0.
А вот и вероятности:
Такой схеме верить нельзя, потому что вряд ли однозначно будет сыграна одна и та же последовательность ходов. Для такого вывода у нас недостаточно игр, в которых игра бы происходила из этих позиций.
Известная цитата (Б. Брюстера?): «В теории нет разницы между теорией и практикой, а вот на практике есть» оказалась в этом случае верна, поэтому мне потребовались кое-какие доработки и самостоятельное исследование, чтобы найти более удачные предполагаемые позиции.
Вторую проблему я исправил, установив для вероятности ребра верхнюю границу, чтобы длинные последовательности ходов, сыгранные только раз, постепенно утрачивали свою вероятность.
Для первой же проблемы я просто вручную отфильтровал плохие предположения. В итоге у меня для проработки осталась всего пара позиций.
Причиной еще одной модификации стало то, что я не хотел, чтобы вероятности ходов белых влияли на вероятность выбора пути, потому что играл за белых и мог сам решать, каким путем идти. По этой причине я установил все вероятности ходов белых на 1.0 (нулевой вес), получив в результате такой граф:
Подготовка
В процессе изучения я остановил свой выбор на следующей позиции:
Согласно Lichess, это защита Алехина (атака двух пешек). В этой позиции для черных есть всего один удачный ход (Nb6), после которого они все равно остаются в менее выгодном положении (+0.6 согласно Stockfish). Однако из этой позиции PlayerX зачастую играет на Nf4, что весьма для него неудачно (+2.3). Я создал на Lichess студию и начал просматривать несколько вариаций (хороших ходов и ходов, сыгранных PlayerX).
В конечном итоге получилось дерево возможностей, которое я постарался запомнить и понять. К примеру, мне нужно было узнать, чему угрожал ход вроде d5, почему ход Nf4 был неудачным, и подготовить на все оптимальные ответы.
Занимался я этим недолго, потому что мне быстро надоело, и подготовился по факту лишь частично.
Решающая партия
Все случилось так, словно я глядел в будущее: мы с PlayerX попали в позицию защиты Алехина. Оказавшись в неудобной ситуации, он прозевал своего коня на пятом ходу. Оказывается, что даже игроки намного опытнее тебя начинают одну за другой совершать ошибки, когда попадают в проигрышные условия. Легко играть четко, когда ты побеждаешь, но удастся ли тебе сохранить хладнокровие в противоположной ситуации? На 10 ходу я уже вел с преимуществом +7.1, при котором сложно проиграть, но на этом также завершалась проработанная мной схема. Взгляните, насколько стеснены сейчас черные, и как мои фигуры нацелены напасть на короля:
С этого момента я начал тут и там совершать ошибки, но при этом мне удалось сохранять некоторое преимущество вплоть до 27 хода:
К сожалению, я был очень ограничен во времени (мы играли ускоренную 10-минутную партию), поэтому ходить приходилось быстро. В конечном итоге я совершил фатальные ошибки на 32 и 33 ходах, а еще через один получил от своего недобитого противника мат :/
Вот весь матч (с грубыми ошибками и прочим):
Выводы
Чему я из всего этого научился? Нескольким вещам, большая часть из которых в ретроспективе выглядит очевидной:
На этом все, друзья. Надеюсь, что однажды мне удастся одолеть брата, а пока что буду стараться достичь этого…своими средствами.
Как компьютер играет в шахматы?
Хикару Накамура, недавно бросивший вызов компьютеру
Компьютер уже давно обыграл человека в шахматы, сейчас сильнейшие шахматисты не способны выиграть даже у старенького ноутбука. Теперь шахматные движки используются для анализа партий, поиска новых вариантов и игры по переписке.
Если вам интересно, как же устроены шахматные движки — добро пожаловать под кат.
Введение
Когда-то я был уверен, что шахматные программы (они же движки, впрочем об этом чуть позже), просто держат в памяти огромное количество сыгранных партий и находят в них нынешнюю позицию и делают верный ход. По-моему, я прочитал об этом в какой-то книжке.
Это, несомненно, очень наивное мнение. Новую позицию в шахматах можно получить к десятому ходу. Хоть в шахматах и меньше позиций, чем в го, тем не менее, уже после 3 ходов (ход — это один ход белых и чёрных, полуход — ход только одной стороны) дерево ходов состоит из почти 120 миллионов узлов. Более того, размер дерева после 14 полуходов из начальной позиции энтузиасты считают уже больше года, продвинувшись пока что примерно на треть.
Ещё я думал, что шахматные программы, несмотря на давнюю победу в матче над чемпионом мира, все еще находятся в пределах досягаемости лучших людей. Это тоже не верно.
Кроме того, партии игрались с контролем 45″+15′, то есть 45 минут на партию и 15 секунд добавления каждый ход. Обычно, более короткие контроли дают дополнительное преимущество компьютеру, в то время как более длинные — несколько повышают шансы человека. Компьютер даже за доли секунды успеет отмести откровенно проигрывающие ходы, в то время как из-за экспоненциального роста дерева вариантов каждое последующее улучшение анализа занимает всё больше времени.
Тем не менее, фора была и человек проиграл в матче 2.5-1.5, сведя в ничью первые 3 партии и проиграв четвёртую. Вместе с тем, слабый гроссмейстер достаточно уверенно выиграл с форой в 2 пешки. Следовательно, преимущество лучших программ над лучшими людьми на данный момент где-то между 1 и 2 пешками форы. Конечно, эта оценка очень грубая, но для точной оценки надо сыграть несколько тысяч партий между людьми и программами, а этим вряд ли кто-то будет заниматься. Обратите внимание, что рейтинг ЭЛО, нередко указываемый для программ, не имеет ничего общего с рейтингом людей.
Что такое шахматный движок?
Чтобы человек мог играть в шахматы с компьютером, кроме собственно поиска лучшего хода, нужен GUI. К счастью, был придуман универсальный интерфейс (даже два, Winboard и UCI, но большинство движков использует UCI) для связи между GUI и собственно шахматной программой (движком). Таким образом, программисты могут сосредоточиться на самом алгоритме игры в шахматы, не задумываясь об интерфейсе. Обратная сторона монеты — так как создание GUI гораздо более скучное занятие, чем написание движка, то бесплатные GUI заметно проигрывают платным. В отличии от движков, где свободный Stockfish уверенно борется за первую строчку рейтинга с платным Komodo.
Как же они все таки играют?
Итак, как же устроен современный шахматный движок?
Представление доски
Основа любого движка — представление шахматной доски. В первую очередь, надо «объяснить» компьютеру все правила шахмат и дать ему возможность хранить шахматную позицию. Без этого невозможно оценивать позицию и делать ходы.
Есть два основных способа хранить представление доски — по фигурам или по клеткам. В первом случае мы храним для каждой фигуры её место на доске, во втором — наоборот, для каждой клетки храним что находится там. У каждого метода есть свои преимущества и недостатки, но на данный момент все топовые движки используют одно и то же представление доски — bitboards.
Bitboards
По счастливому совпадению, на шахматной доске 64 клетки. А значит, если для каждой клетки использовать один бит, мы можем хранить всю доску в 64-битном целом числе.
В одной переменной будем хранить все белые фигуры, в другой — все черные, и ещё в 6 — каждый тип фигур по отдельности (другой вариант — 12 битбордов для каждого цвета и типа фигур по отдельности).
В чем преимущество такого варианта?
Во-первых, память. Как мы узнаем позже, при анализе представление доски копируется много раз, и, соответственно, отъедает оперативку. Битборды — это одно из самых компактных представлений шахматной доски.
Во-вторых, скорость. Многие вычисления, например, расчёт возможных ходов, сводятся к нескольким битовым операциям. За счёт этого, например, использование инструкции POPCNT дает
15% ускорение современным движкам. Кроме того, за время существования битбордов было придумано немало алгоритмов и оптимизаций, как, например, «магические» битборды.
Поиск
Минимакс
В основе большинства шахматных движков лежит алгоритм поиска минимакс или его модификация негамакс. Вкратце, мы спускаемся вниз по дереву, оцениваем листья, а потом поднимаемся вверх, каждый раз выбирая оптимальный для текущего игрока ход, минимизируя оценку для одного (чёрных) и максимизуруя для второго (белых). Отсюда и название. Оказавшись в корне, мы получаем последовательность ходов, оптимальную для обоих игроков. Разница между минимаксом и негамаксом в том, что в первом случае мы по очереди выбираем ходы с максимальной и минимальной оценкой, а во втором вместо этого меняем знак для всех оценок и всегда выбираем максимальную (название сами поняли откуда). Подробнее здесь и здесь.
Альфа-бета
Первая оптимизация — альфа-бета. Идея альфа-беты проста — если у меня уже есть хороший ход, то можно отсечь ходы, которые заведомо хуже. Рассмотрим пример на жуткой картинке слева. Допустим, у игрока А есть 2 возможных хода — a3 и b3. Проанализировав ход a3, программа получила оценку +1.75. Начав оценивать ход b3, программа увидела, что у игрока B есть два хода — a6 и a5. Оценка хода a6 +0.5. Так как игрок B выбирает ход с минимальной оценкой, то он никак не выберет ход с оценкой выше 0.5, а значит оценка хода b3 меньше 0.5, и рассматривать его смысла нет. Таким образом, все оставшееся поддерево хода b3 отсекается.
Для отсечений мы храним верхнюю и нижнюю границы — альфу и бету. Если при анализе ход получает оценку выше беты — то текущий узел отсекается. Если оценка выше альфы — то альфа обновляется.
Сортировка ходов
При использовании альфа-беты, важным становится порядок ходов. Если мы сможем поставить лучший ход первым, то оставшиеся ходы будут проанализированы гораздо быстрее за счёт отсечений по бете.
Кроме использования хеша и лучшего хода из предыдущей итерации, существуют несколько техник сортировки ходов.
Для взятий может использоваться, например, простая эвристика MVV-LVA (Most Valuable Victim — Least Valuable Aggressor). Мы сортируем все взятия по убыванию ценности «жертвы», а внутри соритруем еще раз по возрастанию ценности «агрессора». Очевидно, что обычно забрать пешкой ферзя выгоднее, чем наоборот.
Для «тихих» ходов используется метод «убийственных» (killer) ходов — ходов которые вызвали отсечение по бете. Это ходы обычно проверяются сразу после ходов из хеша и взятий.
Хеш таблицы или таблицы перестановок
Несмотря на огромные размеры дерева, многие узлы в нём идентичные. Чтобы не анализировать одну и ту же позицию дважды, компьютер хранит результаты анализа в таблице и каждый раз проверяет, нет ли уже готового анализа этой позиции. Обычно в такой таблице хранится собственно хеш позиции, оценка, лучший ход и возраст оценки. Возраст необходим для замены старых позиций при заполнении таблицы.
Итерационный поиск
Как известно, если мы не можем проанализировать все дерево полностью, минимаксу необходима оценочная функция. Тогда достигнув определенной глубины, мы останавливаем поиск, оцениваем позицию и начинаем подъем по дереву. Но такой метод требует заранее заданной глубины и не предоставляет качественные промежуточные результаты.
Эти проблемы решает итерационный поиск. Для начала мы проводим анализ на глубину 1, потом на глубину 2 и т.д. Таким образом, каждый раз мы спускаемся чуть глубже, чем в прошлый раз, пока анализ не будет остановлен. Чтобы уменьшить размеры дерева поиска, результаты прошлой итерации обычно используются, чтобы отсекать заведомо плохие ходы на текущей. Этот метод называется «окно стремлений» (aspiration window) и используется повсеместно.
Поиск спокойствия(Quiescence Search)
Этот метод предназначен для борьбы с «эффектом горизонта». Простая остановка поиска на нужной глубине может быть очень опасной. Представим, что мы остановились посреди размена ферзей — белый забрал чёрного ферзя, а следующим ходом чёрный должен забрать белого. Но в данный момент на доске — лишний ферзь у белых и статическая оценка будет в корне неверной.
Для этого, прежде чем заняться статической оценкой, мы проверяем все взятия (иногда еще и шахи) и спускаемся по дереву до позиции, в которой нет возможных взятий и шахов. Естественно, если все взятия ухудшают оценку, то мы возвращаем оценку текущей позиции.
Выборочный поиск
Идея выборочного поиска в том, чтобы дольше рассматривать «интересные» ходы и меньше — неинтересные. Для этого используются продления, которые увеличивают глубину поиска в определённых позициях, и сокращения, уменьшающие глубину поиска.
Глубину увеличивают в случае взятий, шахов, если ход единственный или гораздо лучше альтернатив или при наличии проходной пешки.
Отсечения и сокращения
С отсечениями и сокращениями всё гораздо интереснее. Именно они позволяют значительно сократить размер дерева.
Сокращение используются, когда мы не настолько уверены, что ход плох, и поэтому не отсекаем его, а просто уменьшаем глубину. Например, razoring — это сокращение при условии, что статическая оценка текущей позиции меньше, чем альфа.
За счёт качественной сортировки ходов и отсечений, современные движки умудряются достигать коэффициента ветвления ниже 2. За счёт этого, к сожалению, они иногда не замечают нестандартные жертвы и комбинации.
NegaScout и PVS
Две очень похожие техники, которые используют тот факт, что после того как мы нашли PV-node (приусловии что наши ходы достаточно хорошо отсортированы), она скорее всего не изменится, то есть все оставшиеся узлы вернут оценку ниже, чем альфа. Поэтому вместо поиска с окном от альфа до бета, мы ищем с окном от альфа до альфа+1, что позволяет ускорить поиск. Конечно, если в каком-то узле мы получаем отсечение по бете, то его надо ценить заново, уже нормальным поиском.
Разница между двумя методами лишь в формулировке — они были разработаны примерно в одно время, но независимо, и поэтому известны под разными названиями.
Параллельный поиск
Распараллеливание альфа-беты — отдельная большая тема. Я вкратце пройдусь по ней, а кому интересно — почитайте Parallel Alpha-Beta Search on Shared Memory Multiprocessors. Сложность в том, что при параллельном поиске многие Cut-nodes анализируются до того, как другой поток найдет опровержение (установит бету), в то время как в последовательном поиске, при хорошей сортировке многие из этих узлов отсеклись бы.
Lazy SMP
Очень простой алгоритм. Мы просто запускаем все потоки одновременно с одним и тем же поиском. Коммуникация потоков происходит за счёт хеш-таблицы. Lazy SMP оказался неожиданно эффективным, настолько, что топовый Stockfish перешел на него с YBW. Правда, некоторые считают, что улучшение произошло из-за плохой реализации YBWC и слишком агрессивных отсечений, а не из-за преимущества Lazy SMP.
Young Brothers Wait Concept (YBWC)
Первый узел (старший брат) должен быть полностью проанализирован, после чего запускается параллельный анализ остальных узлов (младших братьев). Идея всё та же, первый ход либо заметно улучшит альфу, либо вообще позволит отсечь все остальные узлы.
Dynamic Tree Splitting (DTS)
Быстрый и сложный алгоритм. Немного о скорости: скорость поиска измеряется через ttd (time to depth), то есть время, за которое поиск достигает определенной глубины. Этот показатель обычно можно использовать для сравнения работы разных версий движка или движка, запущенного на разном количестве ядер (хотя Komodo, например, увеличивает ширину дерева при большем количестве доступных ядер). Кроме того, во время работы движок отображает скорость поиска в nps (nodes per second). Это метрика гораздо более популярная, но она не позволяет сравнивать даже движок сам с собой. Lazy SMP, в котором нет никакой синхронизации, практически линейно увеличивает nps, но из-за большого объема лишней работы, его ttd не так впечатляющ. В то время как для DTS nps и ttd изменяются практически одинаково.
Если честно, я так и не смог до конца разобраться в этом алгоритме, который, несмотря на высокую эффективность, используется буквально в паре движков. Кому очень интересно, проследуйте по ссылке выше.
Оценка
Итак, мы достигли необходимой глубины, произвели поиск спокойствия и, наконец нам надо оценить статическую позицию.
Какие параметры компьютер учитывает при оценке позиции?
Материал и мобильность
Самое простое. Ферзь 9-12 пешек, ладья 5-6, конь и слон 2.5-4 и пешка, соответственно, одна пешка. В общем, материал — это достойная эвристика оценки позиции и любое позиционное преимущество обычно трансформируется в конце концов в материальное.
Мобильность считается просто — количество возможных ходов в текущей позиции. Чем их больше, тем более мобильна армия игрока.
Таблицы позиций фигур
Конь в углу доски обычно плох, пешки ближе к вражескому тылу становятся всё ценнее и так далее. Для каждой фигуры составляется таблица бонусов и штрафов в зависимости от ее положения на доске.
Пешечная структура
Этапы игры
Все вышеперечисленные параметры влияют по-разному на оценку игры, в зависимости от этапа игры. В дебюте нет толку от проходной пешки, а в эндшпиле нужно выводить короля в центр доски, а не прятать за пешками.
Поэтому многие движки имеют отдельную оценку для эндшпиля и для дебюта. Они оценивают этап игры в зависимости от оставшегося на доске материала и в соответствии с этим считают оценку — чем ближе к концу игры, тем меньше влияет дебютная оценка и тем больше — эндшпильная.
Прочее
Кроме этих основных факторов движки могут добавлять еще какие-то факторы к оценке — например безопасность короля, запертые фигуры, пешечные острова, контроль центра и т.д.
Точная оценка или быстрый поиск?
Традиционный спор: что эффективнее, точно оценить позицию или достичь большей глубины поиска. Опыт показывает, что слишком «тяжелые» оценочные функции неэффективны. С другой стороны, более подробная оценка, учитывающая больше факторов, обычно приводит к более «красивой» и «агрессивной» игре.
Дебютные книги и эндшпильные таблицы
Дебютные книги
На заре компьютерных шахмат программы очень слабо играли дебют. Дебют часто требует стратегических решений, которые повлияют на всю игру. С другой стороны, у людей дебютная теория была развита хорошо, дебюты были многократно проанализированы и игрались по памяти. Вот и для компьютеров была создана подобная «память». Начиная с начальной позиции строилось дерево ходов и каждый ход оценивался. Во время игры движок просто выбирал один из «хороших» ходов с определенной вероятностью.
С тех пор дебютные книги разрослись, многие дебюты проанализированы при помощи компьютеров вплоть до эндшпиля. Необходимости в них нет, сильные движки научились играть дебют, но сходят с главных линий достаточно быстро.
Эндшпильные таблицы
Вернемся к введению. Помните идею хранить много позиций в памяти и выбирать нужную. Вот она. Для малого (до 7) количества фигур просчитаны все существующие позиции. То есть в этих позициях компьютер начинает играть идеально, выигрывая в минимальное количество ходов. Минус — размер и время генерации. Создание этих таблиц помогло в исследовании эндшпилей.
Генерация таблиц
Сгенерируем все возможные (с учетом симметрии) позиции с определенным набором фигур. Среди них найдем и обозначим все позиции, где стоит мат. Следующим проходом обозначим все позиции, в которых можно попасть в позиции с матом — в этих позициях ставится мат в 1 ход. Таким образом находим все позиции с матом 2,3,4,549 ходов. Во всех неотмеченных позициях — ничья.
Таблицы Налимова
Первые эндшпильные таблицы, опубликованные в далёком 1998 году. Для каждой позиции хранится результат игры и количество ходов до мата при идеальной игре. Размер всех шестифигурных окончаний — 1.2 терабайта.
Таблицы Ломоносова
В 2012 году на суперкомпьютере Ломоносов в МГУ были посчитаны все семифигурные окончания (кроме 6 против 1). Эти базы доступны только за деньги и это единственные существующие полные семифигурные эндшпильные таблицы.
Syzygy
Стандарт де-факто. Эти базы гораздо компактнее баз Налимова. Они состоят из двух частей — WDL (Win Draw Lose) и DTZ (Distance to zeroing). WDL базы предназначены для использования во время поиска. Как только узел дерева найден в таблице, у нас есть точный результат игры в этой позиции. DTZ предназначены для использования в корне — они хранят количество ходов до обнуляющего счётчик ходов хода (хода пешкой или взятия). таким образом для анализа достаточно WDL баз, а DTZ базы могут пригодиться при анализе эндшпилей. Размер Syzygy гораздо меньше — 68 гигабайт для шестифигурных WDL и 83 для DTZ. Семифигурных баз не существует, так как их генерация требует примерно терабайт оперативной памяти.
Использование
Эндшпильные таблицы используются в основном для анализа, прирост силы игры движков небольшой — 20-30 пунктов ЭЛО. Тем не менее, так как глубина поиска современных движков может быть очень большой, запросы к эндшпильным базам из дерева поиска происходят еще в дебюте.
Прочие интересности
Жираф или нейронные сети играют в шахматы
Некоторые из вас возможно слышали о шахматном движке на нейронных сетях, достигшем уровня IM (что, как мы поняли во введении, не так уж и круто для движка). Его написал и выложил на Bitbucket Matthew Lai, который, к сожалению прекратил работу над ним из-за того, что начал работать в Google DeepMind.
Тюнинг параметров
Добавить новую функцию в движок несложно, но как проверить что она дала усиление? Простейший вариант — сыграть несколько партий между старой и новой версией и посмотреть кто победит. Но если улучшение небольшое, а так оно обычно и бывает после того, как все основные фичи добавлены, игр должно быть несколько тысяч, иначе достоверности не будет.
Stockfish
Над этим движком работ немало людей, и каждую их идею надо проверить. При текущей силе движка каждое улучшение дает прибавку в пару пунктов рейтинга, но в итоге получается стабильный рост на несколько десятков пунктов ежегодно.
Их решение типично для опенсорса — добровольцы предоставляют свои мощности чтобы прогнать на них сотни тысяч игр.
Программа, которая оптимизирует параметры через линейную регрессию, используя результаты игр движка с самим собой с разными параметрами. Из минусов — очень ограниченной размер задачи: оптимизировать сотню параметров (вполне адекватное число для движка) ей не под силу, по крайней мере за адекватное время.
Texel’s tuning
Решает проблему предыдущего метода. Берем большое количество позиций (автор предлагал 9 миллионов позиций из 64000 игр, я брал 8 миллионов из почти 200000), для каждой сохраняем результат партии (победа белых 1, ничья 0.5, поражение 0). Теперь минимизируем ошибку, которая находится сумма квадратов разности результата и сигмоида оценки. Метод эффективный и популярный, но работает не на всех движках.
Stockfish tuning
Еще одна методика от лидера. Берем параметр равный x, и сравниваем (в нескольких десятках тысяч партий) движок с параметром равным x-sigma и x+sigma. Если победил движок с большим параметром, сдвигаем немного вверх, иначе — немного вниз, и повторяем.
Соревнования движков
Из всех проводимых тестирований соревнований хотелось бы отдельно выделить TCEC. От всех остальных он отличается мощным железом, тщательным подбором дебютов и длинным контролем. В последнем финале было сыграно 100 партий на 2 x Intel Xeon E5-2690v3 с 256 гигабайтами RAM с контролем 180’+30″. В таких условиях количество ничей огромно, и результативными было всего 11 партий.