Компьютерные шахматы -Computer chess

Сенсорный шахматный компьютер 1990-х годов с ЖК-экраном

Компьютерные шахматы включают в себя как оборудование (выделенные компьютеры), так и программное обеспечение, позволяющее играть в шахматы . Компьютерные шахматы дают игрокам возможность тренироваться даже в отсутствие противников-людей, а также предоставляют возможности для анализа, развлечения и обучения.

Компьютерные шахматные приложения, которые играют на уровне шахматного мастера или выше, доступны на оборудовании от суперкомпьютеров до смартфонов . Также доступны автономные шахматные машины. Stockfish , GNU Chess , Fruit и другие бесплатные приложения с открытым исходным кодом доступны для различных платформ.

Компьютерные шахматные приложения, независимо от того, реализованы ли они в аппаратном или программном обеспечении, используют стратегии, отличные от человеческих, для выбора своих ходов: они используют эвристические методы для построения, поиска и оценки деревьев, представляющих последовательности ходов из текущей позиции, и пытаются выполнить наилучшую такую ​​последовательность во время игры. . Такие деревья обычно довольно большие, от тысяч до миллионов узлов. Вычислительная скорость современных компьютеров, способных обрабатывать от десятков тысяч до сотен тысяч и более узлов в секунду, наряду с эвристиками расширения и сокращения, которые сужают дерево до наиболее релевантных узлов, делают такой подход эффективным.

Первыми шахматными машинами, способными играть в шахматы или сокращенные шахматные игры, были программы, работавшие на цифровых компьютерах в начале эпохи ламповых компьютеров (1950-е годы). Ранние программы играли настолько плохо, что их мог победить даже новичок. В течение 40 лет, в 1997 году, шахматные движки , работающие на суперкомпьютерах или специализированном оборудовании, были способны побеждать даже лучших игроков-людей . К 2006 году программы, работающие на настольных ПК , достигли таких же возможностей. В 2006 году Монро Ньюборн , профессор компьютерных наук Университета Макгилла , заявила: «Наука сделана». Тем не менее, решение шахмат в настоящее время невозможно для современных компьютеров из- за чрезвычайно большого количества возможных вариантов игры .

Когда-то компьютерные шахматы считались « дрозофилой ИИ», вершиной инженерии знаний . Но сейчас эта область считается научно завершенной парадигмой, а игра в шахматы — рутинной вычислительной деятельностью.

Доступность и игровая сила

Компьютерная шахматная ИС, носящая имя разработчика Франса Морша (см. Мефисто ) .

Шахматные машины/программы доступны в нескольких различных формах: автономные шахматные машины (обычно это микропроцессор, на котором работает программная шахматная программа, но иногда и специализированная аппаратная машина), программы, работающие на стандартных ПК, веб-сайты и приложения для мобильных устройств. . Программы работают на всем, от суперкомпьютеров до смартфонов. Аппаратные требования для программ минимальны; приложения занимают не больше нескольких мегабайт на диске, используют несколько мегабайт памяти (но могут использовать гораздо больше, если она доступна), и достаточно любого процессора 300 МГц или выше. Производительность незначительно зависит от скорости процессора, но достаточный объем памяти для хранения большой таблицы транспонирования (до нескольких гигабайт и более) важнее для силы игры, чем скорость процессора.

Большинство доступных коммерческих шахматных программ и машин могут играть с силой супергроссмейстера (Elo 2700 или выше) и использовать преимущества многоядерных компьютерных процессоров с гиперпоточностью. Лучшие программы, такие как Stockfish , превзошли даже игроков уровня чемпионов мира. Большинство шахматных программ содержат шахматный движок, подключенный к графическому интерфейсу, например Winboard или Chessbase . Сила игры, контроль времени и другие параметры, связанные с производительностью, настраиваются в графическом интерфейсе. Большинство графических интерфейсов также позволяют игроку настраивать и редактировать позиции, отменять ходы, предлагать и принимать ничьи (и уходить в отставку), запрашивать и получать рекомендации по ходам, а также отображать анализ движка по ходу игры.

Существует несколько шахматных движков , таких как Sargon , IPPOLIT , Stockfish , Crafty , Fruit , Leela Chess Zero и GNU Chess , которые можно скачать (или получить исходный код иным образом) из Интернета бесплатно.

Виды и особенности шахматного софта

Возможно, наиболее распространенным типом шахматного программного обеспечения являются программы, которые просто играют в шахматы. Игрок-человек делает ход на доске, ИИ рассчитывает и выполняет следующий ход, а человек и ИИ делают ходы по очереди, пока один из игроков не сдастся. Шахматный движок , рассчитывающий ходы, и графический пользовательский интерфейс (GUI) иногда представляют собой отдельные программы. К графическому интерфейсу можно подключить разные движки, что позволяет играть против соперников разных стилей. Движки часто имеют простой текстовый интерфейс командной строки , в то время как графические интерфейсы могут предлагать различные наборы фигур, стили доски или даже трехмерные или анимированные фигуры. Поскольку современные движки настолько функциональны, движки или графический интерфейс могут предложить какой-то способ ограничить возможности движка, чтобы повысить шансы на победу игрока-человека. Двигатели универсального шахматного интерфейса (UCI), такие как Fritz или Rybka , могут иметь встроенный механизм для снижения рейтинга Elo движка (через параметры UCI uci_limitstrength и uci_elo). В некоторых версиях Fritz есть режим Handicap and Fun для ограничения текущего движка или изменения процента ошибок, которые он совершает, или изменения его стиля. У Фрица также есть режим друга, в котором во время игры он пытается соответствовать уровню игрока.

Скриншот Chess , компонента macOS

Шахматные базы данных позволяют пользователям осуществлять поиск в большой библиотеке исторических партий, анализировать их, проверять статистику и составлять дебютный репертуар. Chessbase (для ПК) является распространенной программой для этих целей среди профессиональных игроков, но есть альтернативы, такие как Shane's Chess Information Database (Scid) для Windows, Mac или Linux, Chess Assistant для ПК, Chess PGN Master Герхарда Калаба для Android или Giordano. Шахматная студия Vicoli для iOS.

Такие программы, как Playchess , позволяют вам играть в игры против других игроков через Интернет.

Программы обучения шахматам учат шахматам. У Chessmaster были обучающие программы по прохождению от ММ Джоша Вайцкина и гроссмейстера Ларри Кристиансена . Стефан Мейер-Кален предлагает программу Shredder Chess Tutor, основанную на учебниках Step Роба Брунии и Кора Ван Вейгердена. Компания Play Magnus чемпиона мира Магнуса Карлсена выпустила приложение Magnus Trainer для Android и iOS. В Chessbase есть Fritz и Chesster для детей. Convekta предоставляет большое количество обучающих приложений, таких как CT-ART и его линейка Chess King, на основе руководств гроссмейстера Александра Калинина и Максима Блоха.

Существует также программное обеспечение для решения шахматных задач .

Компьютеры против людей

Обнаружив в 1957 году скрининг опровержений — применение альфа-бета-отсечения для оптимизации оценки ходов, — команда из Университета Карнеги-Меллона предсказала, что к 1967 году компьютер победит чемпиона мира среди людей. Они не предвидели сложности определения правильного порядка. оценивать ходы. Исследователи работали над улучшением способности программ идентифицировать убийственные эвристики , необычайно результативные ходы для повторного изучения при оценке других ветвей, но в 1970-х годах большинство ведущих шахматистов считали, что компьютеры не скоро смогут играть на уровне мастеров . В 1968 году международный мастер Дэвид Леви сделал известное пари , что ни один шахматный компьютер не сможет победить его в течение десяти лет, а в 1976 году старший магистр и профессор психологии Элиот Херст из Университета Индианы написал, что «единственный способ, которым современная компьютерная программа когда-либо могла выиграть одну партию у мастера означало бы, что мастер, возможно, в пьяном угаре, играя 50 игр одновременно, совершил какую-нибудь ошибку, которая случается раз в год».

В конце 1970-х шахматные программы внезапно начали побеждать высококвалифицированных игроков-людей. В год заявления Херста команда Северо-Западного университета Chess 4.5 на уровне класса B чемпионата Америки по шахматам Пола Массона стала первой, выигравшей человеческий турнир. Леви выиграл свою ставку в 1978 году, обыграв Chess 4.7 , но он одержал первую компьютерную победу над игроком мастер-класса на турнирном уровне, выиграв одну из шести игр. В 1980 году Белль начала часто побеждать Мастерс. К 1982 году две программы играли на уровне Master, а три были немного слабее.

Внезапное улучшение без теоретического прорыва было неожиданным, так как многие не ожидали, что способности Белль проверять 100 000 позиций в секунду — около восьми слоев — будет достаточно. Spracklens, создатели успешной микрокомпьютерной программы Sargon , подсчитали, что 90 % улучшений произошло за счет более высокой скорости оценки и только 10 % за счет улучшения оценок. В 1982 году New Scientist заявил, что компьютеры «играют в ужасные шахматы ... неуклюжие, неэффективные, расплывчатые и просто уродливые», но люди проиграли им, совершая «ужасные ошибки, поразительные упущения, непонятные оплошности, грубые просчеты и т.п. гораздо чаще, чем они думали; «Короче говоря, компьютеры выигрывают прежде всего благодаря своей способности находить и использовать просчеты в человеческих инициативах».

