Zwycięska strategia gry polegającej na usuwaniu „krawędzi lub izolowanego wierzchołka”

Czy ta doskonała gra informacyjna rozgrywana na wykresach jest znana / studiowana?

Biorąc pod uwagę wykres $G= (V,E)$ , dwóch graczy na przemian wybiera krawędź lub izolowany węzeł. Jeśli gracz wybierze krawędź $e = (u,v)$ dwa węzły $u$ i $v$ zostaną usunięte wraz ze swoimi krawędziami padania. Jeśli gracz wybierze izolowany węzeł, węzeł zostanie usunięty. Pierwszy gracz, który nie może się poruszyć, przegrywa.

Jaka jest złożoność znalezienia zwycięzcy?

Jakieś odniesienia do podobnych gier?

reference-request combinatorial-game-theory

— Marzio De Biasi
źródło

Zakładam, że izolowany węzeł zostanie usunięty, jeśli zostanie wybrany? Jeśli tak, gracz 0 wygrywa również na wszystkich niepustych ścieżkach, wydając pierwszy ruch, dzieląc problem na dwa równe elementy, a następnie odzwierciedlając ruch przeciwnika na przeciwnym elemencie od tego momentu, aby zachować izomorfizm. Oznacza to, że gracz 1 wygrywa w cyklu, ponieważ pierwszy ruch redukuje problem do ścieżki.

— Yonatan N

@YonatanN: tak, izolowany węzeł można wybrać (i usunąć); ale strategia symetrii działa na ścieżkach o parzystej długości (gracz 0 wybiera pierwsze środkowe 2 węzły, a następnie odzwierciedla ruchy gracza 1), ale nie na ścieżkach o nieparzystej długości: spróbuj zastosować strategię na ścieżce o długości 11 i to nie działa (w przypadku ścieżki o długości 11 zwycięzcą zostaje gracz 1).

— Marzio De Biasi,

@Marzio De Biasi: Przykro mi, ale kiedy gram w fajne gry, zwykle gram ręcznie. O ile nie popełniłem błędów, gracz 0 ma strategię wygrywania: Zauważ, że: a) dla P1, P2, P5 i P8, gracz 0 zawsze wygrywa. b) w przypadku P3 i P7 gracz 1 zawsze wygrywa. c) w przypadku P4 i P6 gracz 0 może zdecydować o wygraniu lub przegranej. Teraz w przypadku P11: - Numeruj węzły P11 za pomocą v1, v2, ... v11. - Gracz 0 ma przewagę v9, v10, a reszta to izolowany węzeł v11 i P8. Jeśli gracz 1 weźmie v11, gracz 0 wygra, ponieważ ma równą ścieżkę. W przeciwnym razie gracz 0 wygra o a), b) ic).

— user13136,

Zgodnie z moim programem wartości n ≤ 100, tak że pierwszy gracz przegrywa w grze na ścieżce z n wierzchołkami, to 3, 7, 23, 27, 37, 41, 57, 61, 71, 75, 91 i 95. Niestety nie widzę żadnego wzorca innego niż bycie nieparzystym (co było już znane), a OEIS nie pokazuje żadnych dopasowań.

— Tsuyoshi Ito

@TsuyoshiIto: ... weź różnicę par: (3 7) (23 27) (37 41) (57 61) (71 75) (91 95) i otrzymasz 4 4 4 4 4 4 ... wydaje się wzór :-) .... (3 ... 23) ... (37 ... 57) ... (71 ... 91) i dostaniesz 20 20 20 ... kolejny! :-D

— Marzio De Biasi

Publikuję aktualizację jako odpowiedź własną, aby odróżnić ją od pytania ( które jest nadal otwarte ).

Jak pokazano w komentarzach (dzięki Tsuyoshi Ito) problem polega na rozwiązaniu ścieżek wielomianowych:

iif $Win(P_n) = 1$ $(n \bmod 34) \in \{3,7,23,27\}$

Począwszy od 0, (obliczona) sekwencja wartości NIM jest okresowa:

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

Nie pracowałem nad rygorystycznym dowodem matematycznym, ale pomysł jest taki:

załóżmy, że chcemy obliczyć element , a następnie pierwszy ruch (wybierz krawędź) może podzielić ścieżkę na różne sposoby (n-2,0), (n-3,1), ( n-4,2), ...). Nowa wartość nim jest równa: $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}\}$

Pierwsze 34 elementy zestawu są wytwarzane przez pierwszą niepowtarzalną sekwencję (0,1,1,0, ...) (nim) zsumowaną z elementami sekwencji powtarzalnej w odwrotnej kolejności, zaczynając od elementu . $(34-2-x) \bmod 34$

Na przykład: dla : $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

Dla x = 0..33 wynikowa sekwencja mex jest równa powtarzalnej sekwencji:

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

Pozostałe elementy zestawu są calulated tylko w powtarzającej się sekwencji (a): (w z pary są powtarzane, więc nie zmieniają wyniku mex). Wynikowa sekwencja mex dla x = 0..33 to: $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,

Co jest równe powtarzającej się sekwencji, z wyjątkiem i ; ale wartości są niższe niż odpowiadający mex w powtarzającej się sekwencji, więc: $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}\}$

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

— Marzio De Biasi
źródło

Według moich obliczeń, pierwszy gracz ma zwycięską strategię dla

, co daje przeciwny przykład dla twojego roszczenia

iff

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}$

Przepraszam, muszę teraz wyjść.

— 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})$