Выигрышная стратегия игры удаления «ребро или изолированная вершина»

Знается ли / изучена ли эта совершенная информационная игра на графиках?

Учитывая график , два игрока поочередно выбирают ребро или изолированный узел. Если игрок выбирает ребро два узла и удаляются вместе с их падающими ребрами. Если игрок выбирает изолированный узел, узел удаляется. Первый игрок, который не может двигаться, проигрывает. $G= (V,E)$ $e = (u,v)$ $u$ $v$

В чем сложность поиска победителя?

Есть ссылки на похожие игры?

reference-request combinatorial-game-theory Марцио де Биаси
источник

Я предполагаю, что изолированный узел удаляется, если выбран? Если это так, игрок 0 выигрывает также на всех непустых путях, тратя первый ход, разделяя задачу на две равные составляющие, а затем отражая ход противников на противоположной составляющей, чтобы сохранить изоморфизм. Это подразумевает, что игрок 1 выигрывает в цикле, так как первый ход уменьшает проблему до пути.

Йонатан N

@YonatanN: да, изолированный узел можно выбрать (и удалить); но стратегия симметрии работает на путях четной длины (игрок 0 выбирает 2 центральных узла первым ходом, затем отражает ходы игрока 1), но не на путях нечетной длины: попытайтесь применить стратегию к пути длины 11, и это не работает (действительно, для пути длиной 11 победителем является игрок 1).

Марцио Де Биаси

@Marzio De Biasi: извините, но когда я играю в хорошие игры, я обычно играю вручную. Если я не допустил ошибок, у игрока 0 есть выигрышная стратегия: обратите внимание: a) для P1, P2, P5 и P8 игрок 0 всегда выигрывает б) для P3 и P7 игрок 1 всегда выигрывает. c) для P4 и P6 игрок 0 может решить выиграть или проиграть. Теперь в случае P11: - Нумеровать узлы P11 с помощью v1, v2, ... v11. - Игрок 0 берет ребро v9, v10, а остальное - изолированные узлы v11 и P8. Если игрок 1 берет v11, игрок 0 выиграет, потому что у него четный путь. В противном случае игрок 0 победит а), б) и в).

user13136

Согласно моей программе , значения n≤100 такие, что первый игрок проигрывает в игре на пути с n вершинами, равны 3, 7, 23, 27, 37, 41, 57, 61, 71, 75, 91, и 95. К сожалению, я не вижу никаких паттернов, кроме странных (которые уже были известны), и OEIS не показывает никаких совпадений.

Цуёси Ито

@TsuyoshiIto: ... возьмите попарную разницу: (3 7) (23 27) (37 41) (57 61) (71 75) (91 95) и вы получите 4 4 4 4 4 4 ... кажется, шаблон :-) .... (3 ... 23) ... (37 ... 57) ... (71 ... 91) и вы получите 20 20 20 ... еще один! :-D

Марцио Де Биаси

Ответы:

Я выкладываю обновление в качестве самостоятельного ответа только для того, чтобы отличать его от вопроса ( который все еще открыт ).

Как показано в комментариях (спасибо Tsuyoshi Ito), проблема разрешима для путей за полиномиальное время:

если $Win(P_n) = 1$ $(n \bmod 34) \in \{3,7,23,27\}$

Начиная с 0 (вычисленная) последовательность значений nim является периодической:

0,1,1,0,2,1,3,0,1,1,3,2,2,3,4,1,5,3,2,2,3,1,1,0,3,1,2,0,1,1,4,4,2,6,
4,1,1,0,2,1,3,0,1,1,3,2,2,3,4,4,5,7,2,2,3,1,1,0,3,1,2,0,1,1,4,4,3,6,
4,1,1,0,2,1,3,0,1,1,3,2,2,3,4,4,5,7,2,2,3,1,1,0,3,1,2,0,1,1,4,4,3,6,
...
the subsequence rseq of length 34:
4,1,1,0,2,1,3,0,1,1,3,2,2,3,4,4,5,7,2,2,3,1,1,0,3,1,2,0,1,1,4,4,3,6
is repeated

