Изучение предмета Информатика 11 класс
Информатика 11 класс
Урок№8 - Знакомство с теорией игр.
Модели для построения стратегий
В «Словаре иностранных слов» написано, что стратегия — это наука ведения борьбы по определенным правилам. Как мы знаем, одним из методов, применяемых в науке, является построение моделей на подходящем формальном языке. На этом уроке мы попытаемся построить такие модели, которые помогут в построении стратегии — ведении борьбы по заданным правилам. Любая борьба происходит, по крайней мере, между двумя сторонами и преследует определенные цели. Как достичь этих целей? Вот на какой вопрос мы попытаемся сегодня ответить на уроке.
мы узнаем:
• основные алгоритмы обработки массивов;
мы научимся:
• записывать основные алгоритмы обработки массивов на языке Паскаль;
мы сможем:
• решать задачи с использованием массивов.
Построение стратегии
Для игр необходимо перебрать все возможные ходы игроков, что может потребовать огромного количества времени. Так, если игра состоит в выборе одного из 2 шагов и будет сделано n ходов, то потребуется рассмотреть 2n последовательностей. Например, всего лишь 10 ходов приведет к дереву из 1024 листьев.
Инвариант стратегии
Как легко заметить, стратегия строится от одной проигрышной ситуации до другой, которую мы пытаемся создать противнику. Поэтому для построения выигрышной стратегии достаточно найти все проигрышные ситуации. Иногда количество таких ситуаций может быть очень велико, поэтому легче найти не все такие ситуации, а попытаться найти свойство, подходящее под проигрышные ситуации и не подходящие под выигрышные. Такое свойство будет называться инвариантом стратегии.
На уроке вы научились:
Cтроить дерево игры.
Находить выигрышные стратегии.
Решать 26 задачу ЕГЭ по информатике.
Если игрок точно знает, к какой позиции приведет его выбранный ход, то она называется игрой с полной информацией, к таким играм мы отнесем шахматы, шашки, «крестики-нолики» и много других интересных игр, в которых будет участвовать только игроки.
Выигрышная стратегия — это такое правило совершения ходов, при соблюдении которого игрок добьется выигрыша при любых ответных ходах противника.
Эвристика — это правило, сокращающее число потенциальных вариантов перебора.