Игра ним как выиграть

Игра ним как выиграть

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

Частный случай, когда кучка одна, но максимальное число предметов, которые можно взять за ход, ограничено, известен как игра Баше. Ним — конечная игра с полной информацией. Классическая игра Ним имеет фундаментальное значение для теоремы Шпрага — Гранди. Эта теорема утверждает, что обычная игра в сумму беспристрастных игр эквивалентна обычной игре в Ним. При этом каждой беспристрастной игре-слагаемому соответствует кучка Ним, число предметов в которой равно значению функции Шпрага — Гранди для игровой позиции данной игры.

Содержание

История игры [ править | править код ]

Китайская игра ним упоминалась европейцами ещё в XVI веке. Имя «ним» было дано игре американским математиком Чарльзом Бутоном (англ. Charles Bouton ), описавшим в 1901 году выигрышную стратегию игры. Существует несколько вариантов происхождения названия игры:

  • от немецкого глагола nehmen или от староанглийского глагола Nim, имеющих значение «брать»;
  • ананим от английского глагола Win («побеждать»).

Игрушка «Доктор Ним», небольшой шариковый компьютер, придуманный в 1960-х, играл не в ним, а в игру Баше.

Стратегия игры [ править | править код ]

В общем случае рассматривается p <displaystyle p> кучек предметов с N 1 , N 2 , ⋯ N p <displaystyle N_<1>,N_<2>,cdots N_

> предметами. Игроки ходят по очереди. Ход заключается в том, что игрок берёт из кучки i ∈ [ 1 , p ] <displaystyle iin [1,p]> n ∈ [ 1 , N i ] <displaystyle nin [1,N_]> предметов. Каждой позиции игры ставится в соответствие ним-сумма этой позиции — результат сложения размеров всех кучек в двоичной системе счисления без учёта переноса разрядов, то есть сложение двоичных разрядов чисел в поле вычетов по модулю 2: S = N 1 ⊕ N 2 ⊕ ⋯ ⊕ N p <displaystyle S=N_<1>oplus N_<2>oplus cdots oplus N_

>

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

Пример: предположим, в игре три кучки, в них соответственно 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_> игрокам разрешается брать предметы из максимум i <displaystyle i> кучек. Легко видеть, что обычная игра ним является N i m 1 <displaystyle Nim_<1>> . Для решения необходимо записать размеры каждой кучки в двоичной системе счисления и просуммировать эти числа в ( i + 1 ) <displaystyle (i+1)> -ичной системе счисления без переносов разрядов. Если получилось число 0, то текущая позиция проигрышная, иначе — выигрышная и из неё есть ход в позицию с нулевой величиной.

Читайте также:  Где собирают телевизоры филипс для россии

Форкед-ним [ править | править код ]

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

Аннотация научной статьи по математике, автор научной работы — Пискарев Алексей Валерьевич

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

Похожие темы научных работ по математике , автор научной работы — Пискарев Алексей Валерьевич

Текст научной работы на тему «Игра «Ним» оценка игровой ситуации. Алгоритм игры»

Пискарев Алексей Валерьевич

ОЦЕНКА ИГРОВОЙ СИТУАЦИИ. АЛГОРИТМ ИГРЫ

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

Пусть перед нами лишь одна кучка спичек. Что делать — ясно: забрать все спички из этой кучки и выиграть.

Что, если перед нами две кучки, и в них одинаковое количество спичек? Тог-

. лефаН Нескольку кугек клких-Наа прерме&аб, Например,, спигек.

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

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

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

Возникает вопрос: любая ли ситуация окажется выигрышной или проигрышной?

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

"ЧЛаа если пере^ Нлми Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

— двоичные цифры, стоящие в столбиках левее первого слева крестика (возможно, их вовсе нет, п = 0), а Ь , Ь , . , Ь

— цифры, стоящие правее первого слева крестика (их тоже может не быть, т = 0). После описанного выше преобразования числа А мы получим число

Первые п цифр останутся неизменными, следующая цифра поменяется с 1 на 0, и как-то могут поменяться остальные цифры. Из наглядного поразрядного сравнения чисел А и С:

