Читаем без скачивания К достижению цели - Михаил Моисеевич Ботвинник
Шрифт:
Интервал:
Закладка:
24 июня была достигнута договоренность с руководством института, что с сего числа я занимаюсь только программой для ЭВМ. Нелегким было это решение: 19 лет посвятил я проблеме управляемой машины, да и научные исследования не удалось завершить полностью — работа машины в динамическом режиме продолжала оставаться неисследованной. И хотя здесь не только идеи, но и план работы был ясен, и в успехе поиска не было сомнений — динамическая устойчивость машины может быть обеспечена так же, как и статическая, — решил я распроститься с электротехникой...
К осени 1974 года алгоритм был приведен в порядок, Штильман заработал с полной нагрузкой. В чем же вкратце суть работы, почему она столь важна?
Когда я впервые прочел работы Клода Шеннона, то не оценил их в полной мере. Меня тогда интересовало лишь то, что Шеннон предлагал по формализации игры: 1) полный перебор всех ходов в пределах усеченного дерева и 2) выборочный перебор по аналогии с игрой шахматного мастера.
Первый метод — американские математики образно назвали его «брут форс» («грубая сила», грубая в том смысле, что грубая сила животного противопоставляется изощренным человеческим приемам) — меня, конечно, устроить не мог (правда, тогда еще не был известен метод ветвей и границ, метод, который позволяет сократить объем дерева перебора, но и это не может спасти метод полного перебора от критики). Второй метод, разумеется, вполне подходил в принципе, но никаких ясных рекомендаций по применению этого метода дано не было. Да это и понятно — Шеннон познакомился с шахматами слишком поздно, шахматным специалистом он не был. И все же в статье содержится ясное указание на то, как мастер использует свою библиотеку позиций, использует опыт прошлого, партии, сыгранные ранее. Тогда на это указание я не обратил внимания, я продолжал работать лишь над поиском хода в оригинальной позиции, когда опыт прошлого не помогает...
Впоследствии я понял значение этой работы Клода Шеннона. Он поставил весьма важную проблему в кибернетике — как улучшить управление, как усовершенствовать принятие решений. Шеннон предложил формализовать и программировать шахматы для того, чтобы использовать шахматный компьютер как модель, для решения аналогичных задач управления. Авторитет Шеннона (автора теории информации) столь велик, что его статья незамедлительно положила начало новому научному направлению.
Математики считают, что полное дерево перебора в шахматах, хотя и является конечным, содержит примерно 1О120 позиций! И если партия продолжается 100 ходов, то среднюю ширину дерева составляют Ю118 позиций. Получается, что это дерево — тончайший блин...
Не только изучить, но и сформировать такое сверхгигантское дерево перебора нет возможности. Как же быть? Нет никакого другого выхода, как срезать верхушку, то есть формировать и анализировать усеченное дерево перебора, где длина вариантов сравнительно невелика.
Мастер считает варианты на 5—6 ходов. Если измерять эти варианты в единицах шахматного времени (математики это время измеряют в полуходах), то длина вариантов равняется 10—12 полуходам. Примем, что варианты ограничены 6 полуходами, то есть в два раза короче. Примем также, что мы анализируем позицию, где в среднем в каждом узле (позиции) дерева возможно 20 различных ходов. Нетрудно подсчитать, что такое усеченное дерево содержит около 70 000 000 позиций...
Математики применяют тонкий метод, который позволяет сократить число ходов в дереве перебора, так называемый метод ветвей и границ. Суть дела в том, что далеко не все ходы в дереве необходимы для принятия решения (выбора хода). Этот метод ветвей и границ позволяет . освободиться от значительной части балласта (ненужных ходов). Дерево сокращается с 70 000 000 до нескольких десятков тысяч, то есть примерно в тысячу раз. Но если учесть, что у шахматного мастера варианты анализа содержат всего десятки ходов, то мусора в дереве перебора остается более чем достаточно. Если поделить 70 000 на 6 полуходов, то средняя ширина дерева превышает 10 000 позиций...
Разрастание дерева вширь с увеличением глубины расчета происходит катастрофически.
Человек решает задачи, подобные шахматам (а шахматы — типичная задача среди тех, которые непрерывно решают люди), формируя дерево перебора вариантов. Если вообще и можно решить задачу точно, то надо формировать полное дерево перебора всех вариантов. При этом оптимальный вариант определяется с помощью точной оценочной функции или, упрощенно говоря, точной цели игры. Но в подавляющем большинстве случаев формирование полного дерева — задача непосильная; приходится длину вариантов сокращать. А при усеченном дереве перебора точная цель игры, как правило, бесполезна, нужна уже другая, неточная цель. Да, сохранять в усеченном дереве перебора все варианты — и плохие, и хорошие — невыгодно, ибо приходится сильно ограничивать предельную длину вариантов. Вот если было бы возможным сделать так, что варианты обрывались логически, тогда вместо широкого и короткого дерева можно было бы сформировать узкое и длинное (да и при существенно меньшем количестве ходов, включенных в дерево перебора) — решение было бы более точным. В книжечке «О кибернетической цели игры», выпущенной в свет издательством «Советское радио» в 1975 году, объясняется, что успех определяется в первую очередь качеством избранной цели игры.
Если ЭВМ будет по этому алгоритму (и соответствующей ему программе) играть в силу гроссмейстера, то можно будет использованные здесь методы перенести в решение важных с практической точки зрения задач, и прежде всего в области экономики.
В декабре 1974 года приезжал в Москву английский мастер Ливи — он судил все шахматные соревнования среди машин, в том числе и первый чемпионат мира в Стокгольме 1974 года и второй, в Торонто 1977 года, пригласил он нас играть в следующем чемпионате мира. Мы согласились.
Появились еще два добровольца: Миша Цфасман и Саша Резницкий, первый — с мехмата МГУ, второй — с кафедры прикладной математики Нефтехимического института (там в ту пору работал профессор Криницкий). У Миши был первый разряд, Саша — действующий кандидат в мастера (шахматная команда ВНИИЭ усилилась!). Оба (как и Штильман, и Юдин) говорят по-английски; конечно, по сравнению с опытными моими программистами новобранцы казались птенцами, но быстро освоились.
Началась работа по составлению библиотеки позиций миттельшпиля. Под руководством А. Юдина студент А. Резницкий выполнил ее как дипломную работу. Здесь пришлось решить принципиально новую задачу: что заносить в память ЭВМ и (в соответствии с тем, как шахматный мастер использует свою библиотеку) как ЭВМ пользоваться этими данными?
По сути дела, когда