К 1982 году шахматные программы на микрокомпьютерах могли оценивать до 1500 ходов в секунду и были такими же сильными, как шахматные программы для мэйнфреймов пятью годами ранее, и могли победить большинство игроков-любителей. Хотя они смогли заглянуть вперед только на один или два этапа больше, чем при их дебюте в середине 1970-х, это улучшило их игру больше, чем ожидали эксперты; кажущиеся незначительными улучшения «похоже, позволили преодолеть психологический порог, после которого становится доступным богатый урожай человеческих ошибок», пишет New Scientist . При обзоре SPOC в 1984 году BYTE написал, что «компьютеры - мейнфреймы, мини и микро - имеют тенденцию играть в уродливые, неэлегантные шахматы», но отметил заявление Роберта Бирна о том, что «тактически они более свободны от ошибок, чем средний игрок-человек». Журнал описал SPOC как «современную шахматную программу» для IBM PC с «удивительно высоким» уровнем игры и оценил ее рейтинг USCF в 1700 (класс B).

На чемпионате Северной Америки по компьютерным шахматам 1982 года Монро Ньюборн предсказал, что шахматная программа может стать чемпионом мира в течение пяти лет; директор турнира и международный мастер Майкл Вальво предсказал десять лет; Spraclens предсказал 15; Кен Томпсон предсказал более 20; а другие предсказывали, что этого никогда не произойдет. Однако наиболее широко распространено мнение, что это произойдет примерно в 2000 году. В 1989 году Леви потерпел поражение от Deep Thought в показательном матче. Тем не менее, уровень Deep Thought все еще был значительно ниже уровня чемпионата мира, что продемонстрировал действующий чемпион мира Гарри Каспаров , одержав две сильные победы в 1989 году. Только в матче 1996 года с Deep Blue от IBM Каспаров проиграл свою первую игру компьютеру. на контроле времени турнира Deep Blue против Каспарова, 1996, партия 1 . Фактически, в этой игре действующий чемпион мира впервые проиграл компьютеру с обычным контролем времени. Однако Каспаров перегруппировался, чтобы выиграть три и сыграть вничью две из оставшихся пяти партий матча, что привело к убедительной победе.

В мае 1997 года обновленная версия Deep Blue победила Каспарова со счетом 3½–2½ в ответном матче. Документальный фильм в основном о противостоянии был снят в 2003 году под названием Game Over: Kasparov and the Machine .

а б с г е ф грамм час
8
Шахматная доска480.svg
h7 белая ладья
f6 черный ферзь
h6 черный король
d5 белый ферзь
g5 белый конь
d4 черная пешка
а3 белая пешка
b3 белая пешка
f3 черная пешка
g3 белая пешка
h3 белая пешка
f2 черный конь
h2 белый король
e1 черная ладья
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
а б с г е ф грамм час
Конечная позиция

С увеличением вычислительной мощности и улучшенными функциями оценки шахматные программы, работающие на имеющихся в продаже рабочих станциях, начали конкурировать с лучшими игроками. В 1998 году Rebel 10 победили Вишванатана Ананда , который в то время занимал второе место в мире, со счетом 5–3. Однако большинство из этих игр не проводились с нормальным контролем времени. Из восьми партий четыре были блиц - партиями (пять минут плюс пять секунд задержки Фишера на каждый ход); эти повстанцы выиграли 3–1. Две полублиц-игры (по пятнадцать минут для каждой стороны), которые Ребель также выиграл (1½–½). Наконец, две партии были сыграны как обычные турнирные игры (сорок ходов за два часа, один час внезапная смерть); здесь Ананд выиграл ½–1½. В быстрых играх компьютеры играли лучше людей, но в классическом контроле времени, при котором определяется рейтинг игрока, преимущество было не столь явным.

В начале 2000-х коммерчески доступные программы, такие как « Юниор » и « Фриц », могли сыграть вничью матчи против бывшего чемпиона мира Гарри Каспарова и классического чемпиона мира Владимира Крамника .

В октябре 2002 года Владимир Крамник и Дип Фриц соревновались в восьмиматчевом матче Brains in Bahrain , завершившемся вничью. Крамник выиграл партии 2 и 3, используя «традиционную» антикомпьютерную тактику - играйте консервативно ради долгосрочного преимущества, которое компьютер не может увидеть в своем дереве игр. Однако Фриц выиграл пятую партию после серьезной ошибки Крамника. Шестая партия была названа комментаторами турнира «захватывающей». Крамник, находящийся в лучшей позиции в начале миттельшпиля , попытался пожертвовать фигурой, чтобы провести сильную тактическую атаку, стратегию, которая, как известно, очень рискованна против компьютеров, которые лучше всего защищаются от таких атак. Верный форме, Фриц нашел непроницаемую защиту, а атака Крамника захлебнулась, оставив его в плохой позиции. Крамник сдал партию, считая позицию проигранной. Однако послематчевый человеческий и компьютерный анализ показал, что программа Fritz вряд ли смогла добиться победы, и Крамник фактически пожертвовал ничейной позицией. Последние две игры были ничьими. Учитывая обстоятельства, большинство комментаторов по-прежнему оценивают Крамника как более сильного игрока в матче.

В январе 2003 года Каспаров играл в еще одну шахматную компьютерную программу Junior в Нью-Йорке. Матч закончился со счетом 3–3.

В ноябре 2003 года Каспаров сыграл X3D Fritz . Матч закончился со счетом 2–2.

В 2005 году Hydra , специализированный шахматный компьютер со специальным оборудованием и шестьюдесятью четырьмя процессорами, а также победитель 14-го IPCCC в 2005 году, победил Майкла Адамса , занявшего седьмое место, со счетом 5½–½ в матче из шести партий (хотя подготовка Адамса была гораздо менее серьезной). тщательнее, чем у Крамника для сериала 2002 года).

В ноябре-декабре 2006 года чемпион мира Владимир Крамник играл с Deep Fritz. На этот раз победил компьютер; матч закончился со счетом 2–4. Крамник смог просмотреть вступительную книгу компьютера. В первых пяти партиях Крамник вел партию в типичном «антикомпьютерном» позиционном состязании. Он проиграл одну партию ( пропустив мат в одной ) и сыграл вничью следующие четыре. В финальной партии, пытаясь свести матч вничью, Крамник применил более агрессивную сицилианскую защиту и потерпел поражение.

Было предположение, что интерес к шахматным соревнованиям между людьми и компьютерами резко упадет в результате матча Крамник-Дип Фриц в 2006 году. По словам Ньюборна, например, «наука сделана».

Шахматные матчи между людьми и компьютерами показали, что лучшие компьютерные системы обгоняют чемпионов по шахматам среди людей в конце 1990-х годов. За 40 лет до этого тенденция была такова, что лучшие машины получали около 40 баллов в год в рейтинге Эло , в то время как лучшие люди получали только примерно 2 балла в год. Наивысший рейтинг, полученный компьютером в соревнованиях между людьми, был рейтингом USCF Deep Thought, равным 2551 в 1988 году, и ФИДЕ больше не принимает результаты человека и компьютера в свои рейтинговые списки. Для оценки машин были созданы специализированные пулы Elo только для машин, но такие числа, хотя и похожи внешне, не сравниваются напрямую. В 2016 году Шведская шахматная компьютерная ассоциация оценила компьютерную программу Komodo на 3361 балл.

Шахматные движки продолжают совершенствоваться. В 2009 году шахматные движки, работающие на более медленном оборудовании, достигли уровня гроссмейстера . Мобильный телефон выиграл турнир категории 6 с рейтингом производительности 2898: шахматный движок Hiarcs 13, работающий внутри Pocket Fritz 4 на мобильном телефоне HTC Touch HD , выиграл турнир Copa Mercosur в Буэнос-Айресе, Аргентина, с 9 победами и 1 ничьей 4 августа. 14, 2009. Pocket Fritz 4 ищет менее 20 000 позиций в секунду. Это в отличие от суперкомпьютеров, таких как Deep Blue, которые искали 200 миллионов позиций в секунду.

Продвинутые шахматы — это форма шахмат, разработанная Каспаровым в 1998 году, в которой человек играет против другого человека, и оба имеют доступ к компьютерам для повышения своей силы. Каспаров утверждал, что получившийся «продвинутый» игрок сильнее человека или компьютера. Это было доказано во многих случаях, например, на турнирах по фристайлу.

Современные игроки склонны относиться к шахматным движкам как к инструментам анализа, а не как к противникам. Шахматный гроссмейстер Эндрю Солтис заявил в 2016 году: «Компьютеры слишком хороши» и что чемпион мира Магнус Карлсен не будет играть в компьютерные шахматы, потому что «он просто все время проигрывает, и нет ничего более удручающего, чем проигрывать, даже не участвуя в игре. "

