Удивительная история информатики и автоматики
Шрифт:
Шахматные автоматы стали, вероятно, самым знаменитым из изобретений Торреса в области автоматики. Даже спустя двадцать лет после первой демонстрации, в 1930 году, один из французских журналов писал о них с тем же восхищением. Почти сорок лет они оставались непревзойденным примером выполнения машиной интеллектуальных действий. Вершиной же признания стал показ шахматного автомата Торреса-и-Кеведо на конгрессе по кибернетике в Париже в январе 1951 года, — т. е. уже после начала компьютерной эпохи.
С началом компьютерной эры создание специализированных шахматных автоматов потеряло смысл — теперь в шахматы стали играть программы.
Еще раз об игре
Напомним, что нимом называется игра, суть которой заключается в следующем. Пусть имеется определенное количество фишек (монет, камешков и т. д.), разложенных в несколько рядов (или кучек), и два игрока по очереди забирают по одной или нескольку фишек из любого ряда. Выигрывает (или, наоборот, проигрывает) тот, кто взял последнюю фишку.
В литературе нередко пишут о выигрышной стратегии и о программировании соответствующих алгоритмов. Однако с игрой «ним» связаны и другие интересные сюжеты. Так, до сих пор нет полной ясности ни с корнями игры, ни даже с происхождением ее названия. Сегодня, в эпоху повального увлечения компьютерными играми, небезынтересно узнать, что «ним» был первой игрой, в которую человек сыграл против машины.
В 1902 году американский математик, профессор Гарвардского университета Чарльз Бутон, опубликовал описание правил игры, которую назвал «ним». По его словам, поначалу эта игра заинтересовала его своей кажущейся сложностью, которая обернулась затем в высшей степени простым и полным математическим описанием. Для варианта игры, в котором произвольное количество фишек раскладывалось в три ряда, Бутон предложил беспроигрышную стратегию, основанную на анализе двоичных представлений числа фишек в рядах. Кроме того, он обобщил решение для случая произвольного количества рядов.
Чарльз Леонард Бутон родился 25 апреля 1869 года в Сент-Луисе (штат Миссури) в семье инженера. Инженером был и его дед, инженерами стали трое братьев — однако Чарльз посвятил себя чистой науке. Степень бакалавра он получил в Вашингтонском университете, затем продолжил учебу в Гарварде. Здесь, как лучший студент, Бутон был удостоен стипендии для обучения за границей, и два года провел в Лейпциге у выдающегося норвежского математика, автора работ по дифференциальной геометрии Софуса Ли. Бутон стал одним из последних его учеников, а общение с Ли определило его научные интересы. Вплоть до своей кончины 20 февраля 1920 года Бутон оставался одним из ведущих профессоров Гарвардского университета и активным членом математического сообщества. Так, в течение многих лет он являлся редактором Бюллетеня и Трудов Американского Математического общества.
Относительно происхождения и истории игры Бутон в своей статье дал только самую скудную информацию. По его словам, похожая игра в свое время пользовалась популярностью у учащихся некоторых американских колледжей, и в нее также охотно играли участники ярмарок в провинциальных американских городках. Бутон говорит, что ее называли «фан-тан» (Fan-Tan). Это название наводит на мысль о Китае, но Бутон справедливо пишет, что хотя в Китае действительно имеется игра с таким названием, с «нимом» она не имеет ничего общего. Эта игра заключается в следующем — крупье предлагает делать ставки на то, каким будет остаток от деления на 4 количества жетонов, которое он возьмет двумя горстями из большой кучи жетонов. «Фантан» пользуется дурной репутацией, поскольку опытный крупье, оценив соотношение сделанных ставок, может вынуть из кучи именно столько жетонов, сколько необходимо для того, чтобы остаться в выигрыше.
На работу Бутона сразу же обратили внимание.
Так, много писал о ней известный немецкий математик и автор нескольких книг по занимательной математике Вильгельм Аренс, который, между прочим, как и Бутон, учился в Лейпциге у Софуса Ли.
Сегодня известно, что похожие (хотя и не в точности такие же) игры были знакомы многим народам Азии и Африки. Однако и через сто лет после статьи Бутона происхождение игры «ним» не стало более ясным. Встречающиеся в литературе ссылки на ее китайские корни (например, в первых изданиях классической книги Г. Харди и Э. Райта по теории чисел авторы прямо называли ее «китайской игрой «ним»») ничем не подкреплены и кажутся просто отзвуком приведенных нами выше, но плохо понятых слов Бутона. Кстати, не обнаружилось и никаких свидетельств того, что такая игра когда-либо действительно была распространена в Америке. Так что не исключено, что правила игры Чарльз Бутон определил сам, — хотя, быть может, и опирался при этом на какой-то образец.
Итак, название «ним» игре дал сам Бутон, однако никак его не объяснил. За прошедшие сто лет появилось немало версий его происхождения, в той или иной степени убедительных. Самая остроумная из них утверждает, что nim — это перевернутое слово win (победа). Конечно, такое объяснение представляется явной натяжкой. Несомненно ошибочным является утверждение, будто ним — это китайское название игры (в действительности, в основных диалектах китайского языка слова вообще не могут заканчиваться на — м).
Гораздо более убедительной кажется другая версия, настаивающая на английском происхождении слова. В самом деле, в староанглийском языке глагол to nim некогда означал брать, а позднее он стал частью уголовного жаргона со смыслом, близким к русскому стянуть, свистнуть.
Но версия английского происхождения названия игры не является единственной. В появившейся в 1953 Г°ДУ статье ее автор, профессор Алан Росс, предположил, что, поскольку Бутон долго жил в Германии, то мог заимствовать название игры из немецкого языка; он указал также, что в немецком языке есть глагол nehmen («брать, хватать»), который в единственном числе в настоящем времени имеет форму nimmt. Действительно, в немецком языке даже имеется идиома Er ist vom Stamme «Nimm» (у него руки загребущие).
Не исключено, что Бутон, хорошо знавший немецкий язык, мог вдохновиться именно этим значением.
Росс выразил надежду, что кто-либо из людей, близко знавших профессора Бутона, может внести ясность в этот вопрос. И действительно, в одном из ближайших номеров журнала был опубликован отклик на это обращение известного гарвардского математика Джозефа Уолша. Уолш сообщил, что он в молодости был учеником Бутона, часто бывал у него дома и отлично помнит, как тот говорил, что произвел название игры от немецкого nimm, — отбросив последнюю букву.
Казалось бы, свидетельство уважаемого ученого, не доверять которому нет никаких оснований, должно было подвести черту под дискуссией, однако этого так и не произошло, и ссылки на различные версии по-прежнему встречаются в литературе.
Несмотря на то, что Бутон дал исчерпывающее математическое описание игры (а может быть, именно по этой причине), «ним» надолго попал в поле зрения специалистов по теории игр. Были предложены и досконально изучены многочисленные варианты и разновидности игры. С приходом компьютерной эры программирование «нима» стало одним из популярных упражнений для начинающих программистов (в Интернете можно найти множество ее реализаций). Входила игра, например, в популярный в середине 1990-х годов набор «24 Games for Windows».