Шахматные движки: анализ и эволюция программного обеспечения

Введение

Компьютерная программа для анализа шахмат и игры.

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

История

Значение термина «шахматный движок» со временем менялось. В 1986 году Линда и Тони Шерцер представили свою программу Bebe на 4-м Чемпионате мира по компьютерным шахматам, запустив её на «Chess Engine» — их торговой марке для шахматного компьютерного оборудования, производимого и продаваемого их компанией Sys 10, Inc. К 1990 году разработчики Deep Blue, Фэн Хсиунг Хсу и Мюррей Кэмпбелл, писали о том, что они снабжают свою программу «поисковым движком», подразумевая, по-видимому, программное обеспечение, а не аппаратное. В декабре 1991 года журнал Computer schach & Spiele назвал недавно выпущенный Fritz от Chessbase «Schachmotor» — немецкий перевод термина «шахматный движок». К началу 1993 года Марти Хирш проводил различие между коммерческими шахматными программами, такими как Chessmaster 3000 или Battle Chess, с одной стороны, и «шахматными движками», такими как ChessGenius или его собственная MChess Pro, с другой. По его мнению, коммерческие шахматные программы были недорогими, обладали эффектной графикой, но не занимали высоких позиций в рейтинговых списках SSDF (Шведской шахматной компьютерной ассоциации), в то время как движки были более дорогими и имели высокие рейтинги. В 1994 году Шей Бушинский работал над ранней версией своей программы Junior. Он хотел сосредоточиться на шахматной игре, а не на графике, и поэтому спросил Тима Манна, как можно заставить Junior взаимодействовать с Winboard. Ответ Тима послужил основой для протокола связи шахматных движков (Chess Engine Communication Protocol) или Winboard-движков, изначально являвшегося подмножеством интерфейса командной строки GNU Chess. Также в 1994 году Стивен Дж. Эдвардс опубликовал спецификацию Portable Game Notation (PGN). В ней упоминается, что программам для чтения PGN не обязательно иметь «полноценный шахматный движок». Также упоминаются три «графических пользовательских интерфейса» (GUI): XBoard, pgnRead и Slappy — база данных. К середине 2000-х годов движки стали настолько сильными, что смогли побеждать даже лучших игроков-людей. За исключением развлекательных целей, особенно при использовании движков с ограниченной силой, матчи между людьми и движками стали редкостью; движки все чаще рассматриваются как инструменты для анализа, а не как соперники.

The meaning of the term "chess engine" has evolved over time. In 1986, Linda and Tony Scherzer entered their program Bebe into the 4th World Computer Chess Championship, running it on "Chess Engine," their brand name for the chess computer hardware made, and marketed by their company Sys 10, Inc. By 1990 the developers of Deep Blue, Feng hsiung Hsu and Murray Campbell, were writing of giving their program a 'searching engine,' apparently referring to the software rather than the hardware. In December 1991, Computer schach & Spiele referred to Chessbase's recently released Fritz as a 'Schach motor,' the German translation for 'chess engine. By early 1993, Marty Hirsch was drawing a distinction between commercial chess programs such as Chessmaster 3000 or Battle Chess on the one hand, and 'chess engines' such as ChessGenius or his own MChess Pro on the other. In his characterization, commercial chess programs were low in price, had fancy graphics, but did not place high on the SSDF (Swedish Chess Computer Association) rating lists while engines were more expensive, and did have high ratings. In 1994, Shay Bushinsky was working on an early version of his Junior program. He wanted to focus on the chess playing part rather than the graphics, and so asked Tim Mann how he could get Junior to communicate with Winboard. Tim's answer formed the basis for what became known as the Chess Engine Communication Protocol or Winboard engines, originally a subset of the GNU Chess command line interface. Also in 1994, Stephen J. Edwards released the Portable Game Notation (PGN) specification. It mentions PGN reading programs not needing to have a "full chess engine." It also mentions three "graphical user interfaces" (GUI): XBoard, pgnRead and Slappy the database. By the mid 2000s, engines had become so strong that they were able to beat even the best human players. Except for entertainment purposes, especially using engines with limited strength, matches between humans and engines are now rare; engines are increasingly regarded as tools for analysis rather than as opponents.

Протокол интерфейса

