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

Урок 8. Знакомство с теорией игр

Знакомство с теорией игр
Инвариант стратегии
Необходимо запомнить

ВАЖНО!

На уроке вы научились:

  1. Cтроить дерево игры.
  2. Находить выигрышные стратегии.
  3. Решать 26 задачу ЕГЭ по информатике.

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

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

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

Игра «Крестики-нолики»
Задача 26 из ЕГЭ

Давайте разберем несколько задач 26 из ЕГЭ

Задача №1

Два игрока играют в следующую игру. На координатной плоскости стоит фишка. Игроки ходят по очереди. В начале игры фишка находится в точке с координатами (1, 0). Ход состоит в том, что игрок перемещает фишку из точки с координатами (x, y) в одну из трёх точек: или в точку с координатами (x+3, y), или в точку с координатами (x,y+5),или в точку с координатами (x+2,y+ 4). Выигрывает игрок, после хода которого расстояние по прямой от фишки до точки с координатами (0, 0) больше 8 единиц. Кто выиграет при безошибочной игре обоих игроков — игрок, делающий первый ход, или игрок, делающий второй ход? Ответ обоснуйте.

Решение.

Квадрат расстояния от фишки до точки с координатами (0, 0): r2 = x2 + y2. Побеждает игрок, после хода которого r2> 64. Алгоритм выигрышной стратегии определим при помощи дерева всех возможных партий.

Построим дерево игры, где зеленым цветом обозначим выигрыш первого игрока, а красным - второго. Если при каком-либо ходе игрок выигрывает, то рассматривать остальные варианты не имеет смысла.

Из дерева видно, что первому игроку выгодно сходить первым ходом (х+3, y). Тогда как бы ни сходил второй игрок, первый ВСЕГДА выиграет

  

Задача №2

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или два камня, или увеличить количество камней в куче в два раза. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.

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

Кто из игроков выиграет в игре, если в куче было 20 камней, при этом каждый игрок играет безошибочно.

Решение

После первого хода Пети в куче будет 21, 22 или 40 камней. Если в куче станет 40 камней, Ваня удвоит количество камней и выиграет первым ходом. Если в куче будет 21 или 22 камней Ваня сходит в соответствии с деревом решений:

Предметы

По алфавиту По предметным областям

Классы

1 2 3 4 5 6 7 8 9 10 11
angle-skew-bottom mix-copy next-copy-2 no-copy step-1 step-2 step-3 step-4 step-5 step-6 step-6