Игра на вычитание - Subtraction game

В комбинаторная теория игр, а игра на вычитание является абстрактная стратегическая игра состояние которого может быть представлено натуральное число или же вектор чисел (например, количество игровых жетонов в стопках жетонов или положение фигур на доске), и в которых разрешенные ходы уменьшают эти числа.^[1][2] Часто ходы в игре позволяют уменьшить любое число путем вычитания значения из указанного набор вычитания, и разные игры на вычитание различаются своими наборами вычитания.^[1] Эти игры также различаются в зависимости от того, побеждает ли последний ходящий игрок ( обычная игровая конвенция ) или проигрывает (Misère ).^[2] Другое соглашение о выигрыше, которое также использовалось, заключается в том, что игрок, который переходит на позицию со всеми числами, равными нулю, выигрывает, но любая другая позиция, в которой нет возможных ходов, является ничьей.^[1]

Примеры

Примеры известных игр на вычитание включают следующее:

• Ним - это игра, состояние которой состоит из нескольких стопок жетонов, таких как монеты или спички, и допустимый ход удаляет любое количество жетонов из одной стопки. У Нима есть хорошо известная оптимальная стратегия, в которой цель на каждом ходу - достичь набора стопок, ним-сумма равен нулю, и эта стратегия является центральной для Теорема Спрага – Гранди оптимальной игры в беспристрастные игры. Однако при игре только с одной стопкой жетонов оптимальная игра тривиальна (просто удалите все жетоны за один ход).^[3]
• Вычесть квадрат - это вариант нима, в котором за один ход можно удалить только квадратное количество жетонов. Получившаяся игра имеет нетривиальную стратегию даже для одной стопки жетонов; в Теорема Фюрстенберга – Шаркози означает, что его выигрышные позиции имеют нулевую плотность среди целых чисел.^[4]
• Ним Фибоначчи это еще один вариант нима, в котором разрешенные ходы зависят от предыдущих ходов той же стопки жетонов. На первом ходу в стопку запрещено брать всю стопку, а при последующих ходах вычитаемая сумма должна быть не более чем в два раза больше, чем предыдущая сумма, извлеченная из той же стопки.^[5]
• Игра Wythoff Играется путем размещения шахматного ферзя на большой шахматной доске и на каждом шаге его перемещения (обычным образом шахматного ферзя) к нижнему, левому или нижнему левому углу доски. Эту игру можно эквивалентно описать с двумя стопками жетонов, из которых каждый ход может удалять любое количество жетонов из одной или обеих стопок, удаляя одинаковое количество из каждой стопки, когда обе стопки уменьшаются. Имеет оптимальную стратегию, включающую Битти последовательности и Золотое сечение.^[6]

Теория

Игры на вычитание обычно беспристрастные игры, что означает, что набор ходов, доступных в данной позиции, не зависит от игрока, чей ход идет. Для такой игры состояния можно разделить на ${ displaystyle { mathcal {P}}}$-позиции (позиции, в которых предыдущий игрок, только что перешедший, выигрывает) и ${ Displaystyle { mathcal {N}}}$-позиции (позиции, в которых побеждает следующий игрок), а оптимальная игровая стратегия состоит в перемещении к ${ displaystyle { mathcal {P}}}$-позиционирование, когда это возможно. Например, при обычном игровом соглашении и одной стопке жетонов каждое число в наборе вычитания является ${ Displaystyle { mathcal {N}}}$-позиция, потому что игрок может выиграть с такого числа, перейдя к нулю.^[2]

Для обычных игр с вычитанием, в которых есть несколько чисел, в которых каждый ход уменьшает только одно из этих чисел, и в которых сокращения, которые возможны из данного числа, зависят только от этого числа, а не от остальной части состояния игры , то Теорема Спрага – Гранди может использоваться для вычисления «значения нима» каждого числа, числа, представляющего эквивалентную позицию в игре нима, так что значение общего состояния игры равно ним-сумма его ним-ценностей. Таким образом, оптимальная стратегия для всей игры может быть сведена к вычислению ним-значений для упрощенного набора игровых позиций, в которых есть только одно число.^[7] Ним-значения равны нулю для ${ displaystyle { mathcal {P}}}$-позициями и ненулевым для ${ Displaystyle { mathcal {N}}}$-позиции; согласно теореме Том Фергюсон, однозначные позиции с ним-значением один - это в точности числа, полученные путем добавления наименьшего значения в вычитании, установленном к ${ displaystyle { mathcal {P}}}$-позиция. Результат Фергюсона приводит к оптимальной стратегии в играх с множественным вычитанием с минимальным отличием от обычной стратегии игры.^[8]

