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

О фильме 2013 года см. «Компьютерные шахматы» (фильм) . Информацию о шахматах, в которые играют через Интернет, см. в разделе «Онлайн-шахматы» .

Шахматный компьютер 1990-х годов с сенсором давления и ЖК-экраном

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

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

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

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

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

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

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

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

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

Виды и особенности шахматного программного обеспечения

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

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

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

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

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

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

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

Основная статья: Шахматные матчи человека и компьютера

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

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

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

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

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

В мае 1997 года обновленная версия Deep Blue победила Каспарова со счетом 3½–2½ в ответном матче. В 2003 году был снят документальный фильм, в основном о противостоянии, под названием « Игра окончена: Каспаров и машина» .

Deep Blue против Каспарова, 1996, игра 1

	а	б	с	д	и	ж	г	час
8									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 , который завершился вничью. Крамник выиграл вторую и третью партии, используя «традиционную» антикомпьютерную тактику – играйте консервативно ради долгосрочного преимущества, которое компьютер не может увидеть при поиске в дереве игр . Однако Фриц выиграл пятую партию после грубой ошибки Крамника. Шестую игру комментаторы турнира охарактеризовали как «зрелищную». Крамник, находившийся в более выгодной позиции в начале миттельшпиля , попробовал пожертвовать фигуру, чтобы добиться сильной тактической атаки, стратегия, известная как очень рискованная против компьютеров, которые лучше всего защищаются от таких атак. Верный своей форме, Фриц нашел надежную защиту, а атака Крамника захлебнулась, оставив его в плохой позиции. Крамник отказался от игры, посчитав позицию проигранной. Однако послеигровой человеческий и компьютерный анализ показал, что программа Фрица вряд ли смогла добиться победы, и Крамник фактически пожертвовал ничейной позицией. Последние две игры завершились вничью. Учитывая обстоятельства, большинство комментаторов по-прежнему считают Крамника более сильным игроком в матче.

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

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

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

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

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

Шахматные матчи между человеком и компьютером показали, что лучшие компьютерные системы обогнали чемпионов по шахматам среди людей в конце 1990-х годов. В течение 40 лет до этого наблюдалась тенденция, согласно которой лучшие машины получали около 40 баллов в год в рейтинге Эло, в то время как лучшие люди получали только примерно 2 балла в год. Наивысшим рейтингом, полученным компьютером в соревнованиях между людьми, был рейтинг USCF компании Deep Thought, равный 2551 в 1988 году, и ФИДЕ больше не принимает результаты человека и компьютера в своих рейтинговых списках. Для рейтинговых машин были созданы специализированные пулы Эло, состоящие только из машин, но такие цифры, хотя и схожи по внешнему виду, не сравниваются напрямую. В 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-го века было разработано несколько различных схем для представления знаний и мышления применительно к игре в шахматы (и другие игры, такие как шашки):

• на основе поиска (грубая сила или выборочный поиск)
  • Поиск по схеме на основе поиска ( минимакс / альфа-бета , поиск по дереву Монте-Карло )
  • Оценки в схеме на основе поиска ( машинное обучение , нейронные сети , настройка текселей , генетические алгоритмы , градиентный спуск , обучение с подкреплением )
• основанный на знаниях (PARADISE, базы таблиц эндшпиля )

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

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

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

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

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

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

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

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

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

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

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

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

Основная статья: Представительство в совете (шахматы)

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

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

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

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

Дополнительная информация: Альфа-бета-обрезка и минимакс.

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

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

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

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

Дополнительная информация: Поиск по дереву Монте-Карло.

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

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

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

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

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

История

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

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

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

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

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

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

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

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

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

