Первые десять лет исследований, начиная с 1958 года, закончились публикацией книги "Алгоритм игры в Шахматы" (Ботвинник, 1968, 1970). В то время как математическое описание алгоритма было ещё недостаточным для программирования (и, возможно, несколько сомнительным), основные принципы сокращения перебора заложили прочный фундамент для дальнейшего развития. Другая публикация "Блок-схема Алгоритма игры в Шахматы" (Ботвинник, 1972) уже может рассматриваться как официальное начало проекта ПИОНЕР. К сожалению, обе вышеупомянутые публикации не включали ничего кроме идей и набора блок-схем для низкоуровневых процедур алгоритма. Собственно алгоритм и программу шахматный игры ещё только предстояло разработать.

Группа исследователей, занятых в этом проекте, имела два предмета научных исследований: выдающихся экспертов (подобно самому Ботвиннику) и компьютерные программы (после того как они были разработаны). Эти программы включали шахматную программу ПИОНЕР 1.x и множество программ ПИОНЕР 2.x — 4.x для планирования народного хозяйства СССР и составления графика ремонтов. Взаимосвязи между этими предметами исследований приводили к постоянному пересмотру наших взглядов и к многократной перестройке алгоритмов и программ. Много старых и новых идей были проверены в ходе проекта ПИОНЕР. Например, идея Траекторий, ограниченных горизонтом, и идея о декомпозиции Сложной Системы в динамическую иерархию подсистем доказали свою важность с самого начала. Этого не произошло с подсистемой второго уровня — Сетью Траекторий. Определенная первоначально, как ключевая область боя, а позже как Зона (в многочисленных версиях) и как Цепочка фигур, эта подсистема прошла множество существенных и менее значительных изменений. Эвристические алгоритмы для генерации подсистем первого и второго уровня — Траекторий и Зон — были представлены в (Штильман, 1975, 1977, 1979, 1984a). Подобные проблемы возникали и с подсистемами высокого уровня, и с алгоритмом глобального управления, позже формализованным как Грамматика Переводов.

К концу 1976 года первая версия шахматной программы ПИОНЕР был закончена. Она была проверена на решении шахматных этюдов. Конечно, цель состояла не только в том, чтобы решить эти этюды. При решении нужно было получить дерево перебора, близкое к тому, которое строит шахматный мастер. Что касается точности, то получаемые решения никогда не рассматривались как оптимальные. Кроме того, для огромного большинства этюдов оптимальные решения до сих пор неизвестны. Доказательство оптимальности при использовании традиционных алгоритмов типа «брут форс» требует огромного перебора, который часто превышает возможности любых компьютеров (разд.1.2). То, что обычно называют решением — это вариант (или несколько вариантов), которые признаны экспертами. Более глубокое понимание оптимальности и его роли в LG пришло намного позже на 3-м этапе развития LG (разд.1.9 и глава 13).

Первые два этюда, отобранные для тестирования программы ПИОНЕР — этюд Рети и этюд М.Ботвинника-С.Каминера, считаются простыми для шахматиста. Однако эта простота скрыта за миллионами ходов в дереве перебора, которые должны быть проанализированы при поиске решения по методу «брут форс». Конечно, шахматный эксперт способен избежать этого множества вычислений. Во время экспериментов с ПИОНЕРом оценивалось множество параметров, включая коэффициент ветвления (разд.1.2), а также некоторые другие параметры перебора (Ботвинник, 1979, 1984). Дерево перебора, построенное ПИОНЕРом в январе 1977 года при решении этюда Рети, содержало 54 хода (T=54). Следовательно, принимая во внимание, что глубина перебора, необходимого для решения этой задачи должна быть не меньше L=6, мы получили коэффициент ветвления B≈1,68 (1.2.2). Деревья перебора, построенные традиционными шахматными программами для этого этюда, включают приблизительно 106 ходов. В этюде Ботвинника и Каминера (Ботвинник, 1979, 1984), общее количество ходов, включённых в перебор, было равно 145, максимальная глубина L=12 и B≈1,35. Хотя оба этюда могут быть решены традиционными шахматными программами, эти результаты были очень интересны из-за существенного уменьшения коэффициента ветвления. Одна из этих задач, этюд Рети, продолжает служить моделью для далеко идущих обобщений в LG (главы 3, 4, 6, 13 и 14).

