Как выиграть компьютер в шахматы
Как выигрывать в шахматах
Что нужно сделать, чтобы выиграть?
На доске мат, когда король под боем другой фигуры и у него нет возможности закрыться, отступить или взять нападающую фигуру. На этом партия заканчивается. Но мат нужно подготовить.
Чтобы выиграть партию в шахматы, необходимо соблюдать шесть правил:
2. Не отдаем фигуры просто так
3. Занимаем фигурами активные позиции
Прежде чем добраться до короля, нужно занять своими фигурами подходящие позиции для атаки. Это означает, что при атаке нам понадобятся активные фигуры, у которых много возможностей.
4. Атакуем короля всеми фигурами
Редко, когда получается поставить мат одной фигурой. Для этого необходимо взаимодействие нескольких фигур. Чаще всего одна фигура объявляет шах королю, и еще одна фигура, защищает нападающую фигуру, чтобы король не мог её взять. Иногда приходится жертвовать несколько фигур, чтобы сломить оборону соперника.
5. Заботимся о безопасности своего короля
6. Всегда будем вежливы
Оставайтесь добрыми и благодарными даже после неудачной партии, а после игры просто подумайте, как сыграть лучше в следующий раз.
Чтобы узнать, как побеждать в шахматах, регистрируйтесь на Chess.com. Это просто и бесплатно!
Падение последнего интеллектуального бастиона: действительно ли компьютер-шахматист сильнее человека?
На написание этого обзора натолкнул пост «Секрет древней игры го. Почему компьютер до сих пор не обыграл человека?», опубликованный 25 мая. В самом посте, и, тем более, в комментариях, было много сказано по поводу компьютерных шахмат вообще и матча Deep Blue — Каспаров (1997) в частности. Понятно, что сейчас, спустя уже без малого двадцать лет, мало кому интересны все подробности того матча: компьютеры развиваются с колоссальной скоростью, современные смартфоны легко дадут фору компьютерам того времени, да и возможно, сами шахматы несколько утратили популярность последнее время — по каким причинам — это уже тема отдельного разговора.
Впрочем, некоторые подробности, судя по всему, действительно неизвестны, а подробности эти таковы, что заголовки о “падении последнего интеллектуального бастиона” — не более, чем газетный прием, ибо случившийся по итогам матча, по сути, скандал, в силу своей шахматной специфичности вряд ли был бы интересен широкой публике. Нет, я, несмотря на то, что всегда являлся поклонником Гарри Кимовича Каспарова (исключительно в шахматном плане), не собираюсь его оправдывать за то поражение и пытаться доказать, что все было совсем не так, как сейчас общеизвестно. И уж тем более целью не является опровержение некоторых комментариев на шахматную тему к посту хабраюзера alizar. Единственная цель — рассказать некоторые подробности того, что именно произошло в Нью-Йорке в начале мая 1997 года, и почему результат этого противостояния, по мнению автора, на самом деле никому ничего не доказал.
Сразу оговорюсь: автор не является высококвалифицированным шахматистом. Возможно, некоторые, чисто шахматные моменты в данном материале, могут быть раскритикованы людьми, занимающимися шахматами профессионально. Также, увы, автор не силен ни в теории игр, ни в шахматном программировании, и попытается лишь высказать мнение частично шахматиста, частично знакомого с компьютерами, а не создать Всемирную и всемерную энциклопедию Шахматного Программирования.
Недостаточно быть хорошим игроком; вы также должны хорошо играть
(З.Тарраш)
История шахматного программирования началась, по сути, сразу же с обычным программированием. Искусственный интеллект, возможность его создания, волновали людей издавна, и программируемая вычислительная техника оказалась более подходящим средством для поиска такой возможности, чем человек, который обыгрывал Наполеона, сидя в тумбочке. Первые шахматные программы были, впрочем, соперниками лишь друг другу: в силу огромного количества вариантов шахматных партий, речи о полном переборе не было, и нет, кстати, и по сей день. (И не предвидится (с) Швондер.) Это не мешало шахматным программам периодически удивлять профессиональных шахматистов как неожиданно лучшими ходами (что объясняется в первую очередь тем, что форсированные варианты компьютер считает все же быстрее и точнее), так и внезапными просмотрами мата в пару-тройку ходов ради спасения ферзя. Однако, если в тактике даже сравнительно слабые компьютеры были вполне себе сильны, то вот в позиционной игре все было очень печально — если еще как-то можно было научить программу, что ферзь дороже пешки (что в некоторых случаях приводило к вышеупомянутым просмотрам мата), то научить оценке позиции, на которой, собственно, вся партия и держится, возможным не представлялось. Это и неудивительно — правильная оценка позиции — это задача непростая даже для шахматистов-разрядников, единого рецепта нет, даже две практически одинаковые позиции, отличающиеся лишь положением одной пешки, могут иметь противоположные оценки.
С течением времени, впрочем, прогресс стал брать свое. Дебютные библиотеки позволили программам не “плавать” в начальной стадии партии — такие “плавания” нередко приводили к окончанию партии еще в дебюте — все же, несколько столетий опыта и рост дебютной теории с начала ХХ века давали человеку немалую фору. Дебютные библиотеки эту фору не просто устранили — в отличие от человека, компьютер теперь мог разыграть абсолютно любой дебют, уйти от любой дебютной ловушки, да и сам, соответственно, мог в любую ловушку поймать! Шахматистов, знающих все дебюты, не бывает — есть понятие “дебютный репертуар” — это некоторое количество начал, использующихся шахматистом. Человек может этот репертуар расширять, пополнять, готовить, например, новые дебюты к новому турниру, но с появлением у компьютеров в памяти дебютной энциклопедии человек стал проигрывать в этом компоненте. Кстати, фора тут вышла двойная: в отличие от компьютера, который по сути, играет по дебютной библиотеке, человек в ходе партии подсмотреть в дебютную энциклопедию не может. Единственный вариант уравнять тут шансы — неправильные начала, не внесенные в энциклопедии, причем, максимум шансы получится именно уравнять — человек ведь также не имеет возможности применить багаж своих дебютных знаний.
Надо сказать, что проблема дебютных знаний и их чрезмерной распространенности и доступности волновала и самих шахматистов. Так, совершенно нормальными в профессиональных шахматах стали ситуации, когда игроки сделали по 30-40 ходов, и ничего нового в них не было — все эти ходы уже были в другой партии. (Тут, конечно, дело касается не только дебюта, но, как правило, такие ситуации были связаны в первую очередь с дебютными спорами, и некий вариант мог отстаиваться и в глубоком миттельшпиле, и даже в эндшпиле!) Либо ситуации из партий гросс- и супергросс- мейстеров — партия до 20 ходов, обычно — 16-18, все “из книжки” и соглашение на ничью — потому что позиция теоретически ничейна. Спасением виделись Шахматы Фишера, они же Шахматы-960, где фигуры в начальной позиции могут располагаться произвольным образом. Увы (или к счастью?), обычные шахматы этот вариант вытеснить не смог. Почему — сказать сложно, но рискну предположить, что профессиональным шахматистам он не был вполне интересен, им и в стоковых дебютах хватало, чем заняться, а остальным — не давал никаких преимуществ — см. комментарий Каспарова. В самом деле, дебютные принципы не поменялись — “развивай фигуры как можно быстрее и безопаснее и мешай делать то же самое сопернику”, и тот, кто эти принципы понимал в стандартных шахматах — не перестал их понимать и в фишеровских, а кто двигал фигуры исключительно по памяти из справочника и при любом отклонении впадал в панику — стал в эту самую панику впадать гораздо быстрее, на 2-3 ходу.
Гораздо лучше в теории дела обстояли с эндшпилем. Особенно с малофигурными окончаниями — чем меньше фигур — тем лучше. Такие ситуации, в отличие от дебютов, просчитывались куда как проще: фигур-то гораздо меньше! Да и ограничения по количеству ходов способствовали (см. Правило 50 ходов). Так или иначе, компьютеры получили возможность пользоваться Эндшпильными таблицами Налимова и это, пожалуй было еще большей победой, нежели дебютные библиотеки. Впрочем, человек тут имел свои козыри — например то, что множество вариантов шахматных окончаний можно было играть, практически не считая варианты, а пользуясь известными алгоритмами, самый знаменитый пример (первый этюд, вероятность возникновения подобных мотивов в реальной партии достаточно высока).
А вот в миттельшпиле человек оставался хозяином положения. Да, совершенствовались алгоритмы для оценки позиции, да, компьютеры считали все дальше и глубже, но оставалось одно, то, из-за чего компьютеры так пока что и не стали ни писателями, ни композиторами: план. Если в дебюте компьютер мог двигать фигуры исключительно “по книжке”, а в эндшпиле — придерживаться неких алгоритмов, то с планом были трудности. Да, очевидно, если при оценке позиции машина находила у соперника слабые места — то могла делать ходы, направленные на их использование. Если слабые места были у машины — то она могла предпринимать действия для защиты. Однако, живой шахматист не будет руководствоваться только своим планом — он попытается определить планы соперника. Замечательная задача для ИИ. Вот только выполнимая ли?
Тринадцатый чемпион мира Гарри Каспаров всегда считал свое занятие прежде всего творчеством. То есть, тем, что машине недоступно и не будет доступно никогда. Каспаров говорил:
“Если компьютер сможет превзойти в шахматах лучшего из лучших, это будет означать, что ЭВМ в состоянии сочинять самую лучшую музыку, писать самые лучшие книги. Не могу в это поверить. Если будет создан компьютер с рейтингом 2800, то есть равным моему, я сам сочту своим долгом вызвать его на матч, чтобы защитить человеческую расу.”
По иронии судьбы, именно Каспаров стал первым чемпионом мира, проигравшим компьютеру. Первая же партия матча Deep Blue — Каспаров (Филадельфия, февраль 1996 г.) принесла сенсацию — Чемпион Мира повержен машиной. Увы для поклонников ИИ — уже во второй партии чемпион мира реваншировался, а после еще двух партий, завершившихся вничью, выиграл дважды, доказав таким образом, что чемпион мира — это чемпион мира. Все же, было уже понятно, что компьютерные шахматы — это реальная сила, и что во втором матче, который IBM предложила спустя чуть более года, чемпиону-человеку придется постараться, чтобы защитить человеческую расу.
Второй матч Каспарова с “Темно-синим” начался, наверное, даже с огорчительного для любителей интриги результата — Каспаров выиграл белыми легко, избрав неправильное начало (точнее, этот дебют вполне можно классифицировать, как Дебют Рети). Казалось, все ясно, идея Каспарова проста — лишить соперника первого козыря, дебютной библиотеки, и играть просто в шахматы, что машине не дано. Конечно, отойти от теории при игре черными гораздо сложнее, тон ведь задают белые, и тут Каспаров, вероятно, надеялся на Испанскую партию, ту самую, которую в количестве восемнадцати штук играл сам Остап Бендер — старинный дебют, где отыграть по книжке сам дебют мало, надо уметь играть миттельшпиль. И тут-то и началось.
Тот не шахматист, кто, проиграв партию, не заявляет, что у него было выигрышное положение
(И.Ильф)
Итак, сначала — только игровые факты. Партии игрались с контролем 2 часа на 40 ходов (классический контроль времени). Играя черными, Каспаров попытался оживить позицию с помощью жертв, машина эти жертвы отклонила, и в итоге, чемпион мира, оказавшийся в сложнейшей позиции, сдался. Все просто и ясно. Далее часть описания и цитат заимствована отсюда (там же можно посмотреть всю партию №2), часть — описана автором.
По мнению чемпиона, первый звоночек прозвенел на 35 ходу — суперкомпьютер, до этого тративший не более трех минут на ход, задумался на четверть часа. Еще шесть минут — над следующим ходом. Результат был еще более неожиданным — компьютер отклоняет жертву пешек черными.
По условиям, после каждой партии IBM предоставляла распечатки анализов, которые компьютер производил во время каждой партии. По словам Каспарова, вариант, избранный машиной, ей же был оценен, как неясный, в отличие от принятия жертвы, которое машина оценивала как выгодное для себя. “Очень мило. Мы имеем дело с уникальным событием, Машина отказывается от выигрыша трех пешек, потому что ей якобы “неясно” — Г.Каспаров.
Партия продолжалась, и двигалась к логическому финалу, который в конце концов и наступил — Каспаров сдался. Однако чудеса на этом не закончились. Как выяснилось практически сразу — чемпион мира сдался в ничейной позиции. Казалось бы, обвинять тут некого, кроме самого потерпевшего. Но все не так просто. Каспаров сдался, просто поверив, что машина непогрешима. И ошибся. Своим последним ходом в партии машина допустила грубейшую тактическую ошибку, после чего черные могли закончить партию вничью. Удивление Каспарова после партии вполне понятно: машина, нашедшая сильнейший позиционный ход, который оказался не под силу даже многим белковым шахматистам, то есть, обошедшая людей на их же территории — в позиционной игре, тут же проиграла на своей территории, где она не может ошибаться — допустив элементарный тактический зевок?
Эти вопросы до сих пор остаются вопросами, а матч, тем не менее, продолжался. Три партии завершились вничью. Была ли шестая партия для Каспарова своеобразным финалом? Финалом в матче за честь и ум человеческой расы.
В шахматах выигрывает тот, кто ошибается предпоследним
(С.Тартаковер)
Пожалуй, с точки зрения компьютерных шахмат, в шестой партии не произошло ничего интересного. Вопросы в этой партии в основном к чемпиону мира — каким образом он мог сделать ход 7.… h6? Компьютер тут же пожертвовал коня и позиция черных покатилась под откос. После 19-го хода белых Каспаров сдался. Единственное его достижение в данной партии — это то, что официально она не стала самым быстрым поражением в его карьере — шахматные статистики не учитывают партии человека с компьютером. Хотя формально, как вы поняли, это именно такая партия.
Дальше было менее интересно — якобы, IBM отказалась предоставлять логи анализов этой партии, что, судя по всему, неправда (см. ссылки внизу), а предложение Каспарова сыграть еще один матч было встречено корпорацией оригинально — герой матча (Deep Blue) был демонтирован и сдан в утильмузей. Впрочем, это как раз легко объяснить тем, что так или иначе, но чемпион мира был побежден, цель достигнута, а выкладывать еще раз круглую сумму для утешения Каспарова в IBM как-то не очень хотели.
И все же, что доказали эти матчи? Что человек повержен? Если брать оба матча Каспарова с DB — то счет остался в пользу Каспарова — 6,5-5,5. Если даже брать только второй — то во-первых, наверное, статистически результат 2-1 в пользу одной стороны (без учета ничьих) ничего не доказывает. Во-вторых, поражение Каспарова в шестой партии — из-за явного зевка — вряд ли на основании такой грубейшей ошибки (я молчу про сдачу Каспаровым второй партии в ничейной позиции) можно доказывать силу шахматной программы.
После переезда Deep Blue в музей, люди, разумеется, не перестали играть в шахматы с компьютером. Однако, о подобных матчах вообще не слышно, гроссмейстеры теперь предпочитают более экзотические виды использования компьютера. Может, ведущие гроссмейстеры просто боятся поражений от машины? Почему тогда владельцы суперкомпьютеров, авторы мощных шахматных программ, не заявляют, мол, вот мы предложили матч, а чемпион мира отказался? Скорее всего дело действительно в падении интереса к шахматам, интереснее сейчас ставить другие задачи перед ИИ, а поражение от машины в шахматы, пусть даже и чемпиона мира — кому оно интересно, ведь “уже давно машина выиграла у чемпиона мира”.
Как выигрывать в шахматы – 10 ключевых моментов, которые стоит знать
Дата публикации: 2021-07-06
Когда Вы играете на уровне 1800 и ниже, выигрыши (впрочем, как и проигрыши) достигаются довольно легко. Ведь исход многих поединков между игроками с таким рейтингом решается ошибками и зевками. И если вы сейчас находитесь именно на этой ступени развития, то наверняка мечтаете сделать свои победы стабильными. Откроем Вам небольшой секрет – чтобы выйти на следующую шахматную орбиту, не нужно обладать фотографической памятью или просчитывать на 10 ходов вперед. Всё проще. Просто попробуйте следовать десяти рекомендациям из списка ниже.
1. Научитесь быстро развивать фигуры
Все говорят, что дебюты желательно знать досконально, и чтобы чаще побеждать, следует быть теоретически подкованным игроком. Да, у вас должно быть общее представление, как развивать фигуры и как действовать сразу после. Но главная цель любого дебюта – развить фигуры на нужные поля быстрее, чем ваш соперник. И если вы смогли это сделать, значит вы на шаг приблизились к победе в игре.
Выигрышная стратегия в шахматах №1: быстро развивайте фигуры
2. Ранняя рокировка
Некоторые игроки-любители совершают ошибку, когда отказываются от рокировки, польстившись на пешки соперника или переключившись на развитие других фигур. Это часто приводит к агрессивной атаке на их короля, и потом они платят огромную цену за восстановление.
Выигрышная стратегия в шахматах №2: Ранняя рокировка
3. Контроль центра
Контроль над центром даёт вам нечто большее, чем просто возможность перемещать фигуры по своему усмотрению. Гораздо важнее, что это обеспечивает легкую транспортировку ваших фигур к обеим сторонам доски. Таким образом, вы получаете отличные возможности для мощной атаки, которая, в свою очередь, может привести к победе в игре.
И если вы колеблетесь и не знаете, как играть конкретную партию, вспомните, что контроль над центром обычно является выигрышной стратегией.
Выигрышная стратегия в шахматах №3: Контроль центра
4. Планируйте больше, чем на один ход вперед
Конечно, Вам не нужно просчитывать на 10 ходов вперед (хотя, если вы можете, то это здорово).
Выигрышная стратегия в шахматах №4: Думайте больше, чем на один ход вперед
5. Научитесь делать связку, вилку и сквозную атаку против фигур соперника
Связка, вилка и сквозная атака принесли за всю историю шахмат больше побед, чем все другие комбинации вместе взятые. Вот почему важно идентифицировать их и быстро находить даже в сложных позициях. Краткое напоминание о роли этой «могучей тройки»:
Выигрышная стратегия в шахматах №5: Связать фигуру соперника
Выигрышная стратегия в шахматах №6: Вилка на фигуры соперника
Сквозная атака очень похожа на связку, но здесь сначала атакуется более ценная фигура. Когда она отходит, то теряется менее ценная фигура.
Выигрышная стратегия в шахматах №7: Сквозная атака на фигуру соперника
Потренируйтесь находить эти ключевые элементы в разных позициях, и вы заметите, что начнете выигрывать в шахматы часто!
6. Всегда держите все ваши фигуры под защитой
Игроки-любители игнорируют данное важное правило и расплачиваются за это. Даже если вам в моменте кажется достаточно безопасным оставить своего коня без защиты, дважды подумайте, прежде чем это сделать (хотя есть исключения).
Выигрышная стратегия в шахматах №8: Сохраняйте свои фигуры под защитой
7. Сохраните свою пешечную структуру в наилучшем виде
Многие игроки полагают, что пешечная структура играет важную роль только в гроссмейстерских играх. Это не так. Если ваша пешечная структура слаба, даже на уровне ниже 1800 вы окажетесь в невыгодном положении. Слабые, изолированные или сдвоенные пешки не могут защитить себя и требуют постоянной защиты от других фигур. Если пешки недостаточно защищены, они упадут. И все мы знаем, что очень трудно выиграть в шахматы, если у вас не хватает 2-3 «солдат» в Пешечном окончании.
Чтобы избежать этого печального сценария, всегда учитывайте изменение пешечной структуры, когда вы:
Выигрышная стратегия в шахматах №9: Держите свою пешечную структуру в хорошей форме
8. Всегда ищите возможности для атаки
Выигрышная стратегия в шахматах № 10: Атака, атака, атака!
9. Если вы играете чёрными, это не значит, что вы в невыгодном положении
Многие клубные игроки думают, что если им выпало быть на чёрной стороне, то придётся играть на уравнивание или другими словами, на ничью. Это утверждение отчасти верно для профессиональных шахмат. Однако в шахматах до 2000 ЭЛО игра чёрными не означает автоматически более слабые позиции. Большинство исходов партий на этом уровне определяются не крошечными преимуществами, полученными в дебюте. Большее значение имеет разница в материале, серьезные и позиционные ошибки. Если ваш рейтинг не превышает 2200, то не беспокойтесь о цвете фигур. У вас абсолютно равные шансы на победу.
Выигрышная стратегия в шахматах № 11: Чёрными фигурами нужно играть на победу
10. Научитесь играть форсированные ходы
Форсированные ходы заставляют вашего противника реагировать на них. Например, если вы ставите шах королю, то ваш соперник обязан выйти из-под шаха. Таким образом, шах является форсированным ходом. Если вы захватите фигуру противника, то ему, скорее всего, нужно будет отбить её обратно. И это также форсированный ход.
Почему в шахматах важны форсированные ходы?
Форсированные ходы упрощают процесс расчёта, следовательно, снижают неопределенность в игре. Если вы видите, как можете поставить мат противнику через постоянные шахи королю, то это будет намного безопаснее, чем если бы ваша комбинация не предполагала форсированных ходов. Гораздо легче держать ситуацию под контролем, когда вам нужно рассчитать лишь один вариант. Поэтому, если вы хотите выигрывать в шахматы, вам нужно научиться определять форсирующие ходы и применять их в своих играх.
Выигрышная стратегия в шахматах № 12: Применяйте форсированные ходы
Как компьютер играет в шахматы?
Хикару Накамура, недавно бросивший вызов компьютеру
Компьютер уже давно обыграл человека в шахматы, сейчас сильнейшие шахматисты не способны выиграть даже у старенького ноутбука. Теперь шахматные движки используются для анализа партий, поиска новых вариантов и игры по переписке.
Если вам интересно, как же устроены шахматные движки — добро пожаловать под кат.
Введение
Когда-то я был уверен, что шахматные программы (они же движки, впрочем об этом чуть позже), просто держат в памяти огромное количество сыгранных партий и находят в них нынешнюю позицию и делают верный ход. По-моему, я прочитал об этом в какой-то книжке.
Это, несомненно, очень наивное мнение. Новую позицию в шахматах можно получить к десятому ходу. Хоть в шахматах и меньше позиций, чем в го, тем не менее, уже после 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 партий.