Дилемма заключенного и доминантные стратегии. Теория игр - [16]
Из этих примеров становится понятно, что порой игры, кажущиеся совершенно разными, на самом деле полностью эквивалентны. Для этого достаточно иметь возможность преобразовать цель и правила одной игры в цель и правила другой. Однако в других случаях происходит обратное. Игры, которые кажутся полностью аналогичными, в действительности очень отличаются, особенно если разбирать их выигрышные стратегии. Рассмотрим еще одну игру, которая, кажется, полностью совпадает с игрой 1, о которой мы говорили выше.
Игра 10: маргаритка
Нарисуем маргаритку с 11 лепестками и поставим по одной фишке на каждом лепестке. На каждом ходу игрок может брать одну или две фишки, причем две фишки можно брать только с соседних лепестков.
Начальная позиция в игре«Маргаритка».
Эта игра очень похожа на первую игру из этой главы, но фишек не 20, а 11. Кажется, что выигрышная стратегия для первого игрока — взять две фишки на первом ходу, затем всегда оставлять число фишек, кратное трем. Однако наложенное ограничение (можно брать не любые две фишки, а только соседние) полностью нейтрализует эту стратегию. Теперь главную роль играет не количество фишек, а их расположение. Фактически исходное число фишек неважно, так как если фишек больше трех, то выигрышная стратегия звучит одинаково для любого числа фишек.
Эта игра уже не относится к семейству игр Ним. Она принадлежит к играм типа Нимбус, и общая стратегия для игр подобного типа неизвестна. Здесь мы рассказали о простейшей из игр такого типа. В нашем конкретном примере можно заметить, что второй игрок всегда будет выигрывать независимо от исходного числа фишек, если будет использовать симметричную стратегию. Попрактиковавшись в этой игре, можно увидеть, что если один из игроков разделит фишки на две одинаковые группы (если все фишки в одной группе находятся рядом, то и во второй они также должны находиться рядом), то будет всегда выигрывать, используя симметричную стратегию. Иными словами, он должен будет повторять для своей группы фишек ходы, которые делает соперник на другой группе фишек, причем положение фишек должно оставаться симметричным. Первый игрок не может разделить фишки на две группы первым ходом. Для этого ему нужно будет взять две фишки, не расположенные рядом друг с другом, что невозможно. Значит, после его хода между фишками образуется промежуток, и второй игрок сможет образовать второй промежуток, разделив фишки на две группы.
Современные абстрактные стратегические игры, несмотря на очевидную простоту, очень сложно анализировать. Хотя для них можно определить существование выигрышной стратегии, найти такую стратегию почти невозможно. Игра «Вавилон» французского автора Бруно Файдутти — наглядный пример подобных игр. На стол кладутся 12 фишек четырех разных цветов, по 3 фишки каждого цвета. Каждый из двух игроков берет одну стопку (изначально все стопки имеют высоту в 1 фишку) и кладет ее поверх другой, соблюдая следующие условия: одну стопку можно поставить на другую, если они имеют одинаковую высоту или же если верхние фишки обеих стопок одинакового цвета. Тот игрок, который не может поставить стопку поверх другой, проигрывает.
Хотя на первый взгляд кажется, будто решение можно найти, рассмотрев частные случаи с последующим обобщением, тщательный компьютерный анализ показывает, что найти стратегию, которую мог бы запомнить и использовать человек, невозможно.
«Вавилон»— игра, созданная Бруно Файдутти.
Игры и псевдоигры
Существуют игры, похожие на те, о которых мы только что говорили. Однако в действительности их нельзя назвать стратегическими играми, так как ни один из игроков не может повлиять на исход партии. Другими словами, выигрышная стратегия содержится в самих правилах, поэтому решения, принимаемые игроками, не имеют значения и не влияют на исход партии. Игры подобного типа, часто встречающиеся среди математических игр, получили название псевдоигр. Найти выигрышную стратегию для таких игр невозможно, так как ее не существует. Вместо этого можно доказать, что результат игры действительно не зависит от решений игроков и что правила однозначно определяют, кто будет всегда выигрывать. Рассмотрим три примера псевдоигр.
Игра 11: только нечетные
На столе лежит 20 фишек. Каждый из двух игроков своим ходом может взять 1, 3 или 5 фишек. Тот, кто забирает последнюю фишку, выигрывает. Какой из игроков имеет преимущество — тот, кто ходит первым или вторым? Что произойдет, если изменится число фишек? Эта игра является стратегической, как предыдущие, или же отличается от них?
Попрактиковавшись в этой игре, мы быстро увидим, что второй игрок всегда выигрывает, и первый игрок никак не может этому помешать. Можно сказать, что второй игрок будет выигрывать даже тогда, когда специально захочет проиграть. В отличие от предыдущих игр в этой игре определяющим условием является начальное число фишек и количество фишек, которое могут забирать игроки на каждом ходу. Значит, в этом случае нельзя говорить о выигрышной стратегии, так как победитель игры определен ее правилами.
Если изначально на столе лежит 20 фишек (или любое другое четное число) и первый игрок берет 1, 3 или 5 фишек (или любое другое нечетное число), то на столе останется нечетное число фишек (если вычесть из четного числа нечетное, получим нечетное). После этого второй игрок также должен взять нечетное количество фишек, и на столе останется четное число фишек (если вычесть из нечетного числа нечетное, получим четное число). Поэтому после хода первого игрока на столе всегда будет оставаться нечетное число фишек, а после хода второго игрока — четное. Так как 0 является четным числом, то побеждать всегда будет второй игрок вне зависимости от того, какие ходы будут совершать оба игрока. Аналогично, если начальное число фишек нечетно, победа всегда будет оставаться за первым игроком.
Книга посвящена жизни и творчеству выдающегося советского кристаллографа, основоположника и руководителя новейших направлений в отечественной науке о кристаллах, основателя и первого директора единственного в мире Института кристаллографии при Академии наук СССР академика Алексея Васильевича Шубникова (1887—1970). Классические труды ученого по симметрии, кристаллофизике, кристаллогенезису приобрели всемирную известность и открыли новые горизонты в науке. А. В. Шубников является основателем технической кристаллографии.
Нильс Бор — одна из ключевых фигур квантовой революции, охватившей науку в XX веке. Его модель атома предполагала трансформацию пределов знания, она вытеснила механистическую модель классической физики. Этот выдающийся сторонник новой теории защищал ее самые глубокие физические и философские следствия от скептиков вроде Альберта Эйнштейна. Он превратил родной Копенгаген в мировой центр теоретической физики, хотя с приходом к власти нацистов был вынужден покинуть Данию и обосноваться в США. В конце войны Бор активно выступал за разоружение, за интернационализацию науки и мирное использование ядерной энергии.
Джеймс Клерк Максвелл был одним из самых блестящих умов XIX века. Его работы легли в основу двух революционных концепций следующего столетия — теории относительности и квантовой теории. Максвелл объединил электричество и магнетизм в коротком ряду элегантных уравнений, представляющих собой настоящую вершину физики всех времен на уровне достижений Галилея, Ньютона и Эйнштейна. Несмотря на всю революционность его идей, Максвелл, будучи очень религиозным человеком, всегда считал, что научное знание должно иметь некие пределы — пределы, которые, как ни парадоксально, он превзошел как никто другой.
«Занимательное дождеведение» – первая книга об истории дождя.Вы узнаете, как большая буря и намерение вступить в брак привели к величайшей охоте на ведьм в мировой истории, в чем тайна рыбных и разноцветных дождей, как люди пытались подчинить себе дождь танцами и перемещением облаков, как дождь вдохновил Вуди Аллена, Рэя Брэдбери и Курта Кобейна, а Даниеля Дефо сделал первым в истории журналистом-синоптиком.Сплетая воедино научные и исторические факты, журналист-эколог Синтия Барнетт раскрывает удивительную связь между дождем, искусством, человеческой историей и нашим будущим.
Эта книга – захватывающий триллер, где действующие лица – охотники-ученые и ускользающие нейтрино. Крошечные частички, которые мы называем нейтрино, дают ответ на глобальные вопросы: почему так сложно обнаружить антиматерию, как взрываются звезды, превращаясь в сверхновые, что происходило во Вселенной в первые секунды ее жизни и даже что происходит в недрах нашей планеты? Книга известного астрофизика Рэя Джаявардхана посвящена не только истории исследований нейтрино. Она увлекательно рассказывает о людях, которые раздвигают горизонты человеческих знаний.
Можно ли выразить красоту с помощью формул и уравнений? Существует ли в мире единый стандарт прекрасного? Возможно ли измерить гармонию с помощью циркуля и линейки? Математика дает на все эти вопросы утвердительный ответ. Золотое сечение — ключ к пониманию секретов совершенства в природе и искусстве. Именно соблюдение «божественной пропорции» помогает художникам достигать эстетического идеала. Книга «Золотое сечение. Математический язык красоты» открывает серию «Мир математики» — уникальный проект, позволяющий читателю прикоснуться к тайнам этой удивительной науки.
В чем состоит загадка творчества? Существуют ли правила созидания? Действительно ли решение сложной задачи можно найти только в моменты удивительного озарения? Этими вопросами, наверное, задавался каждый из нас. Цель этой книги — рассказать о правилах творчества, его свойствах и доказать, что творчество доступно многим. Мы творим, когда мы размышляем, когда задаемся вопросами о жизни. Вот почему в основе математического творчества лежит умение задавать правильные вопросы и находить на них ответы.
Физика, астрономия, экономика и другие точные науки основаны на математике — это понятно всем. Но взаимосвязь математики и творчества не столь очевидна. А ведь она куда глубже и обширнее, чем думают многие из нас. Математика и творчество развивались параллельно друг другу на протяжении веков. (Например, открытие математической перспективы в эпоху Возрождения привело к перевороту в живописи.) Эта книга поможет читателю посмотреть на некоторые шедевры живописи и архитектуры «математическим взглядом» и попробовать понять замысел их создателей.
Число π, пожалуй, самое удивительное и парадоксальное в мире математики. Несмотря на то что ему посвящено множество книг, оно по праву считается самым изученным и сказать о нем что-то новое довольно сложно, оно по-прежнему притягивает пытливые умы исследователей. Для людей, далеких от математики, число π окружено множеством загадок. Знаете ли вы, для чего ученые считают десятичные знаки числа π? Зачем нам необходим перечень первого миллиарда знаков π? Правда ли, что науке известно все о числе π и его знаках? На эти и многие другие вопросы поможет найти ответ данная книга.