Эта статья возникла из личного публичного аккаунта:TechFlow, оригинальность это не просто, прошу внимания
Сегодня этоТемы алгоритмов и структур данныхВ статье 27 мы продолжаем углубляться в проблемы теории игр. Сегодня мы познакомим вас с очень важной теоремой и функцией в теории игр, с помощью которых мы можем решать многие игровые задачи, которые кажутся запутанными, что позволяет нам легко решать большой класс игровых задач.
С функцией SG и теоремой SG мы больше не решаем проблемы, просто придумывая, анализируя и находя правила. А игры Bash, Wyzhov и Nim, которые мы изучили раньше, могут быть решены с помощью функции SG.Это равносильно тому, что мы нашли общее решение этого большого класса проблем.. Ниже мы рассмотрим несколько основных теорем и основных понятий.
Основная теорема
ICG игры
Как мы уже говорили ранее, функция СГ и теорема СГ могут решать большой класс игровых задач. Этот широкий класс игровых задач называетсяICG игры, три игровые модели, которые мы представили ранее, по сути являются играми ICG.
Что касается игры ICG, то она определяется следующим образом, и необходимо выполнить три условия:
- В игре участвуют два человека, и двое по очереди принимают решения, и решения, которые они принимают, являются лучшими для них самих.
- Когда один человек не может принять решение, этот человек терпит неудачу. Независимо от того, как они решат, игра закончится через ограниченное время.
- Одно и то же состояние не может быть достигнуто в игре несколько раз, и в игре нет ничьей. Набор решений, принимаемых игроком в определенном состоянии, связан только с состоянием и не имеет ничего общего с игроком.
Победа и победа
Другими словами, сингулярное состояние и несингулярное состояние мы определяем как состояние P как состояние неизбежного поражения, а состояние N как состояние неизбежной победы. Мы можем просто понять, что,Игрок в состоянии P обязательно проиграет, а игрок в состоянии N обязательно выиграет..
Этот момент был подробно проанализирован в предыдущей статье о выборке Ним.С точки зрения расширения, на самом деле их три:
- Состояние, в котором нельзя двигаться, — это состояние P.
- Состояние, которое может перейти в состояние P, это N
- Позиция, в которой все ходы будут идти в позицию N, называется P.
Когда мы анализировали игровую задачу Вежова, мы абстрагировали игровую ситуацию в точки в двумерной плоской системе координат. На самом деле всеИгры ICG можно представить как ориентированный ациклический граф (DAG)., игра начинается с пешки, помещенной в исходную точку, и два игрока по очереди перемещают пешку, пока игрок, который не может двигаться, не будет побежден. Все позиции, которые можно передвинуть только до конца, являются беспроигрышными, а все точки, которые можно соединить только с выигрышными очками, являются беспроигрышными. Мы можем вычислить состояние всех точек, используя рекурсивное мышление.
Конечно, перебор всех состояний с помощью алгоритма занимает у нас слишком много времени, мы можем вычислить его с помощью функции, которой и посвящена наша сегодняшняя статья -Функция СГ.
Вывод чисел Спрэга-Гранди
SG — это аббревиатура Sprague-Grundy, я правильно помню, это должно быть имя двух человек, оно очень простое в использовании, но процесс деривации немного сложен. Если мы проигнорируем происхождение и сразу перейдем к его использованию, вы почувствуете, что используете магию. Поскольку вы вообще не можете угадать его принцип, нам нужно подробно объяснить процесс его получения, чтобы углубить наше понимание.
Давайте сначала проясним несколько понятий. Во-первых, для игр ICG:Существует только одно конечное состояние отказа — точка, которую нельзя сдвинуть., которую можно рассматривать как конечную точку графа DAG. Отталкиваясь от этой конечной точки, все точки, которые могут напрямую соединиться с конечной точкой, составляют N точек. Это легко понять: если в текущем состоянии вы можете перейти в состояние обязательного поражения противника, то, конечно, текущий игрок должен победить.
Мы делаем простое наслоение этих состояний,Точка, которая может напрямую соединиться с точкой P, является состоянием победы первого уровня.. Например, состояние (1, 0) в ним-игре — это выигрышное состояние первого уровня, которое может привести только к точке P. мы кладемТочка, которая может стать проигрышным состоянием или выигрышным состоянием первого уровня, называется выигрышным состоянием второго уровня., например (0, 2) в игре ним. Например, когда он входит в (1, 0), это выигрышное состояние первого уровня, и он также может напрямую войти в (0, 0) и стать проигрышным состоянием.Мы называем это состояние выигрышным состоянием второго уровня. сродни,Если выигрышное состояние может стать проигрышным состоянием или всеми выигрышными состояниями уровня от 1 до n-1, такое состояние называется выигрышным состоянием n-го уровня., состояние поражения можно рассматривать как состояние победы уровня 0.
Затем мы смотрим на комбинацию выигрышных состояний и можем скопировать вывод из подзадачи Нима.Выигрышная комбинация из двух равных — проигрышное состояние.,Комбинация двух выигрышных состояний разного уровня является выигрышным состоянием.. Причина также очень проста, она такая же, как проблема с доставкой Нима, когда он сталкивается с двумя грудами одинакового количества камней, он проигрывает. Поскольку вторая рука может копировать операцию первой руки, до тех пор, пока операция больше не может быть продолжена, игра окончена. Для двух разных выигрышных состояний первый ход может преобразовать одно из них в такое же, как и другое, так что вторая рука сталкивается с одними и теми же двумя выигрышными состояниями, поэтому комбинация разных выигрышных состояний является выигрышным состоянием.
Обратите внимание, что для того, чтобы сделать этот вывод, есть два предварительных условия, первое из которыхВыигрышное состояние уровня n может быть переведено в любое выигрышное состояние уровня 1 - n-1. ВторойСтатус победы можно только понизить, но не повысить, на самом деле поднять его не проблема, а вторая рука может понизить уровень, поднятый первой рукой, и это не повлияет на вывод.
Если вы понимаете этот слой, наше определение ряда на самом деле является значением функции SG. Функцию SG можно использовать для сопоставления состояния с неотрицательным целым числом. Его формула записывается так:
в формулеA и B указывают статус,
Указывает, что состояние A может перейти в состояние B. mex — это функция, определенная для набора, которая возвращает наименьшее неотрицательное целое число, не принадлежащее этому набору. Например, mex(0, 1)= 2, mex(0, 2) = 1, mex(0,1, 2, 3)=4. То есть мы можемРассчитайте значение SG для A по значению функции SG для состояния, которое может достичь A..
Например, в задаче о сборе Нима, если камня нет, он будет побежден, и у него нет состояния преемника, поэтому SG(0) = 0. 1 камень можно переместить в 0, поэтому SG(1) = mex {SG(0)} = 1. так что мыЭто соответствует ряду выигрышных состояний в подзадаче Ним и задаче ICG.. Номер SG соответствует куче камешков в ним.Если у нас есть несколько кучек камешков, как мы рассчитываем статус выигрыша и проигрыша в начале? Из вывода задачи Нима о частичном взятии мы знаем, что она заключается в вычислении или значения количества камней в каждой куче камней.Если результат или последующий результат равен 0, то первый ход проиграет, в противном случае выиграет первый ход. Точно так же мы вычисляем значение SG всех состояний, еслиОкончательное значение SG или результат равен 0, что указывает на то, что первый ход проиграет, в противном случае первый ход выиграет..
Что касается SG (A + B) = SG (A) xor SG (B), мы можем доказать это с помощью математической индукции, но это доказательство не обязательно. Нам важнее понять идею и процесс вывода функции SG . Наконец, мы используем функцию SG, чтобы увидеть пример проблемы.
практический пример
Давайте рассмотрим улучшенную версию задачи Нима о добыче.Предположим, что есть n кучек камней, и в каждой кучке несколько камней. Теперь два человека по очереди берут из нее камни, один человек может взять несколько камней из любой кучи камней, илиВыберите кучу камней больше 1 камня и разделите ее на две кучки.. Тот, кто не сможет взять камни в конце, проигрывает, а кто выиграет, учитывая количество камней в каждой кучке.
Если эта задача снимает ограничение, заключающееся в том, что куча камней может быть разделена, то это голая подзадача Ним. Но после добавления ограничения мы не можем напрямую использовать правило Нима для решения проблемы. Но когда мы проанализируем его, мы обнаружим, что хотя это и имеет ограничения, ноПо-прежнему соответствуют ограничениям игр ICG, поэтому мы можем использовать функцию SG для решения.
Для состояния N он может перейти в любое состояние 0-N-1 и может быть разделен на два состояния i и N-i. Согласно приведенной выше формуле: SG(A+B) = SG xor SG(B), поэтому для нашего SG(N) его можно перевести в состояние 0-N-1, ** и (i, Ni)* * состояние.
В соответствии с отношениями между состояниями мы можем легко написать код для решения функции SG:
sg_arr = [0 for _ in range(50)]
def mex(nums):
# 返回第一个不在nums当中的自然数
if len(nums) == 0:
return 0
for i in range(1, len(nums)+1):
if i not in nums:
return i
return len(nums) + 1
def sg(n):
sgs = []
# 记录下0-N-1状态
for i in range(n):
sgs.append(sg_arr[i])
# N也可以达到(i, N-i)状态，SG(i, N-i) = SG(i) ^ SG(N-i)
for i in range(1, n):
ret = sg_arr[i] ^ sg_arr[n-i]
if ret not in sgs:
sgs.append(ret)
# 通过mex函数求解出sg[n]
sg_arr[n] = mex(sorted(sgs))
print(sg_arr[n])
Поскольку нам нужно использовать предыдущее значение SG для вычисления более позднего значения SG, нам нужно сохранить предыдущий ответ в массиве. В противном случае, еслиРекурсивное выполнение заняло бы очень много времени.. На самом деле, вычисление значения SG каждого числа занимает очень много времени, особенно когда N очень велико. Итак, в это время вы можете применить хитрый подход, которыйВоспроизведите значение SG некоторых состояний, чтобы наблюдать и найти закон.
Метод игры в часы, чтобы найти закон, не очень умный, но он часто используется в игре.
После того, как мы распечатаем некоторые значения SG, мы можем найти, что для n, если n % 4 == 0, то SG(n) = n-1, n % 4 == 3, SG(n) = n+1, иначе СГ(п) = п.
Используя это правило, мы можем напрямую получить значение SG, и, объединив значение SG каждой кучи камней вместе, мы получим окончательный ответ.
Суммировать
На этом мы закончили знакомить с использованием значений функции SG в теории игр. Хотя мы использовали много чернил, чтобы объяснить принцип, для начинающих предполагается, что это все еще круг. Это очень нормально.Сама задача по теории игр является тестом мышления.Кроме того, процесс вывода функции SG не очень интуитивен.Несомненно, новички будут чувствовать себя утомительно и непонятно.
Существует хитрость, позволяющая уловить соответствующую взаимосвязь между значением SG и моделью подигры Нима:Начните с игры Ним, так будет проще. На самом деле значение SG изначально было получено из подигры ним.
После понимания функции SG,Достаточно для решения большинства алгоритмических задач теории игр.. Это также очень важная концепция и метод в области теории игр, и я надеюсь, что каждый сможет его понять.
Сегодняшняя статья здесь.Если вам нравится эта статья, если вы можете, пожалуйста,обращать внимание, подбодрите меня и облегчите доступ к другим статьям.
В этой статье используетсяmdniceнабор текста