Мат в N ходов

История шахматных компьютеров.

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

Считается, что первый шахматный автомат сконструировал австриец Вольфганг фон Кемпелен. В 1769 году изобретатель продемонстрировал устройство, которое назвал «Турок».

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

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

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

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

Следующие полтора столетия в компьютерных шахматах не было существенных подвижек — лишь несколько вариаций на тему «Турка».

И вот в 1912 году испанский инженер и математик Леонардо Торрес представил миру «El Ajedrecista» — «Шахматиста» (исп.) — первый автономный шахматный компьютер.

«Шахматист» всё ещё не мог вести полноценную партию. Аппарат демонстрировал игру тремя фигурами: король и ладья ставили мат королю соперника. Но, в отличие от предшественников, устройство могло играть самостоятельно, без помощи оператора.

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

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

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

В 30-40-х годах немецкий инженер и пионер компьютеростроения Конрад Цузе разработал язык программирования Планкалькюль (Plankalkül), на котором начал писать программу для полноценной игры в шахматы. Однако война помешала работе Цузе, и программа так и не была реализована на «железе».

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

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

Основатель теории информации и «отец информационного века» Клод Шеннон публикует книгу «Programming a Computer for Playing Chess» («Компьютерное программирование для игры в шахматы»), которая становится самым фундаментальным трудом в этой области на тот момент.

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

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

Оценивающая функция, как это следует из названия, даёт оценку позиции на доске. Оценка включает в себя и материальную, и позиционную составляющую. Если одна из сторон имеет лишние фигуры, то оценка склоняется в её сторону: лишняя пешка дает «+1» к оценке, лишний слон — «+3». В то же время централизованный конь «весит» больше коня в углу доски. Это, разумеется, упрощённая схема, ведь ценность фигур меняется в зависимости от стадии игры, но для иллюстрации принципов этого достаточно.

Теперь разберёмся с деревом вариантов. Рассмотрим начальную расстановку фигур на доске — она будет корнем нашего дерева. Любой ход фигуры даёт начало новой ветви в этом дереве. С учётом того, что в начальной позиции могут ходить только пешки и кони, получается:

После первого хода в нашем дереве есть уже 20 ветвей. А после ответа чёрных каждая ветвь также получит по 20 продолжений, и ко второму ходу дерево будет включать уже 400 ветвей.

Думаю, вы уже поняли, что количество ветвей в дереве растёт очень быстро. Например, после четвёртого хода ветвей станет уже 71870.

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

В 1956 году в лаборатории Лос-Аламоса — колыбели ядерной бомбы — разрабатывают вариант игры в шахмат без слонов на доске размером 6×6 клеток. По сравнению с классическим, такой вариант игры требует меньше вычислений и отлично подходит для разработки и тестирования шахматных программ на одном из первых электронных компьютеров MANIAC I.

Сотрудники лаборатории Пол Стейн и Марк Уэллс разработали программу, работающую методом полного перебора .

Их компьютер работал со скростью 11 тысяч операций в секунду и просчитывал варианты на четыре хода вперёд. Лучший в этих пределах ход отыскивался в среднем за 12 минут.

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

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

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

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

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

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

Но переломный момент наступает на рубеже 80-х и 90-х.

Скорее всего, вы что-то слышали про Deep Blue и его матчах с Каспаровым. Но прежде чем рассказать об их противостоянии, стоит упомянуть предшественников.

В 1988 году инженеры IBM создали Deep Thought. В этом же году машина приняла участие в шахматном турнире в Лонг-Бич, где поделила первое место с британским гроссмейстером Энтони Майлзом, обойдя при этом экс-чемпиона мира Михаила Таля.

На этом удача Deep Thought заканчивается. В 1989 году машина уступает в матче с Каспаровым со счётом 0:2, а в следующем году — Карпову со счётом 0:1.

IBM принимает решение развивать проект дальше, и вскоре на свет появляются Deep Thought ||, а за ним Deep Blue. В феврале 1996 последний пробует свои силы в матче с Каспаровым и вновь терпит поражение со счетом 2:4.

Инженеры вносят значитильные изменения прямиком в шахматный процессор машины и в мае 1997 Deep Blue II берет реванш.

Матч протекает с большой интригой. Первую партию выигрывает Каспаров, вторую — Deep Blue. Третья и четвёртая завершаются вничью. В пятой партии у Каспарова выигранная позиция, однако машина выкручивается и добивается ничьи посредством вечного шаха. Таким образом, накануне последней партии счет равный — 2½ на 2½. В заключительной партии Каспаров неудачно разыгрывает дебют, и, получив безнадёжную для себя позицию, сдаётся всего через 19 ходов.

Окончательный счет матча — 3½ на 2½. Компьютер одолел чемпиона мира.

В новом веке противостояние продолжается, причём машина участвует в нём уже с позиции силы. В 2002 году Fritz вничью проводит матч с новым чемпионом мира — Владимиром Крамником. В 2006 году в повторном матче Крамник проигрывает со счётом 2:4.

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

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

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

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

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

Долгое время программисты не могли «заставить» нейронку успешно играть в шахматы, пока в 2017 году инженеры из DeepMind Technologies, дочерней компании Google, не добились успеха.

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

Вскоре после этого гугловские инженеры представили AlphaZero — нейронку, основанную на AlphaGo, но предназначенную для игры в шахматы. Новую программу выставили против Stockfish 8 — самой сильной на тот момент не-нейронки. Из ста партий AlphaZero выиграл 28, а остальные 72 свёл в ничью.

Компьютеры-компьютерами, а мы давайте тоже играть, ведь это интересно и весело.

Орзик, помнится, обещал устраивать регулярные турниры среди читателей TJ, но что-то филонит.

Вот предыдущий пост о том, как начать играть.

#шахматы #нейросети