Презентация на тему "Дерево игры. Поиск выигрышной стратегии" 11 класс

Содержание

• 
  Слайд 1

  Дерево игры

  Поиск выигрышной стратегии Учитель информатики и ИКТ МБОУ СОШ № 7 г. Оха Сахалинской области Сергиенко Татьяна Геннадьевна

• 
  Слайд 2

  Что нужно знать:

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

• 
  Слайд 3
  

  Все позиции в простых играх делятся на выигрышные и проигрышные Выигрышная позиция – это такая позиция, в которой игрок, делающий первый ход, может гарантированно выиграть при любой игре соперника, если не сделает ошибку; при этом говорят, что у него есть выигрышная стратегия – алгоритм выбора очередного хода, позволяющий ему выиграть

• 
  Слайд 4
  

  Если игрок начинает играть в проигрышной позиции, он обязательно проиграет, если ошибку не сделает его соперник; в этом случае говорят, что у него нет выигрышной стратегии; таким образом, общая стратегия игры состоит в том, чтобы своим ходом создать проигрышную позицию для соперника

• 
  Слайд 5
  

  выигрышные и проигрышные позиции можно охарактеризовать так: позиция, из которой все возможные ходы ведут в выигрышные позиции – проигрышная для соперника; позиция, из которой хотя бы один из возможных ходов ведет в проигрышную позицию – выигрышная для соперника, при этом стратегия игрока состоит в том, чтобы перевести игру в эту проигрышную (для соперника) позицию.

• 
  Слайд 6

  Задача

  Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу два камня или увеличить количество камней в куче в два раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 17 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 25. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 25 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 24.

• 
  Слайд 7

  1. При каких S: 1а) Петя выигрывает первым ходом;

  За один ход игрок может добавить в кучу два камня или увеличить количество камней в куче в два раза. Выиграть ходом +2 можно только из S= 23 или 24. Увеличив число камней в 2 раза, он получит число, большее 24 при S от 13 (26) до 24 (48), причём числа 23 и 24 тоже войдут в этот промежуток. Следовательно, выигрышными для первого хода Пети будут все значения S от 13 до 24. S = 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24

• 
  Слайд 8

  1. При каких S: 1б) Ваня выигрывает первым ходом?

  S = 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24 Для ответа на этот вопрос нужно найти позицию, из которой все возможные ходы ведут к выигрышу Вани за 1 ход. Ваня выиграет первым ходом, если после первого хода Пети S = 11 или 12, т.к. любой его ход в этом случае будет выигрышным. 11 + 2 = 13 12 + 2 = 14 11 * 2 = 22 12 * 2 = 24, т.е. при S = 11 или 12 Ваня выиграет первым ходом.

• 
  Слайд 9
  

  2. Назовите три значения S, при которых Петя может выиграть своим вторым ходом?

  Петя может выиграть своим вторым ходом на основе Ваниных выигрышных вариантов, т.е. попав в позицию, которая заведомо могла быть выигрышной для Вани, но стала для него проигрышной, т.к. ход Пети. 11 – 2 = 9 11 на 2 не делится, пропускаем 12 – 2 = 10 12 / 2 = 6 Следовательно, при S = 6, 9, 10 Петя может выиграть своим вторым ходом.

• 
  Слайд 10

  3. При каком S Ваня выигрывает своим первым или вторым ходом?

  Ваня выиграет своим первым или вторым ходом, если оба его хода приведут в промежуток S от 13 до 24 или S = 6, 9, 10. 6 – 2 = 4 4 * 2 = 8 (не входит ни в один промежуток) 9 – 2 = 7 7 * 2 = 14 (подходит) 10 – 2 = 8 8 * 2 = 16 (подходит) Следовательно, при S = 7 или 8 Ваня выиграет своим первым ходом.

• 
  Слайд 11
  

  Остается построить таблицу возможных вариантов игры из позиции S = 7 и 8. Красным цветом выделим позиции, в которых игра заканчивается.

• 
  Слайд 12
  
• 
  Слайд 13
  

  Спасибо за внимание!