Компьютерные методы

Начиная с эры механических машин, которые играли в ладьи и короля, и электрических машин, которые играли в другие игры, такие как гекс , в первые годы 20-го века, ученые и теоретики стремились разработать процедурное представление того, как люди учатся, запоминают, думают и применяют. знаний, а игра в шахматы из-за своей пугающей сложности стала « дрозофилой искусственного интеллекта (ИИ)». Процедурное разрешение сложности стало синонимом мышления, и ранние компьютеры, еще до эпохи шахматных автоматов, в народе назывались «электронными мозгами». Начиная со второй половины 20-го века было разработано несколько различных схем для представления знаний и мышления применительно к игре в шахматы (и другие игры, такие как шашки):

Используя эвристику «цели и средства», человек-шахматист может интуитивно определить оптимальные результаты и способы их достижения независимо от количества необходимых ходов, но компьютер должен быть систематическим в своем анализе. Большинство игроков согласны с тем, что для хорошей игры необходимо смотреть как минимум на пять ходов вперед (десять слоев ), когда это необходимо. Обычные турнирные правила дают каждому игроку в среднем три минуты на ход. В среднем на одну шахматную позицию можно сделать более 30 допустимых ходов, поэтому компьютер должен изучить квадриллион возможностей, чтобы заглянуть вперед на десять слоев (пять полных ходов); тому, кто мог бы исследовать миллион позиций в секунду, потребовалось бы более 30 лет.

Самые ранние попытки процедурного представления игры в шахматы предшествовали эпохе цифровой электроники, но именно цифровой компьютер с хранимой программой дал возможность вычислить такую ​​сложность. Клод Шеннон в 1949 году изложил принципы алгоритмического решения шахмат. В этой статье игра представлена ​​​​«деревом» или цифровой структурой данных выбора (ветвей), соответствующих ходам. Узлы дерева были позициями на доске в результате выбора хода. Невозможность представить всю шахматную партию путем построения дерева от первого хода до последнего стала очевидной сразу: в шахматах на одну позицию приходится в среднем 36 ходов, а средняя партия длится около 35 ходов до отказа (60-80 ходов, если играть поставить мат, пат или другую ничью). Возможны 400 позиций после первого хода каждого игрока, около 200 000 после двух ходов каждого и почти 120 миллионов после всего лишь 3 ходов каждого.

Таким образом, был предложен ограниченный просмотр вперед (поиск) на некоторую глубину с последующим использованием знаний, специфичных для предметной области, для оценки результирующих конечных позиций. Получилась бы своего рода средняя позиция при хороших ходах обеих сторон, и ее оценка информировала бы игрока о хороших или плохих выбранных ходах. Операции поиска и сравнения на дереве хорошо подходили для компьютерных вычислений; представления тонких шахматных знаний в оценочной функции не было. Ранние шахматные программы страдали в обеих областях: для поиска в огромном дереве требовались вычислительные ресурсы, намного превышающие имеющиеся, а для того, чтобы выяснить, какие шахматные знания были полезны и как их кодировать, потребовались десятилетия.

Разработчики шахматной компьютерной системы должны решить ряд принципиальных вопросов реализации. Это включает:

  • Графический пользовательский интерфейс (GUI) — как вводятся ходы и сообщаются пользователю, как записывается игра, как устанавливается контроль времени и другие аспекты интерфейса.
  • Представление на доске — как отдельная позиция представлена ​​в структурах данных;
  • Методы поиска – как определить возможные ходы и выбрать наиболее перспективные для дальнейшего изучения;
  • Оценка листа — как оценить значение позиции доски, если дальнейший поиск с этой позиции производиться не будет.

Адриан де Гроот взял интервью у ряда шахматистов разной силы и пришел к выводу, что и мастера , и новички рассматривают примерно от сорока до пятидесяти позиций, прежде чем решить, какой ход сыграть. Что делает первых лучшими игроками, так это то, что они используют навыки распознавания образов , основанные на опыте. Это позволяет им исследовать некоторые линии гораздо глубже, чем другие, просто не рассматривая ходы, которые они могут считать плохими. Еще одним доказательством этого является то, что хорошим игрокам-людям гораздо легче вспоминать позиции из настоящих шахматных игр, разбивая их на небольшое количество узнаваемых подпозиций, а не на совершенно случайное расположение одних и тех же фигур. Напротив, плохие игроки имеют одинаковый уровень припоминания для обоих.

Эквивалентом этого в компьютерных шахматах являются оценочные функции для оценки листьев, которые соответствуют навыкам распознавания образов людьми-игроками, и использование методов машинного обучения для их обучения, таких как настройка Texel, стохастический градиентный спуск и обучение с подкреплением , которые соответствует накоплению опыта у игроков-людей. Это позволяет современным программам исследовать некоторые линии гораздо глубже, чем другие, используя прямое сокращение и другие выборочные эвристики, чтобы просто не учитывать ходы, которые программа считает плохими с помощью своей функции оценки, так же, как это делают игроки-люди. Единственное фундаментальное различие между компьютерной программой и человеком в этом смысле заключается в том, что компьютерная программа может искать гораздо глубже, чем человек-игрок, что позволяет ей искать больше узлов и обходить эффект горизонта в гораздо большей степени, чем это возможно с человеком. игроки.

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

Компьютерные шахматные программы обычно поддерживают ряд общих стандартов де-факто . Почти все современные программы могут читать и записывать игровые ходы в виде переносимой игровой нотации (PGN), а также могут читать и записывать отдельные позиции в виде нотации Форсайта-Эдвардса (FEN). Старые шахматные программы часто понимали только длинные алгебраические записи , но сегодня пользователи ожидают, что шахматные программы будут понимать стандартные алгебраические шахматные записи .

Начиная с конца 1990-х годов, программисты начали разрабатывать отдельные движкиинтерфейсом командной строки, который вычисляет, какие ходы являются самыми сильными в позиции) или графический пользовательский интерфейс (GUI), который предоставляет игроку шахматную доску, которую он может видеть, и фигуры. что можно двигать. Двигатели сообщают свои ходы графическому интерфейсу, используя такой протокол, как протокол связи Chess Engine (CECP) или универсальный шахматный интерфейс (UCI). Разделив шахматные программы на эти две части, разработчики могут писать только пользовательский интерфейс или только движок, без необходимости писать обе части программы. (См. также шахматный движок .)

Разработчики должны решить, подключать ли движок к вводной книге и/или таблицам эндшпиля или оставить это на усмотрение графического интерфейса.

Представительства в совете директоров

Структура данных, используемая для представления каждой шахматной позиции, является ключом к производительности генерации ходов и оценки позиции . Методы включают элементы, хранящиеся в массиве («почтовый ящик» и «0x88»), позиции элементов, хранящиеся в списке («список элементов»), наборы наборов битов для местоположений элементов (« битовые доски ») и кодированные позиции Хаффмана для компактного хранения. длительное хранение.

Методы поиска

Компьютерные шахматные программы рассматривают шахматные ходы как игровое дерево . Теоретически они изучают все ходы, затем все ходы, противодействующие этим ходам, затем все ходы, противодействующие им, и так далее, где каждый отдельный ход одного игрока называется « слоем ». Эта оценка продолжается до тех пор, пока не будет достигнута определенная максимальная глубина поиска или программа не определит, что достигнута окончательная позиция "листья" (например, мат).

Минимаксный поиск

Одним из конкретных типов алгоритмов поиска, используемых в компьютерных шахматах, являются алгоритмы минимаксного поиска, в которых на каждом этапе выбирается «лучший» ход игрока; один игрок пытается максимизировать счет, другой - минимизировать его. С помощью этого чередующегося процесса будет достигнут один конкретный конечный узел, оценка которого представляет искомое значение позиции. Его значение резервируется до корня, и эта оценка становится оценкой позиции на доске. Этот поисковый процесс называется минимаксным.

Наивная реализация минимаксного алгоритма может выполнять поиск только на небольшую глубину за практический промежуток времени, поэтому были разработаны различные методы, значительно ускоряющие поиск хороших ходов. Альфа-бета-обрезка , система определения верхних и нижних границ возможных результатов поиска и поиска до тех пор, пока границы не совпадут, обычно используется для уменьшения пространства поиска в программе.

Кроме того, также используются различные эвристики выборочного поиска, такие как поиск в состоянии покоя , прямое сокращение, расширение поиска и сокращение поиска. Эти эвристики запускаются на основе определенных условий в попытке отсеять явно плохие ходы (исторические ходы) или исследовать интересные узлы (например, проверить расширения, проходные пешки на седьмой горизонтали и т. д.). Однако эти эвристики выборочного поиска следует использовать очень осторожно. Перерасход и программа тратит слишком много времени на просмотр неинтересных позиций. Если обрезать или уменьшить слишком много, есть риск вырезать интересные узлы.

Поиск дерева Монте-Карло

Поиск по дереву Монте-Карло (MCTS) — это эвристический алгоритм поиска, который расширяет дерево поиска на основе случайной выборки пространства поиска. Вариантом поиска по дереву Монте-Карло, обычно используемым в компьютерных шахматах, является PUCT , предиктор и верхние доверительные границы, применяемые к деревьям .

