#time-complexity #graph-algorithm #game-theory
#сложность по времени #граф-алгоритм #теория игр
Вопрос:
Игра:
- существует неориентированный простой граф с некоторыми специальными, выигрышными узлами и 2 игроками, которые играют по очереди
- первый игрок (Искатель) перемещается по графику (сидит на узле и движется вдоль ребра) и пытается достичь выигрышного узла. Если она может, она выигрывает.
- второй игрок (Ластик) может превратить выигрышные узлы в обычные узлы. Она выигрывает, если другой игрок не может выиграть, то есть она стерла все выигрышные узлы в обычные.
Меня интересует эта игра.
Например, если эта игра «может быть решена» за полиномиальное или даже за NP или coNP время, то есть, возможно ли решить, у кого выигрышная стратегия. Или есть ли эта игра в литературе, и известно ли, что она легкая или сложная, возможно, в другой форме.
Спасибо!
Редактировать:
- Я дал игрокам имена в соответствии с их ролями.
- Позиция P1 является частью начальной настройки
Комментарии:
1. Игрок один — начните с победившего узла, готово. Таким образом, начальная позиция игрока 1 должна быть частью экземпляра игры. У игрока 2 есть позиция, и он также должен двигаться? В противном случае стратегия p2 будет тривиальной, уничтожьте один из узлов, который ближе всего к p1. Если p1 слишком далеко, выигрывает p2, в противном случае выигрывает p1.
2. Это, по-видимому, связано с группой задач теории графов «полицейские и грабители» en.wikipedia.org/wiki/Cop-win_graph
3. «В противном случае стратегия p2 будет тривиальной, уничтожьте один из узлов, который ближе всего к p1». Это не работает даже на деревьях. Рассмотрим следующий график: (W) —- ( ) —- ( р1) —— ( ) —— ( Q) где W — выигрышный узел, и к Q присоединены 3 дополнительных выигрышных узла. В этом случае p2 может выиграть, но только если она уничтожит выигрышный узел рядом с Q, а не ближайший выигрышный узел.