ИГРАЮЩИЕ МАШИНЫ

Конструирование играющих машин на первый взгляд может показаться скорее интересным времяпрепровождением, чем серьезной научной задачей, и действительно, для многих ученых—любителей и профессионалов — этот увлекательный предмет стал любимым занятием. Однако эта работа имеет свою серьезную сторону и важную цель, и по крайней мере четыре или пять университетов и лабораторий работают сейчас в этом направлении. Если бы был жив Бенджамин Франклин, то, я уверен, он заинтересовался бы этой проблемой, так как в ней сливаются два направления, которым он отдавал энергию и время. Всем нам известны его достижения как ученого и изобретателя, но не столь широко известно, что он был также и сильным шахматистом. Он является автором занимательного очерка под названием «Мораль в шахматах», представляющего собой смесь шахматной теории и дипломатии, которому вполне подошел бы подзаголовок «Как можно быть счастливым, даже будучи шахматистом».

Одним из наиболее важных технических достижений за последние двадцать лет является развитие универсальных электронных вычислительных машин. Эти машины могут автоматически выполнять длинные последовательности вычислительных операций со скоростью тысяч операций в секунду. Последовательность команд, сообщающих машине, что именно ей следует делать, называется программой. Если машине предстоит решить задачу, то сначала нужно составить программу, переводящую процесс нахождения решения в ряд простых операций. Эти основные операции могут включать элементарные арифметические действия — сложение, умножение и т. п., а также операции «передачи управления», позволяющие машине выбрать одну из двух возможностей в зависимости от результатов предшествующих вычислений. Когда программа

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

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

Составление программ для решения таких неарифметических задач на вычислительных машинах важно по целому ряду причин. Оно расширяет наши знания относительно возможностей того поразительно гибкого орудия, каким является универсальная вычислительная машина; представляется несомненным, что мы лишь поверхностно знакомы с возможностями таких вычислительных устройств и каждая новая сфера их применения ведет к расширению наших знаний. Кроме того, это более широкое использование вычислительных машин приводит к полезным изменениям в их конструкции, порождает новые типы операций, которые могут использоваться в необычных программах и даже в обычных численных задачах. Наконец, можно надеяться, что исследования в области конструирования играющих машин могут привести к углублению наших знаний о работе человеческого мозга. Разумеется, было бы наивным ожидать, что мозг действует так же, как машина, предназначенная для ведения игр или сколько-нибудь аналогично ей. Тем не менее несомненно, что создание любой обучающейся машины будет освещать путь к пониманию работы мозга.

Пожалуй, самой первой играющей машиной был Маельзельский автомат для игры в шахматы. Это было устройство, сконструированное в 1769 году австрийцем фон Кемпеленом и широко демонстрировавшееся в Европе и Америке предпринимателем Маельзелем.

Большая механическая фигура, сидевшая за столом, играла с людьми в шахматы. Перед демонстрацией стол и фигура открывались, чтобы показать, что внутри никого нет. Машина обычно выигрывала партии против человека-шахматиста. В то время автомат вызвал подлинную сенсацию и предлагался ряд теорий с объяснением его работы. Среди них был, например, очерк Эдгара Аллана По, который вывел верное заключение (хотя отчасти при помощи неверных аргументов), что машина была мистификацией и в действительности управлялась человеком-шахматистом, искусно спрятанным внутри. Так оно на самом деле и было, а требуемое впечатление, как это бывает во многих трюках иллюзионистов,

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

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

Если не принимать во внимание подобных мистификаций, то играющие машины в зависимости от степени их сложности можно подразделить на три основных типа. Самый простой тип представляют машины, предназначенные для игры в полностью проанализированные игры. Под этим подразумевается, что для сравнительно простой игры полностью известна стратегия, которая диктует соответствующий ход в каждой ситуации, возникающей в игре. Примерами таких игр являются «крестики и нолики» (tic-tac-toe), настольная игра Ним и ряд других математических игр. В подобных случаях можно представить известную стратегию в виде программы для универсальной или специализированной вычислительной машины так, чтобы машина делала правильный ход в любой момент игры. Этот тип машины, как правило, будет играть наилучшим образом. Машина будет выигрывать всякий раз, когда возможен выигрыш.

