Игровая модель для двух лиц

 

Игрок A:{A_i} – множество стратегий A (i=1..m)

Игрок B:{B_j} – множество стратегий B (j=1..n)

Игра антагонистическая.

 

       Представление игры.

       - в виде дерева игры. (можно построить для любой игры)

       - в виде матрицы (платёжной) игры.

 

       Представление игры в виде дерева.

Вершины дерева – это ситуации или состояния, возможные в игре.

Корень дерева отражает начальную ситуацию.

Концевые вершины – это конечные состояния, взвешенные платежами.

Дуги – возможные переходы из состояния под действием стратегии.

 

       Пример:

       Два игрока A, B.

       1 ход (личный) А выбирает цифру 1 или 2.

2 ход (случайный) Если герб, то В сообщается о выборе А, иначе – нет.

3 ход (личный) В выбирает 3 или 4.

 

Итог: Суммируются выборы игроков А и В, и если сумма чётная, то В выплачивает А, в противном случае А выплачивает В.

 

                       

 

 

 

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

       Следовательно, данная игра распадается на две игры: с полной и с неполной информацией.

           

       Стратегии А:                                Стратегии В:

       A₁ (1), A_i (2)                                  8 стратегий.          B = (a, b, d)   

                                                                   B₁ = (3, 3, 3)                          

                                                                   B₂ = (3, 3, 4)             S₂ S₃ S₄

                                                                   …

                                                              B₈ = (4, 4, 4)

                                                                                   

                                                                                   

Построение дерева игры. Поиск на дереве игры.

 

- полный перебор (“в глубину”, “в ширину”, комбинированные методы).

- сокращённый перебор (использование оценочных функций)

       - точная оценка (будет получено оптимальное решение)

- эвристическая оценка (нет гарантий получения оптимального решения, будет получено допустимое решение).

           

Определение.

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

 

Определение.

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

 

       Оценка алгоритма – это оценка временных ресурсов, требуемых для оценки вершин.