Стратегические игры и решение задач. Вступление
Решил написать серию постов основанных чуть более, чем наполовину на тексте 2010 года составленным Хорди Деулофеу (Jordi Deulofeu). Опубликован DeAGOSTINI (Может быть ещё кем-то и где-то опубликован) в книге "Мир математики. Том 8. Дилемма заключенного и доминантные стратегии"
Глава о том, как, используя математику, выработать выигрышную стратегию в паре-тройке игр.
...Занимательная математика — это не только... разумное средство
заполнения досуга взрослых людей. Занимательная математика — это
прежде всего математика, причем в лучших своих образцах математика
прекрасная. Недаром видный английский математик Дж. Литлвуд заметил,
что хорошая математическая шутка лучше дюжины посредственных работ.
Мартин Гарднер
Игры можно классифицировать различными способами в зависимости от выбранного критерия: место для игры, число участников, длительность партии, уровень сложности и так далее.
Применительно к математике игры можно разделить на две большие группы в зависимости от того, присутствуют в них случайные события или нет. Случайные события могут фигурировать как в начальных условиях игры, так и при совершении ходов.
• Например, в большинстве карточных игр карты раздаются игрокам случайным образом. Так же происходит и в домино.
• Напротив, начальное положение шахматных фигур строго определено и неизменно, как и в нардах, реверси или испанской игре парчис.
Если говорить о случайности ходов, то во многих играх игроки свободно выбирают следующий ход из всех возможных, в то время как в других играх ходы зависят от броска одной или нескольких игральных костей. В этом случае игрок выбирает лишь из нескольких ходов, возможных для выпавшего числа очков на игральных костях.
Доска для игры парчис на 4-х игроков.
Стратегическими называются игры, в которых никогда не происходит случайных событий. Всё определяют только решения игроков. Благодаря отсутствию случайности, игры этого типа можно проанализировать и найти способ победить.
В некоторых случаях можно полностью определить выигрышную стратегию, в других ввиду сложности игры это не удастся, но можно показать, что подобная стратегия существует для одного из игроков. Несмотря на очевидное разнообразие игр такого типа, к ним применимо ограниченное число математических понятий и приемов, которые относятся преимущественно к арифметике (системы счисления и признаки делимости) и геометрии (равновесные ситуации, главным образом, симметрия).
Понятие выигрышной стратегии
В математике слово «игра» может обозначать как собственно игру, в которой участвует более одного игрока, имеются определенные правила, а цель игры — одержать победу в партии, так и математические развлечения и головоломки. В дальнейшем мы будем говорить об играх, в которых участвуют минимум два игрока. Эти игры также можно разбить на группы разными способами, но с точки зрения математики существует признак, определяющий две большие группы: игры с полной информацией и игры, в которых присутствует элемент неопределенности. В этой главе игры первой группы будем называть стратегическими, игры второй группы — азартными.
Как следует изучив игру, возникает вопрос: какие ходы нужно совершать, чтобы одержать победу в определенной партии? В азартных играх этот вопрос не имеет смысла, поскольку игроки лишь двигают фишки согласно выпавшим очкам на игральных костях и следуют инструкциям на игровых клетках. Иными словами, здесь нет места для принятия решений, поэтому нет «хороших» или «плохих» игроков. Результат игр подобного типа полностью зависит от случая, поэтому определить какую-либо выигрышную стратегию невозможно. В этом смысле можно сказать, что интересность игры с точки зрения математики равна нулю.
Другой крайний случай — игры с полной информацией, в которых в любой момент можно узнать все возможные ходы и их последствия (как минимум в теории) и нет места неопределенности. Из всех подобных игр нам больше всего знакомы шахматы, хотя подобных стратегических игр, как традиционных (го, манкала, шашки, крестики-нолики), так и современных (гекс, ним, реверси, абалон и другие), существует великое множество.
Японские гейши играют в го, автор — Эйдзан, 1811 год
Когда мы говорили об анализе игр этого типа, мы упомянули понятие выигрышной стратегии, то есть множества условий, позволяющих одному из игроков (как правило, речь идет об играх только для двух игроков) определить, как следует действовать в каждый момент времени, учитывая ходы, сделанные противником, чтобы одержать победу вне зависимости от ходов соперника. Существование выигрышной стратегии предполагает, что игра оканчивается победой одного из игроков, но в некоторых играх возможна и ничья, например, как в шахматах. В этом случае нужно вести речь о стратегиях, которые позволяют никогда не проигрывать. Когда стратегическая игра не может завершиться ничьей, можно убедиться, что существует выигрышная стратегия для первого или второго игрока, но это не означает, что подобную стратегию можно будет точно определить: игра может быть весьма сложной.
Допустим, что некая игра для двух игроков имеет следующие свойства:
1. В любой момент времени каждый игрок обладает всей информацией, чтобы решить, каким должен быть следующий ход.
2. Игроки совершают ходы поочередно.
3. В игре полностью отсутствует элемент неопределенности.
4. Любая партия оканчивается победой одного из игроков после конечного числа ходов.
При этих условиях можно показать, что обязательно существует выигрышная стратегия для одного из двух игроков: первого (игрок А) или второго (игрок Б). Допустим, что выигрышной стратегии для игрока А не существует, иными словами, для игрока Б всегда будет существовать ход, на который у игрока А не найдется достойного ответа, и он проиграет. Это означает, что победит игрок Б. Таким образом, для него существует выигрышная стратегия. Подобные рассуждения лишь доказывают, что в подобных играх всегда существует выигрышная стратегия, но это не означает, что ее будет легко обнаружить.
Для игр, в которых партия не обязательно содержит конечное число ходов, применимость этого утверждения зависит от принятия так называемой аксиомы выбора. Эта известная и противоречивая математическая аксиома утверждает, что для каждого семейства (конечного или бесконечного) непустых непересекающихся множеств существует новое множество, образованное путем выбора определенного элемента из каждого множества этого семейства. С помощью этой аксиомы Банах, Мазур и Улам в 1930 году определили бесконечную игру и доказали, что в ней не существует выигрышной стратегии ни для одного из игроков.
Ну вот пока всё. Следующий пост будет о том, как использовать преимущества и как определять стратегии. Найдём формулу победы в игре Ним и ей подобным.
