Позиционные игры с полной информацией

Позиционные игры с полной информацией

Позиционные игры с полной информацией

Позиционные игры с полной информацией

Позиционные игры с полной информацией

По этой ссылке вы найдёте полный курс лекций по математике:

Решение задач по математике

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

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

Однако известное доказательство существования равновесной ситуации неконструктивно и не дает эффективных приемов фактического нахождения решения игры. Позиционные игры с полной информацией И такие способы (стратегии) в шахматах не найдены до сих пор, и даже неизвестно, какая из перечисленных возможностей имеет место на самом деле. Иное дело с игрой крестики-нолики: стратегий в ней немного и она разобрана до самого конца — существуют оптимальные чистые стратегии, ведущие игроков к ничьей.

Рассмотрим несколько примеров. 1. Как нетрудно заметить, двухходовая игра из примера 11 является игрой с полной информацией. Ее нормализация приводит к матрице с седловой точкой (см. пример 13). 2. «Выкладывание монет на стол*. Два игрока поочередно кладут монеты одинаковых размеров на обыкновенный стол, всякий раз выбирая произвольное доступное место для монеты (взаимное накрывание монет не допускается). Тот из игроков, кто положит монету, не оставляющую места для новых монет, выигрывает.

Это игра с полной информацией. Существует вполне определенная стратегия, обеспечивающая выигрыш тому из игроков, кто начинает игру. А именно, начинающий игру должен положить первую монету точно в центр стола и на каждый ход противника отвечать симметричным ходом. Исход игры от стратегии второго игрока не зависит. 3. «Переговоры*.

В переговорах участвуют две стороны А и В, В слегка идеализированном варианте это может выглядеть, например, так. Сначала сторона А высказывает одно из нескольких предложений, способных заинтересовать сторону В. Затем сторона В, ознакомившись с предложением стороны А, высказывает одно из нескольких встречных предложений, способных, по ее мнению, заинтересовать сторону А.

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

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

1-й ход делает сторона А. она выбирает одно из двух возможных предложений — число х из множества двух чисел {1, 2}. 2-й ход делает сторона В: она выбирает число у из множества двух чисел {I, 2}, зная число х, предложенное стороной А. 3-й ход делает сторона А: она выбирает число z из множества двух чисел {1, 2}, зная о предложении стороны В на 2-м ходе и помня собственное предложение на 1-м ходе. После этого сторона А либо получает вознаграждение (например, в виде кредита от стороны В), либо выплачивает стороне В штраф.

Возможно вам будут полезны данные страницы:

Амиды карбоновых кислот
Проекции отрезка прямой линии
Вычисления по стехиометрическим схемам
Металлическая связь примеры

Все эти возможности описываются функцией выигрышей W(x, у, г), заданной следующей таблицей Позиционные игры с полной информацией Графическое представление этой игры показано на рис. 11. Ясно, что описанная позиционная игра является игрой с полной информацией. Начнем с описания возможных стратегий игрока В. Поскольку игроку В выбор игрока А на 1-м ходе известен, то у игрока В те же четыре стратегии, что и в при- Рис. 11 мере 13. С описания возможных стратегий игрока А дело обстоит немного посложнее — их восемь.

Чистая стратегия игрока А в данной игре описывается упорядоченной тройкой Здесь — альтернатива, которую игрок А выбирает на 1-м ходе, альтернатива, которую игрок А выбирает на 3-м ходе, если на 2-м ходе игрок В выбрал выбрал первую альтернативу альтернатива, которую игрок А выбирает на 3-м ходе, если на 2-м ходе игрок В выбрал вторую альтернативу Например, выбор игроком А стратегии (I, (2, 1]) означает, что на 1-м ходе игрок А выбирает х = I. а на 3-м z — 2, если игрок В выбрал если игрок В выбрал у = 2.

Тем самым, у игрока А восемь чистых

стратегий: Покажем теперь, как в зависимости от применяемых стратегий определяются элементы таблицы выигрышей игрока А. Пусть, например, игрок А выбрал стратегию , а игрок В —стратегию Вз — Тогда вытекает, что , что z = 1. Отсюда Рассчитывая по этой же схеме все остальные элементы таблицы выигрышей, в итоге получим Вследствие того, что рассматриваемая позиционная игра является игрой с полной информацией, полученная матрица имеет седловую точку при любой функции выигрышей.

