Информатика

Выигрышные стратегии в играх

 

На предыдущем уроке мы рассмотрели различные игры и примеры выигрышных стратегий в этих играх.

 

На этом уроке мы на практике научимся составлять алгоритмы выигрышных стратегий в различных играх. Кроме того, мы научимся записывать эти алгоритмы в виде блок-схем.

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

Пример 1.

Двое играют в шашки на доске 8 х 8. При этом запрещается бить шашки соперника или превращать шашки в дамки. Проигрывает тот, кто не может сделать ход. Кто выиграет при правильной игре?

Решение.

Давайте рассуждать логически: на доске изначально16 шашек, вариантов походить у обоих игроков более чем достаточно (рис. 1).

Рис. 1. Шашки

Из этого следует такая подсказка: выигрышная стратегия должна быть простой и не сильно привязанной к правилам самих шашек.

Вспоминаем про один из основных способов построения стратеги: симметрия.

Докажем, что при правильной игре всегда выигрывает второй игрок. Для этого ему достаточно ходить симметрично первому относительно центра доски (рис. 2).

Рис. 2. Симметрия хода

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

Ответ: выигрышная стратегия есть у второго игрока.

 

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

Пример 2. Дана полоска размерами 1 х 99. Двое учеников по очереди делают свои ходы. За один ход разрешается зачеркнуть одну произвольную клетку полоски или какие-то две соседние клетки полоски. Проигрывает тот, кто не сможет сделать ход. Кто выиграет при правильной игре?

Решение.

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

Вырисовывается следующая выигрышная стратегия: первый игрок закрашивает 50-ю клетку полоски. После его хода полоска разбивается на две одинаковые полоски (рис. 3).

Рис. 3. Полоса игры

Теперь задача первого игрока – ходить симметрично тому, как ходит второй игрок. Как видим, у первого игрока всегда будет ход после хода второго игрока (рис. 4).

Рис. 4. Полоса игры

Значит, выигрышная стратегия существует у первого игрока.

Составим четкий алгоритм выигрышной стратегии:

1. Закрасить клетку с номером 50.

2. Если второй игрок закрасил клетку с номером k, то закрасить клетку с номером 100-k.

3. Если второй игрок закрасил клетки с номерами k и k+1, то закрасить клетки с номерами 100-k и 99-k.

Этот алгоритма принесет первому игроку победу.

Составим блок-схему для описания этого алгоритма (рис. 5):

Рис. 5. Блок-схема алгоритма выигрышной стратегии игры

Рассмотрим еще один пример на нахождение выигрышной стратегии.

 

Пример 3.

Двое по очереди ставят крестики и нолики в клетки таблицы 9 х 9. Первый игрок ставит крестики, второй – нолики. В конце игры надо посчитать, сколько строк и столбцов, в которых крестиков больше, чем ноликов. Это количество очков первого игрока. Соответственно, количество строк и столбцов, в которых ноликов больше – это очки второго игрока. Выигрывает тот, у кого больше очков. Кто выиграет при правильной игре?

Решение.

И снова воспользуемся симметрией. У нас опять есть подсказка – нечетное количество клеток доски. Поэтому напрашивается такая стратегия: первый игрок своим первым ходом ставит крестик в центр. А дальше ходит симметрично второму игроку относительно центра (рис. 6).

Рис. 6. Крестики-нолики

Мы получаем, что если в каком-то столбце или строке ноликов больше, то в симметричном ему столбце или строке их, соответственно, меньше. А вот центральные строка и столбец остаются за первым игроком, так как в них в центре стоит крестик, а остальные клетки разбиты на симметричные пары. Значит, при такой игре выиграет первый игрок.

Ответ: выиграет первый игрок.

На этом уроке мы рассмотрели на практике составление выигрышных стратегий.

На следующем уроке мы начнем изучение новой темы – Среда программирования Лого.

---

Шашки

Шашки – одна из самых древних игр (рис. 7).

Рис. 7. Шашки (Источник)

У Платона встречается миф о том, как бог Гермес, придумавший эту игру, предложил богине Луне играть с ним в шашки с тем условием, что в случае проигрыша он получит от Луны пять дней. Одержав победу, Гермес прибавил эти пять дней к тем 360 дням, которые до этого составляли год.

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

Увлекались шашками и египетские фараоны. Во время раскопок в Египте обнаружили гробницу вельможи, который был приближенным фараона. На стенах гробницы есть росписи, отражающие три страсти древнего египтянина – охоту, рыбную ловлю и игру в шашки. В Лувре хранятся две шашечные доски, принадлежащие фараонам. Из гробницы Тутанхамона была извлечена доска для игры в шашки, состоявшая из тридцати клеток.

