Почему компьютеры подчинили шахматы: рассердили Каспарова* еще в 90-х, их отрыв от Карлсена – космос
Шахматы и компьютеры неразрывно связаны: сначала игра помогала в развитии технологий, а сейчас все гроссмейстеры пользуются программами при подготовке.
Первые шахматные машины появились еще в XVIII веке, а в наше время их рейтинг уже недостижим для человека.
От подсадного шахматиста до машины физика, работавшего над ядерным оружием
История механических шахмат начинается в 1769-м – задолго до появления первых компьютеров. Тогда изобретатель и писатель Вольфганг фон Кемпелен, вдохновленный иллюзионистами, придумал первый шахматный автомат. И показал его перед Марией Терезой Австрийской во дворце Шенбрунн в Вене.
Кемпелен соорудил сложную конструкцию с механической куклой, которая играла в шахматы. И не просто передвигала предметы по доске, а обыгрывала опытных противников. Изобретение назвали «Механический турок» – из-за восточного наряда куклы.
Кукла гастролировала по Европе до 1804-го, удивляя зрителей и вызывая восторг. После смерти Кемпелена «Турок» перешел к немецкому инженеру Иоганну Мельцелю, но все так же играл в шахматы до середины XIX века.
И это одна из ярких мистификаций того времени. На самом деле «Турком» управлял человек, который прятался в столе. Так как отсеков было несколько, Кемпелен часто демонстрировал «прозрачность» своего изобретения: пока он открывал одно отделение стола, шахматист находился в другом, потом перемещался. Во время игры он определял текущую позицию на доске благодаря магнитам, прикрепленным к фигурам снизу, а затем совершал ходы, используя рычаг.
В 1836-м знаменитый американский писатель Эдгар Аллан По даже написал эссе-разоблачение «Шахматист Мельцеля», в котором раскрыл секрет механизма.
Первый движок оказался обманом, но удивительно предсказал вектор развития шахматных программ.
Настоящий прорыв в этой области произошел в 1948-м, когда английский математик Алан Тьюринг приступил к разработке алгоритма Turochamp. С помощью него машина в теории могла играть в шахматы. Спустя три года алгоритм был готов, но возникла одна проблема – механизм, который мог бы его распознавать, еще не изобрели. Поэтому в качестве движка снова выступал человек.
Хотя на этот раз он мог и не играть в шахматы, даже не знать правил – просто делал тот ход, который подсказывал алгоритм. «Бумажная машина» даже проводила партии – хотя и уступила компаньону Тьюринга.
Одновременно с этим американский инженер Клод Шеннон написал статью о шахматном программировании. Там он объяснял, почему именно эта игра поможет в развитии технологий: в ней есть допустимые операции (ходы) и конечная цель (мат); структура шахмат хорошо подходит цифровой природе компьютеров; к тому же правила игры простые, а сама она сложная, но логичная. Шеннон отметил существование в шахматах лучшего хода и практическую невозможность его нахождения.
В 1952-м появился первый шахматный компьютер – MANIAC I: с помощью алгоритма MiniMax машина выбирала лучший из ходов. Программа родилась в ядерной лаборатории Лос-Аламоса, над ней работал американский математик и физик Николас Метрополис, который до этого сотрудничал с командой Роберта Оппенгеймера при создании ядерного оружия.
Машина играла на доске 6х6, без слонов. Компьютер сыграл партию против сильного шахматиста – она продолжалась 10 часов, и победил человек. А вот другой поединок закончился в пользу MANIAC – обыграл девушку, которая только недавно познакомилась с шахматами. Машина победила на 23-м ходу.
Через 5 лет американец Алекс Бернштейн создал программу, использующую уже все фигуры.
А в 1958-м его соотечественники Аллен Ньюэлл, Клифф Шоу и Герберт Саймон написали алгоритм «альфа-бета-отсечение». С его помощью «дерево» поиска отсекало лишние ходы, то есть заведомо слабый ход машина даже не рассматривала, придерживаясь только сильных вариантов. Этот алгоритм используется и сейчас.
Компьютер обрабатывает массу информации, но думает ли как человек?
Почему же в информатике такой интерес к шахматам? Игра проста по структуре – понятные правила, которые не допускают вольную трактовку. При этом количество вариантов развития событий и допустимых ходов – невероятно большое, что придает масштаб для исследования.
На шахматах испытывали многие направления в развитии искусственного интеллекта: оптимизацию перебора, логическое программирование, экспертные системы.
В обычной позиции на доске есть около 40 возможных ходов, плюс столько же ответных. Получается, каждая пара полуходов – это 1600 позиций, две пары – 2,5 млн позиций, три – 4 млрд. Клод Шеннон в 1950-м оценил минимальное количество неповторяющихся шахматных партий. И оно оказалось фантастическим – 10 в 120 степени. Правда, это количество включало и позиции, исключаемые правилами. Так что легальных позиций «всего» 10 в 40 степени.
Если в базу данных компьютера поместить абсолютно все, то получится идеальная машина для шахмат. Вот только такого хранилища данных просто не существует – для него понадобились бы миллионы квадратных километров.
Так что шахматные программы рассчитывают несколько последующих ходов. Благодаря «альфа-бета-отсечению» большое количество вариантов не рассматривается. И количество ходов, которые машина может предсказать, постоянно увеличивается.
Программа перебирает возможные ходы, пока не достигнет максимальной глубины поиска или не придет к конечно позиции (мат, пат). И на основании этого анализа она выбирает наилучшую стратегию.
Понятно, что с дебютами компьютерам сложнее всего – в самом начале любой игры слишком много вариантов. Нашелся простой выход – большинство современных движков используют дебютные библиотеки, которые облегчают им игру на первые 20-25 ходов. Подобные базы есть и для эндшпильных окончаний.
При этом шахматные программы все-таки далеки от искусственного интеллекта в понимании, которое развилось благодаря научной фантастике. Компьютер не думает как человек, а просто следует алгоритму.
Шестой чемпион мира Михаил Ботвинник мечтал, чтобы машина работала как человеческий мозг – анализировала опыт ведущих шахматистов, оценивала приемы, которые использует человек. Ботвинник много лет работал над этим, но оставил лишь теоретические материалы (хотя, кажется, в последние годы к его мечте приблизились – об этом ниже).
От третьего разряда до победы над чемпионом мира за 30 лет
Компьютерные программы разрабатывали не только для усовершенствования технологий, но и для главного противостояния – человека и машины.
С конца 1960-х компьютеры играли друг с другом – и тогда гроссмейстеры оценивали успехи машин на третий шахматный разряд. В 1968-м шотландец Дэвид Леви оказался на вечеринке основателя отделения машинного интеллекта и восприятия Эдинбургского университета Дональда Мичи. Туда пришел и Джон Маккарти, автор термина «искусственный интеллект».
Разговаривая о достижениях в шахматных программах, они заключили пари: Маккарти верил, что в ближайшие 10 лет машина обыграет человека, Леви поставил на себя 1250 фунтов.
В последующее десятилетие компьютеры заметно прибавили. В 1974-м прошел первый чемпионат мира среди программ, выиграла советская «Каисса», названная в честь богини шахмат. И вот в 1977-м она встретилась с Леви. Шотландец победил в первой партии, после чего матч решили не продолжать. Так что он выиграл и пари.
Но с каждым годом доминирование компьютеров приближалось. В 1983-м американцы Джо Кондон и Кен Томпсон спроектировали первый компьютер, предназначенный только для шахмат. И движок Belle играл не просто хорошо, он достиг уровня мастера (как Леви) и рейтинга Эло 2250. Он производил 180 000 операций в секунду (обычные компьютеры – лишь 5000) и просчитывал позицию на 8-9 полуходов.
И вот в 1989-м Леви проиграл компьютеру Deep Thought. Он высчитывал уже 500 000 операций в секунду. К этому моменту уже не поднималось вопроса, может ли программа обыграть человека. Возник другой: может ли она одолеть лучшего шахматиста? Deep Thought провел две партии против 13-го чемпиона мира Гарри Каспарова* (признан иноагентом в России), и оба раза выиграл советский шахматист.
Разработкой заинтересовались в IBM и спустя несколько лет анонсировали другой суперкомпьютер – Deep Blue. В это время Каспаров поделил первое место с программой Fritz на турнире по блицу.
В 1996-м чемпион мира наконец встретился с Deep Blue. Первую же партию выиграл компьютер, что вызвало шок у любителей шахмат. Да, матч остался за Каспаровым (4:2), но общая победа программы казалась вопросом времени.
Уже через год они встретились снова.
И матч-реванш выиграл Deep Blue – он вычислял 50 миллиардов позиций каждые три минуты. Каспаров подозревал IBM в читерстве, не верил в такую «человечную» игру машины, ругал организаторов, но так и остался побежденным: после матча компания не соглашалась на реванш.
После победы суперкомпьютера над сильнейшим шахматистом развитие программ пошло в сторону доступности. Улучшались алгоритмы, снижались требования к аппаратной части. В 2000-м коммерческие программы Junior и Fritz добились ничейного результата в матчах с Каспаровым и Владимиром Крамником.
В 2005-м программно-аппаратный комплекс с 64 процессорами Hydra разгромил Майкла Адамса (на тот момент 7-го игрока в мире) со счетом 5,5:0,5. В том же году Hydra, Deep Junior и Fritz обыграли команду гроссмейстеров со средним рейтингом 2681 (Веселин Топалов, Руслан Пономарев и Сергей Карякин).
Спустя год 14-й чемпион мира Крамник уступил Deep Fritz со счетом 2:4. На этом равное противостояние человека и машины закончилось. Сейчас гроссмейстеры иногда проводят партии против программ, но людям дают фору в одну-две пешки, что не всегда спасает от поражения.
Программы помогают чемпионам и почти научились думать
С 2008-го главный шахматный движок – Stockfish. Разные его версии использовали гроссмейстеры для подготовки к чемпионским матчам, на онлайн-площадках с его помощью анализируют партии.
Хотя с развитием программ появилась проблема противоположная той, что была в «Механическом турке». Если тогда человек прятался в машину, чтобы та выигрывала, то теперь распространилось читерство, когда шахматисты пользуются программами во время матчей.
С победой над человеком компьютер перешел в ранг главного помощника, но не остановился в развитии. В 2017-м произошла еще одна революция: Google AI Deep Mindshattered представила разработку AlphaZero. На этом движке вместо уже привычного «альфа-бета» алгоритма использовалась функция нелинейного приближения, основанная на глубокой нейронной сети. Проще говоря: AlphaZero обучает сам себя.
Если запустить процесс с нуля, то сначала «Альфа» будет играть как маленький ребенок, через час, анализируя собственные ходы, достигнет уровня любителя, а через сутки – максимального рейтинга.
«Он играет очень по-человечески, легко идет на жертвы за инициативу, рискует, атакует. Именно этим он отличается от сильнейших движков предыдущего поколения. Оценка позиции от AlphaZero намного ближе к человеческой», – восхищался Крамник. Кажется, о чем-то таком и мечтал Ботвинник.
Команда Google проверила новую разработку в игре с самым сильным на тот момент движком Stockfish 8 (провели 100 партий). AlphaZero выиграла со счетом 72:28. Через год новинка выиграла 155 партий из 1000 при шести поражениях (839 партий вничью).
Сейчас движки на основе нейронной сети набирают популярность. Хоть Stockfish и сохранял лидерство по рейтингу, но уже терял преимущество. Поэтому осенью 2020-го и он начал работу с нейросетями.
Перебор вариантов теперь улучшился за счет оценочных возможностей – идеальная комбинация. На апрель-2023 рейтинг Эло последней версии Stockfish оценивается в 3500 и более. Максимальный рейтинг, который набирал человек – 2882 балла (рекорд Магнуса Карлсена). Меньше чем за век компьютеры ушли в отрыв, который человеку уже не ликвидировать.
* Гарри Каспаров признан иноагентом в России
Фото: Gettyimages.ru/Yvonne Hemsey, Juergen Schwarz, Mario Tama; РИА Новости/Дмитрий Донской
То есть при таком количестве фигур и любом их расположении МАШИНА со 100% точностью знает оценку позиции и способы выиграть партию (или свести вничью, если выиграть априори нельзя.
Это жестко.
Ну и сейчас движки показывают оценки, основанные на СВОИХ расчетах. В которых всегда есть такие стратегические ходы, что не сделает ни один человек в мире.
То есть оценка позиции движком (если фигур больше 7 или 8) верна, если человек будет играть как машина. А это пока нет.
Закрытие проекта АльфаЗеро показало, что это был лишь демонстрационный стенд. К Стокфиш приживили нейронные сети, а вот приживлять досчитывание до победы каждой ветви к АльфаЗеро не стали.
Кстати, это же машинное обучение. Очень может быть, что АльфаЗеро обучился играть именно против определенной версии Стокфиша, а не хорошо в абстрактные шахматы играть. Крамник, давно, когда компьютеры были слабыми, говорил, что любит и не боится играть с компьютерами, что надо лишь уметь создавать для них проблемы и эксплуатировать их слабые места. АльфаЗеро мог придерживаться тех позиций, той линии игры что эксплуатировала уязвимые места алгоритма Стокфиш.
* 7-фигурные - 1.5 TB
* 8-фигурные - 1.5 Пб
И судя по википедии не все 8-фигурные позиции просчитаны.