Материал: 4329

Внимание! Если размещение файла нарушает Ваши авторские права, то обязательно сообщите нам

Совокупность ходов, предпринятых игроками от начала до окончания игры, называется партией.

Стратегией игрока называется совокупность правил, определяющих выбор его действий при каждом личном ходе в зависимости от сложившейся ситуации. Обычно в процессе игры при каждом личном ходе игрок делает выбор в зависимости от конкретной ситуации, сложившейся в процессе игры. Игра называется конечной, если у каждого игрока имеется конечное число стратегий, и бесконечной – в противном случае.

Для того чтобы решить игру, или найти решение игры, следует для каждого игрока выбрать стратегию, которая удовлетворяет условию оптимальности, т.е. один из игроков должен получить максимальный выигрыш, когда второй придерживается своей стратегии. В тоже время второй игрок должен иметь минимальный проигрыш, если первый придерживается своей стратегии. Такие стратегии называются оптимальными. Оптимальные стратегии должны также удовлетворять условию устойчивости, т.е. любому из игроков должно быть не выгодно отказаться от своей стратегии в этой игре.

Конечная парная игра с нулевой суммой называется матричной игрой.

Рассмотрим парную конечную игру с нулевой суммой. Пусть игрок

располагает

m личными стратегиями

A1, A2 , A3 , … , Am . Пусть у игрока

имеется n личных стратегий

B1 , B2 ,

B3 , … , Bn . В этом случае говорят, что

игра имеет размерность m n .

В результате выбора игроками любой пары

стратегий

B j

( i = 1, 2, 3, … , m ;

j = 1, 2, 3, … , n ) однозначно

определяется исход игры, т.е. выигрыш

aij

игрока

А (положительный или

отрицательный) и проигрыш

( – aij )

игрока

В. Предположим, что значения

aij

известны для любой пары стратегий ( Ai , B j ).

Матрица Р (аij )m n

(i = 1, 2, 3, … , m ;

j = 1, 2, 3, … , n ),

элементами которой являются выигрыши,

соответствующие стратегиям

B j , называется платежной матрицей

или матрицей игры

	а	a	...	а
	11	12		1n
Р a21		a22	...	а2n .
... ...			...	...
	аm1	am2
	аm1	am2	...	аmn

Общий вид такой матрицы может быть представлен в виде таблицы (табл. 1), строки которой соответствуют стратегиям игрока А, а столбцы стратегиям игрока В.

				Таблица 1

	В	B1	B2	…	Bn
	А	B1	B2		Bn
	А

	A1	a11	a12	…	a1n
	A1	a11	a12		a1n
	A2	a21	a22	…	a2n
	A2	a21	a22		a2n
	…	…	…	…	…

	Am	am1	am2	…	amn
	Am	am1	am2		amn
Поставим задачу: определить оптимальные стратегии игроков.
Выбирая стратегию Ai , игрок			А должен рассчитывать на то, что игрок

В ответит на нее той стратегией B j , для которой выигрыш для игрока А будет минимален ( игрок В стремится «навредить» игроку А ).

Обозначим через		i	наименьший выигрыш игрока		А при выборе им
стратегии Ai	для всех	возможных стратегий игрока		В ( наименьшее число в
i – ой строке платежной матрицы ), т. е. min				a .	Следовательно, для
			i 1 j n	i j

получения наибольшего выигрыша игроку А нужно выбирать ту из стратегий,

для которой число		i		максимально.		Среди чисел i			( i = 1, 2, 3, … , m )
выберем наибольшее			max i .
				1 i m
Число	max min a					называется		нижней ценой			игры, или
			1 i m 1 j n		i j
максимальным выигрышем (максимином). Это								гарантированный			выигрыш
игрока А при любой стратегии игрока В .
Стратегия,		соответствующая				максимину, называется				максиминной
стратегией.
Таким образом, если игрок А будет придерживаться максиминной
стратегии, то ему гарантирован выигрыш, не меньше, чем										, при любом
поведении игрока В.
Проанализируем теперь платежную матрицу с точки зрения игрока В,
заинтересованного в том, чтобы игрок						А	выиграл, как можно меньше.
Если игрок		В	выберет стратегию				B j , то все возможные выигрыши
игрока А будут элементами j – го столбца платежной матрицы Р.
В наихудшем			для	игрока	В	случае, когда игрок				А	применяет

