Восьмеричная игра
Восьмеричные игры — это класс игр для двух игроков, в которых нужно удалять жетоны (игровые фишки или камни) из кучи жетонов.Они изучались в комбинаторной теории игр как обобщение игр Ним , Кейлса и подобных игр. [1] [2]
Восьмеричные игры беспристрастны , что означает, что каждый ход, доступный одному игроку, также доступен и другому игроку.Они отличаются друг от друга количеством жетонов, которые можно удалить за один ход, и (в зависимости от этого количества) можно ли удалить всю кучу, уменьшить размер кучи или разделить кучу на две кучки. . Эти варианты правил могут быть компактно описаны с помощью системы кодирования с использованием восьмеричных цифр.
Спецификация игры
[ редактировать ]Восьмеричная игра ведется с жетонами, разделенными на кучки. Два игрока ходят по очереди, пока ходы не станут невозможны. Каждый ход состоит из выбора только одной из кучек, и либо
- удаление всех токенов в куче, не оставляя кучи,
- удаление некоторых, но не всех жетонов, оставление одной кучи меньшего размера или
- удаление некоторых фишек и разделение оставшихся фишек на две непустые кучи.
Кучи, отличные от выбранной, остаются неизменными. побеждает игрок, сделавший ход последним В обычной игре . В игру также можно вести мизерную игру , в которой проигрывает игрок, сделавший ход последним.
Игры, в которые играют с кучами таким образом, в которых разрешенные ходы для каждой кучи определяются исходным размером кучи, называются играми «взятие и разрушение» . в литературе [1] Восьмеричные игры — это подмножество игр «взять и разбить», в которых разрешенные ходы определяются количеством жетонов, удаленных из кучи.
Восьмеричный код игры указывается как
- 0 . д 1 д 2 д 3 д 4 …,
где восьмеричная цифра d n указывает, разрешено ли игроку покидать ноль, одну или две кучи после удаления n жетонов из кучи. Цифра d n представляет собой сумму
- 1, если разрешено оставлять нулевые кучи, 0 в противном случае;
- 2, если разрешен выход из одной кучи, 0 в противном случае; и
- 4, если разрешено оставлять две кучи, 0 в противном случае.
Нулевые токены не считаются кучей. Таким образом, цифра d n является нечетной, если кучу из n жетонов можно удалить полностью, и даже в противном случае. Спецификация результатов с одной кучей в d n применяется к удалению n токенов из кучи, превышающей n . Результаты с двумя кучами в d n применяются к удалению n токенов из кучи размером не менее n +2 и разделению остатка на две непустые кучи.
Восьмеричные игры могут позволить разделить кучу на две части, не удаляя никаких жетонов, используя цифру 4 слева от десятичной точки. Это похоже на ход в игре Гранди , заключающийся в разделении кучи на две неравные части. Однако стандартная восьмеричная запись игры не способна выразить ограничение неравных частей.
Восьмеричные игры с конечным числом ненулевых цифр называются конечными восьмеричными играми .
Особые восьмеричные игры
[ редактировать ]Nim
[ редактировать ]Самая фундаментальная игра в комбинаторной теории игр — это Ним , в которой из кучи можно удалить любое количество жетонов, оставив после себя ноль или одну кучку. Восьмеричный код Нима — 0,333… , который в опубликованной литературе встречается как
- ,
для обозначения повторяющейся части, как в повторяющейся десятичной дроби . Однако важно понимать, что повторяющаяся часть не играет той же роли, что и в восьмеричных дробях, поскольку игры
и
не идентичны, несмотря на их равенство как восьмеричные дроби.
Кейлс
[ редактировать ]Игру Кейлса обычно визуализируют как игру с рядом из n кеглей, но ее можно смоделировать кучей из n фишек. Разрешается удалить одну или две фишки из кучи, а оставшиеся разложить в ноль, одну или две кучи. Восьмеричный код Кейлса — 0,77 .
Шахматы Доусона
[ редактировать ]«Шахматы Доусона» — игра, возникшая на основе шахматной головоломки, поставленной Томасом Рейнером Доусоном в «Диких розах Каиссы » 1938 года. [3] Загадка была поставлена в виде противоположных рядов пешек, разделенных одной шеренгой. Хотя головоломка не рассматривается как беспристрастная игра , предположение об обязательности захватов подразумевает, что перемещение игрока по любому файлу приводит только к удалению этого файла и его соседей (если таковые имеются) из дальнейшего рассмотрения, при этом перемещается противоположный игрок. . Моделируя это как кучу из n жетонов, игрок может удалить всю кучу из одного, двух или трех жетонов, может уменьшить любую кучу на два или три жетона или разделить кучу на две части после удаления трех жетонов. Таким образом, шахматы Доусона представлены восьмеричным кодом 0,137 .
Кейлс Доусона
[ редактировать ]В игре 0.07 , называемой «Кейлс Доусона» , ход состоит в том, чтобы удалить из кучи ровно две фишки и распределить остаток по нолю, одной или двум кучкам. Кейлс Доусона назван в честь своего (неочевидного) сходства с шахматами Доусона, поскольку куча Кейлса Доусона из n +1 жетонов действует точно так же, как куча Кейлса Доусона из n жетонов. Говорят, что Кейлс Доусона является двоюродным братом шахмат Доусона.
Обобщение на другие базы
[ редактировать ]Восьмеричные игры, такие как Nim , в которых каждый ход преобразует кучу в нулевую или одну кучу, называются четвертичными играми , потому что появляются только цифры 0, 1, 2 и 3. Восьмеричная система записи также может быть расширена за счет включения шестнадцатеричных игр . какие цифры позволяют разделить кучу на три части. На самом деле возможны сколь угодно большие базы. Анализ четверичных, восьмеричных и шестнадцатеричных игр показывает, что эти классы игр заметно отличаются друг от друга. [1] а поведение более крупных баз не подвергалось столь пристальному вниманию.
Ним-последовательность
[ редактировать ]Теорема Спрага -Грунди подразумевает, что куча размера n эквивалентна куче нимов заданного размера, обычно обозначаемого G (n). Тогда анализ восьмеричной игры заключается в нахождении последовательности ним-значений для куч возрастающего размера. Эту последовательность G(0), G(1), G(2)... обычно называют ним-последовательностью игры.
Все проанализированные до сих пор конечные восьмеричные игры показали, что ним-последовательность в конечном счете периодична, и вопрос о том, являются ли все конечные восьмеричные игры в конечном счете периодическими, остается открытым. называет это Ричард Гай важной проблемой в области комбинаторных игр . [4]
Записи вычислений
[ редактировать ]Полный анализ восьмеричной игры приводит к нахождению ее периода и предпериода ним-последовательности. показано В книге «Пути к победе в математических играх» , что для доказательства периодичности конечной восьмеричной игры необходимо лишь конечное число значений ним-последовательности, что открыло двери для компьютерных вычислений.
Восьмеричные игры, содержащие не более трех восьмеричных цифр, анализировались на протяжении многих лет. Всего 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]
Ссылки
[ редактировать ]- ^ Jump up to: Перейти обратно: а б с д и ж Берлекамп, Элвин Р .; Джон Х. Конвей; Ричард К. Гай (1982). Пути выигрыша в математических играх . Том. 1. Академическая пресса. ISBN 0-12-091101-9 . Переработано и переиздано как
Пути победы в математических играх (2-е изд.) . АК Петерс Лтд. 2004. ISBN 1-56881-130-6 . - ^ Конвей, Джон Хортон (1976). О числах и играх . Академическая пресса. ISBN 0-12-186350-6 . Переработано и переиздано как
— (2000). О числах и играх . АК Питерс Лтд. ISBN 1-56881-127-6 . - ^ Доусон, Томас Рейнер (1973). Пять классических сказок в шахматах . Дуврские публикации.
- ^ Ричард К. Гай, Нерешенные проблемы в комбинаторных играх, Игры без шансов, 1996
- ^ Jump up to: Перейти обратно: а б Ахим Фламменкамп, Восьмеричные игры