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

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

Эта статья является частью серии статей, посвященных
Шахматное программирование
Представительства Совета
0x88 Битборды
Шахматные компьютеры
Belle Темно-синий
Шахматные движки
Фриц Шахматы GNU Лила Чесс Зеро Stockfish
v т е

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

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

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

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

Доступность и сила игры [ править ]

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

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

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

Типы и особенности шахматного программного обеспечения [ править ]

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

Шахматные базы данных позволяют пользователям искать в большой библиотеке исторических партий, анализировать их, проверять статистику и составлять вступительный репертуар. Chessbase (для ПК), пожалуй, самая распространенная программа для этого среди профессиональных игроков, но есть альтернативы, такие как Shane's Chess Information Database (Scid) ^[2] для Windows, Mac или Linux, Chess Assistant ^[3] для ПК, ^{[4 ]} Chess PGN Master Герхарда Калаба для Android ^[5] или Chess-Studio Джордано Виколи для iOS. ^[6]

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

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

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

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

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

В конце 1970-х шахматные программы внезапно начали побеждать лучших игроков-людей. ^[8] Год заявления Херсто, Северо - Западный университет «s Шахматный 4,5 В настоящее время Массона Пола американского шахматного чемпионат класс B стал первым , чтобы выиграть турнир человеческого уровня. Леви выиграл свою ставку в 1978 году, победив Chess 4.7 , но он добился первой компьютерной победы над игроком мастер-класса на турнирном уровне, выиграв одну из шести партий. ^[9] В 1980 году Белль начала часто побеждать Мастерс. К 1982 году две программы играли на уровне мастера, а три были немного слабее. ^[8]

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

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

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

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

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

	а	б	c	d	е	ж	грамм	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	c	d	е	ж	грамм	час

Конечная позиция

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

В начале 2000-х коммерчески доступные программы, такие как Junior и Fritz, могли сыграть вничью с бывшим чемпионом мира Гарри Каспаровым и чемпионом мира по классической игре Владимиром Крамником .

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

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

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

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

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

Было предположение, что интерес к шахматным соревнованиям между людьми и компьютером резко упадет в результате матча Крамника и Дип Фрица в 2006 году. ^[14] Согласно Newborn, например, «наука сделана». ^[15]

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

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

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

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

Компьютерные методы [ править ]

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

• на основе поиска (минимакс / алфавит или выборочный поиск)
• основанный на знаниях (РАЙ)
• статистическая выборка (поиск по дереву Монте-Карло)
• генетические алгоритмы
• машинное обучение

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

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

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

В 1974 году в программе Chess 4.0 Северо-Западного университета впервые была реализована другая парадигма поиска. Альтернатива, описанная в статье Шеннона 1949 года, называлась поиском по всей ширине или методом «грубой силы». В этом подходе ищутся все альтернативные ходы в узле, и ни одно из них не удаляется. Они обнаружили, что время, необходимое для простого перебора всех ходов, было намного меньше, чем время, необходимое для применения наукоемкой эвристики для выбора лишь нескольких из них, а преимущество предотвращения преждевременного или случайного отсечения хороших ходов привело к существенно более высокой производительности. .

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

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

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

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

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

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

Представления Совета [ править ]

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

Методы поиска [ править ]

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

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

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

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

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

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

Шеннон предположил, что вместо того, чтобы тратить впустую вычислительную мощность на плохие или тривиальные ходы, в программах «типа B» использовались бы два улучшения:

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

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

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

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

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

Программы поиска по всей ширине («грубой силы») выиграли по той простой причине, что их программы лучше играли в шахматы. Такие программы не пытались имитировать человеческий мыслительный процесс, но полагались на полноформатный альфа-бета- поиск и поиск в режиме негашоу . Большинство таких программ (включая все современные программы сегодня) также включали довольно ограниченную выборочную часть поиска, основанную на поисках в состоянии покоя, и обычно расширения и отсечения (особенно отсечение нулевого хода с 1990-х годов), которые запускались на основе определенных условий при попытке чтобы отсеять или уменьшить явно плохие ходы (ходы истории) или исследовать интересные узлы (например, проверить расширения, проходные пешки на седьмом ряду, так далее.). Однако триггеры расширения и сокращения нужно использовать очень осторожно. Слишком много времени, и программа тратит слишком много времени на поиск неинтересных позиций. Если обрезать слишком много, есть риск вырезать интересные узлы. Шахматные программы различаются по тому, как и какие типы правил сокращения и расширения включены, а также в функции оценки. Некоторые программы считаются более избирательными, чем другие (например, Deep Blue был известен как менее избирательный, чем большинство коммерческих программ, потому что они могли позволить себе выполнять более полный поиск по всей ширине), но все они имеют базовый поиск по всей ширине в качестве основы и у всех есть некоторые селективные компоненты (Q-поиск, сокращение / расширение).

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

