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

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

В 1960 г. Дональд Мичи разработал программу, получившую название «Спичечнокоробочный обучающийся движок для крестиков-ноликов» (Matchbox Educable Noughts And Crosses Engine, MENACE; слово menace по-английски значит «угроза»). Эта программа была способна обучиться идеальной игре в крестики-нолики и для своего выполнения не требовала такого дефицитного ресурса, как компьютер. Вместо него Мичи использовал набор из трёх сотен спичечных коробков, каждый из которых соответствовал уникальному состоянию доски. Спичечные коробки были заполнены цветными бусинками, соответствующими отдельным ходам. Количество шариков каждого цвета указывало на «уверенность» в том, что соответствующий ход является наилучшим. В зависимости от результата каждой сыгранной партии производилось изменение количества бусинок в коробках, соответствующих возникшим в игре позициям, в результате чего программа постепенно всё более уверенно выбирала правильные ходы [486] . В статье Мичи, посвящённой MENACE, впервые был введён термин «обучение с подкреплением» [reinforcement learning] [487] .

486

Michie D. (1963). Experiments on the mechanization of game-learning // http://people.csail.mit.edu/brooks/idocs/matchbox.pdf

487

Brooks R. (2019). Interesting Stuff for Download / Rodney Brooks — Roboticist // http://people.csail.mit.edu/brooks/documents.html

Простота

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

3.3 Играть на уровне бога: от Цермело до «Ломоносова» (первое отступление)

Двух операторов била нервная дрожь. Тысячелетия ожидания прошли не впустую.

— Он действительно существует? — выдохнул Хвуудт.

— Он действительно существует, — подтвердил Глубокомысленный.

— Главный Ответ? На Главный Вопрос Жизни, Вселенной, и Всего Такого?

— Да.

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

— И ты готов выдать его нам? — успокоившись, спросил Колнгкилл.

— Готов.

— Сейчас?

— Сейчас.

Оба оператора облизали сухие губы.

— Хотя я не думаю, — добавил компьютер, — что он вам понравится.

— Неважно! — сказал Хвуудт. — Мы должны знать его! Сейчас же!

— Сейчас? — переспросил Глубокомысленный.

— Да! Сейчас!

— Отлично, — сказал компьютер и снова погрузился в молчание. Хвуудт и Колнгкилл трепетали. Напряжение становилось невыносимым.

— Серьёзно, он вам не понравится, — заметил Глубокомысленный.

— Говори!

— Отлично, — сказал компьютер. — Ответ на Главный Вопрос…

— Ну…!

— Жизни, Вселенной, и Всего Такого…, — продолжал компьютер.

— Ну…!!!

— Это… — сказал Глубокомысленный и сделал многозначительную паузу.

— Ну…!!!!!!

— Сорок два, — сказал Глубокомысленный с неподражаемым спокойствием и величием.

Дуглас Адамс. Путеводитель хитч-хайкера по Галактике [488]

488

^* Пер. В. Филиппова.

3.3.1 Основоположник теории игр Эрнст Цермело

Серьёзный разговор о теории игр обычно не обходится без упоминания немецкого математика Эрнста Цермело и его теоремы. Цермело в жизни сопутствовала научная удача: его именем названо сразу две теоремы, первая из них — одна из фундаментальных теорем теории множеств — называется также теоремой о полном упорядочении; вторая, доказанная в 1913 г., стала первой формальной теоремой теории игр.

В современной литературе по теории игр даются различные формулировки этой теоремы [489] . Некоторые авторы утверждают, что Цермело доказал, что шахматы являются детерминированной (т. е. лишённой элемента случайности) игрой, например: «В шахматах либо белые могут добиться форсированной победы, либо чёрные могут добиться форсированной победы, либо обе стороны могут форсировать ничью» [490] ^, [491] ^, [492] .

489

Schwalbe U., Walker P. (1997, 1999). Zermelo and the Early History of Game Theory // http://abel.math.harvard.edu/~elkies/FS23j.03/zermelo.pdf

490

