История шахматных движков

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

ВВЕДЕНИЕ

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

Так, в конце 19 века первый чемпион мира Вильгельм Стейниц заложил основы позиционных шахмат.

В середине ХХ века шестой чемпион мира Михаил Ботвинник начал посвящать много времени физической и шахматной подготовке перед турнирами, объявив эру строгого шахматного профессионализма.

В 1970-х годах претерпела огромные изменения дебютная теория - во многом, под влиянием одиннадцатого чемпиона мира Роберта Джеймса Фишера. Были введены новые дебютные системы, такие как «Система Ёжа», а также были обнаружены новые идеи в древних дебютных системах, демонстрируя неисчерпаемые возможности шахмат.

Однако ничто иное не произвело такой революции в шахматах, как появление компьютерных шахматных движков. В наше время даже новички знакомы с терминами «Стокфиш» (Stockfish) и «Комодо» (Komodo).

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

Все мы уже воспринимаем шахматные движки, как нечто обыденное и привычное, многие используют их ежедневно. Но большинство из нас даже не представляет себе тех проблем, с которыми приходилось столкнуться предыдущим поколениям при создании данных движков. Кто изобрел первый шахматный компьютер? Сколько времени понадобилось искусственному интеллекту, чтобы стать сильнее людей? В чем разница между классическими шахматными движками и Альфа Зеро (Alpha Zero) от Google?

Здесь мы постараемся ответить на эти вопросы и более подробно рассмотрим историю шахматных движков.

18 ВЕК: Механический турок

В 1769 году французский иллюзионист Франсуа Пеллетье выступал перед Марией Терезой  Австрийской во дворце Шенбрунн в Вене. Среди зрителей был Венгерский изобретатель и писатель Вольфганг фон Кемпелен. Вдохновленный работой Пеллетье, Кемпелен немедленно приступил к созданию изобретения, которое впоследствии стало одной из самых громких мистификаций за всю историю.

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

Турок был способен играть в шахматы самостоятельно и побеждать противников-людей. Он даже умел распознавать неправильные ходы и заставлять своих противников переходить. На одной выставке он даже решил сложную задачу «Обход доски шахматным конем».

Была только одна проблема. Все это было подделкой. Не «Турок» делал все ходы. Внутри него был спрятан человек.

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

И это сработало? Кемпелен гастролировал по Европе, выставляя свое изобретение до 1804 года. После его смерти машина сменила нескольких владельцев и продолжала играть в шахматы до 1854 года, когда пожар в Филадельфии решил ее судьбу. Удивительно, что никто не осознал фальсификацию при жизни Турка.

Таким образом, первый компьютерный шахматный «движок» имел большой коммерческий успех.

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

1950-е годы: НАЧАЛО ЭРЫ

Во время Второй мировой войны руководство стран «Оси» и союзников тратило много времени на то, чтобы нанять лучших ученых и собрать их в команды. Цель была ясна - выиграть войну. Поэтому величайшие умы 20-го века посвятили свои военные годы разработке новых технологий и оружия, которые помогли бы одолеть врага. Наука была на службе военной промышленности.

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

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

Накануне войны, получив докторскую степень, Шеннон и Тьюринг начали работать над криптоанализом в США и Великобритании соответственно. Они внимательно следили за работой друг друга и даже встретились лично в 1943 году, во время двухмесячного пребывания Тьюринга в Bell's Lab в Нью-Йорке, где работал Шеннон. После окончания войны они оба проявили повышенный интерес к программированию шахматного компьютера.

В 1949 году Шеннон опубликовал культовую работу под названием «Программирование компьютера для игры в шахматы», в которой описал алгоритм для шахматной машины. Одновременно Тьюринг разрабатывал собственную программу игры в шахматы. Его работа над «Турошам» (Turbochamp) началась еще в 1948 году и закончилась в 1950 году.

Стоит отметить, что Тьюринг запрограммировал Турошам на бумаге, без доступа к реальному компьютеру. Он попытался протестировать его на Ferranti Mark I - первом коммерчески доступном компьютере - и потерпел неудачу. В конце концов, он проверил её вручную (!) В товарищеской шахматной партии в 1951 году.

51 год спустя не кто иной, как Гарри Каспаров тестировал «Турошам». У программы не было ни единого шанса, но величайшие игроки всех времен признали, насколько огромным было достижение Тьюринга.