В этом легко убедиться, произвольно выбирая значения параметров При увеличении числа ходов стратегии в позиционной игре с полной информацией строятся по аналогичной схеме. Рассмотрим, например, четырех*одовую позиционную игру. 1-й ход делает игрок .А: он выбирает число х из множества двух чисел {1,2}. 2-й ход делает игрок В: он выбирает число у из множества двух чисел {1,2}, зная число х, выбранное игроком А на 1-м ходе.

3-й ход делает игрок А: он выбирает число г из множества двух чисел {1,2}, зная число у, выбранное игроком В на 2-м ходе, и помня свой выбор числа х на 1-м ходе. 4-й ход делает игрок В: он выбирает число и из множества двух чисел {1, 2}, зная число z, выбранное игроком А на 3-м ходе, помня свой выбор числа у на 2-м ходе и зная выбор игрока А на 1-м ходе — число ж.

После этого игроки А и В расплачиваются в соответствии с заданной функцией выигрышей lV(z,y,z,«). В этой игре стратегии у игрока А те же, что и в задаче, рассмотренной выше: каждая из них задается тройкой вида (*, [«|>*г))> и общее их число равно восьми. Что касается стратегий игрока В, то в этой игре их шестнадцать и каждая из них задается четверкой вида Матрица выигрышей игрока А в данной игре имеет размер 8 х 16. Покажем, как определяются ее элементы в зависимости от применяемых стратегий игроков.

Пусть, например, игрок А выбрал стратегию а игрок В стратегию . Из того, что (ui.tij) — (1.2J, получаем, что и = I. Отсюда следует, что искомый элемент матрицы выплат равен Остальные элементы матрицы вычисляются аналогично. Так как эта позиционная игра также является игрой с полной информацией, то получаемая матрица будет иметь садловую точку. В рассмотренных примерах основное внимание было уделено описанию процесса нормализации позиционной игры — построению дерева игры и информационных множеств, выработке стратегий игроков и вычислению элементов платежной матрицы.

Следующий естественный шаг — отыскание цены игры и оптимальных стратегий игроков — проводится методами, о которых рассказывалось в главе, посвященной матричным играм. Мы достаточно подробно остановились на позиционных играх двух лиц, где были явно выражены интересы одного из игроков (игрока А). Следует, однако, иметь в виду, что в одних случаях интересы игрока Б могут быть полностью противоположными интересам игрока А, в то время как в других вполне может оказаться, что то, что хорошо для одного игрока, не обязательно плохо для другого. Приведем два простых примера.

Пример А. 1-й ход. Игрок А выбирает число х из множества двух чисел {1,2}. 2-й ход. Игрок В выбирает число у из множества двух чисел {1,2}, зная выбор числа х игроком Л. Функции выплат игрокам соответственно — задаются так: Позиционные игры с полной информацией Дерево игры показано на рис. 12. Исход игры зависит от того, каковы намерения игрока В — максимизировать свой выигрыш: или максимизировать свой относительный выигрыш: В первом случае это достигается так.

Во втором случае: Пример Б. Игра задается деревом (см. рис. 13). 1-й ход. Игрок А выбирает число х из множества двух чисел {1,2}. Если х = 1, то каждый из игроков получает свой выигрыш, равный 2. Если х = 2, то право 2-го хода получает игрок В, где он и выбирает выбирает число у из множества двух чисел {1,2}. При у = 1 выигрыш игрока А равен \, а игрока В — 4.

При у = 2 оба игрока получают поровну — по 3. В случае, когда каждый из игроков стремится к получению максимального выигрыша и любые виды кооперации запрещены, исход игры ясен — игрок А выбирает z = 1, и игра заканчивается. Но при х = 2 и у = 2 каждый из игроков получает по 3 (такой исход предпочтительнее простейшего (1, 1)), и, если допустить соглашение между игроками, это обстоятельство вполне может изменить исход игры.