МатБюро Статьи по математикеДерево решений в теории игр

Дерево решений в теории игр

Как сделать правильный выбор в стратегически важных ситуациях, когда успех зависит от выбора других «участников проекта» или от обстоятельств, с Вами не связанных? Изучением этой темы занят отдельный раздел прикладной математики – теория игр, которая помогает "математически" выбрать поведение в таких ситуациях.

Что делать? Создать модель, предсказывающую итоговое значение (например, выигрыш, сумму прибыли или затрат) при различных исходных данных и условиях.

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

Понравилось? Добавьте в закладки

Решение на ветвях. Не случайные случайности

дерево решений в теории игр

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

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

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

Рассмотрим пример создания дерева решений для задачи теории игр.
Колесо разделено на две области: белую и красную и управляется двумя кнопками: сильное и легкое вращение. В белой области колесо останавливается с вероятностью 0,3. В красной – 0,7.

платежная матрица задача дерево решений

Построим дерево решений:
1) Выбираем первое звено – исходное действие, которое может развиваться по нескольким «веткам» - вращение колеса.
2) Определяем критерий, по которому далее будет происходить распределение – кнопка для сильного (С) или легкого (Л) вращения.
3) Параметр разветвления – цвет области на колесе.
4) Над «ветвями» указываем возможные варианты (белый (Б) и красный (К) цвет) и вероятности их появления (учтем их далее – 0,3 и 0,7, соответственно).
5) Указываем результат – «лист» на каждой «ветке», используя исходную таблицу возможных выигрышей.
6) Вычисляем вероятность получения прибыли для каждого «листа».
7) Определяем полную вероятность для каждого варианта по исходному критерию (для каждой из двух кнопок, которые можно выбрать).

пример задачи дерево решений в теории игр

Подведем итоги игры:
- если выберете легкое вращение, выигрыш 240+140 = 380 (вариант гарантированно принесет прибыль);
- для сильного вращения получаете (-750)+700 = (-50) (выбор может привести к затратам).

Подробные примеры: Задачи теории игр с решениями.

Понравилось? Добавьте в закладки

Дополнительно:


Любые задачи теории игр на заказ. Только на отлично.