Лекции в печатном виде (990087), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Бесконечные

Непрерывные

Бесконечные

N лиц

Коалиционные (кооперативные)

Некоалиционные (некооперативные)

2-х лиц

Антагонистические (игры с нулевой суммой)

(интересы сторон противоположны)

Неантагонистические (интересы сторон не совпадают)

С полной информацией (если игроку, делающему личный ход известна вся предыстория игры)

С неполной информацей

С нулевой суммой (суммарный платёж равен нулю)

С ненулевой суммой

О дноходовые

Многоходовые

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

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

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

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

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

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

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

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

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

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

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

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

Пример:

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

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

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

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

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

1 ход S

(Л)

1 2

2 ход

(С) Г Р Г Р

3 ход

(Л)

3 4 3 4 3 4 3 4

4 -5 4 -5 4 -5 4 -5

S1

S3

S2

S4

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

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

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

A₁ (1), A_i (2) 8 стратегий. B = (, ,)

B₁ = (3, 3, 3)

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

…

B₈ = (4, 4, 4)

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

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

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

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

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

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

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

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

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

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

Методы сокращения перебора.

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

- эвристические методы (учитывают специфику задачи).

Универсальные методы

Метод максимина.

Метод заключается в максимизации выигрыша, при минимизации проигрыша.

(при отсутствии дополнительной информации). Этот метод позволяет отсекать неперспективные направления.

Игрок А: (MAX)

Игрок В: (MIN)

Идея алгоритма:

1. Строится полное поисковое дерево на ту глубину, которую возможно позволить по затратам памяти, времени и т.д.. Число ходов должно быть чётно.

2. Концевые вершины дерева оцениваются оценочной функцией.

3. Совершается обратное движение по дереву от концевой к начальной вершине. Выбирается лучший ход игрока А.

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

Пример:

S₀

3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 8 8 3 2 7 9

(Внизу - выигрыши А. В стремится их минимизирует.)

A

5

5

3

B

A

B

7

5

1

1

5

3

7

2

3

4

7

3

2

4

3

2

7

Метод отсечения

Идея метода была предложена Дж. Маккарти в 1961 г.

В основе метода лежит то, что процессы построения и отсечения дерева происходят одновременно.

Существуют 2 случая  отсечения:

1. Неглубокое(простое)  отсечение.

2. Глубокое  отсечение.

1.Неглубокое  отсечение

Рассмотрим следующее дерево:

S

A A

A B

f(A)= …………

B

C

f(C)=z

Пусть на известны оценки f(A)= и f(C)=z. Докажем, что если f(C), то ветви, исходящие из вершины B (на рисунке обозначенные синим цветом) можно отсечь.

Т.к. игрок B стремится минимизировать оценочную функцию, следовательно оценка вершины B будет не больше z.

Т.к. оценка вершины B - f(B)  f(C)  , следовательно вершина B не перспективна (потому что f(A)=, а игрок A стремится максимизировать оценочную функцию).

Все вышесказанное справедливо для -отсечения.

Для -отсечения :

• ход делает игрок B

• f(A)= 

• f(C)= w

2.Глубокое  отсечение

Рассмотрим следующее дерево:

S

A A

A … ………… B

f(A)=

B

C ……

A

D

……

B

E ……

f(E)=z

Пусть на известны оценки f(A)= и f(E)=z. Докажем, что если f(E), то ветви, исходящие из вершины D (на рисунке обозначенные синим цветом) можно отсечь.

Т.к. игрок B стремится минимизировать оценочную функцию, следовательно оценка вершины D будет не больше z (f(D)  f(E)=z ).

Т.к. игрок A стремится максимизировать оценочную функцию,

следовательно оценка вершины С будет не меньше оценки вершины D (f(C)f(D)).

Возможны 2 случая:

1). f(C)=f(D) , тогда f(C)=f(D)  f(E)  - т.е. имеем неглубокое  - отсечение.

2). f(C)f(D), тогда вершина D для получения оценки f(C) не использовалась.

Пример.

5 S

A A

5 3

B

5 7 3=z

A

 5 3 7=w=5 3

B

3 1 4 1=z=1 6 5 3 5 8 9 7 3=z 4

 возрастает при построении оценки снизу вверх

 убывает при построении оценки снизу вверх

Пусть оценивается дерево на n уровней. На каждом уровне имеется m вариантов выбора. Тогда сложность вычислений

для метода максимина -

для метода  отсечений -

(при больших n  )

Недостатки методов максимина и  отсечений

1). Оба метода не являются стратегиями и базируются на классических

переборных алгоритмах, с использованием оценочной функции.

2). Эффект горизонта (никакие жертвы, которые не дают выигрыш в пределах

обозрения программой не принимаются).

Пример.

Построение оценочной функции для игры в шахматы.

f(s)= ,

f1 – оценка, учитывающая алгебраическую стоимость фигур;

f2 – оценка, учиьываюшая относительную безопасность короля;

f3 – оценка, учитывающая подвижность фигур;

f4 - оценка, учитываюшая степень контроля центра;

f5 - оценка, учиваюшая пешечный строй;

f6 – оценка, учитывающая аттакующие позиции;

Матричное представление парной антагонистической игры.

Число стратегий конечно.

Игрок A: {A_i} i=1…m

Игрок B: {B_j} j=1…n

a_ij – это выигрыш игрока A при выборе им стратегии A_i, и игрок B отвечает ему стратегией B_j.

Пример.

1 ход S

(Л)

1 2

2 ход

(С) Г Р Г Р

3 ход

(Л)

3 4 3 4 3 4 3 4

4 -5 4 -5 4 -5 4 -5

S1

S3

S2

S4

Построим матрицу игры. Возможны два случая:

1. Ситуация с неполной информацией. (Игроку В не сообщается о выборе игрока А).

А

1. 2

В

3 4 3 4

4 -5 -5 6

Характеристики

Список файлов лекций