Конспект урока по информатике. Группа №91. Тема: «Дерево игры»

Конспект урока по информатике

Группа №91

Курс 2

Тема: «Дерево игры»

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

При этом игра в футбол будет сильно отличаться от игры в шахматы. Так как в играх типа теннис, баскетбол может вмешиваться третьи стороны: ветер, солнце и т. д. и не всегда ясно к чему приведет тот или иной ход игрока. Если же игрок точно знает, к какой позиции приведет его выбранный ход, то она называется игрой с полной информацией, к таким играм мы отнесем шахматы, шашки, «крестики-нолики» и много других интересных игр, в которых будет участвовать только игроки.

Давайте начнем с простой игры. Имеется горка из n монет. Маша и Петя должны каждым своим ходом делить одну горку на две таким образом, чтобы в каждой из них было не менее 2. При этом если игрок не сможет этого сделать, то он проигрывает.

Для примера, рассмотрим задачу, когда n=10. Тогда Маша может сходить (2,8), (3,7), (4,6) и (5,5). Запишем это в виде графа. (Такой граф мы будем называть деревом игры). Продолжим рисовать граф. Его анализ покажет, что Маше не выгодно ходить первым ходом (2,8) или (4,6), что может привести к позиции (2,2,2,4), которая приведет ее к проигрышу. Поэтому если она хочет выиграть своим первым ходом она сходит (5,5) или (3,7), что гарантированно приведет ее к победе независимо от ходов Пети. Это и будет ее выигрышной стратегией.

Итак, выигрышная стратегия — это такое правило совершения ходов, при соблюдении которого игрок добьется выигрыша при любых ответных ходах противника.

Для построения дерева игры необходимо перебрать все возможные ходы игроков, что может потребовать огромного количества времени. Так, если игра состоит в выборе одного из 2 шагов и будет сделано n ходов, то потребуется рассмотреть 2ⁿ последовательностей. Например, всего лишь 10 ходов приведет к дереву из 1024 листьев.

Давайте построим дерево игры для задачи, рассмотренной ранее, но возьмем количество монет — 9.

Ясно, что, если два хода игрока приводят к одному и тому же результату, рассматривать их как разные не имеет смысла.

Вывод: Анализировать надо не последовательность ходов, а позиции, приводящие к выигрышу

Рассмотрим следующую игру:

На поле 10×10 находится фишка. За один ход ее можно переместить на любое количество клеток вправо или вниз, либо по диагонали вправо и вниз. Два игрока по очереди делают ходы. Проигрывает тот, кто не сможет сделать ход. Ясно, что проигрышная позиция здесь только одна — это правый нижний угол.

Рис. 1

Получается, что если за один ход можно попасть в эту клетку, то ты гарантированно придешь к победе. Поставим «+» во все такие клетки (рис.1).

Далее проставим знаком «–» клетки из которых нельзя попасть в «–» за 1 ход, но любой ход приводит в клетку «+» (рис.2).

Рис. 2

Следуя этим рассуждениям, заполним таблицу (рис.3)

Рис. 3

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

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

Однако таких вариантов очень много и справиться с перебором всех не может ни только человек, но и компьютер. При этом человек «интуитивно» может отбрасывать некоторые из неперспективных вариантов основываясь на не совсем логичных обоснованиях. Такие обоснования называются эвристиками.

Эвристика — это правило, сокращающее число потенциальных вариантов перебора.