Основы теории игр

Слайд 1. Основы теории игр

Информатика, 11 класс

Слайд 2. Что изучает теория игр

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

В информатике теория игр помогает моделировать переговоры, конкуренцию алгоритмов, распределение ресурсов и поведение агентов в компьютерных системах.

Слайд 3. Основные элементы игры

Игроки — участники конфликта или сотрудничества.

Стратегия — правило выбора действий.

Ход — конкретное действие игрока в определённый момент.

Исход — результат выбранных стратегий.

Выигрыш — оценка результата для игрока.

В играх с нулевой суммой выигрыш одного равен проигрышу другого.

Слайд 4. Стратегия и оптимальное решение

• Доминирующая стратегия всегда даёт игроку результат не хуже других доступных стратегий.

• Осторожная стратегия ориентирована на лучший результат в худшем случае.

• Равновесие — ситуация, в которой игрокам невыгодно менять свой выбор в одиночку.

• Оптимальный выбор зависит не только от собственных возможностей, но и от поведения соперника.

Слайд 5. Матрица выигрышей

Матрица показывает выигрыши при каждой паре стратегий. В каждой клетке записана упорядоченная пара: первое число относится к игроку A, второе — к игроку B.

Задание: найдите для каждого игрока лучший ответ на каждую стратегию соперника.

Слайд 6. Дерево решений в игре

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

Такое представление используют алгоритмы минимакса: один игрок стремится увеличить итоговую оценку, а другой — уменьшить её.

Слайд 7. Алгоритм минимакса

Алгоритм минимакса применяют в играх с полной информацией, когда состояние игры и возможные ходы известны.

1. Построить дерево возможных продолжений.

2. Оценить конечные позиции с точки зрения выбранного игрока.

3. На ходах одного игрока выбрать максимальную оценку.

4. На ходах соперника выбрать минимальную оценку.

5. Передать полученную оценку к корню дерева.

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

Слайд 8. Где встречается теория игр

Компьютерный соперник выбирает ход на основе оценки будущих позиций.

Узлы распределяют ресурсы и учитывают действия других участников.

Участники выбирают ставки, стремясь получить лучший результат.

Защитник и атакующий выбирают действия в условиях противодействия.

Слайд 9. «Лучшее решение определяется не только собственными возможностями, но и тем, что могут сделать другие участники»

— Основной принцип стратегического мышления

Слайд 10. Итоги и задание

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

• Матрица выигрышей удобна для одновременного выбора стратегий.

• Дерево решений показывает последовательность ходов и возможные исходы.

• Минимакс помогает выбирать ход в игре с противодействующим соперником.

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