home | login | register | DMCA | contacts | help | donate |      

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Э Ю Я


my bookshelf | genres | recommend | rating of books | rating of authors | reviews | new | форум | collections | читалки | авторам | add



Глава 8. Можно ли просчитать шахматы?

Шахматы – это уникальное познавательное поле, та сфера, где наука и искусство соединяются в человеческом представлении, а затем оттачиваются и совершенствуются по мере накопления опыта[35].

Гарри Каспаров

Представьте себе невероятно мощный компьютер, способный всегда, при любой ситуации на шахматной доске рассчитать лучший следующий ход. При этом “лучший” значит такой, который позволяет как можно быстрее выиграть или как минимум не проиграть – другими словами, ведет к оптимальному для участника исходу. Теперь вообразите, что этот компьютер играет против другого, идентичного ему во всех отношениях. Который из них победит? Или всегда будет ничья? Мы решили так много монументальных проблем в математике, что, казалось бы, такая древняя игра, как шахматы, с ее несложными правилами не должна представлять никакой трудности для теоретиков, вооруженных передовыми компьютерными технологиями. Но не тут-то было.

Первая машина для игры в шахматы, известная под названием “Турок”, была на самом деле ловким фокусом, бутафорией, хотя на эту мистификацию и клюнуло немало народу в период с 1770 года, когда машина была представлена публике венгерским изобретателем Вольфгангом фон Кемпеленом, по 1854 год, когда она сгорела во время пожара. Среди наблюдавших ее в действии – Наполеон Бонапарт (сам незаурядный математик), Бенджамин Франклин и один из пионеров современной вычислительной техники Чарльз Бэббидж. Машина представляла собой большой деревянный ящик, за которым располагались голова и туловище манекена в натуральную величину в богато украшенном османском одеянии и тюрбане. Через три открывающиеся дверцы на передней стороне ящика можно было рассмотреть различные детали сложного механизма, а когда поочередно открывались дверцы в задней части ящика, зрители могли видеть механизм насквозь. Постоянно скрытой от их взора оставалась лишь одна мелочь – находившийся внутри живой человек, опытный шахматист, передвигавшийся на скользящем сиденье из одной части ящика в другую, пока демонстратор одну за другой открывал смотровые дверцы. Обдумав очередной ответный ход, спрятанный шахматист передвигал фигуры на видимой зрителям доске с помощью механической руки “Турка”, соединенной посредством системы тросиков и шарниров со скрытой внутри ящика второй шахматной доской, с отверстиями для фигур. Оригинальный, превосходной работы автомат фон Кемпелена в игре тем не менее полностью полагался на интеллект управлявшего им человека.

Никакое механическое чудо, никакая самая слаженная система шестеренок, передач, рычагов и тросиков не обладает достаточным быстродействием, чтобы сыграть даже посредственную партию в шахматы – настолько сложна эта игра. Надежда на создание реальной шахматной машины появилась только после окончания Второй мировой войны, когда был разработан электронный компьютер. Пионеров машинных вычислений – таких как Алан Тьюринг, Джон фон Нейман, Клод Шеннон – шахматы интересовали как средство практической проверки своих идей в области искусственного интеллекта. В своей эпохальной статье 1950 года Шеннон пишет: “Хотя никакой практической ценности в этом и нет, вопрос все же представляет определенный теоретический интерес, и есть надежда, что… решение этой проблемы послужит толчком к решению других, более важных задач”. Два года спустя коллега Тьюринга Дитрих Принц написал для нового компьютера Ferranti Mark I в Манчестерском университете первую программу для игры в шахматы. Объем оперативной памяти и производительность машины позволяли ей решать лишь задачи категории “мат в два хода”, то есть она могла рассчитать лучший ход в ситуации, когда до мата оставалось не больше двух ходов. В 1956 году компьютер MANIAC I в Лос-Аламосской национальной лаборатории был запрограммирован на игру в облегченную версию шахмат – без слонов на доске размером 6 x 6 клеток. Всего было сыграно три “бесслоновых” партии: первую компьютер сыграл против самого себя, вторую против сильного шахматиста, исходно отказавшегося от ферзя, дав фору машине (та проиграла), и третью против новичка, только что выучившего правила. Эта заключительная партия, выигранная компьютером, пусть и у очень слабого соперника, знаменовала собой первую победу машины над человеком.

