Стратегические игры. Игра НИМ
проект

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

Суть стратегической игры для двух игроков, известной под названием Ним, заключается в том, что игроки выкладывают на стол одну или несколько групп фишек (камней, спичек, конфет…) и определяют правила, по которым нужно снимать фишки со стола. Цель игры — взять последнюю фишку.

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

 Может быть, мы сумеем найти эту стратегию?

Цель моей работы: Найти оптимальную стратегию для игры НИМ.

Задачи:

• Собрать информацию  об игре Ним;
• Опытным путем определить «выигрышные» и «проигрышные» ходы,
  выделить основные идеи решения игровых задач.
• Описать оптимальную стратегию игры НИМ.

Происхождение этой игры неизвестно. Некоторые считают, что она родом с Востока. Существует версия, что это древняя китайская игра. В неё любили играть китайские императоры. Тем, кто у них выигрывал, отрубали голову. Также неясно и происхождение названия. Среди возможных версий — староанглийское слово «ним», означавшее «брать», «красть». Некто очень остроумный заметил, что если применить к слову NIM центральную симметрию, получится слово WIN — «выиграть» в переводе с английского. Как бы то ни было, игре Ним больше ста лет.

Правила игры Ним

Ним — игра для двух игроков, каждый из которых по очереди делает ход.

• На столе лежат три кучки спичек;

• игроки по очереди забирают спички из любой кучки;

• не разрешается за один ход брать спички из нескольких кучек;

• за один ход игрок должен взять хотя бы одну спичку ;

• выигрывает тот, кто возьмет последнюю спичку.

В наиболее известном варианте игры 12 спичек раскладываются так 3. 5 .7

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

Например:

357        307        303    а дальше все ваши шаги соперник будет повторять

По этой же причине не стоит оставлять  в двух кучках из трех равное количество спичек

357        355        055     дальше все ваши шаги соперник будет повторять

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

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

В данной игре симметрия несколько необычная — вроде бы и не симметрия вовсе, однако, равенство спичек в кучках, и «одинаковые» ходы, проводимые игроками очень ее напоминают.

Очевидно, что в позиции {1,1} выигрывает второй, а в позициях {1}, {1,1,1} выигрывает первый.Если игрок умный и ходит первым из выигрышной позиции, то он выиграет. Но как бы ни был умён игрок, он может проиграть, если будет ходить первым из проигрышной позиции.

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

Делим все возможные ходы на «выигрышные» и «проигрышные». Стратегия победителя заключается в том, что он делает ходы «выигрышные .

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

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

В начале нашей  игры имеются три кучки – из трех, пяти и семи спичек. Запишем эти числа в следующем виде.

3 = 2 + 1;

 5 = 4 + 1;

 7 = 4 + 2 + 1.

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

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

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

.