все возможные позиции и присвоим каждой из них неопределённую оценку, поскольку мы пока не знаем, какие из них являются выигрышными, проигрышными или ничейными. Затем присвоим оценку тем позициям, в которых на доске присутствует три крестика в ряд, — эти позиции выиграны крестиками, и мы с чистой совестью можем присвоить им соответствующую оценку, равную 1 (единицей мы будем обозначать победу крестиков). Аналогичную операцию проделаем с позициями, в которых в ряд выстроились три нолика, — этим, выигранным ноликами позициям мы присвоим оценку –1 (минус единица будет соответствовать позициям, выигранным ноликами). Затем настаёт очередь очевидно ничейных позиций, то есть таких позиций, в которых не осталось ни одного свободного поля, но при этом отсутствуют выстроившиеся в ряд по три крестики и нолики. Оценку таких позиций назначим равной 0, что будет соответствовать ничьей.

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

3. Аналогично для позиций с очередью хода, принадлежащей ноликам, имеющих неопределённую оценку, при наличии у ноликов хотя бы одного хода, ведущего в позицию с оценкой –1, устанавливаем оценку, равную –1.

4. Рассмотрим теперь позиции, для которых все возможные ходы приводят в позиции с определённой оценкой. Для таких позиций выберем оценку, соответствующую лучшему из возможных исходов для стороны, которой принадлежит очередь хода. То есть если очередь хода принадлежит крестикам и у них есть ход, ведущий в ничейную позицию, то оценкой позиции является 0, в противном случае (т. е. если все ходы ведут к проигрышным позициям) оценкой позиции становится –1. Если же очередь хода за ноликами и у них есть ход, ведущий в ничейную позицию, то оценкой позиции становится 0, в противном же случае — 1.

5. Если на шагах 2–4 была получена хотя бы одна новая оценка, возвращаемся к шагу 2.

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

Работу алгоритмов удобно рассматривать в графической форме, используя представление игры в виде древовидной структуры, в которой узлы соответствуют позициям в игре, а ветви — возможным ходам. Алгоритм начинает работу с установления оценки для нижних (терминальных) узлов дерева, а затем постепенно поднимается вверх, пока не достигает корневого узла — начальной позиции игры.

Рис. 54. Метод ретроспективного анализа в применении к игре крестики-нолики

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

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

Таким образом мы и получаем введённые ранее Цермело заполненные множества последовательностей ходов.

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). Леви сам