Теория родов - Genus theory

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

Теория родов впервые была опубликована в книге О числах и играх, а позже в Выигрышные способы для ваших математических игр Том 2.

в отличие от Теория Спрэга – Гранди для нормальных беспристрастных игр теория родов не является законченной теорией для беспристрастных игр, которые играют плохо.

Род игры

Род игры определяется с помощью Мексика (минимальный исключающий) вариантов игры.

g + - грубое значение или проворный игры согласно правилам нормальной игры.

г- или λ₀ является классом исхода игры в соответствии с соглашением об игре с мизерными играми.

Более конкретно, чтобы найти g +, определяется, что * 0 имеет g + = 0, а во всех других играх g + равно mex его опций.

Чтобы найти g−, * 0 имеет g− = 1, а во всех других играх g− равняется mex g− его вариантов.

λ₁, λ₂..., равно значению g− игры, добавленному к количеству игр * 2 nim, где это число равно нижнему индексу.

Таким образом, род игры g^{λ₀λ₁λ₂...}.

* 0 имеет значение рода 0¹²⁰. Обратите внимание, что верхний индекс продолжается бесконечно, но на практике верхний индекс записывается с конечным числом цифр, потому что можно доказать, что в конечном итоге последние 2 цифры меняются бесконечно ...

Итоги игр

Его можно использовать для прогнозирования результатов:

Сумма любых нимберов и любых ручных игр
Сумма любой игры с учетом ее вида, любого количества игр нимов * 1, * 2 или * 3 и, возможно, одной другой игры нимов с числом нимера 4 или выше.
Сумма беспокойной игры и любого количества игр нимов любого размера

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

Некоторые беспокойные пары, добавленные к другой беспокойной игре того же вида, все еще остаются ручными.

Прирученная игра, добавленная сама к себе, эквивалентна * 0.

Обратимые ходы

Для дальнейшего понимания теории родов важно знать, как работают обратимые ходы. Предположим, есть две игры A и B, в которых A и B имеют одинаковые варианты (доступны ходы), тогда они, конечно, эквивалентны.

Если у B есть дополнительная возможность, скажем, для игры X, то A и B по-прежнему эквивалентны, если есть переход от X к A.

То есть B во всех отношениях то же самое, что и A, за исключением дополнительного хода (X), который можно отменить.

Типы игр

Различные игры (позиции) можно разделить на несколько типов:

Ним
Приручить
Беспокойный
Беспокойный
Наполовину прирученный
Дикий

Ним

Это не означает, что позиция в точности подобна куче нимов в соответствии с соглашением об игре «misère play», но классификация игры как ним означает, что она эквивалентна куче нимов.

Игра считается ним-игрой, если:

он имеет род 0¹, 1⁰, 2², 3³...
он перемещается только в отдельные кучи нимов, т.е. перемещается в позицию * 1 или * 2, но не, например, * x + * y (но см. следующий пункт)
в ней также могут быть ходы в игры, которые не являются нимами, при условии, что они не требуются для определения рода, и каждая из этих игр имеет как минимум один вариант игры с нимами того же рода

Приручить

Это позиции, которые мы можем притвориться позициями нимов (обратите внимание на разницу между позициями нимов, которые могут быть сложенными вместе множеством куч нимов, и одной кучей нимов, которая может быть только кучей нимов). Игра G считается ручной, если:

он имеет род 0¹, 1⁰, или 0⁰, 1¹, 2², 3³...
все варианты G ручные
G также может иметь дикие варианты (позиции, которые не являются ручными или нимскими), если они не влияют на род, и каждый вариант имеет обратимые ходы для приручения игр с родом g.^? и ?^λ.

Обратите внимание на движение к g^? и ?^λ на самом деле может быть такой же вариант. ? означает любое число.

Смотрите также

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