Игры
На этом уроке мы познакомимся с одним из типов задач, который практически всегда нуждается в нахождении алгоритма – это игры. Конечно же, речь пойдет не о компьютерных играх в стиле Call of Duty или GTA. Мы поговорим о логических играх, то есть тех играх, в которых победа достигается за счет нахождения выигрышного алгоритма. Многие такие игры реализованы и в компьютерном варианте – о них мы тоже не забудем упомянуть.
Важность игр состоит в том, что чаще всего за простенькой игрой скрывается важная задача, имеющая прикладное значение.
Игры бывают разные. Если говорить о математических играх, то чаще всего они связаны с действиями двух игроков.
Постановка задачи в такой игре обычно следующая:
1. Начальные условия игры.
2. Правила игры для обоих игроков.
3. Указания условий выигрыша.
Чаще всего в таких задачах просят найти выигрышный алгоритм для одного из игроков. При этом обычно неизвестно, кто из игроков выигрывает при нахождении правильного алгоритма. Весь смысл таких задач состоит в том, что такой алгоритм должен существовать.
То есть независимо от действий одного из игроков, другой может обеспечить себе победу.
Пример 1.
Рассмотрим простой пример: двое по очереди кладут на круглый стол одинаковые монеты. Проигрывает тот, кто не может сделать ход. Кто выиграет при правильной игре?
Решение.
На первый взгляд кажется, что задача слишком неоднозначная – неизвестны размеры стола и монет. Однако данная задача имеет решение.
Выигрывает первый игрок. Для этого первым своим ходом он кладет монету так, чтобы ее центр совпал с центром стола (рис. 1).
Рис. 1. Первый ход
А дальше ходит симметрично второму игроку (рис. 2).
Рис. 2. Дальнейшие ходы
Почему у первого игрока будет ход? Потому, что если второй игрок смог походить, то симметричное место должно быть свободно (иначе его заняли бы монетой на каком-то из предыдущих ходов) (рис. 3).
Рис. 3. Дальнейшие ходы
Вывод: до тех пор пока есть ход у второго игрока, есть ход и у первого игрока. Но площадь стола конечна, поэтому рано или поздно игра должна закончиться. Значит, последний ход будет за первым игроком. Он и выиграет в этой игре.
Ответ: выигрывает первый игрок.
Стоит отметить, что метод симметрии при построении алгоритмов выигрышных стратегий является одним из наиболее популярных.
Выигрышные стратегии
Рассмотрим следующий пример.
Пример 2.
В коробке 60 спичек. За один ход можно взять любое количество спичек от 1 до 5. Проигрывает тот, кто не может сделать ход. Кто из игроков выиграет при правильной игре?
Решение.
Проанализируем концовку такой игры. Если количество спичек меньше 5, то тот игрок, чья очередь ходить, заканчивает игру и выигрывает. Если количество спичек больше 6, то игра закончится через 2 или больше хода.
Если же количество спичек равно 6, то игрок, чей ход был до появления этой позиции, свои следующим ходом заканчивает игру. Действительно, сколько бы ни взял своим следующим ходом другой игрок, останется от 1 до 5 спичек. И у игрока будет возможность игру закончить.
Значит, позиция «6 спичек» проигрышна для того, кто ходит. Аналогично проигрышными являются позиции «12 спичек», «18 спичек» и т. д. Значит, и позиция «60 спичек» является проигрышной для того, кто будет ходить, то есть для первого игрока (рис. 4).
Рис. 4. Проигрышная позиция
Выиграет второй игрок.
Осталось придумать выигрышную стратегию. Мы ее уже практически сформулировали: второй игрок должен своим ходом дополнять количество спичек, взятое первым игроком, до 6 (рис. 5).
Рис. 5. Стратегия второго игрока
Тогда после пары их ходов количество спичек будет уменьшаться на 6. В итоге, через 10 пар ходов спичек не останется. И у первого игрока не будет хода.
Ответ: выиграет второй игрок.
На самом деле, в этой игре мы фактически также воспользовались симметрией. Только специфической – симметрия состояла в том, что сумма взятых спичек должна равняться 6.
Пример 3.
Фишка стоит в углу шахматной доски размером 8 х 8. Двое игроков по очереди передвигают ее на соседнее поле (поля соседние, если у них есть общая сторона). Второй раз ходить на поле, где фишка уже побывала, нельзя. Тот, кому некуда ходить, проигрывает. Кто победит при правильной игре?
Решение.
Разобьем шахматную доску на прямоугольники размерами 1 х 2 произвольным образом (рис. 6).
Рис. 6. Разбиение доски
Тогда алгоритм действий первого игрока напрашивается следующий: на своем ходе он передвигает фишку на вторую клетку прямоугольника 1 х 2, в который попала исходная клетка фишки.
Следующим ходом второй игрок вынужден будет менять прямоугольник, так как не может ходить на ту клетку, где фишка уже побывала (рис. 7).
Рис. 7. Ход второго игрока
Тогда первый игрок снова должен походить во вторую клетку уже нового прямоугольника 1 х 2. И т. д. Таким образом, каждым своим ходом второй игрок будет вынужден менять прямоугольник. И после его хода у первого игрока всегда будет ход. Значит, выиграет первый игрок.
Ответ: выиграет первый игрок.
На этом уроке мы разобрали некоторые математические игры, а также примеры выигрышных стратегий.
На следующем уроке мы на практике обсудим составление алгоритмов выигрышных стратегий в играх.
Выигрышная стратегия в шахматах
Одной из самых загадочных и интересных логических игр для двух участников во все времена оставались шахматы (рис. 8).
Рис. 8. Шахматы (Источник)
Одним из залогов успеха этой игры является то, что она не имеет известного на данный момент выигрышного алгоритма.
Это связано с тем, что правила шахмат достаточно сложны – существует 6 видов фигур, количество фигур одного вида различно, а, кроме того, у каждой фигуры свои правила хода. Таким образом, сформулировать простой алгоритм выигрыша в шахматы на данный момент не удалось.
С другой стороны, как только это произойдет, шахматы перестанут быть столь привлекательной для многих игрой.
Существует множество книг по теории шахмат. Есть описания различных тактик – защитной, атакующей.
Шахматную партию принято делить на три части – дебют (начало), миттельшпиль (середина) и эндшпиль (конец). Вполне логично, что большая часть моделей игры создана для дебюта (от классического е2–е4 и «детского мата» до сицилийской защиты). Дебют закладывает основу всей партии, а, кроме того, в самом начале на доске находятся все фигуры и известно их местоположение. Поэтому его изучение не так сложно, как изучение миттельшпиля. Представьте себе, что часть фигур уже сбита, остальные расположены в произвольном порядке на доске. Описать такую ситуацию достаточно тяжело.
Другое дело – эндшпиль. В конце партии на доске остаются считаные фигуры – обычно короли и несколько фигур + пешки. Описывать такие ситуации несколько проще.
Проблема создания алгоритма для игры в шахматы возникла с созданием компьютерной программы, которая должна была обыграть человека.
История шахматных машин старше, чем история компьютеров. Идея создать машину, играющую в шахматы, датируется еще восемнадцатым веком. Около 1769 года появился шахматный автомат «Механический турок». Он был предназначен для развлечения королевы Марии-Терезии. Машина действительно неплохо играла — внутри нее находился сильный шахматист, который и делал ходы.
В 1951 году Алан Тьюринг написал алгоритм, с помощью которого машина могла бы играть в шахматы, только в роли машины выступал сам изобретатель. Этот нонсенс даже получил название – «бумажная машина Тьюринга». Человеку требовалось более получаса, чтобы сделать один ход. Алгоритм был довольно условный, и сохранилась даже запись партии, где «бумажная машина» Тьюринга проиграла одному из его коллег. За отсутствием доступа к компьютеру, программа ни разу не проверялась в работе.
Следующим шагом в развитии шахматного программирования стала разработка в ядерной лаборатории Лос-Аламоса в 1952 году на компьютере Maniac 1 (тактовая частота 11 кГц) шахматной программы для игры на доске 6 x 6, без участия слонов. Известно, что этот компьютер сыграл одну партию против сильного шахматиста, она продолжалась 10 часов и закончилась победой шахматиста. Еще одна партия была сыграна против девушки, которая недавно научилась играть в шахматы. Машина победила на 23-м ходу. Сейчас это выглядит смешно, но для своего времени это было большое достижение.
В 1994 Гарри Каспаров (рис. 9) проиграл программе Fritz 3 турнирную блиц-партию в Мюнхене. Программа также выиграла у Вишванатана Ананда, Бориса Гельфанда и Владимира Крамника. Гроссмейстер Роберт Хюбнер отказывался играть против программы и автоматически проиграл. Каспаров сыграл второй матч с Fritz и победил с 4 выигрышами и 2 ничьими.
Рис. 9. Гарри Каспаров (Источник)
В феврале 1996 года Гарри Каспаров победил шахматный суперкомпьютер Deep Blue со счетом 4-2. Этот матч необычен тем, что первую партию выиграл Deep Blue, автоматически став первым компьютером, победившим чемпиона мира по шахматам в турнирных условиях (рис. 10).
Рис.10. Шахматный суперкомпьютер Deep Blue (Источник)
Крестики-нолики
Игра в крестики-нолики известна практически каждому. В таблице 3 х 3 участники по очереди расставляют крестики и нолики (каждый – свои символы). Выиграет тот, кто получит в ряду, столбце или диагонали три крестика или три нолика. Попытаемся узнать – кто выиграет при правильной игре.
Рис. 11. Крестики-нолики (Источник)
На самом деле, при правильной игре всегда будет ничья.
Докажем, что первый игрок может обеспечить себе «непроигрыш». Для этого достаточно поставить первым ходом крестик в центр таблицы. А затем ходить так, чтобы у второго ни в одной строке или столбце не оказывалось больше 2 ноликов. То, что это можно сделать, легко доказать с помощью перебора.
Аналогично и второй игрок: если первый игрок походит не в центр, то походить в центр, а дальше действовать аналогично написанному выше для первого игрока. Если первый походит в центр, то занять один из углов, а затем действовать аналогично написанному выше для первого игрока.
Существует более общая стратегия, однако ее описание достаточно громоздко.
Интереснее, с точки зрения алгоритма, игра в крестики-нолики, которая называется «хожу чем хочу», то есть когда каждый из игроков выбирает сам – крестик ему ставить или нолик (на любом из ходов). В этом случае всегда побеждает первый. Опишем алгоритм выигрыша:
1. Ставим крестик в середину.
2. Если второй игрок ставит крестик, то крестиком закрываем линию.
3. Если второй игрок ставит нолик в углу, то ставим нолик в противоположном углу. Любой следующий ход второго игрока – и мы закрываем линию.
4. Если второй игрок ставит нолик не в углу, то ставим нолик симметрично относительно центральной клетки. Второму игроку ничего не остается, как поставить ноли в еще одной неугловой клетке, на что мы отвечаем ноликом в 4-й неугловой клетке. Куда бы ни походил теперь второй игрок, первый игрок выиграет.
У крестиков-ноликов существует ряд модификаций. Одна из наиболее популярных – игра на бесконечном поле, где надо собрать линию из 5 одинаковых символов.
Игры без алгоритма
Существует целый ряд задач, в которых необходимо не найти выигрышный алгоритм, а доказать, что его не существует или, наоборот, он существует.
Рассмотрим пример такой задачи.
Есть три кучки камней: 10, 15 и 20 камней соответственно. За ход разрешается разделить любую кучку на две меньшие. Проиграет тот, кто не сможет сделать ход. Кто выиграет при правильной игре?
Решение:
Всего в кучках 45 камней. Игра закончится только тогда, когда все камни будут лежать по отдельности, то есть будет 45 кучек по 1 камню в каждой. За каждый ход количество кучек увеличивается на 1. Изначально кучек 3, должно получиться 45. Значит, всего будет сделано 42 хода. Так как количество ходов четное, то последним сделает ход второй игрок. Значит, проиграет первый игрок.
Ответ: выиграет второй игрок.
Список литературы
1. Босова Л.Л. Информатика и ИКТ: учебник для 6 класса. – М.: БИНОМ. Лаборатория знаний, 2012.
2. Босова Л.Л. Информатика: рабочая тетрадь для 6 класса. – М.: БИНОМ. Лаборатория знаний, 2010.
3. Босова Л.Л., Босова А.Ю. Уроки информатики в 5–6 классах: методическое пособие. – М.: БИНОМ. Лаборатория знаний, 2010.
Дополнительные рекомендованные ссылки на ресурсы сети Интернет
1. Интернет портал «Фестиваль педагогических идей» (Источник)
2. Интернет портал «Наша сеть» (Источник)
3. Интернет портал «Хостинг презентаций» (Источник)
Домашнее задание
1. §3.1., 3.4 (Босова Л.Л. Информатика и ИКТ: учебник для 6 класса)
2. Львенок и Черепаха решили сыграть в крестики-нолики (рис. 12).
Рис. 12. Львенок и Черепаха. (Источник)
Черепаха ставила крестики, а Львенок – нолики (рис. 13).
Рис.13. Заготовки для крестиков-ноликов
- Кто сколько ходов сделал? Чей ход следующий?
- Где Львенок должен поставить нолик, чтобы выиграть? (в первой игре – по диагонали).
- Как можно определить победителя второй игры? (выиграет тот, чей ход следующий).
- В третьей игре у соперников возникла проблема: они сделали уже по три хода, а победитель еще не определился. Кто победит в этой игре? (Никто, так как трех последовательных фигур уже не получится).
- Рассмотрите игру № 4. Кто выигрывает? (Львенок, так как ему осталось только поставить один нолик).
- Но следующий ход делает Черепаха… Представьте, что Черепаха попросила вас о помощи. В какой клетке нужно поставить ей крестик, чтобы помешать Львенку выиграть? (второй столбец, последняя строка).
- В каком случае в этой игре выиграет Черепаха? (Если Львенок ошибется в последнем ходе и поставит нолик в верхней строке, тогда у Черепахи будет три крестика в нижней строке).
3. Сформулируй правила (секреты) выигрышной стратегии.
