Читаем без скачивания Охота на электроовец. Большая книга искусственного интеллекта - Марков Сергей Николаевич

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

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

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

Дьёрдь Маркс в книге «Прибытие марсиан» (A marslakók érkezése) писал:

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

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

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

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

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

Методология динамического программирования, позволяющая машинам осуществлять ретроспективный анализ игр, была создана Беллманом в 1965 г.[510] Публикация Беллмана стала итогом его работы, о которой сообщалось ещё четырьмя годами ранее[511]. Беллман полагал, что рано или поздно появятся машины, способные, применяя его метод, найти полное вычислительное решение задачи оптимальной игры для шашек, в отношении же шахмат он считал, что удастся получить точные решения для некоторых классов окончаний — например для чисто пешечных эндшпилей[512].

Давайте рассмотрим пример применения метода ретроспективного анализа к такой простой игре, как крестики-нолики.

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

2. Теперь рассмотрим множество позиций с неопределённой оценкой, в которых очередь хода за крестиками и существует хотя бы один ход, ведущий в позицию с оценкой 1. Оценкой для таких позиций тоже становится единица: то есть позиции, в которых у крестиков есть хотя бы один ход, ведущий в выигрышную для них позицию, являются для них тоже выигрышными.

3. Аналогично для позиций с очередью хода, принадлежащей ноликам, имеющих неопределённую оценку, при наличии у ноликов хотя бы одного хода, ведущего в позицию с оценкой –1, устанавливаем оценку, равную –1.

4. Рассмотрим теперь позиции, для которых все возможные ходы приводят в позиции с определённой оценкой. Для таких позиций выберем оценку, соответствующую лучшему из возможных исходов для стороны, которой принадлежит очередь хода. То есть если очередь хода принадлежит крестикам и у них есть ход, ведущий в ничейную позицию, то оценкой позиции является 0, в противном случае (т. е. если все ходы ведут к проигрышным позициям) оценкой позиции становится –1. Если же очередь хода за ноликами и у них есть ход, ведущий в ничейную позицию, то оценкой позиции становится 0, в противном же случае — 1.

5. Если на шагах 2–4 была получена хотя бы одна новая оценка, возвращаемся к шагу 2.

Таким образом, мы, начав с финальных позиций игры, постепенно перемещаемся в направлении её начальной позиции, присваивая по пути оценки позициям промежуточным. Именно из-за этого движения задом наперёд метод называется ретроспективным анализом.

Работу алгоритмов удобно рассматривать в графической форме, используя представление игры в виде древовидной структуры, в которой узлы соответствуют позициям в игре, а ветви — возможным ходам. Алгоритм начинает работу с установления оценки для нижних (терминальных) узлов дерева, а затем постепенно поднимается вверх, пока не достигает корневого узла — начальной позиции игры.