В 1958 году исследователь из IBM Алекс Бернстайн написал первую программу для игры в стандартные шахматы для IBM 704 – компьютера, на котором были разработаны языки программирования Fortran и Lisp и впервые синтезирована человеческая речь. Именно под впечатлением от демонстрации синтеза речи этой машиной Артур Кларк через несколько лет написал сцену для фильма “2001 год: Космическая одиссея”, показывающую, как постепенно угасает сознание компьютера HAL 9000, когда Дейв Боумен один за другим отключает его модули личности. В одной из предыдущих сцен фильма HAL легко выигрывает у астронавта Фрэнка Пула партию в шахматы. Режиссер Стэнли Кубрик сам был страстным шахматистом, поэтому неудивительно, что ходы HAL и Пула были взяты им из реальной партии между А. Рёшем и В. Шлаге, сыгранной в 1910 году в Гамбурге.

Проблема, стоящая перед любой машиной для состязания в шахматы – невероятная сложность игры, связанная с выработкой стратегии и многообразием возможных ходов. Существует в общей сложности около 1046 возможных позиций, а уникальных партий – не меньше 10120 (это число Шеннона, названное в честь американского математика Клода Шеннона, который описал его вычисление в опубликованной в 1950 году статье “Программирование компьютера для игры в шахматы”). В начале партии все довольно просто: у белых есть только двадцать возможных ходов – шестнадцать пешками (самых популярных всего три) и четыре конями (из них распространен всего один). Но по ходу игры, когда вовлеченными оказываются и другие фигуры – слоны, ладьи, ферзь и король, – количество возможных ходов очень быстро растет. После того как каждый из игроков сделал по одному ходу, на доске может возникнуть 400 различных позиций, после двух ходов – 72 084 позиции, после трех – более 9 миллионов, а после четвертого хода – более 288 миллиардов. Это примерно по одной игровой позиции на каждую из звезд нашей галактики. А общее количество возможных партий во много раз превышает число элементарных частиц во Вселенной.

На заре компьютерных шахмат созданию эффективных программ мешала относительно низкая производительность вычислительных машин. Но основной принцип программирования сильного компьютерного шахматиста был выработан уже в 1950-х годах венгерско-американским математиком Джоном фон Нейманом. Алгоритм “минимакс” был назван так потому, что его цель – свести к минимуму счет противника, максимизируя при этом свой собственный. К концу десятилетия этот алгоритм удалось усовершенствовать с помощью метода, получившего название “альфа-бета-отсечение”. Используя эвристические правила, выведенные на основе игровой стратегии лучших шахматистов мира, он при поиске оптимального хода заранее отсекает возможные неудачные ходы, чтобы компьютер не тратил зря время на проверку заведомо бесплодных ветвей своего дерева поиска. Это не то же самое, что компьютер, который учится на собственных ошибках, – такие появились позже, – а лишь попытка учесть в программе приемы и комбинации ходов, использовавшиеся гроссмейстерами в реальных играх.

