Прошло ровно 4 года с тех пор, как рукопись книги "Лингвистическая Геометрия: от Перебора к Построению" была сдана в печать. По случайному совпадению, ровно столько же времени прошло с тех пор, как была основана компания STILMAN Advanced Strategies (далее STILMAN). В книге я писал о возможном начале четвёртого этапа развития LG — и он действительно начался в 1999 году в связи с открытием этой компании. В сущности, STILMAN — это пока ещё небольшое, но весьма эффективное научно-производственное объединение ("НПО" в советской терминологии), которое лидирует в разработке теории и приложений LG на четвёртом этапе.

Четыре года назад я не мог и предположить, сколь могучей окажется роль LG в военном деле, сколь многообразными и революционными окажутся её применения. Ещё поразительнее то, что эта проблемная область оказалась настолько глубокой и насыщенной, что уже оказала и продолжает оказывать плодотворное влияние на развитие общей теории LG.

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

Борис Штильман Денвер, США октябрь, 2003

Эта книга не о лингвистике и не о геометрии. Она — о переборных задачах. Лингвистическая Геометрия (LG) — это подход к построению математических моделей для представления знаний и логического вывода в крупномасштабных многоагентных системах. Множество таких систем (формально определяемых здесь как Сложные Системы), включая воздушный бой, роботизированное производство, конверсию программного обеспечения, кибервойну в Интернете и т.д., образуют все те системы, которые могут быть смоделированы как абстрактные настольные игры (ABG). Сложные Системы — это игры многих игроков, ходы которых могут быть представлены передвижениями абстрактных фигур по полям абстрактной доски. Размерность (пространства) абстрактной доски (2D, nD и даже его нелинейность), его форма и размер, подвижность фигур, очерёдность ходов (включая одновременные ходы) — всё это может быть использовано для моделирования разнообразных многоагентных систем. Таким образом, абстрактные настольные игры понимаются здесь как класс Сложных Систем. Цель LG состоит в том, чтобы обеспечить участников игры стратегиями, необходимыми для достижения их целей. Традиционно, чтобы найти такие стратегии нужно перебрать все ветви в гигантском дереве игры (ДИ). Такой перебор часто превышает (по ресурсам времени и памяти) возможности современных и даже мыслимых компьютеров будущего.

LG позволяет значительно уменьшить объём перебора, делая переборные задачи решаемыми. LG обеспечивает формализацию и обобщение эвристик перебора, заимствованных у лучших экспертов. По существу, эти эвристики заменяют перебор построением стратегий. Формализованные экспертные стратегии вполне масштабируемы, т.е. они приводят к эффективным алгоритмам для приложений, размерности которых могут быть значительно больше тех, для которых эксперты разрабатывали свои стратегии. Кроме того, эти формальные стратегии позволили в различных областях решать новые задачи, с которыми эксперты ещё не сталкивались. Удивительно то, что для некоторых классов задач эти экспертные стратегии доказуемо приводят к оптимальным решениям. Чтобы формализовать эвристики, LG использует теорию формальных языков (т.е. формальную лингвистику), а также некоторые геометрические структуры на абстрактной доске. Поскольку обе дисциплины — лингвистика и геометрия — были использованы совместно, этот подход был назван Лингвистической Геометрией.

Это первая книга по предмету. Я не намеревался представить здесь полную теорию LG, поскольку она ещё не закончена. Однако, эта книга включает основы теории LG.

LG имеет длинную и поучительную историю. Шахматы — дрозофила искусственного интеллекта (ИИ) — наибольшим образом способствовали созданию LG. Они и теперь остаются постоянным источником идей и движущей силой, подталкивающей развитие LG. Начавшись с компьютерных экспериментов в 1972 году, продолженных уже с развитием теоретических идей в 80-х и формально определившаяся в 1991, LG развивалась по многим направлениям. Некоторые из них основаны на строгих теоретических построениях, другие — на сложных и утонченных экспериментах. Цель этой книги состоит в том, чтобы представить читателю разнообразие подходов, идей и экспериментов. Каждая глава написана как эссе на одну тему в LG, теоретическую или экспериментальную, хотя все главы связаны вместе и поддерживают друг друга.

Глава 1 включает введение в предмет и краткую историю исследований. Глава 2 включает основные определения и обзор формализмов LG, т.е. иерархию формальных языков. Главы 3-7 охватывают несколько экспериментов с инструментами LG. Они демонстрируют, как алгоритмы LG решают задачи постепенно возрастающей сложности. Помимо интересных фактических результатов, детальное описание экспериментов предназначено развить интуитивное понимание алгоритмов LG и их общей структуры. Вооруженный этой интуицией, читатель будет способен воспринять формальное описание инструментов LG, приведенное в главах 8-12. В главе 13 основы LG рассмотрены более глубоко. Пересматривая эксперименты из главы 3, мы вводим новое направление в LG: решение переборных задач путём построения стратегий (без какого-либо перебора на дереве). В главе 14 мы обсуждаем некоторые вопросы вычислительной сложности. В этой книге высказывается предположение, что инструменты LG позволяют выделить широкий подкласс легко решаемых задач (т.е. полиномиально сложных) среди тех, которые обычно считались трудноразрешимыми (т.е. экспоненциально сложными). Алгоритмы LG обеспечивают эффективное решение задач из этого подкласса.

Книга может использоваться как учебник для дипломированного специалиста или старшекурсника по курсу LG в течение одного-двух семестров или в качестве приложения к курсу по ИИ. Часть этого материала преподавалась в курсе Представление Знаний для Интеллектуальных Систем и в курсе Сложных Интеллектуальных Систем в Университете Колорадо в Денвере. Также, многие из тем, включенных в эту книгу, ранее преподавались в качестве отдельных лекций и кратких курсов по LG, проводимых по всему миру.

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