Среди разнообразных сложных задач, решённых ПИОНЕРом, мы обсудим ещё две. Обе задачи до сих пор не могут быть решены традиционными шахматными программами. Алгоритмы перебора с альфа-бета отсечением (разд.1.2) не в состоянии обеспечить существенное уменьшение коэффициента ветвления. Поэтому время, требуемое для расчёта, оказывается немыслимым.

Первая задача — этюд Г.Надареишвили (Надареишвили, 1976; Ботвинник, 1979, 1984). Он был решён ПИОНЕРом в августе 1977 года. Общее количество построенных узлов было T=200, в то время как глубина перебора, требуемого для нахождения решения L=25. Следовательно, B≈1,14. Неуменьшенный коэффициент ветвления для алгоритмов типа «брут форс» здесь можно оценить как B≈15. Решение этого этюда продемонстрировало мощь эвристической модели, на которой основан ПИОНЕР. Динамическая иерархия подсистем, Траекторий и Сетей, позволила нам найти очень глубокое решение почти без ветвления. Конечно, это было всего лишь решение, одобренное экспертами. Тогда никто не поднимал вопроса об оптимальности или хотя бы о точности этого решения. Теперь, 20 лет спустя, мы можем предположить, что это — математический оптимум. Разумно ожидать, что это будет доказано при использовании идей беспереборного подхода в LG (глава 13) в ближайшем будущем. Этюд Надареишвили также послужил образцом для множества обобщений, включенных в эту книгу (глава 5).

Вторая сложная задача — это позиция в середине игры из легендарной партии М.Ботвинник и Х.Р.Капабланка, сыгранной в 1938 году на АВРО-турнире (Голландия)(Ботвинник, 1984a). Эту шахматную комбинацию обычно рассматривают как бессмертный пример выдающегося шахматного мастерства. Начальная позиция содержит 19 фигур, а неуменьшенный коэффициент ветвления можно оценить как B≈20. Глубина перебора для этой задачи не должна быть меньше, чем 23. В апреле 1980 года программа ПИОНЕР построила дерево перебора из 40 узлов с коэффициентом ветвления B≈1,05 (Ботвинник, 1980a, 1980b, 1982, 1987). Решение, найденное ПИОНЕРом, было точно таким же, как и вариант в той партии 1938 года. Вероятно, это решение является доказуемо оптимальным.

