Почти полвека спустя после начала разработки шахматных программ интересно познакомиться с первыми шагами, сделанными на этом поприще. В числе тех, кто проявил интерес к этому направлению, были Г.М. Адельсон-Вельский, В.Л. Арлазаров, А.В. Усков (АВАУ) — сотрудники лаборатории, руководимой Александром Семеновичем Кронродом.

Как он вспоминает в книге «Беседы о программировании» (см. рецензию на с. 84), интерес к программированию шахматной игры у них возник после неудачи с программированием карточной игры в подкидного дурака. Шахматы были взяты в качестве объекта деятельности по соображениям научного характера, аналогично тому, как генетики выбрали муху дрозофилу.

Вот как, по словам Александра Семеновича, представлялась схема работы программы. «Каждый раз машина (программа) воспринимает позицию (шахматной игры) заданной непосредственно, не учитывая всего, что происходило перед тем, кроме, конечно, таких деталей, как возможность рокировки и взятие пешки на проходе, — это учитывается. В заданной позиции машина пробует сделать все принципиально возможные ходы (полуход машины). На каждый из них она пробует все разрешенные правилами ответные ходы противника (полуход человека)». Эта часть программы повторяется столько раз, сколько делается ходов, в ее основе лежит переборный механизм («абсолютный перебор», по А.С. Кронроду). Собственно, в шахматной партии производится перебор определенной глубины, которая характеризуется суммарным числом полуходов человека и машины, следующих друг за другом. Глубина перебора и определяет время рассмотрения позиции. Количественно, исходя из обычной практики человека, разумно она определяется часами, а ЭВМ М-20 позволяла рассматривать коллизии длиной не более пяти полуходов. Перебираемые позиции образуют граф последовательно связанных позиций, при этом конечную (но отнюдь не заключительную) позицию веточки перебора игроку необходимо оценить, чтобы решить, как действовать дальше. Но на самом деле это решение зависит от значения функции двух переменных — числа полуходов и величины оценки позиции, производимой с шахматной точки зрения. Например, сообразуясь с ценой фигур по Ласкеру, в оценку следует включать суммарное значение цен всех фигур в позиции. Критерий, предложенный АВАУ, носил название минимаксного (что является распространенным подходом при выборе оптимальной стратегии в играх), т.е. в алгоритме выбора оптимального хода из данной (начальной) позиции следовало выбирать такую цепочку ходов для попадания в конечную позицию ветви (среди всех возможных), для которой оценка принимала бы максимальное значение по цене и минимальное по количеству полуходов.

Теперь АВАУ предстояло уйти от использования в программе алгоритма прямого перебора позиций и приблизить их количественную оценку к представлениям об этом шахматистов. Появление форсированного варианта стало переходом от абсолютного перебора позиций только к тем, где рассматривались взятия фигур и ответные взятия. Это значительно увеличило глубину анализа и качество игры программы, но далеко не достаточно учитывало глубинные особенности шахмат, так называемые «тихие ходы». Но при этом улучшении программы возросло время анализа позиции, хотя сохранение качества игры было возможно за счет сокращения глубины анализа на полуход. Затраты машинного времени в этом случае превращались уже часов эдак в пять на ход.

В борьбе за ускорение работы, как пишет А.С. Кронрод, программу пришлось совершенствовать двумя путями: схемным и техническим. На первом улучшение было достигнуто благодаря предложенному А.Л. Брудно способу предварительной оценки, при котором ходы выбирали в порядке убывания их силы. Так появилась особая программа УХУДУ, упорядочения ходов, удовлетворяющих данному условию, за которой следовала Предварительная Оценка и специальная программа переупорядочения ходов ПУП. Это дало сокращение времени выбора хода.

На техническом пути улучшения достигали за счет более экономного использования памяти путем изменений в программах. Александр Семенович в своих «Беседах» приводит закон А.Л. Брудно (своеобразный предшественник ИТ-закона Мура): «При улучшении текста программы нормально экономится до 10% ячеек памяти».

После этого программа, по тестовой оценке гроссмейстеров Д.И. Бронштейна и М.Н. Таля, стала играть в силу 3-го разряда всесоюзной шахматной классификации и была в то время самой сильной в мире. Хотя эндшпиль партии программа проваливала и никак не переходила на уровень второразрядника, А.С. Кронрод назвал это Ватерлоо АВАУ. Усиление программы «любыми средствами» привело к введению понятий активного хода и отказа от полного перебора всех ходов, за исключением начальных (двух-трех полуходов). В качестве условий для УХУДУ задавались активность хода, максимальная цена позиции по экспресс-оценке пассивного хода и, конечно, действовала часть программы, названной Форсированный Вариант. Сокращение времени работы программы было значительным. Так, в шахматной программе, как отмечает А.С. Кронрод, родилась общая переборная схема в игре двух партнеров с минимаксным критерием выбора оптимальной стратегии выигрыша.

Полную версию статьи см. на «Мир ПК-диске».