Введение в теорию игр. Жариков И.А - 26 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

26
но, стратегия второго игрока состоит в указании, какое из двух чисел 3
или 4 он выбирает в каждом классе информации.
Стратегия в классе информации (4, 3, 3) означает, что второй иг-
рок выбирает 4 в классе информации S
2
и S
3
в классах информации S
3
и
S
4
. Пространство стратегий второго игрока приведено в табл. 1, б.
Пространство стратегий третьего игрока представлено в табл. 1, в.
3.8. ПРОСТРАНСТВА СТРАТЕГИЙ ДЛЯ ИГРЫ В ПРИМЕРЕ 1
3.8.1. ПОИСК НА ИГРОВЫХ ДЕРЕВЬЯХ
Деревья игры. Поиск выигрышной стратегии.
Рассмотрим класс игр двух лиц с полной информацией. В таких
играх участвуют два игрока, которые поочередно делают свои ходы.
В любой момент игры каждому игроку известно все, что произошло в
игре к этому моменту и что может быть сделано в настоящий момент.
Игра заканчивается либо выигрышем одного игрока (и проигрышем
другого), либо ничьей.
Таким образом, в рассматриваемый класс не попадают игры, ис-
ход которых зависит хотя бы частично от случая − большинство кар-
точных игр, игральные кости, «морской бой» и пр. Тем не менее класс
достаточно широк: в него входят такие игры, как шахматы, шашки,
реверси, крестики-нолики и другие игры.
Для формализации и изучения игровых стратегий в классе игр с
полной информацией может быть использован подход, основанный на
редукции задач. Напомним, что при этом должны быть определены
следующие составляющие: форма описания задач и подзадач; опера-
торы, сводящие задачи к подзадачам; элементарные задачи, а также
задано описание исходной задачи.
Наиболее интересной представляется задача поиска выигрышной
стратегии для одного из игроков, отправляясь от некоторой конкрет-
ной конфигурации (позиции) игры (не обязательно начальной). При
использовании подхода, основанного на редукции задач, выигрышная
стратегия ищется в процессе доказательства того, что игра может быть
выиграна. Аналогично, поиск ничейной стратегии, исходя из некото-
рой конкретной позиции, ведется в процессе доказательства того, что
игра может быть сведена к ничьей.
Ясно, что описание решаемой задачи должно содержать описание
конфигурации игры, для которой ищется нужная стратегия. Например,
в шашках игровая позиция включает задание положений на доске всех
шашек, в том числе дамок. Обычно описание конфигурации содержит
также указание, кому принадлежит следующий ход.
Пусть именами игроков будут ПЛЮС и МИНУС. Будем исполь-
зовать следующие обозначения:

Страницы