Охота на электроовец. Большая книга искусственного интеллекта - Марков Сергей Николаевич
Если игра, подобно описанной Цермело версии шахмат, допускает достижение ничьей при помощи бесконечных последовательностей ходов, то описанный нами алгоритм по завершении работы оставит оценку для таких позиций неопределённой и нам достаточно будет просто заменить неопределённые оценки на нули, соответствующие ничьей, чтобы иметь определённые оценки для всех игровых позиций.
Получив точные оценки для всех позиций игры, мы можем использовать их для того, чтобы в любой позиции совершать идеальный ход. Достаточно просто просмотреть список всех возможных ходов в текущей позиции и выбрать тот, который ведёт в позицию с наилучшей для нас оценкой.
Таким образом мы и получаем введённые ранее Цермело заполненные множества последовательностей ходов.
3.3.3 Применение обратной индукции для анализа шахматных окончаний
В 1969 г. в СССР математики Александр Брудно и Игорь Ландау применили ретроанализ для решения шахматной задачи под названием «Неприкосновенный король». В задаче на доске три фигуры: белый король, белый ферзь и чёрный король. Белый король находится на поле c3 и не имеет права двигаться (поэтому и называется неприкосновенным). Вопрос заключается в том, может ли белый ферзь с помощью своего неприкосновенного короля заматовать одинокого короля чёрных. Эта задача была известна ещё в XIX в., и многие шахматисты, в том числе гроссмейстеры, ошибочно предполагали, что заматовать короля нельзя. Брудно и Ландау выяснили с помощью машины, что мат даётся при любом начальном положении белого ферзя и чёрного короля, причём не позднее двадцать третьего хода. Они также доказали, что белые побеждают только в том случае, если «неприкосновенный король» в задаче стоит на полях c3, c6, f3 или f6. Вполне вероятно, что это был первый случай в истории шахмат (и математики), когда вычислительная машина решила шахматную задачу раньше человека [513], [514].
В 1970 г. математик Томас Штрохлейн защитил диссертацию о компьютерном анализе шахматных окончаний [515]. Когда на шахматной доске остаётся мало фигур, задача нахождения оптимальных ходов становится вычислимой. В 1969 г. Штрохлейн выполнил ряд расчётов на компьютере AEG-Telefunken TR4 в Вычислительном центре им. Лейбница в Мюнхене (Leibniz-Rechenzentrum München, сегодня это учреждение обычно называют Суперкомпьютерным центром им. Лейбница), проанализировав такие окончания, как «король и ферзь против короля» (KQK), «король и ладья против короля» (KRK), «король и пешка против короля» (KPK), «король и ферзь против короля и ладьи» (KQKR), «король и ладья против короля и слона» (KRKB) и «король и ладья против короля и коня» (KRKN) [516]. Это традиционно считается первым случаем практического применения ретроспективного анализа для шахматных окончаний [517].
В 1970-е гг. сотрудники Института проблем управления АН СССР Эдуард Комиссарчик и Арон Футер осуществили машинный анализ эндшпиля «король, пешка, ферзь против короля и ферзя» (с белой пешкой, фиксированной на поле g7) [518], а также эндшпиля «король, пешка, ладья против короля и ладьи» (KRPKR) [519], [520].
Именно работу по анализу последнего эндшпиля я вспоминаю, когда смотрю очередную серию анимационного сериала Netflix «Любовь, смерть и роботы» (Love, Death & Robots), и вот почему. В 2007 г. свет увидела книга Дэвида Леви с похожим названием — «Любовь и секс с роботами» (Love and Sex with Robots) [521]. Леви также выступает в качестве организатора скандально известной одноимённой ежегодной конференции (loveandsexwithrobots.org), проведение которой в 2015 г. было сорвано из-за запрета властей Малайзии. Дэвид Леви весьма яркая личность в мире ИИ. Например, он руководил разработкой и финансировал создание чат-ботов, становившихся победителями премии Лёбнера в 1997-м (Converse) и 2008-м (Do-much-more). Леви возглавляет Международную ассоциацию компьютерных игр (International Computer Games Association, ICGA), созданную в 1977 г. как Международная ассоциация компьютерных шахмат (International Computer Chess Association, ICCA). Леви сам является международным мастером спорта по шахматам, победителем чемпионата Шотландии по шахматам (1968-го, в 1975-м разделил первое место со Стивеном Суонсоном), а в 1972 г. играл на первой доске за команду Шотландии на Шахматной олимпиаде в Скопье. Как видите, мы совсем близко, до искомого эндшпиля уже практически рукой подать.
Кроме игры в шахматы и очевидного интереса к теме ИИ, Дэвид Леви также является заядлым спорщиком.
В 1968 г. Леви и Джон Маккарти, один из пионеров шахматного программирования (и автор термина «искусственный интеллект», о чём мы упоминали в начале книги), встретились на вечеринке, устроенной Дональдом Мичи. Маккарти пригласил Леви сыграть в шахматы — и последний одержал победу. Маккарти прокомментировал эту победу словами: «Вы можете победить меня, но через десять лет появится компьютерная программа, которая сможет победить вас». Леви предложил заключить пари, и Маккарти согласился. Спорщики поставили по 500 фунтов, это была более чем внушительная сумма, эквивалентная примерно 14 000 долларов 2023-го [522]. По признанию самого Леви, в то время он зарабатывал 895 фунтов в год [523]. Позже ставка более чем удвоилась, когда к ней присоединились Дональд Мичи, Сеймур Пейперт из Массачусетского технологического института и Эд Коздровицкий из Калифорнийского университета в Дейвисе.
Забегая вперёд, скажем, что Леви одержал победу в этом пари, выиграв в последующие годы несколько матчей против различных программ (Chess 4.5, Каиссы и MacHack), включая решающий матч 1978 г. против программы Chess 4.7 в Торонто [524], [525], а в 1984 г. Леви выиграл вторую, на этот раз пятилетнюю ставку в пари против разработчиков программы Cray Blitz [526].
Но вернёмся назад, когда исход этого пари ещё был неясен, а Леви не прекращал спорить.
В 1973 г. во время Северо-Американского чемпионата по шахматам среди компьютерных программ (North American Computer Chess Championship, NACCC), организованного Ассоциацией вычислительной техники (Association for Computing Machinery, ACM) в Атланте, Леви поспорил с создателями программы CHAOS, которые выразили сомнение в его заявлении о том, что в течение года они не смогут запрограммировать компьютер для правильной игры в окончании «король и ладья с пешкой против короля и ладьи» так, чтобы машина всегда была способна выиграть, находясь в выигрышной позиции, и никогда не проигрывала в ничейной. Сумма пари составила 100 долларов, и спустя год, в ноябре 1974 г., Леви получил деньги, поскольку программисты признали, что задача оказалась слишком сложной для них.
Однако удача не всегда способствовала Леви, и как минимум одно знаменитое пари он проиграл. Этот спор в истории компьютерных шахмат носит название «Скотч против водки» (Scotch versus Vodka). Как пишет сам Леви, «будучи довольно жадным», он решил повторить успех пари с создателями CHAOS и в декабре 1974 г., находясь в Москве, заключил аналогичное пари с Владимиром Арлазаровым: в случае поражения Леви должен был подарить Арлазарову двенадцать бутылок скотча, а в случае победы Леви должно было достаться двенадцать бутылок водки. Примерно через год спор завершился победой Арлазарова, под началом которого как раз и работали Комиссарчик и Футер, успешно решившие упомянутое окончание при помощи программы, использующей метод ретроспективного анализа [527], [528].
