МАШИНА ДЛЯ ИГРЫ В ШАХМАТЫ

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

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

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

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

Игра в шахматы является идеальной для начальных попыток в этом направлении по нескольким причинам. Она четко определена как допустимыми операциями (шахматные ходы), так и конечной целью (мат). Она не является ни настолько простой, чтобы быть тривиальной, ни слишком трудной для получения удовлетворительного решения.

Рис. 1. Шахматный автомат XVIII века действительно управлялся человеком, спрятанным внутри.

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

Уже имеется значительная литература по описанию машин, играющих в шахматы. В конце XVIII и начале XIX века венгерский изобретатель Вольфганг фон Кемпелен поразил Европу устройством, которое известно под названием Маельзельского (Maelzels) шахматного автомата. Автор демонстрировал автомат, путешествуя по континенту. Вскоре появилось большое число статей, объяснявших его действие, включая аналитическую статью Эдгара Аллана По. Большинство авторов заключало вполне правильно, что автомат управляется шахматным мастером, скрытым внутри. Несколько лет спустя был вскрыт истинный принцип его работы (см. рис; 1).

Более честная попытка создать машину, играющую в шахматы, была сделана в 1914 г. испанским изобретателем Л. Торресом-и-Квеведо (L. Torres у Quevedo), который построил автомат, разыгрывающий эндшпиль — король и ладья против короля. Машина,

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

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

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

Машина имеет четыре главные части:

1) арифметическое устройство,

2) управляющее устройство,

3) устройство для запоминания и хранения чисел (числовая память),

4) устройство для запоминания программ (программная память).

(В некоторых конструкциях устройства для запоминания чисел и программ устроены одинаково.)

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

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

Оно означает: сложить число, хранящееся в ячейке 372, с числом из ячейки 451 и получившуюся сумму записать в ячейку 133. Другой тип команд заставляет машину сделать выбор продолжения решения. Например, команда:

означает: сравнить содержимое ячеек 291 и 118 и, если число в ячейке 291 больше числа в ячейке 118, перейти к выполнению следующей по порядку команды; если нет, перейти к выполнению команды, хранящейся в ячейке 345. Этот тип команд позволяет машине сделать выбор из двух возможностей в зависимости от результатов предыдущих вычислений. «Словарь» электронной машины может включать около 30 различных типов команд.

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

Задача постановки игры в шахматы на вычислительной машине может быть разделена на три основных этапа.

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

2. Должна быть выбрана некоторая стратегия для выбора хода.

3. Эта стратегия должна быть переведена в последовательность элементарных команд машины или программу.

На рис. 2 показан код для шахматной доски и фигур. Каждый квадрат имеет номер, состоящий из двух чисел: первое число соответствует строке или горизонтали, а второе — столбцу или вертикали. Разным шахматным фигурам приписаны различные числа: пешке 1, коню 2, слону 3, ладье 4 и т. д. Белым фигурам соответствуют положительные числа, а черным отрицательные. Положение всех фигур на доске может быть представлено последовательностью 64 чисел, причем пустому квадрату соответствует 0. Таким образом, любая шахматная позиция может быть записана как ряд чисел и введена в числовую память машины.

Любой ход определяется заданием номера поля, на котором стояла фигура, и номером поля, на который она пошла. Обычно этих двух номеров бывает достаточно для описания хода, но нужно учитывать специальный случай превращения пешки в более ценную фигуру, когда необходимо третье число. Во всех других случаях третье число равно нулю. Следовательно, ход коня с поля 01 на 22 кодируется как 01, 22, 0. Продвижение пешки с 62 на 72 и превращение ее в ферзя записывается как 62, 72, 5.

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

Рис. 2. Кодирование начальной позиции для шахматной машины изображено в виде шахматной доски. Каждый квадрат может быть определен двумя числами: одно задает горизонталь, авторов — вертикаль. Фигурам также соответствуют числа.

Эти эмпирические принципы вносят некоторый порядок в нагромождение возможных вариантов игры. Даже огромные скорости электронных вычислительных машин совершенно недостаточны для ведения абсолютно точной игры в шахматы путем просчета всех возможных вариантов игры до конца. В типичной шахматной позиции имеется около 32 возможных ходов с 32 допустимыми ответами, это создает 1024 варианта на один ход. В большинстве шахматных партий делается 40 или больше ходов с каждой стороны. Следовательно, общее число вариантов в средней игре составляет около 10120. Машина, вычисляющая один вариант в одну миллионную долю секунды, будет работать лет, прежде чем выберет первый ход!

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

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

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

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

Глубина анализа и выбора, достигнутая шахматными мастерами при проверке различных вариантов, была изучена экспериментально датским шахматистом и психологом А. Д. де Гроотом {A. D. De Groot). Он показывал различные типовые позиции шахматным мастерам и просил их выбрать наилучший ход, описывая

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

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

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

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

1) Она делает конкретные вычисления с гораздо большей скоростью.

2) Ее игра свободна от ошибок, не считая программных слабостей, в то время как человек часто делает простые и очевидные просмотры.

3) Машина никогда не будет лениться, никогда не поддастся соблазну сделать ход инстинктивно без надлежащего анализа позиции.

4) У машины нет «нервов», следовательно, она не будет переоценивать свою позицию или наоборот — недооценивать свои шансы.

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

В противовес этим качествам ум человека обладает гибкостью, воображением и способностью к обучению.

В некоторых случаях машина может победить человека, задавшего ей стратегию игры. Но в одном смысле он все же остается сильнее, - зная стратегию игры машины, человек может применить ту же самую тактику, но продолжив ее на большую глубину. При этом, возможно, ему потребуется несколько недель для выбора хода, а машина вычислит его в несколько минут. При одинаковом количестве времени на «обдумывание» быстродействие, выдержка и высокая точность машины позволят ей успешно играть с человеком. Однако, сильно разозлившись, создатель программы может легко ослабить игровое мастерство машины, изменив программу таким образом, чтобы уменьшилась глубина исследования (см. рис. 3).

Эта идея была выражена в карикатурах на страницах журнала (The Saturday Evening Post) год назад.

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

Случайные элементы могут быть введены также в начале игры. Желательно иметь много стандартных дебютов с различными вариантами (до нескольких сотен), которые хранятся в памяти машины. Начиная с первого хода, до тех пор пока противник не отклонится от стандартных ответов или машина не исчерпает последовательности ходов, записанных в памяти, — она будет играть по теории. Это нельзя назвать обманом, так как таким же образом шахматные мастера разыгрывают дебют.

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

Комбинации такого типа часто не замечаются в любительских играх.

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

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

Главный вопрос, который легче задать, чем на него ответить, это: воспроизводит ли машина, играющая в шахматы, процесс «мышления»? Ответ будет зависеть от того, как определить мышление. Так как сейчас нет общего решения о точном смысле этого термина, на этот вопрос нельзя дать определенный ответ. С точки зрения поведения машина действует так, как будто она мыслит.

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

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

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

заметить, что это почти точное описание того, как действует, играя в шахматы, машина, если заменить слово «мысленно» словами «внутри машины».

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