Эта статья возникла из личного публичного аккаунта:TechFlow, оригинальность это не просто, прошу внимания
СегодняАлгоритмы и структуры данныхВ специальных 26 статьях давайте рассмотрим новую модель теории игр — подзадачу Ним.
Эта игровая проблема очень старая,длится тысячи лет, только в начале 20-го века математик из Гарвардского университета нашел решение, которое показывает сложность его мышления. Но сам вопрос очень интересен, а процесс вывода еще интереснее, даже если у вас не так много базы данных, вы точно сможете в нем разобраться.
Проблема с ним
Название этого вопроса такое, у нас есть 3 кучки камней, есть два человека А и БПо очереди берите камни из одной из куч. Оговорено, что каждый человек будет брать не менее 1 штуки за раз, а текущую кучу можно взять максимум.Те, кто не может продолжать брать камни, терпят поражение. Есть ли у вас выигрышная стратегия, если вы делаете первый ход?
Согласно нашей предыдущей процедуре анализа игровой задачи Вежова, нам нужно сначала проанализировать задачу и найти несколько типичных ситуаций. Например, (0, 0, 0) должен быть побежден для первого хода Аналогично, для позиции (0, n, n) он также должен быть побежден. Потому что как бы первая рука ни брала камни, второй руке нужно толькоСделайте то же самое в другой куче камней., то для первого хода еще остается (0, n, n) позиция. В задачах теории игр мы обычно называем ситуацию первого хода и проигравшего какстранная ситуация.
Так есть ли какая-то связь между этими странными ситуациями? Можем ли мы найти связь или формулу между этими ситуациями?
Нам очень трудно придумать причудливые ситуации, которые мы можем придумать, просто думая об этом в уме или с ручкой и бумагой, иначе это не озадачивало бы людей более тысячи лет. Но ответ на этот вопрос так прост, невероятно прост.
Прежде всего, давайте подумаем о задаче.Фундаментальная причина сложности этой задачи состоит в том, что вместо двух куч стоят три кучи камней.Если есть две кучки камней, то легко, побеждает тот, кто сделает первый ход, если две кучки камней не равны. Потому что он может оставить две стопки одинаковых для второй руки, взяв камни, так что независимо от того, как вторая рука возьмет его, первой руке нужно только выполнить ту же операцию в другой стопке, и это неизбежно оставит странное ситуация на вторую руку. Это то же самое, что и ситуация (0, n, n), которую мы только что проанализировали.
Но в заголовке четко сказано, что 3 стопки вместо двух, мы не можем не начать представлять проблему, мыМожете ли вы придумать стратегию «преобразования» трех кучек камней или обращения с ними как с двумя кучками камней?? Таким образом, мы можем легко судить, выиграл камень или проиграл.
анализ решения
Там явно три кучи камней, как это можно считать двумя кучами? В любом случае, это все разговоры с самим собой, но если вы знакомы с двоичным кодом, вы увидите, что эта проблема не является неразрешимой.
Да, бинарник — это естественное двухмерное «существо», в бинарном мире есть только два вида всего, 0 и 1. Так что интуитивно мы бы чувствовали, что,Может быть, можно соотнести количество камней с двоичным числом?. Возможно, такая корреляция поможет нам найти решение. Остается вопрос, что именно представляет собой эта ассоциация?
Давайте подумаем над другой проблемой: для кучи камней, если взять количество, количество камней уменьшится, что очевидно. Это отражается в общем количестве камней, которое представляет собой число, представляющее количество камней в куче, за вычетом другого числа. Это операция вычитания, и ученики начальной школы знают ее. Но чего не знают ученики начальной школы, так это того,Как работает вычитание в двоичном формате, или в этом есть какой-то закон?
Не будем спешить с первым ответом, давайте внимательно его проанализируем. Во-первых, и вычитаемое, и уменьшаемое можно преобразовать в двоичное число, т. е. в число из 1 и 0. Мы предполагаем, что значение уменьшаемого, соответствующее каждому 1 двоичному биту вычитаемого, также равно 1, тогда вычитание будет происходить очень гладко. Это соответствует процессу удаления ряда единиц из вычитаемого.
Например, уменьшаемое равно 9, а вычитаемое равно 1. Все мы знаем, что 9, записанное в двоичном формате, равно 1001, а 1 в двоичном формате — это 1. Таким образом, значение уменьшаемого минус вычитаемое равно 8, что равно 1000, что можно рассматривать как 1001 с удаленной единицей в конце.
Если вычитаемое имеет двоичную цифру 0, например 10 - 3, двоичная цифра 10 равна 1010, а двоичная цифра 3 равна 11. Очевидно, что 0-й бит 3 равен 1, а 10 равен 0, что мне делать в этом случае? Во-первых, мы сначала удаляем двоичные биты, которые являются единицами из 3 и 10. Остаток равен 1000 минус 1, тогда мы можем сначала вычесть 1 из 1000, чтобы получить 111, поэтому мы возвращаемся к первому случаю, упомянутому выше, а затем добавляем его обратно после вычитания, так что результат равен 111, что равноПо сути, это процесс заимствования с высокого положения.. На протяжении всего процесса вычисления вычитания это на самом деле вычитаемоеПроцесс изменения двоичных битов, вычитание определенного числа эквивалентно превращению нескольких нулей в 1 и 1 в 0 в уменьшаемом конце.
В сочетании с бинарным мы можем придумать стратегию. Это подсчет всех двоичных битов этих чисел 3. Поскольку у нас есть числа 3, поэтомуКаждая двоичная цифра имеет не более 3 единиц и не менее 0 единиц.. Если сумма количества единиц в каждом бите четная, то есть либо 0, либо 2, то это должна быть исключительная ситуация.
Например, скажем, [10, 8, 2] — это единичная ситуация, мы записываем их в двоичном формате. 10 в двоичном формате — это 1010, 8 в двоичном — 1000, а 2 в двоичном — 10. Таким образом, мы можем обнаружить, что двоичные разряды этих трех чисел складываются, и две единицы появляются в 1-й, 2-й и 3-й цифрах. В это время, независимо от того, как работает первая стрелка, второй стрелке нужно только убедиться, что двоичные биты оставшихся трех чисел сохраняют эту функцию. Это гарантирует, что после завершения последнего дубля у первого игрока останется [0, 0, 0]. По сути,Его принцип тот же, что и при наличии двух куч камней., а превратилась в форму.
Например, если мы возьмем 3 камня из 10 и получим (7, 8, 2), мы увидим, что двоичные цифры равны 111, 1000, 10 соответственно. Будет обнаружено, что число каждой 1 равно [1, 2, 1, 1] от младшего к старшему. так что мыВы можете взять 3 камня из 1000 и убедиться, что осталось 101, то есть 5.. Таким образом, количество оставшихся единиц равно [2, 2, 2], что по-прежнему является четным числом. Поэтому, как бы ни взял первый ход, второй ход может гарантировать, что оставшиеся числа останутся четными в двоичном виде, и первый ход обязательно проиграет. В ситуациях, которые не удовлетворяют этому условию, первый ход должен выиграть, потому что первый ход может убрать лишнюю 1 при первом проходе, гарантируя, что проигрышная позиция останется для второго хода.
Это также решение этой проблемы, то есть определить, выиграет ли первый ход, по двоичным числам. Нам нужно определить, является ли сумма количества единиц, которые появляются в каждом двоичном бите, четным числом,Это можно сделать побитовым ИЛИ. В операции ИЛИ вычисляется каждый двоичный бит, нечетное число равно 1, а четное число равно 0. Таким образом, нам нужно только вычислить, равен ли результат этих трех кучек камней или после них 0, и тогда мы можем узнать, является ли количество единиц в каждом двоичном бите четным числом.
Код, который мы пишем, очень прост, мы обычно используем символ ^ для обозначения операции ИЛИ, поэтому в коде достаточно одной строки:
def win_or_lose(a, b, c):
return (a ^ b ^ c) == 0
продвижение и доказательство
Это еще не конец, мы тоже можемОбобщите положение 3 кучек камней до n кучек., сколько бы кучек камней ни встретил игрок в игре, этот вывод остается в силе. Причину этого легко понять: ради строгости мы можем доказать это с помощью обычных процедур доказательства для игровых задач.
В игровой задаче, если есть сингулярная ситуация, т. е. некоторая проигрышная ситуация, тоДолжны быть соблюдены три условия. Первое условие заключается в том, что ситуация, в которой ничего нельзя сделать, является исключительной ситуацией. Второе условие состоит в том, что позиция, которую можно переместить в сингулярную позицию, не является сингулярной позицией. Третье условие состоит в том, что любая операция, выполняемая в сингулярной ситуации, приводит к несингулярной ситуации.
Пока мы можем доказать эти три пункта, мы можем доказать, что наше мышление правильно.
Нет сомнения в первом пункте, когда все каменные кучи не имеют камней, они не могут двигаться, что является определенным состоянием поражения.
Рассмотрим второе условие Предположим, что количество n кучек камней равно a1, a2, ... an. Если текущая позиция является неособой позицией, согласно нашей теории, то a1 ^ a2 ^ a3 ^... ^an > 0. Другими словами, в определенном двоичном бите есть нечетное количество единиц.
Предположим, что a1 ^ a2 ^ a3 ^... ^an = k, тогдаДолжна быть возможность найти такое ai, что его двоичное представление равно 1 в старшем бите k., поскольку все двоичные единицы числа k взяты из этих n чисел, поэтому такое ai должно существовать. Тогда мы можем продолжить вывод: ai^k Обе части уравнения одновременно или ai, вы можете получить a1^a2^...^ai-1^ai+1^...^an = k ^ai, поэтому a1^a2^...^p ^...an = 0.
Третье условие также легко доказать, потому что если текущая ситуация является ситуацией must-проигрыша, то есть a1 ^ a2 ^ ... ^ an=0. Предположим, что у нас все еще есть a1 ^ a2 ^ ... ^p=0, p
Таким образом, мы получаем изМатематически доказывает правильность этого рассуждения, на самом деле, некоторые люди уже провели углубленное исследование проблемы Нима, берущего сабы, что также является доказанной теоремой, называемойТеорема Бутона. Содержание теоремы состоит в том, что первый двигатель может выиграть несбалансированную игру NIM, а вторая Mover может выиграть сбалансированную игру NIM. Баланс здесь означает, что количество всех двоичных 1S является четным числом.
Далее пишем код тоже очень простой:
def win_or_lose(nums):
ret = 0
for i in nums:
ret ^= i
return ret == 0
Суммировать
На этом задача игры Ним решена. Решение для суждения по операции действительно очень простое, но понять процесс вывода непросто. Я видел много блогов, во всех из которых прямо дан тот или иной вывод, и редко могу увидеть подробный процесс вывода. Вывод легко запомнить непосредственно, но также легко и забыть,Только получив его лично, вы поймете, как произошла эта магическая операция., почему это может решить проблему игры Ним.
На протяжении всего процесса размышлений о рассуждениях и доказательствах мыШирокое использование или эта побитовая операция, это может показаться немного тревожным для студентов, которые не знакомы с ним. Предполагается, что вы можете сначала понять природу изучения двоичного кода или прочитать эту статью, и эффект будет лучше.
До сих пор мы представили по Bash Game, игре Weizuo Fu и игре Nim три относительно простые игровые модели. В следующей статье мыПродолжайте углубляться в проблему теории игр, давайте вместе изучим более сложные задачи теории игр и посмотрим, как мы можем найти сингулярные состояния в сложных сценариях.
Статья здесь, если вам понравилась эта статья, если можно, пожалуйстаобращать внимание, подбодрите меня и облегчите доступ к другим статьям.
В этой статье используетсяmdniceнабор текста