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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

29
Представленная в решающем графе выигрышная стратегия может
быть сформулирована словесно так: если в очередном ходе игрок
ПЛЮС берет одну монету, то в следующем ходе МИНУС должен
взять две, а если ПЛЮС берет две монеты, то МИНУС должен забрать
одну. Отметим, что для аналогичной задачи W(7
+
) решающий граф
построить не удастся (начальная вершина неразрешима); таким обра-
зом, у игрока ПЛЮС нет выигрышной стратегии в этой игре.
В большинстве игр, представляющих интерес, таких как шашки и
шахматы, построить полные решающие деревья и найти полные игро-
вые стратегии не представляется возможным. Например, для шашек
число вершин в полном игровом дереве оценивается величиной поряд-
ка 10
40
, и просмотреть такое дерево практически нереально. Алгорит-
мы же упорядоченного перебора с применением эвристик не настолько
уменьшают просматриваемую часть дерева игры, чтобы дать сущест-
венное, на несколько порядков, сокращение времени поиска.
Тем не менее для неполных игр в шашки и шахматы (например,
для эндшпилей), так же как и для всех несложных игр, таких как «кре-
стики-нолики» на фиксированном квадрате небольшого размера, мож-
но успешно применять алгоритмы поиска на И/ИЛИ-графах, позво-
ляющие обнаруживать выигрышные и ничейные игровые стратегии.
Рассмотрим, к примеру, игру «крестики-нолики» на квадрате 3×3.
Игрок ПЛЮС ходит первым и ставит крестики, а МИНУС − нолики.
Игра заканчивается, когда составлена либо строка, либо столбец, либо
диагональ из крестиков (в этом случае выигрывает ПЛЮС) или ноли-
ков (выигрывает МИНУС). Оценим размер полного дерева игры: на-
чальная вершина имеет 9 дочерних вершин, каждая из которых в свою
очередь − 8 дочерних; каждая вершина глубины 2 имеет 7 дочерних и
т.д. Таким образом, число концевых вершин в дереве игры равно
9! = 362 880, но многие пути в этом дереве обрываются раньше на за-
ключительных вершинах. Значит, в этой игре возможен полный про-
смотр дерева и нахождение выигрышной стратегии. Однако ситуация
изменится при существенном увеличении размеров квадрата или же в
случае неограниченного поля игры.
В таких случаях, как и во всех сложных играх, вместо нереальной
задачи поиска полной игровой стратегии решается, как правило, более
простая задача − поиск для заданной позиции игры достаточно хоро-
шего первого хода.
3.8.2. МИНИМАКСНАЯ ПРОЦЕДУРА
С целью поиска достаточно хорошего первого хода просматрива-
ется обычно часть игрового дерева, построенного от заданной конфи-
гурации. Для этого применяется один из переборных алгоритмов
(в глубину, в ширину или эвристический) и некоторое искусственное

Страницы