Эвристика поиска и другие оптимизации [ править ]

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

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

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

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

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

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

Оценка листа [ править ]

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

Функции оценки обычно оценивают позиции с точностью до сотых долей пешки (называемой центипедом) и рассматривают материальную ценность наряду с другими факторами, влияющими на силу каждой стороны. При подсчете материала для каждой стороны типичные значения фигур: 1 очко за пешку , 3 очка за коня или слона , 5 очков за ладью и 9 очков за ферзя . (См. Раздел « Относительная ценность шахматной фигуры» .) Королю иногда дают произвольно высокое значение, например 200 очков ( статья Шеннона ), чтобы гарантировать, что мат перевешивает все другие факторы ( Levy & Newborn 1991).: 45). По соглашению, положительная оценка благоприятствует белым, а отрицательная - черным.

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

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

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

Таблицы для эндшпиля [ править ]

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

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

Результаты компьютерного анализа иногда удивляли. В 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]}Во всех этих базах данных эндшпиля предполагается, что рокировка больше невозможна.

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

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

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

Открытие книги [ править ]

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

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

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

CEGT , ^[30] CSS , ^[31] SSDF , ^[32] и WBEC ^[33] поддерживают списки рейтингов, позволяющие фанатам сравнивать мощность двигателей. Различные версии Stockfish, Komodo и Houdini доминируют в рейтинге IPON в конце 2010-х годов.

CCRL (Computer Chess Рейтинг Lists) является организацией, тесты компьютерных движков " силы , играя программу друг против друга. CCRL была основана в 2006 году для продвижения компьютерно-компьютерной конкуренции и внесения результатов в рейтинговый список. ^[34]

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

История [ править ]

Докомпьютерный век [ править ]

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

Эра раннего программного обеспечения: выборочный поиск [ править ]

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

Более поздняя эпоха программного обеспечения: полноформатный поиск [ править ]

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

Расцвет шахматных машин [ править ]

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

Революция микрокомпьютеров [ править ]

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

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

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

Следующее поколение: нейронные сети и поиск по дереву Монте-Карло [ править ]

Программа AlphaZero использует вариант поиска по дереву Монте-Карло без развертывания. ^[37] The Royal Society «S Venki Ramakrishnan утверждает , что с Deep Blue,«мы могли бы сказать , что победившие программы были разработаны с (шахматы) алгоритмы , основанные на собственном понимании - с использованием, в данном случае, опыт и советы высшего рояле мастера ... (Deep Blue) был просто тупой машиной ... (Но с AlphaZero) этот способ программирования кардинально меняется. ^[38]

Хронология [ править ]

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

• 1956 - Лос-Аламосские шахматы - первая программа для игры в шахматы, разработанная Полом Штайном и Марком Уэллсом для компьютера MANIAC I.
• 1956 - Джон Маккарти изобретает алгоритм альфа-бета- поиска.
• 1957 - Разработаны первые программы, которые могут играть в шахматы полностью, одна Алексом Бернштейном ^[41], а другая русскими программистами, использующими БЭСМ .
• 1958 - NSS становится первой шахматной программой, использующей алгоритм альфа-бета поиска.
• 1962 - В Массачусетском технологическом институте издается первая заслуживающая доверия программа « Коток-Маккарти» .
• 1963 - гроссмейстер Давид Бронштейн побеждает М-20, выполняя раннюю шахматную программу. ^[42]
• 1966–67 - Проведен первый шахматный матч между компьютерными программами. Московский институт теоретической и экспериментальной физики (ИТЭФ) побеждает Котока-Маккарти в Стэнфордском университете по телеграфу за девять месяцев.
• 1967 - Mac Hack VI , Ричард Гринблатт и др. вводит таблицы транспонирования и использует десятки тщательно настроенных эвристик выбора хода; это первая программа, которая побеждает человека в турнирной игре. Mac Hack VI играл на уровне C.
• 1968 - Шотландский чемпион по шахматам Дэвид Леви делает ставку на 500 фунтов с пионерами искусственного интеллекта Джоном Маккарти и Дональдом Мичи, что никакая компьютерная программа не выиграет у него шахматный матч в течение 10 лет.
• 1970 - Монти Ньюборн и Ассоциация вычислительной техники организуют первый Североамериканский чемпионат по компьютерным шахматам в Нью-Йорке.
• 1971 - Кен Томпсон , американский ученый-компьютерщик из Bell Labs и создатель операционной системы Unix, пишет свою первую шахматную программу под названием «шахматы» для самой ранней версии Unix . ^[43]
• 1974 - Дэвид Леви , Бен Миттман и Монти Ньюборн организуют первый чемпионат мира по компьютерным шахматам , выигранным российской программой « Каисса» .
• 1975 - После почти десятилетия лишь незначительного прогресса с момента пика Гринблатта MacHack VI в 1967 году, Northwestern University Chess 4.5 представляет собой поиск по всей ширине, нововведения в битбордах и итеративном углублении. Также была восстановлена ​​таблица транспонирования, впервые увиденная в программе Гринблатта. Таким образом, это была первая программа с интегрированной современной структурой, которая стала моделью для всего будущего развития. Chess 4.5 хорошо играл в классе B и в том году выиграл 3-й чемпионат мира по компьютерным шахматам. Шахматы Северо-Западного университета и его потомки доминировали в компьютерных шахматах до эры компьютерных шахматных машин в начале 80-х.
• 1976 - В декабре канадский программист Питер Р. Дженнингс выпускает Microchess , первую продаваемую игру для микрокомпьютеров. ^[44]