Aumann R. J. (1989). Game Theory / Eatwell J., Milgate M., Newman P. (1989). The New Palgrave: Game Theory, Macmillan Press, London.

491

Eichberger J. (1993). Game Theory for Economists, Academic Press, San Diego.

492

Hart S. (1992). Games in Extensive and Strategic Forms, in Robert J. Aumann and Sergiu Hart (eds.), Handbook of Game Theory, Volume 1, NorthHolland, Amsterdam.

Другие делают более общие утверждения, называя их теоремой Цермело, например: «В каждой конечной игре с полной информацией имеется строгое стратегическое равновесие Нэша, которое может быть найдено при помощи обратной индукции. Более того, если ни у одного из игроков нет одинаковых результатов в двух произвольных конечных узлах, то существует уникальное равновесие Нэша, которое может быть найдено таким образом» [493] . Равновесием Нэша называется ситуация, в которой ни один участник не может увеличить выигрыш, изменив свою стратегию, если другие участники своих стратегий не меняют. Авторов не смущает, что Джон Нэш родился спустя 15 лет после доказательства теоремы Цермело.

493

Mas-Colell A., Whinston M. D., Green J. R. (1995). Microeconomic Theory, Oxford University Press, New York.

Некоторые вообще утверждают, что белые не могут проиграть: «…в конечной игре существует стратегия, следуя которой игрок, первым осуществляющий ход… может избежать поражения, но неизвестно, существует ли стратегия, следуя которой он может победить» [494] .

Кроме того, многие авторы указывают, что методом доказательства, использованным Цермело, была обратная индукция, например: «Цермело использовал этот метод ещё в 1912 году для анализа шахмат. Он начинает с конца игры и затем движется к её началу. По этой причине данную технику иногда называют обратной индукцией» [495] .

494

Dimand M. A., Dimand R. W. (1996). A History of Game Theory, Volume 1: From the Beginnings to 1945, Routledge, London.

495

Binmore K. (1992). Fun and Games: A Text on Game Theory, D. C. Heath and Company, Lexington

Несмотря

на большой интерес к теории игр, в англоязычной литературе распространилась путаница в отношении того, в чём именно заключался вклад Цермело, равно как и вклад некоторых других ранних теоретиков. Как это ни странно, проблема возникла, по всей видимости, из-за языкового барьера: многие ранние работы по теории игр были написаны на немецком и не переводились на английский. Например, оригинальная работа Цермело под названием «О применении теории множеств к теории шахмат» (Uber eine Anwendung der Mengenlehre auf die Theorie des Schachspiels) [496] , увидевшая свет в 1913 г., не была переведена на английский вплоть до 1997 г. Также не была своевременно переведена на английский менее известная, но связанная работа Денеша Кёнига, написанная в 1927 г. [497] Вторая статья, связанная с работой Цермело, была написана Ласло Кальмаром в 1928–1929 гг. [498] ^, [499] , но на английский язык её перевели только в 1997 г. До работы Швальбе и Уокера «Цермело и ранняя история теории игр» (Zermelo and the Early History of Game Theory) [500] , написанной в 1997 г., по всей видимости, существовал только один корректный анализ работы Цермело — в статье Николая Воробьёва «Управляемые процессы и теория игр» (1955). Проблема в том, что эта книга переводилась только на немецкий язык (1975) и была недоступна англоязычному читателю. Со времён книги Воробьёва в русскоязычной литературе бытовало корректное описание вклада Цермело: «Цермело доказал детерминизм игр, подобных шахматам, и то, что рациональные игроки могут, используя полную информацию, разработать оптимальную стратегию игры». Вот как звучит вопрос, задаваемый Цермело в его статье: «Можно ли определить объективную оценку произвольной позиции в игре, а также наилучший возможный ход <…> или по крайней мере определить их математически объективно, без необходимости ссылаться на субъективные психологические понятия, такие как «идеальный игрок» и тому подобное?»

496