Пока не ясно, работали ли Шеннон и Тьюринг независимо или вдохновлялись друг другом - содержание их разговоров в 1943 году неизвестно. Однако, даже если они не сотрудничали, их вклад был огромен. Все последующие поколения разработчиков компьютерных шахмат «стояли на плечах» этих двух гигантов.

В 1951 году Дитриху Принцу, коллеге Тьюринга, удалось реализовать алгоритм на Ferranti Mark I и создать программу, способную решать мат в два хода. В 1956 году группа ученых под руководством Стэна Улама (одного из изобретателей водородной бомбы) создала программу, способную играть в шахматы на доске 6 × 6. И, наконец, в 1957 году инженер IBM Алекс Бернштейн создал первую автоматизированную программу, полностью способную сыграть полную партию в шахматы.

Эра компьютерных шахмат официально началась.

1960-1970-е годы: МАЛЕНЬКИЙ ШАГ ИЛИ ГИГАНСКИЙ ПРЫЖОК?

Первые компьютерные шахматные движки были довольно слабыми и примитивными. Однако в течение 1960-х и 1970-х годов их сила быстро росла. Этому качественному скачку способствовали два основных фактора:

1. Улучшенные и более сложные алгоритмы.

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

2. Улучшенное и более быстрое оборудование

Самым большим ограничением для Тьюринга и других пионеров была вычислительная мощность. Однако в 1960-х и 1970-х годах скорость оборудования росла экспоненциально - согласно закону Мура, вычислительная мощность удваивалась каждые два года. Это позволило реализовать продвинутые алгоритмы - время поиска МиниМакса значительно сократилось.

Но дело не только в чистой вычислительной мощности. В 1960-х и 1970-х годах компьютерные шахматы приобрели известность. Первый чемпионат среди шахматных компьютеров был проведен в 1970 году в Нью-Йорке. Вскоре после этого, в 1974 году, в Стокгольме состоялся первый чемпионат мира по компьютерным шахматам. Появление "сцены" неизбежно привело к появлению специализированных компаний, которые начали разрабатывать индивидуальное программное и аппаратное обеспечение для игры в шахматы. Это позволило шахматным движкам стать еще лучше.

Насколько хороши были шахматные компьютеры по сравнению с людьми в то время? Опыт показал: достаточно хороши, чтобы победить любителя, но недостаточно, чтобы соревноваться с мастером.

Например, в 1967 году MacHack VI стал первым шахматным компьютером, который победил человеческого противника. Его игровая сила была около 1300 ЭЛО. Но уже в 1976 году произошел значительный скачок - шахматный движок Chess 4.5 выиграл группу «B» турнира Пола Мейсона в Северной Калифорнии. В 1977 году он также выиграл Minnesota Open с турнирным рейтингом (перформанс) 2271 и обыграл игрока из группы «А» Стенберга с рейтингом 1969.

Однако компьютеры не были на равных с более сильными людьми. В 1968 году международный мастер Дэвид Леви поставил 3000 долларов, что в ближайшие 10 лет он сможет победить любой шахматный движок. В 1977 году он выиграл свою ставку в матче против шахматного движка KAISSA. Он также победил более новую версию MacHack в 1978 году.

Поэтому в конце 1970-х шахматный компьютер мог соревноваться с людьми, но не мог играть на уровне мастера.

Но затем наступили 80-е.

1980-е годы: ВЫЗОВ ЧЕЛОВЕЧЕСТВУ

К началу 1980-х программирование шахматных движков стало прибыльным бизнесом. Персональные компьютеры получили широкое распространение в домашних хозяйствах. Интерес к индивидуальному и специализированному программному обеспечению, включая шахматные движки, резко возрос. Только в 1982 году продажи шахматных компьютеров превысили 100 миллионов долларов.

Поэтому неудивительно, что шахматные движки продолжали совершенствоваться. В 1980 году их программирование превратилось в серьезное соревнование. Эдвард Фредкин, профессор компьютерных наук в Университете Карнеги-Меллона, представил премию Фредкина. Он предлагал денежные призы за различные достижения в мире шахматного программирования (5000$ за первый движок, который достигнет уровня мастера, 10000$ за первый движок, который достигнет уровня гроссмейстера, 100000$ за первый движок, который победит чемпиона мира).

Гонка началась. Число и мощность шахматных движков продолжало расти.

