Хаим ШапираГладиаторы, пираты иигры на доверии. Какнами правят теория игр
 Скачать 1.08 Mb.
|
|
Игра 3. Яд и шоколад Это довольно простая игра, более известная как «Хрум!» (Chomp!). За ее формулировку с плитками шоколада, которую использую ямы в долгу перед ныне покойным американским математиком Дэвидом Гейлом. В нее играют на шахматной доске, каждая клеточка которой сделана из шоколада, но при этом крайняя левая клетка содержит смертельный яд. Вот правила. Игрок, делающий первый ход, ставит отметку X на одной из клеток, выбирая ее по желанию. После этого все клетки, расположенные и справа, и сверху от клетки с отметкой X, получают такую же отметку Теперь очередь второго игрока. Он отмечает какую-либо из клеток, оставшихся свободными, как О. Как только это произойдет, все пустые клетки справа и сверху от нее тоже получают такую отметку. Потом первый игрок снова ставит отметку X, отчего такую же получают помеченная клетка и все клетки справа и сверху от нее (если таковые есть, а второй игрок ставит очередную отметку O – на выбранную клетку и все клетки справа и сверху от нее (если таковые есть. Игра длится до тех пор, пока кому-либо из игроков не придется выбрать яд, тогда он проигрывает и умирает (конечно же метафорически). С радостью приглашаю вас сыграть в эту игруна доске 7×4 (7 рядов и 4 колонки, или наоборот). Если играть в эту игруна квадрате (с равным числом рядов и колонок, то есть стратегия, следуя которой игрок, делающий первый ход, всегда побеждает. Сможете ее найти? Возьмите три минуты на размышление. Решение: Пусть в игру играют Джоан и Джилл. Если Джо- ан ходит первой, она должна придерживаться следующей стратегии – и непременно одержит победу. На первом ходу она должна выбрать клетку, расположенную справа по диагонали от клетки с пометкой «Яд». Теперь все, что ей нужно делать, – это симметрично повторять ходы противника иными словами, делать тот же ход, что и Джилл, только на противоположной стороне доски. Картинка, приведенная ниже, объяснит это лучше всяких слов То, как победить в этой игре, теперь должно быть совершенно ясно. Все становится намного сложнее, если играть на прямоугольнике. Но и тогда можно доказать, что у игрока, делающего первый ход, есть выигрышная стратегия, проблема только в том, что доказательство не определяет ее точно. В математике такой вид доказательств называют неконструктивным доказательством существования». Игра 4. Старики не играют! Одним из самых ценных навыков, которые я получил в средней школе в родном Вильнюсе, столице Литвы, было умение играть в стратегические игры на листочке бумаги, в классе, тайком от учителей. Мне очень нравилась бесконечная версия «крестиков-ноликов»: они часто помогали мне выжить на скучных уроках. Думаю, большинству знакома классическая версия игры с полем 3×3. Шестилеток она приводит в восторг. Дети постарше и взрослые, как правило, сводят все поединки вничью, если только один из игроков не уснет на середине партии (это имеет смысл, игра все-таки скучная. Впрочем, в «бесконечной» версии игра проходит на поле с бесконечной решеткой, а цель – выстроить последовательность из пяти крестиков или ноликов, которая, как ив обычной игре, может быть горизонтальной, вертикальной и диагональной. Игроки по очереди ставят на клетки поля X или O (по предварительному соглашению, и первый, кому удастся сформировать пятерку, побеждает На рисунке слева игрок, выбравший крестики, уже по- бедил. На рисунке справа ход игрока, выбравшего нолики, – но он ничем не может помешать противнику одержать победу. Видите почему? В те далекие школьные дни я верил в то, что сам изобрел эту игру, но со временем, в должный час, понял, что я далек от правды. Оказалось, сходная игра под названием гомоку была на протяжении многих лет очень популярна в Японии и Вьетнаме. Го в переводе с японского означает «пять». Хотя в гомоку иногда играют на той же доске, что ив древнюю игру го, эти две игры не связаны. Го – старинная китайская игра, она даже упоминается в Анналах Конфуция, нона Западе с ней познакомились благодаря японцами потому она известна под японским названием. Пусть я и обрел немалый опыт, играя в «бесконечную» версию «крестиков-ноликов» на нескончаемых уроках или переменах (на переменах веселья меньше, потому что играть разрешено, я все еще не уверен нив том, есть ливней оптимальная стратегия для игрока, который начинает игру (игрок, выбравший крестики, нив том, всегда ли игра заканчивается вничью (то есть не заканчивается никогда, если в нее играют двое сильных игроков. Впрочем, я готов даже заключить пари на то, что выигрышная стратегия существует. Когда я выйду на пенсию и у меня будет много свободного времени, я постараюсь найти ее для игрока, делающего первый ход. И все-таки, если уж быть честным до конца, я должен сказать, что не играл в «крестики-нолики» уже несколько десятков лети вспомнило них, только когда писал эту книгу. А поскольку мои планы на то, чтобы вновь уделить внимание стратегическим аспектам этой игры, рассчитаны на очень долгий срок, прошу – будьте первыми, найдите эту стратегию и сберегите мне время и силы. Игра 5. У соседа конверт зеленее Представьте такую ситуацию. Мне дают два конверта сна- личными и говорят, что водном из них денег в два раза больше, чем в другом. Я могу выбрать себе любой, какой хочу, и забрать его. Предположим, я выбираю конверт, открываю его и нахожу внутри $1000. Поначалу я очень доволен, но потом начинаю гадать а что же было в другом конверте, который я не выбрал Конечно, я не знаю. Там могло быть $2000, и тогда я выбрал плохо, или могло быть $500. Уверен, вы понимаете, в чем проблема. Я думаю, думаю, и тут Несчастный я человек Ведь в том, другом конверте потенциальных денег в среднем больше, чему меня в руках В конце концов, там либо $2000, либо $500, шансы равны, в среднем это а это больше, чем $1000. Я свою математику знаю!» По правде, чтобы я ни обнаружил в своем конверте, подтвердится закон Мерфи: Все, что может пойти не так, пойдет не так. Другой конверт в среднем всегда будет лучше моего. Если я найду в своем конверте $400, в другом будет либо $800, либо $200, а значит, среднее – $500. При таком образе мыслей я никогда не смогу выбрать верно. Выгода в оставшемся конверте всегда будет на 25 % больше моей. Так может, лучше переменить решение – если мне предложат такой вариант, прежде чем я смогу увидеть, что там, в другом конверте Если я сделаю так, то начну бесконечную петлю». Но почему такой простой выбор стал столь сложным? История, которую я вам рассказал, – это знаменитый парадокс, и впервые его представил бельгийский математик Мо- рис Крайчик (1882–1957). Впрочем, его история была о галстуках. Двое спорили о том, чей галстук лучше, и попросили третьего, ведущего галстучного эксперта Бельгии, выступить в роли судьи. Тот согласился, но при условии, что победитель отдаст свой галстук проигравшему в качестве утешительного приза. Владельцы недолго думая согласились, ведь каждый решил Не знаю, лучше ли мой галстук. Я могу его лишиться, но могу и приобрести лучший, так что эта игра мне на пользу, как и пари. Как мог каждый из соперников поверить в то, что преимущество на его стороне? В 1953 г. Крайчик предложил иную версию истории, задействовав в ней двух других поссорившихся бельгийцев. Они галстуков уже не носили, потому что были так набиты бельгийским шоколадом, что едва могли дышать. Вместо этого они спорили о том, сколько денег у другого в кошельке, и решили, что тот, кто окажется богаче и счастливее, отдаст свой бумажник бедному противнику. А если все закончится ничьей, оба вернутся к своим шоколадкам. Опять же, каждому казалось, что преимущество на его стороне. Если случится потерпеть поражение – что же, отдавать все равно придется меньше, чем может принести победа. Что же это – великая игра или нечто иное Попытайтесь сыграть в нее на улице со случайными прохожими и посмотрите, что будет. В 1982 г. Мартин Гарднер сделал эту историю популярной в своей книге А ну-ка, догадайся 910 – одной из самых лучших, самых простых и самых увлекательных из всех самых лучших, самых простых и самых увлекательных книг, когда-либо написанных о проницательности и смекалке. Барри Нейлбаф (профессор менеджмента на кафедре Ми- лтона Стейнбаха в Йельской школе менеджмента, ведущий специалист по теории игр, в своей статье, опубликованной в г, предложил версию этой истории с конвертом. Возможно, вы удивитесь, но даже сегодня у этой игры нет решения, с которым были бы единодушно согласны все статистики Выходила на русском языке в изд-ве Мир в 1984 г. – Примеч. ред С размышлениями Мартина Гарднера об игре 5 можно ознакомиться по книге Одно из предлагаемых решений подразумевает, что мы противопоставляем среднее геометрическое и среднее арифметическое. Среднее геометрическое – это квадратный корень из произведения двух чисел. Например, среднее геометрическое и 9 равняется квадратному корню из их произведения (результата перемножения обоих чисел) – а именно. Итак, если мы нашли в своем конверте X долларов и знаем, что другой содержал 2X или ½X, то среднее геометрическое другого конверта будет равняться X – ив точности соответствовать тому, что попало к нам в руки. Логика применения среднего геометрического опирается на тот факт, что мы говорим не о сложении, а об умножении (вдвое больше. Если бы мы сказали, что водном конверте на $10 больше, чем в другом, то использовали бы среднее арифметическое, нашли бы его, и никакого парадокса бы не возникло, ведь в нашем конверте содержится X, а в другом – X+10 или, и среднее количество денег в конверте, который мы не выбрали, равняется Студенты, изучающие теорию вероятностей, сказали бы: «Вам не найти равномерное распределение для множества рациональных чисел. Впечатляет? Если вы не понимаете, что это значит, превосходно Лучшая версия этого парадокса не имеет никакого отношения к вероятностям. Она появляется в книге Сатана, Кантор и бесконечность, прекрасном произведении (с прекрасным названием, правда) Рэймонда Смаллиана, американского математика, философа, классика-пианиста и фокусника 11 Смаллиан представляет две версии парадокса. Если в вашем конверте B банкнот, то вы либо получите либо потеряете ½B, заменив этот конверт другим. Следовательно, вам следует их поменять. Если конверты содержат соответственно Си С, а вы решаете заменить один на другой, то вы либо получите С, либо потеряете С так что шансы равны ивы можете получить столько же, сколько рискуете потерять. Вы в растерянности Я тоже. В любом случае многие пессимистично заявляют, что здесь нет никакого парадокса, просто такова жизнь, и не имеет значения, что вы сделаете или куда пойдете лучше всегда будет там, где нас нет. Например, если вы в браке – возможно, вам следовало никогда в него не вступать. В конце концов, как писал Чехов Если боитесь одиночества, тоне женитесь. И все же, если решите остаться в одиночестве, вы снова неправы. В Библии слова нехорошо впервые встречаются в Книге Бытия нехорошо быть человеку одному. Это не я сказала Господь Бог Smullyan Raymond M. Satan, Cantor, and Infinity: And Other Mind-Boggling Puzzles. Alfred A. Knopf, New York, 1992; Dover Publications, 2009. Игра 6. Золотые шары «Золотые шары (Golden Balls) – британское телевизионное шоу, выходившее в эфир с 2007 по 2009 г. Не будем вдаваться в детали правили ходов, нона последней стадии игры двое оставшихся игроков должны договориться о том, как разделить между собой определенную сумму денег. У каждого игрока – два шара с наклейками на одном написано (Дележ, на другом – STEAL (Кража. Если оба решают выбрать Дележ, деньги делят поровну если оба выбирают Кражу, то остаются ни с чем а если их выбор не совпадает, тогда приз забирает тот, кто выбрал Кражу. Сперва игроки могут обсудить то, каким поступить, и только потом делать выбор первого же взгляда на таблицу, основанную на правилах игры, совершенно ясно одно если каждый думает лишь о своей выгоде, то Кража лучше, чем Дележ. Но есть проблема если каждый из игроков думает только о себе, проигрывают оба. (Да, это в какой-то мере похоже на Дилемму заключенного, о которой вы, возможно, уже знаете. Эту знаменитую дилемму мы обсудим позже.) В большинстве случаев игроки пытаются убедить друг друга выбрать Дележи иногда это срабатывает. На немало записей игры с душераздирающими сценами, когда игроки, доверявшие противнику, выбирали Дележ лишь для того, чтобы жестоко обмануться. Однажды игрок по имени Ник применил неожиданный подход. Он сказал своему сопернику Ибрагиму, что выберет «Кражу», и умолял того решиться на Дележ, обещая разделить деньги (в этом случае приз £13 600) между ними после того, как игра окончится. Ибрагим не мог поверить своим ушам Ник снова и снова обещал сжульничать Но почему тогда он говорил об этом заблаговременно Да потому, говорил Ник, что я принципиально честен Будет тебе твоя половина, Ибрагим! Выбери Дележа то проиграешь – говорил Ник. – Тебе все только на пользу В этот момент игроков попросили прекратить диалоги взять шар. Ибрагим выбрал Дележ – но тоже самое сделали Ник! Почему? Просто он был на все сто уверен, что убедил Ибра- гима! Так к чему лишние проблемы Зачем делить деньги после игры Делим прямо сейчас! Остается лишь признать, что Ник, вероятно, был достоин звания Стратег года». Эта игра посвящена не только стратегиям переговоров, но и доверию между игроками. Игра 7. Шахматные лабиринты (Все, что написано ниже, предназначено только для любителей шахмат и математики.) Многие считают, что теория игр появилась в 1944 гс выходом в свет каноничной книги Теория игр и экономическое поведение, авторами которой стали великий математик Джон фон Нейман (1903–1957) и экономист Оскар Мор- генштерн (1902–1977). (Впрочем, проблемы, к которым обращается теория игр, в той или иной мере существовали сначала времен. Первые примеры можно обнаружить в Талмуде, в трактате Сунь Цзы Искусство войны ив произведениях Платона.) Но все же некоторые склонны полагать, что теория игр как дисциплина – зародилась в 1913 г, когда немецкий математик Эрнст Цермело (1871–1953) представил свою теорему о шахматах, игре королей Либо белые могут форсировать выигрыш, либо черные могут форсировать выигрыш, либо обе стороны могут по крайней мере форсировать ничью. Другими словами, он утверждал, что существует всего три варианта. У белых есть стратегия, следование которой всегда ведет к победе 2. У черных есть стратегия, следование которой всегда ведет к победе. И у белых, и у черных есть сочетание стратегий, следование которым всегда ведет к ничьей. Помню, когда я впервые прочел эту теорему, то подумал (со своим обычным сарказмом Ухты Как умно и как ново Немецкий знаток говорит мне, что победят либо белые, либо черные, либо все кончится ничьей. А я-то думал, тут столько вариантов И только вчитавшись в строки доказательства, я понял, в чем именно состоит теорема. По сути, Цермело доказал, что игра в шахматы неотличима от имеющей предел (3×3) игры в «крестики-нолики». Мы уже упоминали если в партии в «крестики-нолики» оба игрока не сошли на время сума (да, иногда такое бывает), все игры всегда закончатся вничью. Иного варианта нет. Даже те, кто раз за разом проигрывает в «крестики-нолики», в конце концов сумеют понять, как не проигрывать никогда, и это превратит игру, итак не особо захватывающую, в нечто столь же скучное, как чтение книги с белыми страницами без текста. Цермело сумел доказать, что шахматы (и многие другие игры) представляют собой практически те же «крестики-но- лики и отличие – не в качестве, а в количестве. В шахматах стратегия – это набор ответов на любое положение, какое только может возникнуть на доске. Ясно, что у двух игроков может быть огромное множество стратегий. Отметим стратегии белых (первого игрока) буквой S, астра- тегии его противника – буквой Т. Как мы уже сказали, теорема Цермело говорит о существовании лишь трех вариантов: либо у белых есть стратегия (назовем ее S4), при которой они побеждают всегда, независимо от действий черных = победа белых B = победа черных X = ничья) либо у черных есть стратегия (назовем ее T3), при которой они побеждают всегда, независимо от действий белых… либо у обоих игроков есть сочетание стратегий, которые при следовании им неизменно приведут к ничьей 12 (как при игре в «крестики-нолики»): Если все именно так, зачем же люди тогда играют вшах- маты И более того, почему это интересно Истина вот в чем: когда мы играем партию или наблюдаем за ней, мы не знаем, с каким из трех случаев столкнулись. Возможно, в будущем суперкомпьютеры и смогут найти верные стратегии, номы еще и близко не подошли к этой стадии, и именно поэтому игра по-прежнему столь увлекает. По словам американского математика и криптографа Клода Шеннона (отца теории информации, в шахматах существует более 10 43 возможных позиций, не противоречащих правилам. Взгляните на это число Факт кажется очевидным, нона деле возникают вопросы, например, о том, существуют ли циклы из стратегий, побеждающих друг друга, когда стратегия белых Б обыгрывает стратегию черных Ч, в свою очередь Ч обыгрывает Б2, та обыгрывает Ч, а она в свой черед побеждает Б. Также важен тот факт, что игра является конечной. – Примеч. ред 10 000 000 000 000 000 000 000 000 000 000 000 000 000 Ого Многие думают, что временные рамки, необходимые компьютеру для проверки всех вариантов в шахматах, выходят за пределы возможностей самых современных техноло- гий. Как-то за ланчем мы разговорились с Борисом Гель- фандом, финалистом чемпионата мира по шахматам 2012 г. И я сказал, что сам играю не то чтобы очень, но при этом не так давно мог обыграть любую программу – а сейчас компьютеры выигрывают у меня так быстро, что даже стыдно. И он ответил, что пропасть между игроками-людьми и компьютерами с каждым днем становится все больше и дела складываются не в нашу пользу. Сегодня, добавил он, компьютерные программы легко могут превзойти сильнейших игроков, и разрыв столь велик, что матчи формата человек против машины уже не представляют никакого интереса. В шахматах люди потерпели жестокое поражение. В наши дни, заключил гроссмейстер Гельфанд, играть с мощными компьютерными программами (известными как движки) – это примерно как бороться против медведя гризли просто поверьте, не стоит вам этого делать. Игры в формате люди против людей намного интерес- нее. В наше время, когда в шахматы играют гроссмейстеры, иногда выигрывает тот, кто делает первый ход, иногда – тот, кто отвечает на этот хода бывает итак, что игра заканчивается вничью. Игроки и теоретики, как правило, согласны в том, что у белых, делающих первый ход, есть небольшое преимущество. Статистики поддерживают этот взгляд: белые последовательно выигрывают чуть чаще черных, примерно в 55 % всех матчей. Игроки уже долго спорят о том, чем обернется исход идеальной игры – неизменной победой белых или ничьей. Они не верят в то, что существует выигрышная стратегия за черных (впрочем, несмотря на это широко распространенное мнение, венгерский гроссмейстер Андраш Адорьян, напротив, полагает, что идея о начальном преимуществе белых всего лишь заблуждение). Я уже оставил шахматы итак и не достиг в них успеха, но если мне будет позволено высказать свою догадку, то она такова когда оба игрока делают верные ходы, партия всегда окончится ничьей (как при игре в «крестики-нолики»). В будущем компьютеры смогут проверить все уместные варианты и решить, прав ли я в своем предположении. Довольно интересно, что ученые все еще не могут прийти к согласию в том, каково истинное значение теоремы Церме- ло. Изначально она была написана на немецком языке, а если вычитали научные или философские тексты на немецком (прекрасный пример – труды Гегеля), то вряд ли удивитесь и тому, что смысл теоремы туманен (о, как женам повезло, что сейчас язык науки – английский Свет Камера Мотор! |