• 1977 - В марте Fidelity Electronics выпускает Chess Challenger , первый специализированный шахматный компьютер, который будет продан. Международная шахматная ассоциация Computer была основана шахматными программистами организовать компьютерные шахматные чемпионаты и отчет об исследованиях и усовершенствования по компьютерным шахматам в своем журнале. Также в том же году Applied Concepts выпустили Boris , специальный шахматный компьютер в деревянном ящике с пластиковыми шахматными фигурами и складной доской.
• 1978 - Дэвид Леви выигрывает ставку, сделанную 10 годами ранее, победив Chess 4.7 в матче из шести партий со счетом 4½ – 1½. Победа компьютера в четвертой игре - первое поражение человеческого мастера в турнире. ^[9]
• 1979 - Фредерик Фридель организует матч между IM Дэвидом Леви и Chess 4.8 , который транслируется по немецкому телевидению. Levy and Chess 4.8, работающая на CDC Cyber ​​176, самом мощном компьютере в мире, провела изнурительную ничью из 89 ходов.
• 1980 - Компьютеры Fidelity выигрывают чемпионаты мира по микрокомпьютерам каждый год с 1980 по 1984 год. В Германии Hegener & Glaser выпускает свой первый специализированный шахматный компьютер Mephisto . USCF запрещает компьютерам участвовать в турнирах среди людей, за исключением случаев, когда они представлены создателями шахматных систем. ^[45] Учреждена премия Фредкина, предлагающая 100 000 долларов создателю первой шахматной машины для победы над чемпионом мира по шахматам.
• 1981 - Cray Blitz выигрывает чемпионат штата Миссисипи с идеальным счетом 5–0 и рейтингом производительности 2258. В 4-м раунде он побеждает Джо Зентефа (2262) и становится первым компьютером, победившим мастера в турнирной игре, и первым компьютером, который получить рейтинг мастера.
• 1984 - Линия специализированных шахматных компьютеров Mephisto немецкой компании Hegener & Glaser начинает длинную серию побед (1984–1990) в Чемпионате мира по микрокомпьютерам с использованием специализированных компьютеров с программами ChessGenius и Rebel .
• 1986 - Software Country (см. Software Toolworks ) выпустила Chessmaster 2000 на базе движка Дэвида Киттингера, первое издание того, что должно было стать самой продаваемой линией шахматных программ в мире.
• 1987 - Фредерик Фридель и физик Маттиас Вюлленвебер основали Chessbase , выпустив первую программу шахматной базы данных. Stuart Cracraft выпускает GNU Chess , один из первых « шахматных движков », который будет связан с отдельным графическим пользовательским интерфейсом (GUI), chesstool. ^[46]
• 1988 - HiTech , разработанный Гансом Берлинером и Карлом Эбелингом , выигрывает матч у гроссмейстера Арнольда Денкера 3½ – ½. Deep Thought делит первое место с Тони Майлзом на чемпионате Software Toolworks Championship, опережая бывшего чемпиона мира Михаила Таля и нескольких гроссмейстеров, включая Самуэля Решевского , Уолтера Брауна и Михаила Гуревича . Он также побеждает гроссмейстера Бента Ларсена , что делает его первым компьютером, победившим гроссмейстера на турнире. Его рейтингза результативность в этом турнире 2745 (по шкале USCF) было самым высоким показателем, полученным компьютерным игроком. ^{[47] [48]}
• 1989 - Deep Thought уничтожает Дэвида Леви в матче из 4 игр 0–4, положив конец его знаменитой серии ставок, начавшейся в 1968 году.
• 1990 - 25 апреля бывший чемпион мира Анатолий Карпов проиграл в сеансе одновременной игры шахматному компьютеру Mephisto Portorose M68030 компании Hegener & Glaser. ^[49]
• 1991 - ChessMachine на основе повстанца Эда Шредера выигрывает чемпионат мира по шахматам на микрокомпьютерах.
• 1992 - ChessMachine выигрывает 7-й чемпионат мира по компьютерным шахматам , впервые микрокомпьютер превосходит мэйнфреймы . МГ Джон Нанн выпускает « Секреты ладейных окончаний» , первую книгу, основанную на таблицах эндшпиля, разработанных Кеном Томпсоном .
• 1993 - Deep Thought-2 проигрывает Бенту Ларсену в матче из четырех игр . Шахматные программы, работающие на персональных компьютерах, превосходят специализированные шахматные компьютеры Мефисто, чтобы выиграть чемпионат по микрокомпьютерам, ознаменовав переход от специализированного шахматного оборудования к программному обеспечению на многоцелевых персональных компьютерах.
• 1995 - Fritz 3 , работающий на ПК Pentium с тактовой частотой 90 МГц, превосходит специализированную шахматную машину Deep Thought-2 и программы, работающие на нескольких суперкомпьютерах, чтобы выиграть 8-й чемпионат мира по компьютерным шахматам в Гонконге. Это первый случай, когда шахматная программа, работающая на стандартном оборудовании, побеждает специализированные шахматные машины и огромные суперкомпьютеры, указывая на смещение акцента с грубой вычислительной мощности на алгоритмические улучшения в эволюции шахматных машин.
• 1996 - Deep Blue из IBM проигрывает Гарри Каспарову матч из шести игр со счетом 2–4.
• 1997 - Deep (er) Blue , сильно модифицированная версия оригинала, выигрывает матч из шести партий против Гарри Каспарова со счетом 3,5–2,5.
• 2000 - Стефан Мейер-Кален и Рудольф Хубер разрабатывают универсальный шахматный интерфейс , протокол для взаимодействия графических интерфейсов с движками, который постепенно станет основной формой, которую будут принимать новые движки.
• 2002 - Владимир Крамник проводит вничью матч из восьми против Deep Fritz .
• 2003 - Каспаров проводит вничью матч из шести против Deep Junior и из четырех игр против X3D Fritz .
• 2004 г. - команда компьютеров ( Hydra , Deep Junior и Fritz ) выигрывает 8½ – 3½ у довольно сильной команды людей, сформированной Веселином Топаловым , Русланом Пономаревым и Сергеем Карякиным , которые имели средний рейтинг Эло 2681. Фабьен Летузей сообщает источник код для Fruit 2.1, движка, вполне конкурентоспособного с лучшими движками с закрытым исходным кодом того времени. Это заставляет многих авторов пересматривать свой код, включая новые идеи.
• 2005 - Рыбка выигрывает турнир IPCCC и очень быстро становится сильнейшим локомотивом. ^[50]
• 2006 - чемпион мира Владимир Крамник терпит поражение от Deep Fritz со счетом 4: 2 .
• 2009 - Pocket Fritz 4 работает на смартфоне, выигрывает Copa Mercosur, международный турнир уровня мастеров, 9½ / 10, получив рейтинг производительности 2900. ^[18] Группа русских программистов под псевдонимом публикует исходный код Ippolit, движка, который кажется более мощным. чем Рыбка . Это становится основой для двигателей Robbolito и Ivanhoe, и многие авторы двигателей перенимают идеи из него.
• 2010 - Перед чемпионатом мира по шахматам 2010 Топалов готовится к спаррингу против суперкомпьютера Blue Gene с 8 192 процессорами, способными выполнять 500 триллионов (5 × 10 ¹⁴ ) операций с плавающей запятой в секунду. ^[51] Разработчик Rybka, Васик Райлих, обвиняет Ипполита в том, что он является клоном Рыбки.
• 2011 - ICGA лишает Рыбку титулов WCCC. ^{[52] [53]}
• 2017 - AlphaZero , цифровой автомат на основе нейронной сети, побеждает Stockfish со счетом 28–0 при 72 ничьих в матче из 100 игр.
• 2019 - Лила Чесс Зеро (LCZero v0.21.1-nT40.T8.610) побеждает Stockfish 19050918 в матче из 100 игр с 53,5 до 46,5 за титул 15 сезона TCEC . ^[54]

