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

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

Время игры Тривиальным решением является заполнение фишками n-вершинного графа за n шагов, используя n фишек. Хопкрофт, Пол и Вэлиент показали, что любая вершина графа с n вершинами может быть посещена с фишками, где константа зависит от максимальной полустепени захода. Это дало им возможность доказать, что содержится в для всех f. Липтон и Тарьян показали, что любой n-вершинный планарный ациклический ориентированный граф с максимальной полустепенью захода k может быть пройден с фишками. Они также доказали, что можно получать существенное сокращение числа фишек, сохраняя полиномиальную границу числа шагов размещения фишек, доказав теорему, что любой n-вершинный планарный ацикличный ориентированный граф с максимальной полустепенью захода k может быть пройден с фишками за время . Алон, Сеймур и Томас показали, что любой n-вершинный ацикличный ориентированный граф без kh-миноров и максимальной полустепенью захода k может быть пройден с фишками.

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

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

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

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

Примечания

Литература

Литература для дальнейшего чтения

Категория:Теория сложности вычислений Категория:Комбинаторная теория игр