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

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

Игровое поле для калаха схематически изображено на рис. 14.1. Игроки (их двое) садятся друг против друга. Каждому игроку принадлежат шесть малых лунок вдоль длинной стороны поля и одна лунка большего размера по его правую руку, называемая калахом. В начале игры в каждую малую лунку помещается некоторое количество к камней (для k ≤ 3 известно полное решение; африканцы обычно используют k = 6). Ход игрока заключается в том, что он забирает все камни в одной из малых лунок на своей стороне и раскладывает их по одному в остальные лунки, двигаясь против часовой стрелки. Первый камень кладется в лунку справа от той, из которых взяты камни, затем в следующие, включая свой калах и малые лунки противника, но не калах противника. Может случиться (и это допускается правилами), что раскладывая камни, мы обойдем всю доску и вернемся в исходную лунку или даже пройдем дальше. На рис. 14.2а и b, показаны позиции до и после выполнения такого циклического хода.

Рисунок 14.1. Игровое поле для калаха. Числа в лунках показывают количество находящихся там камней.

Рисунок 14.2а. Перед циклическим ходом Макса. Макс ходит из лунки 6.

Рисунок 14.2b. После циклического хода Макса. Калах Макса пополнялся дважды.

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

Рисунок 14.3a. Серия ходов из лунки 6 Макса. Последний камень попадает в лунку 3 Макса, и из этой лунки делается повторный ход.

Рисунок 14.3b. После серии ходов. Камни из лунки 3 разложены в следующие лунки.

Рисунок 14.4а. Перед взятием в плен камней Мима. Ходом из лунки 3 Макс попадает в лунку 4 Мина.

Рисунок 14.4b. После взятия в плен камней из лунки 4 Мина. В калах Макса один камень попадает при раскладывании камней и еще три — при пленении.

Рисунок 14.5а. Многократный захват пленных Максом. Камни из лунок Мина 2, 3 и 4 берутся в плен одним ходом из лунки 6.

Рисунок 14.5b. Макс почти опустошил лунки Мина. Отметим, что Макс мог бы сделать ход с пленением из лунки 5 вместо лунки 6.

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

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

Максу следует проанализировать каждый ответ Мина на свои ходы. Допустим, один из этих ответов приводит к выигрышу Мина. Со стороны Макса было бы глупо делать ход, дающий Мину шанс на немедленную победу (хотя иногда Максу не избежать этого). В таком случае Макс узнает, какие ходы не делать. Однако, чтобы выбрать, какой ход делать, Максу придется построить еще один уровень ответов на ответы Мина к исходным ходам Макса. Если можно найти выигрышный ответ для некоторого множества ответов Мина, то Максу следует выбрать тот первоначальный ход, при котором Мину остаются только ответы, для которых есть выигрышный ответ Макса (помните дом, который построил Джек?). Если все это непонятно, попробуйте найти ходы, ответы и ответы на ответы для позиции с рис. 14.6.

Рисунок 14.6а. Ход Макса. Макс ходит из лунки 1.

Рисунок 14.6b. Результат хода Макса. Мин отвечает ходом из лунки 6.

Рисунок 14.6с. Позиция после ответа Мина. Макс отвечает ходом из лунки 2.

Рисунок 14.6d. Позиция после ответа Макса. Это всего лишь одна из примерно б3 подобных цепочек ходов.

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

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

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

Пусть Макс хочет заглянуть вперед на d уровней. Будем считать, что начальная позиция лежит на уровне 0. Постройте все шесть мыслимых ходов, приводящих нас на уровень 1. Применяя в каждой позиции уровня 1 ходы Мина, получите все позиции уровня 2.

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

Теперь, чтобы перенести оценку с уровня d на уровень 0, выполните следующие действия на всех уровнях, начиная с уровня d и кончая нулевым. Примените статическую оценочную функцию ко всем листьям на рассматриваемом уровне. Это дает разницу очков в листьях. Для нелистовых узлов постройте оценку разницы очков, найдя максимум оценок по всем непосредственным преемникам данного узла, если он находится на четном уровне, и минимум, если узел — на нечетном уровне. Такой способ действий отвечает стремлению Макса максимизировать разрыв и стремлению Мина минимизировать его (или сделать более отрицательным). После того как пройден весь путь до нулевого уровня и найдена разница очков в исходном узле, выберите любой из шести ходов, позволяющий получить эту разницу очков. Отметим, что, как правило, все листья будут находиться на уровне d. Кроме того, при построении дерева можно всегда проходить каждую ветвь сначала вглубь,т.е. строить дерево в порядке перебора в глубину, а не в порядке перебора в ширину, как описано. На рис. 14.7 показана часть возможного дерева игры. До листьев доведена лишь одна ветвь. Изображены правильные значения, вычисленные исходя из показанной на рисунке информации. Максу следует выбрать ход из лунки 1.

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

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

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

