Фишечная игра (Snoycugx nijg)
Фишечная игра — это вид математической игры[англ.], в которой игра заключается в передвижении «фишек» или «маркеров» на ориентированном графе. Существует большое число различных фишечных игр.
Прохождение фишками
[править | править код]- Прохождение фишками — это игра, в которой фишки размещаются на вершинах направленного ациклического графа G согласно некоторым правилам.
- Ход игры состоит либо в размещении фишки в вершине графа G, либо изъятию фишки из занимаемой фишкой вершины.
- Вершина может быть занята фишкой, только если имеются все её предшественницы.
- Целью игры является успешное посещение фишками всех вершин графа G (в любом порядке) с минимальным числом фишек, выставленных на графе одновременно.
Время игры
[править | править код]Тривиальным решением является заполнение фишками n-вершинного графа за n шагов, используя n фишек. Хопкрофт, Пол и Вэлиент[1] показали, что любая вершина графа с n вершинами может быть посещена с фишками, где константа зависит от максимальной полустепени захода. Это дало им возможность доказать, что DTIME[англ.] содержится в DSPACE[англ.] для всех времяконструируемых функций[англ.] f. Липтон и Тарьян[2] показали, что любой n-вершинный планарный ациклический ориентированный граф с максимальной полустепенью захода k может быть пройден с фишками. Они также доказали, что можно получать существенное сокращение числа фишек, сохраняя полиномиальную границу числа шагов размещения фишек, доказав теорему, что любой n-вершинный планарный ацикличный ориентированный граф с максимальной полустепенью захода k может быть пройден с фишками за время . Алон, Сеймур и Томас[3] показали, что любой n-вершинный ацикличный ориентированный граф без kh-миноров и максимальной полустепенью захода k может быть пройден с фишками.
Прохождение черными и белыми фишками
[править | править код]Обобщение этой игры, известное как «прохождение черными и белыми фишками», разрабатывали Стивен Артур Кук и Рави Сети в статье 1976 года[4]. В игру добавляются белые фишки, которые могут быть размещены в любой вершине, какой захотим, но удалить такую фишку можно, только если все непосредственные дочерние вершины также заняты фишками. Цель остаётся той же — разместить чёрную фишку на целевой вершине, но заполнение фишками смежных вершин можно делать фишками любого цвета.
Другие варианты
[править | править код]Такуми Касаи, Акэо Адати и Сигэки Ивата разработали игру, в которой фишка может двигаться вдоль ребра в неоккупированную вершину, только если вторая фишка расположена на третьей контрольной вершине. Целью является продвинуть фишку до целевой вершины. Эти вариации делают фишечную игру обобщением игр, таких как китайские шашки и халма. Они определяют вычислительную сложность версий игры с одним и двумя игроками и их специальные версии. В версии с двумя игроками игроки двигают фишки поочерёдно. Могут существовать ограничения на то, какие фишки игрок может двигать[5].
Игра с прохождением фишками может быть обобщена до игры Эренфойхта — Фраиса[6].
См. также
[править | править код]Прохождение фишками графа[англ.]: некоторое число фишек располагается в вершинах неориентированного графа. Целью является достижение целевой вершины, но чтобы передвинуть фишку на смежную вершину, другая фишка на той же вершине должна быть удалена.
Примечания
[править | править код]- ↑ Hopcroft, Paul, Valiant, 1977.
- ↑ Lipton, Tarjan, 1980.
- ↑ Alon, Seymour, Thomas, 1990.
- ↑ Cook, Sethi, 1976, с. 25–37.
- ↑ Kasai, Adachi, Iwata, 1979, с. 574–586.
- ↑ Straubing, 1994, с. 39–44.
Литература
[править | править код]- Hopcroft J., Paul W., Valiant L. On Time versus space // J. Assoc. Comput. Mach.. — 1977.
- Richard J. Lipton, Robert E. Tarjan. Applications of a Planar Separator Theorem // SIAM J. Comput.. — 1980.
- Noga Alon, Paul Seymour, Robin Thomas. A Separator Theorem for Graphs with an Excluded Minor and its Applications // ACM. — 1990.
- Stephen Cook, Ravi Sethi. Storage requirements for deterministic polynomial time recognizable languages // Journal of Computer and System Sciences. — 1976. — Т. 13, вып. 1. — С. 25–37. — doi:10.1016/S0022-0000(76)80048-7.
- Takumi Kasai, Akeo Adachi, Shigeki Iwata. Classes of pebble games and complete problems // SIAM Journal on Computing. — 1979. — Т. 8, вып. 4. — doi:10.1137/0208046.
- Howard Straubing. Finite automata, formal logic, and circuit complexity. — Basel: Birkhäuser, 1994. — (Progress in Theoretical Computer Science). — ISBN 3-7643-3719-2.
- Nicholas Pippenger. Pebbling. Technical Report RC 8258, IBM Watson Research Center // Proceedings of the 5th IBM Symposium on Mathematical Foundations of Computer Science, Japan. — 1980.
- Jakob Nordström. Pebble Games, Proof Complexity, and Time-Space Trade-offs // Logical Methods in Computer Science. — 2013. — Сентябрь (т. 9, вып. 3).
Литература для дальнейшего чтения
[править | править код]- Erich Grädel, Phokion G. Kolaitis, Leonid Libkin, Marx Maarten, Joel Spencer, Moshe Y. Vardi, Yde Venema, Scott Weinstein. Finite model theory and its applications. — Berlin: Springer-Verlag, 2007. — (Texts in Theoretical Computer Science. An EATCS Series). — ISBN 978-3-540-00428-8.
Для улучшения этой статьи желательно:
|