Общие движки Winboard включают Crafty, ProDeo (на основе Rebel), Chenard, Zarkov и Phalanx. В 1995 году Chessbase выпустила версию своей программы базы данных, включающую Fritz 4 как отдельный движок. Это было первое появление протокола Chessbase. Вскоре после этого они добавили движки Junior и Shredder в свою продуктовую линейку, включая движки в протоколе CB в качестве отдельных программ, которые можно было установить в программу Chessbase или в один из других графических интерфейсов в стиле Fritz. Fritz 1–14 выпускались только как движки Chessbase, в то время как Hiarcs, Nimzo, Chess Tiger и Crafty были портированы в формат Chessbase, хотя изначально они были движками UCI или Winboard. В последнее время Chessbase начала включать в свои игровые программы движки, такие как Komodo, Houdini, Fritz 15–16 и Rybka, вместо того чтобы конвертировать их в движки Chessbase. В 2000 году Стефан Майер-Кален и Франц Губер выпустили Universal Chess Interface, более детальный протокол, который представил расширенный набор функций. Вскоре после этого Chessbase прекратила поддержку движков Winboard и добавила поддержку UCI в свои графические интерфейсы и программы Chessbase. Большинство ведущих движков в настоящее время используют UCI: Stockfish, Komodo, Leela Chess Zero, Houdini, Fritz 15–16, Rybka, Shredder, Fruit, Critter, Ivanhoe и Ruffian. С 1998 года немецкая компания Millenium 2000 на короткое время перешла от специализированных шахматных компьютеров к рынку программного обеспечения, разработав протокол Millennium Chess System (MCS) для серии компакт-дисков, содержащих ChessGenius или Shredder, но после 2001 года прекратила выпуск нового программного обеспечения. Более длительное время протокол движка использовался голландской компанией Lokasoft, которая в конечном итоге взяла на себя маркетинг Rebel Эда Шрёдера.

Увеличение силы

Шахматные движки постоянно увеличивают силу игры. Это отчасти связано с ростом вычислительной мощности, позволяющей проводить расчеты на всё большую глубину за заданное время. Кроме того, улучшились методы программирования, что позволяет движкам более избирательно анализировать варианты и лучше понимать позицию. Шахматный движок часто использует обширную предварительно вычисленную дебютную "книгу" для повышения своей силы в первые несколько ходов, возможно, до 20 ходов и более в глубоко проанализированных вариантах. Некоторые шахматные движки поддерживают базу данных шахматных позиций, вместе с ранее вычисленными оценками и наилучшими ходами, фактически представляющую собой своего рода "словарь" повторяющихся шахматных позиций. Поскольку эти позиции вычислены заранее, движок просто выбирает один из ходов, указанных в базе данных, тем самым экономя вычислительное время и достигая более сильной и быстрой игры. Некоторые шахматные движки используют табличные базы эндшпилей для повышения своей силы в эндшпиле. Табличная база эндшпиля включает в себя все возможные эндшпильные позиции с небольшим количеством фигур. Каждая позиция однозначно определяется как выигрышная, проигрышная или ничейная для стороны, которой предстоит ход, а также количество ходов до конца при оптимальной игре обеих сторон. Табличная база определяет для каждой позиции ход, который обеспечит наиболее быструю победу при оптимальной защите противника, или ход, который позволит проиграть как можно медленнее при оптимальном нападении. Такие табличные базы доступны для всех шахматных эндшпилей с семью или менее фигурами (исключаются тривиальные эндшпильные позиции, например, шесть белых фигур против одинокого черного короля). Когда для достижения необратимого улучшения в эндшпиле требуется больше ходов, чем горизонт расчета шахматного движка, движок не гарантированно найдет наилучший ход без использования табличной базы эндшпиля и во многих случаях может нарушить правило пятидесяти ходов. Многие движки используют "постоянный мозг" (продолжающий вычисления во время хода противника) как способ повышения своей силы. Распределенные вычисления также используются для улучшения программного кода шахматных движков. В 2013 году разработчики шахматной программы Stockfish начали использовать распределенные вычисления для улучшения программного кода. По состоянию на 2017 год было использовано более 745 лет процессорного времени для игры в более чем 485 миллионов шахматных партий, а результаты использовались для внесения небольших, постепенных улучшений в шахматное программное обеспечение. В 2019 году автор Ethereal Эндрю Грант запустил распределенную систему тестирования OpenBench, основанную на системе тестирования Stockfish, и в настоящее время это наиболее широко используемая система тестирования для шахматных движков.

