Охота на электроовец. Большая книга искусственного интеллекта

Марков Сергей Николаевич

Существуют и другие способы разделения игр на классы, но мы не будем далее углубляться в этот вопрос. Итак, наша жизнь — игра. Игра некооперативная, асимметричная, параллельная, с непостоянной суммой, с неполной и несовершенной информацией.

3.1 Ним и ниматрон

— Пари, что год моего рождения, умноженный на два, даёт чётное число.

Том Стоппард. Розенкранц и Гильденстерн мертвы [444]

444

^* Пер. И. Бродского.

При игре в ним два игрока по очереди берут предметы, разложенные на несколько кучек (обычно на три).

За один ход можно взять любое количество предметов (больше нуля) из любой кучки. Выигрывает игрок, взявший последний предмет. В древние времена, когда люди ещё пользовались спичками, для игры в ним обычно использовали кучки из спичек. В принципе, для нима подходят любые предметы — монетки, камешки, пуговицы, золотые слитки 999-й пробы. Для особых ценителей существуют даже специальные наборы для игры в ним, но выпускают их на всякий случай ограниченными сериями.

Различные разновидности этой игры известны с древних времён. По одной из существующих версий, она возникла в Китае, поскольку очень похожа на китайскую игру «сбор камней» (? ??, jian-shizi, цзяньшицзы) [445] , но это не точно [446] . Самые ранние европейские упоминания нима относятся к началу XVI в. Однако его современное название придумано на рубеже XIX–XX вв. математиком Чарльзом Бутоном из Гарвардского университета, который в 1901–1902 гг. разработал математическую теорию этой игры [447] . Это стало одним из первых случаев создания теории игры в истории математики. Вся теория вместе с описанием правил игры занимает всего пять страниц текста. Хотя Бутон и создал математическую теорию игры, он так и не дал объяснения тому, почему было выбрано такое странное название. Некоторые исследователи полагают, что название было образовано от немецкого глагола nehmen или от староанглийского nim, имеющих значение «брать». По другой версии, название было получено путём переворота букв английского глагола win («побеждать»). Несложно заметить, что игра в ним — некооперативная, симметричная, последовательная, с нулевой суммой, с полной и совершенной информацией. Трудно представить себе что-нибудь более простое. Неудивительно, что именно такие игры первыми стали подвластны машинам.

445

Яглом И. М. (1971). Две игры со спичками / Квант. № 2 // http://kvant.mccme.ru/1971/02/dve_igry_so_spichkami.htm

446

Jorgensen A. H. (2009). Context and driving forces in the development of the early computer game Nimbi / IEEE Annals of the History of Computing, Vol. 31, Iss. 3, pp. 44–53 // https://doi.org/10.1109/MAHC.2009.41

447

Bouton C. L. (1901–1902). Nim, A Game with a Complete Mathematical Theory / The Annals of Mathematics, 2nd Ser., Vol. 3, No. 1/4. (1901–1902), pp. 35–39 // https://paradise.caltech.edu/ist4/lectures/Bouton1901.pdf

На Всемирной выставке в Нью-Йорке в 1940 г. компания Westinghouse Electric представила двух роботов — Elektro и Sparko, а также машину под названием «Ниматрон» (Nimatron), способную играть в ним.

Главным конструктором машины был американский физик-ядерщик Эдвард Кондон, который с 1937 г. занимал в Westinghouse Electric позицию заместителя директора по исследованиям [448] . Идея сделать машину для игры в ним пришла к Кондону, когда он понял, что пересчётные схемы, которые используются в счётчиках Гейгера, можно применить для представления чисел, описывающих состояния игры [449] . Кондон разработал и собрал «Ниматрон» зимой 1939/40 года с помощью своих ассистентов — Джерельда Тоуни и Уилларда Дерра. 26 апреля 1940 г. он подал заявку на получение патента на устройство, который был выдан 24 сентября того же года [450] .

448

Dalakov G. The Nimatron of Edward Condon / History of Computers: hardware, software, internet… // https://history-computer.com/ModernComputer/Relays/Condon.html

449

Weiner C. (1968). Edward Condon – Session II. Oral History Interviews. Interviews that offer unique insights into the lives, works, and personalities of modern scientists / American Institute of Physics // https://www.aip.org/history-programs/niels-bohr-library/oral-histories/4997-2

450

См. патент «Machine to play game of nim». 1940-09-24 .

Масса машины, логика которой была основана на электромеханических реле, составляла более тонны [451] . На передней панели «Ниматрона» располагалось четыре столбца по семь ламп. Игрок, делая ход, мог погасить одну или несколько ламп в одном из рядов, после чего очередь хода переходила к машине. Если «Ниматрон» проигрывал партию, то выдавал игроку жетон с надписью Nim Champ (Чемпион по ниму).

