Решение игры методом последовательных приближений

 

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

Относительные частоты применения этих стратегий определяют приближенное значение оптимальной смешанной стратегии, а средний выигрыш - приближенное значение цены игры.

Идея метода состоит в следующем. Пусть 1-й игрок выбирает чистую стратегию , на что 2-й игрок отвечает стратегией , которая наименее выгодна для первого. На этом ход противника 1-й игрок отвечает стратегией x_k, которая дает ему максимальный выигрыш. Далее, 2-й игрок отвечает на пару ходов 1-го игрока той стратегией, которая дает ему наименьший средний проигрыш за пару ходов и т. д.

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

	-1		-3

 

Cведем все результаты вычислений в таблицу:

 

									-3		1,5
					0,5					1,5
					0,333
					0,25					1,5	1,875
					0,8						1,3
					0,5						0,75
					0,857					1,286	1,072
					0,857					1,125
					0,778						0,889
					0,7					1,2	0,95
					0,9					1,364	1,137
					0,75						0,875

 

– номер партии (партия = 2 полухода);

– номер чистой стратегии первого игрока, выбранной в партии ;

– общий платеж 1-му игроку после партий, если 2-й все время применяет стратегию ;

– наименьший средний выигрыш 1-го за ходов, равный ;

– номер чистой стратегии 2-го игрока в -ой партии;

– общий платеж 1-му игроку, если он все время использует стратегию ;

– наибольший средний выигрыш 1-го за ходов, равный .

– приближенное значение цены игры, равное .

После 12 ходов получаем: , .

Для сравнения точное значение ν = 1, , .

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

Доказано, что процесс сходится при . При этом приближенное значение ν стремится к цене игры, а ξ и η могут колебаться около значения оптимальных стратегий. Трудоемкость метода снижается, если в ходе каждого приближения определять не только номер очередной чистой стратегии, но и то, сколько раз подряд она должна применяться.

 

 

1.5 Решение игр (m×n) методом линейного программирования

 

Теория игр находится в тесной взаимосвязи с линейным программированием (ЛП): любая конечная игра двух лиц может быть сведена к паре двойственных задач ЛП, и наоборот, задача ЛП может быть представлена как игра двух лиц. Таким образом, после сведения к игровой задачи к задаче ЛП можно применить любой известный метод (например симплекс-метод) и получить не приближенное, а точное решение игровой задачи.

Пусть дана игра . Будем считать, что в ней отсутствует седловая точка и удалены все доминируемые стратегии. Требуется найти точное решение. При m, n≥3 геометрическая интерпретация становится затруднительной.

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

Из свойств оптимальных стратегий следует, что если 1-й игрок использует оптимальную смешанную стратегию, а 2-й игрок использует любую из своих чистых стратегий , то

, j=1,…, n (1)

Кроме того , (2)

Аналогичные соотношения могут быть составлены и для 2-го игрока:

, i=1,…, m, (1*)

где . (2*)

Без ограничения общности будем считать, что цена игры , q_ij>0. Если в этом есть сомнения, то необходимо воспользоваться операцией приведения матрицы к виду без отрицательных элементов путем прибавления некоторой константы.

Разделим неравенства (1) и равенство (2) на цену игры ν и введем переменные p_i и z_j: .

После подстановки переменных в (1), (2) и (1*), (2*) получаем прямую и двойственную задачи ЛП следующего вида.

Прямая задача: , при условиях:

Двойственная задача: , при условиях:

Однако из теории ЛП известно, задача ЛП не всегда имеет решение, в отличие от конечной игры 2-х лиц с нулевой суммой (см. основную теорему теории игр). Следовательно, необходимо доказать, что в полученной паре двойственных задач всегда существует допустимое решение и целевая функция (ЦФ) является ограниченной.

Действительно, предположим, что в полученной задаче ЛП нет допустимого решения. Чтобы опровергнуть это, нужно указать на существование хотя бы одной точки в пространстве поиска решений, в которой все условия-ограничения выполняются. Какая это точка?

Поскольку все , то обозначим через . Тогда точка с координатами p₁ =1/ μ, р₂ = р₃ =…= р_m =0 является допустимым решением, т.к. она удовлетворяет условиям (2).

Целевая функция для прямой задачи ЛП минимизируется, поэтому она должна быть ограниченной снизу. В самом деле, все p_i ≥0, а коэффициенты в выражении (1) положительны, следовательно, целевая функция ограничена снизу нулем!

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

где i=1,…, m, j=1,…, n.

Рассмотрим пример. Найти решение игровой задачи следующего вида:

			-2
	-1
		-3

 

 

В матрице имеются отрицательные элементы, поэтому прибавляем ко всем элементам число 3 (цена игры увеличится на 3, на оптимальность стратегий операция не влияет):

 