AlphaZero и Leela Chess Zero от DeepMind используют MCTS вместо минимакса. Такие механизмы используют пакетную обработку на графических процессорах для расчета своих функций оценки и политики (выбора хода) и, следовательно, требуют алгоритма параллельного поиска, поскольку вычисления на графическом процессоре по своей сути параллельны. Алгоритмы минимаксного и альфа-бета-отсечения, используемые в компьютерных шахматах, по своей сути являются последовательными алгоритмами, поэтому они не будут хорошо работать с пакетной обработкой на графическом процессоре. С другой стороны, MCTS является хорошей альтернативой, потому что случайная выборка, используемая в поиске по дереву Монте-Карло, хорошо подходит для параллельных вычислений, и именно поэтому почти все механизмы, поддерживающие вычисления на графическом процессоре, используют MCTS вместо альфа-бета.

Другие оптимизации

Можно использовать множество других оптимизаций, чтобы сделать программы для игры в шахматы сильнее. Например, таблицы транспонирования используются для записи позиций, которые были оценены ранее, чтобы сохранить их пересчет. В таблицах опровержений записаны ключевые ходы, которые «опровергают» то, что кажется хорошим ходом; обычно сначала их пробуют в различных позициях (поскольку ход, опровергающий одну позицию, может опровергнуть другую). Недостатком является то, что таблицы транспонирования на большой глубине слоя могут быть довольно большими — от десятков до сотен миллионов записей. Таблица транспонирования IBM Deep Blue в 1996 году, например, содержала 500 миллионов записей. Слишком маленькие таблицы транспонирования могут привести к тому, что на поиск несуществующих записей будет потрачено больше времени из-за обмолота, чем время, сэкономленное найденными записями. Многие шахматные движки используют обдумывание , поиск более глубоких уровней во времени противника, подобно людям, чтобы увеличить свою игровую силу.

Конечно, более быстрое оборудование и дополнительная память могут повысить игровую мощь шахматной программы. Архитектуры с гиперпоточностью могут незначительно повысить производительность, если программа работает на одном ядре или на небольшом количестве ядер. Большинство современных программ предназначены для использования нескольких ядер для параллельного поиска. Другие программы предназначены для работы на компьютере общего назначения и распределения генерации перемещений, параллельного поиска или оценки на выделенных процессорах или специализированных сопроцессорах.

История

Первая статья о поиске была написана Клодом Шенноном в 1950 году. Он предсказал две основные возможные стратегии поиска, которые он назвал «Тип A» и «Тип B», прежде чем кто-либо запрограммировал компьютер для игры в шахматы.

Программы типа А будут использовать подход « грубой силы », проверяя каждую возможную позицию за фиксированное количество ходов с использованием чисто наивного минимаксного алгоритма . Шеннон считал, что это будет непрактично по двум причинам.