С появлением в 1970-х и 1980-х годах более мощных компьютеров поиск оптимального хода стал более глубоким и рациональным. В 1978 году компьютер выиграл партию у международного мастера по шахматам. В том же десятилетии прошел первый чемпионат мира по шахматам среди компьютерных программ. Когда один из авторов этой книги (Дэвид) работал менеджером по прикладному программному обеспечению в компании Cray Research (производителе суперкомпьютеров в Миннеаполисе), ему довелось совместно с Робертом Хайаттом из Университета штата Алабама в Бирмингеме заниматься оптимизацией написанной Хайаттом шахматной программы Blitz для компьютера Cray-1 – самого быстродействующего на тот момент на планете. В 1981 году Cray Blitz стал первым компьютером, получившим мастерский рейтинг после победы в чемпионате штата Миссисипи со счетом 5:0, а в 1983-м он побил своего давнего конкурента, компьютер Belle компании Bell Labs, и стал чемпионом мира по шахматам среди компьютеров.

С того времени компьютерные шахматы сделали огромный шаг вперед. В 1997 году чемпион мира по шахматам Гарри Каспаров в матче из шести партий проиграл компьютеру Deep Blue компании IBM, а последний раз человек одержал победу над сильнейшим в мире компьютерным соперником в 2005 году. Лучшие компьютеры сейчас настолько опережают по рейтингу живых шахматистов, что можно уверенно утверждать: человеку больше никогда не обыграть ни одного из кремниевых гроссмейстеров. На момент написания этой книги наивысший шахматный рейтинг (основанный преимущественно на турнирных победах над достойными соперниками), когда-либо достигнутый углеродной формой жизни, составляет 2882 пункта. Этот рекорд, зафиксированный в мае 2014 года, принадлежит действующему чемпиону мира по шахматам норвежцу Магнусу Карлсену. На сегодняшний день его уже обошли не меньше пятидесяти компьютерных программ, в том числе Stockfish, имеющая самый высокий на планете рейтинг среди людей и машин – 3394 пункта.


Эта странная математика. На краю бесконечности и за ним

Шахматная доска дома у Агниджо. На доске – позиция, возникшая в ходе игры между компьютером Deep Blue (белые) и Гарри Каспаровым (черные) в 1996 году, когда компьютер впервые превзошел чемпиона мира по шахматам.


Но рейтинг рейтингом, и все же, несмотря на высочайшую квалификацию сегодняшних быстродействующих компьютеров, вопрос остается открытым: считать ли шахматы разрешимой игрой? Другими словами, возможно ли просчитать исход партии заранее, еще до ее начала? Есть множество игр попроще, где ответ на этот вопрос будет утвердительным. Одна из самых простых и популярных – крестики-нолики. Ее довольно легко проанализировать, ведь самая длинная партия продолжается не дольше девяти ходов и в большинстве случаев игрок вынужден занимать определенную клетку, чтобы не дать противнику победить. Если оба соперника знакомы с беспроигрышной стратегией, всегда все заканчивается вничью. Тот факт, что поле для крестиков-ноликов мало – всего 3 x 3 клетки, – облегчает задачу просчитывания. Впрочем, малый размер поля далеко не всегда означает, что игра проста. Многим из нас доводилось коротать время за игрой “точки и квадраты”: поле для нее представляет собой квадратную сетку с точками, а участники по очереди соединяют соседние точки отрезками. Если игрок выгораживает целую клетку, дорисовав ее четвертую сторону, клетка достается ему, он ставит в ней свой символ и получает еще один ход. Если при этом он образует еще один квадрат, то снова делает ход, и так далее. Минимальное поле для такой игры – 3 x 3. И хотя его размер такой же, как у крестиков-ноликов, стратегия здесь не в пример сложнее. Известно, что на поле 3 x 3 у второго игрока есть преимущество и он может побеждать всегда, однако мало кто знает выигрышную стратегию – а стратегия эта на удивление сложна. Большинство же из нас, по сути, полагаются на случай: мы просто стараемся сначала не отдавать противнику клетки, а потом сами стремимся занять как можно больше клеток с минимальными жертвами. А вот если поле значительно больше, чем 3 x 3, теоретики бессильны: в начале игры они не имеют ни малейшего представления о том, кто победит. Есть позиции (они довольно часто возникают в партиях между опытными соперниками) заведомо проигрышные для ходящего игрока – любой его ход гарантированно ведет к провалу. Непонятно лишь, как именно должен в такой ситуации действовать второй участник, чтобы победить, – хотя то, что победить он может, известно точно. Это пример того, что в математике называется “неконструктивным доказательством”: оно доказывает, что нечто (например, выигрышная стратегия) существует, а вот как конкретно это нечто получить, совершенно не подсказывает. Кажется нелогичным: как же так, наверняка знаем, что что-то существует, но привести пример не в силах? И тем не менее в подобных играх это случается часто. Такой вот парадокс: доказать, что в определенной ситуации игрок может победить, бывает проще простого, а вот показать, как именно достичь этой победы, невозможно.

