WikiDer > Kayles

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

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

Правила

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

История

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

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

Анализ

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

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

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

Рекурсивный расчет значений (начиная с ) дает результаты, обобщенные в следующей таблице. Чтобы найти значение на столе напишите в качестве и посмотрите на строку a, столбец b:

Kayles nim-values ​​через
01234567891011
0+012314321426
12+412714321467
24+412854721867
36+412314721827
48+412814721427
60+412814721867
72+412814721827

В этот момент последовательность ним-значений становится периодической.[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.