стратегию, соответствующую максимальному элементу этого столбца,

проигрыш игрока В будет равен числу					max a .
				j	1 i m i j
Следовательно, игроку В нужно выбрать такую стратегию, для которой
число j	минимально.
Число		= min max	a	называется		верхней ценой	игры, или
		1 j n 1 i m	ij
минимаксным выигрышем (минимаксом).					Это	гарантированный	проигрыш
игрока В при любой стратегии игрока А .
Стратегия,		соответствующая		минимаксу, называется минимаксной
стратегией.
Таким образом, если игрок В				применяет минимаксную стратегию, то

игрок А не может выиграть больше, чем		.
Принцип,	диктующий игрокам	выбор наиболее «осторожных»
максиминной	и минимаксной стратегий соответственно, называется

принципом минимакса. Этот принцип следует из разумного предположения, что каждый игрок стремится достичь цели, противоположной цели противника.

Нетрудно показать, что нижняя цена игры никогда не превосходит верхней цены игры, т.е. .

Если нижняя и верхняя цены игры совпадают, т.е. = , то игру называют игрой с седловой точкой.

Для игры с седловой точкой общее значение нижней и верхней цены игры

= = называется чистой ценой игры, или ценой игры.

Минимаксные стратегии, соответствующие цене игры, являются

оптимальными стратегиями, а их совокупность – оптимальным решением, или решением игры.

Если игра не имеет седловой точки, то применение чистых стратегий не дает оптимального решения игры. В таком случае можно получить оптимальное решение, случайным образом чередуя чистые стратегии.

Смешанной стратегией

игрока

называется

применение

чистых стратегий

A1, A2 , A3 , … , Am

с вероятностями

р1 , р2 ,

р3 , … , рm

, причем сумма вероятностей равна 1 ( р1 + р2 + р3 +…+ рm = 1).

Смешенные стратегии игрока А записываются в в виде матрицы

...

SA =

...

или в виде строки

S =

...

Аналогично определяются

и обозначаются смешанные стратегии SВ

игрока В :

В ...

= q

... q ,

или S

где сумма

q3 ...

вероятностей появления стратегий равна 1 ( q1 + q2 + q3 +…+ qn = 1).

Замечание. Чистые стратегии можно считать частным случаем смешенных и задавать строкой, в которой 1 соответствует чистой стратегии.

Смешанные стратегии, избранные игроками, называются оптимальными, если одностороннее отклонение любым игроком от своей оптимальной стратегии может изменить средний выигрыш только в сторону невыгодную для игрока.

Совокупность, состоящая из оптимальной стратегии одного игрока и оптимальной стратегии другого игрока, называется оптимальным решением

или решением игры.

Средний выигрыш при применении обоими игроками оптимальных стратегий называется ценой игры.

В 1928 году фон Нейманом была доказана основная теорема теории игр, утверждающая, что каждая конечная игра имеет, по крайней мере, одно оптимальное решение, возможно, среди смешанных стратегий.

Поскольку все чистые стратегии являются частными случаями смешенных стратегий, то из основной теоремы теории игр можно получить:

Следствие 1. Любая игра имеет цену; Следствие 2. Цена игры удовлетворяет неравенству .

Стратегии, входящие в оптимальную стратегию с отличной от нуля вероятностью, называются активными.

Справедлива теорема об активных стратегиях: если один из игроков придерживается своей оптимальной смешанной стратегии, то средний выигрыш остается неизменным и равным цене игры , если второй игрок не выходит за пределы своих активных стратегий.

Эта теорема имеет большое практическое значение, так как указывает методы нахождения оптимальных стратегий при отсутствии седловой точки.

Рассмотрим игру размера 2 2 с платежной матрицей

a	a
P 11	12	.
	a22
a21	a22

Смотрите также:


«ДОХОДЫ, РАСХОДЫ И ПРИБЫЛЬ КОММЕРЧЕСКОГО БАНКА.»
«ДОХОДЫ, РАСХОДЫ И ПРИБЫЛЬ КОММЕРЧЕСКОГО БАНКА.»
Значение, сущность и содержание социально — педагогической деятельности в организации для детей-сирот и детей, оставшихся без попечения родителей
__RGR2
__RGR2
_11_А. Франс для эл версии
_индив анализ данных
- Интерфейс 485 и оптопорт 11
!!!Вопросы_Философские проблемы техники