С = (а а л. ал0с с

"Нре^сЛ-авим. все уадлЯЯш гисмя в фвиг^ой сисйеме сшсмшя.

ясно, что А > С (так как 1 > 0).

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

Итак, «крестиков нет». Тогда ход партнера не станет последним в игре. Вот почему: ход мог бы стать последним, только если на столе ле-

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

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

Читайте также:  Microsoft print to pdf нет в списке

Понятно, что если игра будет так продолжаться (то есть если мы будем продолжать придерживаться того же метода

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

@пособ пр&мого перебарл 6 $ейаНбиАел-&НосНи неприменим и^-^л с6ош НруддемкооНи.

От редакции. Полезным упражнением для читателей будет написание программы для игры в «Ним», для этого можно использовать логическую операцию ХОЯ — исключающее «ИЛИ», которая позволит простыми вычислениями определять правильные ходы.

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

Пискарев Алексей Валерьевич, студент V курса СПбГЭТУ (ЛЭТИ) кафедры автоматизированных систем обработки информации и управления.

Имеется две кучки спичек. В первой 7 спичек, во второй — 5. За один ход разрешается взять любое количество спичек, но из одной кучки. Проигрывает тот, кому нечего брать. Кто выигрывает при правильной игре — начинающий или его партнер? И как для этого ему надо играть?

Ответ: При правильной игре выигрывает начинающий игрок. Его стратегия: первым ходом он должен сравнять количество спичек в кучках, т.е. взять из первой кучки 2 спички. Каждый следующий его ход должен быть "симметричен" ходу второго игрока, т.е. если "второй" берет n спичек из одной кучки, то "первый" должен взять также n спичек, но из другой кучки. Таким образом, если может сделать ход "второй" игрок, то может сделать ход и "первый". Так как после каждого хода количество спичек уменьшается, то наступит момент, когда "второй" не сможет сделать ход (ни в одной из кучек спичек не останется) и проиграет.

Комментарии

Оставлен Гость Сб, 07/10/2010 — 11:46

Ответ неоднозначен. Проигрывает тот, кто начинает игру. Первый берет из одной кучки все, второй — из второй, первый — нечего брать. Он проиграл.

Оставлен Гость Втр, 07/13/2010 — 15:08

Нет тут ты не прав. Написано же при ПРАВИЛЬНОЙ ИГРЕ выигрывает начинающий чтобы не делал его партнер.

Оставлен Гость Втр, 11/23/2010 — 20:22

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

Оставлен Гость Пнд, 10/24/2011 — 16:48

. 1
..11111
1111111
Правы только некоторые из вас. При правильной игре(в 1-ом ряду 3, во 2-ом ряду 5, а в 3-ем 7(чего либо спичек например))Выигрывает тот кто начинает правильно,с ПЕРВОГО ряда берётся одна спичка. а потом главное не ступить. Смотря как походит ваш соперник так и ходите(объяснять не буду как, это опыт)
подскажу вам некоторые комбинации делайте их своим соперникам :
1. 1
. 1 1
. 1 1 1 эту комбинацию делайте своему сопернику главное потом не ступите
2. 1
..1 1 1 1
.1 1 1 1 1 эту комбинацию делайте своему сопернику главное потом не ступите
3. 1 1
. 1 1 эту комбинацию делайте своему сопернику главное потом не ступите(эта комбинация может быть любой главное что цифры были одинаковые )
4. 1
. 1
. 1 эту комбинацию делайте своему сопернику

в этих комбинациях ряды могут быть в разном порядке.

Ну вот и всё весь секрет этой игры
играйте и и усваивайте это, главное первыми походите

Оставлен Гость Чт, 09/26/2013 — 11:18

ребята, все гораздо проще! Если Вы делаете первый ход и берете одну спичку из любого ряда, то после хода соперника, Вы всегда поставите комбинацию 2-4-6 или 1-4-5 или 1-2-3 или 1-1-1 или равное количество при оставшихся двух рядах без третьего. А это Ваш выигрыш! Доводите комбинацию до конца и ВСЁ! Я по началу записывал эти комбинации на спичечный коробок)))) Вы будете непобедимы!

Оставлен Гость Втр, 06/17/2014 — 18:50

Читайте также:  Используя графические средства воспроизведите схему танкового батальона

А если комбинация из 6 рядов: 5,6,7,8,9,10 спичек — с чего нужно начать?

Оставлен Гость Втр, 11/23/2010 — 20:24

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

Оставлен Слава Пт, 08/27/2010 — 14:41

ололол,при правильной игре,тот второй выигрывает,сейчас объясню:
Первый берет 4 спички из 5(допустим,5 из 5 он не берет,т.к сразу проиграет 7 из 7 также!)
второй: берет 6 из 7,
первый любую одну спичку,
второй-оставшуюся.
Если поменять цифра ответ останется,это просто пример,логичной игры.

Оставлен Гость Вс, 01/09/2011 — 13:35

так первый же возьмёт 2 из 7(это при правильной игре)

Оставлен Слава Пт, 08/27/2010 — 15:19

