# Позиционные игры

В рассмотренных ранее играх множество стратегий было неизменным. В позиционных играх анализируется поэтапное принятие решений. Множество стратегий текущего этапа определяет совокупность стратегий для следующего этапа

В качестве модели игры используют **деревья решений** (графическое изображение логической последовательности решений)

Позиционная игра - безкоалиционная игра, моделирующая процесс принятия решения игроками в условиях меняющихся во времени, в условиях неполной информации

Процесс игры состоит в последовательном переходе из одного состояния игры в другое состояние. Выбор действия может осуществляться либо выбором 1 из возможных действий либо случайно.

Примеры: крестики нолики, шашки, шахматы, карточные игры

Конкретное состояние игры называют **узлами** или **позициями игрока**. Возможные выборы в каждой позиции называют **альтернативами**.

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

Окончательные вершины обозначаются через ti (выйгрыш одного из игрока - обычно выйгрыш игрока А. Тогда выйгрыш игрока Б ему противоположен)

Для каждого шага возможно сколько угодно альтернатив. *В задачах будет чаще всего рассматриваться ситуация с 2 альтернативами.*

Процесс игры состоит в переходе из начальной позиции через промежуточные позиции.

ti определяет единственную цепь (последовательность позиций). Такую цепь называют **партией**.

Различают игры **с полной и неполной информацией.**

В играх с неполной информацией игрок не знает точно в какой позиции (вершине дерева) он находится. Множество позиций в которых он может находиться - **информационное множество**. На графе эти вершины изображают пунктирной линией. Если информационное множество всех игроков содержит 1 элемент - то это игра с полной информацией

#### Нормализация позиционной игры

Любой из игроков может выбрать для себя определенную стратегию на всю игру: набор узлов/позиций. Для каждого игрока количество стратегий = количество альтернатив, которое можно выбрать из своей вершины.

**Чистая стратегия игрока** - заранее определенная последовательность ходов игрока

Это позволяет сводить игру к матричной, биматричной или статистической игре. Процесс сведения игры к другому типу - **нормализация позиционной игры**.

Рассмотрим нормализацию двух игр:

1) первый ход осуществляет игрок А. Он выбирает 1 из 2 альтернатив. x = 1 или x = 2. x принадлежит {1,2}

2) второй ход осуществляет игрок B. Он выбирает 1 из 2 альтернатив: y принадлежит {1,2}

3) Игроки расплачиваются в соответствии с функции выйгрыша W(x,y). W(1,1) = 1. W(1,2) = 1. W(2,1) = 2. W(2,2) = 2


4. Начнем нормализацию: Найдем стратегии игроков: Стратегии игрока A: A1 = { x= 1}. A2 = {x = 2}. Стратегии игрока B: [y1,y2], где y1,y2 выбираются из {1,2} B1 = [1,1] B2 = [1,2]. B3 = [2,1], B4 = [2,2]. y = y1 если x = 1. y = y2 если x = 2. B1 означает, что y = 1 при любом x. B2 означает, что y = x. B3 означает что y != x. B4 означает, что y =2 при любом x
5. Найдем выйгрыш игрока A с помощью таблицы выйгрышей

| W | B1 [1,1] | B2 [1,2] | B3 [2,1] | B4 [2,2] |
| ----------- | -------- | -------- | -------- | -------- |
| A1 ( x = 1) | W(1, 1) | W(1,1) | W(1,2) | W(1,2) |
| A2 ( x= 2) | W(2,1) | W(2,2) | W(2,1) | W(2,2) |

6. Строим матрицу игры
$$
P = \begin{pmatrix}1 & 1 & -1 & -1 \\ -2 & 2 & -2 & 2\end{pmatrix}
$$
Игра сведена к игре размерности 2x4. Применим принцип доминирования и сократим столбцы

$$
P = \begin{pmatrix}1 & -1 \\ -2 & -2\end{pmatrix}
$$

Седловая точка: (A1, B3). -1 = Vа

1. первый ход осуществляет игрок А. Он выбирает 1 из 2 альтернатив. x = 1 или x = 2. x принадлежит {1,2}
2. второй ход осуществляет игрок B. Он выбирает 1 из 2 альтернатив: y принадлежит {1,2}, не зная хода игрока А.
3. Игроки расплачиваются в соответствии с функции выйгрыша W(x,y). W(1,1) = 1. W(1,2) = 1. W(2,1) = 2. W(2,2) = 2
4. Начнем нормализацию: Найдем стратегии игроков: Стратегии игрока A: A1 = { x= 1}. A2 = {x = 2}. Стратегии игрока B: B1 = { y= 1}. B2 = {y = 2}.
5. Найдем выйгрыш игрока A с помощью таблицы выйгрышей

| W | B1 | B2 |
| ---- | ------ | ------ |
| A1 | W(1,1) | W(1,2) |
| A2 | W(2,1) | W(2,2) |

6. Строим матрицу

$$
P = \begin{pmatrix}1 & -1\\-2 & 2\end{pmatrix}
$$

В этой игре есть решение только в смешанных стратегиях, отсутствует седловая точка.

Xa = (p, 1-p). Xb = (q, 1-q)

p - 2(1-p) = -p + 2(1-p) = Va

q - (1-q) = -2q + 2(1-q) = Va

Эту игру можно рассмотреть как биматричную, если каждый получает свой выгрыш. Возьмем выгрыши:

t1 = (1, 1). t2 = (-1, 0). t3 = (-2,-2). t4 = (2,1)

ДЗ: составить матрицы для обоих игроков, найти решение.

---

Если у одного из игроков снижается уровень информации о стратегии другого игрока, то его выйгрыш может уменьшиться, а количество его стратегий сокращается.