Во-первых, учитывая примерно тридцать возможных ходов в типичной реальной позиции, он ожидал, что поиск приблизительно 10 9 позиций, связанных с просмотром на три хода вперед для обеих сторон (шесть слоев ), займет около шестнадцати минут, даже в «очень оптимистичном» положении. Дело в том, что шахматный компьютер оценивал миллион позиций каждую секунду. (Чтобы достичь такой скорости, потребовалось около сорока лет. Более поздний алгоритм поиска под названием альфа-бета-обрезка , система определения верхних и нижних границ возможных результатов поиска и поиска до совпадения границ, логарифмически уменьшал коэффициент ветвления игрового дерева, но в то время шахматные программы все еще не могли использовать экспоненциальный рост дерева.

Во-вторых, он игнорировал проблему покоя, пытаясь оценить только позицию, которая находится в конце обмена фигурами или другой важной последовательности ходов («линий»). Он ожидал, что адаптация минимакса для решения этой проблемы значительно увеличит количество позиций, которые необходимо просмотреть, и еще больше замедлит работу программы. Он ожидал, что адаптация типа А для решения этой проблемы значительно увеличит количество позиций, которые необходимо просмотреть, и еще больше замедлит программу.

Это естественным образом привело к так называемому «выборочному поиску» или «поиску типа B», когда с использованием шахматных знаний (эвристики) для выбора нескольких предположительно хороших ходов из каждой позиции для поиска и удаления других без поиска. Вместо того, чтобы тратить вычислительную мощность на проверку плохих или тривиальных ходов, Шеннон предложил использовать в программах типа B два улучшения:

  1. Используйте поиск покоя .
  2. Используйте обрезку вперед; т.е. посмотрите только на несколько хороших ходов для каждой позиции.

Это позволило бы им заглянуть дальше («глубже») в наиболее важные строки за разумное время.

Однако ранние попытки выборочного поиска часто приводили к тому, что лучший ход или ходы отбрасывались. В результате в течение следующих 25 лет преобладала эта первая итерация парадигмы выборочного поиска. Лучшей программой, выпущенной в этот ранний период, была Mac Hack VI в 1967 году; он играл примерно на том же уровне, что и средний любитель (класс C по рейтинговой шкале Шахматной федерации США).

Тем временем аппаратное обеспечение продолжало совершенствоваться, и в 1974 году поиск методом грубой силы был впервые реализован в программе Northwestern University Chess 4.0. В этом подходе просматриваются все альтернативные ходы в узле, и ни один из них не удаляется. Они обнаружили, что время, необходимое для простого поиска всех ходов, было намного меньше, чем время, необходимое для применения эвристики, требующей больших знаний, для выбора лишь нескольких из них, а преимущество отсутствия преждевременного или непреднамеренного удаления хороших ходов привело к значительно более высокой производительности. .

В 1980-х и 1990-х годах наконец был достигнут прогресс в парадигме выборочного поиска с развитием поиска покоя , сокращения нулевых ходов и других современных эвристик выборочного поиска. В этих эвристиках было гораздо меньше ошибок, чем в более ранних эвристиках, и было обнаружено, что они стоят дополнительного времени, которое они сэкономили, потому что они могут выполнять более глубокий поиск и широко используются многими поисковыми системами. Хотя многие современные программы используют альфа-бета-поиск в качестве основы для своего алгоритма поиска, эти дополнительные эвристики выборочного поиска, используемые в современных программах, означают, что программа больше не выполняет поиск методом «грубой силы». Вместо этого они в значительной степени полагаются на эти эвристики выборочного поиска для расширения строк, которые программа считает хорошими, и сокращения и сокращения строк, которые программа считает плохими, до такой степени, что большинство узлов в дереве поиска обрезается, что позволяет современным программам выполнять очень глубокий поиск.

В 2006 году Реми Кулом создал поиск по дереву Монте-Карло , еще один вид выборочного поиска типа B. В 2007 году Левенте Кочиш и Чаба Сепешвари создали адаптацию поиска по дереву Монте-Карло под названием «Верхние границы достоверности, применяемые к деревьям» или сокращенно UCT. В 2011 году Крис Розин разработал вариант UCT под названием Predictor + Upper Confidence bounds, примененный к деревьям, или сокращенно PUCT. Затем PUCT использовался в AlphaZero в 2017 году, а затем в Leela Chess Zero в 2018 году.

Знание против поиска (скорость процессора)

В 1970-х годах большинство шахматных программ работали на суперкомпьютерах, таких как Control Data Cyber ​​176 или Cray-1, что свидетельствует о том, что в тот период развития компьютерных шахмат вычислительная мощность была ограничивающим фактором производительности. Большинство шахматных программ с трудом выполняли поиск на глубину более 3 слоев. Только после аппаратных шахматных машин 1980-х годов связь между скоростью процессора и знаниями, закодированными в функции оценки, стала очевидной.

Было подсчитано, что удвоение скорости компьютера увеличивает игровую силу от пятидесяти до семидесяти очков Эло ( Levy & Newborn 1991 :192).

Оценка листьев

Для большинства шахматных позиций компьютеры не могут предвидеть все возможные финальные позиции. Вместо этого они должны заглянуть на несколько слоев вперед и сравнить возможные позиции, известные как листья. Алгоритм, который оценивает листья, называется « функцией оценки », и эти алгоритмы часто сильно различаются в разных шахматных программах. Функции оценки обычно оценивают позиции в сотых долях пешки (называемой сантипешкой), где по соглашению положительная оценка благоприятствует белым, а отрицательная оценка благоприятствует черным. Однако некоторые функции оценки выводят проценты выигрыша/ничьи/проигрыша вместо сантипешек.

Исторически сложилось так, что созданные вручную функции оценки учитывают материальную ценность наряду с другими факторами, влияющими на силу каждой стороны. При подсчете материала для каждой стороны типичными значениями фигур являются 1 очко за пешку , 3 очка за коня или слона , 5 очков за ладью и 9 очков за ферзя . (См . Относительная ценность шахматной фигуры .) Королю иногда присваивается произвольно высокое значение, например 200 очков ( статья Шеннона ), чтобы гарантировать, что мат перевешивает все другие факторы ( Леви и Ньюборн 1991 : 45). В дополнение к очкам за фигуры большинство созданных вручную функций оценки учитывают многие факторы, такие как структура пешек, тот факт, что пара слонов обычно стоит больше, централизованные фигуры стоят больше и так далее. Обычно учитывается защита королей, а также фаза игры (дебют, миттельшпиль или эндшпиль). Методы машинного обучения , такие как поворот Texel, стохастический градиентный спуск или обучение с подкреплением , обычно используются для оптимизации функций оценки, созданных вручную.

Большинство современных функций оценки используют нейронные сети . Наиболее распространенная функция оценки, используемая сегодня, — это эффективно обновляемая нейронная сеть , представляющая собой неглубокую нейронную сеть, входными данными которой являются таблицы «кусок-квадрат » . Таблицы «кусок-квадраты» представляют собой набор из 64 значений, соответствующих клеткам шахматной доски, и обычно существует таблица «кусок-квадратов» для каждой фигуры и цвета, в результате чего получается 12 таблиц «кусок-квадратов» и, таким образом, 768 входных данных в нейронную сеть. Кроме того, некоторые движки используют в своей функции оценки глубокие нейронные сети . Нейронные сети обычно обучаются с использованием некоторого алгоритма обучения с подкреплением в сочетании с обучением с учителем или обучением без учителя .

Результатом функции оценки является один скаляр, выраженный в сантипешках или других единицах измерения, который, в случае созданных вручную функций оценки, представляет собой взвешенную сумму различных описанных факторов, а в случае функций оценки, основанных на нейронных сетях, выход головы нейросети. Оценка предположительно представляет или аппроксимирует значение поддерева под оцениваемым узлом, как если бы поиск был произведен до конца, т. е. до конца игры. Во время поиска оценка сравнивается с оценками других листьев, исключая узлы, которые представляют плохие или плохие ходы для любой стороны, чтобы получить узел, который путем сходимости представляет значение позиции с лучшей игрой для обеих сторон.

Столы эндшпиля

Игра в эндшпиле долгое время была одной из самых слабых сторон шахматных программ из-за необходимой глубины поиска. Некоторые программы уровня мастера не могли выиграть в позициях, в которых даже игроки среднего уровня могли добиться победы.

Чтобы решить эту проблему, компьютеры использовались для полного анализа некоторых шахматных эндшпильных позиций, начиная с короля и пешки против короля. Такие базы таблиц эндшпиля генерируются заранее с использованием формы ретроградного анализа , начиная с позиций, где конечный результат известен (например, где одна сторона получила мат), и выявляя, какие другие позиции находятся на расстоянии одного хода от них, а какие — на один ход. от тех и т.д. Кен Томпсон был пионером в этой области.

Результаты компьютерного анализа иногда удивляли людей. В 1977 году шахматная машина Belle Томпсона использовала базу таблицы эндшпиля для короля и ладьи против короля и ферзя и смогла нарисовать этот теоретически проигранный эндшпиль против нескольких мастеров (см. Положение Филидора # Ферзь против ладьи ). И это несмотря на то, что он не следовал обычной стратегии отсрочить поражение, удерживая защищающегося короля и ладью как можно дольше. На просьбу объяснить причины некоторых ходов программы Томпсон не смог этого сделать, заявив, что база данных программы просто возвращает лучшие ходы.

Большинство гроссмейстеров отказались играть против компьютера в эндшпиле ферзь против ладьи, но Уолтер Браун принял вызов. Была создана позиция ферзя против ладьи, в которой ферзь может выиграть за тридцать ходов при идеальной игре. Брауну было дано 2,5 часа на то, чтобы сыграть пятьдесят ходов, в противном случае по правилу пятидесяти ходов требовалась бы ничья . После сорока пяти ходов Браун согласился на ничью, так как не смог поставить мат или выиграть ладью в течение следующих пяти ходов. В финальной позиции Брауну оставалось еще семнадцать ходов до мата, но не так уж и далеко до выигрыша ладьи. Браун изучил эндшпиль и через неделю снова сыграл на компьютере в другой позиции, в которой ферзь может выиграть за тридцать ходов. На этот раз он взял ладью на пятидесятом ходу, что дало ему выигрышную позицию ( Levy & Newborn 1991 : 144–48), ( Nunn 2002 : 49).

В других позициях, которые долгое время считались выигранными, оказалось, что для реальной победы требуется больше ходов против идеальной игры, чем позволяет шахматное правило пятидесяти ходов. Как следствие, в течение нескольких лет официальные правила шахмат ФИДЕ были изменены, чтобы увеличить количество ходов, разрешенных в этих окончаниях. Через некоторое время правило вернулось к пятидесяти ходам во всех позициях - таких позиций было обнаружено больше, что еще больше усложнило правило, и это не имело никакого значения для игры людей, поскольку они не могли идеально играть позиции.

За прошедшие годы были выпущены другие форматы баз данных для эндшпиля , включая базу данных Эдварда, базу данных Де Конинга и базу данных Налимова , которая используется многими шахматными программами, такими как Rybka , Shredder и Fritz . Доступны основания стола для всех позиций с шестью частями. Некоторые семифигурные эндшпили были проанализированы Марком Бурзучки и Яковом Коновалем. Программисты, использующие суперкомпьютеры «Ломоносов» в Москве, создали базу шахматных таблиц для всех эндшпилей с семью фигурами или меньше (исключая тривиальные позиции эндшпиля, такие как шесть белых фигур против одинокого черного короля ). Во всех этих базах данных эндшпиля предполагается, что рокировка больше невозможна.

Многие базы таблиц не учитывают правило пятидесяти ходов, согласно которому игра, в которой пятьдесят ходов проходят без взятия или хода пешки, может быть объявлена ​​ничьей любым игроком. Это приводит к тому, что база таблиц возвращает такие результаты, как «Принудительный мат за шестьдесят шесть ходов» в некоторых позициях, которые на самом деле были бы нарисованы из-за правила пятидесяти ходов. Одна из причин этого заключается в том, что если правила игры в шахматы будут изменены еще раз, давая больше времени для победы в таких позициях, не будет необходимости регенерировать все базы таблиц. Программе, использующей базы таблиц, также очень легко заметить и принять во внимание эту «особенность», и в любом случае, если при использовании базы таблиц эндшпиля будет выбран ход, который приведет к быстрейшему выигрышу (даже если он не соответствует пятидесяти -правило хода с идеальной игрой). При игре с противником, не использующим настольную базу, такой выбор даст хорошие шансы на победу в течение пятидесяти ходов.

Базы таблиц Налимова, в которых используются самые современные методы сжатия , требуют 7,05 ГБ места на жестком диске для всех концовок из пяти частей. Для покрытия всех концовок из шести частей требуется примерно 1,2 ТБ . Подсчитано, что для таблицы из семи частей требуется от 50 до 200 ТБ дискового пространства.

Базы данных об эндшпилях были широко представлены в 1999 году, когда Каспаров провел в Интернете показательный матч против остального мира . Был достигнут эндшпиль из семи фигур с ферзем и пешкой , и мировая команда боролась за спасение ничьей. Евгений Налимов помог, создав базу финальной таблицы из шести фигур, в которой у обеих сторон было по две королевы, что активно использовалось для облегчения анализа обеими сторонами.

Открытие книги

Шахматные движки, как и люди, могут экономить время обработки, а также выбирать сильные варианты, изложенные мастерами, ссылаясь на дебютную книгу , хранящуюся в базе данных на диске. Начальные книги охватывают начальные ходы игры с различной глубиной, в зависимости от дебюта и вариации, но обычно до первых 10-12 ходов (20-24 слоя). Поскольку дебюты тщательно изучались мастерами на протяжении столетий, а некоторые из них, как известно, хорошо используются в миттельшпиле, оценки конкретных вариантов мастерами обычно будут выше общей эвристики программы.

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

Рейтинговые списки компьютерных шахмат

CEGT , CSS, SSDF , WBEC, REBEL , FGRL и IPON поддерживают рейтинговые списки, позволяющие фанатам сравнивать мощность двигателей. Различные версии Stockfish , Komodo , Leela Chess Zero и Fat Fritz доминируют в рейтинговых списках начала 2020-х годов.

CCRL (Computer Chess Rating Lists) — это организация, которая проверяет силу компьютерных шахматных движков , играя программы друг против друга. CCRL была основана в 2006 году для продвижения конкуренции между компьютерами и составления таблиц результатов в рейтинговом списке.

Организация использует три разных списка: 40/40 (40 минут на каждые 40 сыгранных ходов), 40/4 (4 минуты на каждые 40 сыгранных ходов) и 40/4 FRC (тот же контроль времени, но Chess960). Обдумывание (или постоянный мозг ) отключено, а синхронизация настроена на процессор AMD64 X2 4600+ (2,4 ГГц) с использованием Crafty 19.17 BH в качестве эталона. Общие, нейтральные вводные книги используются (в отличие от собственной книги движка) до 12 ходов в игре вместе с 4 или 5 настольными базами .

История

Докомпьютерный век

Идея создания шахматной машины восходит к восемнадцатому веку. Около 1769 года шахматный автомат под названием «Турок », созданный венгерским изобретателем Фаркашем Кемпеленом , прославился до того, как был разоблачен как розыгрыш. До появления цифровых вычислений серьезные испытания, основанные на автоматах, таких как El Ajedrecista 1912 года, в которых игралась концовка «король и ладья против короля», были слишком сложными и ограниченными, чтобы их можно было использовать для полноценной игры в шахматы. Область исследований механических шахмат зачахла до появления цифрового компьютера в 1950-х годах.

Ранний век программного обеспечения: выборочный поиск

С тех пор шахматные энтузиасты и инженеры-компьютерщики со все возрастающей степенью серьезности и успеха создавали шахматные машины и компьютерные программы. Одним из немногих шахматных гроссмейстеров, серьезно посвятивших себя компьютерным шахматам, был бывший чемпион мира по шахматам Михаил Ботвинник , написавший на эту тему несколько работ. Он также имел докторскую степень в области электротехники. Работая с относительно примитивным оборудованием, доступным в Советском Союзе в начале 1960-х, у Ботвинника не было другого выбора, кроме как исследовать программные методы выбора ходов; в то время только самые мощные компьютеры могли добиться большего, чем трехслойный поиск по всей ширине, а у Ботвинника таких машин не было. В 1965 году Ботвинник был консультантом команды ИТЭФ в американо-советском компьютерном шахматном матче (см. Коток-Маккарти ).

Более поздний век программного обеспечения: поиск по всей ширине

Одна веха в развитии произошла, когда команда из Северо-Западного университета , которая отвечала за серию программ Chess и выиграла первые три чемпионата ACM по компьютерным шахматам (1970–72), отказалась от поиска типа B в 1973 году. Получившаяся программа Chess 4.0 выиграла. чемпионат того года и его преемники заняли второе место как в чемпионате ACM 1974 года, так и в первом чемпионате мира по компьютерным шахматам в том же году , прежде чем снова выиграть чемпионат ACM в 1975, 1976 и 1977 годах. Реализация типа A оказалась такой же быстро: за то время, которое раньше требовалось, чтобы решить, какие ходы достойны поиска, можно было просто обыскать их все. Фактически, Chess 4.0 задала парадигму, которой следовали и до сих пор придерживаются все современные шахматные программы.

Расцвет шахматных машин

В 1978 году ранняя версия аппаратной шахматной машины Кена Томпсона Belle участвовала в чемпионате Северной Америки по компьютерным шахматам и выиграла его, победив доминирующую версию Northwestern University Chess 4.7.

Микрокомпьютерная революция

Технологический прогресс на несколько порядков в вычислительной мощности сделал подход грубой силы гораздо более острым, чем это было в первые годы. В результате очень надежный тактический игрок с искусственным интеллектом, которому помогают некоторые ограниченные знания о позициях, встроенные в функцию оценки и правила сокращения/расширения, начал соответствовать лучшим игрокам в мире. Оказалось, что для достижения отличных результатов, по крайней мере в области шахмат, компьютеры должны делать то, что они умеют лучше всего (вычислять), а не уговаривать их имитировать мыслительные процессы и знания человека. В 1997 году Deep Blue , машина грубой силы, способная проверять 500 миллионов узлов в секунду, победила чемпиона мира Гарри Каспарова, что стало первым случаем, когда компьютер победил действующего чемпиона мира по шахматам со стандартным контролем времени.

Сверхчеловеческие шахматы

В 2016 году NPR попросило экспертов охарактеризовать стиль игры компьютерных шахматных движков. Мюррей Кэмпбелл из IBM заявил, что «Компьютеры не имеют никакого чувства эстетики ... Они играют то, что считают объективно лучшим ходом в любой позиции, даже если это выглядит абсурдно, и они могут сыграть любой ход, каким бы уродливым он ни был. является." Гроссмейстеры Эндрю Солтис и Сьюзен Полгар заявили, что компьютеры с большей вероятностью отступят, чем люди.

Революция в нейронных сетях

Хотя нейронные сети использовались в функциях оценки шахматных движков с конца 1980-х годов, в таких программах, как NeuroChess, Morph, Blondie25, Giraffe, AlphaZero и MuZero , нейронные сети не получили широкого распространения в шахматных движках до появления эффективных обновляемые нейронные сети летом 2020 года. Эффективно обновляемые нейронные сети были первоначально разработаны Ю Насу в компьютерных сёги в 2018 году, и 31 мая 2020 года их нужно было сначала портировать на производную от Stockfish под названием Stockfish NNUE и интегрировать в официальный Stockfish. движок 6 августа 2020 года, до того, как другие шахматные программисты начали внедрять нейронные сети в свои движки.

Некоторые люди, такие как Венки Рамакришнан из Королевского общества , считают, что AlphaZero привела к широкому распространению нейронных сетей в шахматных движках. Тем не менее, AlphaZero повлияла на очень немногие движки, которые начали использовать нейронные сети, и это, как правило, были новые экспериментальные движки, такие как Leela Chess Zero , которые начали специально копировать работу AlphaZero. Глубокие нейронные сети, используемые в функции оценки AlphaZero, требовали дорогостоящих графических процессоров , несовместимых с существующими шахматными движками. Подавляющее большинство шахматных движков используют только центральные процессоры , а для вычисления и обработки информации на графических процессорах требуются специальные библиотеки в бэкенде, такие как CUDA от Nvidia , к которым ни один из движков не имел доступа. Таким образом, подавляющее большинство шахматных движков, таких как Komodo и Stockfish , продолжали использовать созданные вручную функции оценки до тех пор, пока в 2020 году эффективно обновляемые нейронные сети не были перенесены в компьютерные шахматы, что вообще не требовало использования графических процессоров или библиотек, таких как CUDA. Даже в этом случае нейронные сети, используемые в компьютерных шахматах, довольно неглубокие, а методы глубокого обучения с подкреплением , впервые предложенные AlphaZero, по-прежнему чрезвычайно редки в компьютерных шахматах.

График

  • 1769 — Вольфганг фон Кемпелен строит турок . Представленный как играющий в шахматы автомат, им тайно управляет игрок-человек, спрятанный внутри машины.
  • 1868 г. - Чарльз Хупер представляет автомат Аджиба , внутри которого также спрятан человек-шахматист.
  • 1912 - Леонардо Торрес-и-Кеведо строит El Ajedrecista , машину, которая может играть в эндшпиле король и ладья против короля .
  • 1941 - Конрад Цузе , опередив аналогичную работу как минимум на десять лет, разрабатывает алгоритмы компьютерных шахмат в своем формализме программирования Планкалкюль . Однако из-за обстоятельств Второй мировой войны они не публиковались и не появлялись до 1970-х годов.
  • 1948 — В книге Норберта Винера « Кибернетика » описывается, как можно разработать шахматную программу с использованием минимаксного поиска с ограниченной глубиной и оценочной функцией .
  • 1950 - Клод Шеннон публикует «Программирование компьютера для игры в шахматы», одну из первых статей об алгоритмических методах компьютерных шахмат.
  • 1951 - Алан Тьюринг впервые опубликовал программу, разработанную на бумаге, которая была способна вести полную партию в шахматы (получившую название Turochamp ).
  • 1952 – Дитрих Принц разрабатывает программу для решения шахматных задач.
а б с г е ф
6 а6 черная ладья b6 черный конь с6 черный ферзь d6 черный король e6 черный конь f6 черная ладья 6
5 а5 черная пешка b5 черная пешка с5 черная пешка d5 черная пешка e5 черная пешка f5 черная пешка 5
4 а4 b4 с4 d4 e4 f4 4
3 а3 б3 с3 d3 e3 f3 3
2 а2 белая пешка b2 белая пешка c2 белая пешка d2 белая пешка e2 белая пешка f2 белая пешка 2
1 a1 белая ладья b1 белый конь c1 белый ферзь d1 белый король e1 белый конь f1 белая ладья 1
а б с г е ф
Лос-Аламосские шахматы . В эту упрощенную версию шахмат в 1956 году игралкомпьютер MANIAC I.
  • 1956 — Лос-Аламосские шахматы — первая программа для игры в шахматы, разработанная Полом Стейном и Марком Уэллсом для компьютера MANIAC I.
  • 1956 - Джон Маккарти изобретает алгоритм поиска альфа-бета .
  • 1957 - Разработаны первые программы, которые могут играть в полноценную шахматную партию, одна Алексом Бернштейном, а другая русскими программистами с использованием БЭСМ .
  • 1958 - NSS становится первой шахматной программой, использующей алгоритм поиска альфа-бета.
  • 1962 — В Массачусетском технологическом институте опубликована первая программа, которая заслуживает доверия, Kotok-McCarthy .
  • 1963 г. - гроссмейстер Давид Бронштейн побеждает М-20 , выполняющую раннюю шахматную программу.
  • 1966–67 — Сыгран первый шахматный матч между компьютерными программами. Московский институт теоретической и экспериментальной физики (ИТЭФ) побеждает Коток-Маккарти в Стэнфордском университете по телеграфу в течение девяти месяцев.
  • 1967 — Mac Hack VI , Ричард Гринблатт и др. вводит таблицы транспонирования и использует десятки тщательно настроенных эвристик выбора ходов; это становится первой программой, победившей человека в турнирной игре. Mac Hack VI играл примерно на уровне C-класса.
  • 1968 - Чемпион Шотландии по шахматам Дэвид Леви заключает пари на 500 фунтов с пионерами искусственного интеллекта Джоном Маккарти и Дональдом Мичи , что ни одна компьютерная программа не выиграет у него шахматный матч в течение 10 лет.
  • 1970 - Монти Ньюборн и Ассоциация вычислительной техники организуют первый Североамериканский чемпионат по компьютерным шахматам в Нью-Йорке.
  • 1971 — Кен Томпсон , американский ученый-компьютерщик из Bell Labs и создатель операционной системы Unix, пишет свою первую программу для игры в шахматы под названием «chess» для самой ранней версии Unix .
  • 1974 — Дэвид Леви , Бен Миттман и Монти Ньюборн организуют первый чемпионат мира по компьютерным шахматам , который выигрывает русская программа « Каисса » .
  • 1975 - После почти десятилетия лишь незначительного прогресса с момента достижения высшей точки MacHack VI Гринблатта в 1967 году, представлен Northwestern University Chess 4.5 с поиском по всей ширине, нововведениями в виде битовых досок и итеративного углубления. Он также восстановил таблицу транспонирования, впервые представленную в программе Гринблатта. Таким образом, это была первая программа с интегрированной современной структурой, ставшая образцом для всех будущих разработок. Chess 4.5 играли сильно в классе B и в следующем году выиграли 3-й чемпионат мира по компьютерным шахматам. Шахматы Северо-Западного университета и их потомки доминировали в компьютерных шахматах до эры аппаратных шахматных машин в начале 1980-х годов.
  • 1976 — В декабре канадский программист Питер Р. Дженнингс выпускает Microchess , первую продаваемую игру для микрокомпьютеров.
Выпущенный в 1977 году, Борис был одним из первых шахматных компьютеров, получивших широкое распространение. Он работал на 8-битном микропроцессоре Fairchild F8 с 2,5 КБ ПЗУ и 256 байт ОЗУ.
  • 1977 — В марте Fidelity Electronics выпускает Chess Challenger , первый продаваемый шахматный компьютер. Международная ассоциация компьютерных шахмат основана шахматными программистами для организации чемпионатов по компьютерным шахматам и публикации отчетов об исследованиях и достижениях в области компьютерных шахмат в своем журнале. В том же году Applied Concepts выпустила Борис , специализированный шахматный компьютер в деревянном ящике с пластиковыми шахматными фигурами и складной доской.
  • 1978 - Дэвид Леви выигрывает пари, сделанное 10 лет назад, победив Chess 4.7 в матче из шести партий со счетом 4½–1½. Победа компьютера в четвертой игре — первое поражение мастера-человека в турнире.
  • 1979 - Фредерик Фридель организует матч между ММ Дэвидом Леви и Chess 4.8 , который транслируется по немецкому телевидению. Levy и Chess 4.8, работающие на CDC Cyber ​​176, самом мощном компьютере в мире, боролись с изнурительной ничьей из 89 ходов.
  • 1980 - Компьютеры Fidelity ежегодно выигрывают чемпионаты мира по микрокомпьютерам с 1980 по 1984 год. В Германии Hegener & Glaser выпускает свой первый специализированный шахматный компьютер Mephisto . USCF запрещает компьютерам участвовать в человеческих турнирах, за исключением случаев, когда их представляют создатели шахматных систем. Учреждена премия Фредкина, предлагающая 100 000 долларов создателю первой шахматной машины, победившей чемпиона мира по шахматам.
  • 1981 - Крей Блиц выигрывает чемпионат штата Миссисипи с идеальным счетом 5–0 и рейтингом производительности 2258. В 4-м раунде он побеждает Джо Сентефа (2262), становясь первым компьютером, победившим мастера в турнирной игре, и первым компьютером, получить мастер-рейтинг.
  • 1984 - Линия специализированных шахматных компьютеров Mephisto немецкой компании Hegener & Glaser начинает долгую серию побед (1984–1990) на чемпионате мира по микрокомпьютерам с использованием специализированных компьютеров, на которых работают программы ChessGenius и Rebel .
  • 1986 - Страна программного обеспечения (см. Software Toolworks ) выпустила Chessmaster 2000 на основе движка Дэвида Киттингера, первое издание того, что должно было стать самой продаваемой линейкой шахматных программ в мире.
  • 1987 — Фредерик Фридель и физик Матиас Вюлленвебер основали Chessbase , выпустив первую программу шахматной базы данных. Стюарт Кракрафт выпускает GNU Chess , один из первых « шахматных движков », в котором есть отдельный графический пользовательский интерфейс (GUI), chesstool.
  • 1988 — HiTech , разработанный Гансом Берлинером и Карлом Эбелингом , выигрывает матч у гроссмейстера Арнольда Денкера 3½–½. Deep Thought делит первое место с Тони Майлзом в чемпионате Software Toolworks Championship, опередив бывшего чемпиона мира Михаила Таля и нескольких гроссмейстеров, включая Самуэля Решевского , Уолтера Брауна и Михаила Гуревича . Он также побеждает гроссмейстера Бента Ларсена , что делает его первым компьютером, победившим гроссмейстера в турнире. Его рейтинг за выступление в этом турнире 2745 (по шкале USCF) был самым высоким, полученным компьютерным игроком.
  • 1989 - Deep Thought разгромил Дэвида Леви в матче из 4 игр со счетом 0–4, положив конец его знаменитой серии ставок, начавшейся в 1968 году.
  • 1990 - 25 апреля бывший чемпион мира Анатолий Карпов проиграл в сеансе одновременной игры шахматному компьютеру Hegener & Glaser Mephisto Portorose M68030.
  • 1991 - ChessMachine , основанная на книге Эда Шредера Rebel , выигрывает чемпионат мира по шахматам на микрокомпьютерах .
  • 1992 - ChessMachine выигрывает 7-й чемпионат мира по компьютерным шахматам , впервые микрокомпьютер победил мэйнфреймы . GM Джон Нанн выпускает «Секреты ладейных окончаний », первую книгу, основанную на таблицах эндшпиля, разработанных Кеном Томпсоном .
  • 1993 — Deep Thought-2 проигрывает матч из четырёх игр против Бента Ларсена . Шахматные программы, работающие на персональных компьютерах, превзошли специализированные шахматные компьютеры Мефисто и выиграли чемпионат микрокомпьютеров, ознаменовав переход от специализированного шахматного оборудования к программному обеспечению на многоцелевых персональных компьютерах.
  • 1995 - Fritz 3 , работающий на ПК Pentium с тактовой частотой 90 МГц, побеждает специальную шахматную машину Deep Thought-2 и программы, работающие на нескольких суперкомпьютерах, и выигрывает 8-й чемпионат мира по компьютерным шахматам в Гонконге. Это первый раз, когда шахматная программа, работающая на общедоступном оборудовании, побеждает специализированные шахматные машины и массивные суперкомпьютеры, что свидетельствует о смещении акцента с грубой вычислительной мощности на алгоритмические улучшения в эволюции шахматных движков.
  • 1996 — Deep Blue компании IBM проигрывает матч из шести игр Гарри Каспарову , 2–4.
  • 1997 — Deep(er) Blue , сильно модифицированная версия оригинала, выигрывает матч из шести игр против Гарри Каспарова , 3,5-2,5.
  • 2000 — Стефан Мейер-Кален и Рудольф Хубер разработали универсальный шахматный интерфейс , протокол для GUI для общения с движками, который постепенно станет основной формой, которую примут новые движки.
  • 2002 — Владимир Крамник сыграл вничью восьмиматчевый матч против Deep Fritz .
  • 2003 — Каспаров сыграл вничью матч из шести игр против Deep Junior и сыграл вничью матч из четырёх игр против X3D Fritz .
  • 2004 — команда компьютеров ( Hydra , Deep Junior и Fritz ) побеждает 8½–3½ против сильной человеческой команды, сформированной Веселином Топаловым , Русланом Пономарёвым и Сергеем Карякиным , имевшим средний рейтинг Эло 2681. Фабьен Летузи публикует исходный код для Fruit 2.1, движок, вполне конкурентоспособный с лучшими движками с закрытым исходным кодом того времени. Это заставляет многих авторов пересматривать свой код, включая новые идеи.
  • 2005 – Рыбка выигрывает турнир IPCCC и очень быстро после этого становится сильнейшим паровозом.
  • 2006 — Чемпион мира Владимир Крамник терпит поражение от Deep Fritz со счетом 4–2 .
  • 2009 — Карманный Фриц . 4, запущенный на смартфоне, выигрывает Copa Mercosur, международный турнир уровня мастеров, набрав 9½/10 баллов и заработав рейтинг производительности 2900. Группа российских программистов под псевдонимом публикует исходный код Ippolit, движка, который кажется более мощным, чем Rybka . Это становится основой для двигателей Робболито и Айвенго, и многие авторы двигателей перенимают идеи из него.
  • 2010 — Перед чемпионатом мира по шахматам 2010 Топалов готовится, сражаясь с суперкомпьютером Blue Gene с 8 192 процессорами, способными выполнять 500 триллионов (5 × 10 14 ) операций с плавающей запятой в секунду. Разработчик Рыбки Васик Райлич обвиняет Ипполита в том, что он клон Рыбки.
  • 2011 - ICGA лишает Рыбку титулов WCCC.
  • 2017 — AlphaZero , цифровой автомат на основе нейронной сети, побеждает Stockfish со счетом 28–0 при 72 ничьих в матче из 100 игр.
  • 2018 — Изобретена эффективно обновляемая нейронная сеть (NNUE) для оценки компьютерных сёги .
  • 2019 - Лила Chess Zero (LCZero v0.21.1-nT40.T8.610), шахматный движок, основанный на AlphaZero, побеждает Stockfish 19050918 в матче из 100 игр с окончательным счетом 53,5: 46,5 и выигрывает 15-й сезон TCEC .
  • 2020 - NNUE добавлен в оценку Stockfish , заметно повысив его силу.

Категории

Специальное оборудование

Эти шахматные игровые системы включают специальное оборудование с прибл. даты внедрения (за исключением специализированных микрокомпьютеров):

Коммерческие специализированные компьютеры

Борис Дипломат (1979) дорожный шахматный компьютер
Fidelity Voice Chess Challenger (1979), первый говорящий шахматный компьютер.
Речевой вывод из Voice Chess Challenger
Милтон Брэдли Гроссмейстер (1983), первый коммерческий самодвижущийся шахматный компьютер.
Novag Super Constellation (1984), известный своим человеческим стилем игры.
DGT Centaur (2019), современный шахматный компьютер на базе Stockfish , работающий на Raspberry Pi .

В конце 1970-х - начале 1990-х годов существовал конкурентный рынок специализированных шахматных компьютеров. Этот рынок изменился в середине 1990-х годов, когда компьютеры с выделенными процессорами больше не могли конкурировать с быстрыми процессорами в персональных компьютерах.

  • Борис в 1977 году и Борис Дипломат в 1979 году, шахматные компьютеры, включая фигуры и доску, проданные Applied Concepts Inc.
  • Chess Challenger, линейка шахматных компьютеров, продаваемых Fidelity Electronics с 1977 по 1992 год. Эти модели выиграли первые четыре чемпионата мира по шахматам среди микрокомпьютеров .
  • ChessMachine , специализированный компьютер на базе ARM , который может работать с двумя движками:
    • «Король», который позже стал движком Chessmaster , также использовался в специализированном компьютере TASC R30.
    • Gideon, версия Rebel , в 1992 году стал первым микрокомпьютером, выигравшим чемпионат мира по компьютерным шахматам .
  • Excalibur Electronics продает линейку силовых тренажеров для начинающих.
  • Mephisto — линейка шахматных компьютеров, продаваемых Hegener & Glaser. Эти устройства выиграли шесть чемпионатов мира по шахматам на микрокомпьютерах подряд .
  • Novag продала линейку тактически сильных компьютеров, включая бренды Constellation, Sapphire и Star Diamond.
  • Phoenix Chess Systems выпускает устройства ограниченным тиражом на базе процессоров StrongARM и XScale , работающих на современных движках и эмулирующих классические движки.
  • Saitek продает агрегаты средней мощности средней мощности. В 1994 году они выкупили Hegener & Glaser и ее бренд Mephisto.

В последнее время некоторые любители используют Multi Emulator Super System для запуска шахматных программ, созданных для компьютеров Fidelity или Hegener & Glaser's Mephisto, в современных 64-битных операционных системах, таких как Windows 10 . Автор Rebel Эд Шредер также адаптировал три из Hegener & Glaser Mephisto, которые он написал, для работы в качестве двигателей UCI.

DOS-программы

Эти программы можно запускать в MS-DOS, а также в 64-разрядной версии Windows 10 через эмуляторы, такие как DOSBox или Qemu :

Известные теоретики

Среди известных теоретиков компьютерных шахмат:

Решение шахмат

Перспективы полного решения шахмат обычно считаются довольно отдаленными. Широко распространено мнение, что не существует вычислительно недорогого метода решения шахмат даже в очень слабом смысле определения с уверенностью значения начальной позиции, и, следовательно, идея решения шахмат в более сильном смысле получения практически пригодного описания Стратегия идеальной игры для любой из сторон сегодня кажется нереалистичной. Тем не менее, не было доказано, что не существует дешевого в вычислительном отношении способа определения наилучшего хода в шахматной позиции, и даже того, что традиционный альфа-бета-поисковик , работающий на современном вычислительном оборудовании, не мог найти начальную позицию за приемлемое количество времени. время. Трудность доказательства последнего заключается в том, что, хотя количество позиций на доске, которые могут произойти в ходе шахматной партии, огромно (порядка не менее 10 43 на 10 47 ), трудно исключить с математической точностью вероятность того, что начальная позиция позволяет любой из сторон форсировать мат или тройное повторение после относительно небольшого количества ходов, и в этом случае дерево поиска может охватывать только очень небольшое подмножество множества возможных позиций. Было математически доказано, что обобщенные шахматы (шахматы, в которые играют произвольно большое количество фигур на произвольно большой шахматной доске) являются EXPTIME-полными , что означает, что определение выигравшей стороны в произвольной позиции обобщенных шахмат доказуемо занимает экспоненциальное время в худшем случае. ; однако этот теоретический результат не дает нижней границы объема работы, необходимой для решения обычных шахмат 8x8.

Мини-шахматы Мартина Гарднера , играемые на доске 5×5 с примерно 10 18 возможными позициями на доске, решены; его теоретико-игровое значение равно 1/2 (т. е. ничья может быть форсирована любой стороной), и описана стратегия форсирования для достижения этого результата.

Прогресс был достигнут и с другой стороны: по состоянию на 2012 год решены все эндшпили с 7 и менее фигурами (2 короля и до 5 других фигур).

Шахматные двигатели

«Шахматный движок» — это программное обеспечение, которое вычисляет и упорядочивает наиболее сильные ходы в данной позиции. Авторы движка сосредотачиваются на улучшении игры своих движков, часто просто импортируя движок в графический интерфейс пользователя (GUI), разработанный кем-то другим. Двигатели взаимодействуют с графическим интерфейсом с помощью стандартизированных протоколов, таких как широко распространенный в настоящее время универсальный шахматный интерфейс , разработанный Стефаном Мейер-Каленом и Францем Хубером. Есть и другие, такие как коммуникационный протокол Chess Engine, разработанный Тимом Манном для GNU Chess и Winboard . У Chessbase есть собственный проприетарный протокол, и когда-то в Millennium 2000 для ChessGenius использовался другой протокол . Движки, разработанные для одной операционной системы и протокола, могут быть перенесены на другие ОС или протоколы.

Шахматные движки регулярно соревнуются друг с другом на специальных турнирах по шахматным движкам .

Шахматные веб-приложения

В 1997 году Интернет-шахматный клуб выпустил свой первый Java-клиент для игры в шахматы онлайн против других людей в своем веб-браузере. Вероятно, это было одно из первых шахматных веб-приложений. Вскоре последовал Free Internet Chess Server с аналогичным клиентом. В 2004 году Международная шахматная федерация по переписке открыла веб-сервер, чтобы заменить свою систему электронной почты. Chess.com начал предлагать Live Chess в 2007 году. У Chessbase / Playchess уже давно есть загружаемый клиент, а в 2013 году был добавлен веб-клиент.

Еще одно популярное веб-приложение — обучение тактике. Ныне несуществующий сервер Chess Tactics открыл свой сайт в 2006 году, за ним в следующем году последовал Chesstempo, а Chess.com добавил свой Tactics Trainer в 2008 году. Chessbase добавила веб-приложение для обучения тактике в 2015 году.

Chessbase разместила свою базу данных шахматных игр в сети в 1998 году. Еще одной ранней базой данных шахматных игр была Chess Lab, которая была запущена в 1999 году. Первоначально New In Chess пыталась конкурировать с Chessbase , выпустив программу NICBase для Windows 3.x , но в конце концов решила отказаться от программного обеспечения и вместо этого сосредоточиться на своей онлайн-базе данных, начиная с 2002 года.

С 2006 года можно было играть против движка Shredder онлайн. В 2015 году Chessbase добавила веб-приложение play Fritz, а также My Games для хранения своих игр.

Начиная с 2007 года, Chess.com предлагал своим клиентам содержание учебной программы Chess Mentor в Интернете. Лучшие гроссмейстеры, такие как Сэм Шенкленд и Уолтер Браун , внесли свой вклад.

Смотрите также

Примечания

Рекомендации

Источники

дальнейшее чтение

Внешние ссылки

Средства массовой информации