Категории [ править ]

Выделенное оборудование [ править ]

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

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

Коммерческие выделенные компьютеры [ править ]

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

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

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

Программы DOS [ править ]

Эти программы можно запускать в MS-DOS и в 64-битной Windows 10 с помощью эмуляторов, таких как DOSBox или Qemu : ^[59]

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

Известные теоретики [ править ]

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

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

Решение шахмат [ править ]

Перспективы полного решения шахмат обычно считаются весьма отдаленными. Широко распространено предположение о том, что не существует недорогого в вычислительном отношении метода решения шахмат даже в очень слабом смысле определения с уверенностью значения начальной позиции и, следовательно, идеи решения шахмат в более сильном смысле получения практически пригодного для использования описания задачи. Стратегия идеальной игры для обеих сторон сегодня кажется нереальной. Однако не было доказано, что не существует дешевого в вычислительном отношении способа определения лучшего хода в шахматной позиции или даже того, что традиционный поисковик альфа-бетаработа на современном компьютерном оборудовании не могла решить исходную позицию за приемлемый промежуток времени. Сложность доказательства последнего заключается в том, что, хотя количество позиций на доске, которые могут произойти в ходе шахматной игры, огромно (порядка от 10 ^{43 [61]} до 10 ⁴⁷ ), это сложно. чтобы исключить с математической достоверностью возможность того, что начальная позиция позволяет любой из сторон принудительно выполнить мат или трехкратное повторение после относительно небольшого количества ходов, и в этом случае дерево поиска может охватывать только очень небольшое подмножество набора возможных позиций. Математически доказано, что обобщенные шахматы(шахматы, играемые с произвольно большим количеством фигур на произвольно большой шахматной доске) являются EXPTIME-полными , ^[62] означая, что определение выигравшей стороны в произвольной позиции обобщенных шахмат в худшем случае доказуемо занимает экспоненциальное время; однако этот теоретический результат не дает нижней границы объема работы, необходимой для решения обычных шахмат 8x8.

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

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

