Компьютерные шахматы — популярный термин из области исследования искусственного интеллекта, означающий создание программного обеспечения и специальных компьютеров для игры в шахматы. Также термин «компьютерные шахматы» употребляется для обозначения игры против компьютерной шахматной программы, игры программ между собой. Начиная с 2000-х годов даже сильнейшие гроссмейстеры не имеют никаких шансов в противостоянии с шахматными программамиCheckmate, Human: How Computers Got So Good at Chess .
История
История шахматных машин старше, чем история компьютеров. Идея создать машину, играющую в шахматы, датируется ещё восемнадцатым веком. Около 1769 года появился шахматный автомат «Механический турок». Он был предназначен для развлечения королевы Марии-Терезии. Машина действительно неплохо играла — внутри неё находился сильный шахматист, который и делал ходы.
Создание механических шахматных автоматов прекратилось с появлением цифровых компьютеров в середине XX века. В 1951 году Алан Тьюринг написал алгоритм Turochamp, с помощью которого машина могла бы играть в шахматы, только в роли машины выступал сам изобретатель. Этот нонсенс даже получил название — «бумажная машина Тьюринга». Человеку требовалось более получаса, чтобы сделать один ход. Алгоритм был довольно условный, и сохранилась даже запись партии, где «бумажная машина» Тьюринга проиграла одному из его коллегAlan Turing vs Alick Glennie // «Turing Test», 1952. Из-за отсутствия доступа к компьютеру программа ни разу не проверялась в работе.
Примерно в это же время, в 1951 году, математик Клод Шеннон написал свою первую статью о шахматном программировании. Он писал: «Хотя, возможно, это и не имеет никакого практического значения, сам вопрос представляется теоретически интересным, и будем надеяться, что решение этой задачи послужит толчком для решения других задач аналогичной природы и большего значения». Шеннон также отметил теоретическое существование лучшего хода в шахматах и практическую невозможность его найти.
Следующим шагом в развитии шахматного программирования стала разработка в ядерной лаборатории Лос-Аламоса в 1952 году на компьютере MANIAC I c тактовой частотой 11 кГц шахматной программы для игры на доске 6x6, без участия слонов. Известно, что этот компьютер сыграл одну партию против сильного шахматиста, она продолжалась 10 часов и закончилась победой шахматиста. Ещё одна партия была сыграна против девушки, которая недавно научилась играть в шахматы. Машина победила на 23-м ходу, для своего времени это было большое достижение.
В 1957 году Алексом Бернштейном была создана первая программа для игры на стандартной шахматной доске и при участии всех фигурEarly Computer Chess Programs // Bill Wall’s Wonderful World of Chess.
Важное событие для компьютерных шахмат произошло в 1958 год, когда Аллен Ньюэлл, и Герберт Саймон разработали алгоритм уменьшения дерева поиска, названный «альфа-бета-отсечение»Computer Chess History by Bill Wall , на основе которого построены функции поиска всех сильных современных программ.
В 1967 году в матче из четырёх партий программа, созданная в Институте теоретической и экспериментальной физики (ИТЭФ), обыграла шахматную программу Стэнфордского университета со счётом 3-1. По оценкам гроссмейстеров, игравших с программой, она играла в силу третьего шахматного разряда.
На 1-м Чемпионате мира по шахматам среди компьютерных программ в августе 1974 года в Стокгольме (Швеция) программа «Каисса», созданная в 1971 году сотрудниками Института проблем управления АН СССР, выиграла все четыре партии и стала первым чемпионом мира среди шахматных программ, обогнав программы «Chess 4», «Chaos» и «Ribbit», набравших по 3 очка. В первенстве приняли участие 13 машин из 8 стран мира, передававшие свои ходы в зал проведения первенства оператору по телефону.
Первой же машиной, которая достигла уровня шахматного мастера, была , законченная в 1983 году Джо Кондоном и Кеном Томпсоном. Belle был первым компьютером, спроектированным только для игры в шахматы. Его официальный рейтинг Эло был 2250, таким образом, это была самая сильная шахматная машина своего времени.
В 1994 году Гарри Каспаров проиграл программе Fritz 3 турнирную блиц-партию в Мюнхене. Программа также выиграла у Вишванатана Ананда, Бориса Гельфанда и Владимира Крамника. Гроссмейстер Роберт Хюбнер отказывался играть против программы и автоматически проиграл. Каспаров сыграл второй матч с Fritz и победил с 4 выигрышами и 2 ничьими.
В феврале 1996 года Гарри Каспаров победил шахматный суперкомпьютер Deep Blue со счётом 4-2. Этот матч примечателен тем, что первую партию выиграл Deep Blue, автоматически став первым компьютером, победившим чемпиона мира по шахматам в турнирных условиях. Deep Blue вычислял 50 миллиардов позиций каждые три минуты. В Deep Blue было 200 процессоров. С тех пор шахматные энтузиасты и компьютерные инженеры создали много шахматных машин и компьютерных программ.
В 1997 году Deep Blue победил в матче-реванше (2 победы, 3 ничьих, 1 поражение) и стал первым компьютером, одолевшим сильнейшего шахматиста мира. Отыграться Каспаров уже не смог, потому что IBM отказалась от дальнейших соревнований, посчитав миссию выполненной.
Шахматные компьютеры сейчас доступны по очень низкой цене. Появилось много программ с открытыми кодами, в частности Crafty, Fruit и GNU Chess, которые можно свободно загрузить из Интернета и которые могут победить многих профессиональных шахматистов. Лучшие коммерческие и бесплатные программы, например, Shredder, Fritz или Komodo уже намного превысили уровень людей-чемпионов. Движок с открытым кодом Stockfish находится на высоких местах в таких компьютерных рейтинг-листах, как CEGT, CCRL, SCCT и CSS, благодаря совместной разработке и тестированию многих людей.
Мотивация Первыми мотивами для компьютеризации шахмат было желание развлечься, создать программы для компьютерных шахматных турниров и провести научное исследование, которое позволило бы глубже понять познавательную способность человека. Для первых двух целей компьютерные шахматы имели феноменальный успех: от первых попыток к созданию шахматной программы, которая могла на равных соперничать с лучшими шахматистами, прошло менее пятидесяти лет.
Александр Кронрод определил роль компьютерных шахмат известной фразой: «шахматы — это дрозофила искусственного интеллекта». Аналогия лежит на поверхности: шахматы представляют собой безусловно интеллектуальную, но при этом чётко формализованную, простую по структуре и компактную задачу, то есть являются удобным объектом лабораторных исследований в искусственном интеллекте, так же, как мушка-дрозофила благодаря малым размерам, плодовитости и быстрой смене поколений является удобным лабораторным объектом для изучения наследственности. Действительно, на шахматах были апробированы многие известные методы и направления искусственного интеллекта, в том числе методики оптимизации перебора (уход от «комбинаторного взрыва» при просчёте вариантов вперёд на несколько ходов), распознавание образов, экспертные системы, логическое программирование.
Однако, к удивлению и огорчению многих, шахматы мало приблизили людей к созданию машин с человекоподобным интеллектом. Современные шахматные программы, по сути, остановились на наиболее примитивном этапе интеллектуальной деятельности: они исследуют огромное число возможных ходов обоих игроков, применяя различные методы усечения дерева перебора, в том числе относительно простую функцию оценки. В сочетании с базами данных, хранящими заранее рассчитанные готовые варианты дебютов и эндшпилей, благодаря быстродействию и объёмам памяти современных компьютеров, эти методы уже обеспечивают игру компьютера в шахматы на гроссмейстерском уровне. По этим причинам компьютерные шахматы больше не имеют такого большого академического интереса. Роль «дрозофилы искусственного интеллекта» перешла к другим интеллектуальным играм, таким как, например, го. Гораздо больший, чем в шахматах, объём перебора вариантов в таких играх ограничивает возможности использования простых методов и требует от учёных применять более умозрительные подходы к игре.
Проблемы реализации Разработчики шахматных программ должны сделать ряд решений при их написании. Они включают: Способ изображения шахматной доски — представление цельной позиции как структуры данных. Методы поиска — поиск возможных лучших ходов. Листовая оценка — оценка позиции без учёта дальнейших ходов. См. также: Минимакс Альфа-бета-отсечение Killer эвристика Итерационное заглубление Эвристика нулевого хода
Шахматные компьютеры Шахматный компьютер — специализированное устройство для игры в шахматы. Обычно используется для развлечения и практики игроков в шахматы при отсутствии партнёра-человека, в качестве средства для анализа различных игровых ситуаций, для соревнования компьютеров между собой.
Потребительские шахматные компьютеры обычно выполняются в виде шахматной доски с дисплеем и набором клавиш для выполнения необходимых игровых действий. В зависимости от конструкции, доска может быть никак не связана с компьютерной частью и не иметь электроники, или наоборот, представлять собой дисплей, отображающий графическое представление игровой ситуации.
В СССР с середины 1980-х годов выпускались потребительские шахматные компьютеры «Электроника ИМ-01», «Электроника ИМ-05», «Электроника ИМ-29» («Шахматный партнёр»), «Интеллект-01», «Интеллект-02», «Дебют», «Феникс», «100 лет Новосибирск» и другие.
Большинство программ основано на методе перебора ходов, существуют программы, основанные на эвристических методах. Попытка создать настоящую шахматную программу, на основе алгоритма шахматного мастера, предпринималась экс-чемпионом мира М. Ботвинником и его ассистентами-программистами — Б. Штильманом и А. Резницким.
Большой прорыв в развитии шахматных программ наступил при применении нейронных сетей. Например, в 2017 году DeepMind создал программу для нейронных сетей, которая после самостоятельного обучения в течение нескольких часов, смогла победить лучшие шахматные алгоритмы. В серии из 100 игр против Stockfish, AlphaZero ни разу не проиграл и выиграл 25 игр, играя белыми, и три игры, играя чёрными. Алгоритм AlphaZero был создан на основе программы AlphaGo, которая ранее стала абсолютным чемпионом в игре го. Алгоритм AlphaZero более похож на то, как играет в шахматы человек. Он рассматривает меньше позиций, чем другие программы. По словам авторов, она оценивает 80 тысяч позиций в секунду в сравнении с 70 миллионами в секунду у Stockfish. В отличие от AlphaGo, AlphaZero способен научиться сразу нескольким задачам-играм, а не одной. AlphaZero не обучали игре, а давали только базовые знания о правилах игры. AlphaZero затем играл сам с собой и самостоятельно вырабатывал тактику.
Структура шахматной программы Первое исследование на тему шахматного программирования сделал в 1950 году американский математик Клод Шеннон, успешно предусмотревший два основных возможных метода поиска, которые можно использовать, и назвал их «Тип А» и «Тип B».
Программы типа А используют так называемый подход «грубой силы» (brute force), изучая каждую возможную позицию на фиксированную глубину с помощью алгоритма Минимакс. Шеннон утверждал, что этот метод будет непрактичным по двум причинам.
Во-первых, с примерно тридцатью ходами, возможными в типичной позиции, на изучение около 753 млн узловых позиций (просчёт примерно на три хода вперёд для обеих сторон), надо примерно 12,5 минут, даже в «очень оптимистичном» случае, когда компьютер сможет оценивать миллион позиций в секунду (чтобы достичь этого, понадобилось сорок лет).