Фишечная игра

Фишечная игра — это вид математической игры^[англ.], в которой игра заключается в передвижении «фишек» или «маркеров» на ориентированном графе. Существует большое число различных фишечных игр.

Прохождение фишками

• Прохождение фишками — это игра, в которой фишки размещаются на вершинах направленного ациклического графа G согласно некоторым правилам.
  • Ход игры состоит либо в размещении фишки в вершине графа G, либо изъятию фишки из занимаемой фишкой вершины.
  • Вершина может быть занята фишкой, только если имеются все её предшественницы.
  • Целью игры является успешное посещение фишками всех вершин графа G (в любом порядке) с минимальным числом фишек, выставленных на графе одновременно.

Время игры

Тривиальным решением является заполнение фишками n-вершинного графа за n шагов, используя n фишек. Хопкрофт, Пол и Вэлиент^[1] показали, что любая вершина графа с n вершинами может быть посещена с ${\displaystyle O(n\log n)}$ фишками, где константа зависит от максимальной полустепени захода. Это дало им возможность доказать, что DTIME^[англ.]${\displaystyle (f(n))}$ содержится в DSPACE^[англ.]${\displaystyle (f(n)\log f(n))}$ для всех времяконструируемых функций^[англ.] f. Липтон и Тарьян^[2] показали, что любой n-вершинный планарный ациклический ориентированный граф с максимальной полустепенью захода k может быть пройден с ${\displaystyle O({\sqrt {n}}+k\log _{2}n)}$ фишками. Они также доказали, что можно получать существенное сокращение числа фишек, сохраняя полиномиальную границу числа шагов размещения фишек, доказав теорему, что любой n-вершинный планарный ацикличный ориентированный граф с максимальной полустепенью захода k может быть пройден с ${\displaystyle O(n^{\tfrac {2}{3}}+k)}$ фишками за время ${\displaystyle O(n^{\tfrac {5}{3}})}$. Алон, Сеймур и Томас^[3] показали, что любой n-вершинный ацикличный ориентированный граф без k_h-миноров и максимальной полустепенью захода k может быть пройден с ${\displaystyle O(h^{\tfrac {3}{2}}n^{\tfrac {1}{2}}+k\log n)}$ фишками.

Прохождение черными и белыми фишками

Обобщение этой игры, известное как «прохождение черными и белыми фишками», разрабатывали Стивен Артур Кук и Рави Сети в статье 1976 года^[4]. В игру добавляются белые фишки, которые могут быть размещены в любой вершине, какой захотим, но удалить такую фишку можно, только если все непосредственные дочерние вершины также заняты фишками. Цель остаётся той же — разместить чёрную фишку на целевой вершине, но заполнение фишками смежных вершин можно делать фишками любого цвета.

Другие варианты

Такуми Касаи, Акэо Адати и Сигэки Ивата разработали игру, в которой фишка может двигаться вдоль ребра в неоккупированную вершину, только если вторая фишка расположена на третьей контрольной вершине. Целью является продвинуть фишку до целевой вершины. Эти вариации делают фишечную игру обобщением игр, таких как китайские шашки и халма. Они определяют вычислительную сложность версий игры с одним и двумя игроками и их специальные версии. В версии с двумя игроками игроки двигают фишки поочерёдно. Могут существовать ограничения на то, какие фишки игрок может двигать^[5].

Игра с прохождением фишками может быть обобщена до игры Эренфойхта — Фраиса^[6].

См. также

Прохождение фишками графа^[англ.]: некоторое число фишек располагается в вершинах неориентированного графа. Целью является достижение целевой вершины, но чтобы передвинуть фишку на смежную вершину, другая фишка на той же вершине должна быть удалена.

Примечания

1. Hopcroft, Paul, Valiant, 1977.
2. Lipton, Tarjan, 1980.
3. Alon, Seymour, Thomas, 1990.
4. Cook, Sethi, 1976, с. 25–37.
5. Kasai, Adachi, Iwata, 1979, с. 574–586.
6. 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.