Для игры на вычитание с единственной стопкой жетонов и фиксированным (но, возможно, бесконечным) набором вычитаний, если набор вычитания имеет сколь угодно большие промежутки между его членами, тогда набор ${ displaystyle { mathcal {P}}}$-позиций игры обязательно бесконечно.^[9] Для каждой игры на вычитание с конечным множеством вычитаний значения ним ограничены, и оба разбиения на ${ displaystyle { mathcal {P}}}$-позиции и ${ displaystyle { mathcal {N}}}$-позиции и последовательность ним-значений в конечном итоге являются периодическими. Период может быть значительно больше максимального значения ${ displaystyle x}$ в наборе вычитания, но не более ${ displaystyle 2 ^ {x}}$.^[10] Однако существуют бесконечные множества вычитания, которые производят ограниченные ним-значения, но апериодическую последовательность этих значений.^[11]

Сложность

Для игр на вычитание с фиксированным (но, возможно, бесконечным) набором вычитаний, таких как вычитание квадрата, разделение на P-позиции и N-позиции чисел до заданного значения ${ displaystyle n}$ может быть вычислен во времени ${ Displaystyle О (п журнал ^ {2} п)}$. Ним-значения всех чисел до ${ displaystyle n}$ может быть вычислен во времени ${ Displaystyle О ( мин (нс, нм лог ^ {2} п))}$ куда ${ displaystyle s}$ обозначает размер набора вычитания (до ${ displaystyle n}$) и ${ displaystyle m}$ обозначает наибольшее значение нима в этом вычислении.^[12]

Для обобщений игр на вычитание, в которых используются векторы натуральных чисел с набором вычитания, векторы которого могут иметь как положительные, так и отрицательные коэффициенты, это неразрешимая проблема чтобы определить, имеют ли две такие игры одинаковые P-позиции и N-позиции.^[13]

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

• Игра Гранди и восьмеричные игры, обобщения игр на вычитание, в которых ход может разделить стопку жетонов на две

Примечания

Рекомендации

• Альтхёфер, Инго; Bültermann, Jörg (1995), "Суперлинейные длины периодов в некоторых играх на вычитание", Теоретическая информатика, 148 (1): 111–119, Дои:10.1016 / 0304-3975 (95) 00019-S, МИСТЕР  1347670
• Берлекамп, Элвин Р.; Конвей, Джон Х.; Гай, Ричард К. (2001), Выигрышные способы для ваших математических игр, 1 (2-е изд.), А. К. Петерс
• Бутон, Чарльз Л. (1901–1902), «Ним, игра с законченной математической теорией», Анналы математики, Вторая серия, 3 (1/4): 35–39, Дои:10.2307/1967631, JSTOR  1967631
• Кокстер, Х. С. М. (1953), «Золотое сечение, филлотаксис и игра Витхоффа», Scripta Mathematica, 19: 135–143, МИСТЕР  0057548
• Эппштейн, Дэвид (2018), «Более быстрая оценка игр на вычитание», Ито, Хиро; Леонарди, Стефано; Пагли, Линда; Пренсипи, Джузеппе (ред.), Proc. 9-я Международная конференция по развлечениям с алгоритмами (FUN 2018), Международный журнал Лейбница по информатике (LIPIcs), 100, Дагштуль, Германия: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, стр. 20: 1–20: 12, Дои:10.4230 / lipics.fun.2018.20
• Фергюсон, Т.С. (1974), «О суммах игр с графом, в которых проигрывает последний игрок», Международный журнал теории игр, 3: 159–167, Дои:10.1007 / BF01763255, МИСТЕР  0384169
• Голомб, Соломон В. (1966), "Математическое исследование игр" на вынос"", Журнал комбинаторной теории, 1: 443–458, Дои:10.1016 / S0021-9800 (66) 80016-9, МИСТЕР  0209015
• Ларссон, Урбан; Фокс, Натан (2015), "Апериодическая игра на вычитание двумерного нимера" (PDF), Журнал целочисленных последовательностей, 18 (7), статья 15.7.4, arXiv:1503.05751, МИСТЕР  3370791
• Ларссон, Урбан; Рубинштейн-Сальзедо, Саймон (2016), «Гранди-значения нима Фибоначчи», Международный журнал теории игр, 45 (3): 617–625, arXiv:1410.0332, Дои:10.1007 / s00182-015-0473-y, МИСТЕР  3538534
• Ларссон, Урбан; Вэстлунд, Йохан (2013), «От кучи совпадений до пределов вычислимости», Электронный журнал комбинаторики, 20 (3): P41: 1 – P41: 12, arXiv:1202.0664, МИСТЕР  3118949
• Whinihan, Майкл Дж. (1963), "Фибоначчи ним" (PDF), Ежеквартальный отчет Фибоначчи, 1 (4): 9–13
• Wythoff, W.A. (1907), «Модификация игры ним», Nieuw Archief voor Wiskunde, 7 (2): 199–202