Chess engines increase in playing strength continually. This is partly due to the increase in processing power that enables calculations to be made to ever greater depths in a given time. In addition, programming techniques have improved, enabling the engines to be more selective in the lines that they analyze and to acquire a better positional understanding. A chess engine often uses a vast previously computed opening "book" to increase its playing strength for the first several moves, up to possibly 20 moves or more in deeply analyzed lines. Some chess engines maintain a database of chess positions, along with previously computed evaluations and best moves—in effect, a kind of "dictionary" of recurring chess positions. Since these positions are pre computed, the engine merely plays one of the indicated moves in the database, thereby saving computing time, resulting in stronger, faster play. Some chess engines use endgame tablebases to increase their playing strength during the endgame. An endgame tablebase includes all possible endgame positions with a small amount of material. Each position is conclusively determined as a win, loss, or draw for the player whose turn it is to move, and the number of moves to the end with best play by both sides. The tablebase identifies for every position the move which will win the fastest against an optimal defense, or the move that will lose the slowest against an optimal offense. Such tablebases are available for all chess endgames with seven pieces or fewer (trivial endgame positions are excluded, such as six white pieces versus a lone black king). When the maneuvering in an ending to achieve an irreversible improvement takes more moves than the horizon of calculation of a chess engine, an engine is not guaranteed to find the best move without the use of an endgame tablebase, and in many cases can fall foul of the fifty move rule as a result. Many engines use permanent brain (continuing to calculate during the opponent's turn) as a method to increase their strength. Distributed computing is also used to improve the software code of chess engines. In 2013, the developers of the Stockfish chess playing program started using distributed computing to make improvements in the software code. as of 2017, a total of more than 745 years of CPU time has been used to play more than 485 million chess games, with the results being used to make small and incremental improvements to the chess playing software. In 2019, Ethereal author Andrew Grant started the distributed computing testing framework OpenBench, based upon Stockfish's testing framework, and it is now the most widely used testing framework for chess engines.

Ограничение мощности двигателя

К концу 1990-х годов лучшие шахматные движки стали настолько сильными, что у немногих игроков оставался шанс выиграть партию против них. Чтобы увеличить шансы игроков, движки стали включать настройки для регулировки или ограничения своей силы. В 2000 году, когда Стефан Майер-Кален и Франц Губер выпустили протокол Universal Chess Interface, они добавили параметры `uci limitstrength` и `uci elo`, позволяя авторам движков предлагать различные уровни силы, оцениваемые в соответствии с рейтингом Эло, откалиброванным по одному из рейтинговых списков. Большинство графических интерфейсов для движков UCI позволяют пользователям устанавливать этот рейтинг Эло в меню. Даже движки, не использующие этот параметр, часто имеют настраиваемый параметр силы (например, Stockfish 11). Движки, поддерживающие параметр `uci elo`, включают Houdini, Fritz 15–16, Rybka, Shredder, Hiarcs, Junior, Zappa и Sjeng. Графические интерфейсы, такие как Shredder, Chess Assistant, Convekta Aquarium, Hiarcs Chess Explorer и Arena от Martin Blume, имеют выпадающие меню для настройки параметра `uci elo` движка. Графические интерфейсы семейства Fritz, Chess Assistant и Aquarium также имеют независимые средства ограничения силы движка, основанные, по всей видимости, на способности движка генерировать ранжированные списки ходов (обозначаемые как multipv, что расшифровывается как "principal variation" – главная вариация).

Турниры

Результаты компьютерных турниров дают представление об относительной силе шахматных движков. Однако турниры не проводят статистически значимого количества партий для точного определения силы. Фактически, число партий, необходимых для достижения статистической значимости между примерно равными движками, исчисляется тысячами, что делает это непрактичным в рамках турнира. Большинство турниров также допускают использование любого оборудования, поэтому сравниваются лишь комбинации движка и оборудования. Исторически, самыми сильными были коммерческие программы. Если любительский движок выигрывает турнир или показывает хорошие результаты (например, Zappa в 2005 году), то он быстро становится коммерческим продуктом. Победы в этих турнирах приносят победившим программам большой престиж и, следовательно, используются в маркетинге. Однако с развитием проектов распределенных вычислений, таких как Leela Chess Zero и Stockfish, и тестовых фреймворков, таких как FishTest и OpenBench, в конце 2010-х годов, бесплатные и открытые программы в значительной степени вытеснили коммерческие программы в качестве сильнейших движков на турнирах.

Рейтинги

Рейтинговые списки шахматных движков предназначены для предоставления статистически значимых оценок относительной силы движка. Эти списки проводят множество партий между движками. Некоторые также стандартизируют дебютные книги, контроль времени и компьютерное оборудование, используемое движками, чтобы измерить только различия в силе самих движков. Эти списки предоставляют не только рейтинг, но и погрешности для данных рейтингов. Рейтинги в рейтинговых списках, хотя и вычисляются с использованием системы Эло (или аналогичных методов оценки), не имеют прямого отношения к рейтингам Эло ФИДЕ или рейтингам других шахматных федераций для игроков-людей. За исключением некоторых партий «человек против машины», организованных SSDF много лет назад (когда движки были значительно слабее современных), нет калибровки между этими рейтинговыми списками и группами игроков. Следовательно, важны ранги и разница между рейтингами, а не абсолютные значения. Во многих рейтинговых списках отсутствуют IPPOLIT и его производные. Хотя они очень сильны и имеют открытый исходный код, коммерческие разработчики заявляют, что они были созданы на основе дизассемблированного бинарного кода Rybka. Из-за этого спора все эти движки были занесены в черный список многих турниров и рейтинговых списков. В свою очередь, Rybka была обвинена в том, что основана на Fruit, и в июне 2011 года ICGA официально заявила, что Rybka была создана на основе Fruit и Crafty и запретила Rybka участвовать в чемпионате мира по компьютерным шахматам Международной ассоциации компьютерных игр, аннулировав ее предыдущие победы (2007, 2008, 2009 и 2010). ICGA подверглась критике за это решение. Несмотря на это, Rybka по-прежнему включена во многие рейтинговые списки, такие как CCRL и CEGT, наряду с Houdini, производной от IPPOLIT Robbolito, и Fire, производной от Houdini. Кроме того, Fat Fritz 2, производная от Stockfish, также включена в большинство рейтинговых списков.

Тест-комплекты

Двигатели могут быть протестированы путем измерения их производительности в конкретных позициях. Обычно используются наборы тестов, в которых для каждой заданной позиции существует один оптимальный ход. Эти позиции могут быть направлены на позиционную игру, тактику или эндшпиль. Например, набор тестов Nolot ориентирован на глубокие жертвы. Наборы тестов BT2450 и BT2630 измеряют тактические возможности шахматного движка и использовались REBEL. Также существует общий набор тестов под названием Brilliancy, который был скомпилирован в основном из задач из книги "Как переоценить свою игру в шахматы". Стратегический набор тестов (STS) проверяет стратегическую силу движка. Еще один современный набор тестов – Nightmare II, который содержит 30 шахматных задач.

Каспаров против мира (шахматная игра, играемая с помощью компьютера)

В 1999 году Гарри Каспаров сыграл шахматную партию под названием «Каспаров против мира» через Интернет, организованную игровой зоной MSN. Обе стороны использовали компьютерную помощь (шахматные движки). В «Мировую команду» вошли более 50 000 участников из более чем 75 стран, определявших свои ходы большинством голосов. Игра продолжалась четыре месяца и завершилась после 62-го хода Каспарова, когда он объявил о вынужденном мате в 28 ходов, найденном с помощью компьютерной программы Deep Junior. 22 октября участники голосования за «Мировую команду» признали поражение. После игры Каспаров заявил: «Это величайшая партия в истории шахмат. Огромное количество идей, сложность и вклад, который она внесла в шахматы, делают её самой важной партией, когда-либо сыгранной».

Двигатели для шахматных вариантов

Некоторые шахматные движки были разработаны для игры в варианты шахмат, добавляя необходимый код для симуляции нестандартных фигур или для анализа игры на нестандартных досках. Например, ChessV и Fairy Max способны играть в варианты на шахматной доске размером до 12×8, такие как шахматы Капабланки (доска 10×8). Однако для досок большего размера существует мало шахматных движков, способных играть эффективно, и, фактически, игры в шахматы на неограниченной доске (бесконечные шахматы) практически не изучены шахматным программным обеспечением, хотя теоретически программа, использующая алгоритм, основанный на MuZero, могла бы справиться с неограниченным пространством состояний.

Графические пользовательские интерфейсы

XBoard/Winboard был одним из самых ранних графических пользовательских интерфейсов (GUI). Тим Манн создал его, чтобы предоставить GUI для шахматного движка GNU Chess, но затем появились другие движки, такие как Crafty, которые использовали протокол Winboard. В конечном итоге, программа Chessmaster включила возможность импортировать другие движки Winboard, помимо движка King, который уже был в комплекте. В 1995 году Chessbase начала предлагать движок Fritz как отдельную программу в составе базы данных Chessbase и в GUI Fritz. Вскоре после этого они добавили движки Junior и Shredder в свой ассортимент, упаковывая их в тот же GUI, что и Fritz. В конце 1990-х годов GUI Fritz мог запускать движки Winboard через адаптер, но после 2000 года Chessbase просто добавила поддержку движков UCI и перестала уделять много внимания Winboard. В 2000 году Стефан Майер-Кален начал продавать Shredder в отдельном GUI UCI собственной разработки, позволяя импортировать в него движки UCI или Winboard. Chess Assistant от Convekta и ChessPartner от Lokasoft также добавили возможность импортировать движки Winboard и UCI в свои продукты. Шейн Хадсон разработал Shane's Chess Information Database, бесплатный GUI для Linux, Mac и Windows. Мартин Блюм разработал Arena, и все три могут работать как с движками UCI, так и с движками Winboard. На Android Арт Бик выпустил Chess for Android, еще один бесплатный GUI, а Chess PGN Master Герхарда Калаба и Droidfish Питера Остерлунда также могут использоваться в качестве GUI для движков. В компьютерно-шахматной Вики перечислены многие шахматные GUI.