Пара двойственных задач будет выглядеть следующим образом:

 

прямая задача:

при условиях

 

двойственная задача:

при условиях

 

Составим симплекс-таблицу для прямой задачи (выбор зависит от того, какая из задач имеет меньшее число ограничений, что в свою очередь зависит от числа стратегий игроков) и приведем ее к каноническому виду (изменить знаки в строке целевой функции на обратные). Она будет иметь следующий вид:

				-1
				-1
				-1
	-1	-1	-1

Разрешающий элемент для шага жорданова исключения выбираем исходя из известного условия: , причем ,

. Делаем шаг жорданова исключения с разрешающим элементом а₃₁, получаем следующую симплекс-таблицу:

 

 

		-16	-4
		-21	-12
		-6	-3
	-1			-1

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

Ищем оптимальное решение, выбирая в качестве разрешающего элемента элемент а₁₂, найденный их условия: , причем , .

 

Выполняя шаг жорданова исключения, получим новую симплекс-таблицу:

z2

 

Оптимальное решение не достигнуто (все элементы строки ЦФ неположительны), поэтому выбираем новый разрешающий элемент, используя предыдущее условие (элемент а₂₃), делаем шаг жорданова исключения и получаем новую симплекс-таблицу, которая удовлетворяет условию оптимальности и одновременно является решением прямой и двойственной задачи ЛП. Из полученной таблицы следует, что цена игры

,

 

 

1.6. Варианты заданий для самостоятельной работы

 

1. Построить платежную матрицу для следующих игр.

а) Сторона А посылает в район расположения противника Б два бомбардировщика I и II, причем первый летит впереди, а второй сзади. Один из бомбардировщиков (заранее неизвестно какой) дол­жен нести бомбу, а другой выполняет функцию сопровождения. В рай­оне противника бомбардировщики подверглись нападению истребителя стороны Б. Оба бомбардировщика вооружены пушками. Если истреби­тель атакует задний бомбардировщик, то по нему ведут огонь только пушки этого бомбардировщика, поражающие цель с вероятностью 0,3. Если истребитель атакует передний бомбардировщик, то по нему ве­дут огонь пушки обоих бомбардировщиков и поражают его с вероятностью 0,51. Если истребитель не сбит, то он поражает выбранный бомбардировщик с вероятностью 0,8. Выигрыш стороны А-это вероятность поражения носителя бомбы.

б) Игрок А выбирает одно из чисел:1,2 или 3. Игрок Б пыта­ется угадать выбранное число. При каждой догадке игрока Б игрок А отвечает "много", "мало" или "правильно". Игра ведется до правильной отгадки. Платеж игроку А - число догадок, которое требуется игроку Б, чтобы получить правильный ответ.

в) Игроки А и Б независимо друг от друга выбирают одно из чисел 1,2 или 3. Если выбранные числа совпадают, то игрок А платит игроку Б сумму в размере выбранного числа. В противном случае игрок а получает от игрока Б сумму, равную числу, выбранному иг­роком Б.

г) Две фирмы А и Б производят два конкурирующих товара. Каждый товар в настоящее время "контролирует" 50% рынка. Улучшив качество товаров, обе фирмы собираются развернуть рекламные компании. Если обе фирмы не будут этого делать, то состояние рынка не изменится. Однако если одна из фирм будет более активно рекламировать свои товары, то другая фирма потеряет соответствующий процент потребителей. Обследование рынка показывает, что 50% потенциальных потребителей получают информацию посредством телеви­дения. 30% - через газеты, 20% - через радиовещание. Цель каждой фирмы - выбрать подходящие средства рекламы.

 

2. Укажите область значений р и q, для которых партия (Х₂,У₂) будет седловой точкой в игре:

 

___|_ y_{1__}у₂ __ у₃ _ ___|_ y_{1__}у₂ __ у₃ _

a) Х₁ | 1 q 6 б) Х₁ | 2 4 5

Х₂ | p 5 10 Х₂ | 10 7 q

Х₃ | 6 2 3 Х₃ | 4 p 6

 

3. Доказать, что платежная матрица Q=||qij||nxn, где qij < qi,j+1,имеет седловую точку.

4. Доказать, что платежная матрица Q=||qij||mxn, где q_i,j = i-j имеет седловую точку.

5. Доказать, что если каждая подматрица 2x2 матрицы Q имеет седловую точку, то матрица Q также имеет седловую точку.

6. Привести примеры таких матриц А и В, что цена игры:

a) v(A+B) > v(A)+v(B)

б) v(A+B) < v(A)+v(B)

в) v(A+B) = v(A)+v(B).

7. Определить выигрыш игрока А в игре с матрицей Q, если игрок А выбрал смешанную стратегию ξ(х). а игрок Б - смешанную стратегию η(у):

 

