Компьютерные шахматы включают в себя как аппаратное обеспечение (специализированные компьютеры), так и программное обеспечение, способное играть в шахматы . Компьютерные шахматы предоставляют игрокам возможность практиковаться даже при отсутствии человеческих противников, а также предоставляют возможности для анализа, развлечения и обучения. Компьютерные шахматные приложения, которые играют на уровне гроссмейстера или выше, доступны на оборудовании от суперкомпьютеров до смартфонов . Также доступны автономные машины для игры в шахматы. Stockfish , Leela Chess Zero , GNU Chess , Fruit и другие бесплатные приложения с открытым исходным кодом доступны для различных платформ.
Компьютерные шахматные приложения, реализованные в аппаратном или программном обеспечении, используют иные стратегии, чем люди, для выбора своих ходов: они используют эвристические методы для построения, поиска и оценки деревьев, представляющих последовательности ходов из текущей позиции, и пытаются выполнить лучшую такую последовательность во время игры. Такие деревья, как правило, довольно большие, от тысяч до миллионов узлов. Вычислительная скорость современных компьютеров, способных обрабатывать десятки тысяч до сотен тысяч узлов или более в секунду, наряду с эвристикой расширения и сокращения, которая сужает дерево до наиболее релевантных узлов, делает такой подход эффективным.
Первые шахматные машины, способные играть в шахматы или сокращенные шахматные игры, были программами, работающими на цифровых компьютерах в начале эпохи ламповых компьютеров (1950-е годы). Первые программы играли так плохо, что даже новичок мог их победить. Через 40 лет, в 1997 году, шахматные движки, работающие на суперкомпьютерах или специализированном оборудовании, были способны победить даже лучших игроков-людей . К 2006 году программы, работающие на настольных ПК, достигли тех же возможностей. В 2006 году Монти Ньюборн , профессор компьютерных наук в Университете Макгилла , заявил: «наука сделана». Тем не менее, решение шахмат в настоящее время невозможно для современных компьютеров из-за чрезвычайно большого количества возможных вариаций игры . [1]
Компьютерные шахматы когда-то считались « Дрозофилой ИИ», краем инженерии знаний . Теперь эта область считается научно завершенной парадигмой, а игра в шахматы — обыденной вычислительной деятельностью. [2]
Шахматные машины/программы доступны в нескольких различных формах: автономные шахматные машины (обычно микропроцессор, работающий с программной шахматной программой, но иногда как специализированная аппаратная машина), программы, работающие на стандартных ПК, веб-сайтах и приложениях для мобильных устройств. Программы работают на всем, от суперкомпьютеров до смартфонов. Требования к оборудованию для программ минимальны; приложения не превышают нескольких мегабайт на диске, используют несколько мегабайт памяти (но могут использовать гораздо больше, если она доступна), и любой процессор 300 МГц или выше будет достаточным. Производительность будет умеренно меняться в зависимости от скорости процессора, но достаточный объем памяти для хранения большой таблицы транспозиции (до нескольких гигабайт или более) важнее для силы игры, чем скорость процессора.
Большинство доступных коммерческих шахматных программ и машин могут играть на уровне супергроссмейстера (Эло 2700 или более) и использовать преимущества многоядерных и гиперпоточных архитектур ЦП. Лучшие программы, такие как Stockfish, превзошли даже игроков уровня чемпионов мира. Большинство шахматных программ включают в себя шахматный движок, подключенный к графическому интерфейсу, такому как Winboard или Chessbase . Сила игры, контроль времени и другие параметры, связанные с производительностью, настраиваются из графического интерфейса. Большинство графических интерфейсов также позволяют игроку устанавливать и редактировать позиции, отменять ходы, предлагать и принимать ничьи (и сдаваться), запрашивать и получать рекомендации по ходам, а также показывать анализ движка по ходу игры.
Существуют тысячи шахматных движков, таких как Sargon , IPPOLIT , Stockfish , Crafty , Fruit , Leela Chess Zero и GNU Chess , которые можно бесплатно загрузить (или получить исходный код иным способом) из Интернета .
Возможно, наиболее распространенным типом шахматного программного обеспечения являются программы, которые просто играют в шахматы. Игрок-человек делает ход на доске, ИИ рассчитывает и делает следующий ход, а человек и ИИ поочередно ходят, пока игра не закончится. Шахматный движок , который рассчитывает ходы, и графический пользовательский интерфейс (GUI) иногда являются отдельными программами. Различные движки могут быть подключены к GUI, что позволяет играть против разных стилей противника. Движки часто имеют простой текстовый интерфейс командной строки , в то время как GUI могут предлагать различные наборы фигур, стили доски или даже трехмерные или анимированные фигуры. Поскольку последние движки настолько эффективны, движки или GUI могут предлагать некоторый способ ограничения возможностей движка, чтобы улучшить шансы на победу игрока-человека. Движки универсального шахматного интерфейса (UCI), такие как Fritz или Rybka, могут иметь встроенный механизм для снижения рейтинга Эло движка (через параметры UCI uci_limitstrength и uci_elo). В некоторых версиях Fritz есть режимы Handicap и Fun для ограничения текущего движка или изменения процента ошибок, которые он совершает, или изменения его стиля. Fritz также имеет режим Friend, где во время игры он пытается соответствовать уровню игрока.
Базы данных шахмат позволяют пользователям искать в большой библиотеке исторических партий, анализировать их, проверять статистику и формулировать дебютный репертуар. Chessbase (для ПК) — это распространенная программа для этих целей среди профессиональных игроков, но существуют альтернативы, такие как Shane's Chess Information Database (Scid) [3] для Windows, Mac или Linux, Chess Assistant [4] для ПК, [5] Chess PGN Master Герхарда Калаба для Android [6] или Chess-Studio Джордано Виколи для iOS. [7]
Такие программы, как Playchess, позволяют игрокам играть друг с другом через Интернет.
Программы обучения шахматам обучают шахматам. Chessmaster провел обучающие курсы по игре от международного мастера Джоша Вайцкина и международного мастера Ларри Кристиансена . Стефан Майер-Кален предлагает Shredder Chess Tutor на основе учебников Step Роба Бруниа и Кора Ван Вейгердена. Компания Play Magnus бывшего чемпиона мира Магнуса Карлсена выпустила приложение Magnus Trainer для Android и iOS. Chessbase предлагает Fritz и Chesster для детей. Convekta предлагает большое количество обучающих приложений, таких как CT-ART и линейка Chess King, основанная на обучающих курсах международного мастера Александра Калинина и Максима Блоха.
Существует также программное обеспечение для решения шахматных задач .
После открытия скрининга опровержений — применения альфа-бета-отсечения для оптимизации оценки ходов — в 1957 году команда из Университета Карнеги-Меллона предсказала, что компьютер победит чемпиона мира среди людей к 1967 году. [8] Она не предвидела трудности определения правильного порядка оценки ходов. Исследователи работали над улучшением способности программ определять эвристики-убийцы , необычайно высокооцененные ходы для повторного изучения при оценке других ветвей, но в 1970-х годах большинство ведущих шахматистов считали, что компьютеры не скоро смогут играть на уровне мастера . [9] В 1968 году международный мастер Дэвид Леви заключил знаменитое пари , что ни один шахматный компьютер не сможет победить его в течение десяти лет, [10] а в 1976 году старший мастер и профессор психологии Элиот Херст из Университета Индианы написал, что «единственный способ, которым современная компьютерная программа могла бы когда-либо выиграть одну игру у мастера, — это если бы мастер, возможно, находясь в состоянии пьяного угара, играл 50 партий одновременно, и совершил какую-нибудь ошибку, которая случается раз в год». [9]
В конце 1970-х шахматные программы внезапно начали побеждать высококвалифицированных игроков-людей. [9] В год заявления Херста, Chess 4.5 Северо-Западного университета на уровне класса B чемпионата Америки по шахматам Пола Массона стала первой программой, выигравшей человеческий турнир. Леви выиграл свое пари в 1978 году, победив Chess 4.7 , но она добилась первой компьютерной победы над игроком класса Мастер на турнирном уровне, выиграв одну из шести игр. [10] В 1980 году Belle начала часто побеждать Мастеров. К 1982 году две программы играли на уровне Мастера, а три были немного слабее. [9]
Внезапное улучшение без теоретического прорыва было неожиданным, так как многие не ожидали, что способность Белль проверять 100 000 позиций в секунду — около восьми ходов — будет достаточной. Спраклены, создатели успешной микрокомпьютерной программы Sargon , подсчитали, что 90% улучшения произошло за счет более быстрой скорости оценки и только 10% — за счет улучшенных оценок. New Scientist в 1982 году заявил, что компьютеры «играют в ужасные шахматы... неуклюже, неэффективно, рассеянно и просто уродливо», но люди проигрывали им, делая «ужасные ошибки, поразительные упущения, непостижимые недосмотры, грубые просчеты и тому подобное» гораздо чаще, чем они осознавали; «короче говоря, компьютеры побеждают в первую очередь за счет своей способности находить и использовать просчеты в человеческих инициативах». [9]
К 1982 году программы для микрокомпьютеров могли оценивать до 1500 ходов в секунду и были такими же сильными, как программы для мэйнфреймов пятью годами ранее, способными победить большинство игроков-любителей. Хотя они могли смотреть вперед только на один или два хода больше, чем при своем дебюте в середине 1970-х годов, это улучшило их игру больше, чем ожидали эксперты; казалось бы, незначительные улучшения «похоже, позволили пересечь психологический порог, после которого становится доступен богатый урожай человеческих ошибок», — писал New Scientist . [9] При обзоре SPOC в 1984 году BYTE писал, что «компьютеры — мэйнфреймы, мини и микро — имеют тенденцию играть в уродливые, неэлегантные шахматы», но отметил утверждение Роберта Бирна о том, что «тактически они более свободны от ошибок, чем среднестатистический игрок-человек». Журнал описал SPOC как «современную шахматную программу» для IBM PC с «удивительно высоким» уровнем игры и оценил ее рейтинг USCF в 1700 (класс B). [11]
На чемпионате Северной Америки по компьютерным шахматам 1982 года Монро Ньюборн предсказал, что шахматная программа может стать чемпионом мира в течение пяти лет; директор турнира и международный мастер Майкл Вальво предсказал десять лет; Спраклены предсказали 15 лет; Кен Томпсон предсказал более 20 лет; а другие предсказывали, что этого никогда не произойдет. Однако наиболее распространенное мнение гласило, что это произойдет около 2000 года. [12] В 1989 году Леви был побежден Deep Thought в показательном матче. Однако Deep Thought все еще был значительно ниже уровня чемпионата мира, что продемонстрировал действующий чемпион мира Гарри Каспаров в двух убедительных победах в 1989 году. Только в матче 1996 года с IBM Deep Blue Каспаров проиграл свою первую игру компьютеру на турнирном контроле времени в Deep Blue против Каспарова, 1996, игра 1 . Эта игра была, по сути, первым случаем, когда действующий чемпион мира проиграл компьютеру, используя обычный контроль времени. Однако Каспаров перегруппировался, чтобы выиграть три и свести вничью две из оставшихся пяти партий матча, одержав убедительную победу.
В мае 1997 года обновленная версия Deep Blue победила Каспарова со счетом 3½–2½ в ответном матче. В 2003 году был снят документальный фильм, в основном посвященный противостоянию, под названием Game Over: Kasparov and the Machine .
С ростом вычислительной мощности и улучшением функций оценки шахматные программы, работающие на коммерческих рабочих станциях, начали конкурировать с игроками высшего класса. В 1998 году Rebel 10 победил Вишванатана Ананда , который в то время занимал второе место в мире, со счетом 5–3. Однако большинство этих игр не были сыграны с обычным контролем времени. Из восьми игр четыре были блиц- партиями (пять минут плюс пять секунд задержки Фишера на каждый ход); эти Rebel выиграл со счетом 3–1. Две были полублиц-партиями (пятнадцать минут для каждой стороны), которые Rebel также выиграл (1½–½). Наконец, две игры были сыграны как обычные турнирные партии (сорок ходов за два часа, один час внезапной смерти); здесь Ананд выиграл со счетом ½–1½. [13] В быстрых играх компьютеры играли лучше людей, но при классическом контроле времени — при котором определяется рейтинг игрока — преимущество было не таким явным.
В начале 2000-х годов коммерчески доступные программы, такие как Junior и Fritz, смогли провести матчи с бывшим чемпионом мира Гарри Каспаровым и чемпионом мира по классическому шахматам Владимиром Крамником .
В октябре 2002 года Владимир Крамник и Deep Fritz соревновались в матче из восьми игр Brains in Bahrain , который закончился вничью. Крамник выиграл партии 2 и 3 с помощью «традиционной» антикомпьютерной тактики — играть консервативно ради долгосрочного преимущества, которое компьютер не может увидеть в своем поиске по дереву игры . Однако Fritz выиграл партию 5 после серьезной ошибки Крамника. Партию 6 комментаторы турнира описали как «зрелищную». Крамник, находившийся в лучшей позиции в начале миттельшпиля , попытался пожертвовать фигуру, чтобы добиться сильной тактической атаки, стратегия, известная своей высокой степенью риска против компьютеров, которые сильнее всего защищаются от таких атак. Верный себе, Fritz нашел водонепроницаемую защиту, и атака Крамника иссякла, оставив его в плохой позиции. Крамник сдался, посчитав позицию проигранной. Однако послеигровой анализ человека и компьютера показал, что программа Fritz вряд ли смогла бы форсировать победу, и Крамник фактически пожертвовал ничейной позицией. Последние две партии были ничьими. Учитывая обстоятельства, большинство комментаторов по-прежнему оценивают Крамника как более сильного игрока в матче. [ необходима цитата ]
В январе 2003 года Каспаров играл с Junior , другой шахматной компьютерной программой, в Нью-Йорке. Матч закончился со счетом 3–3.
В ноябре 2003 года Каспаров играл с X3D Fritz . Матч закончился со счетом 2–2.
В 2005 году Hydra , специализированный шахматный компьютер с индивидуальным оборудованием и шестьюдесятью четырьмя процессорами, а также победитель 14-го IPCCC в 2005 году, победил занимавшего седьмое место Майкла Адамса со счетом 5½–½ в матче из шести партий (хотя подготовка Адамса была гораздо менее тщательной, чем у Крамника к серии 2002 года). [14]
В ноябре-декабре 2006 года чемпион мира Владимир Крамник играл с Deep Fritz. На этот раз компьютер победил; матч закончился со счетом 2–4. Крамнику удалось просмотреть дебютную книгу компьютера. В первых пяти партиях Крамник направил игру в типичное «антикомпьютерное» позиционное состязание. Он проиграл одну партию ( просмотрев мат в одной ), и сыграл вничью следующие четыре. В последней партии, пытаясь свести матч вничью, Крамник применил более агрессивную сицилианскую защиту и был разгромлен.
Было предположение, что интерес к шахматным соревнованиям между человеком и компьютером резко упадет в результате матча Крамник-Дип Фриц 2006 года. [15] По словам Ньюборна, например, «наука сделана». [16]
Матчи человек-компьютер показали, что лучшие компьютерные системы обгоняют чемпионов по шахматам среди людей в конце 1990-х годов. За 40 лет до этого наблюдалась тенденция, что лучшие машины набирали около 40 очков в год в рейтинге Эло , в то время как лучшие люди набирали всего около 2 очков в год. [17] Наивысший рейтинг, полученный компьютером в соревнованиях с людьми, был рейтингом USCF Deep Thought в 2551 в 1988 году, и ФИДЕ больше не принимает результаты человек-компьютер в своих рейтинговых списках. Для рейтинговых машин были созданы специализированные пулы Эло только для машин, но такие числа, хотя и похожи по внешнему виду, напрямую не сравниваются. [18] В 2016 году Шведская шахматная компьютерная ассоциация оценила компьютерную программу Komodo в 3361.
Шахматные движки продолжают совершенствоваться. В 2009 году шахматные движки, работающие на более медленном оборудовании, достигли уровня гроссмейстера . Мобильный телефон выиграл турнир категории 6 с рейтингом производительности 2898: шахматный движок Hiarcs 13, работающий внутри Pocket Fritz 4 на мобильном телефоне HTC Touch HD, выиграл турнир Copa Mercosur в Буэнос-Айресе , Аргентина, с 9 победами и 1 ничьей 4–14 августа 2009 года. [19] Pocket Fritz 4 ищет менее 20 000 позиций в секунду. [20] Это контрастирует с суперкомпьютерами, такими как Deep Blue, которые искали 200 миллионов позиций в секунду.
Advanced Chess — это форма шахмат, разработанная в 1998 году Каспаровым, в которой человек играет против другого человека, и оба имеют доступ к компьютерам для повышения своей силы. Получившийся «продвинутый» игрок, по утверждению Каспарова, сильнее человека или компьютера по отдельности. Это было доказано во многих случаях, например, на мероприятиях Freestyle Chess.
Сегодня игроки склонны относиться к шахматным движкам как к инструментам анализа, а не как к противникам. [21] Гроссмейстер по шахматам Эндрю Солтис заявил в 2016 году: «Компьютеры слишком хороши», и что чемпион мира Магнус Карлсен не будет играть в компьютерные шахматы, потому что «он просто все время проигрывает, а нет ничего более удручающе, чем проиграть, даже не приняв участия в игре». [22]
Начиная с эпохи механических машин, игравших в окончания с ладьей и королем, и электрических машин, игравших в другие игры, такие как гексагон, в начале 20-го века, ученые и теоретики стремились разработать процедурное представление того, как люди учатся, помнят, думают и применяют знания, а игра в шахматы из-за своей пугающей сложности стала « Дрозофилой искусственного интеллекта (ИИ)». [Примечание 1] Процедурное разрешение сложности стало синонимом мышления, и первые компьютеры, еще до эры шахматных автоматов, обычно называли «электронными мозгами». Начиная со второй половины 20-го века было разработано несколько различных схем для представления знаний и мышления применительно к игре в шахматы (и другим играм, таким как шашки):
Используя эвристику «цели и средства», шахматист-человек может интуитивно определить оптимальные результаты и способы их достижения независимо от количества необходимых ходов, но компьютер должен быть систематичен в своем анализе. Большинство игроков согласны, что для хорошей игры требуется заглядывать как минимум на пять ходов вперед (десять уровней ), когда это необходимо. Обычные правила турнира дают каждому игроку в среднем три минуты на ход. В среднем существует более 30 допустимых ходов на шахматную позицию, поэтому компьютер должен рассмотреть квадриллион возможностей, чтобы заглянуть вперед на десять уровней (пять полных ходов); тот, кто мог бы рассмотреть миллион позиций в секунду, потребовал бы более 30 лет. [9]
Самые ранние попытки процедурного представления игры в шахматы предшествовали цифровой электронной эпохе, но именно цифровой компьютер с хранимой программой дал простор для вычисления такой сложности. Клод Шеннон в 1949 году изложил принципы алгоритмического решения шахмат. В этой статье игра представлена «деревом» или цифровой структурой данных выборов (ветвей), соответствующих ходам. Узлами дерева были позиции на доске, полученные в результате выбора хода. Невозможность представления всей шахматной партии путем построения дерева от первого хода до последнего была сразу очевидна: в шахматах в среднем 36 ходов на позицию, и средняя игра длится около 35 ходов до сдачи (60-80 ходов, если играется до мата, пата или другой ничьей). Существует 400 возможных позиций после первого хода каждого игрока, около 200 000 после двух ходов каждого и почти 120 миллионов после всего лишь 3 ходов каждого.
Поэтому был предложен ограниченный просмотр вперед (поиск) на некоторую глубину, за которым следовало использование предметно-специфических знаний для оценки полученных конечных позиций. Получилась бы своего рода промежуточная позиция, учитывая хорошие ходы с обеих сторон, и ее оценка информировала бы игрока о хорошем или плохом выбранных ходах. Операции поиска и сравнения на дереве хорошо подходили для компьютерных вычислений; представление тонких шахматных знаний в оценочной функции — нет. Ранние шахматные программы страдали в обеих областях: поиск по обширному дереву требовал вычислительных ресурсов, значительно превышающих доступные, а то, какие шахматные знания были полезны и как их кодировать, потребовало бы десятилетий, чтобы выяснить.
Разработчики шахматной компьютерной системы должны решить ряд фундаментальных вопросов реализации. К ним относятся:
Адриан де Гроот опросил ряд шахматистов разной силы и пришел к выводу, что и мастера , и новички рассматривают около сорока-пятидесяти позиций, прежде чем решить, какой ход сделать. Что делает первых намного лучшими игроками, так это то, что они используют навыки распознавания образов, приобретенные на основе опыта. Это позволяет им изучать некоторые линии гораздо глубже, чем другие, просто не рассматривая ходы, которые они могут считать плохими. Еще одним доказательством этого является то, что хорошим игрокам-людям гораздо легче вспоминать позиции из настоящих шахматных партий, разбивая их на небольшое количество узнаваемых подпозиций, а не на совершенно случайные расстановки тех же фигур. Напротив, у плохих игроков одинаковый уровень памяти для обоих вариантов.
Эквивалентом этого в компьютерных шахматах являются функции оценки для оценки листьев, которые соответствуют навыкам распознавания образов игроков-людей, и использование методов машинного обучения для их обучения, таких как настройка Текселя, стохастический градиентный спуск и обучение с подкреплением , которое соответствует накоплению опыта у игроков-людей. Это позволяет современным программам исследовать некоторые линии гораздо глубже, чем другие, используя прямую обрезку и другие избирательные эвристики, чтобы просто не рассматривать ходы, которые программа считает плохими через свою функцию оценки, так же, как это делают игроки-люди. Единственное фундаментальное различие между компьютерной программой и человеком в этом смысле заключается в том, что компьютерная программа может искать гораздо глубже, чем игрок-человек, что позволяет ей искать больше узлов и обходить эффект горизонта в гораздо большей степени, чем это возможно с игроками-людьми.
Программы для компьютерных шахмат обычно поддерживают ряд общих стандартов de facto . Почти все сегодняшние программы могут читать и записывать ходы игры как Portable Game Notation (PGN), а также читать и записывать отдельные позиции как Forsyth–Edwards Notation (FEN). Старые шахматные программы часто понимали только длинную алгебраическую нотацию , но сегодня пользователи ожидают, что шахматные программы будут понимать стандартную алгебраическую шахматную нотацию .
Начиная с конца 1990-х годов программисты начали разрабатывать отдельные движки (с интерфейсом командной строки , который вычисляет, какие ходы являются самыми сильными в позиции) или графический пользовательский интерфейс (GUI), который предоставляет игроку шахматную доску, которую он может видеть, и фигуры, которые можно двигать. Движки сообщают свои ходы в GUI, используя протокол, такой как Chess Engine Communication Protocol (CECP) или Universal Chess Interface (UCI). Разделив шахматные программы на эти две части, разработчики могут написать только пользовательский интерфейс или только движок, без необходимости писать обе части программы. (См. также шахматный движок .)
Разработчикам предстоит решить, подключать ли движок к дебютной книге и/или таблицам эндшпиля или оставить это на усмотрение графического интерфейса.
Структура данных , используемая для представления каждой шахматной позиции, является ключом к производительности генерации ходов и оценки позиции . Методы включают в себя фигуры, хранящиеся в массиве («mailbox» и «0x88»), позиции фигур, хранящиеся в списке («piece list»), коллекции битовых наборов для местоположений фигур (« bitboards ») и позиции, закодированные по Хаффману, для компактного долгосрочного хранения.
Программы для компьютерных шахмат рассматривают шахматные ходы как игровое дерево . Теоретически они проверяют все ходы, затем все контрходы на эти ходы, затем все контрходы на них и так далее, где каждый отдельный ход одного игрока называется « ply ». Эта оценка продолжается до тех пор, пока не будет достигнута определенная максимальная глубина поиска или программа не определит, что была достигнута конечная позиция «листа» (например, мат).
Одним из конкретных типов алгоритмов поиска, используемых в компьютерных шахматах, являются алгоритмы поиска минимакса , где на каждом этапе выбирается «лучший» ход игрока; один игрок пытается максимизировать счет, другой — минимизировать его. С помощью этого чередующегося процесса будет достигнут один конкретный конечный узел, оценка которого представляет искомое значение позиции. Его значение резервируется в корне, и эта оценка становится оценкой позиции на доске. Этот процесс поиска называется минимаксом.
Наивная реализация алгоритма минимакса может искать только на небольшую глубину за практическое время, поэтому были разработаны различные методы, чтобы значительно ускорить поиск хороших ходов. Альфа-бета-обрезка , система определения верхних и нижних границ возможных результатов поиска и поиска до тех пор, пока границы не совпадут, обычно используется для сокращения пространства поиска программы.
Кроме того, также используются различные эвристики выборочного поиска, такие как поиск покоя , прямое отсечение, расширения поиска и сокращения поиска. Эти эвристики запускаются на основе определенных условий в попытке отсеять явно плохие ходы (ходы истории) или исследовать интересные узлы (например, расширения проверки, проходные пешки на седьмой горизонтали и т. д.). Однако эти эвристики выборочного поиска следует использовать очень осторожно. Если слишком много расширить, программа тратит слишком много времени на просмотр неинтересных позиций. Если слишком много отсечено или сокращено, есть риск отсечения интересных узлов.
Поиск по дереву Монте-Карло (MCTS) — это эвристический алгоритм поиска, который расширяет дерево поиска на основе случайной выборки пространства поиска. Версия поиска по дереву Монте-Карло, обычно используемая в компьютерных шахматах, — это PUCT, Predictor и Upper Confidence bounds, применяемые к деревьям.
AlphaZero и Leela Chess Zero от DeepMind используют MCTS вместо минимакса. Такие движки используют пакетирование на графических процессорах для вычисления своих функций оценки и политики (выбор хода), и поэтому требуют параллельного алгоритма поиска, поскольку вычисления на GPU по своей сути параллельны. Алгоритмы минимакса и альфа-бета-отсечения, используемые в компьютерных шахматах, по своей сути являются последовательными алгоритмами, поэтому не будут хорошо работать с пакетированием на GPU. С другой стороны, MCTS является хорошей альтернативой, поскольку случайная выборка, используемая в поиске по дереву Монте-Карло, хорошо подходит для параллельных вычислений, и именно поэтому почти все движки, поддерживающие вычисления на GPU, используют MCTS вместо альфа-бета.
Многие другие оптимизации могут быть использованы для того, чтобы сделать шахматные программы сильнее. Например, таблицы транспозиции используются для записи позиций, которые были ранее оценены, чтобы сэкономить на их пересчете. Таблицы опровержения записывают ключевые ходы, которые «опровергают» то, что кажется хорошим ходом; они обычно сначала пробуются в позициях с вариантами (поскольку ход, который опровергает одну позицию, скорее всего, опровергнет и другую). Недостатком является то, что таблицы транспозиции на большой глубине могут стать довольно большими — от десятков до сотен миллионов записей. Например, таблица транспозиции IBM Deep Blue в 1996 году содержала 500 миллионов записей. Слишком маленькие таблицы транспозиции могут привести к тому, что на поиск несуществующих записей из-за перемалывания будет затрачено больше времени, чем сэкономлено найденными записями. Многие шахматные движки используют размышления , поиск на более глубоких уровнях за время противника, подобно людям, чтобы увеличить свою игровую силу.
Конечно, более быстрое оборудование и дополнительная память могут улучшить игровую силу шахматной программы. Гиперпоточная архитектура может немного повысить производительность, если программа работает на одном ядре или небольшом количестве ядер. Большинство современных программ разработаны для использования преимуществ нескольких ядер для параллельного поиска. Другие программы разработаны для работы на компьютере общего назначения и распределяют генерацию ходов, параллельный поиск или оценку между выделенными процессорами или специализированными сопроцессорами.
Первая статья о шахматном поиске была написана Клодом Шенноном в 1950 году. [23] Он предсказал две основные возможные стратегии поиска, которые будут использоваться, и назвал их «Тип А» и «Тип В» [24] еще до того, как кто-либо запрограммировал компьютер для игры в шахматы.
Программы типа A использовали бы подход « грубой силы », проверяя каждую возможную позицию для фиксированного числа ходов, используя чистый наивный алгоритм минимакса . Шеннон считал, что это было бы непрактично по двум причинам.
Во-первых, при приблизительно тридцати возможных ходах в типичной реальной позиции он ожидал, что поиск приблизительно 109 позиций , задействованных в просмотре на три хода вперед для обеих сторон (шесть уровней ), займет около шестнадцати минут, даже в «очень оптимистичном» случае, когда шахматный компьютер оценивает миллион позиций каждую секунду. (Потребовалось около сорока лет, чтобы достичь такой скорости. Более поздний алгоритм поиска, называемый альфа-бета-отсечением , система определения верхних и нижних границ возможных результатов поиска и поиска до тех пор, пока границы не совпадут, уменьшил фактор ветвления дерева игры логарифмически, но в то время для шахматных программ все еще было невозможно использовать экспоненциальный взрыв дерева.
Во-вторых, он игнорировал проблему покоя, пытаясь оценить только позицию, которая находится в конце обмена фигурами или другой важной последовательности ходов («линий»). Он ожидал, что адаптация минимакса для решения этой проблемы значительно увеличит количество позиций, которые необходимо рассмотреть, и еще больше замедлит программу. Он ожидал, что адаптация типа A для решения этой проблемы значительно увеличит количество позиций, которые необходимо рассмотреть, и еще больше замедлит программу.
Это естественным образом привело к тому, что называется «выборочным поиском» или «поиском типа B», использующим шахматные знания (эвристики) для выбора нескольких предположительно хороших ходов из каждой позиции для поиска и отбрасывания остальных без поиска. Вместо того, чтобы тратить вычислительную мощность на изучение плохих или тривиальных ходов, Шеннон предположил, что программы типа B будут использовать два улучшения:
Это позволило бы им заглянуть дальше вперед («глубже») в наиболее значимые линии за разумное время. Однако ранние попытки выборочного поиска часто приводили к тому, что лучший ход или ходы отсекались. В результате в течение следующих 25 лет, в течение которых доминировала эта первая итерация парадигмы выборочного поиска, не было достигнуто никакого прогресса. Лучшей программой, созданной в этот ранний период, была Mac Hack VI в 1967 году; она играла примерно на том же уровне, что и средний любитель (класс C по шкале рейтинга Шахматной федерации США).
Тем временем аппаратное обеспечение продолжало совершенствоваться, и в 1974 году поиск методом грубой силы был впервые реализован в программе Northwestern University Chess 4.0. При таком подходе все альтернативные ходы в узле перебираются, и ни один не отбрасывается. Они обнаружили, что время, необходимое для простого перебора всех ходов, было намного меньше времени, необходимого для применения интенсивных по знаниям эвристик для выбора лишь нескольких из них, а преимущество в том, что хорошие ходы не отбрасываются преждевременно или непреднамеренно, привело к существенно более высокой производительности.
В 1980-х и 1990-х годах в парадигме выборочного поиска, наконец, был достигнут прогресс с разработкой поиска покоя , отсечения нулевого хода и других современных эвристик выборочного поиска. Эти эвристики имели гораздо меньше ошибок, чем более ранние эвристики, и, как было установлено, стоили дополнительного времени, которое они сэкономили, поскольку могли искать глубже и широко применяться многими поисковыми системами. Хотя многие современные программы используют альфа-бета-поиск в качестве субстрата для своего алгоритма поиска, эти дополнительные эвристики выборочного поиска, используемые в современных программах, означают, что программа больше не выполняет поиск «грубой силой». Вместо этого они в значительной степени полагаются на эти эвристики выборочного поиска для расширения строк, которые программа считает хорошими, и отсечения и сокращения строк, которые программа считает плохими, до точки, где большинство узлов в дереве поиска отсечены, что позволяет современным программам выполнять очень глубокий поиск.
В 2006 году Реми Кулом создал поиск по дереву Монте-Карло , еще один вид селективного поиска типа B. В 2007 году Левенте Кочиш и Чаба Шепешвари создали адаптацию поиска по дереву Монте-Карло под названием Upper Confidence bounds applied to Trees или сокращенно UCT. В 2011 году Крис Розин разработал вариант UCT под названием Predictor + Upper Confidence bounds applied to Trees или сокращенно PUCT. Затем PUCT использовался в AlphaZero в 2017 году, а затем в Leela Chess Zero в 2018 году.
В 1970-х годах большинство шахматных программ работали на суперкомпьютерах, таких как Control Data Cyber 176s или Cray-1s, что свидетельствует о том, что в этот период развития компьютерных шахмат ограничивающим фактором производительности была вычислительная мощность. Большинство шахматных программ испытывали трудности с поиском на глубину более 3 слоев. Только с появлением аппаратных шахматных машин 1980-х годов стала очевидной связь между скоростью процессора и знаниями, закодированными в оценочной функции.
Подсчитано, что удвоение скорости компьютера увеличивает силу игры примерно на пятьдесят-семьдесят пунктов Эло (Levy & Newborn 1991:192).
Для большинства шахматных позиций компьютеры не могут предвидеть все возможные конечные позиции. Вместо этого они должны предвидеть несколько ходов вперед и сравнивать возможные позиции, известные как листья. Алгоритм, который оценивает листья, называется «функцией оценки», и эти алгоритмы часто сильно различаются в разных шахматных программах. Функции оценки обычно оценивают позиции в сотых долях пешки (называемых сентипешка), где по соглашению положительная оценка благоприятствует белым, а отрицательная — черным. Однако некоторые функции оценки выводят проценты выигрыша/ничьи/проигрыша вместо сентипешек.
Исторически сложилось так, что функции оценки, созданные вручную, учитывают материальную ценность наряду с другими факторами, влияющими на силу каждой стороны. При подсчете материала для каждой стороны типичные значения для фигур составляют 1 очко для пешки , 3 очка для коня или слона , 5 очков для ладьи и 9 очков для ферзя . (См. Относительная ценность шахматной фигуры .) Королю иногда присваивается произвольно высокое значение, например 200 очков ( статья Шеннона ), чтобы гарантировать, что мат перевешивает все другие факторы (Levy & Newborn 1991:45). Помимо очков для фигур, большинство функций оценки, созданных вручную, учитывают множество факторов, таких как структура пешек, тот факт, что пара слонов обычно стоит больше, централизованные фигуры стоят больше и т. д. Обычно учитывается защита королей, а также фаза игры (дебют, середина или эндшпиль). Для оптимизации созданных вручную функций оценки обычно используются такие методы машинного обучения, как поворот Текселя, стохастический градиентный спуск или обучение с подкреплением .
Большинство современных функций оценки используют нейронные сети . Наиболее распространенной функцией оценки, используемой сегодня, является эффективно обновляемая нейронная сеть , которая представляет собой неглубокую нейронную сеть, входными данными которой являются таблицы фигур-квадратов . Таблицы фигур-квадратов представляют собой набор из 64 значений, соответствующих клеткам шахматной доски, и обычно существует таблица фигур-квадратов для каждой фигуры и цвета, что приводит к 12 таблицам фигур-квадратов и, таким образом, 768 входным данным в нейронную сеть. Кроме того, некоторые движки используют глубокие нейронные сети в своей функции оценки. Нейронные сети обычно обучаются с использованием некоторого алгоритма обучения с подкреплением в сочетании с контролируемым обучением или неконтролируемым обучением .
Выход функции оценки — это один скаляр, квантованный в центипешках или других единицах, который в случае функций оценки, созданных вручную, представляет собой взвешенную сумму различных описанных факторов, или в случае функций оценки на основе нейронной сети — выход головы нейронной сети. Оценка предположительно представляет или приближает значение поддерева ниже оцениваемого узла, как если бы поиск был выполнен до завершения, т. е. до конца игры. Во время поиска оценка сравнивается с оценками других листьев, исключая узлы, которые представляют плохие или неэффективные ходы для любой из сторон, чтобы получить узел, который путем конвергенции представляет значение позиции с наилучшей игрой обеих сторон.
Игра в эндшпиле долгое время была одной из самых слабых сторон шахматных программ из-за необходимой глубины поиска. Некоторые программы, в противном случае, уровня мастера, не могли выиграть в позициях, где даже игроки среднего уровня могли заставить выиграть.
Чтобы решить эту проблему, компьютеры были использованы для полного анализа некоторых позиций шахматного эндшпиля , начиная с короля и пешки против короля. Такие таблицы эндшпиля генерируются заранее с использованием формы ретроградного анализа , начиная с позиций, где конечный результат известен (например, где одна сторона была матована), и просматривая, какие другие позиции находятся на один ход дальше от них, затем какие на один ход дальше от них и т. д. Кен Томпсон был пионером в этой области.
Результаты компьютерного анализа иногда удивляли людей. В 1977 году шахматная машина Belle Томпсона использовала таблицу эндшпиля для короля и ладьи против короля и королевы и смогла свести к ничьей теоретически проигранное окончание против нескольких мастеров (см. позиция Филидора#Королева против ладьи ). И это несмотря на то, что она не следовала обычной стратегии отсрочки поражения, удерживая защищающегося короля и ладью близко друг к другу как можно дольше. Когда Томпсона попросили объяснить причины некоторых ходов программы, он не смог этого сделать, за исключением того, что база данных программы просто выдавала лучшие ходы.
Большинство гроссмейстеров отказались играть с компьютером в эндшпиле ферзь против ладьи, но Уолтер Браун принял вызов. Была создана позиция ферзь против ладьи, в которой ферзь может выиграть за тридцать ходов при идеальной игре. Брауну было предоставлено 2,5 часа на то, чтобы сделать пятьдесят ходов, в противном случае по правилу пятидесяти ходов объявлялась ничья . После сорока пяти ходов Браун согласился на ничью, будучи не в состоянии заставить мат или выиграть ладью в течение следующих пяти ходов. В финальной позиции Браун все еще был в семнадцати ходах от мата, но не так уж и далек от победы над ладьей. Браун изучил эндшпиль и снова сыграл с компьютером неделю спустя в другой позиции, в которой ферзь может выиграть за тридцать ходов. На этот раз он взял ладью на пятидесятом ходу, что дало ему выигрышную позицию (Levy & Newborn 1991:144–48), (Nunn 2002:49).
Другие позиции, которые долгое время считались выигранными, как оказалось, требовали больше ходов против идеальной игры, чтобы выиграть, чем позволяло правило пятидесяти ходов в шахматах. Как следствие, в течение нескольких лет официальные правила ФИДЕ по шахматам были изменены, чтобы увеличить количество ходов, разрешенных в этих окончаниях. Через некоторое время правило вернулось к пятидесяти ходам во всех позициях — было обнаружено больше таких позиций, что еще больше усложнило правило, и это не имело никакого значения в человеческой игре, поскольку они не могли играть позиции идеально.
На протяжении многих лет были выпущены другие форматы баз данных эндшпилей, включая Edward Tablebase, De Koning Database и Nalimov Tablebase, которая используется многими шахматными программами, такими как Rybka , Shredder и Fritz . Доступны базы таблиц для всех позиций с шестью фигурами. [25] Некоторые эндшпили с семью фигурами были проанализированы Марком Бурзуцки и Яковом Коновалом. [26] Программисты, использующие суперкомпьютеры «Ломоносов» в Москве, завершили базу шахматных таблиц для всех эндшпилей с семью фигурами или меньше (тривиальные позиции эндшпиля исключены, такие как шесть белых фигур против одинокого черного короля ). [27] [28] Во всех этих базах данных эндшпилей предполагается, что рокировка больше невозможна.
Многие табличные базы не учитывают правило пятидесяти ходов, согласно которому игра, в которой пятьдесят ходов проходят без взятия или хода пешкой, может быть объявлена ничьей любым игроком. Это приводит к тому, что табличная база возвращает результаты, такие как «Принудительный мат в шестьдесят шесть ходов» в некоторых позициях, которые на самом деле были бы ничьей из-за правила пятидесяти ходов. Одна из причин этого заключается в том, что если правила шахмат будут изменены еще раз, давая больше времени для победы в таких позициях, не будет необходимости перегенерировать все табличные базы. Также программе, использующей табличные базы, очень легко заметить и учесть эту «особенность», и в любом случае, если использовать табличную базу эндшпиля, она выберет ход, который приведет к самой быстрой победе (даже если это будет нарушением правила пятидесяти ходов при идеальной игре). Если играть с противником, не использующим табличную базу, такой выбор даст хорошие шансы на победу в течение пятидесяти ходов.
Базы таблиц Налимова, использующие самые современные методы сжатия , требуют 7,05 ГБ дискового пространства для всех пятичастных окончаний. Для покрытия всех шестичастных окончаний требуется приблизительно 1,2 ТБ . По оценкам, для семичастной базы таблиц требуется от 50 до 200 ТБ дискового пространства. [29]
Базы данных эндшпилей заняли видное место в 1999 году, когда Каспаров сыграл показательный матч в Интернете против остального мира . Был достигнут эндшпиль с семью фигурами ферзя и пешки , и сборная мира боролась за спасение ничьей. Евгений Налимов помог, создав таблицу шестифигурных окончаний, где у обеих сторон было по два ферзя, которая активно использовалась для помощи в анализе обеими сторонами.
Самая популярная база таблиц эндшпиля — syzygy, которая используется большинством лучших компьютерных программ, таких как Stockfish , Leela Chess Zero и Komodo . Она также значительно меньше по размеру, чем другие форматы, с базами таблиц из 7 фигур, занимающими всего 18,4 ТБ. [30]
Для современного шахматного движка, такого как Stockfish, табличная база обеспечивает лишь очень незначительное увеличение игровой силы (примерно 3 очка Эло для сизигийной 6-фигурной комбинации по состоянию на Stockfish 15). [31]
Шахматные движки, как и люди, могут экономить время обработки, а также выбирать сильные варианты, изложенные мастерами, ссылаясь на дебютную книгу, хранящуюся в дисковой базе данных. Дебютные книги охватывают дебютные ходы игры на разную глубину, в зависимости от дебюта и варианта, но обычно до первых 10-12 ходов (20-24 слоя). Поскольку дебюты изучались мастерами глубоко на протяжении столетий, и некоторые из них известны даже в середине игры, оценки конкретных вариантов мастерами обычно будут превосходить общую эвристику программы.
Хотя в свое время игра вне книги хода для того, чтобы поставить шахматную программу на ее собственные ресурсы, могла быть эффективной стратегией, поскольку шахматные дебютные книги были избирательны к стилю игры программы, а программы имели заметные слабости по сравнению с людьми, сегодня это уже не так. [ когда? ] Дебютные книги, хранящиеся в компьютерных базах данных, скорее всего, гораздо более обширны, чем даже у самых подготовленных людей, и игра раннего вне книги хода может привести к тому, что компьютер найдет необычный ход в своей книге и поставит противника в резко невыгодное положение. Даже если этого не произойдет, игра вне книги может быть намного лучше для тактически острых шахматных программ, чем для людей, которым приходится находить сильные ходы в незнакомом варианте за доской.
В современных турнирах на движках дебютные книги используются для того, чтобы заставить движки играть намеренно несбалансированные дебюты, чтобы снизить процент ничьих и добавить больше разнообразия в игры. [32]
CEGT , [33] CSS, [34] SSDF , [35] WBEC, [36] REBEL , [37] FGRL, [38] и IPON [39] ведут рейтинговые списки, позволяющие фанатам сравнивать силу движков. Различные версии Stockfish , Komodo , Leela Chess Zero и Fat Fritz доминируют в рейтинговых списках в начале 2020-х годов.
CCRL (Computer Chess Rating Lists) — организация, которая проверяет силу компьютерных шахматных движков , играя программы друг с другом. CCRL была основана в 2006 году для содействия соревнованиям между компьютерами и подсчета результатов в рейтинговом списке. [40]
Организация использует три разных списка: 40/40 (40 минут на каждые 40 сыгранных ходов), 40/4 (4 минуты на каждые 40 сыгранных ходов) и 40/4 FRC (тот же контроль времени, но Chess960). [Примечание 2] Обдумывание (или постоянный мозг ) отключено, а тайминг настроен на процессор AMD64 X2 4600+ (2,4 ГГц) с использованием Crafty 19.17 BH в качестве эталона. Используются общие, нейтральные дебютные книги (в отличие от собственной книги движка) до лимита в 12 ходов в игре вместе с базами таблиц из 4 или 5 человек . [40] [41] [42]
Идея создания шахматной машины восходит к восемнадцатому веку. Около 1769 года шахматный автомат под названием The Turk , созданный венгерским изобретателем Фаркашем Кемпеленом , стал знаменитым, прежде чем был разоблачен как мистификация. До развития цифровых вычислений серьезные испытания, основанные на автоматах, таких как El Ajedrecista 1912 года, построенная испанским инженером Леонардо Торресом Кеведо , которая играла в эндшпиле король и ладья против короля, были слишком сложны и ограничены, чтобы быть полезными для игры в полноценные шахматные партии. Область механических шахматных исследований затаилась до появления цифрового компьютера в 1950-х годах.
С тех пор шахматные энтузиасты и компьютерные инженеры создавали, с возрастающей степенью серьезности и успеха, шахматные игровые машины и компьютерные программы. Одним из немногих шахматных гроссмейстеров, серьезно посвятивших себя компьютерным шахматам, был бывший чемпион мира по шахматам Михаил Ботвинник , который написал несколько работ по этой теме. Интерес Ботвинника к компьютерным шахматам начался в 50-х годах, когда он отдавал предпочтение шахматным алгоритмам, основанным на селективной стратегии типа B Шеннона, как обсуждалось вместе с Максом Эйве в 1958 году на голландском телевидении. Работая с относительно примитивным оборудованием, доступным в Советском Союзе в начале 1960-х годов, у Ботвинника не было иного выбора, кроме как исследовать программные методы выбора ходов; в то время только самые мощные компьютеры могли достичь гораздо большего, чем трехслойный поиск полной ширины, а у Ботвинника таких машин не было. В 1965 году Ботвинник был консультантом команды ИТЭФ в американо-советском шахматном матче между компьютерами, который выиграл заочный шахматный матч против программы Котока-Маккарти под руководством Джона Маккарти в 1967 году (см. Коток-Маккарти ). Позже он консультировал команду, которая создала шахматную программу «Каисса» в Московском институте проблем управления. У Ботвинника были свои собственные идеи по моделированию Ума Мастера Шахмат. После публикации и обсуждения своих ранних идей по картам атак и траекториям в Московском центральном шахматном клубе в 1966 году он нашел Владимира Бутенко в качестве сторонника и соратника. Бутенко первым реализовал представление доски векторных атак 15x15 на компьютере М-20, определяя траектории. После того, как Ботвинник представил концепцию Зон в 1970 году, Бутенко отказался от дальнейшего сотрудничества и начал писать свою собственную программу, названную Эврика. В 70-х и 80-х годах, возглавляя команду Бориса Штильмана, Александра Юдина, Александра Резницкого, Михаила Цфасмана и Михаила Чудакова, Ботвинник работал над собственным проектом «Пионер» — шахматным проектом на основе искусственного интеллекта. В 90-х годах Ботвинник, уже в свои 80 лет, работал над новым проектом «CC Sapiens».
Одна из вех развития произошла, когда команда из Северо-Западного университета , которая отвечала за серию программ Chess и выиграла первые три чемпионата ACM по компьютерным шахматам (1970–72), отказалась от поиска типа B в 1973 году. Получившаяся в результате программа Chess 4.0 выиграла чемпионат того года, а ее последователи заняли второе место как в чемпионате ACM 1974 года, так и в первом чемпионате мира по компьютерным шахматам того года , прежде чем снова выиграть чемпионат ACM в 1975, 1976 и 1977 годах. Реализация типа A оказалась столь же быстрой: за то время, которое требовалось, чтобы решить, какие ходы достойны поиска, можно было просто поискать их все. Фактически, Chess 4.0 задала парадигму, которой следовали и продолжают следовать по сути все современные шахматные программы сегодня, и которая была успешно начата российским ИТЭФ в 1965 году.
В 1978 году ранняя версия аппаратной шахматной машины Кена Томпсона Belle приняла участие в Североамериканском чемпионате по компьютерным шахматам и одержала победу над доминирующей программой Northwestern University Chess 4.7.
Технологические достижения на порядки в вычислительной мощности сделали подход грубой силы гораздо более острым, чем это было в первые годы. Результатом стало то, что очень надежный, тактический игрок ИИ, которому помогали некоторые ограниченные позиционные знания, встроенные в функцию оценки и правила обрезки/расширения, начал соответствовать лучшим игрокам в мире. Оказалось, что это дало превосходные результаты, по крайней мере в области шахмат, позволяя компьютерам делать то, что они делают лучше всего (вычислять), а не уговаривать их имитировать человеческие мыслительные процессы и знания. В 1997 году Deep Blue , машина грубой силы, способная проверять 500 миллионов узлов в секунду, победила чемпиона мира Гарри Каспарова, что стало первым случаем, когда компьютер победил действующего чемпиона мира по шахматам со стандартным контролем времени.
В 2016 году NPR попросило экспертов охарактеризовать стиль игры компьютерных шахматных движков. Мюррей Кэмпбелл из IBM заявил, что «У компьютеров нет никакого чувства эстетики... Они играют то, что считают объективно лучшим ходом в любой позиции, даже если это выглядит абсурдно, и они могут играть любой ход, каким бы уродливым он ни был». Гроссмейстеры Эндрю Солтис и Сьюзан Полгар заявили, что компьютеры более склонны отступать, чем люди. [22]
Хотя нейронные сети использовались в оценочных функциях шахматных движков с конца 1980-х годов в таких программах, как NeuroChess, Morph, Blondie25, Giraffe, AlphaZero и MuZero , [43] [44] [45] [46] [47] нейронные сети не получили широкого распространения в шахматных движках до появления эффективно обновляемых нейронных сетей летом 2020 года. Эффективно обновляемые нейронные сети были первоначально разработаны в компьютерных сёги в 2018 году Ю Насу, [48] [49] и должны были быть сначала перенесены в производную от Stockfish под названием Stockfish NNUE 31 мая 2020 года, [50] и интегрированы в официальный движок Stockfish 6 августа 2020 года, [51] [52] прежде чем другие шахматные программисты начали внедрять нейронные сети в свои движки.
Некоторые люди, такие как Венки Рамакришнан из Королевского общества , считают, что AlphaZero привела к широкому внедрению нейронных сетей в шахматных движках. [53] Однако AlphaZero повлияла на очень немногие движки, чтобы начать использовать нейронные сети, и это были, как правило, новые экспериментальные движки, такие как Leela Chess Zero , которые начали специально копировать статью AlphaZero. Глубокие нейронные сети , используемые в оценочной функции AlphaZero, требовали дорогих графических процессоров , которые были несовместимы с существующими шахматными движками. Подавляющее большинство шахматных движков используют только центральные процессоры , а вычисление и обработка информации на графических процессорах требуют специальных библиотек в бэкэнде, таких как CUDA от Nvidia , к которым ни один из движков не имел доступа. Таким образом, подавляющее большинство шахматных движков, таких как Komodo и Stockfish, продолжали использовать созданные вручную оценочные функции, пока эффективно обновляемые нейронные сети не были перенесены в компьютерные шахматы в 2020 году, что вообще не требовало ни использования графических процессоров, ни библиотек, таких как CUDA. Но даже в этом случае нейронные сети, используемые в компьютерных шахматах, довольно поверхностны, а методы глубокого обучения с подкреплением, впервые разработанные AlphaZero, по-прежнему крайне редки в компьютерных шахматах.
Эти шахматные игровые системы включают в себя специализированное оборудование с примерными датами выпуска (за исключением специализированных микрокомпьютеров):
.jpg/1280px-thumbnail.jpg)
В конце 1970-х — начале 1990-х годов существовал конкурентный рынок специализированных шахматных компьютеров. Этот рынок изменился в середине 1990-х годов, когда компьютеры с выделенными процессорами больше не могли конкурировать с быстрыми процессорами персональных компьютеров.
В последнее время некоторые любители используют Multi Emulator Super System для запуска шахматных программ, созданных для компьютеров Fidelity или Mephisto Хегенера и Глейзера, на современных 64-битных операционных системах , таких как Windows 10. [74] Автор Rebel Эд Шрёдер также адаптировал три из написанных им Mephisto Хегенера и Глейзера для работы в качестве движков UCI. [75]
Эти программы можно запускать в MS-DOS, а также в 64-битной Windows 10 с помощью эмуляторов, таких как DOSBox или Qemu : [76]
Известные теоретики компьютерных шахмат:
Перспективы полного решения шахмат обычно считаются довольно отдаленными. Широко распространено мнение, что не существует вычислительно недорогого метода решения шахмат даже в слабом смысле определения с уверенностью значения начальной позиции, и, следовательно, идея решения шахмат в более сильном смысле получения практически пригодного описания стратегии для идеальной игры для любой из сторон сегодня кажется нереалистичной. Однако не было доказано, что не существует вычислительно дешевого способа определения наилучшего хода в шахматной позиции, и даже что традиционный альфа-бета-искатель, работающий на современном вычислительном оборудовании, не может решить начальную позицию за приемлемое время. Трудность доказательства последнего заключается в том, что, хотя число позиций на доске, которые могут возникнуть в ходе шахматной партии, огромно (порядка как минимум 10 43 [78] до 10 47 ), трудно с математической уверенностью исключить возможность того, что начальная позиция позволяет любой из сторон форсировать мат или троекратное повторение после относительно небольшого количества ходов, в этом случае дерево поиска может охватывать лишь очень небольшое подмножество множества возможных позиций. Математически доказано, что обобщенные шахматы (шахматы, в которые играют произвольно большим количеством фигур на произвольно большой шахматной доске) являются EXPTIME-полными [79] , что означает, что определение выигрывающей стороны в произвольной позиции обобщенных шахмат, как доказуемо, занимает экспоненциальное время в худшем случае; однако этот теоретический результат не дает нижней границы объема работы, необходимой для решения обычных шахмат 8x8.
Была решена игра «Мини-шахматы » Мартина Гарднера , играемая на доске 5×5 с приблизительно 1018 возможными позициями на доске; ее теоретико-игровая ценность составляет 1/2 (т.е. ничья может быть принудительно вызвана любой из сторон), и была описана стратегия принудительного достижения этого результата.
С другой стороны, также был достигнут прогресс: по состоянию на 2012 год были решены все эндшпили с 7 и менее фигурами (2 короля и до 5 других фигур).
«Шахматный движок» — это программное обеспечение, которое вычисляет и упорядочивает, какие ходы являются наиболее сильными для игры в данной позиции. Авторы движков сосредоточены на улучшении игры своих движков, часто просто импортируя движок в графический пользовательский интерфейс (GUI), разработанный кем-то другим. Движки взаимодействуют с GUI с помощью стандартизированных протоколов, таких как ныне вездесущий Universal Chess Interface, разработанный Стефаном Майер-Каленом и Францем Хубером. Есть и другие, например Chess Engine Communication Protocol, разработанный Тимом Манном для GNU Chess и Winboard . Chessbase имеет свой собственный фирменный протокол, и одно время Millennium 2000 использовал другой протокол для ChessGenius . Движки, разработанные для одной операционной системы и протокола, могут быть портированы на другие ОС или протоколы.
Шахматные движки регулярно соревнуются друг с другом на специализированных турнирах .
В 1997 году Internet Chess Club выпустил свой первый Java-клиент для игры в шахматы онлайн против других людей в веб-браузере. [80] Это, вероятно, было одно из первых шахматных веб-приложений. Вскоре после этого появился Free Internet Chess Server с похожим клиентом. [81] В 2004 году Международная федерация заочных шахмат открыла веб-сервер для замены своей системы на основе электронной почты. [82] Chess.com начал предлагать Live Chess в 2007 году. [83] Chessbase / Playchess уже давно имеет загружаемый клиент, а в 2013 году добавил веб-клиент. [84]
Другое популярное веб-приложение — тактическое обучение. Ныне несуществующий Chess Tactics Server открыл свой сайт в 2006 году, [85] за ним в следующем году последовал Chesstempo, [86] а Chess.com добавил свой Tactics Trainer в 2008 году. [87] Chessbase добавил веб-приложение тактического обучения в 2015 году. [88]
Chessbase вывела свою базу данных шахматных партий в онлайн в 1998 году. [89] Еще одной ранней базой данных шахматных партий была Chess Lab, которая была запущена в 1999 году. [90] New In Chess изначально пыталась конкурировать с Chessbase, выпустив программу NICBase для Windows 3.x , но в конечном итоге решила отказаться от программного обеспечения и вместо этого сосредоточиться на своей онлайн-базе данных, начиная с 2002 года. [91]
С 2006 года можно было играть против движка Shredder онлайн. [92] В 2015 году Chessbase добавила веб-приложение для игры Fritz, [93] а также My Games для хранения партий. [94]
Начиная с 2007 года Chess.com предлагал своим клиентам онлайн-контент обучающей программы Chess Mentor. [95] Ведущие гроссмейстеры, такие как Сэм Шенкленд и Уолтер Браун, внесли свой вклад в обучение.
{{cite web}}: CS1 maint: бот: исходный статус URL неизвестен ( ссылка ){{cite web}}: CS1 maint: архивная копия как заголовок ( ссылка )В данной статье использован текст Chess Programming Wiki, доступный по лицензии CC BY-SA 3.0.
