Сравнение методов решения игровых задач: числовые эксперименты
В статье приведены результаты числовых экспериментов по практической эффективности метода Брауна-Робинсон и монотонного алгоритма для матричных игр с точки зрения скорости сходимости и временных затрат, так и их точности. У статті представлені результати числових експериментів щодо практичної ефек...
Збережено в:
| Опубліковано в: : | Искусственный интеллект |
|---|---|
| Дата: | 2014 |
| Автори: | , , |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут проблем штучного інтелекту МОН України та НАН України
2014
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/85236 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Сравнение методов решения игровых задач: числовые эксперименты / О.А. Емец, Д.Н. Ольховский, Е.В. Ольховская // Искусственный интеллект. — 2014. — № 1. — С. 47–56. — Бібліогр.: 13 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859479171051290624 |
|---|---|
| author | Емец, О.А. Ольховский, Д.Н. Ольховская, Е.В. |
| author_facet | Емец, О.А. Ольховский, Д.Н. Ольховская, Е.В. |
| citation_txt | Сравнение методов решения игровых задач: числовые эксперименты / О.А. Емец, Д.Н. Ольховский, Е.В. Ольховская // Искусственный интеллект. — 2014. — № 1. — С. 47–56. — Бібліогр.: 13 назв. — рос. |
| collection | DSpace DC |
| container_title | Искусственный интеллект |
| description | В статье приведены результаты числовых экспериментов по практической эффективности метода
Брауна-Робинсон и монотонного алгоритма для матричных игр с точки зрения скорости сходимости и
временных затрат, так и их точности.
У статті представлені результати числових експериментів щодо практичної ефективності метода Брауна-
Робінсон і монотонного алгоритму для матричних ігор з точки зору збіжності і часових обмежень та точності.
The paper presents the results of numerical experiments about practical effectiveness of the Brown- Robinson method
and monotonic algorithm for matrix games in terms rate of convergence and exactness time outlay.
|
| first_indexed | 2025-11-24T11:53:40Z |
| format | Article |
| fulltext |
ISSN 1561-5359 «Штучний інтелект» 2014 № 1 47
2Е
В
УДК 519.83
О.А. Емец, Д.Н. Ольховский, Е.В. Ольховская
Полтавский университет экономики и торговли, Украина
Украина, 36014, г. Полтава, ул. Коваля, 3
Сравнение методов решения игровых задач:
числовые эксперименты
O.O. Iemets, D.M. Olhovskiy, O.V. Olhovskaya
Poltava University of economics and trade, Ukraine
Ukraine, 36014, c. Poltava, Kovalya st., 3
Comparison of Methods for Solving Game Tasks:
Numerical Experiments
О.О. Ємець, Д.М. Ольховський, О.В. Ольховська
Полтавський університет економіки і торгівлі, Україна
Україна, 36014, м. Полтава, вул. Коваля, 3
Порівняння методів розв’язування ігрових задач:
числові експерименти
В статье приведены результаты числовых экспериментов по практической эффективности метода
Брауна-Робинсон и монотонного алгоритма для матричных игр с точки зрения скорости сходимости и
временных затрат, так и их точности.
Ключевые слова: числовые эксперименты, метод Брауна-Робинсон, матричные игры.
The paper presents the results of numerical experiments about practical effectiveness of the Brown- Robinson method
and monotonic algorithm for matrix games in terms rate of convergence and exactness time outlay.
Key words: numerical experiments, Brown-Robinson method, matrix games.
У статті представлені результати числових експериментів щодо практичної ефективності метода Брауна-
Робінсон і монотонного алгоритму для матричних ігор з точки зору збіжності і часових обмежень та точності.
Ключові слова: числові експерименти, метод Брауна-Робінсон, матричні ігри.
Анализ конфликтных ситуаций приводит к возникновению новых моделей игро-
вых задач. В работах [1-9] введен новый класс задач комбинаторной оптимизации
игрового типа с двумя игроками, в которых платежи представлены матрицей, а на
стратегии игроков накладываются комбинаторные ограничения. Такие задачи имеют
широкое применение в разных областях человеческой деятельности. В [5] предло-
жен приближенный итерационный метод решения таких задач, в основе которого
лежат те же идеи, что и в основании метода Брауна-Робинсон [10]. Как известно,
метод Брауна-Робинсон показал определенную практическую эффективность, но, на
отдельных классах задач, как отмечено в [11] не достаточную скорость сходимости.
Учитывая это для решения задач, рассмотренных в [1-9], возникает необходимость
разработки других методов для решения матричных игр, которые будут основаны на
других подходах.
В [11] предложен монотонный метод решения игровых задач, который, по
мнению авторов этой публикации, является более эффективным и имеет лучшую
Емец О.А., Ольховский Д.Н. , Ольховская Е.В.
«Искусственный интеллект» 2014 № 1 48
2Е
скорость сходимости в сравнении с методом Брауна-Робинсон. В данной статье
поставлена задача на основе числовых экспериментов сравнить известные методы
решения матричных игр как с точки зрения скорости сходимости и временных
затрат, так и их точности, чтобы использовать эту модификацию при решении
задачи из [1-9].
Постановка задачи
Рассмотрим классическую матричную игру [12], в которой первый игрок имеет
m стратегий 1,i m , второй игрок – n стратегий 1,j n . Игроки поочередно делают
ходы: первый игрок выбирает свою i -ю стратегию, второй – свою j -ю стратегию,
после чего первый игрок получает выигрыш ija за счет второго игрока (если 0ija ,
то это означает, что первый игрок платит второму сумму ija ).
Значение функции выигрыша можно записать в виде прямоугольной матрицы А:
111 1
1
... ...
... ... ... ...
... ... ... ...
... ...
n
m mn
a a
A
a a
.
Таким образом, рассматривается матрица ( )ijA a , 1,i m , 1,j n размер-
ности m n . Проведение каждой партии матричной игры с матрицей A сводится к
выбору первым игроком i -й строки, а вторым игроком j -го столбца, и получения
первым игроком (за счет второго) выигрыша ija .
Алгоритмы методов
Если размерность исходной матрицы небольшая, то такую игру, как известно,
можно свести к поиску седловой точки функции или к получению решения пары
двойственных задач линейного программирования [12]. Матричные игры, в которых
исходная матрица имеет довольно большие размерности, чаще всего решаются при-
ближенными итерационными методами, в частности, методом Брауна-Робинсон [10],
и монотонным итеративным алгоритмом [11] и др. Рассмотрим алгоритмы на-
званных методов.
Метод Брауна-Робинсон
Идея метода – многоразовое фиктивное разыгрывание игры с заданной матри-
цей ( )ijA a . Один розыгрыш игры называют итерацией, количество которых не-
ограниченно. С ростом числа итераций N смешанные частоты применения чистых
стратегией игроков приближаются к их смешанным оптимальным стратегиям.
Расчеты делаются в предположении, что игроки хотят увеличить свой выигрыш
(уменьшить проигрыш). Предполагается, что они не знают своих оптимальных
стратегий. Ходы игроки делают в соответствии с принципом: будущее похоже на
прошлое, учитывая все сделанные итерации.
Первая стратегия (например, первым игроком) выбирается произвольно – возможно
с целью увеличить возможный выигрыш.
Сравнение методов решения игровых задач: числовые эксперименты
«Штучний інтелект» 2014 № 1 49
2Е
Выбор следующего ( s -го) хода 2-го игрока (после s ходов 1-го игрока) про-
исходит выбором стратегии ,sj такой, что
11 1
min ( )
N s N
s s
i j i jj nN N
a a v s s vs
, где
1 1( , ),..., ( , )s si j i j – пары стратегии игроков на 1, …, s ходах. А выбор ( 1)s -го хода
1-го игрока, (после s ходов 2-го игрока) происходит выбором стратегии 1si согласно
условию:
1 11 1
max ( )
s N N
s s
i j iji mN N
a a v s s vs
. Цена игры , как известно [10], удовлетво-
ряет неравенству ( ) ( )s s .
Наглядно итерации метода изображены в табл. 1, где N – номер итерации,
1 2, ,..., mA A A − соответственно стратегии первого, а 1 2, ,... nB B B − второго игроков,
N , N − минимальное в столбцах jB и максимальное в столбцах iA на шаге N ;
в строку на каждой итерации записывается накопление за все итерации (пла-
тежи); *
2
− приближенное значение цены игры после N итераций.
Окончание работы алгоритма может производиться при 1 выполнении равенст-
ва minmax ; 2) после выполнения определенного количества итераций, в таком
случае находят max1
max ( )
N s
N
и min
1
min ( )
N s
N
. Если minmax , то можно брать
minmax( ) / 2 .
Пример трех итераций решения игры с матрицей
2 1
3 2
1 4
A
методом Брауна-Робинсон представлено в табл. 1.
Таблица 1 – Три итерации решения матричной игры методом Брауна-Робинсон
N i B1 B2 j A1 A2 A3 N * N
1 2 1 2 1 2 4 1
2 1
1 2 4
1 1 2.5 4 4
3 1 4 1 2 3 1 2
3 5
3 5 5
3 1.5 2 5 2.5
2 3 2 1 2 3 1
3
6 7
5 8 6
6 2 2.3 8 2.7
Рассмотрим другой итеративный процесс – монотонный итерационный алгоритм.
Емец О.А., Ольховский Д.Н. , Ольховская Е.В.
«Искусственный интеллект» 2014 № 1 50
2Е
Монотонный итерационный алгоритм решения
матричных игр
Опишем согласно [11] монотонный алгоритм как итерационный процесс, кото-
рый позволяет найти оптимальное значение цены игры для игры AГ , которая за-
дана матрицей ijA a размерности m n .
На нулевом шаге первый игрок выбирает произвольную чистую страте-
гию 0
1 2, ,..., mx x x x и определяется вспомогательный вектор 0c как вектор скаляр-
ных произведений столбцов матрицы A и вектора 0x , то есть 0
1
,
m
j ij i
i
c a x
1,j n ,
0 0
1 ,..., cnc c .
Шаг 1. Устанавливаем номер итерации N , равный 1, 1N .
Шаг 2. Определяем 1 1min
n
N N
jj J
v c
и обозначим 1 1
1 ,...,N N NJ j j
множество
индексов, на которых достигается 1Nv , то есть 1
1
rg minN N
jj n
J A c
.
Шаг 3. Формируем матричную игру N
AГ Г как частичную игру AГ с матри-
цей N N
ijA a , где 1,i m , Nj J .
Шаг 4. Решаем сформированную частичную игру и определяем оптимальную
стратегию 1 ,..., x
N N N
mx x .
Шаг 5. Определяем вектор 1 ,...,
N N N
nc c c следующим образом:
1
mN
j iij
i
c a x
,
1,j n .
Шаг 6. Рассматриваем игру с матрицей размерности 2 n :
1 1
1
1
,...,
,...,
N N
n
N N
n
c c
c c
.
Находим оптимальную стратегию ,1N N , 0 1N первого игрока в этой игре.
При этом N выбираем согласно следующему соотношению:
1arg max min 1
NN
jN jj
c c
.
Шаг 7. Если 0N , то выход из алгоритма с ценой игры 1Nv , иначе – переход
на следующий шаг алгоритма.
Шаг 8. Вычисляем значение вектора 1 ,..., xN N N
mx x : 11
NN N
N Nx x x .
Шаг 9. Определяем компоненты вектора 1 ,...,N N N
nc c c согласно формуле:
11
NN N
N Nc c c .
Шаг 10. Увеличиваем номер N итерации на 1, переходим на шаг 2 алгоритма.
Сравнение методов решения игровых задач: числовые эксперименты
«Штучний інтелект» 2014 № 1 51
2Е
Числовые эксперименты
С целью исследования практической эффективности рассмотренных методов для
решения матричных игр и перспектив их применения в комбинаторной оптимизации
для задач [1-9] они были программно реализованы на языке Delphi. С использованием
этой программной реализации методов проведена серия числовых экспериментов на
компьютере с процессором AMD FX- 6300 с тактовой частотой 3.5 Ггц и объемом
оперативной памяти 8 ГБ.
Результаты экспериментов приведены в табл. 2 - 4, в которых указана раз-
мерность задачи – параметры n и m – и время, которое было потрачено на
вычисления (решалось по 10 задач при каждой размерности, приведено общее время
вычислений всех задач), где «мс» – миллисекунды, «с» – секунды, «мин» – минуты,
«ч» - часы. Элементы матрицы A для каждой задачи были сгенерированы как целые
числа с равномерным распределением в интервале [1;1000] . Работа алгоритмов
проводилась так:
1. Для метода Брауна-Робинсон до достижения относительной точности по
цене игры вычислений 10 5E , т. е. при minmax осуществлялась остановка.
2. Для монотонного алгоритма до получения значения параметра 0 , что
позволило получать точное решение задач. Следует отметить, что монотонный алго-
ритм требует решения на определенных этапах игровых задач размерности 2n ,
которые в данной программной реализации были решены с использованием симплекс-
метода, что в некоторых случаях не позволило достичь максимальной эффектив-
ности алгоритма.
Для проверки точности решения были использованы решения этих же задач
симплекс-методом, путем приведения игровых задач к паре двойственных задач ли-
нейного программирования.
Таблица 2 – Результаты числовых экспериментов (задачи типа 2n )
Размерность задач Время вычислений
№
п/п n m Метод Брауна-
Робинсон
Монотонный
итерационный
алгоритм
Симплекс-метод
1. 1000 2 202 мс 68мс 16мс
2. 5000 2 702 мс 302мс 22мс
3. 10000 2 1с 631мс 618мс 38мс
4. 20000 2 2с 706мс 1с 231мс 63мс
5. 30000 2 5с 91мс 1с 897мс 86мс
6. 40000 2 6с 657мс 2с 593мс 145мс
7. 50000 2 6с 746мс 3с 237мс 178мс
8. 100000 2 16с 569мс 6с 415мс 415мс
9. 250000 2 42с 301мс 16с 672мс 1с 140мс
10. 500000 2 1мин 3с 33с 851мс 2с 498мс
11. 1000000 2 3мин 57с 1мин 30с 4с 924мс
Емец О.А., Ольховский Д.Н. , Ольховская Е.В.
«Искусственный интеллект» 2014 № 1 52
2Е
Увеличение размерности задач в числовых экспериментах, до больших значений,
чем те, что приведены в табл. 2 и 3, оказалось невозможным в связи с ограни-
ченными вычислительными ресурсами компьютера (объемом оперативной памяти).
В числовых экспериментах, результаты которых приведены в табл. 2, было решено
ограничить размерность значениями 1000n m в связи со значительным временем
вычислений уже при этих параметрах.
С помощью математического пакета CurveExpert [13] была получена регрес-
сионная зависимость времени работы алгоритмов от размерности задач и коэффициент
корреляции 2R (рис. 1-3).
Рисунок 1 – Зависимость времени вычислений от размерности задачи
(для случая 2n )
Таблица 3 – Результаты числовых экспериментов (задачи типа n m )
Размерность
задач Время вычислений №
п/п n m Метод Брауна-Робинсон Монотонный
итерационный алгоритм Симплекс-метод
1. 10 10 1с 436мс 18мс 12мс
2. 20 20 7с 786мс 26мс 13мс
3. 30 30 21с 446мс 95мс 24мс
4. 40 40 38с 455мс 264мс 40мс
5. 50 50 1мин 29с 4с 317мс 84 мс
6. 100 100 4мин 59с 2мин 47с 1с 123мс
7. 200 200 20мин 5 с 16мин 20с 16с 182мс
8. 300 300 42мин 24с 38мин 17с 1мин 25с
9. 400 400 58мин 10с 1ч 5мин 4мин 10с
10. 500 500 1ч 40мин 1ч 58мин 9мин 50с
11. 600 600 2ч 10мин 3ч 40мин 24мин 10с
12. 700 700 2ч 57мин 5ч 30мин 42мин 20с
13. 800 800 3ч 50мин 7ч 30мин 1ч 56мин
14. 900 900 5ч 24мин 9ч 56мин 4ч 32мин
15 1000 1000 6ч 59мин 18ч 20мин 7ч 8мин
Сравнение методов решения игровых задач: числовые эксперименты
«Штучний інтелект» 2014 № 1 53
2Е
Рисунок 2 – Зависимость времени вычислений от размерности задачи
(для случая n m )
Таблица 4 – Результаты числовых экспериментов (задачи типа 2 m )
Размерность задач Время вычислений №
п/п n m Метод Брауна-
Робинсон
Монотонный
итерационный алгоритм
Симплекс-
метод
1. 2 100 892мс 35мс 19мс
2. 2 500 9с 634мс 582мс 244мс
3. 2 750 13с 836мс 1с 408мс 594мс
4. 2 1000 26с 492мс 11с 878мс 1с 309мс
5. 2 2000 1мин 4с 31с 109мс 5с 700мс
6. 2 3000 2мин 7с 57с 106мс 11с 721мс
7. 2 5000 4мин 33с 2мин 26с 36с 959мс
8. 2 10000 7мин 48с 5мин 44с 3мин 2с
9. 2 15000 14мин 28с 14мин 8с 6мин 34с
10. 2 20000 36мин 25с 29мин 11с 16мин 37с
Рисунок 3 – Зависимость времени вычислений от размерности задачи
(для случая 2 m )
Емец О.А., Ольховский Д.Н. , Ольховская Е.В.
«Искусственный интеллект» 2014 № 1 54
2Е
В результате проведенных числовых экспериментов выяснилось, что в случае раз-
мерности задач 2 n и 2n решение монотонным алгоритмом проводится за меньшее
время, чем методом Брауна-Робинсон. При этом следует заметить, что монотонный
алгоритм, в отличие от метода Брауна-Робинсон, позволил получить для каждой за-
дачи точное решение, но при этом определить вероятности стратегий только одного
игрока (в методе Брауна-Робинсон – обоих). Для задач с разными значениями m и n
при размерности, большей 400 400 , вычисления монотонным алгоритмом прово-
дятся дольше, чем методом Брауна-Робинсон. Это может объясняться необходимостью
проводить часть вычислений с использованием симплекс-метода, что обусловлено
данной программной реализацией.
В ходе экспериментов выяснилось, что метод Брауна-Робинсон требует наименьший
объем оперативной памяти, но при этом проводит значительно большее количество
итераций. Также следует отметить, что в осуществленных числовых экспериментах
решение задач симплекс-методом сведением матричной игры к паре двойственных
задач линейного программирования, потребовало меньше всего времени, но в то же
время использован значительный (наибольший из всех методов) объем оперативной
памяти вычислительной системы.
Выводы
В статье приведены результаты числовых экспериментов по практической эф-
фективности метода Брауна-Робинсон и монотонного алгоритма для матричных игр.
В ходе проведенных исследований были проведены сравнения этих двух методов
решения матричных игр с решением этих задач симплекс-методом с целью выясне-
ния возможности их применения для решения задач комбинаторной оптимизации
игрового типа. Полученные результаты позволяют сделать вывод, что монотонный
алгоритм для задач большой размерности предпочтительнее, чем метод Брауна-
Робинсон.
Как направление дальнейших исследований можно рассматривать разработку
методов решения задач комбинаторной оптимизации игрового типа с использова-
нием идей, на которых основывается монотонный алгоритм.
Список литературы
1. Емец О. А. Исследование математических моделей и методов решения задач на перестановках игрового
типа / О. А. Емец, Н. Ю. Устьян // Кибернетика и сист. анализ. – 2007. – № 6. – С. 103-114.
2. Садовский А. Л. Монотонный итеративный алгормитм решения матричных игр. / А. Л. Садовский – ДАН
СССР, 1978. – Т. 238, № 3. - С. 538-540.
3. Петросян Л.А. Теория игор./ Л.А. Петросян, Н.А. Зенкевич, Е.А. Семина. – М : Высш. шк., Книжный дом
«Университет». – 1998. – 304 с.
4. Ємець О.О. Розв’язування ігрових задач на переставленнях / О.А. Емец, Н.Ю. Устьян // Наукові вісті
НТУУ “КПІ”. – 2007. – № 3. – С. 47-52.
5. Емец О.А. Решение некоторых задач комбинаторной оптимизации на размещениях и перестановках
игрового типа / О.А. Емец, Н.Ю. Устьян. // Проблемы управления и информатики. – 2006. – № 3. – С. 37-47.
6. Емец О.А. Исследование задач комбинаторной оптимизации игрового типа на размещениях / О.А. Емец,
Н. Ю. Устьян // Проблемы управления и информатики. – 2007. – № 1. – С. 26-36.
7. Ємець О.О. Один ітераційний метод розв’язування ігрових задач на переставленнях / О.А. Емец, Н.Ю.
Устьян // Наукові вісті НТУУ “КПІ”. – 2008. – № 3. – С.5-10.
8. Емец О.А. Игры с комбинаторными ограничениями / О.А. Емец, Н.Ю. Устьян // Кибернетика и сист.
анализ. – 2008. – № 4. – С. 134-141.
9. Емец О.А. Итерационный метод решения комбинаторных оптимизационных задач игрового типа на раз-
мещениях / О.А.Емец, Е.В. Ольховская // Проблемы управления и информатики. – 2011. – № 3. – С. 69-78.
Сравнение методов решения игровых задач: числовые эксперименты
«Штучний інтелект» 2014 № 1 55
2Е
10. Ємець О.О. Розв’язування комбінаторних задач ігрового типу з обмеженнями-переставленнями у обох
гравців: ітераційний метод / О.О. Ємець, О.В. Ольховська // Системні дослідження та інфораційні
технології . – № 4. – С. 80-93.
11. Емец О.А. Доказательство сходимости итерационного метода решения задачи комбинаторной
оптимизации игрового типа на размещениях / О.А. Емец, Е.В. Ольховская // Кибернетика и сист. анализ. –
2013. – № 1. – С. 102-114.
12. Julia Robinson An Iterative Method of Solving a Game / The Annals of Mathematics, Second Series. – Vol. 54,
№ 2 (Sep., 1951). – P. 296-301
13. CurveExpert Software / Daniel G. Hyams. – 2013. – Режим доступу : http://www.curveexpert.net/.
References
1. Yemets O. O. Study of mathematical models and methods of solving problems on permutations of the
gaming type. Yemets O. O., Ustian N. Y. Kibernetika i sist. analiz (Ukraine), 2007, 6, pp. 103-114.
2. Sadovskiy A.L. Monotone iterative algorithm for solving matrix games. A.L. Sadovskiy. RAS USSR,
1978, vol. 238, № 3, pp. 538-540.
3. Petrosyan L.A. Games theory. L.A. Petrosyan, N.A. Tzenkevich, E.A. Semina. Moscow, 1998, 304 p.
4. Yemets O. O. Solving game problems on permutations. Yemets O. O., Ustian N. Y. Naukovі Visti NTUU
"KPI" (Ukraine), 2007, 3, pp. 47-52.
5. Yemets O. O. Solving some combinatorial optimization problems on arrangements and permutations of the
gaming type. Yemets O. O., Ustian N. Y. Problemy upravleniia i informatiki (Ukraine), 2006, 3, pp. 37-47.
6. Yemets O. O. Study of combinatorial optimization problems of the gaming type on arrangements. Yemets
O. O., Ustian N. Y. Problemy upravleniia i informatiki (Ukraine), 2007, 1, pp. 26-36.
7. Yemets O. O. One iterative method of solving game problems on permutations. Yemets O. O., Ustian N.
Y. Naukovі Visti NTUU "KPI" (Ukraine), 2008, 3, pp. 5-10.
8. Yemets O. O. Games with combinatorial restrictions. Yemets O. O., Ustian N. Y. Kibernetika i sist.
analiz (Ukraine), 2008, 4, pp. 134-141.
9. Yemets O. A. The iterative method of solving combinatorial optimization problems of the gaming type on
arrangements. Yemets O. O., Olkhovska O. V. Problemy upravleniya i informatiki (Ukraine), 2011, 3, pp. 69-78.
10. Yemets O. O. Solving combinatorial problems of the gaming type with permutations-restrictions of both
players: the iterative method. Yemets O. O., Olkhovska O. V. Systemni doslidzhennia ta informatsiini
tekhnolohii (Ukraine), 4, pp. 80-93.
11. Yemets O. O. Proof of convergence of the iterative method for solving combinatorial optimization
problems of the gaming type on arrangements. Yemets O. O., Olkhovska O. V. Kibernetika i sist. analiz
(Ukraine), 2013, 1, pp. 102-114.
12. Julia Robinson An Iterative Method of Solving a Game / The Annals of Mathematics, Second Series,
Vol. 54, No. 2 (Sep., 1951), pp. 296-301
13. CurveExpert Software / Daniel G. Hyams. – 2013.
RESUME
O.O. Iemets, D.M. Olhovskiy, O.V. Olhovskaya
Comparison of Methods for Solving Game Tasks:
Numerical Experiments
Background: іn combinatorial optimization a new class of combinatorial optimization
problems of the gaming type is considered, with two players, in which payments are
presented as a matrix, and combinatorial restrictions are imposed on the strategies of the
players. Such problems can be widely used in various fields of human activity. To solve
this class of problems an approximate solving method is suggested, which is based on the
same ideas as those being in the basis of the method of Brown- Robinson. It is well known
that the method of Brown- Robinson has shown a certain practical efficiency, however in
Емец О.А., Ольховский Д.Н. , Ольховская Е.В.
«Искусственный интеллект» 2014 № 1 56
2Е
separate classes of problems convergence speed was not sufficient. Taking this into consi-
deration for solving combinatorial optimization game type it becomes necessary to develop
other methods for solving matrix games, which will be based on other approaches.
Materials and methods: In our article we have set the task to compare the known
methods for solving matrix games basing on numerical experiments, both in terms of speed
of convergence and time-consumption, as well as in terms of their accuracy, in order to use
this modification at solving combinatorial optimization problems of game type
Results: In order to investigate the practical effectiveness of the method of Brown-
Robinson and monotonic algorithm for solving matrix games as well as the prospects for
their use in combinatorial optimization , they were implemented in the language of Delphi.
Using this software implementation of methods, a series of numerical experiments have
been accomplished on a computer with an AMD FX 6300 processor with a clock speed of
3.5 GHz and 8 GB of RAM. In the course of the experiments 10 tasks have been solved in
each dimension, the A matrix elements for each task were generated as integers with
uniform distribution in the interval[1;1000] . To check the accuracy of the solution the
simplex method has been used to solve the same problems, by bringing the game problems
to a pair of dual problems of linear programming. With the help of mathematical package
CurveExpert we have obtained regression dependence of the work time of algorithms on
the dimension of the tasks and the correlation coefficient 2R , which showed that the time
depends as a second-degree polynomial.
Conclusion: According to the results of experiments monotonic algorithm for large-
dimension problems is preferred to the method of Brown- Robinson.
Статья поступила в редакцию 26.12.2013.
|
| id | nasplib_isofts_kiev_ua-123456789-85236 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1561-5359 |
| language | Russian |
| last_indexed | 2025-11-24T11:53:40Z |
| publishDate | 2014 |
| publisher | Інститут проблем штучного інтелекту МОН України та НАН України |
| record_format | dspace |
| spelling | Емец, О.А. Ольховский, Д.Н. Ольховская, Е.В. 2015-07-22T19:16:32Z 2015-07-22T19:16:32Z 2014 Сравнение методов решения игровых задач: числовые эксперименты / О.А. Емец, Д.Н. Ольховский, Е.В. Ольховская // Искусственный интеллект. — 2014. — № 1. — С. 47–56. — Бібліогр.: 13 назв. — рос. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/85236 519.83 В статье приведены результаты числовых экспериментов по практической эффективности метода Брауна-Робинсон и монотонного алгоритма для матричных игр с точки зрения скорости сходимости и временных затрат, так и их точности. У статті представлені результати числових експериментів щодо практичної ефективності метода Брауна- Робінсон і монотонного алгоритму для матричних ігор з точки зору збіжності і часових обмежень та точності. The paper presents the results of numerical experiments about practical effectiveness of the Brown- Robinson method and monotonic algorithm for matrix games in terms rate of convergence and exactness time outlay. ru Інститут проблем штучного інтелекту МОН України та НАН України Искусственный интеллект Алгоритмическое и программное обеспечение параллельных вычислительных интеллектуальных систем Сравнение методов решения игровых задач: числовые эксперименты Порівняння методів розв’язування ігрових задач: числові експерименти Comparison of methods for solving game tasks: numerical experiments Article published earlier |
| spellingShingle | Сравнение методов решения игровых задач: числовые эксперименты Емец, О.А. Ольховский, Д.Н. Ольховская, Е.В. Алгоритмическое и программное обеспечение параллельных вычислительных интеллектуальных систем |
| title | Сравнение методов решения игровых задач: числовые эксперименты |
| title_alt | Порівняння методів розв’язування ігрових задач: числові експерименти Comparison of methods for solving game tasks: numerical experiments |
| title_full | Сравнение методов решения игровых задач: числовые эксперименты |
| title_fullStr | Сравнение методов решения игровых задач: числовые эксперименты |
| title_full_unstemmed | Сравнение методов решения игровых задач: числовые эксперименты |
| title_short | Сравнение методов решения игровых задач: числовые эксперименты |
| title_sort | сравнение методов решения игровых задач: числовые эксперименты |
| topic | Алгоритмическое и программное обеспечение параллельных вычислительных интеллектуальных систем |
| topic_facet | Алгоритмическое и программное обеспечение параллельных вычислительных интеллектуальных систем |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/85236 |
| work_keys_str_mv | AT emecoa sravneniemetodovrešeniâigrovyhzadaččislovyeéksperimenty AT olʹhovskiidn sravneniemetodovrešeniâigrovyhzadaččislovyeéksperimenty AT olʹhovskaâev sravneniemetodovrešeniâigrovyhzadaččislovyeéksperimenty AT emecoa porívnânnâmetodívrozvâzuvannâígrovihzadaččislovíeksperimenti AT olʹhovskiidn porívnânnâmetodívrozvâzuvannâígrovihzadaččislovíeksperimenti AT olʹhovskaâev porívnânnâmetodívrozvâzuvannâígrovihzadaččislovíeksperimenti AT emecoa comparisonofmethodsforsolvinggametasksnumericalexperiments AT olʹhovskiidn comparisonofmethodsforsolvinggametasksnumericalexperiments AT olʹhovskaâev comparisonofmethodsforsolvinggametasksnumericalexperiments |