Как выиграть в игре ним с 2 кучами
Обновлено: 20.05.2024
Игра ним с двумя кучами камней, начальное количество камней в кучах задаёт пользователь
Игра ним с двумя кучами камней, начальное количество камней в кучах задаёт пользователь.
Компьютер (ИИ) играет против пользователя и ходит первым. В каждый ход можно взять сколько угодно камней из любой одной кучи. При этом нужно предусмотреть ситуацию, когда пользователь не сразу вводит корректное количество камней, которые он забирает.
Выигрывает забравший последний камень, и при окончании игры нужно объявить победителя.
Алгоритм для ИИ можно придумать самостоятельно, а можно найти в интернете.
Игра ним для двух игроков с одной кучей и ограничением на количество забираемых камней
Игра ним для двух игроков с одной кучей и ограничением на количество забираемых камней: за один ход.
Игра "Ним" с двумя кучами для одного игрока
Игра Ним с двумя кучами для одного игрока без ограничений на количество забираемых камней. На.
Игра "Ним" с тремя кучами камней
Игра ним с тремя кучами камней, начальное количество камней в кучах задаёт пользователь. Компьютер.
Подсчитать минимальное количество действий, которые надо совершить обезьянке, чтобы получить кучу из n камней
Цирк, цирк, цирк! Цирковая обезьянка еще не может быть полноценным игроком в Ним, но она обучена.
Текст научной работы на тему «Игра «Ним» оценка игровой ситуации. Алгоритм игры»
Пискарев Алексей Валерьевич
ОЦЕНКА ИГРОВОЙ СИТУАЦИИ. АЛГОРИТМ ИГРЫ
Широко известна игра «Ним». Правила ее очень просты. Играют двое. На столе перед ними лежат несколько кучек каких-то предметов, например, спичек. Игроки ходят по очереди, и каждый игрок в свой ход выбирает одну из кучек и изымает из нее любое количество спичек. Если он изымет все спички из выбранной кучки, то она перестает существовать. Выигрывает тот игрок, который своим очередным ходом сумеет забрать все оставшиеся спички.
Пусть перед нами лишь одна кучка спичек. Что делать - ясно: забрать все спички из этой кучки и выиграть.
Что, если перед нами две кучки, и в них одинаковое количество спичек? Тог-
. лефаН Нескольку кугек клких-Наа прерме&аб, Например,, спигек.
да мы, вероятнее всего, проиграем: сколько бы мы ни брали из одной кучки, наш партнер будет брать столько же из другой и в результате выиграет.
А если две кучки, но с разным количеством спичек? Тогда опять ситуация в нашу пользу: мы можем своим ходом уравнять две кучки и свести ситуацию к предыдущей, которая теперь будет проигрышной уже для нашего партнера.
Можно придумать много разных ситуаций, которые при рассмотрении оказываются заведомо выигрышными или проигрышными.
Возникает вопрос: любая ли ситуация окажется выигрышной или проигрышной?
Выходит, что да, любая. И вот почему. Ситуация с одной-единственной спичкой заведомо выигрышная. Далее будем рассматривать последовательно все варианты более сложных ситуаций для любого количества спичек. Если в какой-то ситуации найдется такой ход, который обеспечивает противнику проигрышную ситуацию (более простую, уже рассмот-
ренную), то эту ситуацию следует считать выигрышной; если же такого хода не найдется и любой ход будет переводить игру к выигрышной для противника ситуации, то такая ситуация для нас - проигрышная.
Итак, любая ситуация в игре «Спички» или выигрышная, или проигрышная. Но как определить тип сложившейся ситуации на практике, по ходу игры? Способ прямого перебора в действительности неприменим из-за своей трудоемкости. Для ответа на этот вопрос обратимся к представлению чисел в двоичной системе счисления.
Дальнейшие рассуждения сопровождаются рассмотрением примера конкретной игровой ситуации -в фигурных скобках перечислены объемы имеющихся пяти кучек.
Представим все заданные числа в двоичной системе счисления: 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). Сложится новая ситуация .
Покажем, что в любом случае новое число (С) будет строго меньше старого (А). Действительно, пусть есть выбранное нами двоичное число
i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.- двоичные цифры, стоящие в столбиках левее первого слева крестика (возможно, их вовсе нет, п = 0), а Ь , Ь , . , Ь
- цифры, стоящие правее первого слева крестика (их тоже может не быть, т = 0). После описанного выше преобразования числа А мы получим число
Первые п цифр останутся неизменными, следующая цифра поменяется с 1 на 0, и как-то могут поменяться остальные цифры. Из наглядного поразрядного сравнения чисел А и С:
С = (а а л. ал0с с
ясно, что А > С (так как 1 > 0).
Теперь после нашего хода партнер, совершая подсчет аналогичным образом, не получит ни одного крестика (подумайте, почему). Рассмотрим этот вариант.
Итак, «крестиков нет». Тогда ход партнера не станет последним в игре. Вот почему: ход мог бы стать последним, только если на столе ле-
жит лишь одна кучка, но в таком случае хотя бы один крестик обязательно получится. Значит, на столе осталось более одной кучки, и ближайший ход не завершит игру.
Пусть игрок совершит любой ход. Найдется столбик двоичных цифр, который изменится от этого хода, причем ровно на одну единицу. И тогда количество цифр 1 в этом столбике станет нечетным, и мы при подсчете поставим под ним крестик и без крестиков, таким образом, не останемся.
Понятно, что если игра будет так продолжаться (то есть если мы будем продолжать придерживаться того же метода
выбора хода), то выиграем в результате именно мы, так как ни один ход нашего партнера не сможет завершить игру (рассмотрите самостоятельно, к чему приведет этот метод, если на столе останется только одна кучка спичек).
i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.@пособ пр&мого перебарл 6 $ейаНбиАел-&НосНи неприменим и^-^л с6ош НруддемкооНи.
От редакции. Полезным упражнением для читателей будет написание программы для игры в «Ним», для этого можно использовать логическую операцию ХОЯ - исключающее «ИЛИ», которая позволит простыми вычислениями определять правильные ходы.
Прочитав статью Борзых А.К. «Универсальная самообучающаяся машина из спичечных коробков» в этом же номере журнала и познакомившись с самообучающимися машинами, можно попробовать сделать программу, которая научится играть в «Ним», не зная правильной стратегии! А в качестве учителя использовать программу, которая эту стратегию знает!
Пискарев Алексей Валерьевич, студент V курса СПбГЭТУ (ЛЭТИ) кафедры автоматизированных систем обработки информации и управления.
Игра "Ним" с двумя кучами для одного игрока
Игра Ним с двумя кучами для одного игрока без ограничений на количество забираемых камней.
На первой и второй строках указывается начальное количество камней в первой и второй кучах. Далее идут ходы, каждый из которых представляется двумя числами на отдельных строках: на первой строке 1 или 2 — номер кучи, из которой берутся камни; на второй строке — количество забираемых камней.
Программа выводит количество камней в двух кучах после каждого хода.
Формат ввода
Первые две строки содержат количество камней в первой и второй кучках, соответственно.
Далее следуют описания ходов в формате, описанном в условии. Гарантируется, что количество забираемых камней каждый раз корректное, и что последним ходом игрок забирает последний камень.
Формат вывода
В ответ на каждый ход игрока выведите два числа через пробел — количество камней в первой и второй кучках после этого хода.
Игра "Ним" с тремя кучами камней
Игра ним с тремя кучами камней, начальное количество камней в кучах задаёт пользователь. Компьютер.
Игра ним с двумя кучами камней, начальное количество камней в кучах задаёт пользователь
Игра ним с двумя кучами камней, начальное количество камней в кучах задаёт пользователь. .
Для каждой строки найти слова, которые не имеют ни одного из букв: "l", "k", "r", "s" i "j"
Задано символьные строки. Строка состоит из нескольких слов (наборов символов), которые разделяются.
Игра "Ним". Двойная буферизация. Логика.
Здравствуйте. Вообще-то задание взято с моей лабы и я ее уже сдал, но все же интрига остается, так.
Стратегические игры и решение задач. Игра Ним и ей подобные
Сосредоточим внимание на так называемых стратегических играх. Их можно разделить на два типа. Те, что описываются простыми правилами, длятся короткое время и количество информации в которых ограничено или относительно невелико, будем называть малыми стратегическими играми.
В других, подобных шахматам или го, полный контроль невозможен ввиду длительности партии, сложности правил и в особенности из-за огромного числа возможных ходов в каждой позиции. На примере малых стратегических игр мы увидим, как математика используется в анализе игр для определения преимущества одного из игроков и для нахождения выигрышной стратегии.
подобного типа был впервые опубликован в 1902 году математиком Гарвардского университета Чарльзом Леонардом Боутоном.
Определение общей выигрышной стратегии, применимой к любой игре такого типа, — одно из ярчайших проявлений того, как математика используется для анализа игр, и в особенности того, насколько эффективно представление чисел в двоичной системе.
Об определении стратегии
Сначала мы проанализируем игры с одной группой фишек, в которых на каждом ходу можно брать со стола минимум одну и максимум n фишек. Мы рассмотрим два частных случая, затем приведем обобщение. Самый простой вариант подобной игры таков.
Игра 1: выигрывает первый
На стол выкладываются 20 фишек одного цвета. На каждом ходу один из двух игроков может брать одну или две фишки. Тот, кто берет последнюю фишку, выигрывает. Какой из игроков имеет преимущество — тот, кто ходит первым, или второй участник? Как нужно играть, чтобы всегда выигрывать? Что произойдет, если изменится число фишек? Что поменяется, если мы изменим правила игры и тот, кто берет последнюю фишку, будет проигрывать? Это достаточно простая игра, поэтому ее можно проанализировать полностью, определить выигрышную стратегию и обобщить ее для любого числа фишек. Если вы незнакомы с этой игрой, перед прочтением попробуйте сыграть в нее самому и постараться ответить на заданные выше вопросы.
Сыграв несколько партий, вы быстро обнаружите, что если кто-то из игроков оставил на столе 3 фишки, то следующим ходом он обязательно выигрывает. Верно подмечено, но это не поможет нам всегда выигрывать: мы не знаем, какие ходы нужно совершать, чтобы на столе осталось 3 фишки. Но теперь мы знаем, что выигрывает тот, кто взял фишку номер 17. Таким образом, число фишек в игре сокращается. Сделав еще один подобный шаг, мы увидим, что игрок, оставивший на столе 6 фишек, тоже будет всегда выигрывать. В общем, всегда выигрывает тот, кто оставляет на столе число фишек, кратное 3. Это позволяет сформулировать выигрышную стратегию: когда в начальной позиции на столе 20 фишек, первый игрок будет всегда выигрывать, если будет брать первым ходом 2 фишки и затем всегда оставлять на столе количество фишек, кратное 3 (если второй игрок снимает одну
фишку, первый игрок должен взять две, и наоборот). В этой игре первый игрок имеет преимущество, так как для него существует выигрышная стратегия.
Изменение начального количества фишек может частично повлиять на эту стратегию и даже на то, какой из игроков будет иметь преимущество. Теперь мы знаем, что выигрышная стратегия состоит в том, чтобы оставлять на столе число фишек, кратное 3. Чтобы узнать, на чьей стороне преимущество, достаточно разделить начальное количество фишек на 3 и посмотреть, каков остаток от деления. Если остаток равен 2 (как в исходном случае), то первый игрок всегда выигрывает, если берет первым ходом 2 фишки, а затем оставляет на столе число фишек, кратное 3 (если противник берет одну фишку, первый игрок берет две, и наоборот). Если остаток от деления равен 1 (например, число фишек равно 19, 25, 100 или 2017), то первый игрок также выигрывает. Для этого достаточно взять первым ходом одну фишку. Наконец, если остаток равен 0 (количество фишек делится на 3), то выигрывает второй игрок: ему нужно взять две фишки, если первый игрок взял одну, и наоборот. В этом случае первый игрок никогда не сможет оставить на столе число фишек, кратное 3.
Таким образом, мы обобщили игру для любого начального числа фишек. Игру
можно обобщить и дальше, изменив число фишек, которые можно брать на каждом
Игра 2: выигрывает второй
Первый игрок пишет на бумаге число от 1 до 10. Второй игрок придумывает число от 1 до 10 и записывает результат сложения этого числа с первым. На каждом ходу игрок прибавляет к общей сумме новое придуманное им число от 1 до 10. Тот игрок, который запишет трехзначное число (100 и больше), проигрывает. Как нужно играть, чтобы выигрывать? Какой из игроков имеет преимущество: тот, кто ходит первым или вторым? Что произойдет, если изменится цель игры или правила?
Как уже предлагалось ранее, будет удобно сыграть несколько партий самому, чтобы попытаться определить выигрышную стратегию для одного из игроков и понять, как эта игра связана с предыдущей. Будем анализировать игру следующим образом: если проигрывает тот, кто напишет 100, выигрывает тот, кто напишет 99. Какое число нужно написать до этого, чтобы гарантированно получить 99 на следующем ходу? Это 88, так как в этом случае противник напишет любое число между 89 и 98, после чего первый игрок легко получит 99. Как и в прошлой игре, продолжая подобные рассуждения (перейдя к числу 88, затем 77, 66, . 11), мы увидим, что на этот раз нужно формировать группы по 11. Теперь нам известна выигрышная стратегия: тот, кто первым записывает 11 и последующие числа, кратные 11, первым получит 99 и выиграет. Если противник прибавляет n, нужно прибавлять 11 - n. Так как на первом ходу первый игрок не может получить 11, а второй может, это означает, что существует выигрышная стратегия для второго игрока. Как и в прошлой игре, при изменении конечного числа будет выигрывать первый игрок, если это число не будет кратно 11. Если это число будет делиться на 11, всегда будет побеждать второй игрок.
Игра 3: общий случай
Допустим, что на столе m фишек и каждым ходом можно брать от 1 до m фишек (n < m). Выигрывает тот, кто забирает последнюю фишку. Для какого из игроков существует выигрышная стратегия — для первого или второго? В чем она заключается? Если игрок, взявший последнюю фишку, будет проигрывать, как изменится стратегия?
Речь идет не об одной игре, а о группе абстрактных игр. Две предыдущие игры — ее частные случаи. Следовательно, выигрышная стратегия для этой игры — это общая стратегия, которая применима к бесконечному множеству аналогичных игр. Эта стратегия формулируется так. Поделим m на n + 1 и определим остаток от деления. Он будет находиться в интервале от 0 до n. Возможны два случая:
Это общее решение применимо к бесконечному множеству игр. Вы можете применить его для такой игры: на столе 2010 фишек, на каждом ходу можно брать от 1 до 49 фишек. Для какого игрока существует выигрышная стратегия? В чем она заключается? Если мы изменим правила и тот, кто берет последнюю фишку, будет проигрывать, то достаточно заметить следующее: для победы будет достаточно взять предпоследнюю фишку, оставив на столе всего одну. В этом случае стратегия не изменится, просто нужно будет учесть, что число фишек равно
m - 1, а не m.
. для победы будет достаточно взять предпоследнюю фишку, оставив на столе всего одну. В этом случае стратегия не изменится, просто нужно будет учесть, что число фишек равно
m - 1, а не m.
Вроде бы автор дал нам все что надо, что бы найти выигрышную стратегию для такого случая. Но для таких как я, которых не поняли у кого преимущество объясню подробнее:
В этом случае если, игрок берёт последнюю фишку и проигрывает, то определение преимущества немного меняется.
Стратегия остаётся той же: поделим m на n + 1 и определим остаток от деления.
Но теперь нам нужны другие остатки от деления.
Если остаток 0 или от 2 до n - 1 (1 ; n), то действует случай 2.
Соответственно, если остаток 1 или n, то действует случай 1. Все эти случаи описаны выше, но для них добавляется одна маленькая деталь:
теперь надо оставлять на столе число фишек равное i + 1 (i - это число кратное n + 1).
Все подобные игры, в которых используется только одна группа фишек, можно
считать упрощенными вариантами игры Ним, о которой я напишу в следующем посте.
Похожие темы научных работ по математике , автор научной работы — Пискарев Алексей Валерьевич
Решение логических задач как основа развития мышления Игра ”Удаление цифр” и связанная с ней Ладейная игра мизер Максимальный гарантированный результат в иерархических играх i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.Читайте также: