Теория рода
 | В этой статье есть несколько проблем. Пожалуйста, помогите улучшить его или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалять эти шаблонные сообщения )
|
В математической теории игр теория рода в беспристрастных играх — это теория, с помощью которой некоторые игры, в которые играют в соответствии с соглашением о несчастной игре можно проанализировать , чтобы предсказать класс результатов игр.
Теория рода была впервые опубликована в книге «О числах и играх» , а затем в книге «Пути к победе в математических играх», том 2.
В отличие от теории Спрэга-Грунди для беспристрастных игр в обычной игре, теория рода не является полной теорией для беспристрастных игр в форме несчастной игры.
Род игры
[ редактировать ]Род игры определяется с помощью mex (минимального исключающего) вариантов игры.
g+ — это базовое значение или номер игры в соответствии с общепринятыми правилами игры.
g- или λ 0 — класс результата игры в соответствии с соглашением о несчастной игре.
Более конкретно, чтобы найти g+, *0 определяется как g+ = 0, а во всех других играх g+ равно mex его вариантов.
Чтобы найти g-, *0 имеет g- = 1, а во всех других играх g- равно mex g- его вариантов.
λ 1 , λ 2 ..., равно значению g− игры, добавленному к числу *2 игр nim, где число равно нижнему индексу.
Таким образом, род игры равен g ля 0 ля 1 ля 2 ... .
*0 имеет значение рода 0 120 . Обратите внимание, что верхний индекс продолжается бесконечно, но на практике верхний индекс записывается с конечным числом цифр, потому что можно доказать, что со временем последние две цифры чередуются бесконечно...
Исходы сумм игр
[ редактировать ]С его помощью можно предсказать результат:
- Сумма любых нимберов и любых ручных игр
- Сумма любой игры с учетом ее рода, любого количества ним-игр *1, *2 или *3 и, возможно, еще одной ним-игры с номером 4 или выше.
- Сумма беспокойной игры и любого количества ним-игр любого размера.
Кроме того, некоторые норовистые или беспокойные пары могут образовывать ручные игры, если они равнозначны. Две игры эквивалентны, если они имеют одинаковые варианты, причем одни и те же варианты определяются как варианты эквивалентных игр. Добавление варианта, из которого происходит обратимый ход, не влияет на эквивалентность.
Некоторые норовистые пары, добавленные в другую норовистую игру того же вида, остаются ручными.
Полуручная игра, добавленная сама к себе, эквивалентна *0.
Реверсивные ходы
[ редактировать ]Для дальнейшего понимания теории рода важно знать, как работают обратимые движения. Предположим, есть две игры A и B, где A и B имеют одинаковые варианты (доступные ходы), тогда они, конечно, эквивалентны.
Если у B есть дополнительная опция, скажем, в игре X, то A и B по-прежнему эквивалентны, если есть ход от X к A.
То есть B во всем аналогичен A, за исключением дополнительного хода (X), который можно отменить.
Виды игр
[ редактировать ]Различные игры (позиции) можно разделить на несколько типов:
- Nim
- Приручить
- беспокойный
- беспокойный
- Половина ручного
- Дикий
Nim
[ редактировать ]Это не означает, что позиция в точности подобна куче нимов в соответствии с соглашением о неправильной игре, но классификация игры как ним означает, что она эквивалентна куче нимов.
Игра является ним-игрой, если:
- у него род 0 1 , 1 0 , 2 2 , 3 3 ...
- он перемещается только в одну кучу нимов, т.е. перемещается в позицию *1 или *2, но не, например, *x+*y (но см. следующий пункт)
- у него также могут быть ходы в игры, которые не являются нимами, при условии, что они не требуются для определения рода, и в каждой из этих игр есть хотя бы один вариант игры с ним того же рода.
Приручить
[ редактировать ]Это позиции, которые мы можем представить как позиции нимов (обратите внимание на разницу между позициями нимов, которые могут состоять из множества куч нимов, сложенных вместе, и одной кучей нимов, которая может составлять только 1 кучу нимов). Игра G является ручной, если:
- у него род 0 1 , 1 0 , или 0 0 , 1 1 , 2 2 , 3 3 ...
- все варианты G ручные
- G также может иметь дикие варианты (позиции, которые не являются ручными или немыми), если они не влияют на род, и каждый вариант имеет обратимые ходы для ручных игр с родом g. ? и ? л .
Обратите внимание на ходы в g ? и ? л на самом деле может быть тот же самый вариант. ? означает любое число.
См. также
[ редактировать ]Ссылки
[ редактировать ]- О числах и играх Конвей Джон Хортон
- Пути победы в математических играх Элвина Берлекэмпа, Джона Конвея и Ричарда Гая .