За несколько веков до нашей эры уже играли на 64-клеточной доске. Шашки были двух цветов – белые и черные. И представляли собой как бы две армии, которым предстояло сражение. Отступление не предусматривалось, поэтому шашки могли ходить только вперед. Если шашка прорывалась в тыл к противнику, то повышалась ее боевая способность и она становилась дамкой. Взятие происходило с помощью перескакивания одной шашки через другую. Точно так же в бою победивший воин перешагивает через побежденного, чтобы дальше продолжить сражение.

Играют в шашки в «Декамероне» Боккаччо, играют в «Дон Кихоте» Сервантеса.

На Руси появление шашек связывают с именем киевского князя Владимира Мономаха (1053–1125). Однако археологические раскопки показали, что еще в III–IV веках нашей эры уже играли в шашки. Во многих былинах рассказывается о том, что шашки были одной из любимых игр русских богатырей.

Петр I всячески поощрял игру в шашки и в шахматы. На учрежденных им «ассамблеях» тот петербургский сановник, которому подошел черед устраивать у себя «ассамблею», должен был, помимо всего прочего, выделить особую комнату для шахмат и шашек.

Примерно в 1535 году в правила шашек добавляют условие: если шашку соперника можно бить, то игрок обязан это делать. Это правило игры используется до сих пор в неизменном виде.

Любителями шашек были Державин, Пушкин. Л.Н. Толстой в «Войне и мире» сравнивает стратегию военного искусства со стратегией шашечной игры. Шашками увлекались Александр Суворов и Антон Чехов, Александр Грин и Фридрих Шопен и многие другие известные личности. Наполеон шахматам предпочитал шашки, черпая в этой игре идеи для тактики ведения боя.

---

Морской бой

Мы уже обсуждали игру «Морской бой» (рис. 8), когда говорили о методе координат в 5 классе. Теперь же может возникнуть вопрос: а есть ли алгоритм выигрышной стратегии для этой игры?

Рис. 8. Морской бой (Источник)

Ответить на этот вопрос однозначно нельзя, но, с большой долей вероятности, такого алгоритма нет. Дело в том, что во многих логических играх начальные положения игроков оговорены правилами. «Морской бой» относится к тому типу игр, в которых сама игра во многом определяется начальным положением (в данном случае – кораблей соперников). А свои корабли игроки располагают произвольным образом.

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

Однако есть несколько тактик ведения игры. Одна из них состоит в поиске четырехпалубника. Такой большой корабль тяжело спрятать. Для того чтобы гарантировать себе нахождение четырехпалубника, достаточно «простреливать» одну клетку в любом четырехугольнике 1 х 4. Даже в случае редкого невезения для этого понадобится максимум 24 выстрела. Однако такое невезение бывает редко – чаще всего «по пути» вы убьете еще несколько кораблей противника, уменьшите количество «проверяемых» клеточек с учетом того, что рядом с кораблем встык другой корабль стоять не может, и с успехом найдете четырехпалубник.

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

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

---

Игры без алгоритма

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

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

Задача.

Существует одна из разновидностей шахмат (рис. 9) – когда каждый из игроков делает по два хода. Доказать, что в такой игре у второго игрока не может существовать выигрышная стратегия.

Рис. 9. Шахматы (Источник)

Доказательство.

Для доказательства воспользуемся так называемым «методом от противного». Пусть такая стратегия у второго игрока существует.

Тогда первый игрок может своим ходом сделать следующий «маневр»: походит любым конем первым своим ходом, а вторым ходом вернет коня обратно.

Что произойдет в этом случае: получается, что второй игрок как бы станет первым, так как перед его ходом на доске снова начальная позиция. Тогда, если бы существовала выигрышная стратегия для второго игрока, то после такой «передачи хода», она стала бы выигрышной для первого игрока – и партию выиграл бы он. Значит, она не была бы выигрышной для второго игрока – получили противоречие.

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

Доказано.

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

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

 

Список литературы

1. Босова Л.Л. Информатика и ИКТ: учебник для 6 класса. – М.: БИНОМ. Лаборатория знаний, 2012.

2. Босова Л.Л. Информатика: рабочая тетрадь для 6 класса. – М.: БИНОМ. Лаборатория знаний, 2010.

3. Босова Л.Л., Босова А.Ю. Уроки информатики в 5–6 классах: методическое пособие. – М.: БИНОМ. Лаборатория знаний, 2010.

 

Дополнительные рекомендованные ссылки на ресурсы сети Интернет

1. Интернет-сайт iv-k.ltd.ua (Источник)

2. Интернет-сайт primwiki.ru (Источник)

3. Интернет-сайт taina-chess.narod.ru (Источник)

 

Домашнее задание

1. §3.1., 3.4 (Босова Л.Л. Информатика и ИКТ: учебник для 6 класса).

2. Попытайтесь самостоятельно составить выигрышную стратегию какой-либо игры.

3. Запишите составленный алгоритм в виде блок-схемы.