В точках и квадратах, как и в крестиках-ноликах, на старте перед участниками открыты все ходы, а в процессе игры количество возможностей уменьшается. Шахматы – изначально гораздо более сложная игра, чем точки и квадраты, с огромным потенциалом для состязания между опытными соперниками и гроссмейстерами. Число возможных ходов в шахматах куда больше, их количество быстро растет, а партии могут продолжаться гораздо дольше. Предсказать, кто победит, в начале игры невозможно. Максимум, на что мы сегодня способны, – увидеть преимущество того или иного игрока в некоторых позициях эндшпиля, когда на доске остается совсем мало фигур. Просчитывание шахматной партии от начала до конца (то есть отыскание оптимальной стратегии, с помощью которой один из игроков всегда сможет одержать победу или хотя бы свести партию к ничьей) кажется несбыточной мечтой. И все же компьютеры невероятно преуспели в том, чтобы просчитывать игру на много ходов вперед и выбирать из миллиардов возможных вариантов перспективные последовательности ходов.

Пожалуй, еще удивительнее успехи, которых компьютерам удалось достичь в другой древней игре, стратегически еще более сложной, – го. Распространена она в основном в Китае, Японии и Южной Корее, а корни ее уходят глубже чем на две с половиной тысячи лет в прошлое – она считается самой старой из существующих сегодня настольных игр. В Древнем Китае игра в го входила в число четырех искусств, которыми должен был владеть благородный муж, наряду с живописью, каллиграфией и игрой на струнном музыкальном инструменте цине. На доске размером 19 x 19 соперники, играющие белыми и черными камнями, ходят по очереди, но, в отличие от шахмат, начинают черные. Делая ход, каждый из участников ставит на доску камень своего цвета, стараясь своими камнями окружить вражеские – тогда те считаются захваченными и удаляются с поля (название “го” происходит от китайского слова, означающего “игра в окружение”). Кроме этих основных правил есть и множество других, но главная особенность игры в том, что ее тактика и стратегия дьявольски сложны. Тактика – это то, что происходит в отдельно взятой части доски, где между группами камней разворачивается противоборство: выжить или погибнуть, спастись или сдаться в плен. А стратегия – это выстраивание игры с учетом общей ситуации на доске. Го превышает шахматы и по размеру поля, и по количеству возможных ходов в каждой позиции, да и партия обычно длится дольше. Метод перебора, дающий компьютерам преимущество в шахматах, к го неприменим, поскольку на просчитывание всех вариантов ушло бы слишком много времени. А в состязании с мастером го перебор просто бесполезен, ведь искусный игрок способен выбрать из множества ходов лучший, используя навыки высшего уровня, такие как распознавание образов – умение, которое приобретается с опытом и к которому человеческий мозг приспособлен гораздо лучше, чем компьютер. Распознать в расположении камней на доске определенный общий рисунок, который в различных ситуациях может выглядеть совершенно по-разному, – задача для компьютера куда более сложная, чем просто считать с молниеносной быстротой. Даже когда компьютеры стали обыгрывать сильнейших шахматистов, мастера го оставались уверенными, что в их игре компьютерам еще долго, очень долго не достичь даже скромного любительского уровня.


