К достижению цели
Шрифт:
Математики применяют тонкий метод, который позволяет сократить число ходов в дереве перебора, так называемый метод ветвей и границ. Суть дела в том, что далеко не все ходы в дереве необходимы для принятия решения (выбора хода). Этот метод ветвей и границ позволяет . освободиться от значительной части балласта (ненужных ходов). Дерево сокращается с 70 000 000 до нескольких десятков тысяч, то есть примерно в тысячу раз. Но если учесть, что у шахматного мастера варианты анализа содержат всего десятки ходов, то мусора в дереве перебора остается более чем достаточно. Если поделить 70 000 на 6 полуходов, то средняя ширина дерева превышает 10 000 позиций...
Разрастание
Человек решает задачи, подобные шахматам (а шахматы — типичная задача среди тех, которые непрерывно решают люди), формируя дерево перебора вариантов. Если вообще и можно решить задачу точно, то надо формировать полное дерево перебора всех вариантов. При этом оптимальный вариант определяется с помощью точной оценочной функции или, упрощенно говоря, точной цели игры. Но в подавляющем большинстве случаев формирование полного дерева — задача непосильная; приходится длину вариантов сокращать. А при усеченном дереве перебора точная цель игры, как правило, бесполезна, нужна уже другая, неточная цель. Да, сохранять в усеченном дереве перебора все варианты — и плохие, и хорошие — невыгодно, ибо приходится сильно ограничивать предельную длину вариантов. Вот если было бы возможным сделать так, что варианты обрывались логически, тогда вместо широкого и короткого дерева можно было бы сформировать узкое и длинное (да и при существенно меньшем количестве ходов, включенных в дерево перебора) — решение было бы более точным. В книжечке «О кибернетической цели игры», выпущенной в свет издательством «Советское радио» в 1975 году, объясняется, что успех определяется в первую очередь качеством избранной цели игры.
Если ЭВМ будет по этому алгоритму (и соответствующей ему программе) играть в силу гроссмейстера, то можно будет использованные здесь методы перенести в решение важных с практической точки зрения задач, и прежде всего в области экономики.
В декабре 1974 года приезжал в Москву английский мастер Ливи — он судил все шахматные соревнования среди машин, в том числе и первый чемпионат мира в Стокгольме 1974 года и второй, в Торонто 1977 года, пригласил он нас играть в следующем чемпионате мира. Мы согласились.
Появились еще два добровольца: Миша Цфасман и Саша Резницкий, первый — с мехмата МГУ, второй — с кафедры прикладной математики Нефтехимического института (там в ту пору работал профессор Криницкий). У Миши был первый разряд, Саша — действующий кандидат в мастера (шахматная команда ВНИИЭ усилилась!). Оба (как и Штильман, и Юдин) говорят по-английски; конечно, по сравнению с опытными моими программистами новобранцы казались птенцами, но быстро освоились.
Началась работа по составлению библиотеки позиций миттельшпиля. Под руководством А. Юдина студент А. Резницкий выполнил ее как дипломную работу. Здесь пришлось решить принципиально новую задачу: что заносить в память ЭВМ и (в соответствии с тем, как шахматный мастер использует свою библиотеку) как ЭВМ пользоваться этими данными?
По сути дела, когда мастер сталкивается с какой-то позицией (из партии или из перебора), и ему кажется, будто что-то похожее он ранее изучал, он действует по ассоциации с прежним опытом. Между прочим, когда работа уже заканчивалась, Саша Резницкий нашел, что об этом же писал еще Клод Шеннон в своей статье 1950 года...
Все просто, но как это формализовать, чтобы передать ЭВМ? Дело оказалось далеко не простым, но задача была формализована и решена.
11 этюдов были давно заготовлены для проверки программы — еще несколько лет назад я писал в предисловии к сборнику этюдов Г. Надареишвили, что именно с этюдов следует начинать эксперименты. Рассуждал я просто — в этюдах форсированная тактическая игра, позиционная оценка не нужна, а так как позиционное понимание будет введено в программу в последнюю очередь, то и надо начинать с этюдов...
Вот и начали со знаменитого этюда Р. Рети (Б. Kph8, п.сб; Ч. Кр аб, п.Ь5. Ничья); что может быть проще и в то же время остроумнее этого произведения?
Кстати, пришлось программу «крестить». В декабре 1976 года пришло из Канады приглашение принять участие во втором чемпионате мира шахматных программ для компьютеров. Требовалось заполнить анкету, где один из вопросов относился к названию программы. Я предложил «Человек», ибо программа играет по человеческому методу. Боря предложил «Пионер» (оказалось, что это было им давно подготовлено), так как программа прокладывает новые пути в области принятия решений. Обсудили и решили, что программе до человека еще далеко, а пионером она уже является!
Итак, в декабре 1976-го — январе 1977 года «Пионер» решил этюд Рети. Думали, что все будет просто — оказалось весьма сложно. Без позиционной оценки и без подключенной библиотеки эндшпиля дерево расползалось. ЭВМ была с небольшой производительностью, на решение уходили часы, а результата не было... Стало ясно, что надо помочь «Пионеру»!
Взяли правило квадрата и запрограммировали в трех модификациях; ввели в библиотеку, и «Пионер» в каждом узле дерева получал из библиотеки необходимую информацию. Эффект был поразительным: этюд был решен за 70 минут, в дереве перебора было всего 54 хода. Небольшое, человеческое дерево впервые получено было 28 января 1977 года — несомненно, знаменательное событие в кибернетике.
Важнейший результат эксперимента: 1) одна подпрограмма поиска хода в оригинальной позиции не может привести к небольшому дереву (нужны библиотеки, хранящие накопленные ранее знания) и 2) без позиционного понимания «Пионеру» приходится также нелегко. Но все же было решено испытать силы «Пионера» еще на одном этюде Ботвинника и Каминера, составленном двумя приятелями в юношеском возрасте (Б. Kpal, Фа2, Cd2, п.п. f3, g2; Ч. Kph5, Og7, Kd3, п.п. e5 и g6. Выигрыш).
С этим этюдом связана забавная ошибка. Когда в 1925 году мы с Сережей работали над этюдом, у нас возникли разногласия. Мой товарищ настаивал на том, чтобы на поле g6 стоял черный слон, а я — черная пешка. Дело в том, что комбинация, реализованная в этюде, была взята из легкой партии — там на поле g6 стояла пешка...
Наконец, Сережа меня убедил, и этюд был опубликован со слоном на g6. Когда же по памяти я восстанавливал этюд для «Пионера», то по ошибке поставил на g6 пешку!
И с этим этюдом бедняга «Пионер» мучился — не владел он позиционной оценкой. Пришлось ввести паллиативные правила (взамен этой оценки), и этюд был решен за 2 часа 43 минуты — в дереве было 143 хода. Произошло это 11 апреля 1977 года и так же, как и 28 января, на ГВЦ Госплана СССР (после улучшений в программе время сократилось до 45 минут).