Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Игры
Во всех играх предполагается, что играют двое, ходы делаются по очереди (игроки не могут проустить ход). Ответить всегда надо на один и тот же вопрос: «кто побеждает: начинающий (первый) или его партнер (второй)?»
Игры-шутки
Игры-шутки — это игры, исход которых не зависит от того, как играют соперники. Поэтому для решения такой игры не нужно указывать выигрышную стратегию. Достаточно лишь доказать, что выигрывает тот или иной игрок (независимо от того, как будет играть).
Пример. Двое по очереди ломают шоколадку 6×8. За ход разрешается сделать прямолинейный разлом любого из кусков вдоль углубления. Проигрывает тот, кто не сможет сделать ход.
Решение. Заметим, что после каждого хода количество кусков увеличивается ровно на 1. Сначала был один кусок, а в конце игры, когда нельзя сделать ни одного хода, шоколадка разломана на 48 маленьких долек. Таким образом, игра будет продолжаться ровно 47 ходов. Последний 47-й ход (нечетный по счету ход) сделает первый игрок. Поэтому он в этой игре побеждает, причем независимо от того, как будет играть.
Симметричная стратегия
Пример. Двое по очереди кладут пятаки на круглый стол, причем так чтобы они не накладывались друг на друга. Проигрывает тот, кто не может сделать ход.
Решение. В этой игре выигрывает первый. Первым ходом он кладет пяток так, чтобы центры монеты и стола совпали. После этого каждый ход второго игрока начинающий отвечает симметрично относительно центра стола. Отметим, что при такой стратегии после каждого хода первого игрока позиция симметрична. Поэтому если возможен очередной ход второго игрока, то возможен и симметричный ему ответный ход первого. Следовательно, он побеждает.
При доказательстве правильности симметричной стратегии нельзя забывать о том, что очередному ходу может помешать только что сделанный ход соперника. Ранее сделанные ходы, в силу симметричности позиции, помешать не могут.
Чтобы решить задачу при помощи симметричной стратегии‚ необходимо найти симметрию, при которой только что сделанный противником ход не препятствует осуществлению выбранного плана игры.
Пример. Имеется две кучи камней по семь камней в каждой. За ход разрешается взять любое количество камней, но только из одной кучки. Проигрывает тот, кому нечего брать.
Решение. В этой игре второй игрок побеждает при помощи симметричной стратегии. Каждым своим ходом он должен брать столько же камней, сколько предыдущим ходом взял первый игрок, но из другой кучки. Таким образом, у второго игрока всегда есть ход.
Выигрышные позиции
Пример. Ладья стоит на поле a1. За ход разрешается сдвинуть ее на любое число клеток вправо или на любое число клеток вверх. Выигрывает тот, кто поставит ладью на поле h8.
Решение. В этой игре побеждает второй игрок. Его стратегия такова: каждым своим ходом он возвращает ладью на диагональ a1—h8. Первый игрок каждый раз вынужден будет уводить ладью с этой диагонали, а второй игрок после этого будет иметь возможность вернуть ладью па линию a1—h8. Так как поле h8 принадлежит диагонали, то на него сумеет встать именно второй игрок.
При решении этой задачи нам удалось выделить класс выигрышных позиций (ладья стоит во одной из клеток диагонали a1—h8)‚ обладающих следующими свойствами:
1) Завершающая игру позиция является выигрышной;
2) За ход из одной выигрышной позиции нельзя попасть в другую.
3) Из любой невыигрышной позиции за один ход можно попасть в какую-то выигрышную.
Нахождение такого класса выигрышных позиций для игры равносильно ее решению. Действительно к победе ведет такая стратегия: ходи в выигрышную позицию. Если исходная позиция выигрышная, то выигрывает второй. В противном случае выигрывает первый.