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

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

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

3.3.2 Метод обратной индукции

Часто приписываемый Цермело метод обратной индукции был впервые описан в 1944 г. в монографии Джона фон Неймана и Оскара Моргенштерна «Теория игр и экономическое поведение» [Theory of Games and Economic Behavior] [502] ,

сегодня считающейся одной из основополагающих работ в области теории игр.

Значимость работ Джона фон Неймана для вычислительной техники трудно переоценить. Наверняка вы слышали, что архитектуру большинства современных компьютеров часто называют архитектурой фон Неймана (мы ещё вернёмся к этому термину позже), а сами компьютеры — фон-неймановскими машинами. Кроме того, фон Нейман заложил основы математического аппарата квантовой механики, внёс существенный вклад в теорию операторов (его именем назван особый вид алгебр — алгебры фон Неймана), предложил теорию клеточных автоматов, а также стал одним из ключевых участников Манхэттенского проекта. В 1970 г. Международный астрономический союз присвоил имя Джона фон Неймана кратеру на обратной стороне Луны. В его память учреждены следующие награды: медаль Джона фон Неймана, Теоретическая премия фон Неймана, «Лекция Джона фон Неймана».

502

von Neumann J., Morgenstern O. (1944). Theory of Games and Economic Behavior. Science Editions, J. Wiley // https://archive.org/details/game_theo_econ/page/n139

Кем же был этот человек со звучной немецкой фамилией?

Янош Лайош Нейман родился в 1903 г. и был старшим из трёх сыновей в состоятельной еврейской будапештской семье. Его отец, Микса Нейман, переселился в Будапешт из маленького городка Печ в конце 1880-х гг. Он получил степень доктора юриспруденции и работал юристом в Венгерском ипотечно-кредитном банке (Magyar Jelzalog-Hitelbank). Мать Яноша, Маргарет Канн, была домохозяйкой и старшей дочерью коммерсанта Якоба Канна — партнёра в фирме Kann—Heller, торговавшей сельхозоборудованием [503] .

503

Israel G., Gasca A. M. (2009). The World as a Mathematical Game: John von Neumann and Twentieth Century Science. Birkhauser Basel // https://books.google.at/books?id=6o52lsjG83UC

Янош с детства проявлял признаки одарённости: в шесть лет он мог делить в уме восьмизначные числа, складывать фразы на древнегреческом, в восемь — уже неплохо разбирался в математическом анализе.

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

В 1913 г. старшему Нейману был пожалован дворянский титул с правом наследования. Таким образом Янош получил дополнение к своему имени в виде символа знатности. Теперь его имя звучало по-австрийски как Янош фон Нейман, а по-венгерски как Нейман Маргиттаи Янош Лайош [504] . Когда позже фон Нейман преподавал в Берлине и Гамбурге, его называли Иоганн фон Нейман. После переезда в 1930-х гг. в США, его имя изменилось на английский манер — Джон. Забавно, что братья фон Неймана, оказавшись в США получили совсем другие фамилии: Vonneumann и Newman.

504

^* Маргиттаи означает «из Маргиты», а окончание –i — типичное окончание, используемое при образовании венгерских дворянских имён от названия местности; но семья Неймана не имела никакого отношения к городу Маргита, фамилию старший Нейман, по всей видимости, избрал по имени жены, а на выбранном гербе были изображены три маргаритки на зелёном поле.

Джон Харсаньи, венгерский эмигрант и представитель следующего поколения исследователей теории игр, хотя лично и не знал фон Неймана, но был хорошо знаком с обществом, из которого он вышел. Согласно Харсаньи, фон Нейман всегда использовал приставку «фон» к фамилии и его задевало, если кто-то опускал её. Более того, фон Нейман настаивал на том, что если предложение начиналось с его фамилии, то вы не должны были использовать заглавную букву в слове «фон», поскольку изменение первоначального написания недопустимо. Это, конечно, было весьма незначительной человеческой слабостью [505] .

505

Leonard R. (2010). Von Neumann, Morgenstern, and the Creation of Game Theory: From Chess to Social Science, 1900–1960. Cambridge University Press // https://books.google.ru/books?id=uV6sAwAAQBAJ