В 2006 году Реми Кулом создал поиск по дереву Монте-Карло , еще один вид выборочного поиска типа B. В 2007 году Левенте Кочиш и Чаба Сепешвари создали адаптацию поиска по дереву Монте-Карло под названием «Верхние доверительные границы», применимую к деревьям или сокращенно UCT. В 2011 году Крис Розин разработал вариант UCT под названием «Предиктор + верхние доверительные границы», применимый к деревьям, или сокращенно 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 очков ( статья Шеннона ), чтобы гарантировать, что мат перевешивает все другие факторы ( Levy & Newborn 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 году, когда Каспаров провел в Интернете показательный матч против остального мира . Был достигнут эндшпиль из семи фигур ферзь и пешка, и сборная мира боролась за спасение ничьей. Евгений Налимов помог, создав основу таблицы концовок из шести фигур, в которой у обеих сторон было по два ферзя, что активно использовалось для облегчения анализа обеими сторонами.

Самая популярная база таблиц для эндшпиля — syzygy, которая используется большинством ведущих компьютерных программ, таких как Stockfish , Leela Chess Zero и Komodo . Он также значительно меньше по размеру, чем другие форматы: табличные базы из 7 частей занимают всего 18,4 ТБ.

Для современного шахматного движка, такого как Stockfish, основание таблицы обеспечивает лишь очень незначительное увеличение игровой силы (приблизительно 3 очка Эло для сизигий 6men по состоянию на Stockfish 15).

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

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

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

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

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

См. Также: Шахматный движок § Рейтинги.

центральноевропейское время , CSS, ССДФ , ВБЭК, МЯТЕЖНИК , ФГРЛ, и ЭКОНОМИЯ вести рейтинговые списки, позволяющие болельщикам сравнивать мощность двигателей. Различные версии Stockfish , Komodo , Leela Chess Zero и Fat Fritz доминируют в рейтинговых списках начала 2020-х годов.

CCRL (Рейтинговые списки компьютерных шахмат) — это организация, которая проверяет компьютерных шахматных движков , силу играя программы друг против друга. 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-х годах.

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

С тех пор шахматные энтузиасты и компьютерные инженеры со все большей серьезностью и успехом создавали шахматные машины и компьютерные программы. Одним из немногих шахматных гроссмейстеров, серьезно посвятивших себя компьютерным шахматам, был бывший чемпион мира по шахматам Михаил Ботвинник , написавший несколько работ на эту тему. Интерес Ботвинника к компьютерным шахматам начался в 50-х годах, когда он отдавал предпочтение шахматным алгоритмам, основанным на селективной стратегии Шеннона типа B, которая обсуждалась вместе с Максом Эйве в 1958 году на голландском телевидении. Работая с относительно примитивным оборудованием, доступным в Советском Союзе в начале 1960-х годов, у Ботвинника не было другого выбора, кроме как исследовать методы программного выбора хода; в то время только самые мощные компьютеры могли добиться большего, чем трехслойный поиск по всей ширине, а у Ботвинника таких машин не было. В 1965 году Ботвинник был консультантом команды ИТЭФ в американо-советском матче по компьютерным шахматам, в результате которого в 1967 году в заочном шахматном матче была выиграна программа Коток-Маккарти, возглавляемая Джоном Маккарти (см. Коток-Маккарти ). Позже он консультировал команду, создавшую шахматную программу «Каисса» в Московском институте управляющих наук. У Ботвинника были свои идеи по моделированию мышления шахматного мастера. После публикации и обсуждения своих ранних идей о картах и ​​траекториях атак в Московском центральном шахматном клубе в 1966 году он нашел Владимира Бутенко своим сторонником и соратником. Бутенко впервые реализовал представление доски векторных атак 15х15 на компьютере М-20, определяя траектории. После того как Ботвинник в 1970 году представил концепцию «Зон», Бутенко отказался от дальнейшего сотрудничества и начал писать собственную программу, получившую название «Эврика». В 70-х и 80-х годах, возглавляя команду Бориса Стильмана, Александра Юдина, Александра Резницкого, Михаила Цфасмана и Михаила Чудакова, Ботвинник работал над собственным проектом «Пионер», который представлял собой шахматный проект, основанный на искусственном интеллекте. В 90-х Ботвинник уже в свои 80 работал над новым проектом «CC Sapiens».

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

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

Восстание шахматных машин

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

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

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

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

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

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

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

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

Хронология

• 1769 г. – Вольфганг фон Кемпелен строит «Тюрк» . Представленный как автомат, играющий в шахматы, он тайно управляется игроком-человеком, спрятанным внутри машины.
• 1868 г. - Чарльз Хупер представляет автомат Аджиба , внутри которого также спрятан человек-шахматист.
• 1912 – Леонардо Торрес-и-Кеведо создает El Ajedrecista , машину, которая могла играть в эндшпиле «Король и ладья против короля» .
• по крайней мере на десять лет раньше аналогичной работы, 1941 – Конрад Цузе, разрабатывает компьютерные шахматные алгоритмы в своем формализме программирования Plankalkül . Однако из-за обстоятельств Второй мировой войны они не были опубликованы и стали известны только в 1970-х годах.
• 1948 — Норберта Винера Книга « Кибернетика » описывает, как можно разработать шахматную программу с использованием минимаксного поиска с ограниченной глубиной и оценочной функцией .
• 1950 - Клод Шеннон публикует «Программирование компьютера для игры в шахматы», одну из первых статей об алгоритмических методах компьютерных шахмат.
• 1951 – Алан Тьюринг первым опубликовал разработанную на бумаге программу, способную вести полноценную партию в шахматы (получившую название Турочамп ).
• 1952 – Дитрих Принц разрабатывает программу, решающую шахматные задачи.

	а	б	с	д	и	ж
6							6
5							5
4							4
3							3
2							2
1							1
	а	б	с	д	и	ж

Лос-Аламосские шахматы . В эту упрощенную версию шахмат в 1956 году играл MANIAC I. компьютер

• 1956 — Лос-Аламосские шахматы — первая программа, похожая на шахматы, разработанная Полом Стейном и Марком Уэллсом для MANIAC I. компьютера
• 1956 – Джон Маккарти изобретает алгоритм альфа-бета- поиска.
• 1957 - Разработаны первые программы, позволяющие полноценно играть в шахматы. Одна из них принадлежит Алексу Бернстайну. и один от российских программистов, использующих БЭСМ .
• 1958 – NSS становится первой шахматной программой, использующей алгоритм поиска альфа-бета.
• первая заслуживающая доверия программа Kotok-McCarthy публикуется 1962 – В Массачусетском технологическом институте .
• 1963 – Гроссмейстер Давид Бронштейн побеждает М-20, выполняющую раннюю шахматную программу.
• 1966–67 – сыгран первый шахматный матч между компьютерными программами. Московский институт теоретической и экспериментальной физики (ИТЭФ) побеждает Коток-Маккарти в Стэнфордском университете по телеграфу за девять месяцев.
• 1967 — Mac Hack VI , Ричард Гринблатт и др. вводит таблицы транспозиции и использует десятки тщательно настроенных эвристик выбора хода; это первая программа, победившая человека в турнирной игре. Mac Hack VI играл примерно на уровне C.
• 1968 – Чемпион Шотландии по шахматам Дэвид Леви заключает пари на 500 фунтов с пионерами искусственного интеллекта Джоном Маккарти и Дональдом Мичи , что ни одна компьютерная программа не выиграет у него шахматный матч в течение 10 лет.
• 1970 – Монти Ньюборн и Ассоциация вычислительной техники организуют первый чемпионат Северной Америки по компьютерным шахматам в Нью-Йорке.
• 1971 — Кен Томпсон , американский ученый-компьютерщик из Bell Labs и создатель операционной системы Unix, пишет свою первую программу для игры в шахматы под названием «шахматы» для самой ранней версии 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 , который транслируется по немецкому телевидению. Леви и Chess 4.8, работающие на CDC Cyber ​​176, самом мощном компьютере в мире, боролись с изнурительной ничьей в 89 ходов.
• 1980 – Компьютеры Fidelity выигрывают чемпионат мира по микрокомпьютерам каждый год с 1980 по 1984 год. В Германии компания Hegener & Glaser выпускает свой первый Mephisto шахматный компьютер . USCF запрещает компьютерам участвовать в человеческих турнирах, за исключением случаев, когда их представляют создатели шахматных систем. Учреждена премия Фредкина в размере 100 000 долларов создателю первой шахматной машины, победившей чемпиона мира по шахматам.
• 1981 – Крей Блиц выигрывает чемпионат штата Миссисипи с идеальным счетом 5–0 и рейтингом производительности 2258. В 4-м раунде он побеждает Джо Сентефа (2262) и становится первым компьютером, победившим мастера в турнирной игре, и первым компьютером, победившим мастера в турнирной игре. получить мастер-рейтинг.
• немецкой компании Hegener & Glaser 1984 - Линия специализированных шахматных компьютеров Mephisto начинает длинную серию побед (1984–1990) на чемпионате мира по микрокомпьютерам с использованием специализированных компьютеров, на которых работают программы ChessGenius и Rebel .
• 1986 - Software Country (см. Software Toolworks ) выпустила Chessmaster 2000 на основе движка Дэвида Киттингера, первое издание того, что должно было стать самой продаваемой в мире линейкой шахматных программ.
• 1987 — Фредерик Фридель и физик Матиас Вюлленвебер основали Chessbase , выпустив первую программу шахматной базы данных. Стюарт Кракрафт выпускает GNU Chess , один из первых « шахматных движков », поставляемый в комплекте с отдельным графическим интерфейсом пользователя (GUI) — Chesstool.
• 1988 — HiTech , разработанная Гансом Берлинером и Карлом Эбелингом , выигрывает матч у гроссмейстера Арнольда Денкера со счетом 3½–½. Дип Сот делит первое место с Тони Майлзом в чемпионате Software Toolworks Championship, опережая бывшего чемпиона мира Михаила Таля и нескольких гроссмейстеров, включая Сэмюэля Решевского , Уолтера Брауна и Михаила Гуревича . Он также побеждает гроссмейстера Бента Ларсена , что делает его первым компьютером, победившим гроссмейстера в турнире. Его рейтинг за выступление на этом турнире 2745 (по шкале USCF) был самым высоким, полученным компьютерным игроком.
• 1989 – Дип Сот разгромил Дэвида Леви в матче из 4 игр со счетом 0–4, положив конец его знаменитой серии ставок, начавшейся в 1968 году.
• 1990 - 25 апреля бывший чемпион мира Анатолий Карпов проиграл в сеансе одновременной игры шахматному компьютеру Mephisto Portorose M68030 компании Hegener & Glaser.
• 1991 - Шахматная машина, основанная на книге Эда Шредера « Бунтарь», выигрывает чемпионат мира по шахматам на микрокомпьютерах.
• 1992 — ChessMachine выигрывает 7-й чемпионат мира по компьютерным шахматам , впервые микрокомпьютер победил мэйнфреймы . МГ Джон Нанн выпускает «Секреты ладейных окончаний» , первую книгу, основанную на таблицах эндшпиля, разработанных Кеном Томпсоном .
• 1993 — Дип Сот-2 проигрывает четырёхматчевый матч против Бента Ларсена . Шахматные программы, работающие на персональных компьютерах, превзошли специализированные шахматные компьютеры Mephisto и выиграли чемпионат по микрокомпьютерам, что знаменует собой переход от специализированного шахматного оборудования к программному обеспечению на многофункциональных персональных компьютерах.
• 1995 — Fritz 3 , работающий на ПК Pentium с тактовой частотой 90 МГц, побеждает специальную шахматную машину Deep Thought-2 и программы, работающие на нескольких суперкомпьютерах, и выигрывает 8-й чемпионат мира по компьютерным шахматам в Гонконге. Это первый случай, когда шахматная программа, работающая на обычном оборудовании, побеждает специализированные шахматные машины и массивные суперкомпьютеры, что указывает на смещение акцента с грубой вычислительной мощности на алгоритмические улучшения в эволюции шахматных движков.
• 1996 – IBM Deep Blue матч из шести игр со проигрывает Гарри Каспарову счетом 2–4.
• 1997 – Deep(er) Blue , сильно модифицированная версия оригинала, выигрывает матч из шести игр у Гарри Каспарова со счетом 3,5-2,5.
• 2000 — Стефан Мейер-Кален и Рудольф Хубер разрабатывают универсальный шахматный интерфейс , протокол для графических интерфейсов для взаимодействия с движками, который постепенно станет основной формой, которую будут принимать новые движки.
• 2002 — Владимир Крамник сыграл вничью матч из восьми партий с Дипом Фрицем .
• 2003 — Каспаров сыграл вничью матч из шести игр с Deep Junior и матч из четырёх игр с X3D Fritz .
• 2004 — команда компьютеров ( Hydra , Deep Junior и Fritz ) побеждает со счетом 8½–3½ у сильной человеческой команды, сформированной Веселином Топаловым , Русланом Пономаревым и Сергеем Карякиным , имевшим средний рейтинг Эло 2681. Фабьен Летузи выпускает исходный код для Fruit 2.1, движок, вполне конкурентоспособный с лучшими движками с закрытым исходным кодом того времени. Это заставляет многих авторов пересматривать свои коды, включая новые идеи.
• 2005 – Рыбка выигрывает турнир IPCCC и очень быстро становится сильнейшим паровозом.
• 2006 — Чемпион мира Владимир Крамник терпит поражение от Дипа Фрица со счетом 4–2 .
• 2009 — Карманный Фриц . 4, работающий на смартфоне, выигрывает Copa Mercosur, международный турнир уровня мастеров, набрав 9½/10 и получив рейтинг производительности 2900. Группа российских программистов под псевдонимами публикует исходный код Ippolit, движка, который, по-видимому, сильнее Рыбки . Это становится основой двигателей Робболито и Айвенго, и многие авторы двигателей перенимают идеи из него.
• 2010 — Перед чемпионатом мира по шахматам 2010 Топалов готовится спаррингом против суперкомпьютера Blue Gene с 8192 процессорами, способными обрабатывать 500 триллионов (5 × 10 ¹⁴ ) операций с плавающей запятой в секунду. Rybka developer, Vasik Rajlich , accuses Ippolit of being a clone of Rybka.
• 2011 – ICGA лишает Рыбку титулов WCCC.
• 2017 — AlphaZero , цифровой автомат на основе нейронной сети, побеждает Stockfish со счетом 28–0 при 72 ничьих в матче из 100 игр.
• 2018 — эффективно обновляемая нейронная сеть изобретена Для компьютерных сёги (NNUE) .
• 2019 - Leela Chess Zero (LCZero v0.21.1-nT40.T8.610), шахматный движок, основанный на AlphaZero, побеждает Stockfish 19050918 в матче из 100 игр с окончательным счетом 53,5: 46,5 и выигрывает 15-й сезон TCEC .
• 2020 г. - ННЭУ добавлен в оценку Stockfish , заметно увеличив его силу.

Категории

Выделенное оборудование

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

• Красавица 1976 года
• Bebe, мощный побитовый процессор , 1980 г.
• ХайТек 1985
• ЧипТест 1985 г.
• Глубокая мысль 1987
• Deep Thought 2 (прототип Deep Blue)~1994 г.
• Глубокий синий 1996, 1997
• Hydra , предшественник назывался Brutus 2002 г.
• AlphaZero Google 2017 (для нейронных сетей использовались тензорные процессоры , но оборудование не предназначено специально для шахмат или игр)
  • MuZero 2019 (аналогично аппаратному обеспечению своего предшественника AlphaZero, не связанному с шахматами или, например, го), изучает правила шахмат.

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

Борис Дипломат (1979) дорожный шахматный компьютер

Fidelity Voice Chess Challenger (1979), первый говорящий шахматный компьютер

Duration: 28 seconds.0:28

Речевой вывод 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 , который может работать на двух движках:
  • «The King», который позже стал движком Chessmaster , также использовался в специализированном компьютере TASC R30.
  • Гидеон, версия 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.

ДОС-программы

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

• Шахматист 2000
• Колоссальные шахматы
• Фриц 1–3
• Гамбит Каспарова
• Мятежник
• Саргон
• Сократ II

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

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

• Георгий Адельсон-Вельский , советский и израильский математик и ученый-компьютерщик.
• Ганс Берлинер , американский ученый-компьютерщик и чемпион мира по шахматам по переписке, руководитель проекта HiTech (1988).
• Михаил Ботвинник , советский инженер-электрик и чемпион мира по шахматам, писал «Пионеру».
• Александр Брудно , российский ученый-компьютерщик, первым разработал алгоритм сокращения алфавита.
• Фэн-сюн Сюй , ведущий разработчик Deep Blue (1986–97)
• Профессор Роберт Хаятт разработал Cray Blitz и Crafty.
• Дэнни Копек , американский профессор компьютерных наук и международный мастер по шахматам, разработал тест Копека-Братко.
• Александр Кронрод , советский ученый-компьютерщик и математик.
• Профессор Монро Ньюборн , председатель комитета по компьютерным шахматам Ассоциации вычислительной техники.
• Клод Э. Шеннон , американский учёный-компьютерщик и математик.
• Алан Тьюринг , английский ученый-компьютерщик и математик.

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

Основная статья: Решение шахмат

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

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

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

Шахматные движки

Основная статья: Шахматный движок

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

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

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

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

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

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

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

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

См. также

• Список шахматного программного обеспечения
• История шахматных движков
• Компьютерные шашки
• Компьютер Го
• Компьютер Отелло
• Компьютерные сёги

Ссылки

В эту статью включен текст Chess Programming Wiki, доступный по лицензии CC BY-SA 3.0 .

Источники

• Сюй, Фэн-сюн (2002), За Deep Blue: создание компьютера, победившего чемпиона мира по шахматам , Princeton University Press , ISBN  0-691-09065-3
• Леви, Дэвид ; Ньюборн, Монти (1991), Как компьютеры играют в шахматы , Computer Science Press, ISBN  0-7167-8121-2
• Ньюборн, Монти (1975), Компьютерные шахматы , Academic Press, Нью-Йорк
• Новорожденный, Монти (1997), Каспаров против Deep Blue: компьютерные шахматы достигают зрелости , Springer, ISBN  0-387-94820-1 (Эта книга фактически охватывает компьютерные шахматы с первых дней до первого матча между Deep Blue и Гарри Каспаровым.)
• Нанн, Джон (2002), Секреты концовок без пешек , Gambit Publications , ISBN  1-901983-65-Х
• Шеннон, Клод Э. (1950), «Программирование компьютера для игры в шахматы» (PDF) , Философский журнал , Сер.7, Том. 41 (314), заархивировано из оригинала (PDF) 6 июля 2010 г. , получено 21 июня 2009 г.
• Освоение игры: история компьютерных шахмат в Музее истории компьютеров
• Хронология компьютерной шахматной истории Билла Уолла

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

• Новые архитектуры в компьютерных шахматах – диссертация о том, как создать шахматный движок
• Коулз, Л. Стивен (30 октября 2002 г.), Компьютерные шахматы: дрозофила искусственного интеллекта , Журнал доктора Добба
• Хуберман (Лисков), Барбара Джейн (1968), Программа для игры в шахматные эндшпили , Факультет компьютерных наук Стэнфордского университета, Технический отчет CS 106, Памятка Стэнфордского проекта искусственного интеллекта AI-65
• Лазар, Мэтью (2011). Грубая сила или интеллект? Медленный рост компьютерных шахмат ». Ars Technica .
• Новорожденный, Монти (1996). Исследования Каспарова , Труды симпозиумов Американского математического общества по прикладной математике: математические аспекты искусственного интеллекта, т. 55, стр. 175–205, 1998. На основе статьи, представленной на зимнем собрании AMS 1996 года, Орландо, Флорида, 9 января – 11, 1996.
• Новорожденный, Монти (2000). Вклад Deep Blue в искусственный интеллект , Анналы математики и искусственного интеллекта, т. 28, стр. 27–30, 2000 г.
• Новорожденный, Монти (2006). Тео и Осьминог на чемпионате мира по программам автоматического мышления 2006 г. , Сиэтл, Вашингтон, 18 августа 2006 г.
• Стиллер, Льюис (1996), Мультилинейная алгебра и шахматные эндшпили (PDF) , Беркли, Калифорния: Научно-исследовательский институт математических наук , Игры без шансов, публикации MSRI, том 29 , получено 21 июня 2009 г.

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

• Список рейтингов шахматных движков и игровых файлов в формате PGN
• Освоение игры: история компьютерных шахмат в Музее истории компьютеров
• Компьютерные шахматы ACM Билла Уолла
• «Компьютерные шахматы» Эдварда Уинтера
• Информация и ресурсы по компьютерным шахматам. Архивировано 18 января 2019 г. на Wayback Machine - блог после создания компьютерного шахматного движка.
• Защищая честь человечества , статья Тима Краббе о шахматах в «антикомпьютерном стиле».
• Руководство по таблицам эндшпиля
• GameDev.net - Шахматное программирование, Франсуа-Доминик Лараме. Часть 1. Архивировано 18 сентября 2011 г. на Wayback Machine 2. Архивировано 27 сентября 2011 г. на Wayback Machine 3. Архивировано 19 сентября 2011 г. на Wayback Machine 4. Архивировано 9 сентября 2011 г. -19 в Wayback Machine 5. Архивировано 20 сентября 2011 г. в Wayback Machine 6. Архивировано 7 августа 2011 г. в Wayback Machine.
• Страница компьютерной теории шахмат Колина Фрейна
• « Как REBEL играет в шахматы» Эда Шредера» (PDF) .   (268 КБ)
• «Играйте в шахматы с Богом». Архивировано 29 ноября 2012 г. на archive.today - за игру в шахматы против базы данных эндшпиля Кена Томпсона.
• Вики по шахматному программированию
• Форумы компьютерного шахматного клуба
• Сильнейшие компьютерные шахматные движки с течением времени

СМИ

• История компьютерных шахмат: взгляд на искусственный интеллект. Архивировано 14 июня 2006 г. в Wayback Machine . Полная лекция с участием Мюррея Кэмпбелла (проект IBM Deep Blue), Эдварда Фейгенбаума, Дэвида Леви , Джона Маккарти и Монти Ньюборна. в Музее компьютерной истории