Игра на вычитание

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

Примеры

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

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

Теория

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

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

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

Сложность

Для игр на вычитание с фиксированным (но, возможно, бесконечным) набором вычитания, таких как вычитание квадрата, разбиение на P-позиции и N-позиции чисел до заданного значения. $n$ можно вычислить во времени $O(n\log ^{2}n)$ . Ним-значения всех чисел до $n$ можно вычислить во времени $O(\min(ns,nm\log ^{2}n))$ где $s$ обозначает размер множества вычитания (до $n$ ) и $m$ обозначает наибольшее значение нима, встречающееся в этом вычислении. ^[12]

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

См. также

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

Примечания

^ Перейти обратно: ^а ^б ^с Голомб (1966) .
^ Перейти обратно: ^а ^б ^с Берлекамп, Конвей и Гай (2001) , «Игры на вычитание», стр. 83–86.
^ Бутон (1901–1902) ; Голомб (1966) ; Берлекамп, Конвей и Гай (2001) , «Зеленый хакенбуш, игра в ним и нимберы», стр. 40–42.
^ Голомб (1966) ; Эппштейн (2018)
^ Уинихан (1963) ; Ларссон и Рубинштейн-Сальцедо (2016)
^ Витхофф (1907) ; Коксетер (1953)
^ Голомб (1966) ; Берлекамп, Конвей и Гай (2001) , «Игры с кучками», с. 82.
^ Фергюсон (1974) , с. 164; Берлекамп, Конвей и Гай (2001) , «Свойство спаривания Фергюсона», с. 86.
^ Голомб (1966) , Теорема 4.1, с. 451.
^ Голомб (1966) , Пример (а), с. 454; Альтёфер и Бюльтерманн (1995)
^ Ларссон и Фокс (2015) .
^ Эппштейн (2018) .
^ Ларссон и Вестлунд (2013) .

Ссылки

Альтёфер, Инго ; Бюльтерманн, Йорг (1995), «Суперлинейные длины периодов в некоторых играх с вычитанием», Theoretical Computer Science , 148 (1): 111–119, doi : 10.1016/0304-3975(95)00019-S , MR 1347670
Берлекамп, Элвин Р .; Конвей, Джон Х .; Гай, Ричард К. (2001), Пути победы в математических играх , том. 1 (2-е изд.), А. К. Петерс
Бутон, Чарльз Л. (1901–1902), «Ним, игра с полной математической теорией», Annals of Mathematics , Second Series, 3 (1/4): 35–39, doi : 10.2307/1967631 , JSTOR 1967631
Коксетер, HSM (1953), «Золотое сечение, филлотаксис и игра Витхоффа», Scripta Mathematica , 19 : 135–143, MR 0057548
Эппштейн, Дэвид (2018), «Быстрая оценка игр на вычитание», Ито, Хиро; Леонарди, Стефано; Пагли, Линда ; Пренсипи, Джузеппе (ред.), Proc. 9-я Международная конференция по развлечениям с алгоритмами (FUN 2018) , Международные труды Лейбница по информатике (LIPIcs), том. 100, Дагштуль, Германия: Замок Дагштуль – Центр компьютерных наук Лейбница, стр. 20:1–20:12, doi : 10.4230/lipics.fun.2018.20
Фергюсон, Т.С. (1974), «О суммах игр на графе с проигрышем последнего игрока», Международный журнал теории игр , 3 (3): 159–167, doi : 10.1007/BF01763255 , MR 0384169
Голомб, Соломон В. (1966), «Математическое исследование игр на вынос» , Журнал комбинаторной теории , 1 (4): 443–458, doi : 10.1016/S0021-9800(66)80016-9 , МР 0209015
Ларссон, Урбан; Фокс, Натан (2015), «Апериодическая игра на вычитание для ним-размерности два» (PDF) , Журнал целочисленных последовательностей , 18 (7), статья 15.7.4, arXiv : 1503.05751 , MR 3370791
Ларссон, Урбан; Рубинштейн-Сальзедо, Саймон (2016), «Значения Гранди Фибоначчи ним», Международный журнал теории игр , 45 (3): 617–625, arXiv : 1410.0332 , doi : 10.1007/s00182-015-0473-y , MR 3538534
Ларссон, Урбан; Вестлунд, Йохан (2013), «От кучи совпадений к пределам вычислимости» , Electronic Journal of Combinatorics , 20 (3): P41:1–P41:12, arXiv : 1202.0664 , doi : 10.37236/2244 , MR 3118949
Уинихан, Майкл Дж. (1963), «Фибоначчи ним» (PDF) , Fibonacci Quarterly , 1 (4): 9–13
Витхофф, Вашингтон (1907), «Модификация игры в ним» , Новый архив математики , 7 (2): 199–202.

[FOOTNOTEGolomb1966-1] Перейти обратно: ^а ^б ^с Голомб (1966) .

[wwsub-2] Перейти обратно: ^а ^б ^с Берлекамп, Конвей и Гай (2001) , «Игры на вычитание», стр. 83–86.

[3] Бутон (1901–1902) ; Голомб (1966) ; Берлекамп, Конвей и Гай (2001) , «Зеленый хакенбуш, игра в ним и нимберы», стр. 40–42.

[4] Голомб (1966) ; Эппштейн (2018)

[5] Уинихан (1963) ; Ларссон и Рубинштейн-Сальцедо (2016)

[6] Витхофф (1907) ; Коксетер (1953)

[7] Голомб (1966) ; Берлекамп, Конвей и Гай (2001) , «Игры с кучками», с. 82.

[8] Фергюсон (1974) , с. 164; Берлекамп, Конвей и Гай (2001) , «Свойство спаривания Фергюсона», с. 86.

[9] Голомб (1966) , Теорема 4.1, с. 451.

[10] Голомб (1966) , Пример (а), с. 454; Альтёфер и Бюльтерманн (1995)

[FOOTNOTELarssonFox2015-11] Ларссон и Фокс (2015) .

[FOOTNOTEEppstein2018-12] Эппштейн (2018) .

[FOOTNOTELarssonWästlund2013-13] Ларссон и Вестлунд (2013) .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]