Шахматные машины [ править ]

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

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

В 1997 году Internet Chess Club выпустил свой первый клиент Java для игры в шахматы онлайн против других людей в своем веб-браузере. ^[63] Вероятно, это было одно из первых шахматных веб-приложений. Вскоре после этого появился бесплатный шахматный сервер в Интернете с похожим клиентом. ^[64] В 2004 году Международная федерация заочных шахмат открыла веб-сервер, чтобы заменить свою электронную почту. ^[65] Chess.com начал предлагать живые шахматы в 2007 году. ^{[66] У} Chessbase / Playchess давно был загружаемый клиент, но к 2013 году у них появился веб-интерфейс. ^[67]

Еще одно популярное веб-приложение - тренировка тактики. Ныне несуществующий Chess Tactics Server открыл свой сайт в 2006 году ^[68], затем Chesstempo в следующем году ^[69], а Chess.com добавили свой Tactics Trainer в 2008 году. ^[70] Chessbase добавила веб-приложение для обучения тактике в 2015 году. ^{[ 71]}

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

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

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

См. Также [ править ]

• Computer Go
• Компьютерные шашки
• Компьютер Отелло
• Компьютерные сёги

Заметки [ править ]

Ссылки [ править ]

Источники [ править ]

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

Дальнейшее чтение [ править ]

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

Внешние ссылки [ править ]

Поищите компьютерные шахматы в Викисловаре, бесплатном словаре.

Викискладе есть медиафайлы, связанные с шахматными компьютерами .

• Список рейтингов шахматного движка и файлы игры в формате PGN
• Освоение игры: история компьютерных шахмат в Музее компьютерной истории
• ACM Computer Chess Билла Уолла
• Информация и ресурсы по компьютерным шахматам - блог после создания компьютерного шахматного движка
• В защиту чести человечества , статья Тима Краббе об " антикомпьютерных " шахматах
• Руководство по таблицам для эндшпиля
• GameDev.net - Шахматное программирование Франсуа-Доминика Лараме Часть 1 2 3 4 5 6
• Страница теории компьютерных шахмат Колина Фрейна
• « » Как REBEL играет в шахматы «Эда Шредера» (PDF) . (268 КБ)
• «Играй в шахматы с Богом» - за игру в шахматы по базе данных эндшпилей Кена Томпсона.
• Вики по шахматному программированию
• Форумы компьютерных шахматных клубов
• Сильнейшие компьютерные шахматные движки с течением времени

СМИ [ править ]

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