Kayles - Kayles

Эта статья о комбинаторной игре. Для игры на газоне см. Боулинг и Кегли (спорт).

Ряд кеглей для боулинга. В свой ход игрок может удалить одну или две соседние булавки.

Kayles это простой беспристрастная игра в комбинаторная теория игр, изобретенный Генри Дудени в 1908 году. Получив ряд воображаемых кеглей, игроки по очереди выбивают одну или две соседние кегли, пока все кегли не исчезнут. Используя обозначения восьмеричные игры, Kayles обозначается 0.77.

Правила

Кейлс играет с рядом жетонов, которые представляют собой кегли для боулинга. Ряд может быть любой длины. Два игрока чередуются; каждый игрок в свой ход может удалить любую одну кеглю (шар, брошенный прямо на эту кеглю), или две соседние кегли (шар, брошенный в обе стороны). Под обычная игровая конвенция, игрок проигрывает, если у него нет разрешенного хода (то есть, когда все кегли упали). В игру также можно играть, используя Misère правила; в этом случае игрок, который не может двигаться выигрывает.

История

Кейлс был изобретен Генри Дудени.^[1][2] Ричард Гай и Седрик Смит были первыми, кто полностью проанализировал версию для нормальной игры, используя Теория Спрага-Гранди.^[3][4] В Misère версия была проанализирована Уильям Сиберт в 1973 году, но он не публиковал свои работы до 1989 года.^[5]

Имя «Кейлс» - это англицизация французского языка. квилли, что означает «боулинг».

Анализ

Большинство игроков быстро обнаруживают, что первый игрок имеет гарантированный выигрыш в обычном Кейлсе, если длина строки больше нуля. Эта победа может быть достигнута с помощью стратегия симметрии. На своем первом ходу первый игрок должен двигаться так, чтобы ряд был разбит на две части равной длины. Это ограничивает все будущие переходы в одну или другую секцию. Теперь первый игрок просто имитирует ходы второго игрока в противоположном ряду.

Интереснее спросить, что за ним-стоимость имеет длину в ряд ${\displaystyle n}$. Это часто обозначается ${\displaystyle K_{n}}$; это проворный, а не номер. Посредством Теорема Спрага – Гранди, ${\displaystyle K_{n}}$ это Мекс по всем возможным ходам ним-сумма из ним-ценности двух результирующих разделов. Например,

${\displaystyle K_{5}={\mbox{mex}}\{K_{0}+K_{4},K_{1}+K_{3},K_{2}+K_{2},K_{0}+K_{3},K_{1}+K_{2}\},\,}$

потому что из ряда длиной 5 можно перейти к позициям

${\displaystyle K_{0}+K_{4},\quad K_{1}+K_{3},\quad K_{2}+K_{2},\quad K_{0}+K_{3},{\text{ and }}K_{1}+K_{2}.\,}$

Рекурсивный расчет значений (начиная с ${\displaystyle K_{0}=0}$) дает результаты, обобщенные в следующей таблице. Чтобы найти значение ${\displaystyle K_{n}}$ на столе напишите ${\displaystyle n}$ в качестве ${\displaystyle 12a+b}$и посмотрите на строку a, столбец b:

Kayles nim-values ​​через ${\displaystyle K_{83}}$

${\displaystyle K_{n}}$	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, поэтому все последующие строки таблицы идентичны последней строке.

Приложения

Потому что определенные позиции в Точки и квадраты уменьшить до позиций Кейлса,^[6] полезно понимать Кейлза, чтобы анализировать общую позицию точек и прямоугольников.

Вычислительная сложность

При нормальной игре Кейлз может быть решен за полиномиальное время используя теорию Спрага-Гранди.^[3]

Узел Кейлс является обобщением Кейлса на графы, в которых каждая чаша «сбивает» (удаляет) желаемую вершину и все соседние с ней вершины. (В качестве альтернативы, эту игру можно рассматривать как двух игроков, которые находят независимый набор вместе.) Шефер (1978)^[7] доказал, что решение исхода этой игры PSPACE-полный. Тот же результат справедлив для партизанской версии узла Кейлса, в котором для каждого узла только одному из игроков разрешено выбрать этот конкретный узел в качестве цели для нокаута.

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

• Комбинаторная теория игр
• Восьмеричные игры
• Кейлс Доусона
• Нимбер

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

1. Дудени, Х. Э. (2002), Игры пазлы Кентербери, Dover, стр. 118–119, головоломка 73, ISBN  0-486-42558-4. Впервые опубликовано в 1908 году.
2. Конвей, Джон Х. О числах и играх. Академическая пресса, 1976.
3. Р. К. Гай и К. А. Б. Смит, The грамм-значения различных игр, Учеб. Cambridge Philos. Soc., 52 (1956) 514–526.
4. T.E. Пламбек, Маргаритки, Кейлз и разложение Сиберта-Конвея в мизерных восьмеричных играх В архиве 2010-07-14 на Wayback Machine, Теорет. Comput. Sci (математические игры) (1992) 96 361–388.
5. Пламбек, Тан, Kayles, заархивировано из оригинал на 2008-10-12, получено 2008-08-15
6. Э. Берлекамп, Дж. Х. Конвей, Р. Гай. Выигрышные способы для ваших математических игр. Академическая пресса, 1982.
7. Шефер, Томас Дж. (1978). «О сложности некоторых игр с идеальной информацией для двух человек». Журнал компьютерных и системных наук. 16 (2): 185–225. Дои:10.1016/0022-0000(78)90045-4.