Эта странная математика. На краю бесконечности и за ним

Игра в го.


Но вот наступил 2016 год, и разработанная Google программа AlphaGo победила одного из лучших в мире игроков в го Ли Седоля со счетом 4:1. AlphaGo полагается не столько на просчитывание ходов и перебор возможных ситуаций, сколько на другие методы, больше свойственные человеку, чем машине. В ее основе – нейронная сеть, моделирующая работу органического мозга при решении проблемы. Изучив заложенную в нее огромную базу данных сыгранных мастерами партий, программа стала нескончаемо состязаться сама с собой, чтобы научиться узнавать выигрышные позиции и комбинации. Сочетание интеллектуального, эвристического подхода, свойственного человеку, с высокой скоростью, обеспечиваемой кремниевой начинкой, позволяет AlphaGo достичь того, что еще до недавнего времени считалось очень дальней перспективой, – уровня суперзвезды го мирового класса. В 2017 году AlphaGo улучшила собственный результат, одержав победу во всех трех партиях с лучшим игроком мира Кэ Цзе.

Мало кто сегодня сомневается, что уже скоро компьютерные мастера игры в го станут такими же непобедимыми соперниками для своих органических создателей, как и их шахматные собратья. Но мы так и не ответили на вопрос: разрешимы ли такие игры, как шахматы и го? В шахматах, поскольку белые ходят первыми, черные могут только реагировать на создаваемые ими угрозы. Поэтому, если когда-нибудь решение будет найдено – то есть будет вычислена оптимальная последовательность ходов белых в ответ на любые действия черных, – почти наверняка единственными возможными исходами игры будут победа белых или ничья. В го ситуация несколько сложнее, потому что по правилам в качестве компенсации за право черных ходить первыми белые получают определенное количество очков (6,5 по японским правилам, 7,5 по китайским). Возможно, этого достаточно для победы белых, но не исключено, что преимущество первого хода настолько перевешивает компенсацию, что выигрыш черным все равно обеспечен. Точно никто не знает – а может, никогда и не узнает.

Верным способом вычислить решение шахматной игры было бы нарисовать дерево со всеми возможными позициями-ветвями, затем, начиная с любой из них, дать оценку каждому из ответвлений, посмотрев, чем они кончаются, и выбрать то, которое ведет к оптимальному исходу. В теории все просто. Но поскольку общее количество возможных вариантов игр составляет приблизительно триллион триллионов триллионов триллионов триллионов триллионов триллионов триллионов триллионов триллионов, получившееся дерево будет иметь колоссальный размер. Создать компьютер, способный вместить такое количество данных, будет несколько проблематично, учитывая, что атомов во всей видимой Вселенной, вероятно, всего-то около 1080, то есть в 1040 раз меньше. На практике большую часть ветвей можно отсечь уже на начальном этапе, потому что многие из возможных позиций совершенно нелепы и в реальной партии никогда не возникнут, даже если играют новички. Но и после такой обрезки оставшееся дерево возможных реалистичных ходов будет чудовищно большим. А в случае с го его крона будет еще ветвистее. Из-за невероятной сложности подобных игр многие считают, что, хотя теоретически их и можно рассчитать, на практике это совершенно нереально. Если во всей Вселенной не хватит элементарных частиц, чтобы сохранить даже сильно обрезанное дерево ходов игры, как же ее просчитать? Возможно, на помощь придет более совершенный искусственный интеллект, который сумеет отсечь в дереве поиска еще больше ветвей и довести его крону до приемлемых размеров. Еще один вариант – квантовые компьютеры, способные вести поиск одновременно в огромном количестве ветвей. Впрочем, в отличие от случая с алгоритмом Шора для разложения на множители больших чисел, на сегодняшний день у нас не только нет алгоритма для решения задач такого типа, но мы даже не знаем, существует ли он вообще. Некоторую надежду вселяет тот факт, что для шашек решение все же было найдено. Это произошло в 2007 году и потребовало почти двадцати лет работы сотен компьютеров, которые все эти годы перебирали возможные комбинации ходов в игре. Как выяснилось, в шашках, если оба соперника играют без ошибок, партия всегда закончится ничьей. Удастся ли благодаря прогрессу технологий и программирования найти аналогичное решение для шахмат, а может быть, и для го? Время покажет.

