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