Войти
Сенсорный шахматный компьютер 1990-х годов с ЖК-экраном Компьютерные шахматы включает как аппаратное обеспечение (выделенные компьютеры), так и программное обеспечение, способное играть в шахматы. Компьютерные шахматы предоставляют игрокам возможность тренироваться даже в отсутствие соперников-людей, а также использовать возможности для анализа, развлечения и тренировок.
Компьютерные шахматные приложения, которые играют на уровне мастера шахмат или выше, доступны на аппаратном уровне от суперкомпьютеров для смартфонов. Также доступны автономные игровые автоматы. Stockfish, GNU Chess, Fruit и другие бесплатные приложения с открытым исходным кодом доступны для различных платформ.
Компьютерные шахматные приложения, реализованные в аппаратном или программном бизнесе, используют иную парадигму, чем люди, для выбора своих ходов: они используют эвристические методы для построения, поиск и оценки деревьев, представляющих ходов из текущей позиции, и используются лучше всего выполнять такую последовательность во время игры. Такие деревья обычно довольно большие, от тысяч до миллионов узлов. Производить вычислений современных компьютеров, обрабатывать от десятков тысяч до сотен тысяч узлов или более в секунду, в сочетании с эвристиками расширения и сокращения, сужающими дерево до наиболее важных узлов, делают такой подход эффективным подходом.
Первыми шахматными машинами, способными играть в шахматы или сокращенные шахматные игры, были программы, работающие на цифровых компьютерах в начале эпохи электронных ламп (1950-е годы). Ранние программы играли настолько плохо, что их мог победить даже новичок. В течение 50 лет, в 1997 году, шахматные движки, работающие на суперкомпьютерах или специализированном оборудовании, были способны победить даже лучших игроков-людей. В 2010 году Монро Ньюборн, профессор компьютерных наук в Университета Макгилла, заявлено: «Наука свершилась». Тем не менее, решение шахмат в настоящее время невозможно для современных компьютеров из-за большого количества вариантов игры.
Компьютерная шахматная ИС на имя разработчика Франса Морша (см. Мефисто )Шахматные машины Программы / доступны в нескольких различных формах: как автономные шахматные машины (обычно микропроцессор, на котором выполняется шахматная программа, но иногда как специализированная машина), программы, работающие на стандартных Программы работают на всех, от суперкомпьютеров для смартфонов. Требования к оборудованию для программ минимальны: размер приложений на диске не большим несколькими мегабайт, используется несколько мегабайт памяти. доступно), и достаточно любого процессора с тактовой частотой 300 МГц или выше. ра, но достаточный объем памяти для хранения большой таблицы транспонирования (до нескольких гигабайт и более) более важен для силы игры, чем скорость процессора.
Большинство доступных коммерческих шахматных программ и машин предоставляют супергроссмейстерскую игровую силу (ELO 2700 или больше) и используют преимущества многоядерных и многопоточных компьютерных архитектурных ЦП. Лучшие, такие как Stockfish, программы превзошли даже игроков мирового уровня. Большинство шахматных движков взаимодействуют с графическим интерфейсом пользователя, например Winboard или Chessbase, а сила игры, контроль времени и другие параметры, связанные с производительностью, регулируются с помощью графического интерфейса. Большинство графических интерфейсов также позволяют игроку настраивать и редактировать позицию, возвращать ходы, использовать функцию «тренера», чтобы рекомендовать ход, когда игрок сомневается, и отображает анализ движка как игра прогрессирует.
Есть несколько шахматных движков, таких как Sargon, IPPOLIT, Stockfish, Crafty, Fruit и GNU Chess, которые можно загрузить (или получить исходный код иным способом) из Интернета бесплатно.
Возможно, наиболее распространенным типом шахматного программного обеспечения являются программы, которые просто играют в шахматы. Вы делаете ход на доске, и ИИ вычисляет и воспроизводит ответ, и вперед и назад, пока один игрок не уйдет. Иногда шахматный движок, который вычисляет ходы, и графический пользовательский интерфейс (GUI) являются отдельными программами. В графический интерфейс можно импортировать различные движки, чтобы вы могли играть против разных стилей. Движки часто имеют простой текстовый интерфейс командной строки, в то время как графические интерфейсы пользователя могут предлагать различные наборы элементов, стили плат или даже трехмерные или анимированные элементы. Последние движки или графические интерфейсы позволяют ограничить силу движка, чтобы у игрока было больше шансов на победу. Механизмы универсального шахматного интерфейса (UCI), такие как Fritz или Rybka, могут иметь встроенный механизм для снижения рейтинга Эло движка (через параметры UCI uci_limitstrength и uci_elo). Некоторые версии Fritz имеют режимы Handicap и Fun для текущего движка или изменения процента ошибок, которые он делает, или изменения его стиля. Фриц также имеет режим друга, в котором во время игры он соответствует уровню игрока.
Шахматные базы данных позволяют использовать поиск в большой библиотеке исторических партий, анализировать их, проверять статистику и вступить в репертуар. Chessbase (для ПК), пожалуй, самая распространенная программа для этого среди профессиональных игроков, но есть альтернативы, такие как Шахматная информационная база данных Шейна (Scid) для Windows, Mac или Linux, Chess Assistant для ПК, Chess PGN Master Герхарда Калаба для Android или Chess-Studio Джордано Виколи для iOS.
Такие программы, как Playchess, позволяют вам играть в игры против других игроков по Интернету.
Программы обучения шахматам обучают шахматам. Chessmaster проходил обучение от IM Джоша Вайцкина и GM Ларри Кристиансена. Стефан Мейер-Кален предлагает Shredder Chess Tutor, основанный на учебниках Step Роба Бруниа и Кор Ван Вейгердена. Чемпионы мира Магнус Карлсен из компании Play Magnus недавно выпустили приложение Magnus Trainer для Android и iOS. Chessbase содержит Fritz and Chesster для детей. Convekta имеет большое количество обучающих приложений, таких как CT-ART и его линейка Chess King, основанные на учебных пособиях Александра Калинина и Максима Блоха.
Существует также Программное обеспечение для решения шахматных задач.
После обнаружения проверки опровержения - применение альфа-бета-отсечения для оптимизации хода - в 1957 году команда из Университета Карнеги-Меллона предсказала, что компьютер победит чемпиона мира среди людей к 1967 году. Они не предвидели трудностей с определением правильного порядка для оценки ходов. Исследователи работали над улучшением способностей программ выявлять эвристику -цу, исследователи работали с необычно высокими показателями, которые нужно пересмотреть при оценке других ветвей, но в 1970-е годы большинство ведущих шахматистов считали, что компьютеры не скоро могут играть в Мастер уровень. В 1968 году международный мастер Дэвид Леви сделал знаменитую ставку, что ни один шахматный компьютер не сможет победить его в течение десяти лет, а в 1976 году старший мастер и профессор Психология Элиот Херст из Университета Индианы писал, что «единственная возможная компьютерная программа, которая могла бы выиграть одну игру против мастера, возможно, находящегося в пьяном оцепенении при одновременном проведении 50 игр». совершают грубую ошибку, которая случается раз в год ".
В конце 1970-х годов шахматные программы внезапно начали побеждать лучших игроков-людей. В год заявления Херста, Северо-Западный университет Шахматы 4.5 на уровне Пола Массона Американского чемпионата по шахматам класс B первый стал, кто выиграть человеческий турнир. Леви выиграл свою ставку в 1978 году, победив Шахматы 4.7, но он добился первой компьютерной победы над игроком Мастер-класса на турнирном уровне, выиграв одну из шести партий. В 1980 году Белль начала часто побеждать Мастерс.
Внезапное улучшение без ожидаемого прорыва удивило людей, которые не ожидали, что способность Белль проверять 100000 позиций в секунду - около восьми уровней - будет достаточно., создатели успешной микрокомпьютерной программы Sargon, подсчитали, что 90% улучшений пр оизошло за счет более высокой скорости и только 10% - за счет улучшения оценок. New Scientist заявил в 1982 году, что компьютеры «играют в ужасные шахматы... неуклюжие, неэффективные, расплывчатые и просто уродливые», но люди проиграли им, сделав «ужасные промахи, удивительные промахи, непонятные упущения, грубые» просчеты и подобное »гораздо чаще, чем они предполагали; «Короче, компьютеры побеждают в первую очередь благодаря их способности находить и использовать просчеты в человеческих инициативах».
В 1982 году шахматные программы на микрокомпьютерах могли оценивать до 1500 ходов в секунду и были такими же сильными, как шахматные программы для мэйнфреймов из пяти летми ранее смог победить почти всех игроков. Хотя они могли заглядывать вперед лишь на один или два слоя больше, чем они могли заглянуть вперед в середине 1970-х, это улучшило их игру больше, чем ожидали эксперты; «На первый взгляд незначительные улучшения», - пишет New Scientist. В обзоре SPOC в 1984 г. BYTE писал, что «компьютеры - мэйнфреймы, мини- и микропроцессоры - имеют тенденцию играть в уродливые, неэлегантные шахматы», но отмечает заявление Роберта Бирна о том, что «тактически они более свободны» Журнал описал SPOC как «современную шахматную программу» для IBM PC с «удивительно высоким» уровнем игры и оценил ее рейтинг USCF как 1700 (класс B).
На Чемпионат Северной Америки по шахматным шахматам в 1982 году, Монро Ньюборн предсказал, что шахматная программа может стать чемпионом мира в течение пяти лет; директор турнира и международный мастер Майкл Вальво предсказал десять лет «Спракленс предсказал 15»; Кен Томпсон предсказал более 20; и другие предсказывали, что это произойдет примерно в 2000 году. 517>Deep Thought в показательном матче. Deep Thought все еще был значительно ниже уровня чемпионата мира, как тогдашний чемпион мира Гарри Каспаров применил две сильные победы в 1989 году. Так продолжалось только в 1996 году в матче с IBM. Deep Blue, что Каспаров проиграл свою первую игру компьютеру на контроле времени турнира в Deep Blue - Каспаров, 1996, игра 1. Фактически, эта игра была первым разом, когда действующий чемпион мира проиграл компьютеру, используя обычный контроль времени. Каспаров перегруппировался, чтобы выиграть три и сыграть вничью в двух оставшихся геймов матча, что принесло убедительную победу.
В мае 1997 года обновленная версия Deep Blue победила Каспарова 3½ - 2½ в ответном матче. Документальный фильм, в основном о противостоянии, был снят в 2003 году под названием Игра окончена: Каспаров и машина. IBM хранит веб-сайт события.
Deep Blue против Каспарова, 1996, игра 1| a | b | c | d | e | f | g | h | ||
| 8 |            | 8 | |||||||
| 7 | 7 | ||||||||
| 6 | 6 | ||||||||
| 5 | 5 | ||||||||
| 4 | 4 | ||||||||
| 3 | 3 | ||||||||
| 2 | 2 | ||||||||
| 1 | 1 | ||||||||
| a | b | c | d | e | f | g | h | ||
С помощью вычислительной мощности и улучшенных функций производительности шахматные программы, работающие на сообществе в продаже рабочих станций, начали соперник топ-игроков. В 1998 году Мятежник 10 победил Вишванатана Ананда, который в то время занимал второе место в мире, со счетом 5–3. Однако в большинстве этих игр не играли при обычном контроле времени. Из восьми партий были блиц партиями (пять минут пять плюс секунд задержки Фишера (см. контроль времени ) на каждый ход); эти повстанцы выиграли 3–1. Две были полублиц-партии (по пятнадцать минут на каждую сторону), которых Rebel также выиграл (1½ - ½). Наконец, две партии были сыграны как обычные турнирные (сорок ходов за два часа, один час внезапной смерти); Здесь Ананд выиграл ½ - 1½. В быстрых компьютерах играли лучше, чем люди, но при котором обнаружен рейтинг игрока, преимущество которого было не очевидным.
В начале 2000-х коммерчески доступные программы, такие как Юниор и Фриц, могли сыграть вничью с бывшим чемпионом мира Гарри Каспаровым и чемпионом мира по классической классике Владимиром. Крамник.
В октябре 2002 года Владимир Крамник и Дип Фриц участвовали в матче из восьми игр Брейнз в Бахрейне, который закончился ничьей. Крамник выигрывал партии 2 и 3 с помощью «обычной» антикомпьютерной тактики - консервативной игры для долгосрочного преимущества, которое компьютер не может увидеть в поиске по дереву игр. Однако Фриц выиграл пятую партию после серьезной ошибки Крамника. Шестую игру комментаторы турнира назвали «зрелищной». Крамник, занимавший более выгодную позицию в раннем миттельшпиле, пожертвовать фигурой для достижения сильной тактической атаки - стратегия, которая, как известно, очень рискованна против компьютеров, которые наиболее сильно защищены от таких атак. Верный своей формой, Фриц нашел надежную защиту, и атака Крамника прекратилась, оставив его в плохой позиции. Крамник отказался от игры, считая, что позиция проиграна. Однако человеческий и компьютерный анализ после игры показал, что программа Фрица вряд ли смогла добиться победы, и Крамник фактически пожертвовал ничьей. Последние две игры завершились вничью. Учитывая обстоятельства, большинство комментаторов по-прежнему считают Крамника более сильным игроком в матче.
В январе 2003 года Гарри Каспаров играл в Младший, другую компьютерную программу для шахмат, в Нью-Йорке. Матч закончился со счетом 3–3.
В ноябре 2003 года Гарри Каспаров играл в X3D Fritz. Матч закончился со счетом 2–2.
В 2005 году Hydra, специализированный шахматный компьютер с нестандартным оборудованием и шестьюдесятью четырьмя процессорами, а также победителем 14-го IPCCC в 2005 году, занял седьмое место Майкл Адамс 5½ - ½ в матче из шести игр (хотя подготовка Адамса была менее тщательной, чем подготовка Крамника к серии 2002 года).
В ноябре - декабре 2006 г. чемпион мира Владимир Крамник играл Дип Фриц. На этот раз победил компьютер; матч закончился со счетом 2–4. Крамнику удалось просмотреть вводную книгу компьютера. В первой пяти партиих Крамник вывел игру в типичную «антикомпьютерную» позиционную борьбу. Он проиграл одну партию (проигнорировал мат в одной ) и в следующих четырех играх вничью. В финальной игре, пытаясь сыграть вничью, Крамник более агрессивной Сицилийская защита и был разгромлен.
Было предположение, что интерес к шахматному соревнованию человек-компьютер резко упадет в результате матча Крамник-Дип Фриц в 2006 году. По словам Ньюборна, например, «наука сделана».
Матчи человек-компьютер в шахматах показали, что лучшие компьютерные системы опередили чемпионов по шахматам среди людей в конце 1990-х. В течение 40 лет до этого была тенденция к тому, что лучшие машины набирали около 40 баллов в год в рейтинге Эло, в то время как лучшие люди получали только примерно 2 балла в год. Наивысший рейтинг, полученный компьютером в соревнованиях людей, был равен 2551 баллу USCF по USCF Deep Thought в 1988 году, и ФИДЕ больше не принимает результаты человеко-компьютерных исследований в свои рейтинговые списки. Для оценочных машин были созданы специализированные пулы Elo, предназначенные только для машин, но такие числа, хотя и похожи по внешнему виду, не должны сравниваться напрямую. В 2016 году Шведская ассоциация шахматных компьютеров оценила компьютерную программу Komodo на 3361.
Шахматные движки продолжают совершенствоваться. В 2009 году шахматные движки, работающие на более медленном оборудовании, достигли уровня grandmaster. Мобильный телефон выиграл турнир категории 6 с рейтингом производительности 2898: шахматный движок Hiarcs 13, работающий внутри Pocket Fritz 4 на мобильном телефоне phone HTC Touch HD выиграл турнир Copa Mercosur в Буэнос-Айресе, Аргентина с 9 победами и 1 розыгрышем 4–14 августа 2009 г. Pocket Fritz 4 выполняет поиск менее 20 000 позиций в секунду. Это контрастирует с такими суперкомпьютерами, как Deep Blue, которые просматривали 200 миллионов позиций в секунду.
Продвинутые шахматы - это разновидность шахмат, разработанная Каспаровым в 1998 году, когда человек играет против другого человека, и оба имеют доступ к компьютерам для увеличения своей силы. Получившийся в результате "продвинутый" игрок, по мнению Каспарова, сильнее человека или компьютера в одиночку, это было многократно доказано на соревнованиях по фристайл-шахматам.
Сегодняшние игроки склонны рассматривать шахматные машины как инструменты анализа, а не противников. Шахматный гроссмейстер Эндрю Солтис заявил в 2016 году, что «компьютеры слишком хороши», и что чемпион мира Магнус Карлсен не будет играть в компьютерные шахматы, потому что «он просто постоянно проигрывает, а нет ничего более удручающего, чем проигрыш, даже не будучи в игре. "
Со времен механических машин, которые играли ладьи и короли, и электрических машин, которые играли в другие игры, такие как hex (игра) в первые годы 20-го века ученые и теоретики стремились разработать процедурное представление о том, как люди изучают, запоминают, думают и применяют знания, а также игру в шахматы из-за ее устрашающей сложности. стала «дрозофилой искусственного интеллекта (ИИ)». Процедурное разрешение сложности стало синонимом мышления, и первые компьютеры, еще до эры шахматных автоматов, в народе назывались «электронными мозгами». Начиная со второй половины 20 века, было разработано несколько различных схем для представления знаний и мышления применительно к игре в шахматы (и другие игры, такие как шашки):
Использование «концы-и- означает« эвристика. Человек-шахматист может интуитивно определить оптимальные и способы их достижения независимо от количества необходимых ходов. Большинство игроков согласны с тем, что смотрит как минимум на пять ходов вперед (десять слоев ), когда это необходимо для хорошей игры. Обычные правила турнира дают каждому игроку в среднем по три минуты на ход. В среднем на каждую шахматную задачу приходится более 30 разрешенных ходов, поэтому компьютер должен изучить квадриллион возможностей, чтобы заглянуть вперед на десять уровней (пять полных ходов); тот, который мог бы исследовать миллион позиций в секунду, потребовал бы более 30 лет.
Самые ранние попытки процедурного представления игры в шахматы предшествовали электронной цифровой эре, но именно цифровой компьютер с хранимой программой давал возможность вычислять такую сложность. Клод Шеннон в 1949 году основил принципы алгоритмического решения шахмат. В этой статье представлена игра «деревом» или цифровой структурой данных выборов (ветвей), соответствующих ходам. Узлы дерева были позициями на доске в результате выбора хода. Невозможность изобразить всю шахматную партию путем построения дерева от первого до последнего хода стала очевидной: в шахматах в среднем 36 ходов на позиции, в среднем игра длится 35 ходов до отказа (60-80 ходов при игре. Мат, или другая ничья). Есть 400 агентов после первого хода каждого игрока, около 200 000 после двух ходов каждого и почти 120 миллионов после всего 3 ходов каждого. Поэтому был предложен ограниченный просмотр (поиск) до фиксированной глубины с последующим предметно-ориентированными знаниями для оценки конечных позиций. Результатом будет своего промежуточная позиция (позже именуемая «минимаксом») при наличии хороших ходов с обеих сторон, и ее оценка сообщит игроку о том, насколько хороши или плохи выбранные ходы. Операции поиска и сравнения на дереве хорошо подходят для компьютерных вычислений; представления тонких шахматных знаний в функции оценки не было. Ранние шахматные программы страдали в обеих областях: поиск в обширном дереве требовал вычислительных ресурсов, значительно превышающих доступные, на то, чтобы выяснить, какие шахматные знания были полезны и как их кодировать, потребовались бы десятилетия.
Ранняя парадигма поиска, называемая альфа-бета-отсечение, система определения верхней и нижней границ результатов поиска и поиска до совпадения границ, логарифмически уменьшала коэффициент ветвления дерева игры., но шахматные программы по-прежнему не могли выступить экспоненциальный взрыв дерева. Это естественным образом привело к так называемому «выборочному поиску», в котором используются шахматные знания (эвристика) для выбора предположительно хороших ходов из каждой позиции для поиска и удаления остальных без поиска. Но шахматы - это не игра, предназначенная для тематического изучения, и качество или плохое качество хода не может быть определено для многих ходов в игре, поэтому выборочный поиск часто приводит к отсечению лучшего хода или ходов. В течение следующих 25 лет, когда доминировала парадигма выборочного поиска, не было никакого прогресса. Лучшей программы, выпущенной за это время, был Mac Hack VI 1967 года; он играл примерно на том же уровне, что и средний любитель (класс C по рейтинговой шкале шахматной федерации США).
В 1974 году в программе Chess 4.0 Северо-Западного университета была впервые реализована другая парадигма поиска. Альтернатива, описанная в статье Шеннона 1949 года, называлась поиском по всей ширине или методом «грубой силы». При таком подходе ищутся все альтернативные ходы в узле, и ни одно из них не удаляется. Было значительно меньше, чем время, необходимое для применения наукоемкой эвристики для выбора нескольких из них, преимущество предотвращения преждевременного или случайного отсечения хороших ходов привело к более высокой производительности..
Разработчики компьютерной системы для игры в шахматы должны решить ряд фундаментальных вопросов реализации. К ним относится:
Компьютерные шахматные программы обычно ряд общих стандартов де-факто. Почти все современные программы могут читать и записывать игровые ходы как Portable Game Notation (PGN) и могут читать и записывать отдельные позиции как Forsyth - Edwards Notation (FEN). Старые шахматные программы часто понимают только длинную алгебраическую нотацию, но сегодня пользователи ожидают, что шахматные программы понимают стандартную алгебраическую шахматную нотацию.
. До конца 1990-х, программисты начали разрабатывать отдельные движки (с который вычисляет какие ходы самые сильные в позиции) или графический пользовательский интерфейс (GUI), с помощью игроку шахматную доску, которую он может видеть, и фигуры, которые можно перемещать. Движки передают свои ходы в графический интерфейс с помощью протокола, такого как Chess Engine Communication Protocol (CECP) или Universal Chess Interface (UCI). Разделив шахматные программы на эти две части, разработчики могут написать только пользовательский интерфейс или только движок, без необходимости писать обе части программы. (См. Также шахматные движки.)
Разработчики должны решить, подключить ли движок к начальной книге и / или эндшпилю tablebases или оставить это на усмотрение графического интерфейса пользователя.
Структура данных , используемая для представления каждой шахматной позиции, является ключом к производительности генерации ходов и оценки позиции. Методы включают элементы, хранящиеся в массиве («почтовый ящик» и «0x88»), элементы позиций, хранящиеся в списке («список элементов»), коллекции наборов битов для местоположений элементов («битовые доски »), и кодированные по Хаффману позиции для компактного длительного хранения.
Компьютерные шахматные программы рассматривают шахматные ходы как дерево игры. Теоретически они проверяют все ходы, затем все встречные ходы к этим ходам, затем все противодействующие им ходы и так далее, где каждый отдельный ход одного игрока называется «ply ». Эта оценка продолжается до тех пор, пока не достигнута максимальная глубина поиска или пока достигнута конечная позиция «листа» (например, мат). На каждом слое выбирается «лучший» ход игрока; один игрок пытается максимизировать счет, другой - уменьшить его. Посредством этого чередующегося будет достигнут один конкретный конечный узел, оценка которого искомое значение позиции. Его значение сохраняется до корня, и эта оценка становится оценкой позиции на доске. Этот процесс поиска называется «минимакс».
Наивная реализация этого подхода позволяет осуществлять поиск только на небольшую глубину за промежуток времени, поэтому были разработаны различные методы, которые значительно ускоряют поиск хороших ходов.
Первая статья по теме была написана Клодом Шенноном в 1950 году. Он предсказал две программы поиска которые будут раскручивать, он назвал «Тип A» и «Тип Б», до того, как кто-либо запрограммировал компьютер для игры в шахматы.
Программы типа A будут использовать подход «грубой силы », исследуя каждую возможную позицию для фиксированного количества ходов с использованием алгоритма минимаксного алгоритма. Шеннон считал это непрактичным по двум причинам.
Во-первых, имея примерно эффективных ходов в типичной реальной позиции, он ожидал, что поиск примерно 10 позиций, участвующих в просмотре трех ходов вперед для обеих сторон (шесть слоев ), потребует около шестнадцати минут, даже в «очень оптимистичном» случае, когда шахматный компьютер оценивал миллион позиций каждую секунду. (Для достижения этой скорости потребовалось около сорока лет.)
Во-вторых, он игнорировал проблему покоя, пытаясь оценить только позицию, которая находится в конце обмена частей или другая важная последовательность ходов (« линий »). Он ожидал, что адаптация типа A, чтобы справиться с этим, значительно увеличит количество позиций, которые необходимо рассмотреть, и еще больше замедлит программу.
Вместо того, чтобы тратить вычислительную мощность на проверку плохих или тривиальных ходов, Шеннон использует использовать в программах «типа B» два улучшения:
Это необходимо им заглянуть дальше («глубже») в наиболее важные линии за разумное время. Проверка временем подтвердила первый подход; все современные программы перед оценкой позиции используют поиск в состоянии покоя. От второго подхода отказались в пользу расширений поиска.
Адриан де Гроот взял интервью у нескольких шахматистов разной силы и пришел к выводу, что и мастера, и новички смотрят примерно от сорока до пятидесяти позиций, прежде чем решить, какой ход играть. Что делает первые намного лучше игроков, так это то, что они используют навыки распознавания образов, основанные на опыте. Это позволяет им исследовать одни линии гораздо глубже, чем другие, просто не указанные ходы, которые они считают плохими.
Еще одним доказательством этого, что игрок хорошим людям легче вспомнить позиции из настоящих шахматных партий, разбивая их на небольшое количество узнаваемых подпозиций, а не полностью случайные комбинации. из тех же частей. Напротив, у плохих игроков одинаковый уровень запоминания для обоих.
Проблема с типом B заключается в том, что она полагается на то, что программа способна решить, какие ходы достаточно хороши, чтобы их можно было рассмотреть («правдоподобно») в любой данной позиции, и это оказалось намного более сложная проблема. решить, чем ускорить поиск типа A с помощью превосходного оборудования и методов расширения поиска.
Программы полноразмерного поиска («грубая сила») выиграли по той простой, что их программы лучше играли в шахматы. Такие не пытались имитировать человеческий мыслительный процесс, но полагались на поиск по всей ширине альфа-бета и negascout. Большинство таких программ (включая все современные программы сегодня) также включают довольно ограниченную выборочную часть поиска, основную на поисках в состоянии покоя, как правило, расширения и отсечения (особенности нулевым ходом с 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 очков (статья Шеннона ), что мат перевешивает все, чтобы убедиться факторы (Леви и Новорожденный 1991 : 45). По соглашению, положительная оценка благоприятствует белым, а отрицательная - черным.
Помимо множества функций, учитывают многие факторы, такие как пешечная структура, тот факт, что пара слонов обычно стоит больше, централизованные фигуры стоят больше и так далее. Обычно учитывается защита королей, а также фаза игры (дебют, середина или эндшпиль).
Результатом функции оценки является единичный скаляр, квантованный в сантипешках или других единицах, который представляет собой взвешенную сумму различных описанных факторов. Оценка предположительно представляет или аппроксимирует значение поддерева под оцениваемым узлом, как если бы в нем был произведен поиск до завершения, то есть до конца игры. Во время поиска сравнивается с другими оценками, удаляя узлы, которые предоставляют или плохие ходы для любой стороны, чтобы получить узел, который в результате схождения представляет значение позиции с наилучшей игрой сторонних сторон.
Не существует аналитической или теоретической основы для определения того, что должно быть функцией оценки. И это не совсем специально. Десятки или отдельных факторов объединены в константу.
Игра в эндшпиле долгое время одной из самых слабых сторон шахматных программ из-за необходимости глубинного поиска. Некоторые игроки уровня магистра не смогли выиграть в позициях, где даже программы среднего уровня могут добиться победы.
Чтобы решить эту проблему, компьютеры были использованы для полного анализа некоторых позиций шахматного эндшпиля, начиная с короля и пешки против короля. Такие эндшпильные табличные базы данных с использованием формы ретроградного анализа, начиная с позиций, где известен окончательный результат (например, когда одна сторона была матирована), и какие другие позиции находятся на один шаг от них., то какие - один ход от тех и т.д. Кен Томпсон был пионером в этой области.
Результаты компьютерного анализа иногда удивляли людей. В 1977 году шахматная машина Belle Томпсона использовала основу таблицы эндшпиля для короля и ладьи против короля и ферзя и смогла нарисовать теоретически проигранный эндшпиль против нескольких мастеров (см. позиция Филидора # Королева против ладьи ). И это несмотря на обычную стратегию отсрочки, удерживающей защищающегося короля и ладью близко к другу как можно дольше. На просьбу объяснить причины некоторых шагов программы, Томпсон не смог этого сделать, кроме того, что база данных программы просто вернула лучшие ходы.
Большинство гроссмейстеров отказались играть против компьютера в эндшпиле ферзь против ладьи, но Уолтер Браун принял вызов. Была создана позиция ферзь против ладьи, в которой ферзь может выиграть за тридцать ходов при идеальной игре. Брауну было дано 2½ часа на то, чтобы сыграть пятьдесят ходов, чтобы была сила была заявлена ничья по правилу пятидесяти ходов. После сорока пяти ходов Браун на ничью, не имея возможности форсировать мат или выиграть ладью в течение следующих пяти ходов. В финальной позиции Брауну оставалось еще семнадцать ходов до мата, но не так уж и далеко до выигрыша ладьи. Браун изучил эндшпиль и через неделю снова на компьютере в другой позиции, в которой ферзь может выиграть за тридцать ходов. На этот раз он взял ладью на пятидесятом ходу, что дало ему выигрышную позицию (Levy Newborn 1991 : 144–48), (Nunn 2002 : 49).
В других позициях, которые долгое время считались выигранными, оказалось, что для победы требуется больше ходов против идеальной игры, чем позволяло шахматное правило пятидесяти ходов. Как следствие, на несколько лет официальные правила шахмат ФИДЕ были, чтобы увеличить количество ходов, разрешенных в этих окончаниях. Через некоторое время правило вернулось к пятидесяти ходам во всех позициях - таких позиций было обнаружено больше, что не имело никакого значения для обратной игры, поскольку они не могли разыграть позицию идеально.
За прошедшие годы были выпущены другие форматы базы данных эндшпилей, включая Edward Tablebase, De Koning Database и Nalimov Tablebase, которая используется многими шахматными программами, такими как Рыбка, Шреддер и Фриц. Доступны столы для всех позиций с шестью предметами. Некоторые семифигонные эндшпили проанализировали Марк Бурзучкий и Яков Коновал. Программисты, использующие суперкомпьютеры «Ломоносов» в Москве, составили основу шахматного стола для всех эндшпилей с или менее семью фигурами (исключены тривиальные позиции в эндшпиле, такие как шесть белых фигур против одинокого черного короля ). Во всех этих базах данных эндшпиля резолюции, что рокировка больше невозможна.
Многие таблицы не учитывают правило пятидесяти ходов, согласно которому может быть объявлена ничьей любым игроком игра, в которой проходит пятьдесят ходов без взятия или пешки. Это приводит к тому, что tablebase возвращает такие результаты, как «Принудительный мат за шестьдесят шесть ходов» в некоторых позициях, которые фактически были бы сыграны из-за правил пятидесяти ходов. Одна из причин этого заключается в том, что если правила шахмат должны быть еще раз, чтобы дать том времени для выигрыша таких позиций, нет необходимости восстанавливать все базы таблиц. Программе, использующую tablebases, также очень легко заметить и учесть `` особенность '', и в любом случае, если используется endgame tablebase, она выберет ход, который приведет к самому быстрому выигрышу (даже если он окажется неверным из пятидесяти. с идеальной игрой). Если играть противником, не использующим базу стола, такой выбор даст хорошие шансы на победу в течение пятидесяти ходов.
Табличные базы данных, используемые самые современные методы сжатия, требуют 7,05 ГБ места на жестком диске для всех пятиэлементных окончаний. Для покрытия всех шестиконечных концов требуется примерно 1,2 TB. Подсчитано, что база из семи частей требует от 50 до 200 ТБ дискового пространства.
Базы данных эндшпиля занимали видное место в 1999 году, когда Каспаров провел показательный матч в Интернете против остальной мир. Эндшпиль из семи фигур ферзя и пешки был достигнут, когда мировая команда боролась за ничью. Евгений Налимов, сгенерировав основу конечного стола из шести частей, где у сторон было по две ферзя, активно использовалось для облегчения анализа обеими сторонами.
Шахматные машины, как и люди, могут экономить время обработки, а также выбирать сильные вариации, изложенные мастерами, путем ссылки на вступительную книгу, хранящуюся в дисковой база данных. Вступительные книги охватывают начальные ходы игры до глубины, в зависимости от открытия и вариации, но до первых 10-12 ходов (20-24 слоев). Некоторые из них известны в средней игре, оценивают мастерами вариантов обычно лучше, чем общие эвристика программы.
Когда-то разыгрывание ходов вне книги, чтобы поставить шахматную программу на собственные ресурсы, могло быть эффективной стратегией, потому что шахматные дебютные книги были избирательны по отношению к стилю игры программы, а программы имели заметные слабости по сравнению с людьми, что сегодня уже не так. Начальные книги, хранящиеся в компьютерных базах данных, скорее всего, намного шире, чем даже у наиболее подготовленных людей, и ранний ход вне книги может привести к тому же компьютер обнаружит необычный ход в своей книге и поставит соперника в невыгодное положение.. Даже если это не так, нестандартная игра может быть намного лучше для тактически продуманных шахматных программ, чем для людей, которым приходится находить сильные ходы в незнакомом варианте за доской.
CEGT,, SSDF и ведение рейтинговых списков, позволяющих фанатам сравнивать мощность двигателей. Различные версии Stockfish, Komodo и Houdini доминируют в рейтинге IPON в конце 2010-х годов.
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 людьми tablebases.
Идея создания шахматной машины восходит к восемнадцатому веку. Примерно в 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 заявлено, что «Компьютеры не обладают чувством эстетики... Они делают то, что они считают объективно лучшим ходом в любой позиции, если даже это выглядит абсурдно, и они могут сыграть любую позицию. Двигаться, каким бы уродливым оно ни было ". Гроссмейстеры Андрестис и Сьюзан Полгар заявили, что компьютеры более склонны к отступлению, чем люди.
Программа AlphaZero использует вариант поиска по дереву Монте-Карло без развертывания. Королевское общество Венки Рамакришнан заявляет, что с Deep Blue «мы могли сказать, что победные программы были разработаны с (шахматными) алгоритмами, основанными на нашем собственном понимании - используя, например, опыт и советы великих великих мастеров... (Deep Blue) был просто тупой машиной»... (Но с AlphaZero) этот способ программирования кардинально меняется.
| a | b | c | d | e | f | |||
| 6 |  |  |  |  |  |  | 6 | |
| 5 |  |  | | | | | 5 | |
| 4 |  |  | | | | | 4 | |
| 3 | | | | | | | 3 | |
| 2 |  |  | | | | | 2 | |
| 1 |  |  |  |  |  |  | 1 | |
| a | b | c | d | e | f |
Выпущенная в 1977 году, «Борис» стал одним из первых шахматных компьютеров, получивших широкое распространение. Он работал на 8-битном микропроцессоре Fairchild F8 с ПЗУ всего 2,5 КБ и ОЗУ 256 байт. Эти шахматные игровые системы включают специальное оборудование с прибл. дата выпуска (за исключением неблагополучных микрокомпьютеров):
В конце 1970-х - начале 1990-х годов существовал конкурентный рынок шахматных компьютеров. Этот рынок изменился в середине 90-х, когда компьютеры с выделенными процессорами больше не могли конкурировать с быстрыми процессорами в систему компьютерах.
В последнее время некоторые любители использовали Multi Emulator Super System для запуска шахматных программ, созданных для компьютеров Fidelity или Mephisto Hegener Glaser на современных компьютерах. 64-битные операционные системы, такие как Windows 10. Автор Ребел, Эд Шредер адаптировал три из написанных им Hegener Glaser Mephisto для работы в качестве движков UCI.
Эти программы можно запускать в MS-DOS и работать в 64-битной Windows 10 с помощью эмуляторов, таких как DOSBox или Qemu :
Среди известных теоретиков компьютерных шахмат:
Перспективы полного решения шахмат обычно считают весьма отдаленными. Широко распространено предположение, что не существует в очень слабом смысле определения с помощью начальной позиции, и, следовательно, идеи решения шахмат в более сильном смысле практически пригодного для использования описания задачи. Стратегия идеальной игры для любой из сторон сегодня кажется нереальной. Однако не было доказано, что не может даже дешевого компьютерного метода определения лучшего хода в шахматной позиции или того, что существует альфа-бета-поисковик, работающий на современном компьютерном оборудовании, не может решить начальное положение в приемлемом количество времени. Сложность доказательства последнего заключается в том, что, хотя количество позиций на доске, которые могут произойти в ходе шахматной игры, огромно (порядка от 10 до 10), трудно исключить математические расчеты. вероятность того, что исходная позиция позволяет любой стороне принудительно выполнить сопряжение или трехкратное повторение после относительно небольшого числа ходов, и в этом случае дерево поиска может охватывать только очень маленькое подмножество множества позиций. Математически доказано, что обобщенные шахматы (шахматы, которые играют произвольно большим числом фигур на произвольно большой шахматной доске) представляют собой EXPTIME-complete, что означает, что определение выигранной стороны в произвольной позиции обобщенных позиций требует экспоненциальное время в худшем случае; однако этот теоретический результат не дает никакой нормы нижней границы работы, необходимой для решения обычных шахмат 8x8.
Minichess Мартина Гарднера, сыгранная на доске 5 × 5 примерно 10 возможными позициями доски, была решена; его теоретико-игровое значение равно 1/2 (т.е. ничья может быть принуждена любой стороной), и описана стратегия принуждения для этого результата.
Прогресс был достигнут и с другой стороны: по на 2012 год все эндшпили из 7 менее и менее фигур (2 короля и до 5 других фигур) решены.
«Шахматные движки» - это программа, которая вычисляет и определяет какие ходы наиболее эффективны в данной позиции. Авторы движка сосредотачиваются на улучшении своих игр, часто просто импортируются в графический пользовательский интерфейс (GUI), например кем-то другим. Механизмы взаимодействуют с графическим интерфейсом пользователя по стандартизированному протоколу, таким как Универсальный шахматный интерфейс, пример Стефаном Мейером-Каленом и Францем Хубером, или протокол обмена Chess Engine, шаблон Тимом Манном для GNU Chess и Winboard. Chessbase имеет собственный проприетарный протокол, а в свое время в Millennium 2000 был другой протокол, используемый для ChessGenius. Механизмы, разработанные для одной операционной системы и протокола, могут быть перенесены на другие ОС или протоколы.
В 1997 году Интернет-шахматный клуб выпустил свой первый Java-клиент для игры в шахматы онлайн с другими людьми внутри своего веб-сайта. Вероятно, это было одно из первых шахматных веб-приложений. Бесплатный шахматный сервер в Интернете вскоре последовал за ним с похожим клиентом. В 2004 году Международная федерация заочных шахмат открыла веб-сервер, чтобы заменить свою почтовую систему. Chess.com начал предлагать живые шахматы в 2007 году. Chessbase / Playchess уже давно имеет загруженный клиент, но в 2013 году у них появился веб-интерфейс.
Еще одно популярное веб-приложение - обучение тактике. Ныне несуществующий Chess Tactics Server открыл свой сайт в 2006 году, последовал за ним Chesstempo в следующем году, а Chess.com добавил свой Tactics Trainer в 2008 году. Chessbase добавила веб-приложение для обучения тактике в 2015 году.
Chessbase разместила свою базу данных по шахматным играм в 1998 году. Другой ранней базой данных по шахматным играм была Chess Lab, которая была запущена в 1999 году. New In Chess изначально пыталась конкурировать с Chessbase, выпустив программу NICBase для Windows 3.x, но в конце концов решили отказаться от программного обеспечения и вместо этого сосредоточиться на своей онлайн-базе данных, начиная с 2002 года.
Можно было играйте против движка Shredder онлайн с 2006 года. В 2015 году Chessbase добавила веб-приложение play Fritz, а также My Games для хранения своих игр.
Начиная с 2007 г., Chess.com предлагал своим клиентам содержание обучающей программы Chess Mentor онлайн. Лучшие GM, такие как Сэм Шенкленд и Уолтер Браун, внесли свой вклад.
 | Найдите компьютерные шахматы в Wiktiona ры, бесплатный способ. |
 | Wikimed ia Commons имеет материалы, относящиеся к шахматным компьютерам. |
