Резюме
• Игры двух лиц поддаются формальному представлению в виде И/ИЛИ-графов. Поэтому процедуры поиска в И/ИЛИ-графах применимы для поиска в игровых деревьях.
• Простой алгоритм поиска в глубину в игровых деревьях легко программируется, но для игр, представляющих интерес, он не эффективен. Более реалистичный подход — минимаксный принцип в сочетании с оценочной функцией и поиском, ограниченным по глубине.
• Альфа-бета алгоритм является эффективной реализацией минимаксного принципа. Эффективность альфа-бета алгоритма зависит от порядка, в котором просматриваются варианты ходов. Применение альфа-бета алгоритма приводит, в лучшем случае, к уменьшению коэффициента ветвления дерева поиска, соответствующему извлечению из него квадратного корня.
• В альфа-бета алгоритм можно внести ряд усовершенствований. Среди них: продолжение поиска за пределы ограничения по глубине вплоть до спокойных позиций, последовательное углубление и эвристическое отсечение ветвей.
• Численная оценка позиций является весьма ограниченной формой представления знаний о конкретной игре. Более богатый по своим возможностям метод представления знаний должен предусматривать внесение в программу знаний о типовых ситуациях. Язык Советов (Advice Language) реализует такой подход. На этом языке знания представляются в терминах целей и средств для их достижения.
• В данной главе мы составили следующие программы: программная реализация минимаксного принципа и альфа-бета процедуры, интерпретатор языка AL0 и таблица советов для окончания "король и ладья против короля".
• Были введены и обсуждены следующие понятия:
игры двух лиц с полной информацией
игровые деревья
оценочная функция, минимаксный принцип
статические оценки, рабочие оценки
альфа-бета алгоритм
последовательное углубление,
эвристическое отсечение,
эвристики для обнаружения спокойных позиций
Языки Советов
цели, ограничения, элементарные советы,
таблица советов
Литература
Минимаксный принцип, реализованный в форме альфа-бета алгоритма, — это наиболее популярный метод в игровом программировании. Особенно часто он применяется в шахматных программах. Минимаксный принцип был впервые предложен Шенноном (Shannon 1950). Возникновение и становление альфа-бета алгоритма имеет довольно запутанную историю. Несколько исследователей независимо друг от друга открыли либо реализовали этот метод полностью или частично. Эта интересная история описана в статье Knuth and Moore (1978). Там же приводится более компактная формулировка альфа-бета алгоритма, использующая вместо минимаксного принципа принцип "него-макса" ("neg-max" principle), и приводится математический анализ производительности алгоритма. Наиболее полный обзор различных минимаксных алгоритмов вместе с их теоретическим анализом содержится в книге Pearl (1984). Существует еще один интересный вопрос, относящийся к минимаксному принципу. Мы знаем, что статическим оценкам следует доверять только до некоторой степени. Можно ли считать, что рабочие оценки являются более надежными, чем исходные статические оценки, из которых они получены? В книге Pearl (1984) собран ряд математических результатов, имеющих отношение к ответу на этот вопрос. Приведенные в этой книге результаты, касающиеся распространения ошибок по минимаксному дереву, объясняют, в каких случаях и почему минимаксный принцип оказывается полезным.
Сборник статей Bramer (1983) охватывает несколько аспектов игрового программирования. Frey (1983) — хороший сборник статей по шахматным программам. Текущие разработки в области машинных шахмат регулярно освещаются в серии Advances in Computer Chess и в журнале ICCA.
Метод Языка Советов, позволяющий использовать знания о типовых ситуациях, был предложен Д. Мики. Дальнейшее развитие этого метода отражено в Bratko and Michi (1980 a, b) и Bratko (1982, 1984, 1985). Программа для игры в эндшпиле "король и ладья против короля", описанная в этой главе, совпадает с точностью до незначительных модификаций с таблицей советов, корректность которой была математически доказана в статье Bratko (1978). Ван Эмден также запрограммировал эту таблицу советов на Прологе (van Emden 1982).
Среди других интересных экспериментов в области машинных шахмат, преследующих цель повысить эффективность знаний (а не перебора), следует отметить Berliner (1977), Pitrat (1977) и Wilkins (1980).
Advances in Computer Chess Series (M.R.B. Clarke, ed). Edinburgh University Press (Vols. 1-2), Pergamon Press (Vol. 3).
Berliner M. A. (1977); A representation and some mechanisms for a problem solving chess program. In: Advances in Computer Chess 1 (M.R.B. Clarke, ed). Edinburgh University Press.
Bramer M. A; (1983, ed). Computer Game Playing: Theory and Practice. Ellis Horwood and John Wiley.
Bratko I. (1978) Proving correctness of strategies in the AL1 assertional language. Information Processing Letters 7: 223-230.
Bratko I. (1982). Knowledge-based problem solving in AL3. In: Machine Intelligence 10 (J. Hayes, D. Michie, J. H. Pao, eds.). Ellis Horwood (an abbreviated version also appears in Bramer 1983).
Bratko I. (1984). Advise and planning in chess end-games. In: Artificial and Human Intelligence (S. Amarel, A. Elithorn, R. Banerji, eds.). North-Holland.
Bratko I. (1985). Symbolic derivation of chess patterns. In: Progress Artificial Intelligence (L. Steels, J. A. Campbell, eds.). Ellis Horwood and John Wiley.
Bratko I. and Michie D. (1980a). A representation of pattern-knowledge in chess end-games. In: Advances in Computer Chess 2 (M.R.B. Clarke, ed). Edinburgh University Press.
Bratko I. and Michie D. (1980b). An advice program for a complex chess programming task. Computer Journal 23: 353-359.
Frey P. W. (1983, ed.). Chess Skill in Man and Machine (second edition). Springer-Verlag.
Knuth D. E. and Moore R. W. (1975). An analysis of alpha-beta pruning. Artificial Intelligence 6: 93-326.
Pearl J. (1984). Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley.
Pitrat J. (1977). A chess combination program which uses plans Artificial Intelligence 8: 275-321.
Shannon C.E. (1950). Programming a computer for playing chess. Philosophical Magazine 41: 256-275. [В сб. Шеннон К. Работы по теории информации и кибернетике. — М.: ИЛ., 1963.]
van Emden M. (1982). Chess end-game advice: a case study in computer utilisation of knowledge. In: Machine Intelligence 10 (J. Hayes, D. Michie, J.H. Pao, eds). Ellis Hordwood.
Wilkins D.E. (1980). Using patterns and plans in chess. Artificial Intelligence 14: 165-203.
Глава 16
Программирование в терминах типовых конфигураций
В этой главе мы будем заниматься системами, ориентированными на типовые конфигурации ("образцы"), рассматривая их как некоторый специальный подход к программированию. Языком, ориентированным на образцы, можно считать и сам Пролог. Мы реализуем небольшой интерпретатор для простых программ этого типа и постараемся передать дух такого "конфигурационной" программирования на нескольких примерах.
16.1. Архитектура, ориентированная на типовые конфигурации
Под системами, ориентированными на типовые конфигурации (образцы), мы будем понимать программные системы специальной архитектуры. Для некоторых конкретных типов задач такая архитектура дает преимущества по сравнению с традиционным способом организации. Среди задач, которые естественным образом вписываются в этот вид архитектуры, находятся многие приложения искусственного интеллекта, в том числе экспертные системы. Основное различие между традиционными системами и системами, ориентированными на образцы, заключается в механизме запуска программных модулей. Традиционная архитектура предполагает, что модули системы обращаются друг к другу в соответствии с фиксированной, заранее заданной и явным образом сформулированной схемой. Каждый программный модуль сам принимает решение о том, какой из других модулей следует запустить в данный момент, причем в нем содержится явное обращение к этим модулям. Соответствующая временная структура передач управления от одних модулей к другим оказывается последовательной и детерминированной.
В противоположность этому организация, ориентированная на образцы, не предполагает прямого обращения из одних модулей к другим. Модули запускаются конфигурациями, возникающими в их "информационной среде". Такие программные модули называют модулями, управляемыми типовыми конфигурациями (или образцами). Программа, управляемая образцами, представляет из себя набор модулей. Каждый модуль определяется
(1) образцом, соответствующим предварительному условию запуска, и
(2) тем действием, которое следует выполнить, если информационная среда согласуется с заданным образцом.
Запуск модулей на выполнение происходит при появлении тех или иных конфигураций в информационной среде системы. Такую информационную среду обычно называют базой данных. Наглядное представление о системе рассматриваемого типа дает рис. 16.1.
Рис. 16.1. Система, управляемая типовыми конфигурациями (образцами)
Следует сделать несколько важных замечаний относительно рис. 16.1. Совокупность модулей не имеет иерархической структуры. Отсутствуют явные указания на то, какие модули могут обращаться к каким-либо другим модулям. Модули связаны скорее с базой данных, чем непосредственно друг с другом. В принципе такая структура допускает параллельное выполнение сразу нескольких модулей, поскольку текущее состояние базы данных может прийти в соответствие сразу с несколькими предварительными условиями, а следовательно, в принципе могут запуститься несколько модулей одновременно. В связи с этим, подобную организацию можно рассматривать как естественную модель параллельных вычислений, имея в виду, что каждый модуль физически реализован на отдельном процессоре.
