Потом первый игрок снова ставит отметку X, отчего такую же получают помеченная клетка и все клетки справа и сверху от нее (если таковые есть), а второй игрок ставит очередную отметку O – на выбранную клетку и все клетки справа и сверху от нее (если таковые есть). Игра длится до тех пор, пока кому-либо из игроков не придется выбрать яд, тогда он проигрывает и умирает (конечно же метафорически).
С радостью приглашаю вас сыграть в эту игру на доске 7×4 (7 рядов и 4 колонки, или наоборот).
Если играть в эту игру на квадрате (с равным числом рядов и колонок), то есть стратегия, следуя которой игрок, делающий первый ход, всегда побеждает. Сможете ее найти? Возьмите три минуты на размышление.
Решение: Пусть в игру играют Джоан и Джилл. Если Джоан ходит первой, она должна придерживаться следующей стратегии – и непременно одержит победу. На первом ходу она должна выбрать клетку, расположенную справа по диагонали от клетки с пометкой «Яд».
Теперь все, что ей нужно делать, – это симметрично повторять ходы противника; иными словами, делать тот же ход, что и Джилл, только на противоположной стороне доски. Картинка, приведенная ниже, объяснит это лучше всяких слов.
То, как победить в этой игре, теперь должно быть совершенно ясно.
Все становится намного сложнее, если играть на прямоугольнике. Но и тогда можно доказать, что у игрока, делающего первый ход, есть выигрышная стратегия, проблема только в том, что доказательство не определяет ее точно. В математике такой вид доказательств называют «неконструктивным доказательством существования».
Одним из самых ценных навыков, которые я получил в средней школе в родном Вильнюсе, столице Литвы, было умение играть в стратегические игры на листочке бумаги, в классе, тайком от учителей. Мне очень нравилась «бесконечная» версия «крестиков-ноликов»: они часто помогали мне выжить на скучных уроках.
Думаю, большинству знакома классическая версия игры с полем 3×3. Шестилеток она приводит в восторг. Дети постарше и взрослые, как правило, сводят все поединки вничью, если только один из игроков не уснет на середине партии (это имеет смысл, игра все-таки скучная). Впрочем, в «бесконечной» версии игра проходит на поле с бесконечной решеткой, а цель – выстроить последовательность из пяти крестиков или ноликов, которая, как и в обычной игре, может быть горизонтальной, вертикальной и диагональной. Игроки по очереди ставят на клетки поля X или O (по предварительному соглашению), и первый, кому удастся сформировать «пятерку», побеждает.
На рисунке слева игрок, выбравший «крестики», уже победил.
На рисунке справа ход игрока, выбравшего «нолики», – но он ничем не может помешать противнику одержать победу. Видите почему?
В те далекие школьные дни я верил в то, что сам изобрел эту игру, но со временем, в должный час, понял, что я далек от правды. Оказалось, сходная игра под названием гомоку была на протяжении многих лет очень популярна в Японии и Вьетнаме. «Го» в переводе с японского означает «пять». Хотя в гомоку иногда играют на той же доске, что и в древнюю игру го, эти две игры не связаны. Го – старинная китайская игра, она даже упоминается в «Анналах» Конфуция, но на Западе с ней познакомились благодаря японцам, и потому она известна под японским названием.
Пусть я и обрел немалый опыт, играя в «бесконечную» версию «крестиков-ноликов» на нескончаемых уроках или переменах (на переменах веселья меньше, потому что играть разрешено), я все еще не уверен ни в том, есть ли в ней оптимальная стратегия для игрока, который начинает игру (игрок, выбравший «крестики»), ни в том, всегда ли игра заканчивается вничью (то есть не заканчивается никогда), если в нее играют двое сильных игроков. Впрочем, я готов даже заключить пари на то, что выигрышная стратегия существует. Когда я выйду на пенсию и у меня будет много свободного времени, я постараюсь найти ее для игрока, делающего первый ход.
И все-таки, если уж быть честным до конца, я должен сказать, что не играл в «крестики-нолики» уже несколько десятков лет и вспомнил о них, только когда писал эту книгу. А поскольку мои планы на то, чтобы вновь уделить внимание стратегическим аспектам этой игры, рассчитаны на очень долгий срок, прошу – будьте первыми, найдите эту стратегию и сберегите мне время и силы.
Представьте такую ситуацию. Мне дают два конверта с наличными и говорят, что в одном из них денег в два раза больше, чем в другом. Я могу выбрать себе любой, какой хочу, и забрать его.
Предположим, я выбираю конверт, открываю его и нахожу внутри $1000. Поначалу я очень доволен, но потом начинаю гадать: а что же было в другом конверте, который я не выбрал? Конечно, я не знаю. Там могло быть $2000, и тогда я выбрал плохо, или могло быть $500. Уверен, вы понимаете, в чем проблема. Я думаю, думаю, и тут: «Несчастный я человек! Ведь в том, другом конверте потенциальных денег в среднем больше, чем у меня в руках! В конце концов, там либо $2000, либо $500, шансы равны, в среднем это $1250, а это больше, чем $1000. Я свою математику знаю!»
По правде, что бы я ни обнаружил в своем конверте, подтвердится закон Мерфи: «Все, что может пойти не так, пойдет не так». Другой конверт в среднем всегда будет лучше моего. Если я найду в своем конверте $400, в другом будет либо $800, либо $200, а значит, среднее – $500. При таком образе мыслей я никогда не смогу выбрать верно. Выгода в оставшемся конверте всегда будет на 25 % больше моей. Так может, лучше переменить решение – если мне предложат такой вариант, прежде чем я смогу увидеть, что там, в другом конверте? Если я сделаю так, то начну «бесконечную петлю». Но почему такой простой выбор стал столь сложным?
История, которую я вам рассказал, – это знаменитый парадокс, и впервые его представил бельгийский математик Морис Крайчик (1882–1957). Впрочем, его история была о галстуках. Двое спорили о том, чей галстук лучше, и попросили третьего, ведущего галстучного эксперта Бельгии, выступить в роли судьи. Тот согласился, но при условии, что победитель отдаст свой галстук проигравшему в качестве утешительного приза. Владельцы недолго думая согласились, ведь каждый решил: «Не знаю, лучше ли мой галстук. Я могу его лишиться, но могу и приобрести лучший, так что эта игра мне на пользу, как и пари». Как мог каждый из соперников поверить в то, что преимущество на его стороне?
В 1953 г. Крайчик предложил иную версию истории, задействовав в ней двух других поссорившихся бельгийцев. Они галстуков уже не носили, потому что были так набиты бельгийским шоколадом, что едва могли дышать. Вместо этого они спорили о том, сколько денег у другого в кошельке, и решили, что тот, кто окажется богаче и счастливее, отдаст свой бумажник бедному противнику. А если все закончится ничьей, оба вернутся к своим шоколадкам.
Опять же, каждому казалось, что преимущество на его стороне. Если случится потерпеть поражение – что же, отдавать все равно придется меньше, чем может принести победа. Что же это – великая игра или нечто иное? Попытайтесь сыграть в нее на улице со случайными прохожими и посмотрите, что будет. В 1982 г. Мартин Гарднер сделал эту историю популярной в своей книге «А ну-ка, догадайся» [9][10] – одной из самых лучших, самых простых и самых увлекательных из всех самых лучших, самых простых и самых увлекательных книг, когда-либо написанных о проницательности и смекалке.
Барри Нейлбаф (профессор менеджмента на кафедре Милтона Стейнбаха в Йельской школе менеджмента), ведущий специалист по теории игр, в своей статье, опубликованной в 1989 г., предложил версию этой истории с конвертом. Возможно, вы удивитесь, но даже сегодня у этой игры нет решения, с которым были бы единодушно согласны все статистики.
Одно из предлагаемых решений подразумевает, что мы противопоставляем среднее геометрическое и среднее арифметическое. Среднее геометрическое – это квадратный корень из произведения двух чисел. Например, среднее геометрическое 4 и 9 равняется квадратному корню из их произведения (результата перемножения обоих чисел) – а именно 6. Итак, если мы нашли в своем конверте
Студенты, изучающие теорию вероятностей, сказали бы: «Вам не найти равномерное распределение для множества рациональных чисел». Впечатляет?
Если вы не понимаете, что это значит, превосходно! Лучшая версия этого парадокса не имеет никакого отношения к вероятностям. Она появляется в книге «Сатана, Кантор и бесконечность», прекрасном произведении (с прекрасным названием, правда?) Рэймонда Смаллиана, американского математика, философа, классика-пианиста и фокусника[11]. Смаллиан представляет две версии парадокса:
1. Если в вашем конверте
2. Если конверты содержат соответственно
Вы в растерянности? Я тоже.
В любом случае многие пессимистично заявляют, что здесь нет никакого парадокса, просто такова жизнь, и не имеет значения, что вы сделаете или куда пойдете: лучше всегда будет там, где нас нет. Например, если вы в браке – возможно, вам следовало никогда в него не вступать. В конце концов, как писал Чехов: «Если боитесь одиночества, то не женитесь». И все же, если решите остаться в одиночестве, вы снова неправы. В Библии слова «не хорошо» впервые встречаются в Книге Бытия: «…не хорошо быть человеку одному…» (2: 18). Это не я сказал, а Господь Бог.
«Золотые шары» (Golden Balls) – британское телевизионное шоу, выходившее в эфир с 2007 по 2009 г. Не будем вдаваться в детали правил и ходов, но на последней стадии игры двое оставшихся игроков должны договориться о том, как разделить между собой определенную сумму денег. У каждого игрока – два шара с наклейками: на одном написано SPLIT («Дележ»), на другом – STEAL («Кража»). Если оба решают выбрать «Дележ», деньги делят поровну; если оба выбирают «Кражу», то остаются ни с чем; а если их выбор не совпадает, тогда приз забирает тот, кто выбрал «Кражу». Сперва игроки могут обсудить то, как им поступить, – и только потом делать выбор.
C первого же взгляда на таблицу, основанную на правилах игры, совершенно ясно одно: если каждый думает лишь о своей выгоде, то «Кража» лучше, чем «Дележ». Но есть проблема: если каждый из игроков думает только о себе, проигрывают оба. (Да, это в какой-то мере похоже на «Дилемму заключенного», о которой вы, возможно, уже знаете. Эту знаменитую дилемму мы обсудим позже.)
В большинстве случаев игроки пытаются убедить друг друга выбрать «Дележ», и иногда это срабатывает. На YouTube немало записей игры с душераздирающими сценами, когда игроки, доверявшие противнику, выбирали «Дележ» – лишь для того, чтобы жестоко обмануться.
Однажды игрок по имени Ник применил неожиданный подход. Он сказал своему сопернику Ибрагиму, что выберет «Кражу», и умолял того решиться на «Дележ», обещая разделить деньги (в этом случае приз £13 600) между ними после того, как игра окончится. Ибрагим не мог поверить своим ушам: Ник снова и снова обещал сжульничать! Но почему тогда он говорил об этом заблаговременно? Да потому, говорил Ник, что я принципиально честен! «Будет тебе твоя половина, Ибрагим! Выбери “Дележ”, а то проиграешь! – говорил Ник. – Тебе все только на пользу!» В этот момент игроков попросили прекратить диалог и взять шар.
Ибрагим выбрал «Дележ» – но то же самое сделал и Ник! Почему? Просто он был на все сто уверен, что убедил Ибрагима! Так к чему лишние проблемы? Зачем делить деньги после игры? Делим прямо сейчас!
Остается лишь признать, что Ник, вероятно, был достоин звания «Стратег года».
Эта игра посвящена не только стратегиям переговоров, но и доверию между игроками.
(Все, что написано ниже, предназначено только для любителей шахмат и математики.)
Многие считают, что теория игр появилась в 1944 г., с выходом в свет каноничной книги «Теория игр и экономическое поведение», авторами которой стали великий математик Джон фон Нейман (1903–1957) и экономист Оскар Моргенштерн (1902–1977). (Впрочем, проблемы, к которым обращается теория игр, в той или иной мере существовали с начала времен. Первые примеры можно обнаружить в Талмуде, в трактате Сунь Цзы «Искусство войны» и в произведениях Платона.)
Но все же некоторые склонны полагать, что теория игр – как дисциплина – зародилась в 1913 г., когда немецкий математик Эрнст Цермело (1871–1953) представил свою теорему о шахматах, «игре королей»: «Либо белые могут форсировать выигрыш, либо черные могут форсировать выигрыш, либо обе стороны могут по крайней мере форсировать ничью». Другими словами, он утверждал, что существует всего три варианта:
1. У белых есть стратегия, следование которой всегда ведет к победе.
2. У черных есть стратегия, следование которой всегда ведет к победе.
3. И у белых, и у черных есть сочетание стратегий, следование которым всегда ведет к ничьей.
Помню, когда я впервые прочел эту теорему, то подумал (со своим обычным сарказмом): «Ух ты! Как умно… и как ново… Немецкий знаток говорит мне, что победят либо белые, либо черные, либо все кончится ничьей. А я-то думал, тут столько вариантов…» И только вчитавшись в строки доказательства, я понял, в чем именно состоит теорема.
По сути, Цермело доказал, что игра в шахматы неотличима от имеющей предел (3×3) игры в «крестики-нолики». Мы уже упоминали: если в партии в «крестики-нолики» оба игрока не сошли на время с ума (да, иногда такое бывает), все игры всегда закончатся вничью. Иного варианта нет. Даже те, кто раз за разом проигрывает в «крестики-нолики», в конце концов сумеют понять, как не проигрывать никогда, и это превратит игру, и так не особо захватывающую, в нечто столь же скучное, как чтение книги с белыми страницами без текста.
Цермело сумел доказать, что шахматы (и многие другие игры) представляют собой практически те же «крестики-нолики» и отличие – не в качестве, а в количестве.
В шахматах «стратегия» – это набор ответов на любое положение, какое только может возникнуть на доске. Ясно, что у двух игроков может быть огромное множество стратегий. Отметим стратегии белых (первого игрока) буквой S, а стратегии его противника – буквой Т. Как мы уже сказали, теорема Цермело говорит о существовании лишь трех вариантов:
либо у белых есть стратегия (назовем ее S4), при которой они побеждают всегда, независимо от действий черных…
(W = победа белых; B = победа черных; X = ничья)
либо у черных есть стратегия (назовем ее T3), при которой они побеждают всегда, независимо от действий белых…
либо у обоих игроков есть сочетание стратегий, которые при следовании им неизменно приведут к ничьей [12] (как при игре в «крестики-нолики»):
Если все именно так, зачем же люди тогда играют в шахматы? И более того, почему это интересно? Истина вот в чем: когда мы играем партию или наблюдаем за ней, мы не знаем, с каким из трех случаев столкнулись. Возможно, в будущем суперкомпьютеры и смогут найти верные стратегии, но мы еще и близко не подошли к этой стадии, и именно поэтому игра по-прежнему столь увлекает. По словам американского математика и криптографа Клода Шеннона (отца «теории информации»), в шахматах существует более 1043 возможных позиций, не противоречащих правилам. Взгляните на это число:
10 000 000 000 000 000 000 000 000 000 000 000 000 000 000.
Ого! Многие думают, что временные рамки, необходимые компьютеру для проверки всех вариантов в шахматах, выходят за пределы возможностей самых современных технологий.
Как-то за ланчем мы разговорились с Борисом Гельфандом, финалистом чемпионата мира по шахматам 2012 г. И я сказал, что сам играю не то чтобы очень, но при этом не так давно мог обыграть любую программу – а сейчас компьютеры выигрывают у меня так быстро, что даже стыдно. И он ответил, что пропасть между игроками-людьми и компьютерами с каждым днем становится все больше и дела складываются не в нашу пользу. Сегодня, добавил он, компьютерные программы легко могут превзойти сильнейших игроков, и разрыв столь велик, что матчи формата «человек против машины» уже не представляют никакого интереса. В шахматах люди потерпели жестокое поражение. В наши дни, заключил гроссмейстер Гельфанд, играть с мощными компьютерными программами (известными как «движки») – это примерно как бороться против медведя гризли… просто поверьте, не стоит вам этого делать.
Игры в формате «люди против людей» намного интереснее.
В наше время, когда в шахматы играют гроссмейстеры, иногда выигрывает тот, кто делает первый ход, иногда – тот, кто отвечает на этот ход, а бывает и так, что игра заканчивается вничью. Игроки и теоретики, как правило, согласны в том, что у белых, делающих первый ход, есть небольшое преимущество. Статистики поддерживают этот взгляд: белые последовательно выигрывают чуть чаще черных, примерно в 55 % всех матчей.
Игроки уже долго спорят о том, чем обернется исход идеальной игры – неизменной победой белых или ничьей. Они не верят в то, что существует выигрышная стратегия за черных (впрочем, несмотря на это широко распространенное мнение, венгерский гроссмейстер Андраш Адорьян, напротив, полагает, что идея о начальном преимуществе белых всего лишь заблуждение).
Я уже оставил шахматы и так и не достиг в них успеха, но если мне будет позволено высказать свою догадку, то она такова: когда оба игрока делают верные ходы, партия всегда окончится ничьей (как при игре в «крестики-нолики»). В будущем компьютеры смогут проверить все уместные варианты и решить, прав ли я в своем предположении.
Довольно интересно, что ученые все еще не могут прийти к согласию в том, каково истинное значение теоремы Цермело. Изначально она была написана на немецком языке, а если вы читали научные или философские тексты на немецком (прекрасный пример – труды Гегеля), то вряд ли удивитесь и тому, что смысл теоремы туманен (о, как же нам повезло, что сейчас язык науки – английский!).
Свет! Камера! Мотор! Кейнсианский конкурс красоты
Представьте, что редакция газеты проводит конкурс, в котором участникам предъявляют двадцать фотографий и просят выбрать самое привлекательное лицо. Те, чей «избранник» наберет большинство голосов, получат право на приз – пожизненную подписку на газету, кофемашину и почетный значок.
Как играть в такую игру? Предположим, мне больше всех понравилось фото № 2. Следует ли отдать за него свой голос? Да – если я хочу, чтобы о моем мнении узнали. И нет – если я хочу подписку, кофемашину и значок.
Великий английский экономист Джон Мейнард Кейнс (1883–1946) описал версию такого конкурса в 12-й главе своей книги «Общая теория занятости, процента и денег» (1936). По мысли Кейнса, если мы хотим выиграть приз, нужно догадаться, какую фотографию одобрит большинство читателей. Это степень бакалавра софистики. Но, если мы еще более искушены, нам следует перейти сразу к степени магистра – и попытаться догадаться, какие снимки, по мнению других участников, будут наиболее привлекательными
Конечно же Кейнс говорил не о фотографиях, а об игре на фондовой бирже, где, как он считал, все поступали примерно так же. В конце концов, если мы намерены купить акции потому, что считаем, будто они хороши, – это подход далеко не лучший. Мудрее держать деньги под матрасом или на сберегательном счете. Цена акций поднимается не тогда, когда они хороши, а когда многие верят в то, что они хороши, – или когда многие, по мнению многих, верят в то, что эти акции хороши.
Хороший пример – цена акций Amazon. В 2001 г. они стоили дороже, чем акции всех остальных книготорговых фирм Америки, – причем Amazon к тому времени не заработала еще ни доллара. Но почему так было? Просто многие, по мнению многих, верили в то, что компания Amazon будет компанией Amazon.
Приведенная ниже игра – хороший пример идеи Кейнса. Ален Леду многое сделал для того, чтобы популярность обрела именно эта версия, которую он опубликовал во французском журнале Jeux et Stratégie [13] в 1981 г.
В комнате группа людей. Каждого просят загадать число от 0 до 100. После этого устроитель игры находит среднее арифметическое выбранных чисел и умножает его на 0,6. Итог умножения становится целевым числом. И игрок, загадавший число, самое близкое к этому итогу, выигрывает «мерседес» (они тогда продавались с неплохой скидкой).
Какое число выберете? Подумайте немного.
Есть два способа выбора: нормативный и позитивный.