Strategi kemenangan dari permainan penghapusan “edge or isolated vertex”

Apakah permainan informasi yang sempurna ini dimainkan pada grafik yang diketahui / dipelajari?

Diberikan grafik , dua pemain bergantian memilih tepi atau simpul yang terisolasi. Jika pemain memilih tepi dua simpul dan dihapus bersama dengan tepi insidennya. Jika pemain memilih simpul yang terisolasi, simpul itu dihapus. Pemain pertama yang tidak bisa bergerak kehilangan permainan. $G= (V,E)$ $e = (u,v)$ $u$ $v$

Apa kompleksitas menemukan pemenang?

Adakah referensi ke game serupa?

reference-request combinatorial-game-theory Marzio De Biasi
sumber

Saya menganggap simpul terisolasi dihapus jika dipetik? Jika demikian, pemain 0 menang juga di semua jalur kosong dengan menghabiskan langkah pertama membagi masalah menjadi dua komponen yang sama dan kemudian mencerminkan lawan bergerak pada komponen yang berlawanan sejak saat itu untuk mempertahankan isomorfisme. Ini menyiratkan pemain 1 menang pada satu siklus, karena langkah pertama mengurangi masalah ke jalur.

Yonatan N

@YonatanN: ya simpul yang terisolasi dapat diambil (dan dihapus); tetapi strategi simetri bekerja pada jalur yang panjangnya genap (pemain 0 mengambil 2 simpul pusat sebagai gerakan pertama, kemudian mencerminkan gerakan pemain 1), tetapi tidak pada jalur yang panjangnya ganjil: cobalah menerapkan strategi ke jalur panjang 11, dan itu tidak berhasil (memang untuk jalur panjang 11 pemenangnya adalah pemain 1).

Marzio De Biasi

@ Marszio De Biasi: Saya minta maaf, tetapi ketika saya memainkan permainan bagus saya biasanya bermain dengan tangan. Kecuali saya membuat kesalahan, pemain 0 memang memiliki strategi kemenangan: Perhatikan bahwa: a) untuk P1, P2, P5, dan P8, pemain 0 selalu menang. b) untuk P3 dan P7, pemain 1 selalu menang. c) untuk P4 dan P6, pemain 0 dapat memutuskan untuk menang atau kalah. Sekarang dalam kasus P11: - Beri nomor node P11 dengan v1, v2, ... v11. - Pemain 0 mengambil tepi v9, v10 dan sisanya adalah simpul terisolasi v11 dan P8. Jika pemain 1 mengambil v11, pemain 0 akan menang karena ia memiliki jalur yang genap. Kalau tidak, pemain 0 akan menang dengan a), b) dan c).

user13136

Menurut program saya , nilai-nilai n≤100 sehingga pemain pertama kalah dalam permainan di jalur dengan n simpul adalah 3, 7, 23, 27, 37, 41, 57, 61, 71, 75, 75, 91, dan 95. Sayangnya, saya tidak melihat pola apa pun selain menjadi aneh (yang sudah diketahui), dan OEIS tidak menunjukkan kecocokan apa pun.

Tsuyoshi Ito

@TsuyoshiIto: ... ambil perbedaan berpasangan: (3 7) (23 27) (37 41) (57 61) (71 75) (91 95) dan Anda mendapatkan 4 4 4 4 4 4 ... sepertinya pola :-) .... (3 ... 23) ... (37 ... 57) ... (71 ... 91) dan Anda mendapatkan 20 20 20 ... satu lagi! :-D

Marzio De Biasi

Jawaban:

Saya memposting pembaruan sebagai jawaban sendiri hanya untuk membuatnya berbeda dari pertanyaan ( yang masih terbuka ).

Seperti yang ditunjukkan dalam komentar (terima kasih kepada Tsuyoshi Ito) masalahnya adalah waktu polinomial yang dapat dipecahkan untuk jalur:

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

Mulai dari 0, urutan (dihitung) dari nilai nim adalah periodik:

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

Saya tidak bekerja pada bukti matematika yang ketat, tetapi idenya adalah:

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

Untuk x = 0..33 urutan mex yang dihasilkan sama dengan urutan berulang:

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

$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)\;$

Marzio De Biasi
sumber

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: apakah Anda memeriksa nilai nim? Untuk nilai nim adalah 0 (saya mendapat nilai Tsuyoshi yang sama dengan program yang berbeda, tapi mungkin kami berdua salah).

P_{23}

$P_{23}$

Marzio De Biasi

Saya pikir kesalahan yang mungkin ada dalam program Anda adalah mengabaikan , dalam hal ini pemain pertama selalu kalah. Jika Anda mau, kami dapat memainkan case sekarang.

P_{0}

$P_0$

P_{23}

$P_{23}$

user13136

Maaf, saya harus pergi sekarang.

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})$ (Anda dapat menghapus komentar sebelumnya yang berisi gerakan)

Marzio De Biasi