Вообщем все не правы ,всё зависи от того какое число вначале возьмет 1,при 4,5 из 5 и 7,6 из 7 выигрывает 2
А при 1,2,3 из 5 или 1,2,3,4,5 из 7 выигрывает 1!
от так от

Оставлен Гость Ср, 09/01/2010 — 02:49

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

Оставлен Virviil Ср, 11/03/2010 — 16:17

2 кучки — это не итерестно, так как выигрывает второй если сначала не поровну(очевидно)

Другое дело, когда кучек n.

Тогда на компе можно посчитать используя XOR(побитовое ИЛИ)

Оставлен Гость Сб, 03/26/2011 — 21:29

Есть игра называется баше расклад 3,5,7 условия аналогиные, только более интересные, выигрывает тот кто доводит до комбинации, 2 радя при одтн-м кол-ве спичек, по одной в каждом ряду, ну или как у нас вариант

Оставлен Гость Пнд, 03/28/2011 — 15:26

очень простая задача. я сразу же догадалась. )

Оставлен Гость Чт, 12/08/2011 — 13:34

мне нужна эта программа на small basic к завтрашнему дню. помогите, кто может, пожалуйста.

Оставлен Кристина Сб, 12/10/2011 — 02:03

Вот все возможные ситуации:
7-5. 6-5. 5-5. 4-5. 3-5. 2-5. 1-5. 0-5
7-4. 6-4. 5-4. 4-4. 3-4. 2-4. 1-4. 0-4
7-3. 6-3. 5-3. 4-3. 3-3. 2-3. 1-3. 0-3
7-2. 6-2. 5-2. 4-2. 3-2. 2-2. 1-2. 0-2
7-1. 6-1. 5-1. 4-1. 3-1. 2-1. 1-1. 0-1
7-0. 6-0. 5-0. 4-0. 3-0. 2-0. 1-0. 0-0

Правильная стратегия — после своего хода оставлять одну из след. ситуаций: 5-5 или 4-4 или 3-3 или 2-2 или 1-1 или 0-0 (победа). При таком подходе у соперника никогда не будет шанса тоже оставить какую-либо из этих ситуаций, в том числе и 0-0 (победа).
Прим.: Из ЛЮБОЙ другой ситуации всегда можно сделать 5-5 или 4-4 или 3-3 или 2-2 или 1-1 или 0-0 (победа), поэтому никогда не дарите сопернику данную возможность и, соотв-но, шанс на победу! =)

Итак, выиграть может и первый и второй, но если Вы первый и знаете данную стратегию, то победа всегда за Вами! ну Вы, конечно, догадались — сразу делаем 5-5 😉

Оставлен Гость Пнд, 05/20/2013 — 10:54

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

Оставлен Гость Пнд, 05/20/2013 — 10:54

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

Оставлен ШГ Пт, 06/14/2013 — 16:18

Это "Ним на мизер" (кому палочек не осталось, тот выигрывает). Позиции, которые должны получаться после вашего хода:
3-5-6, 3-4-7,2-5-7 (т.е. в начальной позиции надо ходить первым и брать 1 спичку из любой кучки)
Х-Х — две одинаковых кучки (Х >1). Это значит, что если среди трех вдруг стали 2 одинаковые кучки (и в каждой больше 1 спички), то заберите третью. Поддерживайте равенство, пока в одной не останется 1 спичка, тогда возьмите вторую кучку, а 1 спичку оставьте проигравшему противнику.
Вот еще позиции которые нужно получить своим ходом: 2-4-6, 1-4-5,1-2-3,1-1-1
Если такую позицию оставил вам противник,то попробуйте сделать какой-то ход. Может противник не знает выигрышного алгоритма.

Ссылка на основную публикацию
Зимний домик для кошки размеры
Наступление зимних холодов сложно переживается не только людьми. Животным, особенно тем, которые живут на улице, или вовсе бездомным, часто приходится...
Замена подшипника в шуруповерте интерскол
Шуруповёрт можно отремонтировать самостоятельно, изучив его устройство и принципы работы отдельных узлов. Устройство и неисправности шуруповёрта Все шуруповёрты устроены примерно...
Запись содержит удаленные заблокированные или непубличные видеозаписи
Друзья, в Sociate.Targeting теперь можно создавать скрытые промопосты с кнопкой призыва к действию (Call-to-Action). Вы можете выбрать название кнопки в...
Знаки в дискретной математике
Таблица обозначений абстрактной алгебры — В абстрактной алгебре повсеместно используются символы для упрощения и сокращения текста, а также стандартные обозначения...
Adblock detector