Зато мы точно знаем, что игры типа шахмат и го, а также более простые, вроде крестиков-ноликов или точек и квадратов, – это “игры с совершенной информацией”: обдумывая ход, участник располагает всей информацией, необходимой, чтобы определить, какие ходы хорошие, а какие плохие. Никакой неопределенности, все на виду. А это значит, что в принципе, при наличии неограниченных ресурсов памяти и времени, такие игры можно просчитать. Но есть и другие игры, такие как покер, где не вся информация участникам доступна. Обдумывая свой ход, игрок в покер не знает, какие карты на руках у соперников – а ведь это решающий фактор, определяющий исход партии. Новичку, противостоящему в турнире профессионалу, конечно, может повезти – соберет роял-флеш да и выиграет партию. Но при длительной игре с большим количеством партий более опытный участник, знающий, когда делать ставку, а когда пасовать, в среднем выигрывает чаще и более крупные суммы, чем новичок.

Прежде чем говорить о просчитывании игр, подобных покеру, необходимо определиться, что же означает “просчитать”, когда речь идет об играх без “совершенной информации”. Ни один компьютер не может гарантировать стопроцентного выигрыша в покере (если не будет жульничать) – всегда ведь есть вероятность, что человеку придет роял-флеш. Поэтому “просчитыванием” в случае с покером будет выработка компьютером такой стратегии, при которой он в среднем окажется в выигрыше максимальное количество раз.

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

И все же для одной из разновидностей покера – техасского холдема для двух участников с лимитом – ученые уже разработали программу, которую невозможно победить в длинной серии игр. Ее появление в 2014 году стало важной вехой: впервые был найден алгоритм, способный просчитать сложную игру, в которой часть информации участникам недоступна. Эта скрытая информация и случайность розыгрыша карт не дают компьютеру выигрывать каждый раз. Но в серии из множества партий у человека практически нет шансов (так же как шахматисту, например, практически невозможно превзойти программу Stockfish) – так что эту версию игры мы вправе объявить просчитанной. Программа может не только помочь участникам усовершенствовать навыки игры; предполагается, что используемый в ней подход найдет применение в здравоохранении и системах безопасности.

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

В игре с совершенной информацией всегда есть какая-то “чистая” стратегия – некая последовательность ходов, которая приводит к наиболее благоприятному исходу. Скажем, в любой шахматной позиции существует лучший ход или, чаще, серия выигрышных ходов, и всякий раз, когда такая позиция возникает на доске, оптимальнее разыгрывать именно их. В случае с игрой “камень, ножницы, бумага” все с точностью до наоборот. Чистая стратегия здесь не работает: если, например, каждый раз показывать “камень” или в одной и той же последовательности “камень”, “ножницы” и бумагу”, вас в два счета обыграют. Лучше всего в подобных играх использовать так называемую смешанную стратегию, при которой в каждой из возникающих позиций с разной вероятностью предпринимаются различные действия. Просчитывание такой игры, как “камень, ножницы, бумага” или покер на двоих, заключается в нахождении оптимальной смешанной стратегии, гарантирующей наиболее высокую вероятность победы. Стратегия “всегда показывать «камень»” будет иметь вероятность выигрыша 100 %, если оппонент настолько несообразителен, что всегда будет разыгрывать “ножницы”. С другой стороны, если второй игрок быстро раскусит первого (а так, скорее всего, и будет) и станет все время показывать “бумагу”, то вероятность выигрыша с помощью “каменной” стратегии тут же упадет до нуля. Так что нет ничего удивительного в том, что игра “камень, ножницы, бумага” была просчитана, причем решение совершенно тривиально. Оптимальная стратегия: треть времени разыгрывать “камень”, треть – “бумагу” и треть – “ножницы”. Если считать ничью за полпобеды, вероятность выигрыша составляет как минимум 50 % – это лучшая из всех возможных стратегий. Есть, конечно, эксперты и более высокого уровня, но они полагаются не столько на теорию игры, сколько на психологию, извлекая выгоду из того факта, что человеку, как правило, плохо удаются по-настоящему случайные ходы, как мы уже видели в третьей главе. В целом, лучшая стратегия в играх с несовершенной информацией – смешанная.