В 1981-1988 годах, все исследования и программные разработки по проекту ПИОНЕР проводились при помощи системы поддержки разработки программ, называвшейся РАБОЧИМ МЕСТОМ ПРОГРАММИСТА (PROGRAMMER'S WORKBENCH — PW), (Штильман, 1994f). Система PW была разработана Мирным, Ройзнером, Чудаковым и Штильманом (1986), и позже переработана и расширена Мирным, Чудаковым и Штильманом (1988). PW была предназначена для того, чтобы поддержать параллельную разработку и конфигурацию программного обеспечения (ПО) для крупномасштабных научно-исследовательских работ. ПИОНЕР и другие сложные проекты включали расширенный период опытной эксплуатации образцов (прототипов) ПО. В основном, компьютерные программы использовались как инструменты для научных исследований и перестройки сложных алгоритмов. Полный цикл жизни компьютерных программ рассматривался как последовательность прототипов. Каждый прототип должен был быть чрезвычайно гибким, чтобы обеспечить многократное перепроектирование. PW поддерживала многократные итерации при перестройке изменяющихся прототипов благодаря жесткому универсальному каркасу версий ПО. Дополнительно, PW эффективно автоматически поддерживала взаимодействие разработчиков в проекте ПИОНЕР, обеспечивая независимость проектировщиков PW от остальных сотрудников (пользователей PW) и одновременно поддерживая строгую дисциплину коллективных разработок. Хотя язык Dijkstra (Дейкстра, 1976; Грис, 1983; Штильман, 1994f) был входным языком (транслятора), полностью реализованным в PW, фактическая разработка (включая отладку) проводилась с использованием проблемно-ориентированного языка очень высокого уровня. PW позволила нам создавать, расширять и поддерживать различные версии этого языка и для других проблемных областей. PW была реализована на IBM 370/144 — оригинальном американском компьютере, на котором в эти годы и велась разработка ПИОНЕРа. Позже, PW инструменты использовались в нескольких НИИ на советских ЭВМ для разработки и поддержки крупномасштабных проектов в области Искусственного Интеллекта. Инструменты PW были подготовлены к модернизации для поддержки объектно-ориентированного программирования.

Проект ПИОНЕР закончился разработкой одной из самых интересных и мощных эвристических моделей, основанной на эвристических сетях. Применение разработанной модели к шахматной игре было полностью реализовано в виде программы ПИОНЕР 1.x (Ботвинник, 1979, 1982, 1984, 1987, 1989). Аналогичная эвристическая модель была также реализована для долгосрочного календарного планирования в виде набора программ ПИОНЕР 2.x, 3.x, 4.x. Они использовались для составления графика ремонтов электроагрегатов, для сглаживания графика потребления мощности и для планирования народного хозяйства в прежнем СССР (Штильман, 1985a, 1993a). Эти модели (Штильман, 1976c, 1977, 1979, 1994a; Ботвинник, 1968, 1972, 1975, 1979, 1989), (Резницкий и Штильман, 1983; Резницкий, Бордюгов и Штильман, 1983), (Ботвинник и др., 1983; Ботвинник, 1989), (Штильман, 1978, 1985b, 1985c, 1993d) были представлены в форме идей, правдоподобных рассуждений и работающих программ.

Эксперименты с программами составления графика ремонтов ПИОНЕР 2.x продемонстрировали преимущества нового подхода. Программа ПИОНЕР 2.1 для составления месячного графика ремонтов электроагрегатов генерировала различные графики с коэффициентом ветвления, не превышающим 1,06, что составляло 50..100-кратное уменьшение этого коэффициента по сравнению с методом «брут форс» (Резницкий и Штильман, 1983; Штильман, 1985a). Эксперименты с программой ПИОНЕР 2.2 по составлению годового (на период в 365 дней) графика ремонтов электроагрегатов также продемонстрировали уменьшение коэффициента ветвления до величины близкой к 1. В отличие от ПИОНЕРа 2.1, эта программа была способна максимизировать число электроагрегатов, включённых в график ремонтов, регулируя продолжительность ремонта этих агрегатов. Особые качества были продемонстрированы программой ПИОНЕР 2.3, которая генерировала годовые графики ремонта агрегатов, регулируя значения резерва мощности. Небольшие вариации резерва мощности (в пределах диапазона 6%) позволяли этой программе включать в план ремонта все электростанции, которые подали заявки. Самые интересные результаты в составлении графика ремонтов были получены программой ПИОНЕР 2.4 для составления годового графика с распределением многочисленных ресурсов, включая различные типы ремонтного персонала. Такая постановка задачи приводила к существенному росту коэффициента ветвления; программа сумела уменьшить этот коэффициент до 1,005. Это позволило генерировать высококачественные годовые графики ремонтов для Единой Энергосистемы бывшего СССР. Применение LG к календарному планированию и дополнительная информация о программах составления графиков ремонта представлены в главе 7.

Программы ПИОНЕР 3.1 и 3.2 позволяли сглаживать еженедельные графики потребления мощности, сдвигая выходные дни для различных потребителей. Они уменьшили максимумы потребления мощности на 3,5% при уменьшении числа потребителей со сдвинутыми выходными (Ботвинник и Мирный, 1983).

Главным достижением модели ПИОНЕР в применении к не шахматным областям была разработка программ ПИОНЕР 4.1 и 4.2 для планирования народного хозяйства СССР на периоды в 15 и 25 лет соответственно. Эти программы балансировали продукцию государственной промышленности и бюджет, основываясь на агрегированной модели, включавшей 18 отраслей народного хозяйства (Резницкий, 1987; Ботвинник, 1989).

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

Что было общего в этих иерархиях? Какие формальные средства могли бы быть использованы, чтобы отразить эту общность и применить её в других проблемных областях?