В своей работе Шеннон рассматривает возможность ограничения количества вариантов, анализируемых на каждом из уровней дерева перебора. Например, на картинке ниже изображено дерево с ограничениями числа рассматриваемых вариантов в 3, 2, 2, 1, 1 для глубины соответственно в 1, 2, 3, 4 и 5 полуходов. Сплошными линиями показаны «разрешённые» к рассмотрению ходы, штриховыми — «запрещённые».
Рис. 65. Дерево перебора с ограничением числа рассматриваемых вариантов в каждом узле (программа типа B)
Количество рассматриваемых вариантов на этой схеме зависит только от глубины и не зависит от качества соответствующей позиции и самих ходов — это, конечно, серьёзное упрощение. В действительности Шеннон предлагал разработать некоторую функцию h(P, M), где P — позиция, а M — ход, для определения того, достоин ли ход рассмотрения в данной позиции. Шеннон даже выполнил некоторые наброски такой функции: предложил присваивать большие значения шахам, развивающим ходам, взятиям, атакам на фигуры, угрозам мата и так далее [657].
В статье Шеннона обнаружилось достаточно деталей для того, чтобы уже знакомый нам Матиас Файст создал на её основе «программу Шеннона». Инго Альтхофер из Йенского университета в 2012 г. организовал демонстрационный матч из десяти партий, в котором «программа Тьюринга» сразилась с «программой Шеннона». Итогом матча стала ничья — каждая из программ выиграла по одной партии, а остальные восемь завершились миром. До последней партии «Тьюринг» лидировал, но последнюю выиграл «Шеннон», сравняв счёт. Причиной поражения «Тьюринга» стал эффект горизонта. Также в ходе матча выяснилось, что ни одна из программ не способна поставить «голому» королю мат ни ладьёй, ни даже ферзём [658].
Сегодня исходные коды «воссозданных» программ Тьюринга и Шеннона, так же как и, например, исходные коды программы, основанной на отдельных идеях Конрада Цузе, размещены в открытом доступе. Однако важно понимать, что все они содержат некоторый произвол со стороны реконструкторов, ведь ни одна из этих программ не существовала в действительности, а дошедшие до нас документы допускают в ряде случаев весьма широкое пространство для трактовок и домыслов.
Интересно, что Turochamp не была единственной «бумажной машиной» того времени. В 1947–1948 гг. уже знакомый нам Дональд Мичи совместно с другим криптоаналитиком из Блетчли-парка Шоном Уайли создали программу, а точнее, алгоритм, получивший название «Макиавелли» (Machiavelli). Это имя он получил в честь знаменитого итальянского мыслителя, писателя и политического деятеля эпохи Возрождения Никколо Макиавелли. В начале 1950‑х гг. Тьюринг вёл работы по превращению Turochamp и Machiavelli в программы для манчестерских компьютеров, но эта работа так и осталась незавершённой. Исторические Machiavelli и Turochamp так и не сыграли ни одной партии, пока до них не добрались неутомимые реконструкторы.
В статье «Машины, которые играют в игры», увидевшей свет в 1961 г., Джон Мейнард Смит и Дональд Мичи описали оценочные функции своих алгоритмов — SOMA (Smith One-Move Analyzer, «Одноходовый анализатор Смита») и Machiavelli. Обе «бумажные машины» предполагали анализ вариантов всего на один полуход в глубину, поэтому вряд ли могли обыграть кого-то, кроме шахматных новичков. Функции оценки включали в себя подсчёт материала, контроль над центром доски и полями, соседствующими с королём, атаки на фигуры, оценки разменов и ряд других стратегических и тактических факторов. Позже Смит создал гибрид SOMA и Machiavelli, получивший название SOMAC. Этот алгоритм при переборе в глубину на два полухода обеспечивал уровень игры, соответствующий среднему шахматному игроку-любителю.
3.5.3 Алекс Бернстайн и первая полноценная шахматная программа
В 1951 г. ещё один коллега Тьюринга, Дитрих Принц, создал первую программу для Ferranti Mark I, способную решать задачки типа «мат в два хода». Было ясно, что созданию полноценной шахматной программы мешает недостаточный объём памяти машины.
Манчестерская команда не была единственной группой программистов, работавших над созданием шахматных программ в 1950-е. За океаном собственную разработку вели физики-атомщики из Лос-Аламоса под руководством самого фон Неймана.
Шахматная программа для компьютера MANIAC I (Mathematical Analyzer, Numerical Integrator, and Computer или Mathematical Analyzer, Numerator, Integrator, and Computer, «Математический анализатор, числовой интегратор и компьютер» или «Математический анализатор, счётчик, интегратор и компьютер»), спроектированного и построенного командой из Лос-Аламоса, была готова к 1956 г. и умела играть в так называемые антиклерикальные шахматы — вариант шахмат на доске 6 × 6 и без слонов (дело в том, что эта фигура в английском языке называется словом bishop — епископ). Также в антиклерикальных шахматах не было рокировки и ходов пешек через одно поле.
Позже эта программа получила название Los Alamos Chess.
Рис. 66. Учёные из Лос-Аламоса Пол Штейн (слева) и Ник Метрополис (справа)
играют в шахматы с MANIAC I (на заднем плане)
Интерес к шахматному программированию проявляли и исследователи социалистических стран. В 1953 г. в ГДР в журнале Funk und Ton (Радио и звук) была опубликована работа Гюнтера Шлибса с описанием алгоритма работы шахматной программы. Идеи Шлибса в целом повторяли идеи Шеннона и Тьюринга: он воспроизводит в своей работе оценочную функцию из статьи Шеннона, включающую оценку материала (девять единиц за ферзя, пять — за ладью, по три — за коня и слона), наличие отсталых, изолированных и сдвоенных (штраф по 0,5 балла) пешек, а также мобильности (по 0,1 балла за каждое поле). Перебор в программе Шлибса, как и в программе Шеннона, должен был осуществляться на фиксированное число полуходов в глубину, а оценка — производиться только в стабильных позициях. В общем, Шлибс почти полностью воспроизводит в своей работе статью Шеннона, внося ряд замечаний и уточнений [659].
Работа Шлибса не упоминается в современной западной литературе, но была хорошо известна советским исследователям. Краткий пересказ идей Шеннона и Шлибса мы впервые находим в книге «Электронные цифровые машины» Анатолия Ивановича Китова — руководителя головного вычислительного центра Министерства обороны СССР. Эта книга стала первой «открытой» книгой по вычислительной технике в Союзе, была позднее переведена на ряд иностранных языков и опубликована в Китае, Польше, Чехословакии. Пересказывая идеи Шлибса и Шеннона, Китов не удержался от того, чтобы скорректировать величину штрафа за изолированную и сдвоенную пешку: в его книге они составляют 0,4 и 0,3 балла соответственно (вместо 0,5 за оба дефекта у Шеннона и Шлибса) [660].
Два года спустя увидела свет новая книга Китова, написанная в соавторстве с Николаем Криницким, — «Электронные вычислительные машины» (в этой книге, вышедшей в «тёплые ламповые времена», слово «алгоритм» пока ещё пишется через Ф — «алгорифм»), в которой уже упоминаются первые проекты советских программистов. Например, созданная В. М. Курочкиным программа, способная решать шахматные задачи, а также созданная В. Д. Кукушкиным программа, способная ставить мат одинокому королю двумя разнопольными слонами [661], [662]. Откровенно говоря, первой моей мыслью, когда я увидел эти фамилии в книге Китова, было то, что за птичьими псевдонимами в данном случае скрывались засекреченные сотрудники ИТМиВТ, во главе которого стоял ещё один, уже известный нам исследователь с «крылатой» фамилией — Сергей Алексеевич Лебедев. В мемуарах его коллег упоминается программа для БЭСМ, которая решала двух- и трёхходовые задачи намного быстрее, чем лучшие шахматисты института [663]. Но красивая версия не выдержала проверки: по крайней мере Владимир Михайлович Курочкин — вполне реальный человек, известный российский учёный в области информатики, стоявший у истоков отечественного программирования. С 1950 по 1955 г. Курочкин работал под началом Лебедева в ИТМиВТ, а затем возглавил отдел систем математического обеспечения Вычислительного центра РАН.
