Валерий Шилов - Удивительная история информатики и автоматики

Уже первый автомат, построенный им в 1911 году и показанный в Париже спустя три года, вызвал небывалый ажиотаж у публики. Автомат был предназначен для разыгрывания эндшпилей шахматных партий. Он матовал черного короля белыми фигурами — королем и ладьей. Известно, что результат игры (победа белых) в таком окончании при правильной игре предопределен алгоритмически, — отметим, правда, что для упрощения устройства мат ставился не самым коротким путем. Автомат самостоятельно с помощью механического манипулятора расставлял фигуры на доске (в зависимости от исходного состояния электрических датчиков) и передвигал их во время партии. Ходы черными фигурами делал игравший против автомата человек. Фактически автомат Торреса оказался первым в мире автоматическим устройством, способным собирать информацию, обрабатывать ее и действовать в соответствии с результатами анализа.

Второй автомат был построен изобретателем в сотрудничестве с сыном Гонзало в 1920 году, и в нем фигуры передвигались посредством магнитов, размещенных под доской. Автомат был снабжен механизмом контроля правильности ходов — при неправильном ходе черных загоралась лампочка. После трех неправильных ходов автомат прекращал партию. При атаке черного короля звучали слова шах или мат.

Шахматные автоматы стали, вероятно, самым знаменитым из изобретений Торреса в области автоматики. Даже спустя двадцать лет после первой демонстрации, в 1930 году, один из французских журналов писал о них с тем же восхищением. Почти сорок лет они оставались непревзойденным примером выполнения машиной интеллектуальных действий. Вершиной же признания стал показ шахматного автомата Торреса-и-Кеведо на конгрессе по кибернетике в Париже в январе 1951 года, — т. е. уже после начала компьютерной эпохи.

С началом компьютерной эры создание специализированных шахматных автоматов потеряло смысл — теперь в шахматы стали играть программы.

Напомним, что нимом называется игра, суть которой заключается в следующем. Пусть имеется определенное количество фишек (монет, камешков и т. д.), разложенных в несколько рядов (или кучек), и два игрока по очереди забирают по одной или нескольку фишек из любого ряда. Выигрывает (или, наоборот, проигрывает) тот, кто взял последнюю фишку.

В литературе нередко пишут о выигрышной стратегии и о программировании соответствующих алгоритмов. Однако с игрой «ним» связаны и другие интересные сюжеты. Так, до сих пор нет полной ясности ни с корнями игры, ни даже с происхождением ее названия. Сегодня, в эпоху повального увлечения компьютерными играми, небезынтересно узнать, что «ним» был первой игрой, в которую человек сыграл против машины.

В 1902 году американский математик, профессор Гарвардского университета Чарльз Бутон, опубликовал описание правил игры, которую назвал «ним». По его словам, поначалу эта игра заинтересовала его своей кажущейся сложностью, которая обернулась затем в высшей степени простым и полным математическим описанием. Для варианта игры, в котором произвольное количество фишек раскладывалось в три ряда, Бутон предложил беспроигрышную стратегию, основанную на анализе двоичных представлений числа фишек в рядах. Кроме того, он обобщил решение для случая произвольного количества рядов.

Чарльз Леонард Бутон родился 25 апреля 1869 года в Сент-Луисе (штат Миссури) в семье инженера. Инженером был и его дед, инженерами стали трое братьев — однако Чарльз посвятил себя чистой науке. Степень бакалавра он получил в Вашингтонском университете, затем продолжил учебу в Гарварде. Здесь, как лучший студент, Бутон был удостоен стипендии для обучения за границей, и два года провел в Лейпциге у выдающегося норвежского математика, автора работ по дифференциальной геометрии Софуса Ли. Бутон стал одним из последних его учеников, а общение с Ли определило его научные интересы. Вплоть до своей кончины 20 февраля 1920 года Бутон оставался одним из ведущих профессоров Гарвардского университета и активным членом математического сообщества. Так, в течение многих лет он являлся редактором Бюллетеня и Трудов Американского Математического общества.

Относительно происхождения и истории игры Бутон в своей статье дал только самую скудную информацию. По его словам, похожая игра в свое время пользовалась популярностью у учащихся некоторых американских колледжей, и в нее также охотно играли участники ярмарок в провинциальных американских городках. Бутон говорит, что ее называли «фан-тан» (Fan-Tan). Это название наводит на мысль о Китае, но Бутон справедливо пишет, что хотя в Китае действительно имеется игра с таким названием, с «нимом» она не имеет ничего общего. Эта игра заключается в следующем — крупье предлагает делать ставки на то, каким будет остаток от деления на 4 количества жетонов, которое он возьмет двумя горстями из большой кучи жетонов. «Фантан» пользуется дурной репутацией, поскольку опытный крупье, оценив соотношение сделанных ставок, может вынуть из кучи именно столько жетонов, сколько необходимо для того, чтобы остаться в выигрыше.

На работу Бутона сразу же обратили внимание.

Так, много писал о ней известный немецкий математик и автор нескольких книг по занимательной математике Вильгельм Аренс, который, между прочим, как и Бутон, учился в Лейпциге у Софуса Ли.

Сегодня известно, что похожие (хотя и не в точности такие же) игры были знакомы многим народам Азии и Африки. Однако и через сто лет после статьи Бутона происхождение игры «ним» не стало более ясным. Встречающиеся в литературе ссылки на ее китайские корни (например, в первых изданиях классической книги Г. Харди и Э. Райта по теории чисел авторы прямо называли ее «китайской игрой «ним»») ничем не подкреплены и кажутся просто отзвуком приведенных нами выше, но плохо понятых слов Бутона. Кстати, не обнаружилось и никаких свидетельств того, что такая игра когда-либо действительно была распространена в Америке. Так что не исключено, что правила игры Чарльз Бутон определил сам, — хотя, быть может, и опирался при этом на какой-то образец.

Итак, название «ним» игре дал сам Бутон, однако никак его не объяснил. За прошедшие сто лет появилось немало версий его происхождения, в той или иной степени убедительных. Самая остроумная из них утверждает, что nim — это перевернутое слово win (победа). Конечно, такое объяснение представляется явной натяжкой. Несомненно ошибочным является утверждение, будто ним — это китайское название игры (в действительности, в основных диалектах китайского языка слова вообще не могут заканчиваться на — м ).