В таких играх есть понятие, которое называют равновесием Нэша – в честь американского математика и экономиста Джона Нэша, внесшего важный вклад в развитие теории игр (ему даже была посвящена книга – а позже и фильм – “Игры разума”). Сильное равновесие Нэша означает, что у каждого участника есть своя стратегия, любое отклонение от которой (в случае если остальные этого не делают) ухудшает его шансы на победу. Есть также слабое равновесие Нэша, когда игрок может отклониться от выбранной стратегии и никак не изменить этим свои шансы, однако невозможно изменением стратегии улучшить свою позицию в игре. Равновесие Нэша – ключевое понятие в теории игр.

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

В игре с нулевой суммой один из участников выигрывает ровно столько, сколько проигрывает другой. Более общий случай – игра с постоянной суммой, в которой общий фонд не меняется. Один из примеров – шахматы. Участники могут сыграть вничью, заработав каждый по пол-очка, или один из них выиграет – и тогда победитель получает одно очко, а проигравший – ничего. А вот футбол, в отличие от шахмат, нельзя назвать игрой с постоянной суммой, поскольку в случае ничьей каждая из команд зарабатывает по очку, но если одна из них побеждает, то она получает три очка, а проигравшая – ноль. Сумма очков, таким образом, может быть 2 или 3. Все игры с постоянной суммой можно превратить в игры с нулевой суммой, добавляя или отнимая некоторое количество очков. Например, если бы у шахматных соперников удерживалось по пол-очка, то сумма игры была бы нулевой. По этой причине результаты, применимые к играм с нулевой суммой, обычно распространяются и на игры с постоянной суммой.

В играх с нулевой или постоянной суммой равновесия Нэша возникают только тогда, когда оба участника используют оптимальную стратегию. В играх же, не относящихся к этой категории, дело обстоит иначе: в них может быть множество других равновесий Нэша. В играх с непостоянной суммой на передний план выходит другой фактор – оптимальность по Парето. Оптимальным по Парето считается такое множество стратегий, в котором невозможно изменить их все в пользу одного из игроков, не ухудшив при этом положение кого-то из других участников. В игре с нулевой суммой любое множество стратегий оптимально по Парето. Но в общем случае это не так. Даже равновесие Нэша может не быть оптимальным по Парето, что демонстрирует нам проблема, известная как “дилемма заключенного”.