Впереди шел коллега Фредкина из Университета Карнеги-Меллон. Самым заметным проектом и острием целого поколения является Deep Thought - первый шахматный движок, достигший уровня гроссмейстера. В 1988 году он разделил первое место с гроссмейстером Тони Майлзом в Открытом чемпионате США. В 1989 году он легко обыграл международного мастера Дэвида Леви в четырех партиях одержав четыре победы.

Гибель человечества казалась неизбежной. Поэтому было принято решение обратиться к действующему чемпиону мира и, возможно, величайшему игроку всех времен - Гарри Каспарову. Во-первых, на культовом сеансе одновременной игры в Гамбурге в 1985 году он играл против 32 (!) сильнейших шахматных машин - и победил их всех (!!). Затем, в 1989 году, он встретился с Deep Thought в матче из двух игр, который также выиграл.

Поэтому против шахматных движков в 1980-х годах Гарри стал “избранным”.

Увы, но в 1990-е годы падёт и он.

1990 – 1997: Шахматные движки берут верх

Итак, в 1989 году человечество выиграло битву, но не войну. В 1990-е годы произошло гораздо больше столкновений между людьми и шахматными компьютерами. Лучшие шахматные движки даже участвовали в элитных шахматных турнирах - с переменным успехом. Было организовано несколько матчей «человек против машины», но ни один из них не стал известен так, как матч, в котором шахматный движок победил чемпиона мира в 1997 году.

В 1989 году исследователи, участвовавшие в проекте Deep Thought, были наняты IBM. Они начали разработку более мощной версии движка.

Название проекта было Deep Blue. В 1996 году, всего через 7 лет после матча Каспаров - Deep Thought, прошел второй раунд «человек против машины»: первый матч Каспаров - Deep Blue. В первой же партии Deep Blue шокировал Каспарова и стал первым шахматным движком, победившим чемпиона мира в классической игре. Однако Гарри собрался и выиграл матч со счетом 4: 2, в очередной раз затянув неизбежное.

Провал не разочаровал программистов Deep Blue. В течение следующего года они продолжали улучшать мощность шахматного движка. Они даже наняли гроссмейстера Джоэла Бенджамина в качестве консультанта, чтобы помочь им составить дебютную книгу. После тщательной подготовки они снова вызвали Каспарова на матч-реванш - и, как говорится, остальное уже история.

В знаменитом матче Каспаров выиграл первую партию. Но парадоксальный 44-й ход шахматного движка смутил его. Это пошатнуло его уверенность, и он упустил серьезные шансы на ничью во второй игре. Затем Deep Blue разгромил его в 6-й игре жертвой коня в начале дебюта. Это решило судьбу Каспарова и принесло команде Deep Blue приз Фредкина.

Смотрите также: Каспаров против Deep Blue - Противостояние, изменившее историю

После матча он заявил, что IBM жульничала и что ходы на самом деле делал человек (Джоэль Бенджамин). Другие источники предполагали, что ошибка в коде Deep Blue принесла ему победу.

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

Однако люди еще не сдались.

1997-2006 ПОСЛЕДНЯЯ БИТВА ЧЕЛОВЕЧЕСТВА

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

Например, в 2000 году шахматный движок Deep Junior участвовал в супертурнире Dortmund Elite Supertournament - и набрал всего 50%.

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

В 2003 году Гарри Каспаров сыграл вничью два матча против Deep Junior 7 и X3d Fritz.

Увы, этот маленький лучик надежды был быстро уничтожен шахматным движком Hydra. В 2004 году он обыграл гроссмейстеров Евгения Владимирова (3-1) и Руслана Пономарева (2-0). Затем, в 2005 году, он уничтожил Майкла Адамса, входящего в десятку лучших в мире, с ужасающим результатом: 5.5-0.5

А в 2006 году Deep Fritz забил последний гвоздь в гроб человечества, победив чемпиона мира Владимира Крамника со счетом 4:2.

2006-2017: ЗОЛОТАЯ ЭРА ШАХМАТНЫХ ДВИЖКОВ

Десятилетие 2006-2017 гг. - золотая эра шахматных движков.

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

Продолжает расти уровень Чемпионатов мира среди компьютерных шахмат (WCC). Из-за престижа и денег возникли споры. Самый печально-известный случай — это дисквалификация шахматного движка Рыбка (Rybka), четырех кратного победителя Чемпионата мира в 2007-2010 годах, из-за плагиата кода.

Помимо чемпионата мира по шахматам, в 2010 году было введено новое соревнование - Top Chess Engines Competition (TCEC). В отличие от WCC, TCEC предлагает более длинные партии, которые играются с использованием высококачественного оборудования, что приводит к более высокому качеству шахмат.

