Нимбер - Nimber

Не путать с Число.

В математика, то ловцы, также называется Гранди числа, представлены в комбинаторная теория игр, где они определяются как значения куч в игре Ним. Нимберы - это порядковые номера наделены ловкое дополнение и ловкое умножение, которые отличаются от порядковое сложение и порядковое умножение.

Из-за Теорема Спрага – Гранди в котором говорится, что каждый беспристрастная игра эквивалентно куче Нима определенного размера, Нимберы возникают в гораздо большем классе беспристрастных игр. Они также могут встречаться в партизанские игры любить Властный.

Нимберы обладают тем свойством, что их левый и правый варианты идентичны, следуя определенной схеме, и что они являются их собственными отрицаниями, так что положительный порядковый номер может быть добавлен к другому положительному порядковому номеру, используя ловкое дополнение найти порядковый номер меньшего значения.[1] В минимальный исключающий операция применяется к комплектам венчиков.

Использует

Ним

Основная статья: Ним

Nim - это игра, в которой два игрока по очереди удаляют предметы из разных куч. Поскольку ходы зависят только от позиции, а не от того, какой из двух игроков в данный момент движется, и где выплаты симметричны, Ним является беспристрастной игрой. На каждом ходу игрок должен удалить хотя бы один объект и может удалить любое количество объектов при условии, что все они происходят из одной кучи. Цель игры - быть игроком, который уберет последний объект. Используя сложение nimber, каждую кучу можно суммировать, чтобы получить значение nim для кучи. Более того, поскольку все кучи вместе можно суммировать с помощью сложения нимов, можно рассчитать скорость игры в целом. Выигрышная стратегия этой игры состоит в том, чтобы довести кумулятивную скорость игры до 0 для хода противников.[2]

Втиснуть

Крэм - это игра, в которую часто играют на прямоугольной доске, в которой игроки по очереди кладут домино горизонтально или вертикально до тех пор, пока больше нельзя будет ставить домино. Первый игрок, который не может сделать ход, проигрывает. Поскольку возможные ходы для обоих игроков одинаковы, это беспристрастная игра, которая может иметь большую ценность. Если каждая строка и столбец считаются кучей, то значение игры - это сумма всех строк и столбцов с использованием сложения ловкости. Например, любая доска размером 2xn будет иметь число 0 для всех четных n и число 1 для всех нечетных n.

Игра Норткотта

Игра, в которой колышки для каждого игрока размещаются вдоль колонны с конечным числом пробелов. Каждый ход каждый игрок должен перемещать фишку вверх или вниз по столбцу, но не может проходить мимо фишки другого игрока. Несколько столбцов сложены вместе, чтобы добавить сложности. Игрок, который больше не может делать ходов, проигрывает. В отличие от многих других игр, связанных с нимбером, количество пробелов между двумя жетонами в каждой строке соответствует размеру кучек нимов. Если ваш противник увеличивает количество пробелов между двумя жетонами, просто уменьшите его на следующем ходу. Или же сыграйте в игру Ним и сделайте Ним-сумму количества пробелов между жетонами в каждой строке равной 0.[3]

Hackenbush

Основная статья: Hackenbush

Hackenbush - игра, изобретенная математиком Джон Хортон Конвей. В него можно играть на любой конфигурации цветных отрезки линии соединены друг с другом своими конечными точками и с линией «земли». игроки по очереди удаляют отрезки линии. Беспристрастная версия игры, таким образом, игра, которую можно анализировать с помощью нимберов, может быть найдена путем удаления различий с линий, позволяя любому игроку обрезать любую ветку. Любые сегменты, зависящие от недавно удаленного сегмента для подключения к линии заземления, также удаляются. Таким образом, каждое соединение с землей можно рассматривать как кучу нимбов со значением ловкости. Кроме того, все отдельные подключения к линии заземления также можно суммировать для измерения состояния игры.

Дополнение

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