Двое заключенных по отдельности осуждены за преступление, предусматривающее тюремный срок в один год. Но кроме того, есть свидетельские показания, согласно которым оба причастны к более серьезному преступлению, грозящему сроком в шесть лет. Каждому из заключенных предоставляют выбор: молчать или тайно сдать подельника. Причем ни один из них не узнает о том, что сделал другой, пока не будет вынесен окончательный приговор. Если оба предадут друг друга, каждый получит по четыре года тюрьмы (по году за первое преступление и по три – за второе, более серьезное). Если только один из них предаст второго, он выйдет на свободу, а второй получит полные семь лет за оба преступления. Если все молчат, обоих приговаривают только на один год – за менее серьезное преступление. Удивительно, но получается, что, как бы ни поступил один, другому всегда выгоднее предать его, чем молчать. Единственно возможное равновесие Нэша в этом случае – взаимное предательство и по четыре года тюрьмы для каждого. Но такой вариант не оптимален по Парето, поскольку лучшим выходом для обоих было бы смолчать и отсидеть всего по году. Дилемму заключенного можно разыгрывать подряд сколько угодно, всякий раз вырабатывая стратегию на основе предыдущего опыта (этот вариант так и называется – повторяющаяся дилемма заключенного), тогда задача становится еще сложнее. Лучшие стратегии для повторяющегося варианта обычно предусматривают упорное молчание, при условии что вторая сторона поступает так же, и ответ предательством на предательство. Такие стратегии позволяют игрокам, с одной стороны, получить преимущество оптимальности по Парето в противостоянии друг другу, а с другой – избежать наихудшего исхода, делая выбор в пользу равновесия Нэша в тех случаях, когда ясно, что стратегия второго игрока – предательство.

Большинство людей предпочитает игры, которые продолжаются не слишком долго, скажем, час или два – пока участники не устали, не проголодались или не начали зевать от скуки. Международной шахматной федерацией для всех крупных турниров установлен лимит времени: 90 минут на первые 40 ходов плюс 30 минут на оставшуюся часть игры. А вот самая длинная из зафиксированных партий состоялась в 1989 году в Белграде между Иваном Николичем и Гораном Арсовичем: она продолжалась больше 20 часов и после 269 ходов закончилась ничьей по так называемому правилу 50 ходов. Оно гласит: партия может быть признана закончившейся вничью, если последние 50 ходов были сделаны игроками без перемещения пешек и без взятия фигур. Игрок, за которым очередь хода, вправе также потребовать объявления ничьей в том случае, если одна и та же позиция на доске повторилась три раза. При использовании правила 50 ходов самая протяженная партия может длиться чуть меньше 6000 ходов.

Гораздо дольше, вероятно в миллиарды раз дольше, чем будет светить Солнце, могла бы длиться игра на шахматной доске, бесконечно простирающейся во всех направлениях. В “бесконечных шахматах” те же правила и столько же фигур, что и в обычных, но поле для игры не имеет границ. Ходы на такой доске возможны весьма эффектные: представьте себе, как с расстояния в триллион клеток мчится на всех парусах черная ладья, а в ответ пронесшийся через межгалактическое пространство белый слон берет пешку. Нам, ограниченным своим крошечным мирком, такая игра покажется чересчур масштабной и несколько затянутой. И все же благодаря математике мы имеем возможность если не принять в ней участие, то как минимум что-то о ней узнать. А самое главное, мы можем абсолютно точно утверждать: что в обычных шахматах, что в бесконечных существует стратегия, гарантирующая выигрыш избравшему ее игроку. Что это за стратегия? Пока у нас в распоряжении не будет компьютера с неограниченным быстродействием и бесконечным объемом памяти, этого нам не узнать. Но само сознание того, что любую разновидность шахмат, да и любую другую игру с совершенной информацией – хоть конечную, хоть бесконечную – можно (пусть и теоретически) просчитать, приносит хоть какое-то удовлетворение.

В 1960-х годах, когда работа над искусственным интеллектом только начиналась, математики и специалисты по вычислительным системам, такие как Клод Шеннон, использовали шахматы для испытания методик, способных обучить компьютеры мыслить как человек. Сложные стратегические игры и сегодня служат этой цели. Сами по себе они не имеют особой ценности (если только не являются источником дохода). Но подходы, используемые при проектировании машин для игр, при их обучении и самообучении, можно перенести в другие области знания, действительно имеющие большое значение. Что еще важнее, попытки просчитать шахматы и аналогичные сложные игры помогают пролить свет на границы возможностей человеческого познания.


Глава 7. Тайны простых чисел | Эта странная математика. На краю бесконечности и за ним | Глава 9. Магия парадокса