Я не работал над строгим математическим доказательством, но идея такова:

предположим, что мы хотим вычислить элемент , то первый ход (выбрать ребро) может разбить путь на различными способами (n-2,0), (n-3,1), ( п-4,2), ...). Новое значение nim равно: $Win(P_n), n = k*34 + x \; (k\geq 4, 0 \leq x < 34)$ $\lceil n / 2 \rceil$

$mex \{ P_{n-2}+P_0, P_{n-3}+P_1, ..., P_{\lceil n / 2 \rceil}+P_{n-\lceil n / 2 \rceil}\}$

Первые 34 элементов множества получают путем первой не повторяющейся последовательность (0,1,1,0, ...) (NIM) суммируется с элементами повторяющейся последовательности в обратном порядке , начиная с элемента . $(34-2-x) \bmod 34$

Например: для : $x = 0$

     0,1,1,0,2,1,3,0,1,1,3,2,2,3,4,1,5,3,2,2,3,1,1,0,3,1,2,0,1,1,4,4,2,6 +
     3,4,4,1,1,0,2,1,3,0,1,1,3,2,2,7,5,4,4,3,2,2,3,1,1,0,3,1,2,0,1,1,4,6 =
mex{ 3,5,5,1,3,1,1,1,2,1,2,3,1,1,6,6,0,7,6,1,1,3,2,1,2,1,1,1,3,1,5,5,6,0 } = 4

Для x = 0..33 результирующая мекс-последовательность равна повторяющейся последовательности:

4,1,1,0,2,1,3,0,1,1,3,2,2,3,4,4,5,7,2,2,3,1,1,0,3,1,2,0,1,1,4,4,3,6

Остальные элементы множества являются рассчитывается по формуле только на повторяющейся последовательности (ы): (для в пары повторяются, поэтому они не изменяют результат mex). Результирующая последовательность mex для x = 0..33: $rseq[j \bmod 34] + rseq[(34-2-x-j) \bmod 34]$ $j \geq 34$

4,1,1,0,2,1,3,0,1,1,3,2,2,3,4,4,4,7,2,2,3,1,1,0,3,1,2,0,1,1,4,4,3,4,

Который равен повторяющейся последовательности, за исключением и ; но значения ниже, чем соответствующий мекс в неповторяющейся последовательности, поэтому: $x=16$ $x=33$

= $mex \{ P_{n-2}+P_0, P_{n-3}+P_1, ..., P_{\lceil n / 2 \rceil}+P_{n-\lceil n / 2 \rceil}\}$ $mex \{ P_{n-2}+P_0, P_{n-3}+P_1, ..., P_{n-2-33}+P_{33}\}$

и , $(k\geq 4, 0 \leq x < 34)$ $Win(P_{k*34 + x}) = Win(P_{34+x}) = Win(P_x)\;$

Марцио де Биаси
источник

Согласно моим подсчетам, у первого игрока есть выигрышная стратегия для

, что дает контрпример к вашему требованию

тогда и только тогда

P_{23}

$P_{23}$

W i n (P_{n}) = 1

$Win(P_n)= 1$

(n \mod 34) \in {3, 7, 23, 27}

$(n \mod\, 34) \in \{3, 7, 23, 27\}$

user13136

P_{23}

$P_{23}$

P_{0}

$P_0$

P_{23}

$P_{23}$

Извините, мне пора уходить.

user13136

(n_{17}, n_{18}) \to (n_{5}, n_{6}) \to (n_{11}, n_{12}) \to (n_{1}, n_{2})

$(n_{17}, n_{18}) \to (n_{5}, n_{6}) \to (n_{11}, n_{12}) \to (n_{1}, n_{2})$