Хорди Деулофеу - Дилемма заключенного и доминантные стратегии. Теория игр

Нарисуем несколько кругов и квадратов, расположив их в ряд. Каждый игрок может убирать две одинаковые фигуры (два круга или два квадрата) и заменять их одним кругом, либо же забирать две разные фигуры и заменять их одним квадратом. Количество фигур будет постоянно уменьшаться, и в конце игры останется только одна. Если останется квадрат, выигрывает первый игрок, если останется круг — второй игрок. Существует ли стратегия, которая позволяет всегда выигрывать? Что произойдет, если изменить начальное число кругов и квадратов? Является ли эта игра стратегической? Рассмотрим начальную позицию, изображенную на рисунке ниже.

Сыграв несколько партий для такой расстановки, мы увидим, что второй игрок, кажется, всегда выигрывает (последней фигурой всегда будет круг). Если изменить число кругов, то кажется, что результат останется прежним. Если изменить число квадратов, то исход игры изменится.

Замкнуть треугольник.Это стратегическая игра для двух игроков. На листе бумаги нужно нарисовать окружность и обозначить на ней шесть произвольных точек. На каждом ходу игрок соединяет две точки отрезком. Один из игроков использует черный карандаш, второй игрок — красный карандаш. Каждый игрок может соединять любые две точки, кроме уже соединенных. Тот, кто нарисует треугольник со сторонами одного цвета, выигрывает.

Какой из игроков имеет преимущество? Как нужно играть, чтобы всегда выигрывать? Что изменится, если изменить начальное число точек? Можно играть по обратным правилам: тот, кто нарисует треугольник одного цвета, проигрывает. Что произойдет в этом случае?

Плитка шоколада (1).Плитка шоколада состоит из 28 окошек, расположенных в 4 ряда по 7 квадратиков. Первый игрок делит плитку на две части, не ломая ни одно из окошек. Второй игрок берет одну из полученных частей (другая откладывается в сторону) и снова делит ее. На каждом ходу игрок берет одну из двух только что полученных частей и делит ее на две части вдоль линий, разделяющих окошки. Тот, кто не сможет разделить плитку подобным образом, проигрывает.

Как нужно играть, чтобы выигрывать? Что изменится, если плитка будет состоять из 27 окошек, расположенных в 3 ряда по 9?

Плитка шоколада (2).На этот раз плитка состоит из 50 квадратных окошек, расположенных в 5 рядах по 10. Каждый игрок делит плитку (или ее часть) вдоль вертикальной или горизонтальной линии, не ломая ни одно из окошек. На этот раз ни одна из частей не откладывается в сторону, все они продолжают участвовать в игре. Первый игрок, который своим ходом получит одно отдельное окошко, проигрывает.

Как нужно играть, чтобы выигрывать? Что произойдет, если победителем будет объявляться тот, кто первым получит одно отдельное окошко?

Чтобы понять, что на самом деле это не игра и что победитель всегда определяется начальным положением фигур и самими правилами, нужно проанализировать, как меняется число квадратов по ходу партии. После каждого хода число квадратов может либо остаться неизменным (если два круга заменяются одним кругом, или если квадрат и круг заменяются квадратом), либо уменьшиться на два (если два квадрата заменяются одним кругом). Это означает, что если начальное число квадратов четное, то оно останется четным в течение всей партии. Следовательно, квадрат не может остаться последней фигурой, так как единица — нечетное число.

В этой главе мы говорили о стратегических играх, а именно о тех, которые можно полностью проанализировать. Мы увидели, как математика помогает найти выигрышную стратегию для одного из игроков, если такая стратегия существует. Такие эвристические методы, как изучение частных случаев; предположение, что игра завершена, и рассуждение в обратном направлении; использование симметрии, применяются при решении математических задач и полезны при анализе игр подобного типа. Как только для игры найдена выигрышная стратегия, это уже не игра, а решенная математическая задача.

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

В этой главе речь пойдет о взаимосвязи игр и вероятностей. Она стала очевидной сразу же, как только люди поняли возможность моделирования хаотических, случайных процессов. До этого в математике всегда говорилось о чем-то определенном, правильном, в чем можно быть уверенным. Можно сказать, что, когда были определены способы вычисления вероятностей, в математике началась новая эпоха. Этот раздел математики приобретал все большую важность по мере того, как становились известными все новые и новые области его применения. С приходом XX века предметами изучения и математического моделирования стали не только случайные процессы, но и хаос или нерегулярность фракталов.

В реальном мире сложные теории, касающиеся вероятностей, применяются в самых разных областях, так как в нашей жизни неопределенность встречается очень часто. Однако теория вероятностей берет свое начало именно в азартных играх. Можно утверждать, что теория случайных событий, основанная на понятии вероятности, начала формироваться во Франции в середине XVII века, в частности в 1654 году, в переписке Блеза Паскаля и Пьера Ферма, которые обсуждали вопросы, поставленные шевалье де Мере. Этот дворянин, знаток азартных игр, попросил Паскаля объяснить результаты некоторых азартных игр с игральными костями.

Антуан Гомбо, известный как шевалье де Мере (род. в Пуату, 1607—1685), посвятил большую часть жизни азартным играм и их анализу. Его интуитивные догадки много раз оказывались верными. По-видимому, он заработал приличную сумму различными азартными играми, где вероятность выигрыша и проигрыша одинакова. Например, такой считалась игра, где нужно было выбросить минимум одну шестерку броском четырех игральных костей. Однако Мере знал, что в этой игре один из игроков имеет преимущество. Он предложил новую игру, в которой требовалось минимум один раз выбросить две шестерки за 24 броска двух костей. Де Мере полагал, что преимущество одного из игроков здесь будет таким же, что и в исходной игре. Некоторое время спустя он убедился, что в действительности все происходит с точностью до наоборот. Поэтому примерно в 1654 году он обратился к Паскалю, чтобы тот нашел ошибку в его рассуждениях и объяснил, почему в новой игре у него не было преимущества.