Охота на электроовец. Большая книга искусственного интеллекта - Марков Сергей Николаевич
Прежде чем продолжить рассуждения о вкладе Цермело, давайте рассмотрим вопрос о максимальной длине шахматной партии. Хотя сегодня шахматы уже не столь популярны, как в 1980-е, основные правила этой игры знакомы едва ли не каждому — худо-бедно почти все мы в детстве освоили, что конь ходит «буквой Г» и что пешки не ходят назад. Однако в шахматах есть правила, о которых знает не каждый любитель. Например, установленное Международной шахматной федерацией (FIDE, от французского Fédération Internationale des Échecs) правило пятидесяти ходов гласит, что если в течение пятидесяти ходов ни одна пешка не двинулась вперёд и ни одна фигура не была взята, то в партии присуждается ничья по требованию любого из игроков. Также любой из игроков вправе потребовать присуждения ничьей в случае как минимум троекратного повторения одной и той же позиции. Благодаря правилу пятидесяти ходов ни одна из сторон не может вопреки воле другой стороны затянуть шахматную партию до бесконечности — для того чтобы она не завершилась в соответствии с вышеуказанным правилом, каждые пятьдесят ходов должно происходить хотя бы одно взятие фигуры или движение вперёд пешки и, кроме этого, позиции не должны повторяться. Весьма остроумные подсчёты показывают, что при таких условиях партия не может продолжаться больше примерно 6000 ходов [501]. В теории игроки могут отказаться от требования ничьей, несмотря на повторение позиции или превышение границы, установленной правилом пятидесяти ходов. Специально для таких случаев (в общем-то, сугубо теоретических) в 2014 г. FIDE установила специальное правило, в соответствии с которым при достижении порога в 75 ходов без взятий и движений пешек ничья присуждается автоматически. Словом, в современных шахматах есть такие тонкости, которые известны не многим. Цермело же рассматривал версию игры, в которой бесконечные партии были теоретически возможны.
Цермело задаётся двумя вопросами: во-первых, что означает, что игрок находится в «выигрышной» позиции, и можно ли это определить объективным математическим способом? Во-вторых, если он находится в выигрышной позиции, можно ли определить количество ходов, необходимых для форсированного выигрыша, то есть такого выигрыша, которому противник не может воспрепятствовать?
Чтобы дать ответ на первый вопрос, Цермело утверждает, что необходимым и достаточным условием является непустота определённого множества, содержащего все возможные последовательности ходов, такие, что игрок (например, играющий белыми фигурами) выигрывает независимо от того, как играет другой игрок. Но если это множество будет пустым, лучшее, чего сможет достичь игрок, — это ничья. Аналогичным образом Цермело определяет и другое множество, содержащее все возможные последовательности ходов, такие, что игрок может отложить своё поражение на бесконечное количество ходов, что подразумевает ничью. Это множество также может быть пустым, то есть игрок может отсрочить поражение только на конечное число ходов в случае, если его противник действует правильно. Однако последнее равносильно тому, что противник может добиться победы. Возможность того, что оба набора будут пустыми, означает, что белые не могут гарантировать, что они не проиграют.
Впрочем, первый вопрос представлял лишь незначительный интерес для Цермело. Его гораздо больше интересовал второй — о количестве ходов, необходимом для победы в «выигрышной позиции». Цермело приходит к выводу, что максимально необходимое для победы число ходов не превышает числа возможных позиций в игре. Он использует доказательство от противного: предположим, что число ходов, необходимое белым для победы, превышает число возможных позиций. Тогда как минимум одна выигрышная позиция будет в процессе выполнения этой последовательности ходов возникать на доске дважды. Следовательно, белые могли бы при первом возникновении этой позиции совершить тот же ход, что и во втором случае, и таким образом достичь победы за число ходов, не превышающее количества возможных позиций.
3.3.2 Метод обратной индукции
Часто приписываемый Цермело метод обратной индукции был впервые описан в 1944 г. в монографии Джона фон Неймана и Оскара Моргенштерна «Теория игр и экономическое поведение» [Theory of Games and Economic Behavior] [502], сегодня считающейся одной из основополагающих работ в области теории игр.
Значимость работ Джона фон Неймана для вычислительной техники трудно переоценить. Наверняка вы слышали, что архитектуру большинства современных компьютеров часто называют архитектурой фон Неймана (мы ещё вернёмся к этому термину позже), а сами компьютеры — фон-неймановскими машинами. Кроме того, фон Нейман заложил основы математического аппарата квантовой механики, внёс существенный вклад в теорию операторов (его именем назван особый вид алгебр — алгебры фон Неймана), предложил теорию клеточных автоматов, а также стал одним из ключевых участников Манхэттенского проекта. В 1970 г. Международный астрономический союз присвоил имя Джона фон Неймана кратеру на обратной стороне Луны. В его память учреждены следующие награды: медаль Джона фон Неймана, Теоретическая премия фон Неймана, «Лекция Джона фон Неймана».
Кем же был этот человек со звучной немецкой фамилией?
Янош Лайош Нейман родился в 1903 г. и был старшим из трёх сыновей в состоятельной еврейской будапештской семье. Его отец, Микса Нейман, переселился в Будапешт из маленького городка Печ в конце 1880-х гг. Он получил степень доктора юриспруденции и работал юристом в Венгерском ипотечно-кредитном банке (Magyar Jelzálog-Hitelbank). Мать Яноша, Маргарет Канн, была домохозяйкой и старшей дочерью коммерсанта Якоба Канна — партнёра в фирме Kann—Heller, торговавшей сельхозоборудованием [503].
Янош с детства проявлял признаки одарённости: в шесть лет он мог делить в уме восьмизначные числа, складывать фразы на древнегреческом, в восемь — уже неплохо разбирался в математическом анализе.
Дела Миксы Неймана шли довольно неплохо — основатель и глава банка Кальман Селль в 1899 г. получил пост премьер-министра Венгрии и хотя и пробыл на нём относительно недолго (до 1903 г.), но впоследствии сохранял видную позицию в венгерской элите.
В 1913 г. старшему Нейману был пожалован дворянский титул с правом наследования. Таким образом Янош получил дополнение к своему имени в виде символа знатности. Теперь его имя звучало по-австрийски как Янош фон Нейман, а по-венгерски как Нейман Маргиттаи Янош Лайош [504]. Когда позже фон Нейман преподавал в Берлине и Гамбурге, его называли Иоганн фон Нейман. После переезда в 1930-х гг. в США, его имя изменилось на английский манер — Джон. Забавно, что братья фон Неймана, оказавшись в США получили совсем другие фамилии: Vonneumann и Newman.
Джон Харсаньи, венгерский эмигрант и представитель следующего поколения исследователей теории игр, хотя лично и не знал фон Неймана, но был хорошо знаком с обществом, из которого он вышел. Согласно Харсаньи, фон Нейман всегда использовал приставку «фон» к фамилии и его задевало, если кто-то опускал её. Более того, фон Нейман настаивал на том, что если предложение начиналось с его фамилии, то вы не должны были использовать заглавную букву в слове «фон», поскольку изменение первоначального написания недопустимо. Это, конечно, было весьма незначительной человеческой слабостью [505].
фон Нейман получил степень доктора философии по математике в Будапештском университете в 1926 г. Параллельно он изучал химические технологии в Швейцарской высшей технической школе Цюриха. Отец Яноша считал, что профессия математика не сможет обеспечить сыну надёжное будущее. В 1927 г. фон Нейман был назначен приват-доцентом Берлинского университета, став самым молодым обладателем этой степени в истории университета. Первую половину 1929/30 учебного года он провёл на должности приват-доцента в Гамбурге [506].
