Восьмеричная игра - Octal game

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

Восьмеричные игры беспристрастный Это означает, что каждый ход, доступный одному игроку, доступен и другому игроку. Они отличаются друг от друга количеством жетонов, которые могут быть удалены за один ход, и (в зависимости от этого числа) разрешено ли удалить весь heap, уменьшите размер кучи или разделите кучу на две кучи. Эти варианты правил могут быть компактно описаны системой кодирования с использованием восьмеричный цифры.

Спецификация игры

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

  • удаление всех токенов в куче, не оставляя кучи,
  • удаление некоторых, но не всех токенов, оставив одну меньшую кучу, или
  • удаление части токенов и разделение оставшихся токенов на две непустые кучи.

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

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

Восьмеричный код для игры определяется как

0 . d1 d2 d3 d4 …,

где восьмеричная цифра dп указывает, разрешено ли игроку оставить ноль, одну или две кучи после удаления п токены из кучи. Цифра dп это сумма

  • 1, если разрешено оставлять нулевые кучи, в противном случае - 0;
  • 2, если оставление одной кучи разрешено, 0 в противном случае; и
  • 4, если разрешено оставить две кучи, в противном случае - 0.

Нулевые токены не считаются кучей. Таким образом, цифра dп странно, если куча п токены могут быть удалены целиком и даже иначе. Спецификация одной кучи приводит к dп применяется к удалению п токенов из кучи более п. Результат с двумя кучами dп применить к удалению п токенов из кучи не менее п+2, а остаток разделить на две непустые кучи.

В восьмеричных играх можно разделить кучу на две части без удаления каких-либо токенов, используя цифру 4 слева от десятичной точки. Это похоже на переезд в Игра Гранди, который должен разбить кучу на две неравные части. Однако стандартная восьмеричная система обозначений игры не способна выразить ограничение неравных частей.

Восьмеричные игры с конечным числом ненулевых цифр называются конечные восьмеричные игры.

Особые восьмеричные игры

Ним

Самая фундаментальная игра в комбинаторная теория игр является Ним, в котором любое количество токенов может быть удалено из кучи, оставляя после себя ноль или одну кучу. Восьмеричный код Нима: 0.333…, появляющиеся в опубликованной литературе как

,

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

и

не идентичны, несмотря на их равенство как восьмеричные дроби.

Kayles

Игра Kayles обычно визуализируется как игра с рядом п булавки, но может быть смоделирована кучей п счетчики. Можно удалить один или два токена из кучи, а оставшиеся - в ноль, один или две кучи. Восьмеричный код Кейлза: 0.77 .

Шахматы Доусона

Шахматы Доусона это игра, возникающая из шахматной головоломки, поставленной Томас Рейнер Доусон в Дикие розы Кайссы, 1938.[3] Задача заключалась в том, чтобы задействовать противоположные ряды пешек, разделенных одной линией. Хотя загадка не ставится беспристрастная игра, предположение, что захваты являются обязательными, подразумевает, что перемещение игрока в любом файле приводит только к удалению этого файла и его соседей (если таковые имеются) из дальнейшего рассмотрения, с перемещением противоположного игрока. Моделируя это как кучу п жетонов, игрок может удалить всю кучу из одного, двух или трех жетонов, может уменьшить любую кучу на два или три жетона или может разделить кучу на две части после удаления трех жетонов. Таким образом, шахматы Доусона представлены восьмеричным кодом 0.137.

Кейлс Доусона

В игре 0.07, называется Кейлс Доусона, ход состоит в том, чтобы удалить ровно два токена из кучи и распределить остаток в ноль, одну или две кучи. Кейлс Доусона назван из-за его (неочевидного) сходства с шахматами Доусона в той куче Кейлса Доусона. п+1 жетон действует точно так же, как шахматная куча Доусона. п жетоны. Кейлз Доусона считается двоюродный брат шахмат Доусона.

Обобщение на другие базы

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

Ним-последовательность

В Теорема Спрага – Гранди означает, что куча размера n эквивалентна ним куча заданного размера, обычно обозначаемого G (n). Затем анализ восьмеричной игры состоит в нахождении последовательности ним-значений для куч увеличивающегося размера. Эта последовательность G (0), G (1), G (2) ... обычно называется nim-последовательностью игры.

Все конечный Восьмеричные игры, проанализированные до сих пор, показали, что ним-последовательность в конечном итоге периодична, и все ли конечные восьмеричные игры в конечном итоге периодичны, остается открытым вопросом. Он указан Ричард Гай как важная проблема в области комбинаторные игры.[4]

Записи вычислений

Полный анализ восьмеричной игры приводит к нахождению ее периода и предпериода ее ним-последовательности. Это показано в Выигрышные способы для ваших математических игр что только конечное число значений nim-последовательности необходимо для доказательства периодичности конечной восьмеричной игры, что открыло двери для вычислений на компьютерах.

На протяжении многих лет анализировались восьмеричные игры, содержащие не более трех восьмеричных цифр. Всего 79 нетривиальных восьмеричных игр, 14 из которых уже решены:

  • .156 Джека Кеньона в 1967 году[1]
  • .356, .055, .644 и .165 Ричард Остин в 1976 г.[1]
  • .16, .56, .127 и .376 Анил Ганголли и Тейн Пламбек в 1989 г.[1]
  • .454, .104, .106, .054 и .354 от Ахима Фламменкампа между 2000 и 2002 гг.[5]

Осталось 63 таких игры, несмотря на подсчет миллионов ним-значений Ахимом Фламменкампом.[5]

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

  1. ^ а б c d е ж Берлекамп, Элвин Р.; Джон Х. Конвей; Ричард К. Гай (1982). Выигрышные способы для ваших математических игр. 1. Академическая пресса. ISBN  0-12-091101-9. Переработано и перепечатано как
    Выигрышные способы для ваших математических игр (2-е изд.). А. К. Петерс Лтд., 2004 г. ISBN  1-56881-130-6.
  2. ^ Конвей, Джон Хортон (1976). О числах и играх. Академическая пресса. ISBN  0-12-186350-6. Переработано и перепечатано как
    --- (2000). О числах и играх. A K Peters Ltd. ISBN  1-56881-127-6.CS1 maint: числовые имена: список авторов (связь)
  3. ^ Доусон, Томас Райнер (1973). Пять классических сказочных шахмат. Dover Publications.
  4. ^ Ричард К. Гай, Нерешенные задачи комбинаторных игр, Игры без шанса, 1996
  5. ^ а б Ахим Фламменкамп, Восьмеричные игры