Составители:
Рубрика:
10 11
1.2. ИГРЫ n ЛИЦ С ПОЛНОЙ ИНФОРМАЦИЕЙ (ПИ)
НА ДРЕВОВИДНЫХ КОНЕЧНЫХ ГРАФАХ
Пусть задан древовидный граф
FX ,Г
. На этом графе задано
разбиение множества вершин X на подмножества
11
,...,,...,,
nni
XXXX
:
1
1
n
i
i
XX
, где
,
lk
XX
l
k
z
, т. е. никакие из подмножеств попар-
но не пересекаются и
x
F
для
1
n
Xx
.
Определение 1.21. Множество
i
X
,
ni ,1
, называется множе-е-
ством очередности игрока i.
Определение 1.22. Множество
11
,:
nxn
XxFX
, называ-
ется множеством окончательных позиций.
На множестве окончательных позиций
1n
X
задана последователь-
ность п вещественных функций
11
,...,,...,,
nni
XxxHxHxH
.
Определение 1.23. Функция
,xH
i
ni 1
, называется выигры-
шем i-ro игрока в позиции или в вершине x.
Введем понятие альтернативы. Пусть существует вершина x
и
xi
Fy
,
ki ,1
(рис. 1.4).
Утверждение 1.5. Исходящие из x дуги можно перенумеровать по
часовой стрелке единственным образом.
Определение 1.24. Номера дуг, исходящих из вершины x, называ-
ются альтернативами в этой вершине.
x
y
1
y
2
y
3
Рис. 1.4
Пусть задано множество
^`
nN ,,2,1
игроков. Игра начинает-
ся из начальной позиции
0
x
каким-либо игроком
1
i
:
1
0 i
Xx
. Будем счи-чи-
тать, что игра не окончательна, иначе не имеет смысла.
Тогда в вершине
0
x
игрок
1
i
выбирает вершину
0
1 x
Fx
. Если
2
1 i
Xx
, то в вершине
1
x
«ходит» игрок
2
i
и выбирает следующую вер-ер-
шину
1
2 x
Fx
, и т. д. Таким образом, если на k-м шаге реализована вер-
шина (позиция)
k
ik
Xx
1
, то в ней «ходит» игрок
k
i
и выбирает следу-
ющую позицию из множества
1k
x
F
.
Выбор игроков осуществляется последовательно, и вся информа-
ция известна, так как предполагаем, что игрок i при совершении выбора
в позиции
i
Xx
знает эту позицию х, а также из-за древовидности гра-
фа Г может восстановить и все предыдущие позиции. Примерами игр
с ПИ являются шахматы и шашки, так как в них игроки могут записы-
вать ходы, а потому можно считать, что они знают предысторию игры
при совершении каждого очередного хода.
Игра прекращается,
как только достигается окончательная верши-
на
1
nl
Xx
, т. е. такая, для которой
l
x
F
.
В позиции
l
x
каждый игрок i,
ni ,1
, получает выигрыш
li
xH
.
Замечание 1.8. Так как граф древовидный, то путь
lk
xxx ,,,,
0
,
однозначно реализуемый, обязательно приводит к окончательной позиции.
Определение 1.25. Путь Z, исходящий из начальной позиции
0
x
и достигающий одной из окончательных позиций игры
l
x
, называется
партией.
Определение 1.26. Под длиной игры G будем понимать длину наи-
большего пути
pll
Pp
max
max
в графе
FX ,Г
.
Введем понятие стратегии, используя понятие альтернативы. Стра-
тегия здесь – это правило, которое предписывает игроку в любой пози-
ции x из множества его очередности X
i
однозначный выбор следующей
позиции.
Определение 1.27. Стратегия i-гo игрока – это функция
niXxxu
ii
dd 1,,
, которая каждой вершине x множества очереднос-
тей игрока i ставит в соответствие номер некоторой альтернативы, воз-
можной в этой вершине x.
Множество всевозможных стратегий игрока i будем обозначать че-
рез
i
U
.
Определение 1.28. Если каждый из игроков выбрал свои страте-
гии, то упорядоченный набор
^`
xuxuxuxu
ni
...,,...,,
1
, где
ii
Uu
,
называется ситуацией в игре.
Определение 1.29. Декартово произведение
n
i
i
UU
1
называется
множеством ситуаций.
Страницы
- « первая
- ‹ предыдущая
- …
- 4
- 5
- 6
- 7
- 8
- …
- следующая ›
- последняя »
