2020-06-29
163
1. Перечислите возможные виды представления антагонистической игры.
2. Дайте определение класса информации.
3. Сформулируйте лемму 2.1.
4. Приведите пример представления антагонистической игры в виде дерева.
5. Назовите возможные методы поиска решений на дереве игры.
6. Дайте определения допустимого и оптимального алгоритмов поиска.
7. Поясните максиминный метод поиска решения.
8. Поясните неглубокое a - b отсечение.
9. Сформулируйте лемму 2.2.
10. Дайте доказательство леммы 2.2.
11. Поясните глубокое a - b отсечение.
12. Сформулируйте лемму 2.3.
13. Дайте доказательство леммы 2.3.
14. Приведите сравнительные оценки методов максимина и a - b отсечений.
15. Перечислите основные недостатки методов максимина и a - bотсечений.
МЕТОДЫ РЕШЕНИЯ АНТАГОНИСТИЧЕСКИХ ИГР, ПРЕДСТАВЛЕННЫХ В МАТРИЧНОЙ ФОРМЕ
Матричное представление антагонистической игры
Пусть заданы множества стратегий { Ai }, i =1,… m, и { Bj }, j =1,…, n, игроков A и B соответственно, а также матрица выигрышей A = ||aij||, i =1, …, m, j =1, …, n, где элемент aij – выигрыш игрока A в ситуации, когда он выбирает стратегию Ai, а игрок B – стратегию Bj. Такая игра G (m ´ n)может быть представленав матричной форме (и называется матричной игрой) в виде таблицы (табл. 3.1).
|
|
|
Таблица 3.1
 Bj
Ai
| B 1 | 
| Bj |
| Bn |
| A 1 | a 11 |
| a 1 j |
| a 1 n |
|
|
|
|
|
|
| Ai | ai 1 |
| aij |
| ain |
|
|
|
|
|
|
|
| Am | am 1 |
| amj |
| amn |
В качестве иллюстрации снова рассмотрим игру из примера 1 п. 2.1 для случая неполной информации, т.е. когда игроку B не сообщается о выборе игрока A. У игроков A и B имеется по две стратегии: A 1и A 2 – выбрать 1 или 2 соответственно, B 1и B 2– выбрать 2 или 3 соответственно. Данная игра G (2´2)в матричной форме представлена табл. 3.2.
Таблица 3.2
 Bj
Ai
| 
| 
|
| A 1 | 4 | –5 |
| A 2 | –5 | 6 |
Для случая, когда игроку B известно о выборе игрока A (т.е. игра с полной информацией), получаем игру G (2´4),матричная форма которой представлена табл. 3.3.
Таблица 3.3
 Bj
Ai
|
|
| 
| 
|
| A 1 | 4 | –5 | 4 | –5 |
| A 2 | –5 | 6 | 6 | –5 |
У игрока B добавились еще две стратегии: B 3 – отвечать стратегией с тем же номером, что выбрал игрок A (т.е. B 1на A 1 и B 2на A 2) и B 4 – отвечать стратегией с номером, отличным от выбора игрока A (т.е. B 2 на A 1 и B 1на A 2).
