Погода
Календарь
Май 2019
Пн Вт Ср Чт Пт Сб Вс
« Сен    
 12345
6789101112
13141516171819
20212223242526
2728293031  
Страницы сайта

Выигрышная стратегия.

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

Кто выиграет при стратегически правильной игре?

  • для того чтобы определить, какой из игроков выиграет при стратегически правильной игре, необходимо ответить на вопросы:
  • Может ли какой-либо из игроков выиграть, независимо от ходов других игроков?
  • Что должен сделать игрок с выигрышной стратегией первым ходом, чтобы он смог выиграть, независимо от действий ходов игроков?

Рассмотрим пример:
Игра: в кучке лежит 5 спичек; играют два игрока, которые по очереди убирают спички из кучки; условие: за один ход можно убрать 1 или 2 спички; выигрывает тот, кто оставит в кучке 1 спичку

Решение:

  • Будем использовать метод построения дерева. Первый играющий может убрать одну спичку (в этом случае их останется 4) или сразу 2 (останется 3), эти два варианта отобразим при помощи дерева:
  • если первый игрок оставил 4 спички, второй может своим ходом оставить 3 или 2; а если после первого хода осталось 3 спички, второй игрок может выиграть, взяв две спички и оставив одну:
  • если осталось 3 или 2 спички, то 1-ый игрок (в обеих ситуациях) выиграет своим ходом:

проанализируем стратегию игры:

  • если первый игрок своим первым ходом взял две спички, то второй сразу выигрывает; если же он взял одну спичку, то своим вторым ходом он может выиграть, независимо от хода второго игрока;
  • итак, убрав всего одну спичку первым ходом, 1-ый игрок всегда может выиграть на следующем ходу;
  • тогда как второй игрок не может выиграть, независимо от действий первого: потому что, если первый игрок сначала убрал одну спичку, второй всегда проиграет.

Ответ: при правильной игре (стратегии игры) выиграет первый игрок; для этого ему достаточно своим первым ходом убрать одну спичку.

Решение заданий

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

Игра завершается в тот момент, когда количество камней в куче становится не менее 32. Если при этом в куче оказалось не более 54 камней,  то победителем считается игрок, сделавший последний ход. В противном случае победителем становится его противник. Например, если в куче было 29 камней и Паша удвоит количество камней в куче, то игра закончится  и победителем будет Валя. В начальный момент в куче было S камней,  1 ≤ S ≤ 31.

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

Выполните следующие задания. 1.а) При каких значениях числа S Паша может выиграть в один ход? Укажите все такие значения и соответствующие ходы Паши. б) У кого из игроков есть выигрышная стратегия при S = 30, 29, 28? Опишите выигрышные стратегии для этих случаев. 2.У кого из игроков есть выигрышная стратегия при S = 15, 14? Опишите соответствующие выигрышные стратегии. 3.У кого из игроков есть выигрышная стратегия при S = 13? Постройте дерево всех партий, возможных при этой выигрышной стратегии (в виде рисунка или таблицы). На рёбрах дерева указывайте, кто делает ход; в узлах – количество камней в позиции.

2.  Два игрока играют в игру. На координатной плоскости в точке с координатами (-3;2) стоит фишка, игроки ходят по очереди. Ход состоит в том, что игрок перемещает фишку в одну из точек (х+5;у), (х;у+4), (х+3;у+3). Выигрывает игрок, после хода которого расстояние по прямой от фишки до начала координат больше 12. Кто выигрывает при безошибочной игре обоих игроков, игрок делающий первый шаг или игрок, делающий второй ход. Каким должен быть первый ход выигрышного игрока.

3. Два игрока играют в «Верёвку». Игроки ходят по очереди. В начале игры верёвка имеет длину 14 см. Ход состоит в том, что игрок отрезает от верёвки кусок длиной 3 см или 4 см. Выигрывает тот игрок, на чьем ходе закончится верёвка (последний выигрышный ход может быть < 3). Кто выиграет при безошибочной игре двух игроков – игрок, делающий первый ход, или игрок, делающий второй ход. Ответ обоснуйте?

Top