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

В комбинаторная теория игр, и особенно в теории беспристрастные игры в Misère играть, коэффициент неразличимости это коммутативный моноид который обобщает и локализует Теорема Спрага – Гранди для набора правил конкретной игры.

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

Пример: вариант Misere Nim

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

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

N: Следующий игрок, который сделает ход, имеет принудительную победу в лучшей игре; или

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

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

Анализ нормальной игры

В ловцы которые встречаются при обычной игре таких позиций: * 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 {egin {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 0end {array} }}

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

{displaystyle mathrm {V} = langle a, bmid a ^ {2} = b ^ {2} = 1angle}

.

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

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

Анализ мизер-игры

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

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

{displaystyle mathrm {M} = langle a, bmid a ^ {2} = 1, b ^ {3} = bangle.}

чьи шесть элементов ${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

Решение правильной игры мизере Ним было полностью описано Бутоном в 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/

[1] Бутон, К. Л. (1901), «Ним, игра с полной математической теорией», Анналы математики, 2, 3 (1/4): 35–39, Дои:10.2307/1967631, JSTOR 1967631

[2] Plambeck, Thane E .; Сигел, Аарон Н., Неверные коэффициенты для беспристрастных игр: дополнительный материал, arXiv:0705.2404, Bibcode:2007arXiv0705.2404P

[1]

[2]