Игра ним как выиграть компьютер
Рассмотрим следующую игру. Даны $n$ кучек, в каждой из них какое-то количество камней. За один ход игрок может выбрать кучку и выбросить оттуда любое ненулевое число камней. Выигрывает тот игрок, который забрал последний камень.
При оптимальной игре в ниме на кучках размера 3, 4 и 5 выигрывает первый игрок
Немного переформулируем условие. Состояние игры однозначно описывается неупорядоченным набором неотрицательных чисел — пронумеруем их и обозначим количество камней в $i$-й кучке как $a_i$. Теперь, за один ход разрешается строго уменьшить любое из чисел. Терминальное состояние — когда все числа стали нулями.
Теорема. Состояние игры выигрышное тогда и только тогда, когда xor-сумма размеров кучек отлична от нуля:
$$ S = a_1 \oplus a_2 \oplus \ldots \oplus a_n \ne 0 $$
Доказательство проведём по индукции.
Для терминального состояния кучек уже нет, и xor-сумма равна нулю, и оно действительно проигрышное. База доказана — теперь докажем переходы.
Из состояния с нулевой xor-суммой все переходы ведут в выигрышные состояния, то есть в состояния с ненулевой суммой. В самом деле, достаточно убрать сколько угодно спичек из любой кучки — xor-сумма изменится с нуля на $a_i \oplus b_i $, где $b_i < a_i$ равно числу камней в $i$-й кучке после нашего действия.
Противоположный случай сложнее. Нужно показать, что если xor-сумма ненулевая, то всегда существует такой $b_i < a_i$, что xor-сумма станет нулевой, то есть
$$ S \oplus a_i \oplus b_i = 0 $$
Для этого посмотрим на старший единичный бит $S$ и возьмём любой $a_i$, у которого этот бит тоже единичный. Такой $a_i$ найдётся хотя бы один — по свойствам xor , их должно быть нечетное число. Из условия выше следует, что искомый $b_i$ должен быть равен $S \oplus a_i$.
Выясняется, что это корректный новый размер кучки, то есть $b_i < a_i$. Почему так? Потому что все старшие биты в выражении остались нетронутыми, $k$-й бит изменился на единицу, а что происходило с дальнейшими битами нам не важно, потому что эти изменения точно не больше, чем $2^k$.
Получается, что оптимальная стратегия такая: посчитать xor-сумму всех $a_i$, найти такой $a_i$, у которого старший бит взведен, и заменить его на $S \oplus a_i$. (А если xor-сумма $S$ оказалась нулевая, то сдаться.)
Модификации
Ним в поддавки (misère nim)
В противоположность обычному ниму, существует также «ним в поддавки»: когда игрок, совершивший последний ход, не выигрывает, а проигрывает.
Решение такого нима удивительно просто. Выигрышность позиции определяется так же, как и в обычном ниме — xor-суммой размеров кучек — но с одним исключением: если размеры всех кучек равны единице, то выигрышность и проигрышность меняются местами.
С учетом этого исключения, будем делать ходы как в обычном ниме, переходя в позицию с нулевой xor-суммой, но если такой ход ведёт в позицию, в которой размеры всех кучек равны единице, то этот ход надо изменить так, чтобы количество остающихся непустых кучек изменило свою чётность.
Доказательство. Рассмотрим некоторое течение игры: выберем произвольную стартовую позицию и выпишем ходы игроков вплоть до завершения игры. В любой игре двух оптимальных игроков рано или поздно наступает момент, когда размеры всех непустых кучек равны единице. Обозначим через $k$ число непустых кучек в этот момент — тогда для текущего игрока эта позиция выигрышна тогда и только тогда, когда $k$ чётно.
Откатимся теперь на один ход назад. Мы оказались в позиции, где ровно одна кучка имеет размер $a_i > 1$, а все остальные кучки (возможно, их было ноль) имеют размер $1$. Эта позиция выигрышна, так как мы всегда можем сделать такой ход, после которого останется нечетное число кучек размера $1$:
- Если всего непустых кучек нечетное количество, то заменяем $a_i$ на $1$.
- В противном случае, заменяем $a_i$ на $0$.
Далее, если продолжим откатываться по игре назад, то для всех состояний выигрышность также будет совпадать с «нормальным» нимом — просто потому, что когда у нас есть более одной кучки размера $>1$, то все переходы ведут в состояния с одной и более кучкой размера $>1$, а для всех них, как мы уже показали, ничего по сравнению с «нормальным» нимом не изменилось.
Таким образом, изменения в ниме «в поддавки» затрагивают только состояния, когда все кучки имеют размер, равный единице — что и требовалось доказать.
Ним Мура (k-ним)
Условие. Есть $n$ кучек камней размера $a_i$. Также задано натуральное число $k$. За один ход игрок может уменьшить размеры от одной до $k$ кучек (то есть теперь разрешаются одновременные ходы в нескольких кучках сразу). Проигрывает тот, кто не может сделать хода.
Очевидно, при $k=1$ ним Мура превращается в обычный ним.
Решение. Запишем размер каждой кучки в двоичной системе счисления. Затем просуммируем эти нули и единицы вдоль каждого разряда и возьмём эту сумму по модулю $(k+1)$. Если во всех разрядах получился ноль, то текущая позиция проигрышная, иначе — выигрышная.
Доказательство, как и для обычного нима, заключается в описании стратегии игроков — нужно показать, что
- из игры с нулевым значением мы можем перейти только в игры с ненулевыми значениями, и
- из любой игры с ненулевым значением найдется ход в игру с нулевым значением.
Первый пункт доказывается следующим рассуждением. Если для всех разрядов сумма бит по модулю $(k+1)$ была равна нулю, то после изменения от одного до $k$ элементов снова получить нулевую сумму можно только «уравновешиванием» всех изменений: для всех элементов, где определенный бит удаляется, должен быть другой элемент, где этот бит добавляется. В частности, это должно выполняться и для самого старшего разряда, для которого хотя бы один бит у любого числа меняется. Но тогда это будет означать, что существует какой-то элемент, для которого добавилась единица в этом разряде, а все более старших разрядах ничего не менялось — значит, этот элемент будет больше исходного, что нарушает правила.
Осталось научиться переходить из состояний с ненулевыми суммами в нулевые. Назовём проблемными те позиции, для которых сумма битов получилась ненулевой. Переберем все биты от старшего к младшему и будем по очереди делать каждую проблемную сумму нулевой, уменьшая какое-то количество элементов.
Обозначим за $u$ количество кучек, которые мы уже начали изменять; изначально, $u = 0$. Обратим внимание, что так в этих $u$ кучках мы уменьшали какой-то из предыдущих, более старших, битов, то все более младшие биты мы можем ставить как угодно.
Пусть мы рассматриваем текущий бит, в котором сумма по модулю $(k+1)$ получилась ненулевой. В идеале, мы хотим сделать её нулевой, изменяя в этом разряде только те $u$ элементов, которые мы и так уже собрались изменять. Мысленно поставим во всех из этих $u$ элементов единицы в соответствующем разряде и пересчитаем сумму, обозначив её за $s$. Теперь рассмотрим два случая:
- Если $s \le u$, то мы можем обойтись уже выбранными элементами, убрав в $s$ из них единичный бит.
- В противном случае, если $s > u$ найдем $(s - u)$ дополнительных кучек, у которых рассматриваемый бит единичный, и будем уменьшать их вместе с $u$ уже имеющимися.
После каждой итерации число $u$ изменяемых кучек станет равным $u' = \max(s, u) \le k$.
Таким образом, мы показали способ выбирать множество изменяемых кучек и какие биты следует в них изменять, чтобы общее их количество $u$ никогда не превысило $k$. Следовательно, мы доказали, что искомый переход из состояния с ненулевой суммой в состояние с нулевой суммой всегда существует, что и требовалось доказать.
Зачем это вообще надо?
Цугцвангом (от немецкого zug — ход, и zwang — принуждение) в шахматах и многих других стратегических играх называют ситуацию, когда у игрока закончились хорошие ходы, и если бы правила позволяли, он бы просто стоял на месте и передал ход оппоненту.
Ход белых. Мат в 2 хода.
Выясняется, что игр, основанных на идее приведения противника к цугцвангу, очень много, и они все эквивалентны ниму — в том смысле, что их графы с точки зрения выигрышности суммы отдельных игр работают точно так же, как графы нима.
Похожие темы научных работ по математике , автор научной работы — Пискарев Алексей Валерьевич
Решение логических задач как основа развития мышления Игра ”Удаление цифр” и связанная с ней Ладейная игра мизер Максимальный гарантированный результат в иерархических играх i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.Текст научной работы на тему «Игра «Ним» оценка игровой ситуации. Алгоритм игры»
Пискарев Алексей Валерьевич
ОЦЕНКА ИГРОВОЙ СИТУАЦИИ. АЛГОРИТМ ИГРЫ
Широко известна игра «Ним». Правила ее очень просты. Играют двое. На столе перед ними лежат несколько кучек каких-то предметов, например, спичек. Игроки ходят по очереди, и каждый игрок в свой ход выбирает одну из кучек и изымает из нее любое количество спичек. Если он изымет все спички из выбранной кучки, то она перестает существовать. Выигрывает тот игрок, который своим очередным ходом сумеет забрать все оставшиеся спички.
Пусть перед нами лишь одна кучка спичек. Что делать - ясно: забрать все спички из этой кучки и выиграть.
Что, если перед нами две кучки, и в них одинаковое количество спичек? Тог-
. лефаН Нескольку кугек клких-Наа прерме&аб, Например,, спигек.
да мы, вероятнее всего, проиграем: сколько бы мы ни брали из одной кучки, наш партнер будет брать столько же из другой и в результате выиграет.
А если две кучки, но с разным количеством спичек? Тогда опять ситуация в нашу пользу: мы можем своим ходом уравнять две кучки и свести ситуацию к предыдущей, которая теперь будет проигрышной уже для нашего партнера.
Можно придумать много разных ситуаций, которые при рассмотрении оказываются заведомо выигрышными или проигрышными.
Возникает вопрос: любая ли ситуация окажется выигрышной или проигрышной?
Выходит, что да, любая. И вот почему. Ситуация с одной-единственной спичкой заведомо выигрышная. Далее будем рассматривать последовательно все варианты более сложных ситуаций для любого количества спичек. Если в какой-то ситуации найдется такой ход, который обеспечивает противнику проигрышную ситуацию (более простую, уже рассмот-
ренную), то эту ситуацию следует считать выигрышной; если же такого хода не найдется и любой ход будет переводить игру к выигрышной для противника ситуации, то такая ситуация для нас - проигрышная.
Итак, любая ситуация в игре «Спички» или выигрышная, или проигрышная. Но как определить тип сложившейся ситуации на практике, по ходу игры? Способ прямого перебора в действительности неприменим из-за своей трудоемкости. Для ответа на этот вопрос обратимся к представлению чисел в двоичной системе счисления.
Дальнейшие рассуждения сопровождаются рассмотрением примера конкретной игровой ситуации -в фигурных скобках перечислены объемы имеющихся пяти кучек.
Представим все заданные числа в двоичной системе счисления: 18=(10010)2 8=(1000)2 14=( 1110)2 9=(1001)2 23=(10111)2
Теперь все эти представления чисел выпишем в столбик цифра под цифрой так, чтобы одна под другой оказались цифры одинаковых разрядов (то есть как при сложении в столбик):
Крестиками следует отметить те столбики, в которых стоит нечетное количество цифр 1. Теперь рассмотрим два возможных случая: какое-то количество столбиков отмечено («крестики есть») и ни один столбик не отмечен (если во всех столбиках количество цифр 1 четно -«крестиков нет»).
Пусть «крестики есть». Тогда найдем первый слева из них и выберем любое из заданных чисел, в котором цифра над этим крестиком равна 1 (здесь таких чисел три: 8, 14 и 9; выберем, например, 8). Проделаем над числом 8 такую операцию: те цифры 1 и 0 двоичной записи этого числа, под которыми оказались крестики, заменим на противоположные (0 на 1 и 1 на 0), остальные цифры оставим без изменения:
Получилась двоичная запись числа 2. Следует совершить ход, оставив из 8 спичек 2 (забрать 6). Сложится новая ситуация .
Покажем, что в любом случае новое число (С) будет строго меньше старого (А). Действительно, пусть есть выбранное нами двоичное число
- двоичные цифры, стоящие в столбиках левее первого слева крестика (возможно, их вовсе нет, п = 0), а Ь , Ь , . , Ь
- цифры, стоящие правее первого слева крестика (их тоже может не быть, т = 0). После описанного выше преобразования числа А мы получим число
Первые п цифр останутся неизменными, следующая цифра поменяется с 1 на 0, и как-то могут поменяться остальные цифры. Из наглядного поразрядного сравнения чисел А и С:
С = (а а л. ал0с с
ясно, что А > С (так как 1 > 0).
Теперь после нашего хода партнер, совершая подсчет аналогичным образом, не получит ни одного крестика (подумайте, почему). Рассмотрим этот вариант.
Итак, «крестиков нет». Тогда ход партнера не станет последним в игре. Вот почему: ход мог бы стать последним, только если на столе ле-
жит лишь одна кучка, но в таком случае хотя бы один крестик обязательно получится. Значит, на столе осталось более одной кучки, и ближайший ход не завершит игру.
Пусть игрок совершит любой ход. Найдется столбик двоичных цифр, который изменится от этого хода, причем ровно на одну единицу. И тогда количество цифр 1 в этом столбике станет нечетным, и мы при подсчете поставим под ним крестик и без крестиков, таким образом, не останемся.
Понятно, что если игра будет так продолжаться (то есть если мы будем продолжать придерживаться того же метода
выбора хода), то выиграем в результате именно мы, так как ни один ход нашего партнера не сможет завершить игру (рассмотрите самостоятельно, к чему приведет этот метод, если на столе останется только одна кучка спичек).
@пособ пр&мого перебарл 6 $ейаНбиАел-&НосНи неприменим и^-^л с6ош НруддемкооНи.
От редакции. Полезным упражнением для читателей будет написание программы для игры в «Ним», для этого можно использовать логическую операцию ХОЯ - исключающее «ИЛИ», которая позволит простыми вычислениями определять правильные ходы.
Прочитав статью Борзых А.К. «Универсальная самообучающаяся машина из спичечных коробков» в этом же номере журнала и познакомившись с самообучающимися машинами, можно попробовать сделать программу, которая научится играть в «Ним», не зная правильной стратегии! А в качестве учителя использовать программу, которая эту стратегию знает!
Пискарев Алексей Валерьевич, студент V курса СПбГЭТУ (ЛЭТИ) кафедры автоматизированных систем обработки информации и управления.
Для этой игры используется несколько кучек камней. За один ход разрешается взять любое количество камней из одной любой кучки (можно взять даже все камни из одной кучки). Выигрывает игрок, взявший последний камень.
Вот пример игры:
Красным цветом показан ход первого игрока, зеленым - второго.
В этой партии победил второй игрок.
Рассмотрим короткий и эффективный способ определения исхода игры в "Ним" (при условии, что оба игрока играют разумно).
Пусть для игры взяли кучки из 7, 8 и 10. Разложим эти числа в суммы степеней двоек, как показано в таблице:
Первый игрок должен сделать такой ход, чтобы в каждом столбце осталось четное число звездочек. Для этого он может взять 5 камней из первой кучки, оставив сопернику такую позицию:
Теперь второй игрок вынужден нарушить четность количества звездочек хотя бы в одном из столбцов: ведь он может брать камни только из одной кучки, то есть менять только одну из строк таблицы. Предположим, что он взял 3 камня из последней кучки, оставив первому такую позицию:
Первый игрок снова может восстановить четность во всех столбцах, взяв три камня из второй кучки:
Так игра продолжается до тех пор, пока первый игрок не заберет последний камень.
Позиция является выигрышной тогда и только тогда, когда количество звездочек в каждом столбце четно. В противном случае позиция является проигрышной. Это правило верно для любого количества кучек камней, в этом случае порязрядный XOR нужно применить ко всем числам.
Сформулируем полученный результат более формально.
Пусть m и n — неотрицательные целые числа.
Возьмем двоичные представления этих чисел, и применим к ним поразрядно операцию "исключающее или" (XOR).
Позиция (m, n) является проигрышной тогда и только тогда, когда m XOR n = 0.
Рассмотрим пример. Пусть m = 21 и n = 39, переведем эти числа в двоичную систему и вычислим поразрядный XOR:
Таким образом, комбинация камней 21 и 39 является выигрышной.
Выигрышные ходы
Итак мы выяснили, что игрок, который каждым своим ходом восстанавливает четность количества камней во всех кучках, выигрывает. Но почему из любой позиции можно получить позицию с четным числом камней во всех кучках? Для этого можно воспользоваться следующим алгоритмом нахождения выигрышного хода.
Мы будем иллюстрировать шаги нашего алгоритма на примере позиции (19, 25, 12)
Представим числа в двоичной системе и применим поразрядно операцию XOR.
Найдем самую левую ненулевую цифру суммы, и мысленно сотрем все, что записано левее. В нашем примере это будет выглядеть так:
Действительно, цифры левее найденной уже равны 0 и делать с ними еще что-то не нужно, наоборот, вмешательство требуется в правой части, где в результате получаются единицы в разных разрядах.
Среди оставшихся слагаемых выберем наибольшее. В нашем примере это число 01100.
Уменьшим это слагаемое до требуемого значения.Чтобы получить результат (00000), необходимо уменьшить выбранное число до (01010).
Примеры других игр.
В шоколадке размером m x n долек в одной из долек оказался камень. Двое играют в такую игру: они по очереди разламывают шоколадку на две части по одной из линий, и съедают часть без камня. Проигрывает тот, кому достается одна долька с камнем. Кто выигрывает при правильной игре?
На полоске 1 x n в каждой клетке может лежать не более одной монеты. За один ход разрешается передвинуть любую монету влево на любое количество клеток не перепрыгивая через другие монеты. Проигрывает игрок, который не может сделать очередного хода.
В следующей игре каждый из игроков контролирует фишки одного цвета. За один ход можно передвинуть любую фишку своего цвета на любое количество клеток влево или вправо, не перепрыгивая через другие фишки. Кто выигрывает при правильной игре? Может ли эта игра закончится вничью при правильной игре обоих игроков?
Изменим правила игры Ним: будем считать проигравшим того игрока, который возьмет последний камень. Как изменится анализ этой игры?
Правила
Игра Ним попала в Европу в XVI веке из Китая. Имя «ним» было дано игре американским математиком Чарльзом Бутоном (англ. Charles Bouton), описавшим в 1901 году выигрышную стратегию игры.
Существует несколько вариантов происхождения названия игры:
- от немецкого глагола Nimm или старо-английского глагола Nim, имеющих значение «брать»;
- от английского глагола WIN («побеждать»), переворачиванием слова;
Ним — математическая игра, в которой два игрока по очереди берут предметы, разложенные на несколько кучек. За один ход может быть взято любое количество предметов (большее нуля) из одной кучки. Выигрывает игрок, не взявший последний предмет.
Показать полное описание Скрыть полное описание
Верхняя панель кнопок в игре с компьютером
Мариенбад (1,3,5,7) — в этом режиме на игровом поле находятся 4 ряда спичек с 1, 3, 5 и 7 спичками в каждом.
Ним 5 рядов — в этом режиме на игровом поле находятся 5 рядов спичек, в каждом из которых от 1 до 10 спичек.
Начать сначала — начинает текущую игру заново.
Новая игра — начинает новую игру.
Во всех режимах в случае заполнения всего поля и равного количества окруженных точек присуждается ничья.
Дополнительные кнпоки в совместной игре
Сдаться — завершает игру (засчитывается поражение).
Покинуть игру — позволяет немедленно завершить текущую игру (засчитывается поражение).
Нижняя панель кнопок
Настройки — открывает меню настроек, в котором вы можете:
- Изменить размер поля для совместной игры;
- Включить/выключить звук в игре;
- Запретить другим игрокам отправлять вам приглашения;
- Открыть черный список игроков.
История — история всех ваших игр с указанием даты игры, противника и его места в рейтинге.
Жёлтым цветом отмечены выигранные вами партии, красным – проигранные, синим – завершенные ничьей.
Звёздочкой отмечены игры, занесённые вами в избранное.
Очки начисляются только за победы над противниками (за ничьи и победы над компьютером очки не начисляются).
Начисление очков идет по системе Эло.
Система рейтингов Эло, коэффициент Эло — метод расчёта относительной силы игроков в играх, в которых участвуют двое игроков. Эту систему рейтингов разработал американский профессор физики венгерского происхождения Арпад Эло.
Авторизация / Личный кабинет — возможность войти в личный кабинет (ЛК), произвести авторизацию или зарегистрироваться.
Читайте также: