Kayles - это простая беспристрастная игра в комбинаторной теории игр , изобретенная Генри Дудени в 1908 году. Имея ряд воображаемых кеглей для боулинга, игроки по очереди выбивают либо одну, либо две соседние кегли, пока все кегли не исчезнут. Используя обозначение восьмеричных игр , Кейлз обозначается 0,77 .
Правила
Кейлс играет с рядом жетонов, которые представляют собой кегли для боулинга. Ряд может быть любой длины. Два игрока чередуются; каждый игрок в свой ход может удалить либо одну кеглю (шар, брошенный прямо в эту кеглю), либо две соседние кегли (шар, брошенный для удара по обоим). Согласно правилам обычной игры , игрок проигрывает, если у него нет разрешенного хода (то есть, когда все кегли упали). В игру также можно играть по правилам Мизера ; в этом случае побеждает игрок, который не может двигаться .
История
Кейлз был изобретен Генри Дудени . [1] [2] Ричард Гай и Седрик Смит были первыми, кто полностью проанализировал версию с нормальной игрой, используя теорию Спрэга-Гранди . [3] [4] Версия misère была проанализирована Уильямом Сибертом в 1973 году, но он не публиковал свою работу до 1989 года. [5]
Название «Кейлс» - это англицизация французского слова quilles , что означает «боулинг».
Анализ
Большинство игроков быстро обнаруживают, что первый игрок имеет гарантированный выигрыш в обычном Кейлсе, если длина строки больше нуля. Этого выигрыша можно добиться, используя стратегию симметрии . На своем первом ходу первый игрок должен двигаться так, чтобы ряд был разбит на две части равной длины. Это ограничивает все будущие переходы в одну или другую секцию. Теперь первый игрок просто имитирует ходы второго игрока в противоположном ряду.
Более интересно спросить, каково значение нима строки длины. Это часто обозначается; это проворство , а не число . По теореме Спрэг-Гранди ,это MEX по всем возможным ходам NIM-сумма из NIM-значений двух полученных секций. Например,
потому что из ряда длиной 5 можно перейти к позициям
Рекурсивный расчет значений (начиная с ) дает результаты, обобщенные в следующей таблице. Чтобы найти значение на столе напишите в виде , и посмотрите на строку a, столбец b:
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |
---|---|---|---|---|---|---|---|---|---|---|---|---|
0+ | 0 | 1 | 2 | 3 | 1 | 4 | 3 | 2 | 1 | 4 | 2 | 6 |
12+ | 4 | 1 | 2 | 7 | 1 | 4 | 3 | 2 | 1 | 4 | 6 | 7 |
24+ | 4 | 1 | 2 | 8 | 5 | 4 | 7 | 2 | 1 | 8 | 6 | 7 |
36+ | 4 | 1 | 2 | 3 | 1 | 4 | 7 | 2 | 1 | 8 | 2 | 7 |
48+ | 4 | 1 | 2 | 8 | 1 | 4 | 7 | 2 | 1 | 4 | 2 | 7 |
60+ | 4 | 1 | 2 | 8 | 1 | 4 | 7 | 2 | 1 | 8 | 6 | 7 |
72+ | 4 | 1 | 2 | 8 | 1 | 4 | 7 | 2 | 1 | 8 | 2 | 7 |
В этот момент последовательность значений нимов становится периодической [5] с периодом 12, поэтому все последующие строки таблицы идентичны последней строке.
Приложения
Поскольку определенные позиции в Dots и коробки сводятся к позиции Kayles, [6] , полезно понять Kayles для того , чтобы проанализировать общие Dots и коробки позиции.
Вычислительная сложность
При нормальной игре Кейлза можно решить за полиномиальное время, используя теорию Спрэга-Гранди. [3]
Узел Кейлса - это обобщение Кейлса на графы, в которых каждая чаша «сбивает» (удаляет) желаемую вершину и все соседние с ней вершины. (В качестве альтернативы, эту игру можно рассматривать как два игрока, которые вместе находят независимое множество .) Шефер (1978) [7] доказал, что решение исхода этой игры является PSPACE-полным . Тот же результат справедлив и для партизанской версии узла Кейлса, в котором для каждого узла только одному из игроков разрешено выбрать этот конкретный узел в качестве цели для нокаута.
Смотрите также
Рекомендации
- ^ Dudeney, HE (2002), Кентерберийские головоломки , Dover, стр. 118-119, головоломка 73, ISBN 0-486-42558-4. Первоначально опубликовано в 1908 году.
- ^ Конвей, Джон Х. О числах и играх. Академическая пресса, 1976.
- ^ a b Р. К. Гай и К. А. Смит, G- значения различных игр, Proc. Cambridge Philos. Soc., 52 (1956) 514–526.
- ^ TE Plambeck, Daisies, Kayles и разложение Сиберта-Конвея в мизерных восьмеричных играх. Архивировано 14 июля 2010 г. в Wayback Machine , Теорет. Comput. Sci (математические игры) (1992) 96 361–388.
- ^ а б Plambeck, тан, Kayles , архивируются с оригинала на 2008-10-12 , извлекаться 2008-08-15
- ^ Э. Берлекамп , Дж. Х. Конвей , Р. Гай. Выигрышные способы для ваших математических пьес . Академическая пресса, 1982.
- ^ Шефер, Томас Дж. (1978). «О сложности некоторых игр с идеальной информацией для двух человек». Журнал компьютерных и системных наук . 16 (2): 185–225. DOI : 10.1016 / 0022-0000 (78) 90045-4 .