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

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

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

Example: Misere Nim variant

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

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

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

П: Предыдущий игрок, сделавший ход, имеет вынужденную победу.

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

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

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

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

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

{\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\end{array}}

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

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

.

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

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

Анализ плохой игры

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

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

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

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

Плохое значение коэффициента	Исход	Позиции в этом классе
$1$	Н	Четное количество куч размера 1 и отсутствие куч размера 2.
$а$	П	Нечетное количество куч размера 1 и отсутствие куч размера 2.
$б$	Н	Четное количество куч размера 1 и нечетное количество куч размера 2.
$аб$	Н	Нечетное количество стопок размера 1 и нечетное количество стопок размера 2.
$b^{2}$	П	Четное количество куч размера 1 и четное количество (больше нуля) куч размера 2.
$ab^{2}$	Н	Нечетное количество куч размера 1 и четное количество (больше нуля) куч размера 2.

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

Формальное определение

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

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

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

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

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

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

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

Алгоритмы расчета коэффициентов нищеты

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

См. также

Ссылки

^ Бутон, CL (1901), «Ним, игра с полной математической теорией», Annals of Mathematics , 2, 3 (1/4): 35–39, doi : 10.2307/1967631 , JSTOR 1967631
^ Пламбек, Тейн Э.; Сигел, Аарон Н., Факторы Мизере для беспристрастных игр: Дополнительные материалы , arXiv : 0705.2404 , Бибкод : 2007arXiv0705.2404P

Пламбек, Тейн Э. (19 июля 2005 г.). «Укрощение дикой природы в беспристрастных комбинаторных играх» (PDF) . ЦЕЛЫЕ ЧИСЛА: Электронный журнал комбинаторной теории чисел (PDF) . 5 (G05) . Проверено 21 декабря 2010 г.

Сигел, Аарон Н. Комбинаторная теория игр . Том. 146. Американское математическое общество, 2013. ISBN. 9780821851906 .

Внешние ссылки

http://miseregames.org/

[1] Бутон, CL (1901), «Ним, игра с полной математической теорией», Annals of Mathematics , 2, 3 (1/4): 35–39, doi : 10.2307/1967631 , JSTOR 1967631

[2] Пламбек, Тейн Э.; Сигел, Аарон Н., Факторы Мизере для беспристрастных игр: Дополнительные материалы , arXiv : 0705.2404 , Бибкод : 2007arXiv0705.2404P

[ 1 ]

[ 2 ]