программа заработала на экспериментальной модели компьютера IBM 701. Кстати, эта первая программа была написана в машинных кодах (набор кодов операций конкретной вычислительной машины. — С. М.) — ещё до того, как у нас появился символьный ассемблер.

Я узнал о работе Стрейчи из статьи, которую он представил в Торонто в сентябре 1952 года. Поскольку его программа в то время уже была опубликована, я должен признать своё поражение. Только в 1954 году, с появлением IBM 704, моя программа смогла продемонстрировать интересную игру. Мой вклад заключался в добавлении «обучения» в программу, и я считаю, что могу претендовать на приоритет в этом вопросе[545].

Рис. 59. Портрет Кристофера Стрейчи, отпечатанный при помощи компьютера,

хранящийся в Бодлианской библиотеке Оксфордского университета

Первая версия программы Стрейчи для прототипа британского компьютера ACE (Automatic Computing Engine) была завершена в феврале 1951 г., однако объёма оперативной памяти машины оказалось недостаточно для полноценной работы программы.

Когда Стрейчи услышал о машине Manchester Mark 1, обладавшей значительно большим объёмом памяти, он попросил у бывшего сокурсника по Кингс-колледжу Кембриджа Алана Тьюринга руководство по программированию этой машины и к октябрю 1951 г. перевёл свою программу в машинный код для Manchester Mark 1 (коммерческая версия этой машины получила название Ferranti Mark 1) — иногда эту машину называют MADM (Manchester Automatic Digital Machine, Манчестерская автоматическая цифровая машина) или даже MADAM. Летом 1952 г. программа могла «сыграть полноценную партию в шашки на разумной скорости»[546].

Стрейчи был также одним из пионеров компьютерной музыки. В руководстве по программированию, полученному Стрейчи от Тьюринга, упоминается инструкция, позволяющая передавать импульсы на встроенный динамик компьютера. Тьюринг пишет, как, управляя паузами между импульсами, можно производить звуки разной высоты. Тьюринг рекомендует использовать эту инструкцию для оповещения оператора машины об определённых событиях[547]. Стрейчи сделал следующий шаг, научив машину исполнять несколько мелодий: британский гимн (God Save the King — дело было ещё при жизни Георга VI), Baa Baa Black Sheep и In the Mood. В 1951 г. мелодии были записаны вещательным подразделением Би-би-си. В 2016 г. исследователи из Университета Кентербери восстановили мастер-диск и загрузили записанные на него мелодии в облачный сервис Soundcloud[548], [549]. Таким образом, мелодии, созданные Стрейчи, стали первой дошедшей до нас компьютерной музыкой. Если бы Стрейчи чуть поторопился, то, возможно, его компьютерная музыка стала бы и первым в мире образцом компьютерной музыки, но его опередил Джеффри Хилл, научивший чуть раньше австралийский компьютер CSIR Mk1 воспроизводить «Марш полковника Боги» (Colonel Bogey March)[550].

Но, так или иначе, шашечная программа Стрейчи не просто научилась играть в шашки раньше программы Сэмюэла, но и исполняла в конце партии британский гимн[551].

В сентябре 1966 г. текст программы Стрейчи, переписанной на изобретённом им высокоуровневом языке программирования CPL, был опубликован в специальном выпуске журнала Scientific American, посвящённом информации. В 2011 г. Питер Норвиг реализовал простой транслятор с языка CPL на Python и, устранив несколько опечаток, смог вернуть программу Стрейчи «к жизни»[552].

Если взглянуть на начальную позицию в английских шашках, легко заметить, что белые могут начать партию одним из семи возможных полуходов (полуход, по-английски ply, возможно сокращение от reply — ответ, — перемещение шашки одного из цветов, ход — два последовательных полухода за белых и за чёрных), на каждый из которых чёрные могут также ответить семью возможными ответными полуходами. Таким образом, в результате первого полухода на доске может возникнуть семь позиций, в результате двух последовательных полуходов — 49 позиций. Далее число возможных полуходов меняется, и после трёх полуходов на доске может возникнуть 302 позиции, но некоторые из них будут повторяться, поскольку возникнут в результате перестановок ходов, и уникальных позиций будет всего 216. Современные шашечные программы умеют учитывать подобные повторения, запоминая часть проанализированных позиций в оперативной памяти[553], но в начале 1950-х оперативная память Ferranti Mark 1 позволяла хранить всего 512 чисел, по 20 бит каждое[554], поэтому о таких изысках, как таблица перестановок, не приходилось и мечтать. С увеличением количества полуходов число их возможных цепочек растёт очень быстро: 5 полуходов — 7361 вариант (уникальных позиций — 2733), 6 полуходов — 36 768 вариантов (уникальных позиций — 9105), 7 полуходов — 179 740 вариантов (уникальных позиций — 28 123) и так далее. При 28 полуходах мы получим астрономическое число 16 377 718 018 836 900 735 вариантов[555]. Современному компьютеру, способному просматривать 10 млн вариантов в секунду, потребовалось бы на их рассмотрение почти 52 000 лет, а ведь речь идёт лишь о партиях не длиннее 14 ходов. Совершенно очевидно, что перебор необходимо каким-то образом ограничить. Программа Стрейчи способна просматривать дерево вариантов игры на фиксированное число полуходов. При этом, поскольку позиции в терминальных узлах дерева в ряде случаев ещё далеки от завершения игры, Стрейчи использовал вместо неизвестной точной оценки позиции приближённую, выбрав в качестве приближения разницу в числе своих шашек и шашек противника (дамка оценивалась в четыре шашки). Функцию, выполняющую такую приближённую оценку позиции, сегодня принято называть оценочной функцией [evaluation function]. Подчёркивая неточный, основанный на предположениях и догадках характер заложенного в них знания, подобные функции называют эвристическими (от др.-греч. εὑρίσκω — отыскиваю, открываю). Действительно, хотя позиции, в которых у одной из сторон есть преимущество в числе шашек, часто являются выигрышными для этой стороны, но из такого правила несложно найти множество исключений.

Примечательно, что с математической точки зрения оценочная функция, выбранная Стрейчи, является полиномом: f = Mc – Mp + 4Kc – 4Kp, где Mc — число шашек машины, Mp — число шашек противника, Kc — число дамок машины, Kp — число дамок противника. Все позиции в шашках, согласно теореме Цермело, должны быть либо выигрышными, либо проигранными, либо ничейными при идеальной игре обеих сторон. В примере с крестиками-ноликами мы использовали для выигрышной позиции оценку «1», для ничейной — «0» и для проигрышной — «–1». Такая оценка очевидным образом связана с числом очков, которое игрок получит при соответствующем результате, s = (v + 1) / 2, где s — число очков, а v ∈ {−1, 0, 1} — оценка, которую мы использовали в крестиках-ноликах. Оценка со знаком позволяла нам легко получить значение оценки для противника, достаточно было просто поменять у оценки знак: vc = –vp, вместо того чтобы выполнять менее наглядную операцию вычитания оценки из единицы: sc = 1 – sp, но это в