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

• Прохождение фишками — это игра, в которой фишки размещаются на вершинах направленного ациклического графа 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].

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

• 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.