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

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

Если пользователь системы запрашивает доказательство для одного из терминальных узлов этого урезанного дерева, то программа осуществляет перебор вариантов для поиска решения (в среднем такой перебор предполагает рассмотрение также около 10 млн позиций; в 2007 г. использованному Шеффером компьютеру требовалось на это в среднем около двух минут).

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

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

Проект Шеффера стал триумфом переборных методов ИИ и массивных параллельных вычислений и внёс существенный вклад в оба этих направления. Аналогичные подходы в наши дни используются, в частности, при решении задач из области биоинформатики — там, где ограниченность наших знаний сочетается с большой комбинаторной сложностью исследуемых систем. Решение шашек раздвинуло границы возможного для алгоритмов, основанных на интенсивном переборе [615].

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

3.5 Шахматы

3.5.1 Шахматные автоматы и механизмы

Машина, играющая в шахматы, — этот образ давно занял в массовой культуре место одного из наиболее узнаваемых символов искусственного интеллекта. Многие книги и статьи, посвящённые искусственному интеллекту вообще или компьютерным шахматам в частности, не обходятся без изображения антропоморфного автоматона в турецком тюрбане, восседающего за шахматной доской. Интернет-портал, созданный компанией Amazon для разметки людьми массивов данных для задач машинного обучения, получил название Amazon Mechanical Turk. В честь того же «турка» получили имена сразу несколько шахматных программ, например программа Mr. Turk Гари Буса и Джеймса Мундстока из Миннесотского университета, The Turk турецкого программиста Якупа Ипека, шахматный робот Raspberry Turk Джоуи Мейера и шахматная программа The Turk, созданная Ингви Бьёрнссоном и Андреасом Юнгхансом — учениками Джонатана Шеффера, того самого, под руководством которого удалось создать идеального игрока в шашки.

Итак, первый шахматный «автомат», созданный придворным инженером Вольфгангом фон Кемпеленом, был продемонстрирован в Вене в 1769 г. Устройство представляло собой выполненную в натуральную величину восковую фигуру, одетую в экзотический турецкий наряд и сидящую за деревянным ящиком (1,2 × 0,6 × 0,9 м) с шахматной доской на крышке. Перед началом игры дверцы ящика раскрывались, и при помощи свечи публике демонстрировался сложный бутафорский механизм. Вслед за этим дверцы закрывались, механизм заводился ключом, и начиналась игра, которую за автомат вёл спрятанный в ящике сильный шахматист [616]. «Турок» умел не только играть в шахматы, но и общаться со зрителями, указывая рукой на буквы, изображённые на специальной табличке на поверхности стола. В отличие от современных чат-ботов Автомат не испытывал проблем с прохождением теста Тьюринга.

Вольфганг фон Кемпелен, венгр по происхождению, занимал при дворе Марии Терезии высокие государственные посты советника казначейства и управляющего соляной промышленностью, составлявшей государственную монополию. Пользуясь ресурсами, свойственными его высокому положению, он создал множество интересных приспособлений и конструкций: пишущий набор для незрячих, паровую машину, гидравлическую систему фонтанов во дворце Шёнбрунн. Богатство венского двора располагало к созданию невиданных диковинок, способных потешить пресыщенную придворную аристократию.

Вот как описывает встречу с «турком» современник фон Кемпелена, писатель и журналист Карл Готлиб фон Виндиш:

Первой мыслью, возникшей после поверхностного осмотра Шахматного Игрока, стало подозрение, что его движения находятся под непосредственным руководством какого-то человека. От этой ошибки я не был освобождён сам; когда я впервые увидел, как изобретатель извлекает из алькова свой Автомат, прикреплённый к довольно большому сундуку, я, как и другие, сразу же заподозрил, что этот сундук достаточно большой, чтобы в нём уместился ребёнок — как я оценил, прикинув размеры, — лет десяти или постарше. Некоторые говорили об этом вслух, и я про себя соглашался с ними. В ответ на это фон Кемпелен поднял одежду Автомата, вытащил выдвижной ящик и открыл все двери сундука. Перемещая открытый Автомат на четырёх колёсиках, изобретатель повернул его во всех направлениях и позволил каждому присутствующему осмотреть Автомат со всех сторон.

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

Я не знаю, думали ли остальные зрители так же, как и я; мне во всяком случае показалось, что некоторые думали о сверхъестественных силах. Одна старая дама, припомнив сказки, которыми её развлекали в детстве, перекрестилась и отошла подальше к окну, чтобы быть подальше от злого духа, присутствие которого она чувствовала [617].