Матчи человек-машина доказали, что разрыв увеличивается. В течение десятилетия было проведено ряд матчей с гандикапом, в которых шахматные движки давали разные «форы» сильным гроссмейстерам. Результаты были удручающими для человечества. Например, в 2014 году шахматный движок Stockfish победил гроссмейстера Дэниэля Народицкого, который воспользовался помощью ранней версии движка Рыбки. В 2015 году шахматный движок Komodo сыграл 6 партий с форой против Сергея Мовсесяна, бывшего ТОП-10, и легко его разгромил. А в 2016 году Хикару Накамура, входящий в десятку лучших в мире, тоже почувствовал всю силу шахматного движка Комодо.

В любом случае с 2006 по 2017 год преобладали классические шахматные движки. До конца 2017 года ничего революционного не произошло. Их сила менялась последовательно, но медленно. Все казалось знакомым, и кардинальных изменений, серьезных прорывов никто не ожидал. Затем случился Альфа Зеро (AlphaZero).

2017 год: НОВАЯ РЕВОЛЮЦИЯ?

5 декабря 2017 года группа ученых из компании Google AI Deep Mindshattered расколола шахматный мир.

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

Команда проверила силу нового движка в матче из 100 партий против самого сильного классического шахматного движка, доступного на тот момент - Stockfish 8. Результат матча был ошеломляющим - +28-0 = 72 в пользу AlphaZero. Но что еще более впечатляло, так это стиль игры AlphaZero - он был более интуитивным и похожим на человека, чем игра традиционных движков.

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

Однако 7 декабря 2018 года команда Deep Mind опубликовала еще одну статью под названием «Общий алгоритм обучения с подкреплением, которые позволяет достичь мастер уровня в шахматах, сёги и Го через самостоятельную игру».

В нём они представили результаты ещё одного матча между Alpha Zero и Stockfish. Из 1000 игр A0 выиграла 155 игр и проиграла только 6. Несмотря на то, что использовалась более старая версия Stockfish, это впечатляющий результат.

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

C 2019 года: Начало Эры Искусственного интеллекта

После выхода на сцену AlphaZero - движка на основе нейронной сети, шахматы изменились навсегда. К сожалению, никто не мог купить AlphaZero или лицензировать его, поэтому появился проект Leela Chess Zero – движок на нейронной сети с открытым исходным кодом.

В 2019 году Лила выигрывает в финале самый сильный традиционный шахматный движок StockFish, дав тем самым старт новой Эры Искусственного интеллекта.

Хотя по рейтингу Stockfish сохранил лидирующее место в списке шахматных движков, движки на нейронных сетях стали подбираться все ближе и ближе. Поэтому в сентябре 2020 г. был выпущен Stockfish 12, и было объявлено, что Stockfish поглотил проект Stockfish + NNUE (NNUE означает эффективно обновляемая нейронная сеть).

Что означает этот ход?

Теперь грубый перебор Stockfish был улучшен за счет оценочных возможностей нейронной сети - потрясающая комбинация!

По состоянию на март 2021 года Stockfish 13 является движком с самым высоким рейтингом согласно списку компьютерных шахматных рейтингов (CCRL).

Что будет дальше?

2033 год. Уровень Бог?

10 февраля 2033 года весь шахматных мир был потрясен выходом нового шахматного движка, который уверенно обыграл Stockfish 17 и преодолел планку 4000 ЭЛО.

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

Вот комментарии представителя Ижевск Дайнемикс Корпорейшн:

«Сегодня мы стали свидетелями нового огромного скачка в компьютерных шахматах. Без сомнения данные технологии помогут существенно модернизировать робототехнику, что ускорит закладку нового межпланетного космического корабля и человечество наконец-то колонизирует Марс».

А как видите будущее шахмат Вы?

Примечание: Если вы стремитесь к резкому увеличению шахматного уровня, то необходимо систематически работать над всеми элементами игры:

• Тактика
• Позиционная игра
• Атакующие навыки
• Техника эндшпиля
• Анализ классических игр
• Психологическая подготовка
• И еще многое другое

На первый взгляд кажется, что предстоит много работы. Но благодаря нашему учебному курсу Ваше обучение пройдёт легко, эффективно и с минимальными затратами времени. Присоединяйтесь к программе обучения «Шахматы. Перезагрузка за 21 День», прямо сейчас!