Коэффициент неразличимости

В комбинаторной теории игр , и в частности , в теории беспристрастных игр в мизере игре, неразличимость фактор является коммутативной Моноид , обобщающими и локализует Спрэг-Гранди теоремы для набора правил конкретных игр.

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

Пример: вариант Misere Nim [ править ]

Предположим, что игра в Ним ведется как обычно с кучей объектов, но в начале игры каждая куча ограничена одним или двумя объектами. В соответствии с соглашением о нормальной игре игроки по очереди удаляют любое количество объектов из кучи, и последний игрок, взявший объект из кучи, объявляется победителем; в игре Misere этот игрок проигрывает.

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

N

У следующего игрока, который сделает ход, есть принудительная победа в лучшей игре; или же

п

Предыдущий ход игрок получает принудительную победу.

Мы можем записать коммутативное моноидное представление для мизерного частного этой одно- и двухъярусной игры Ним, сначала преобразовав ее обычное решение на основе Нимбера в мультипликативную форму, а затем немного изменив это для мизерной игры.

Анализ нормального режима [ править ]

В nimbers , которые происходят в нормальной игре таких позиций являются * 0, * 1, * 2 и * 3.

Нимбер	Исход	Позиции с этим ловким
${\ displaystyle \ ast 0}$	п	Четное количество куч размера 1 и четное количество куч размера 2
${\ displaystyle \ ast 1}$	N	Нечетное количество куч размера 1 и четное количество куч размера 2
${\ displaystyle \ ast 2}$	N	Четное количество куч размера 1 и нечетное количество куч размера 2
${\ displaystyle \ ast 3}$	N	Нечетное количество куч размера 1 и нечетное количество куч размера 2

Эти четыре значения нима объединяются в соответствии с четырехгруппой Кляйна :

${\ displaystyle {\ begin {array} {c | ccc} + & \ ast 0 & \ ast 1 & \ ast 2 & \ ast 3 \\\ hline \ ast 0 & \ ast 0 & \ ast 1 & \ ast 2 & \ ast 3 \\\ ast 1 & \ ast 1 & \ ast 0 & \ ast 3 & \ ast 2 \\\ ast 2 & \ ast 2 & \ ast 3 & \ ast 0 & \ ast 1 \\\ ast 3 & \ ast 3 & \ ast 2 & \ ast 1 & \ ast 0 \ конец {множество}}}$

Четырехгруппа Клейна также определяется представлением коммутативной группы

${\ Displaystyle \ mathrm {V} = \ langle a, b \ mid a ^ {2} = b ^ {2} = 1 \ rangle}$.

Элементы можно рассматривать как однозначно соответствующие значениям нимов, которые возникают в этой упрощенной игре с ним; они сочетаются точно так же.${\ Displaystyle \ mathrm {V} = \ {1, a, b, ab \}}$${\ displaystyle \ {\ ast 0, \ ast 1, \ ast 2, \ ast 3 \}}$

До сих пор это формальное введение четырехгруппы Кляйна не добавило ничего нового к традиционному анализу одно- и двухъярусных нимов с использованием нимберов и сложения нимбов. Вместо этого мы просто переделали теорию в мультипликативную форму.

Misere-play анализ [ править ]

Преимущество мультипликативной формы состоит в том, что она позволяет нам записать аналогичное решение для мизерного частного Нима, играемого только с кучей размера один и два.

Введем представление коммутативного моноида

${\ displaystyle \ mathrm {M} = \ langle a, b \ mid a ^ {2} = 1, \ b ^ {3} = b \ rangle.}$

чьи шесть элементов ${\displaystyle \{1,a,b,ab,b^{2},ab^{2}\}.}$

Неверное значение частного	Исход	Должности в этом классе
1	N	Четное количество куч размера 1 и без куч размера 2
а	п	Нечетное количество куч размера 1 и отсутствие куч размера 2
б	N	Четное количество куч размера 1 и нечетное количество куч размера 2
ab	N	Нечетное количество куч размера 1 и нечетное количество куч размера 2
${\displaystyle b^{2}}$	п	Четное количество куч размера 1 и четное количество (больше нуля) куч размера 2
${\displaystyle ab^{2}}$	N	Нечетное количество куч размера 1 и четное количество (больше нуля) куч размера 2

Решение правильной игры misere Nim было полностью описано Бутоном в 1902 году. ^[1] В последнем предложении этой статьи Бутон пишет, что в misere Nim «безопасные комбинации такие же, как и раньше, за исключением того, что нечетные комбинации. количество стопок, каждая из которых содержит по одной, теперь безопасно [т.е. является P-позицией], в то время как четное количество единиц небезопасно [т.е. является N-позицией] ». Легко увидеть, что приведенная выше формулировка неправильного отношения эквивалентна случаю, когда Ним играет с кучей только первого и второго размера.

Формальное определение [ править ]

Предположим, что это набор беспристрастных комбинаторных игр, который конечно порожден относительно дизъюнктивных сумм и замкнут в обоих следующих смыслах:${\displaystyle A}$

(1) Аддитивное замыкание : если и являются играми , то их дизъюнктивная сумма также равна .${\displaystyle G}$${\displaystyle H}$${\displaystyle A}$${\displaystyle G+H}$${\displaystyle A}$

(2) Наследственное закрытие : если это игра и есть возможность , то также входит .${\displaystyle G}$${\displaystyle A}$${\displaystyle H}$${\displaystyle G}$${\displaystyle H}$${\displaystyle A}$

Далее, определим на в неразличимости конгруэнции ≈ что касается двух игр и , если для любого выбора игры в , две позиции и имеют один и тот же результат (то есть, либо оба первых, игрок выигрывает в лучшей игре , или в качестве альтернативы оба второго -игрок побеждает).${\displaystyle A}$${\displaystyle G}$${\displaystyle H}$${\displaystyle X}$${\displaystyle A}$${\displaystyle G+X}$${\displaystyle H+X}$${\displaystyle A}$

Легко проверить, что ≈ действительно является конгруэнцией на множестве всех сумм дизъюнктивных позиций , и что это верно независимо от того, ведется ли игра в нормальном или неправильном режиме. Совокупность всех классов конгруэнтности образует фактор неразличимости .${\displaystyle A}$

Если в нее играют как в беспристрастную игру с нормальной игрой (выигрыш последней игры), то классы конгруэнтности находятся во взаимно однозначном соответствии со значениями нимов, которые встречаются в ходе игры (сами по себе определяемые Спрагом-Гранди теорема ).${\displaystyle A}$${\displaystyle A}$

Вместо этого в мизерной игре классы конгруэнтности образуют коммутативный моноид , который стал известен как мизер-фактор.

Алгоритмы вычисления мизерных частных [ править ]

Для различных беспристрастных игр, особенно для восьмеричных игр , было вычислено множество более сложных и замысловатых мизерных коэффициентов . Универсальный алгоритм для вычисления мизерного представления частного моноида данного конечного набора мизерных беспристрастных игровых позиций был разработан Аароном Н. Сигелем и описан ^[2] в Приложении C.

См. Также [ править ]

• Теорема Спрага – Гранди
• Теория родов

Ссылки [ править ]

Внешние ссылки [ править ]

• http://miseregames.org/