Дилемма заключенного и доминантные стратегии. Теория игр - [17]
Игра 12: круги и квадраты
Нарисуем несколько кругов и квадратов, расположив их в ряд. Каждый игрок может убирать две одинаковые фигуры (два круга или два квадрата) и заменять их одним кругом, либо же забирать две разные фигуры и заменять их одним квадратом. Количество фигур будет постоянно уменьшаться, и в конце игры останется только одна. Если останется квадрат, выигрывает первый игрок, если останется круг — второй игрок. Существует ли стратегия, которая позволяет всегда выигрывать? Что произойдет, если изменить начальное число кругов и квадратов? Является ли эта игра стратегической? Рассмотрим начальную позицию, изображенную на рисунке ниже.
Сыграв несколько партий для такой расстановки, мы увидим, что второй игрок, кажется, всегда выигрывает (последней фигурой всегда будет круг). Если изменить число кругов, то кажется, что результат останется прежним. Если изменить число квадратов, то исход игры изменится.
Замкнуть треугольник. Это стратегическая игра для двух игроков. На листе бумаги нужно нарисовать окружность и обозначить на ней шесть произвольных точек. На каждом ходу игрок соединяет две точки отрезком. Один из игроков использует черный карандаш, второй игрок — красный карандаш. Каждый игрок может соединять любые две точки, кроме уже соединенных. Тот, кто нарисует треугольник со сторонами одного цвета, выигрывает.
Какой из игроков имеет преимущество? Как нужно играть, чтобы всегда выигрывать? Что изменится, если изменить начальное число точек? Можно играть по обратным правилам: тот, кто нарисует треугольник одного цвета, проигрывает. Что произойдет в этом случае?
Плитка шоколада (1). Плитка шоколада состоит из 28 окошек, расположенных в 4 ряда по 7 квадратиков. Первый игрок делит плитку на две части, не ломая ни одно из окошек. Второй игрок берет одну из полученных частей (другая откладывается в сторону) и снова делит ее. На каждом ходу игрок берет одну из двух только что полученных частей и делит ее на две части вдоль линий, разделяющих окошки. Тот, кто не сможет разделить плитку подобным образом, проигрывает.
Как нужно играть, чтобы выигрывать? Что изменится, если плитка будет состоять из 27 окошек, расположенных в 3 ряда по 9?
Плитка шоколада (2). На этот раз плитка состоит из 50 квадратных окошек, расположенных в 5 рядах по 10. Каждый игрок делит плитку (или ее часть) вдоль вертикальной или горизонтальной линии, не ломая ни одно из окошек. На этот раз ни одна из частей не откладывается в сторону, все они продолжают участвовать в игре. Первый игрок, который своим ходом получит одно отдельное окошко, проигрывает.
Как нужно играть, чтобы выигрывать? Что произойдет, если победителем будет объявляться тот, кто первым получит одно отдельное окошко?
Чтобы понять, что на самом деле это не игра и что победитель всегда определяется начальным положением фигур и самими правилами, нужно проанализировать, как меняется число квадратов по ходу партии. После каждого хода число квадратов может либо остаться неизменным (если два круга заменяются одним кругом, или если квадрат и круг заменяются квадратом), либо уменьшиться на два (если два квадрата заменяются одним кругом). Это означает, что если начальное число квадратов четное, то оно останется четным в течение всей партии. Следовательно, квадрат не может остаться последней фигурой, так как единица — нечетное число.
В этой главе мы говорили о стратегических играх, а именно о тех, которые можно полностью проанализировать. Мы увидели, как математика помогает найти выигрышную стратегию для одного из игроков, если такая стратегия существует. Такие эвристические методы, как изучение частных случаев; предположение, что игра завершена, и рассуждение в обратном направлении; использование симметрии, применяются при решении математических задач и полезны при анализе игр подобного типа. Как только для игры найдена выигрышная стратегия, это уже не игра, а решенная математическая задача.
В общих чертах проанализированные игры принадлежат к играм типа Ним, где важно количество фишек, и к играм типа Нимбус, где, помимо количества, также важно расположение фишек, поэтому выигрышные стратегии для игр типа Ним здесь неприменимы. В целом стратегии для игр типа Нимбус определять сложнее.
Глава 3. Игры и азарт
Где заканчивается игра и начинается серьезная математика? <...> Для многих математика смертельно скучна и не имеет ничего общего с играми. Напротив, для большинства математиков это всегда игра, а также многое, многое другое.
Мигель де Гусман
В этой главе речь пойдет о взаимосвязи игр и вероятностей. Она стала очевидной сразу же, как только люди поняли возможность моделирования хаотических, случайных процессов. До этого в математике всегда говорилось о чем-то определенном, правильном, в чем можно быть уверенным. Можно сказать, что, когда были определены способы вычисления вероятностей, в математике началась новая эпоха. Этот раздел математики приобретал все большую важность по мере того, как становились известными все новые и новые области его применения. С приходом XX века предметами изучения и математического моделирования стали не только случайные процессы, но и хаос или нерегулярность фракталов.