фон Нейман получил степень доктора философии по математике в Будапештском университете в 1926 г. Параллельно он изучал химические технологии в Швейцарской высшей технической школе Цюриха. Отец Яноша считал, что профессия математика не сможет обеспечить сыну надёжное будущее. В 1927

г. фон Нейман был назначен приват-доцентом Берлинского университета, став самым молодым обладателем этой степени в истории университета. Первую половину 1929/30 учебного года он провёл на должности приват-доцента в Гамбурге [506] .

506

Aspray W. (1990). John Von Neumann and the Origins of Modern Computing. MIT Press // https://books.google.ru/books?id=M6DmngEACAAJ

В 1930 г. фон Нейман был приглашён на преподавательскую позицию в Принстонский университет, а далее, с 1933 г. и до самой смерти, занимал профессорскую должность в уже знакомом нам Институте перспективных исследований (IAS) [507] .

В межвоенные годы многие европейские евреи эмигрировали в США, среди них был ряд венгерских учёных: помимо фон Неймана в США перебрались Теодор фон Карман, Пол Халмош, Юджин Вигнер, Эдвард Теллер, Дьёрдь Пойа, Денеш Габор и Пал Эрдёш, многие из них затем приняли участие в разработке ядерного оружия. Современники отмечали, что венгерские учёные обладали развитым интеллектом, говорили на необычном языке, а их родиной была сравнительно небольшая страна. В результате их стали в шутку называть марсианами, что сами учёные приняли с должным чувством юмора.

507

Macrae N. (1992). John von Neumann: The Scientific Genius Who Pioneered the Modern Computer, Game Theory, Nuclear Deterrence, and Much More. Pantheon Press // https://books.google.ru/books?id=ratFAAAAYAAJ

В соответствии с шуточной легендой венгерские учёные были потомками разведывательных сил Марса, которые якобы приземлились в Будапеште на рубеже XIX–XX вв. и от которых женщины зачали детей. Вскоре марсиане, посчитав планету непригодной для исследований и жизни, оставили Землю. Родившиеся якобы от марсиан дети позднее уехали в Америку.

Дьёрдь Маркс в книге «Прибытие марсиан» (A marslakok erkezese) писал:

— …Вселенная — огромная, содержит мириады звёзд, и многие из них не слишком отличаются от нашего Солнца. Вокруг многих из этих звёзд, возможно, вращаются планеты. Какая-то часть этих планет содержит жидкую воду на своей поверхности и газообразную атмосферу. Исходящая от звезды энергия приводит к синтезу органических веществ, превращает океан в тонкий слой тёплого супа. Эти химические вещества соединяются друг с другом и создают систему самопроизводства. Простейшие живые организмы размножаются, эволюционируют в ходе естественного отбора и становятся более сложными, пока не появятся по-настоящему мыслящие существа. Далее последуют цивилизация, наука и технология. И в поисках новых миров они отправятся на соседние планеты, а затем планеты у соседних звёзд. И они расселятся по всей галактике. И эти исключительно развитые люди уж точно не проглядят такое прекрасное место, как наша Земля. Итак, — Ферми подошёл к решающему вопросу, — если всё это произошло, то они уже наверняка прибыли сюда. Так где же они?

Именно Лео Силард, человек с отличным чувством юмора, дал идеальный ответ парадоксу Ферми:

— Они среди нас, — ответил он, — но называют себя венграми.

Итак, фон Нейман и Моргенштерн дали формальное математическое определение обратной индукции (заметим, что они не использовали этот термин как таковой, а говорили лишь об индукции и последовательном рассмотрении позиций игры в обратном порядке — от тривиальных к нетривиальным). Сам термин «обратная индукция» периодически использовался математиками и ранее [508] , но современное его применение в качестве обозначения процедуры, предложенной фон Нейманом и Моргенштерном, начинает утверждаться только в начале 1950-х в работах отца динамического программирования Ричарда Беллмана [509] .

508

Brown T. A. (1941). Elementary Inequalities. The Mathematical Gazette, Vol. 25, Iss. 263, pp. 2–11 // https://doi.org/10.2307/3606471

509

Bellman R. (1954). Inequalities / Mathematics Magazine, Vol. 28, Iss. 1, pp. 21–26 // https://doi.org/10.2307/3029433

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