Zermelo E. (1913). Uber eine Anwendung der Mengenlehre auf die Theorie des Schachspiels / Proceedings of the Fifth Congress Mathematicians (Cambridge 1912), pp. 501–504 // https://doi.org/10.1007/978-3-540-79384-7_9

497

Konig D. (1927). Uber eine Schlussweise aus dem Endlichen ins Unendliche / Acta Scientiarum Mathematicarum, Vol. 3, pp. 121–130.

498

Kalmar L. (1928, 1929), Zur Theorie der abstrakten Spiele / Acta Scientiarum Mathematicarum, Vol. 4, pp. 65–85.

499

Dimand M. A., Dimand R. W. (1997). The Foundations of Game Theory, Volume I. Edward Elgar, Aldershot.

500

Schwalbe U., Walker P. (1997, 1999). Zermelo and the Early History of Game Theory // http://abel.math.harvard.edu/~elkies/FS23j.03/zermelo.pdf

Прежде чем продолжить рассуждения о вкладе Цермело, давайте рассмотрим вопрос о максимальной длине шахматной партии. Хотя сегодня шахматы уже не столь популярны, как в 1980-е, основные правила этой игры знакомы едва ли не каждому — худо-бедно почти все мы в детстве освоили, что конь ходит «буквой Г» и что пешки не ходят назад. Однако в шахматах есть правила, о которых знает не каждый любитель. Например, установленное Международной шахматной федерацией (FIDE, от французского Federation Internationale des Echecs) правило пятидесяти ходов гласит, что если в течение пятидесяти ходов ни одна пешка не двинулась вперёд и ни одна фигура не была взята, то в партии присуждается ничья по требованию любого из игроков. Также любой из игроков вправе потребовать присуждения ничьей в случае как минимум троекратного повторения одной и той же позиции. Благодаря правилу пятидесяти ходов ни одна из сторон не может вопреки воле другой стороны затянуть шахматную партию до бесконечности — для того чтобы она не завершилась в соответствии с вышеуказанным правилом, каждые пятьдесят ходов должно происходить хотя бы одно взятие фигуры или движение вперёд пешки и, кроме этого, позиции не должны повторяться. Весьма остроумные подсчёты показывают, что при таких условиях партия не может продолжаться больше примерно 6000 ходов [501] . В теории игроки могут отказаться от требования ничьей, несмотря на повторение позиции или превышение границы, установленной правилом пятидесяти ходов. Специально для таких случаев (в общем-то, сугубо теоретических) в 2014 г. FIDE установила специальное правило, в соответствии с которым при достижении порога в 75 ходов без взятий и движений пешек ничья присуждается автоматически. Словом, в современных шахматах есть такие тонкости, которые известны не многим. Цермело же рассматривал версию игры, в которой бесконечные партии были теоретически возможны.

501

Godden K. (2007). The Longest Possible Chess Game / Blog at Chess.com // https://www.chess.com/blog/kurtgodden/the-longest-possible-chess-game

Цермело задаётся двумя вопросами: во-первых, что означает, что игрок находится в «выигрышной» позиции, и можно ли это определить объективным математическим способом? Во-вторых, если он находится в выигрышной позиции, можно ли определить количество ходов, необходимых для форсированного выигрыша, то есть такого выигрыша, которому противник не может воспрепятствовать?

Чтобы дать ответ на первый вопрос, Цермело утверждает, что необходимым и достаточным условием является непустота определённого множества, содержащего все возможные последовательности ходов, такие, что игрок (например, играющий белыми фигурами) выигрывает независимо от того, как играет другой игрок. Но если это множество будет пустым, лучшее, чего сможет достичь игрок, — это ничья. Аналогичным образом Цермело определяет и другое множество, содержащее все возможные последовательности ходов, такие, что игрок может отложить своё поражение на бесконечное количество ходов, что подразумевает ничью. Это множество также может быть пустым, то есть игрок может отсрочить поражение только на конечное число ходов в случае, если его противник действует правильно. Однако последнее равносильно тому, что противник может добиться победы. Возможность того, что оба набора будут пустыми, означает, что белые не могут гарантировать, что они не проиграют.