Ним — игра, в которой два игрока по очереди берут предметы, разложенные на несколько кучек. За один ход может быть взято любое количество предметов (большее нуля) из одной кучки. Выигрывает игрок, взявший последний предмет. В классическом варианте игры число кучек равняется трём.
Частный случай, когда кучка одна, но максимальное число предметов, которые можно взять за ход, ограничено, известен как игра Баше. Ним — конечная игра с полной информацией. Классическая игра Ним имеет фундаментальное значение для теоремы Шпрага — Гранди. Эта теорема утверждает, что обычная игра в сумму беспристрастных игр эквивалентна обычной игре в Ним. При этом каждой беспристрастной игре-слагаемому соответствует кучка Ним, число предметов в которой равно значению функции Шпрага — Гранди для игровой позиции данной игры.
Содержание
История игры [ править | править код ]
Китайская игра ним упоминалась европейцами ещё в XVI веке. Имя «ним» было дано игре американским математиком Чарльзом Бутоном (англ. Charles Bouton ), описавшим в 1901 году выигрышную стратегию игры. Существует несколько вариантов происхождения названия игры:
- от немецкого глагола nehmen или от староанглийского глагола Nim, имеющих значение «брать»;
- ананим от английского глагола Win («побеждать»).
Игрушка «Доктор Ним», небольшой шариковый компьютер, придуманный в 1960-х, играл не в ним, а в игру Баше.
Стратегия игры [ править | править код ]
В общем случае рассматривается p <displaystyle p> 
>
>
Выигрышная стратегия состоит в том, чтобы оставлять после своего хода позицию с ним-суммой, равной нулю. Она основана на том, что из любой позиции с ним-суммой, не равной нулю, можно одним ходом получить позицию с нулевой ним-суммой, а из позиции с нулевой ним-суммой любой ход ведёт в позицию с ним-суммой, отличной от нуля.
Пример: предположим, в игре три кучки, в них соответственно 2 (0010 в бинарном представлении), 8 (1000) и 13 (1101) предметов. Ним-сумма этой позиции — 7 (0111). Следовательно, выигрышная стратегия состоит в том, чтобы взять 3 предмета из третьей кучки — там останется 10 (1010) предметов, и ним-сумма позиции станет 0 (0000). Предположим, после вашего хода противник забирает все предметы из первой кучки — выигрышная стратегия будет заключаться в том, чтобы забрать 2 предмета из третьей кучки. В таком случае после вашего хода в кучках будет соответственно 0 (0000), 8 (1000) и 8 (1000) предметов, ним-сумма по прежнему будет равняться 0.
Варианты игры [ править | править код ]
Шоколадка [ править | править код ]
Есть шоколадка m×n, одна долька «отравленная». Игрок своим ходом разламывает шоколадку по линии и съедает неотравленную часть. Проигрывает тот, кому останется отравленная долька. Игра эквивалентна ниму с четырьмя кучками.
Мизер [ править | править код ]
В этом варианте игрок, взявший последний объект, проигрывает. Выигрышная стратегия совпадает с выигрышной стратегией обычной игры до того момента, когда в результате хода игрока на столе должно остаться некоторое количество кучек с единственным предметом в каждой из них. В случае мизера игрок должен оставить нечётное количество кучек, тогда как выигрышная стратегия обычной игры требует оставить чётное количество кучек, чтобы ним-сумма равнялась нулю. Это можно сформулировать так: если осталась ровно одна кучка, содержащая более одного предмета, то забрать из неё все предметы или все кроме одного, чтобы осталось нечетное количество единичных кучек; иначе придерживаться выигрышной стратегии обычной игры.
Мультиним [ править | править код ]
Более общий случай игры Ним был предложен Элиакимом Муром. В игре N i m i <displaystyle Nim_>
Форкед-ним [ править | править код ]
Еще один вариант игры был предложен Матвеем Бернштейном. В нем можно произвольно разбивать любую кучку на две произвольные кучки вместо хода. Во всем остальном игра ведется по обычным правилам.
Напишите программу с «искусственным интеллектом» (ИИ), которая играет против пользователя и выигрывает, если может. Исходное количество камней в куче задаёт пользователь, программа всегда ходит первой. После каждого хода пользователя и программы необходимо сообщать, сколько камней взято и сколько осталось. В конце необходимо сообщить, кто выиграл.
Пользователь в свой ход вводит количество камней до тех пор, пока не введёт разрешённое число — от одного до трёх (или меньше — если камней осталось меньше).
Примечания
Данная задача дополнительно проверяется преподавателем.
Аннотация научной статьи по математике, автор научной работы — Пискарев Алексей Валерьевич
Статья содержит описание алгоритма для игры "Ним". Игра состоит в следующем. В начальной позиции перед двумя игроками сложено несколько кучек одинаковых мелких предметов например, спичек. Игроки по очереди могут выбрать одну из кучек и взять из нее одну или несколько спичек. Выигрывает тот, кто возьмет последнюю спичку. Предложенная выигрышная стратегия связана с представлением натуральных чисел в двоичной системе счисления.
Похожие темы научных работ по математике , автор научной работы — Пискарев Алексей Валерьевич
Текст научной работы на тему «Игра «Ним» оценка игровой ситуации. Алгоритм игры»
Пискарев Алексей Валерьевич
ОЦЕНКА ИГРОВОЙ СИТУАЦИИ. АЛГОРИТМ ИГРЫ
Широко известна игра «Ним». Правила ее очень просты. Играют двое. На столе перед ними лежат несколько кучек каких-то предметов, например, спичек. Игроки ходят по очереди, и каждый игрок в свой ход выбирает одну из кучек и изымает из нее любое количество спичек. Если он изымет все спички из выбранной кучки, то она перестает существовать. Выигрывает тот игрок, который своим очередным ходом сумеет забрать все оставшиеся спички.
Пусть перед нами лишь одна кучка спичек. Что делать — ясно: забрать все спички из этой кучки и выиграть.
Что, если перед нами две кучки, и в них одинаковое количество спичек? Тог-
. лефаН Нескольку кугек клких-Наа прерме&аб, Например,, спигек.
да мы, вероятнее всего, проиграем: сколько бы мы ни брали из одной кучки, наш партнер будет брать столько же из другой и в результате выиграет.
А если две кучки, но с разным количеством спичек? Тогда опять ситуация в нашу пользу: мы можем своим ходом уравнять две кучки и свести ситуацию к предыдущей, которая теперь будет проигрышной уже для нашего партнера.
Можно придумать много разных ситуаций, которые при рассмотрении оказываются заведомо выигрышными или проигрышными.
Возникает вопрос: любая ли ситуация окажется выигрышной или проигрышной?
Выходит, что да, любая. И вот почему. Ситуация с одной-единственной спичкой заведомо выигрышная. Далее будем рассматривать последовательно все варианты более сложных ситуаций для любого количества спичек. Если в какой-то ситуации найдется такой ход, который обеспечивает противнику проигрышную ситуацию (более простую, уже рассмот-
"ЧЛаа если пере^ Нлми Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.
— двоичные цифры, стоящие в столбиках левее первого слева крестика (возможно, их вовсе нет, п = 0), а Ь , Ь , . , Ь
— цифры, стоящие правее первого слева крестика (их тоже может не быть, т = 0). После описанного выше преобразования числа А мы получим число
Первые п цифр останутся неизменными, следующая цифра поменяется с 1 на 0, и как-то могут поменяться остальные цифры. Из наглядного поразрядного сравнения чисел А и С:
С = (а а л. ал0с с
"Нре^сЛ-авим. все уадлЯЯш гисмя в фвиг^ой сисйеме сшсмшя.
ясно, что А > С (так как 1 > 0).
Теперь после нашего хода партнер, совершая подсчет аналогичным образом, не получит ни одного крестика (подумайте, почему). Рассмотрим этот вариант.
Итак, «крестиков нет». Тогда ход партнера не станет последним в игре. Вот почему: ход мог бы стать последним, только если на столе ле-
жит лишь одна кучка, но в таком случае хотя бы один крестик обязательно получится. Значит, на столе осталось более одной кучки, и ближайший ход не завершит игру.
Пусть игрок совершит любой ход. Найдется столбик двоичных цифр, который изменится от этого хода, причем ровно на одну единицу. И тогда количество цифр 1 в этом столбике станет нечетным, и мы при подсчете поставим под ним крестик и без крестиков, таким образом, не останемся.
Понятно, что если игра будет так продолжаться (то есть если мы будем продолжать придерживаться того же метода
выбора хода), то выиграем в результате именно мы, так как ни один ход нашего партнера не сможет завершить игру (рассмотрите самостоятельно, к чему приведет этот метод, если на столе останется только одна кучка спичек).
@пособ пр&мого перебарл 6 $ейаНбиАел-&НосНи неприменим и^-^л с6ош НруддемкооНи.
От редакции. Полезным упражнением для читателей будет написание программы для игры в «Ним», для этого можно использовать логическую операцию ХОЯ — исключающее «ИЛИ», которая позволит простыми вычислениями определять правильные ходы.
Прочитав статью Борзых А.К. «Универсальная самообучающаяся машина из спичечных коробков» в этом же номере журнала и познакомившись с самообучающимися машинами, можно попробовать сделать программу, которая научится играть в «Ним», не зная правильной стратегии! А в качестве учителя использовать программу, которая эту стратегию знает!
Пискарев Алексей Валерьевич, студент V курса СПбГЭТУ (ЛЭТИ) кафедры автоматизированных систем обработки информации и управления.