Идея этой процедуры обобщает рассмотренный пример. Допустим, что в некотором внутреннем узле А дерева ход должен сделать Макс и что он с помощью перебора в глубину уже построил полное дерево В для хода из лунки 1 и дерево С для хода из лунки 2. Предположим далее, что оценка, вычисленная при анализе дерева, равна 1 для узла В и 2 — для С. Тогда можно приписать узлу А предварительную оценку (ПО), равную 2. Что бы ни случилось, Макс может отвергнуть любой ход из А с оценкой меньше 2. Допустим теперь, что Макс начинает строить дерево для хода из лунки 3 в узел D. В узле D ход Мина. Как только D получит ПО, равную или меньшую 2, дальнейшее построение дерева ниже D окажется уже ненужным. Действительно, Мин заведомо не выберет ход с оценкой больше 2, если доступно значение 2 или меньше. Но тогда узел D не будет интересовать Макса, коль скоро он уже имеет возможность получить 2. Итак, можно прекратить раскрытие узла D. Обсуждавшееся дерево показано на рис. 14.8.

Рисунок 14.8. Часть дерева для альфа-бета-процедуры, описанного в тексте. Как только ПО в узле D опустится ниже 3, можно прекращать раскрытие узла D и его преемников.

Альфа-бета-процедура

Для выполнения альфа-бета-процедуры поиска минимакса начните с перебора дерева игры в глубину. Каждому узлу приписывается предварительная оценка (ПО) и окончательная оценка (ОО). Для листьев как ПО, так и ОО равна статической оценке. ПО во внутренних узлах Макса равна максимуму из ОО преемников этого узла, в узлах Мина — минимуму. Всякий раз, когда ПО меняется, мы проверяем, не следует ли прекратить раскрытие этого узла. (Первоначально ПО равна −∞ во внутренних узлах Макса и +∞ во внутренних узлах Мина). В узле Макса происходит отсечение всякий раз, как только ПО этого узла становится не меньше ПО какого-либо предшественника этого узла, принадлежащего Мину. Аналогично в узле Мина отсечение происходит, когда его ПО становится не больше ПО какого-либо из предшественников, принадлежащего Максу. При отсечении узла его ПО становится его ОО. Вам следует убедиться, что альфа-бета-процедура всегда выбирает тот же ход, что и обычная минимаксная процедура.

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

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

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

Длительность исполнения. Одному исполнителю на 4 недели.

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

Еще одно обобщение состоит в изменении статической оценочной функции. Часто используют оценку, равную разности числа всех камней на стороне Макса (в калахе и лунках) и числа камней на стороне Мина. Можно применить любую простую линейную функцию от 14 значений для всех лунок. Наилучшую такую функцию можно выбрать при помощи турнира {это было рассмотрено в гл. 5). Не забывайте, однако, что главным фактором, определяющим силу игрока, является, до всей видимости, глубина просмотра.

Литература

Алеф0 (Aleph0). Computer Recreations. Software — Practice and Experience, 1, pp. 297–300, 1971.

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

Белл (Bell R, С). Board and Table Games from Many Civilizations. Oxford University Press, London, 1969.

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

Нильсон (Nilsson N. J.). Problem-Solving Methods in Artificial Intelligence. McGraw-Hill, New York, NY, 1971. [Имеется перевод: Нильсон H. Искусственный интеллект. Методы поиска решений. — М.: Мир, 1973.]

Книга Нильсона, вероятно, наилучшее введение в эту дисциплину. В гл. 6 очень понятно разобраны минимаксные методы. Даются ценные рекомендации по дальнейшему чтению.

Слэйгл (Slagle J.R.). Artificial Intelligence: The Heuristic Programming Approach. McGraw-Hill, New York, NY, 1971. [Имеется перевод: Слэйгл Дж. Искусственный интеллект. Подход на основе эвристического программирования. — М.: Мир, 1973.]

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

* «Наука и жизнь», № 12, 1971.

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