Одна из первых машин этого типа была создана приблизительно в 1914 г. испанским изобретателем Торресом-и-Квеведо. Эта машина проводила шахматный эндшпиль — король и ладья против короля. Этот эндшпиль сравнительно прост, и надлежащие ходы могут быть описаны несколькими простыми правилами. Машина Торреса переводила эти правила в переключательную схему. Хотя по сегодняшним стандартам это устройство выглядит простым, для своего времени это было, несомненно, выдающимся изобретением.

Другой игрой, поддающейся полному математическому анализу, является игра Ним. Было сконструировано много машин, играющих в эту игру. Как я полагаю, первая машина такого рода

экспонировалась на всемирной выставке в Нью-Йорке в 1939 г. Игру Ним математики исследовали давно, и оказалось, что правильную стратегию этой игры очень легко выразить в двоичной системе счисления. Релейные схемы естественнее всего могут быть приспособлены к двоичной системе, и поэтому было легко перевести математическую стратегию игры в Ним и в релейную схему. Большинство машин для игры в Ним играют наилучшим образом в том смысле, что они выигрывают, когда выигрыш вообще возможен, но они обычно представляют сделать первый ход человеку, так что последний может выиграть, если он играет безошибочно. Если противник сделает хотя бы одну ошибку, машина перехватывает инициативу и выигрывает.

Любимой игрой всех, кто конструирует машины, является игра «крестики и нолики». Игру можно полностью проанализировать путем перечисления всех возможных партий. Если принять во внимание симметрию доски, то число таких вариантов сравнительно невелико. Одна из первых машин, играющих в крестики и нолики, была создана лет пятнадцать назад У. Кейстером, и здесь у меня имеется такая машина, реализующая электрическую схему Кейстера. При игре с машиной первый ход делает человек и машина всегда сводит игру по меньшей мере к ничейному результату. Если, однако, игрок допускает серьезную ошибку, то машина выигрывает. В машине имеется также «противообманное» устройство. Если попробовать сделать два хода подряд, то загорается лампочка «протеста».

Второй основной класс машин относится к играм, полный анализ которых неизвестен, но для которых известны общие принципы игры или принципы построения правильной стратегии. К таким играм относится большинство общеизвестных игр, как, например, шашки, шахматы, бридж и покер. Такая машина, играющая в шахматы, исследует в каждой данной позиции различные ходы, которые она может сделать, различные ответные ходы своего партнера и т. д. на два или три хода вперед. В конце каждой из таких проб машина может применить к результатам «оценочную функцию». В качестве своего хода она выбирает тот, который ведет к позиции с наивысшей оценкой, а относительно противника предполагается, что он играет так, чтобы свести эту оценку к минимуму. Это — известный в теории игр процесс минимакса. Поскольку оценочная функция или общие принципы игры не могут быть здесь непогрешимыми, сконструированная на их основе машина не будет играть безукоризненно. Однако можно ожидать, что она будет делать достаточно хорошие ходы, если общие принципы тщательно продуманы.

Примером системы, реализующей игру по общим стратегическим принципам этого типа, является программа игры в шашки,

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

Другая программа для игры в шашки была разработана A. Л. Самуэлем, и имеются сведения, что между машинами Стрэчи и Самуэля организуется матч. О программе Самуэля рассказывают одну, может быть неправдоподобную, историю. Когда он впервые ввел свою программу в машину и нажал пусковую кнопку, чтобы машина сделала свой первый ход, она бешено проработала в течение нескольких минут, а потом напечатала ответ; «Сдаюсь»!

Другая играющая машина, принципиально совершенно иного типа была построена Э. Ф. Муром и мной. Это специализированная машина для игры в «Геке». Геке — это игра на доске, разбитой на правильные шестиугольники. Двое игроков по очереди передвигают фигурки людей по шестиугольникам. Один играет желтыми фигурами, а другой — синими. Цель желтых — образовать непрерывную цепь фигур от верхнего края доски до нижнего. Цель синих — образовать непрерывную цепь фигур от правого края доски до левого. После изучения этой игры у Мура и у меня возникла мысль представить доску в виде сети сопротивлений, а положение фигур — напряжением, подаваемым в соответствующие точки сети: положительным для желтых фигур и отрицательным для синих. Мы предполагали, что некоторые седловые точки в поле напряжения, образовавшемся в сети сопротивлений, будут соответствовать хорошим ходам в игре. Было построено простое устройство, реализующее эту сеть, и оказалось, что машина играла достаточно хорошо. Она выигрывала около 70% игр против посетителей лаборатории, если делала первый ход. Если машина делала второй ход, то выигрыш составлял 50% или меньше. Часто нас приятно удивляло, когда машина выбирала ходы, представлявшиеся на первый взгляд слабыми, но после тщательного анализа оказывавшиеся правильными и сильными. В одной из начальных позиций машина даже «открыла» такой ход, который был лучше всех ходов, применявшихся нами, и которым теперь обычно пользуются.

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