а) 2 3 4 0 б) 8 2 3 5 1 в) 1 2 3 4 г) 2 0 4 4

3 2 0 1 6 5 7 2 5 5 6 7 8 3 2 0 2

4 0 5 1 8 4 2 3 1 12 11 10 9 4 5 0 1

0 4 0 2 2 7 4 6 10 2 5 3 1 2 4 2 3

а) ξ(х) = (1/4,1/4, 1/4,1/4) б) ξ(х) = (2/5, 2/5, 1/5,0)

η(у) = (1/8, 3/8,1/8,3/8) η(у) = (1/2,1/4, 0, 0,1/4)

 

в) ξ(х) = (l/4,1/4, 1/4, 1/4), г) ξ(х) = (1/4,3/8, 3/8,0)

η(у) = (1/8, 3/8,1/8,3/8) η(у) = (0,1/4,1/2,1/4).

 

8. Проверить, являются ли стратегии ξ(х) и η(у) оптимальны­ми в игре с матрицей:

 

а) 5 50 50 б) 2 0 2 3 в) 1 2 3 г) 3 3 2 2 6

1 1 0.1 3 1 0 2 5 6 7 0 4 2 6 2

10 1 10 4 0 1 4 2 5 3 7 3 6 2 2

0 3 2 2

 

 

а) ξ(х) = (1/6,0, 5/6) б) ξ(х) = (1/8, 3/8,1/8,3/8)

η(у) = (49/54, 5/54,0) η(у) = (0,1/2,1/2,0)

 

в) ξ(х) = (1/3,1/3, 1/3) г) ξ(х) = (1/3,1/3, 1/3)

η(у) = (1/2, 0,1/2) η(у) = (1/3,0,1/2,0,1/6).

 

9. Матрица размером mxm называется латинским квадратом, ес­ли каждая строка и каждый столбец ее содержат некоторую переста­новку из чисел от 1 до m. Найти цену игры для платежной матрицы, которая является латинским квадратом.

 

10. Обоснуйте ответ на вопрос: может ли строка матрицы иг­ры, в которой все элементы не превосходят цены игры, а некоторые меньше этого значения, входить с ненулевой вероятностью:

а) в некоторую оптимальную стратегию игрока А?

б) в любую оптимальную стратегию игрока А?

В случае положительного ответа привести конкретный пример.

 

11. Найти. решение геометрическим методом:

 

а) 2 3 -4 5 -1 0 б) 7 1 -2 6 3 4 в) 1 5 г) -2 4

4 -1 9 5 3 2 1 5 3 -5 3 2 6 0 0 -1

3 3 2 2

-1 7 6 -5

4 2 1 4

8 5 -3 5

 

12. Доказать, что игра имеет решение в чистых стратегиях:

 

а) a b б) a e a e a e a e

с d b f b f f b f b

a d c g g c c g g c

с b

 

где a, b, c, d. e, f, g - произвольные числа.

 

13. Найти хотя бы одно решение в игре с платежной матрицей:

 

а) Q=||qij||mxn, если qij = { 1, i<>j 0, i = j, причем n>=m

 

б) Q=||qij||mxn, если qij = { 1, i<>j 0, i = j, причем n<m

 

в) q 2q 1/2 2q 1/4 2q 1/6...

q 1 2q 1/3 2q 1/5 2q...

 

г)

			-5
			-1
			-2

 

д)

 

14. Найти решение игры методом линейного программирования и методом последовательных приближений:

 

а) 1 2 3 б) -1 1 1 в) 3 6 1 4 г) 1 3 -5 3 д) 5 8 3 1 6

4 0 1 2 -2 2 5 2 4 2 -1 4 7 2 4 2 6 3 5

2 3 0 3 3 -4 1 4 3 5 5 -1 1 9 2 4 6 4 1

1 3 2 5 3

 

15. Найти все решения в игре с матрицей:

 

-1 3 -3

2 0 3

2 1 0

 

16. Каждый из двух игроков записывает одно из чисел: 0,1 или 2, не показывая написанного противнику. Затем игрок А называет предполагаемую сумму записанных чисел, после чего игрок Б также называет предполагаемую сумму, причем ему не разрешается называть ту сумму, которую назвал игрок А. Угадавший получает от противни­ка 1 рубль. Если никто не угадал, то - ничья. Определить число чистых стратегий каждого из игроков. Найти хотя бы одно решение игры.

 

17. Два одинаково метких игрока, один из которых (А) воору­жен бесшумным ружьем, а другой (Б) - обычным, могут, двигаясь с одинаковой скоростью, сделать пять шагов по направлению к мишени. Каждый из них может выстрелить либо сразу, либо на одном из пяти шагов. Вероятность поражения мишени на S-м шаге равна S/5. Каждый из игроков имеет только по одной пуле, и только игрок А может ус­лышать, выстрелил игрок Б или нет (естественно, если игрок А ус­лышит выстрел игрока Б, то он будет стрелять на последнем пятом шаге). Тот, кто первым поразит цель, получает 1 рубль от своего противника. Если ни один из игроков не поразит мишень или оба поразят цель одновременно, то выигрыш равен нулю. Найти решение игры.

 

 

 

