Группа: №5
Курс: 1
Тема: « Выигрышные стратегии в играх»
Пример 1.
Двое играют в шашки на доске 8 х 8. При этом запрещается бить шашки соперника или превращать шашки в дамки. Проигрывает тот, кто не может сделать ход. Кто выиграет при правильной игре?
Решение.
Давайте рассуждать логически: на доске изначально16 шашек, вариантов походить у обоих игроков более чем достаточно (рис. 1).
Рис. 1. Шашки
Из этого следует такая подсказка: выигрышная стратегия должна быть простой и не сильно привязанной к правилам самих шашек.
Вспоминаем про один из основных способов построения стратеги: симметрия.
Докажем, что при правильной игре всегда выигрывает второй игрок. Для этого ему достаточно ходить симметрично первому относительно центра доски (рис. 2).
Рис. 2. Симметрия хода
Очевидно, что при таком подходе у второго игрока всегда будет ход (это достигается благодаря тому, что центр доски расположен не в какой-то из клеток, а на стыке 4 клеток). Таким образом, поскольку ходы рано или поздно закончатся (напомним, что в шашках нельзя ходить назад – только бить или ходить дамкой, но бить и менять шашки на дамки в наших шашках запрещено условием задачи), то они закончатся у первого игрока (так как у второго всегда будет ход).
Ответ: выигрышная стратегия есть у второго игрока.
Рассмотрим еще один пример выигрышной стратегии, в которой используется симметрия. Однако в этом примере мы попытаемся составить четкий алгоритм игры (похожий на тот, который может реализовать компьютер). Этот алгоритм мы попытаемся записать в виде блок-схемы.
Пример 2. Дана полоска размерами 1 х 99. Двое учеников по очереди делают свои ходы. За один ход разрешается зачеркнуть одну произвольную клетку полоски или какие-то две соседние клетки полоски. Проигрывает тот, кто не сможет сделать ход. Кто выиграет при правильной игре?
Решение.
Мы уже намекнули, что необходимо использовать симметрию. Однако клеток в полоске – нечетное число. Это подсказка к тому, что симметрию будет использовать первый игрок.
Вырисовывается следующая выигрышная стратегия: первый игрок закрашивает 50-ю клетку полоски. После его хода полоска разбивается на две одинаковые полоски (рис. 3).
Рис. 3. Полоса игры
Теперь задача первого игрока – ходить симметрично тому, как ходит второй игрок. Как видим, у первого игрока всегда будет ход после хода второго игрока (рис. 4).
Рис. 4. Полоса игры
Значит, выигрышная стратегия существует у первого игрока.
Составим четкий алгоритм выигрышной стратегии:
1. Закрасить клетку с номером 50.
2. Если второй игрок закрасил клетку с номером k, то закрасить клетку с номером 100-k.
3. Если второй игрок закрасил клетки с номерами k и k+1, то закрасить клетки с номерами 100-k и 99-k.
Этот алгоритма принесет первому игроку победу.
Составим блок-схему для описания этого алгоритма (рис. 5):
Рис. 5. Блок-схема алгоритма выигрышной стратегии игры
Рассмотрим еще один пример на нахождение выигрышной стратегии.
Пример 3.
Двое по очереди ставят крестики и нолики в клетки таблицы 9 х 9. Первый игрок ставит крестики, второй – нолики. В конце игры надо посчитать, сколько строк и столбцов, в которых крестиков больше, чем ноликов. Это количество очков первого игрока. Соответственно, количество строк и столбцов, в которых ноликов больше – это очки второго игрока. Выигрывает тот, у кого больше очков. Кто выиграет при правильной игре?
Решение.
И снова воспользуемся симметрией. У нас опять есть подсказка – нечетное количество клеток доски. Поэтому напрашивается такая стратегия: первый игрок своим первым ходом ставит крестик в центр. А дальше ходит симметрично второму игроку относительно центра (рис. 6).
Рис. 6. Крестики-нолики
Мы получаем, что если в каком-то столбце или строке ноликов больше, то в симметричном ему столбце или строке их, соответственно, меньше. А вот центральные строка и столбец остаются за первым игроком, так как в них в центре стоит крестик, а остальные клетки разбиты на симметричные пары. Значит, при такой игре выиграет первый игрок.
Ответ: выиграет первый игрок.