проигрышей и т. п. машина постепенно улучшит свое искусство игры. Хотя эта проблема обсуждалась много раз, машин, полностью подходящих под это определение, построено не было. Эта задача очень трудна, и стоимость проведения соответствующей программы исследований очень велика, но уже были построены несколько более элементарные обучающиеся машины. Рассмотрим две из них.

Д. У. Хегельбергер разработал интересное устройство, которое играет с человеком в «монетку». В обычной игре в монетку два игрока показывают монеты одновременно. Они могут показать монету либо гербом, либо решеткой. При совпадении выигрывает первый игрок, в противном случае — второй.

Получается своего рода психологическая игра в отгадывание, и выигрывает в конечном итоге тот, кто лучше может предсказать реакции противника. В машине Хегельбергера монеты заменены лампочками и переключателями. В машине есть регистры памяти, в которых запоминаются некоторые результаты игры с противником. Во время игры эти результаты анализируются машиной с целью отыскания некоторой системы или психологической тенденции у игрока — человека. Например, у одного может быть тенденция перейти от герба к решетке, когда он выиграл два раза подряд. Другой может делать обратное. Угадывающая машина ищет такие тенденции у противника, и те, что она находит, используются в последующей игре. Таким образом, она предполагает, что в будущем человек будет следовать тем тенденциям, которым он следовал в прошлом, и машина играет так, чтобы выиграть, если это повторение на самом деле произойдет. В результате игры с самыми различными людьми машина выиграла около 55% партий, что гораздо лучше, чем 50%, если бы выигрыш был чисто случайным.

Глубоко заинтересованный машиной Хегельбергера, я сконструировал другую машину для игры в монетку, использующую те же основные принципы, но гораздо более простую по объему памяти и другим деталям. После долгих споров о том, какая машина выиграет, мы решили поставить эксперимент. Была сконструирована третья машина — посредник, которая могла передавать информацию между обеими машинами, считать очки и следить, чтобы игра велась по правилам. Все три машины были соединены вместе и играли несколько часов, причем зрители заключали небольшие пари и сопровождали игру громкими криками. Оказалось, что меньшая и, как предполагалось, менее «умная» машина победила большую со счетом около 55 на 45. Возможно, это произошло потому, что она быстрее меняла свои оценки действий партнера. Обе машины стараются найти схему игры противника, и как только одна находит

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

Машина для разгадывания лабиринта является другим примером обучающейся машины. Хоть она и не учится играть в какую-нибудь игру, она опытным путем учится решать определенный тип задач. Классический пример психологической задачи обучения состоит в том, что животное помещают в лабиринт и наблюдают за тем, какое время ему понадобится, чтобы найти дорогу к кормушке. Попыткой выяснения того, как подобную задачу сможет решить релейная схема, является машина для разгадывания лабиринта. Перегородки в лабиринте можно произвольно менять местами и получить около тысячи миллиардов различных лабиринтов, которые решает машина. Во время своего первого путешествия мышь следует принципам стратегии исследования, включающей большое количество испытаний и ошибок и неверных ходов, приводящих в тупики. Наконец, она достигает медного диска, представляющего кормушку. Если теперь поместить мышь в первоначальное положение, то она пойдет прямо к цели, без ошибочных ходов. Это показывает, что релейная схема запомнила верный путь. Более того, если мышь поместить в другую часть лабиринта, которую она исследовала раньше, она придет также прямо к цели. Если ее поместить в ту часть лабиринта, в которую она не попадала ранее, то она будет бродить до тех пор, пока не попадет на знакомую клетку, а оттуда пойдет прямо к цели. Если теперь поместить ее снова в исходную точку, она прямо идет к цели. Это показывает, что мышь добавила информацию об этой части лабиринта к предыдущему опыту. Наконец, если изменить лабиринт, мышь сначала пробует прежний путь, и когда ее постигает неудача, начинает вновь свои исследования и ищет другой путь к цели. Если кормушка закрыта со всех сторон и пути к ней нет, то мышь обследует все части лабиринта, до которых можно добраться.

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