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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

27
X
S
или Y
S
− некоторая конфигурация игры, причем индекс S при-
нимает значения + или −
−−
−, указывая тем самым, кому принадлежит сле-
дующий ход (т.е. в конфигурации X
+
следующий ход должен делать
игрок ПЛЮС, а в X
−
−−
−
– игрок МИНУС);
W(X
S
) − задача доказательства того, что игрок ПЛЮС может вы-
играть, исходя из конфигурации X
S
;
V(X
S
) − задача доказательства того, что игрок МИНУС может вы-
играть, отправляясь от конфигурации X
S
.
Рассмотрим сначала игровую задачу W(X
S
). Операторы сведения
(редукции) этой задачи к подзадачам определяются исходя из ходов,
допустимых в проводимой игре:
1. Если в некоторой конфигурации X
+
очередной ход делает иг-
рок ПЛЮС и имеется N допустимых ходов, приводящих соответствен-
но к конфигурациям
,...,,,
21
−−−
N
XXX
то для решения задачи W(X
+
)
необходимо решить по крайней мере одну из подзадач
(
)
−
i
XW
. Дейст-
вительно, так как ход выбирает игрок ПЛЮС, то он выиграет игру,
если хотя бы один из ходов ведет к выигрышу − см. рис. 2, а.
2. Если же в некоторой конфигурации Y
−
−−
−
ход должен сделать иг-
рок МИНУС, и имеется K допустимых ходов, приводящих к конфигу-
рациям
,...,,,
21
+++
K
YYY
то для решения задачи W(Y
−
−−
−
) требуется ре-
шить каждую из возникающих подзадач
(
)
+
i
YW
. Действительно, по-
скольку ход выбирает МИНУС, то ПЛЮС выиграет игру, если выиг-
рыш гарантирован ему после любого хода противника (см. рис. 4, б).
Последовательное применение данной схемы редукции к исходной
конфигурации игры порождает И/ИЛИ-дерево (И/ИЛИ-граф), которое
называют деревом (графом) игры. Дуги игрового дерева соответствуют
ходам игроков, вершины − конфигурациям игры, причем листья дерева −
это позиции, в которых игра завершается выигрышем, проигрышем или
ничьей. Часть листьев являются заключительными вершинами, соответ-
ствующими элементарным задачам − позициям, выигрышным для игро-
ка ПЛЮС. Заметим, что для конфигураций, где ход принадлежит
ПЛЮСу, в игровом дереве получается ИЛИ-вершина, а для позиций, в
которых ходит МИНУС, получается И-вершина.
W(X
+
)
. . .
W(X
1
–
)
W(X
2
–
)
W(X
N
–
)
. . .
W(Y
–
)
W(Y
1
+
)
W(Y
2
+
)
W(Y
K
+
)
а) б)
Рис. 4

Страницы