Охота на электроовец. Большая книга искусственного интеллекта - Марков Сергей Николаевич

Хотя Чемпернаун в 1980 г. и описал алгоритм работы программы в письме в редакцию журнала Personal Computing, некоторые детали за три десятилетия стёрлись из памяти учёного [651]. К счастью, до нас дошло достаточно подробное описание алгоритма Turochamp, подготовленное самим Тьюрингом для вышедшего в 1953 г. сборника «Быстрее мысли: симпозиум по цифровым вычислительным машинам» (Faster than Thought: A Symposium on Digital Computing Machines) под редакцией Бертрама Баудена [652]. Текст, набранный на печатной машинке, содержит собственноручные пометки и исправления Тьюринга. Выбор хода в программе Тьюринга и Чемпернауна был основан на переборе вариантов на фиксированную глубину. При этом варианты со взятиями рассматривались в глубину вплоть до позиций, в которых ни одно взятие было невозможно. Оценочная функция Turochamp оценивала материал (конь оценивался в три пешки, слон — в три с половиной, ладья — в пять и ферзь —в десять пешек), мобильность фигур, а также некоторое количество других позиционных признаков [653].

В 2004 г., основываясь на имеющихся материалах, Фредерик Фридель — известный научный журналист, многолетний редактор журнала Computerschach und Spiele (Компьютерные шахматы и игра) и сооснователь компании ChessBase, — заручившись поддержкой одного из ведущих разработчиков ChessBase Матиаса Файста, воссоздал Turochamp в виде работающей программы. Таким образом, спустя более чем полстолетия программа Тьюринга наконец обрела компьютерное «тело».

В процессе работы над Turochamp команда ChessBase столкнулась с проблемой: программа отказалась повторять все ходы, записанные Тьюрингом в игре против Гленни. Исследователи потратили несколько недель на повторное изучение материалов Тьюринга и обсуждение особенностей их реализации. К работе команды подключился Кен Томпсон, который написал собственный код на основе инструкций Тьюринга. Но и его программа вела себя сходным образом и повторяла большую часть ходов программы ChessBase, отличавшихся от ходов Тьюринга в партии.

В чём же было дело? Были ли это ошибки Тьюринга или неточности реконструкторов?

Фридель связался с Дональдом Мичи, работавшим с Тьюрингом в Блетчли-парке, описал суть проблемы и рассказал о наиболее существенных расхождениях между ходами в партии и ходами программы. «Возможно, мы делаем что-то не так, — писал Фридель, — но я сомневаюсь в этом, поскольку очень часто, особенно в начале игры, мы получаем те же ходы с одинаковыми оценками. Думаю, вполне возможно, что Тьюринг устал после пятнадцати ходов, когда вдобавок ко всему позиция стала достаточно сложной?!» Реакция Мичи была следующей: «Вы ищете ошибку в программе, Фредерик? Нет-нет, вы должны искать её у Алана Тьюринга! Алан не заботился о деталях; его интересовал общий принцип». Он также привёл слова Чемпернауна, который помогал Тьюрингу в создании «бумажной машины»: «В натурном эксперименте, я подозреваю, мы были слегка небрежны и наверняка наделали множество ошибок, поскольку расчёты были чрезвычайно утомительны при использовании карандаша и бумаги».

Результаты работы по воссозданию Turochamp были представлены на конференции, прошедшей в Блетчли-парке 23 июня 2012 г. и посвящённой столетию со дня рождения Алана Тьюринга. Вместе с Фриделем на конференции выступил тринадцатый чемпион мира по шахматам Гарри Каспаров, который провёл короткую демонстрационную партию против Turochamp — играя чёрными, он выиграл её за 16 ходов [654].

