Теория игр и исследование операций. Модели, алгоритмы, сложность: Конспект лекций, страница 19

6)  для каждой позиции sÎS_ij существует нумерация дочерних позиций, и ход игрока состоит в выборе номера дочерней позиции (даже не зная самой позиции, выбор будет однозначным).

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

Пример игры с полной информацией. Одномастка.

Есть два игрока, стол и колода из 2n пронумерованных карт. Случайно карты раздаются поровну между игроками и определяется ХОДЯЩИЙ игрок. Игроки знают свои карты Þ знают карты соперника, т.е. игра идет “в открытую”. ХОДЯЩИЙ выбирает и кладет на стол одну из своих карт, а соперник ОТВЕЧАЕТ своей. Хозяин старшей карты стола получает очко и право ХОДА, карты стола удаляются из игры. Цель игры – набрать максимум очков.

Каждой карте припишем индекс – разность числа своих и чужих карт; старших или равных этой карте. Пусть a – вектор индексов карт ХОДЯЩЕГО, b – вектор соперника. При оптимальной игре индексы, как правило, сохраняются.               Правила редукции:

при ОТВЕТЕ рассматриваем только два варианта: бить (самой младшей бьющей картой–если есть) или отдать (самую младшую), причем если после взятия хозяин старшей карты не меняется, то ответ отдать отбрасываем;

при ХОДЕ отбрасываем мажорируемые по Парето карты (если их индекс не меньше & они младше), ход с одиночки (если это не самая младшая карта ХОДЯЩЕГО) и ход с туза (если остались другие варианты ХОДА).                Двойные стрелки отмечают лучший ход. Жирные цифры помечают карты игроков, ? – варианты хода, * - ХОД, цифры внизу – последовательность ходов в игре без вариантов.

На этом построение дерева можно закончить. Число висячих вершин равно 4. (6!)² ≈500 000.

На дереве игры для S1 мы использовали процедуру a-b отсечений.

Сколько вообще может быть таких отсечений? Что такое  a-b отсечение?

Объем дерева игры = mⁿ. Пусть есть кто-то, кто подсказывает вариант игры, тогда получим рекуррентное соотношение для трудоемкости:

T_n^сп=T_n-1+(m-1)T_n-2; T_n^сп=O(n^(m+1)/2) -для сокращенного перебора;

T^пп=mT_n-1=m²T_n-2=…=mⁿ -для полного перебора.

Пример: n=10, m=7. Полный перебор требует 10⁷, а с α–β отсечениями 10⁴ операций.

Если цена игры одинакова при двух вариантах хода, надо учитывать, что соперник может сыграть неверно. Поэтому выбирается ход, максимально обладающий "ловушечными" свойствами. Антиловушечный метод - игроки избегают ситуации, в которых сами могут сделать ошибку.

Способы игры:

Интересные позиции:

+0110000111 – старшая единица активна (должна взять очко) Þ ход с нее плох – ее побьют.

+0110001011 – оба хода верные, но ход с младшей лучше – это «антиловушка».

+0110000101011011 – ход со старшей (активной) единицы плох – ей отдадут, но промежуточные карты уменьшат свой индекс и число активных карт уменьшится.

+011000111001 – просто интересная позиция. Верный розыгрыш – ход со старшей, бить, старшая (ловушка), отдать, старшая (ловушка), бить.

+110010110100,  100011001110, 1001011010, 1000111010,  0110011010, 10010101, 01100101.

Стратегии позиционной игры.

Def: Стратегия - это правило однозначного выбора хода в любой возможной позиции.

В терминах дерева игры стратегия i-ого игрока - это поддерево, в котором в позициях с ходом i-ого игрока есть только одна дочерняя, а в позициях с ходом других игроков - все дочерние из дерева Г. Число стратегий - число различных таких поддеревьев дерева игры.

Правило подсчета числа стратегий: в позициях со своим ходом числа стратегий суммируются, а в позициях с ходом соперника - перемножаются.

Пример:   Посчитаем число стратегий в игре «крестики - нолики» размера 3*3.