Моделирование
Графы. Игровые стратегии
Игровые стратегии
Как вы уже знаете из § 6, игровые модели — это модели, которые описывают соперничество двух (или более) сторон, каждая из которых стремится к выигрышу, т. е. преследует свою цель. Часто цели участников противоречивы — выигрыш одного означает проигрыш других.
Построением и изучением игровых моделей занимается теория игр — раздел прикладной математики. Задача состоит в том, чтобы найти стратегию (алгоритм игры), который позволит тому или другому участнику получить наибольший выигрыш (или, по крайней мере, наименьший проигрыш) в предположении, что соперники играют безошибочно.
Во многих простых играх, в которых игроки ходят по очереди, есть не так много вариантов развития событий, и их можно рассмотреть полностью, однозначно определив, кто выиграет в заданной начальной ситуации, если оба соперника не будут ошибаться.
Все позиции (игровые ситуации) делятся на выигрышные и проигрышные. Выигрышная позиция — это такая позиция, в которой игрок, делающий первый ход, может гарантированно выиграть при любой игре соперника, если сам не сделает ошибку. При этом говорят, что у него есть выигрышная стратегия — алгоритм выбора очередного хода, позволяющий ему выиграть.
Если игрок начинает играть в проигрышной позиции, он обязательно проиграет, если ошибку не сделает его соперник. В этом случае говорят, что у него нет выигрышной стратегии. Таким образом, общая стратегия игры состоит в том, чтобы своим ходом создать проигрышную позицию для соперника.
Выигрышные и проигрышные позиции можно охарактеризовать так:
• позиция, из которой все возможные ходы ведут в выигрыш
ные позиции, — проигрышная;
• позиция, из которой хотя бы один из возможных ходов
ведёт в проигрышную позицию, — выигрышная, при этом
стратегия игрока состоит в том, чтобы перевести игру в эту
проигрышную (для соперника) позицию.
Для примера рассмотрим игру с камнями, в которой участвуют два игрока. Вначале перед игроками лежит куча из некоторого количества камней (обозначим его S). За один ход игрок может добавить в кучу один камень (ход « + 1») или увеличить количество камней в куче в два раза (ход «*2»). Например, имея кучу из 5 камней, за один ход можно получить кучу из 6 или 10 камней. У каждого игрока есть неограниченное количество камней. Победителем считается игрок, первым получивший кучу, в которой 14 камней или больше.
Рассмотрим возможный результат игры при разном начальном количестве S камней в куче. Очевидно, что при S > 6 первый игрок (т. е. игрок, делающий первый ход) выигрывает сразу, удвоив число камней в куче. Начнём заполнять таблицу, в которой для каждого значения S будем указывать, выигрышная это позиция или проигрышная, и через сколько ходов завершается игра:
Здесь «В1» обозначает выигрыш за один ход.
При S = 6 у первого игрока есть два хода: ход «+1» даёт кучу из 7 камней, а ход «*2» — кучу из 12 камней. Выиграть за один не может, оба возможных хода ведут в выигрышные (для второго!) позиции, поэтому первый игрок проиграет, если второй не ошибётся. Позицию S — 6 отметим в таблице как «X1» (проигрыш за 1 ход):
Вспомним, что задача игрока — перевести игру в проигрышную для соперника позицию. Если S = 5 или S = 3, первый игрок может получить (ходом «+1» или «*2» соответственно) кучу из 6 камней, т. е. создать проигрышную позицию. Этого достаточно для выигрыша, но выиграть можно только за 2 хода:
Рассуждая аналогично, выясняем, что позиция S = 4 — проигрышная, так как возможные ходы ведут в выигрышные позиции (соперник выиграет за 1 или за 2 хода). При S = 2 первый игрок может своим ходом «*2» перевести игру в проигрышную позицию (S = 4), поэтому он выиграет. А при S = 1 он проиграет, потому что может своим ходом получить только кучу из 2 камней:
Полученная таблица показывает результат игры первого игрока в том случае, если второй не будет ошибаться. Если игра начинается в проигрышной позиции, первый игрок проиграет, а если в выигрышной — его стратегия состоит в том, чтобы на каждом шаге своим ходом создавать проигрышную позицию для соперника.
Для полного исследования всех вариантов игры можно построить дерево, содержащее все возможные ходы. Предположим, что сначала в куче 4 камня (эта позиция будет корнем дерева). Тогда в результате первого хода может получиться куча из 5 или 8 камней:
Следующий уровень дерева показывает все возможные позиции после ответного хода второго игрока:
Мы видим, что второй игрок может выиграть своим первым ходом (получив 16 камней), если первый построит кучу из 8 камней. В остальных случаях игра продолжается, и дерево можно строить дальше по тому же принципу.
Как мы уже показали ранее с помощью таблицы, при S = 4 выигрывает второй игрок. Чтобы доказать это с помощью дерева, не нужно строить полное дерево игры. Достаточно рассмотреть все возможные ходы соперника и для каждого из них найти один (!) выигрышный ход второго игрока. Вариант с выигрышем в один ход мы уже разобрали, теперь посмотрим, что произойдёт, если первый игрок получит кучу из 5 камней. Как следует из построенной выше таблицы, для кучи из 5 камней выигрышный ход второго игрока — «+1», он переводит игру в проигрышную позицию. При любом ответе первого игрока второй выигрывает своим вторым ходом «*2»:
Таким образом, мы доказали, что при S = 4 у второго игрока есть стратегия, позволяющая ему гарантированно выиграть, по крайней мере, за 2 хода.
на реальной местности.