Рис. 52. «Ниматрон»

451

Dreher T. (2015). History of Computer Art // http://iasl.uni-muenchen.de/links/GCA.pdf

Первая

версия машины совершала свои ходы моментально — по оценке Кондона, на выбор хода у «Ниматрона» уходило менее одной сотой доли секунды. Но такое поведение механического соперника слишком пугало игроков, и разработчики решили добавить в схемы замедляющие цепи. Таким образом, машина делала вид, что в течение нескольких секунд обдумывает ход. По мнению Кондона, это был первый в истории случай намеренного замедления работы компьютера [452] .

452

Flesch R. (1951). The Art of Clear Thinking. — 1. — New York, USA: Harper & Brothers Publishers // https://dc135.files.wordpress.com/2012/11/flesch-the-art-of-clear-thinking.pdf

«Ниматрон» всегда выбирал оптимальные ходы, но разработчики решили всегда предоставлять право первого хода человеку, а в качестве стартовой позиции выбиралась одна из девяти заложенных в память машины позиций, в которых игрок, делающий ход первым, при правильной игре выходил победителем. Когда кто-нибудь из посетителей, раздосадованных проигрышем, заявлял, что машину обыграть невозможно, операторы стенда показывали, как это можно сделать [453] . За время выставки в игру сыграло не менее 50 000 человек, из которых около 90% не смогли выиграть у «Ниматрона» [454] .

453

Rougetet L. (2016). Machines designed to play Nim games. Teaching supports for mathematics, algorithmics and computer science (1940–1970) // https://hal.archives-ouvertes.fr/hal-01349260/document

454

Dalakov G. The Nimatron of Edward Condon / History of Computers: hardware, software, internet… // https://history-computer.com/ModernComputer/Relays/Condon.html

В последний раз машина участвовала в выставке в 1942 г. в Нью-Йорке, затем «Ниматрон» был перемещён в научные коллекции Планетария в Питтсбурге (штат Пенсильвания), где какое-то время демонстрировался публике [455] , после чего следы машины теряются.

«Ниматрон» был одной из первых в мире машин, способных играть в игру, иногда его даже называют первой в мире компьютерной игрой. Это, по всей видимости, действительно так, если не принимать в расчёт «шахматного игрока» (El Ajedrecista), о котором мы расскажем несколько позже.

455

Rougetet L. (2016). Machines designed to play Nim games. Teaching supports for mathematics, algorithmics and computer science (1940–1970) // https://hal.archives-ouvertes.fr/hal-01349260/document

Несмотря на этот успех «Ниматрона», Кондон считал его одним из самых больших провалов в своей карьере — ведь он не смог увидеть весь потенциал машины: «Это было как минимум за четыре или пять лет до Джонни фон Неймана, Эккерта, Мокли и всего этого цифрового компьютерного бизнеса, и [я] ни разу не подумал об этом всерьёз; я просто думал об этом как о забавной штуке, но схемы и всё прочее были точь-в-точь такими же, как позже в компьютерах, программируемых компьютерах». В итоге влияние «Ниматрона» на цифровые компьютеры и компьютерные игры оказалось незначительным [456] .

456

Dalakov G. The Nimatron of Edward Condon / History of Computers: hardware, software, internet… // https://history-computer.com/ModernComputer/Relays/Condon.html

Вслед на «Ниматроном» было создано множество других машин для игры в ним. В 1948 г. Реймонд Редхеффер представил машину массой менее 2,5 кг. По словам Редхеффера, её конструкция была разработана им в 1941–1942 гг. [457] Несколько лет спустя компания Ferranti, занимающаяся разработкой электротехнического и военного электронного оборудования, создала первый цифровой компьютер, предназначенный для игры в ним, — «Нимрод» (The Nimrod). Он был представлен на Британском фестивале (научная выставка) в мае 1951 г., а затем на Берлинской торговой ярмарке (промышленная выставка) в октябре того же года. На этих выставках «Нимрод» произвёл настоящий фурор. Многие очевидцы рассказывали, что наибольшее впечатление производила не игра с «Нимродом», а наблюдение за мигающими огнями, которые должны были отражать мыслительную деятельность машины. Чтобы контролировать гигантскую толпу зрителей, организаторы выставки даже были вынуждены обратиться за помощью к полиции [458] .

457

Redheffer R. (1948). A Machine for Playing the Game Nim / The American Mathematical Monthly, Vol. 55, Iss. 6, pp. 343–349 // https://doi.org/10.1080/00029890.1948.11999249

458

Rougetet L. (2016). Machines designed to play Nim games. Teaching supports for mathematics, algorithmics and computer science (1940–1970) // https://hal.archives-ouvertes.fr/hal-01349260/document