WikiDer > 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 {и}} К_ {1} + К_ {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, поэтому все последующие строки таблицы идентичны последней строке.

Приложения

Эта секция нуждается в расширении. Вы можете помочь добавляя к этому. (Июль 2016)

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

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

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

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

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

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

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