До своей трагической смерти в 1954 г. Тьюринг так и не успел реализовать Turochamp в виде программного кода, но эстафету подхватили другие исследователи. Вообще говоря, шахматы с самого начала рассматривались в качестве своеобразного священного Грааля машинного интеллекта — эта традиция берёт истоки ещё в работах Бэббиджа. Конрад Цузе, работая над своим языком программирования Plankalkül, анализировал задачу определения валидности шахматных ходов и разработал для этого ряд программных процедур [655]^, [656]. В 1950 г. опубликована написанная двумя годами ранее программная статья Клода Шеннона «Программирование компьютера для игры в шахматы», в которой сформулированы основные подходы к созданию шахматных программ, в значительной мере определившие развитие шахматного программирования в последующие полстолетия.

В целом идеи, изложенные Шенноном в статье, во многом пересекаются с идеями Тьюринга. Шеннон также предлагает использовать оценочную функцию, принимающую в расчёт материал, мобильность, отдельные элементы пешечной структуры: слабые, изолированные и сдвоенные пешки, нахождение ладей на открытых вертикалях и некоторые другие широко известные признаки, используемые шахматистами при оценке позиции. Интересно, что Шеннон предлагает немного отличающиеся значения для оценки фигур (у Тьюринга слон стоит три с половиной пешки, а у Шеннона — три, как и конь). Шеннон также пишет о том, что перебор в узле дерева можно прерывать только в «спокойных» [quiescent] позициях, поскольку значение оценочной функции бессмысленно в середине цепочки разменов. Если при переборе в глубину на три полухода белые третьим полуходом взяли чёрного ферзя, то программа может посчитать результатом соответствующего варианта выигрыш ферзя, хотя в действительности чёрные заберут «лишнего» ферзя белых следующим ходом, тем самым уравняв позицию. Термин quiescent, употреблённый Шенноном, и в наши дни используется для обозначения в шахматных программах функций, отвечающих за анализ форсированных вариантов, например: quiescence_search() или просто quiescence(). Шеннон по сути приводит в статье свой вариант этой функции: он предлагает продолжать перебор в течение нескольких дополнительных полуходов, если хотя бы одна фигура на доске атакована более слабой фигурой, либо атакована недостаточно защищённая фигура, либо существует возможность дать шах на незащищённое поле.

Вообще статья Шеннона интересна в первую очередь как раз анализом задачи перебора вариантов. Шеннон описывает две программы — тип A и тип B. Программа типа A просматривает дерево игры на фиксированную глубину, при этом в каждом узле дерева (соответствующем позиции на доске) рассматриваются все возможные ходы соответствующей стороны. Такой подход гарантирует нахождение любой игровой комбинации, если глубина рассмотрения дерева достаточна для этого. Однако дерево шахматной игры, особенно в миттельшпиле, ветвится чрезвычайно быстро. В среднестатистической шахматной позиции возможно примерно 35 различных полуходов, что более чем в десять раз превосходит аналогичный показатель для английских шашек. Оценив вычислительные возможности машин, Шеннон делает неутешительный вывод: программа типа A вряд ли когда-либо сможет сравниться с лучшими шахматистами, ведь некоторые комбинации чемпионов мира насчитывают 15–20 ходов в глубину! В качестве альтернативы программе типа A Шеннон предлагает программу типа B, которая будет рассматривать в каждом узле дерева игры не все, а только некоторые альтернативы — это позволит увеличить глубину рассмотрения дерева за счёт уменьшения его ширины. Похожим образом действуют и профессиональные шахматные игроки — включают в рассмотрение только те варианты, которые считают осмысленными.

Дьявол, однако, как обычно, кроется в деталях. В 1950 г. в арсенале методов ИИ ещё не было инструментов, позволявших получить оценку «осмысленности» того или иного варианта, сопоставимую по качеству с человеческой. Да что уж говорить — даже самого ИИ как направления ещё не существовало. Программа типа B, руководствуясь примитивными способами отсеивания вариантов, неизбежно часто допускала бы грубые ошибки, эту проблему видел и Шеннон. Последовавшие десятилетия развития шахматных программ во многом стали поиском разумного компромисса между полным и селективным, избирательным перебором вариантов, а также поиском быстрых и в то же время умных оценочных функций.