Математика/Прикладна математика

Д.ф.-м.н. Ємець О.О., Устьян Н.Ю.

Полтавський університет споживчої кооперації України

Ітераційний метод знаходження оптимальної стратегії гравця в ігрових комбінаторних задачах на переставленнях

В [1] була побудована математична модель ігрової задачі з комбінаторними обмеженнями на використання стратегій одним гравцем. Для знаходження оптимальної стратегії гравця, на стратегії якого накладаються комбінаторні обмеження, в таких задачах будемо використовувати наступний ітераційний метод. Цей метод використовує ідеї метода Брауна-Робінсона для розв'язування класичних ігор (див, наприклад, [2]). Розрахунки робляться, виходячи з припущення, що гравці прагнуть збільшити свій виграш (зменшити програш) та роблять ходи за принципом "майбутнє схоже на минуле", враховують всі зроблені ходи. Будемо вважати, що перший гравець має за мету зменшити свій програш, а другий гравець – збільшити свій виграш.

Кроки ітерації будемо заносити в таблицю (табл. 1), в якій – номер кроку, – вибрана стратегія першого гравця, – стратегії другого гравця, – скалярний добуток векторів, – максимальний накоплений виграш другого гравця стратегія другого гравця, – програш першого гравця для його чистої -тої стратегії при вибраній стратегії другого; числа в рядку – накоплені суми значень у попередньому рядку sum, – мінімальний накоплений програш першого гравця, ,

Спочатку перший гравець вибирає одну зі своїх стратегій навмання. Другий гравець аналізує виграш, який він отримає при кожній своїй стратегії, та вибирає стратегію з метою максимізувати накоплений виграш – значення в рядку В наведеному прикладі більший прибуток він отримає, якщо застосує свою другу чисту стратегію. Перший гравець вибирає свою наступну стратегію яка б мінімізувала програш (починаючи з другої ітерації накоплений програш) – скалярний добуток елементів векторів і Цей процес продовжується далі.

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

Розглянемо роботу ітераційного метода на прикладі. Нехай за умовою Складемо таблицю (табл.1), в яку будемо заносити результати розрахунків на кожній ітерації метода. В якості першої стратегії першого гравця виберемо стратегію навмання – наприклад,

Таблиця 1. Розв'язування ігрової задачі ітераційним методом

N	X	B1	B1 X	B2	B2 X	Nv	v	j	A1	A2	A3	Nv	v	v*
1	0,2	9	1,8	7	1,4			2	7	5	6
	0,3	7	2,1	5	1,5			sum	7	5	6
	0,5	2	1	6	3			SUM	7	5	6	5,7	5,7	5,8
	sum		4,9		5,9			Next X	0,2	0,5	0,3
	SUM		4,9		5,9	5,9	5,9
2	0,2	9	1,8	7	1,4			2	7	5	6
	0,5	7	3,5	5	2,5			sum	7	5	6
	0,3	2	0,6	6	1,8			SUM	14	10	12	11,4	5,7	5,75
	sum		5,9		5,7			Next X	0,2	0,5	0,3
	SUM		10,8		11,6	11,6	5,8
…
48	0,2	9	1,8	7	1,4			1	9	7	2
	0,5	7	3,5	5	2,5			sum	9	7	2
	0,3	2	0,6	6	1,8			SUM	352	256	256	275,2	5,733	5,733
	sum		5,9		5,7			Next X	0,2	0,5	0,3
	SUM		275,2		275,2	275,2	5,733

Можна побачити, що на 48-ій ітерації методу максимальний накоплений виграш другого гравця однаковий (275,2) при застосуванні будь-якої стратегії, тому другий гравець може вибирати будь-яку стратегію. Для першого гравця в рядку також стоять два однакових числа (352 256 256), а мінімальний накоплений програш дорівнює 275,2, тобто дорівнює максимальному накопленому виграшу другого гравця. На цьому кроці можна зупинити розрахунки – коли всі стратегії супротивника забезпечують приблизно однаковий виграш (програш) для якогось гравця.

Після 48-ї ітерації методу виявилось, що стратегія першого гравця використовувалась 40 разів, а стратегія – 8 разів, тому ймовірність застосування стратегії становить 5/6, а стратегії – 1/6.

Тепер, якщо ми знаходили розв'язок гри, яка може бути зіграна лише раз, то оптимальною стратегією першого гравця буде стратегія з максимальною ймовірністю, тобто стратегія Якщо ж гра може бути зіграна багато разів, тоді замість оптимальної стратегії – вектора ми будемо шукати вектор ймовірностей повторення кожної стратегії тут – кількість елементів в множині В даному прикладі в оптимальній стратегії першого гравця стратегія використовується з ймовірністю 5/6, стратегія – 1/6, а ймовірності застосування всіх інших стратегій дорівнюють 0.

Литература:

1. Ємець О.О., Устьян Н.Ю. Ігрова комбінаторна модель однієї задачі сільськогосподарського виробництва //Матеріали VII Міжнародної науково-практичної конференції "Наука і освіта '2004" – Дніпропетровськ: Наука і освіта, 2004, том 70 – С.46-49

2. Вентцель Е.С. Элементы теории игр. Узд. 2-е, стереотип. – М.: Физматгиз, 1961. – 67 с.