Игровые задачи

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

По первому пути (названному "брут форс" - грубая сила) играют современные шахматные программы и в каком-то смысле ему же следуют очень слабые шахматисты, по второму - мастера. Цель программирования игры в шахматы на ЭВМ - "научить" машину второму "стилю" игры, что, как считают, откроет путь решению ряда практических проблем "искусственного интеллекта", среди которых особое место занимает разработка методов решения задач перспективного планирования.

Интересно хотя бы совсем кратко рассмотреть прогресс в развитии машинного программирования игры в шахматы. В 1964 г. Г. М. Адельсоном-Вельским, В. Л. Арлазаровым и А. В. Усковым была разработана программа, которая позволяла машине играть в силу четвертого разряда. Программа предусматривала варьирование "стиля" игры машины, в частности, за счет разной глубины просмотра позиции; в случае варианта программы с просмотром позиции на глубину 5 полуходов (ходов одного из партнеров) машина "думала" над ходами по 10-20 м. и более. В экспериментах разыгрывались партии между машиной и человеком и между машиной и машиной.

Начиная с 1974 г. между шахматными программами производятся международные чемпионаты. Они приурочиваются к конгрессам Международной Федерации по обработке информации (ИФИП). Сильнейшими из программ оказались советская "Каисса' (авторы Г. М. Адельсон-Вельский, В. Л. Арлазаров и М. В. Донской) и американская "Чесс 4.6" (авторы Д. Слейт и Л. Аткин).

В 1974 г. в Стокгольме победу одержала "Каисса". В 1977 г. в Торонто победила "Чесс 4.6", ибо быстродействие, с каким она работает (12 млн. операций/с) позволило ей вести расчет вариантов до двенадцати полуходов. Быстродействие же "Каиссы" (3 млн операций/с) - до девяти полуходов. А поскольку обе программы работали по принципу "брут форс", это обстоятельство и предопределило поражение "Каиссы". Однако уже здесь, по мнению М. М. Ботвинника, сила игры этих программ была на уровне второго разряда [82].

В течение многих лет группа ученых ВНИИ электроэнергетики во главе с М. М. Ботвинником разрабатывает шахматную программу "Пионер", которая, по-видимому, будет единственной, использующей методы, аналогичные тем, которыми пользуется шахматный мастер. Ибо, как и он, "Пионер" не рассматривает заведомо лишенные смысла ходы. При решении сложного этюда грузинского шахматного композитора Г. Надареишвили "Пионер" рассчитывал варианты до 25 полуходов. М. М. Ботвинник полагает, что решение данного этюда на ЭВМ с быстродействием в 10 млн. операций/с потребовало бы приблизительно 10 м машинного времени; вместе с тем не каждый шахматист высокой квалификации уложился бы в это время. Американская машина "Сайбр-176" после миллиона ходов по программе "Чесе 4.6" этюд не решила.

Третий чемпионат среди семнадцати машинных программ проводился с 25 по 30 сентября 1980 г. в г. Линце (Австрия). По мнению участника этого чемпионата (и одного из авторов программы "Каисса") М. В. Донского, на этом турнире программ наиболее ярко выразилась специфика такого рода соревнований: органическое сочетание спортивного начала с чисто научными, далеко идущими исследовательскими интересами. Турнир отличался обилием ничьих. Программа-победительница (США) играла на уровне мастера, но, по мнению Донского, если бы удалось сосредоточить в одной из программ достоинства всех ее конкурентов, участвовавших в турнире, то не исключено, что она уже теперь играла бы на уровне гроссмейстера. Разумеется, это вовсе не является для программистов самоцелью: например, уже сейчас принципы программирования игры в шахматы группой под руководством М. Ботвинника используются для решения задач, связанных с планированием ремонта оборудования электростанций.

Пока что Международная федерация по шахматам (ФИДЕ) допустила ко всякого рода чемпионатам наряду с шахматистами и шахматные программы, оговорив, однако, условие, согласно которому денежное вознаграждение за призовое место программе не выплачивается...

Значительная часть рассмотренных нами примеров моделирования элементов творчества (программы ЛТ, "Пионер" и некоторые другие) носит так называемый эвристический характер. Слово "эвристика" означает, с одной стороны, общую теорию творчества [93], а с другой - приемы решения задач, не связанные с жесткими правилами, приемы, резко сокращающие перебор вариантов и потому допускающие риск ошибок, неточных решений. Очень часто под эвристическими методами понимают совокупность эмпирических алгоритмов, которые примерно дают те же результаты, что и эвристическая деятельность человеческого мозга. Эти алгоритмы могут не отражать содержательную сторону процесса, но то, что они выдают, близко к тому, что получил бы человек, если бы он решал ту же задачу.