α ⊕ β = mex ({α′ ⊕ β : α ' < α} ∪ {α ⊕ β′ : β′ < β}),

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

Для конечных ординалов ним-сумма легко оценить на компьютере, взяв побитовый Эксклюзивный или (XOR, обозначается ⊕) соответствующих номеров. Например, ним-сумму 7 и 14 можно найти, записав 7 как 111 и 14 как 1110; единица добавляет к 1; место двоек прибавляет к 2, которое мы заменяем на 0; место четверок добавляет к 2, которое мы заменяем на 0; разряды восьмерок прибавляются к 1. Таким образом, ним-сумма записывается в двоичном формате как 1001 или в десятичном виде как 9.

Это свойство сложения следует из того факта, что и mex, и XOR дают выигрышную стратегию для Nim, и такая стратегия может быть только одна; или это можно показать непосредственно по индукции: Пусть α и β - два конечных ординала, и предположим, что ним-сумма всех пар с приведенной одной из них уже определена. Единственное число, XOR которого с α является α ⊕ β является β, наоборот; таким образом α ⊕ β исключен. С другой стороны, для любого порядкового номера γ < α ⊕ β, XORing ξ ≔ α ⊕ β ⊕ γ со всеми α, β и γ должен привести к уменьшению одного из них (так как ведущий 1 в ξ должен присутствовать хотя бы в одном из трех); поскольку ξ ⊕ γ = α ⊕ β > γ, мы должны иметь α > ξ ⊕ α = β ⊕ γ или β > ξ ⊕ β = α ⊕ γ; таким образом γ включен как (β ⊕ γ) ⊕ β или как α ⊕ (α ⊕ γ), и, следовательно α ⊕ β - минимальный исключенный порядковый номер.

Умножение

Умножение Нимбера (Ним-умножение) определяется рекурсивно

α β = mex ({α′ β ⊕ α β′ ⊕ α ' β′ : α′ < α, β′ < β}).

За исключением того, что нимберы образуют правильный класс а не набор, класс нимберов определяет алгебраически замкнутое поле из характеристика 2. Нимбер-аддитивная идентичность - это порядковый номер 0, а Нимбер-аддитивная идентичность - это ординал 1. В соответствии с характеристикой, равной 2, аддитивная Нимбер-аддитивная инверсия порядкового номера α является α сам. Нимбер-мультипликативная инверсия ненулевого ординала α дан кем-то 1/α = mex (S), где S это наименьший набор ординалов (нимберов) такой, что

  1. 0 является элементом S;
  2. если 0 < α′ < α и β′ является элементом S, тогда [1 + (α ′ - α) β ′] / α ′ также является элементом S.

Для всех натуральных чисел п, набор венчиков меньше 22п сформировать Поле Галуа GF (22п) порядка22п.

В частности, отсюда следует, что множество конечных нимберов изоморфно прямой предел так как п → ∞ полей GF (22п). Это подполе не является алгебраически замкнутым, поскольку никакое другое поле GF (2k) (так с k ни в одном из этих полей не содержится степени 2) и, следовательно, не в их прямом пределе; например, многочлен Икс3 + Икс + 1, имеющий корень в GF (23), не имеет корня в множестве конечных венчиков.

Так же, как и в случае с добавлением скорости, есть способ вычисления произведения конечных порядковых чисел. Это определяется правилами, которые

  1. Резкое произведение 2-степени Ферма (числа вида 22п) с меньшим номером равняется их обычному товару;
  2. Угловой квадрат Fermat 2-power Икс равно 3Икс/2 как вычислено при обычном умножении натуральных чисел.

Наименьшее алгебраически замкнутое поле нимберов - это множество нимберов, меньших порядкового ωωω, где ω это наименьший бесконечный порядковый номер. Отсюда следует, что, будучи ловким, ωωω является трансцендентный над полем.[4]

Таблицы сложения и умножения

В следующих таблицах показано сложение и умножение первых 16 нимберов.
Это подмножество закрыто при обеих операциях, так как 16 имеет вид22п.(Если вы предпочитаете простые текстовые таблицы, они Вот.)

Сложение нимбера (последовательность A003987 в OEIS )
Это тоже Стол Кэли из Z24 - или таблица побитовый XOR операции.
Маленькие матрицы показывают однозначные двоичные числа.
Умножение Нимбера (последовательность A051775 в OEIS )
Ненулевые элементы образуют Стол Кэли из Z15.
Маленькие матрицы переставляются двоичными Матрицы Уолша.
Нимбер умножение силы двух (последовательность A223541 в OEIS )
Вычисление nim-произведений степеней двойки является решающим моментом в рекурсивном алгоритме умножения nimber.

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

Заметки

  1. ^ Достижения в компьютерных играх: 14-я международная конференция, ACG 2015, Лейден, Нидерланды, 1-3 июля 2015 г., Отредактированные отдельные статьи. Херик, Яап ван ден, Плат, Аске, Костерс, Вальтер. Чам. 2015-12-24. ISBN  978-3319279923. OCLC  933627646.CS1 maint: другие (ссылка на сайт)
  2. ^ Ананы., Левитин (2012). Введение в разработку и анализ алгоритмов (3-е изд.). Бостон: Пирсон. ISBN  9780132316811. OCLC  743298766.
  3. ^ «Теория беспристрастных игр» (PDF). 3 февраля 2009 г.
  4. ^ Конвей 1976, стр. 61.

использованная литература