Библиографический список

Основная литература

1. Борисов А.Н. и др. Принятие решений на основе нечетких моделей. – Рига: Зинанте. 1990.

2. Вагин В.Н. Дедукция и обобщение в системах принятия решений. М.: Наука. 1988.

3. Венцель Е.С. Исследование операций: задачи, принципы, методология. М.: Наука. 1988.

4. Кини Р.Л., Райфа Х. Принятие решений при многих критериях: предпочтения и замещения. М: Радио и связь. 1981.

5. Коршунов Ю.М. Математические основы кибернетики. М: Энергия. 1980.

6. Ларичев О.И. Теория и методы принятия решений, а также хроника событий в волшебных странах. М.: Логос. 2002.

7. Ларичев О.И. и др. Выявление экспертных знаний. – М.: Наука. 1998.

8. Мушик Э., Мюллер П. Методы принятия технических решений. М.: Мир. 1990.

9. Нейман Дж., Моргенштерн О. Теория игр и экономическое поведение. М.: Наука. 1970

10. Саати Т.Л., Кернс К. Аналитическое планирование оргсистем. М.: Радио и связь. 1991.

11. Справочник: Искусственный интеллект// Под ред. Д.А. Поспелова. Т. 1,2. М: Наука. 1990.

12. Таха Х. Введение в исследование операций. Кн. 1,2. –М.: Мир. 1985.

13. Теория выбора и принятия решений. Учебное пособие. М.: Наука. 1982.

14. Трахтенгерц Э.А. Компьютерная поддержка принятия решений. М.: Синтег. 1998

Дополнительная литература

16. Аверкин А.Н. и др. Нечеткие множества в моделях управления и искусственного интеллекта / Под ред. Д.А. Поспелова. – М.: Наука. 1986.

17. Берштейн Л.С. и др. Методы и алгоритмы принятия решений при четких и нечетких исходных данных. Учебное пособие. Таганрог: ТРТУ. 2000. 92с.

18. Гаврилова Т.А., Хорошевский В.Ф. Базы знаний интеллектуальных систем. – СПб:Питер. 2000.

19. Гиг Дж. Прикладная общая теория систем. В 2-х кн. – М.: Мир. 1981.

20. Грешилов А.А. и др. Математические методы построения прогнозов. –М.: Радио и связь.1997.

21. Дюран Б., Оделл П. Кластерный анализ. – М.: Статистика. 1977.

22. Заде Л. Понятие лингвистической переменной и его применение к принятию приближенных решений. – М.: Мир. 1976.

23. Иберла К. Факторный анализ. – М.: Статистика. 1980.

24. Исследование операций/ Под ред. Н.Ш. Кремера. –М.: Банки и биржи, ЮНИТИ. 1997.

25. Ковалев С.М., Родзин С.И. Информационные технологии. – Ростов-на-Дону: СКНЦ ВШ, 2002.

26. Колемаев В.А. Математические методы принятия решений в экономике. Учебник. –М.: Финстатинформ. 1999.

27. Корнеев В.В. и др. Базы данных. Интеллектуальная обработка информации.–М.: Нолидж. 2000.

28. Курейчик В.В. Эволюционные, синергетические и гомеостатические методы принятия решений. Таганрог: ТРТУ. 2001. 221с.

29. Нариньяни А.С. НЕ – факторы: неточность и недоопределенность – различие и взаимосвязь // Ж. Известия РАН. Теория и системы управления. 2000. №5. -С.44-56.

30. Осипов Г.Н. Информационные технологии, основанные на знаниях// Ж. Новости искусственного интеллекта. 1993. №1. -С.7-41.

31. Попов Э.В. Экспертные системы. – М.: Наука. 1988.

32. Поспелов Д.А. Ситуационное управление: Теория и практика. – М.: Наука. 1986.

33. Силов В.Б. Принятие стратегических решений в нечеткой обстановке.– М.: ИНПРО-РЭС. 1995.

34. Тарасов В.Б. Агенты, многоагентные системы, виртуальные сообщества: стратегическое направление в информатике и ИИ (обзор) // Ж. Новости ИИ. 1998. №2. -С.5-63.

35. Труды международного конгресса «Искусственный интеллект в 21 веке». –М.:Физматлит.2001.

36. Франселла Ф., Баннистер Д. Новый метод исследования личности: руководство по репертуарным личностным методикам. – М.: Прогресс. 1987.

Практика №2