Redux permutasi game

Ini adalah pernyataan kembali dari pertanyaan sebelumnya .

Pertimbangkan permainan informasi sempurna yang tidak memihak antara dua pemain, Alice dan Bob. Para pemain diberi permutasi bilangan bulat 1 sampai n. Di setiap belokan, jika permutasi saat ini meningkat, pemain saat ini kalah dan pemain lain menang; jika tidak, pemain saat ini menghapus salah satu angka, dan memainkan pass ke pemain lain. Alice bermain terlebih dahulu. Sebagai contoh:

• (1,2,3,4) - Bob langsung menang, menurut definisi.

• (4,3,2,1) - Alice menang setelah tiga putaran, tidak peduli bagaimana orang bermain.

• (2,4,1,3) - Bob bisa menang pada giliran pertamanya, tidak peduli bagaimana Alice bermain.

• (1,3,2,4) - Alice segera menang dengan menghapus 2 atau 3; jika tidak, Bob dapat menang pada giliran pertamanya dengan menghapus 2 atau 3.

• (1,4,3,2) - Alice akhirnya menang jika dia mengambil angka 1 pada giliran pertama; jika tidak, Bob bisa menang pada giliran pertamanya dengan tidak melepas 1.

Apakah ada algoritma waktu polinomial untuk menentukan pemain mana yang memenangkan game ini dari permutasi awal yang diberikan, dengan asumsi bermain sempurna ? Lebih umum, karena ini adalah permainan standar yang tidak memihak, setiap permutasi memiliki nilai Sprague-Grundy ; misalnya, (1,2,4,3) memiliki nilai * 1 dan (1,3,2) memiliki nilai * 2. Seberapa sulit untuk menghitung nilai ini?

Algoritma backtracking yang jelas berjalan dalam waktu O (n!), Meskipun ini dapat direduksi menjadi waktu melalui pemrograman dinamis.$O(2^n poly(n))$

"Permutasi game" isomorfik untuk gim berikut:

Memutuskan. Pemain bergantian menghapus simpul dari graf . Pemain yang menghasilkan grafik yang terputus sepenuhnya (yaitu, grafik tanpa tepi) adalah pemenangnya.$G$

Grafik berhubungan dengan permutasi awal tertentu π ∈ S n berisi hanya sisi-sisi tersebut ( i , j ) yang i - j dan π ( i ) - π ( j ) memiliki tanda-tanda yang berlawanan. Artinya, setiap pasangan angka salah$G_{\pi}$$\pi\in S_n$$(i,j)$$i-j$$\pi(i)-\pi(j)$urutan permutasi dikaitkan dengan edge. Jelas gerakan yang diizinkan adalah isomorfis bagi yang ada dalam permutasi permainan (hapus angka = hapus simpul), dan kondisi yang menang adalah isomorfik juga (tidak ada pasangan dalam urutan menurun = tidak ada tepi yang tersisa).

Pandangan komplementer diperoleh dengan mempertimbangkan memainkan game "ganda" pada komplemen grafik , yang berisi tepi-tepi ( i , j ) yang i dan j berada dalam urutan yang benar dalam permutasi. Game ganda untuk Putus adalah:$G^{c}_\pi = G_{R(\pi)}$$(i,j)$$i$$j$

Hubungkan kembali. Pemain bergantian menghapus simpul dari graf . Pemain yang menghasilkan grafik lengkap adalah pemenangnya.$G$

Bergantung pada permutasi tertentu, salah satu game ini mungkin tampak lebih sederhana daripada yang lain untuk dianalisis. Keuntungan dari representasi grafik adalah jelas bahwa komponen-komponen grafik yang terputus adalah permainan yang terpisah, sehingga orang berharap untuk pengurangan kompleksitas. Itu juga membuat simetri posisi lebih jelas. Sayangnya, kondisi yang menang tidak standar ... permutasi permainan akan selalu berakhir sebelum semua gerakan habis, memberikannya karakter misère . Secara khusus, nim-nilai tidak dapat dihitung sebagai nim-sum (biner XOR) dari nim-nilai komponen yang terputus.

Untuk Putus, tidaklah sulit untuk melihat bahwa untuk grafik setiap dan setiap bahkan n , permainan G ∪ ˉ K n setara dengan G (di mana ˉ K n adalah grafik edgeless pada n simpul). Untuk membuktikannya, kita harus menunjukkan bahwa jumlah disjungtif G + G ∪ ˉ K n adalah kemenangan pemain kedua. Buktinya adalah dengan induksi pada | G | + n . Jika $G$$n$$G \cup \bar{K}_n$$G$$\bar{K}_n$$n$$G + G\cup\bar{K}_n$$|G|+n$$G$edgeless, maka pemain pertama langsung kalah (kedua game berakhir). Jika tidak, pemain pertama dapat bergerak di salah satu , dan pemain kedua dapat menyalin gerakannya di yang lain (dikurangi menjadi G ′ + G ′ ∪ ¯ K n dengan | G ′ | = | G | - 1 ); atau, jika n ≥ 2 , pemain pertama dapat bergerak di bagian yang terputus, dan pemain kedua dapat melakukan hal yang sama (dikurangi menjadi G + G ∪ ˉ K n - 2 ).$G$$G' + G'\cup \bar{K_n}$$|G'|=|G|-1$$n\ge 2$$G + G\cup\bar{K}_{n-2}$

Ini menunjukkan bahwa setiap graf adalah setara dengan H ∪ K p , di mana H adalah bagian dari G tanpa simpul terputus, dan p = 0 atau 1 adalah paritas dari jumlah simpul terputus di G . Semua game di kelas kesetaraan memiliki yang sama nim-nilai, dan terlebih lagi, kesetaraan hubungan hal operasi union: jika G ~ H ∪ K p dan G ' ~ H ' ∪ K p ' kemudian $G$$H \cup K_p$$H$$G$$p=0$$1$$G$$G \sim H \cup K_p$$G' \sim H' \cup K_{p'}$ . Selain itu, orang dapat melihat bahwa permainan di [ H ∪ K 0 ] dan [ H ∪ K 1 ] memiliki nilai nim yang berbeda kecuali H adalah grafik nol: ketika bermain H + H ∪ K 1 , pemain pertama dapat mengambil yang terisolasi simpul, meninggalkan H + H , dan kemudian menyalin gerakan pemain kedua sesudahnya.$G \cup G' \sim (H \cup H')\cup K_{p\oplus p'}$$[H \cup K_0]$$[H \cup K_1]$$H$$H + H \cup K_1$$H+H$

Saya tidak tahu hasil dekomposisi terkait untuk Hubungkan kembali.

Dua jenis permutasi khusus berhubungan dengan game heap yang sangat sederhana.

1. Yang pertama adalah menaik menjalankan dari keturunan , misalnya, . Ketika π mengambil formulir ini, grafik G π adalah gabungan dari klik-klik yang terpisah, dan permainan Disconnect dikurangi menjadi sebuah game dengan tumpukan: pemain secara bergantian menghapus satu kacang dari tumpukan sampai semua tumpukan memiliki ukuran 1 .$32165487$$\pi$$G_{\pi}$$1$
2. Yang kedua adalah penurunan yang naik , misalnya, . Ketika π mengambil formulir ini, grafik G c π adalah gabungan klik yang terputus-putus, dan gim Reconnect mengecil menjadi gim dengan tumpukan: pemain secara bergantian melepas satu biji dari tumpukan sampai hanya ada satu tumpukan yang tersisa .$78456123$$\pi$$G^{c}_{\pi}$

Sebuah pemikiran kecil menunjukkan bahwa dua permainan berbeda ini bertumpuk (kita dapat menyebutnya 1-Tumpukan dan Satu Tumpukan , dengan beberapa risiko kebingungan), pada kenyataannya, itu sendiri isomorfis. Keduanya dapat diwakili oleh permainan pada diagram Young (seperti yang awalnya diusulkan oleh @domotorp) di mana pemain secara bergantian menghapus kotak kanan bawah sampai hanya satu baris yang tersisa. Ini jelas merupakan game yang sama dengan 1-Heaps ketika kolom sesuai dengan heaps, dan game yang sama dengan One-Heap ketika baris sesuai dengan heaps.

Elemen kunci dari game ini, yang meluas ke Disconnect dan Reconnect, adalah durasinya terkait dengan status game final dengan cara yang sederhana. Saat giliran Anda tiba, Anda akan menang jika gim masih tersisa, termasuk gim yang akan Anda buat. Karena satu kotak dihapus setiap gerakan, ini berarti Anda ingin jumlah kotak yang tersisa di akhir permainan memiliki paritas yang berlawanan dengan yang ada sekarang. Selain itu, jumlah kotak akan memiliki paritas yang sama di semua belokan Anda; jadi Anda tahu dari awal berapa paritas yang Anda inginkan untuk penghitungan akhir. Kita dapat memanggil dua pemain Eve dan Otto, berdasarkan apakah penghitungan akhir harus genap atau ganjil bagi mereka untuk menang. Hawa selalu bergerak di negara-negara dengan paritas ganjil dan menghasilkan negara-negara dengan paritas genap, dan Otto sebaliknya.

Dalam jawabannya, @PeterShor memberikan analisis lengkap One-Heap. Tanpa mengulangi buktinya, hasilnya adalah sebagai berikut:

• Otto suka heaps dan 2- heaps, dan bisa mentolerir tumpukan yang lebih besar. Dia menang jika dia dapat membuat semua ukuran tumpukan kecuali satu ≤ 2 , setidaknya tanpa memberi Hawa kemenangan langsung dari formulir ( 1 , n ) . Strategi optimal untuk Otto adalah untuk selalu mengambil dari tumpukan terbesar kedua kecuali ketika negara adalah ( 1 , 1 , n > 1 ) , ketika ia harus mengambil dari n . Otto akan kalah jika terlalu banyak kacang dalam tumpukan besar untuk memulai.$1$$2$$\le 2$$(1,n)$$(1,1,n>1)$$n$
• Eve tidak suka -heaps. Dia menang jika dia dapat membuat semua ukuran tumpukan ≥ 2 . Strategi optimal untuk Hawa adalah selalu mengambil dari 1- heap, jika ada, dan tidak pernah mengambil dari 2- heap. Hawa akan kalah jika terlalu banyak 1- tumpukan untuk memulai.$1$$\ge 2$$1$$2$$1$

Seperti disebutkan, ini memberikan strategi optimal untuk 1-Heaps juga, walaupun mereka agak canggung untuk frase (dan saya mungkin membuat kesalahan dalam "terjemahan" primer-ke-ganda). Dalam game 1-Heaps:

• Otto menyukai satu atau dua tumpukan besar, dan dapat mentoleransi jumlah tumpukan. Dia menang jika dia bisa membuat semua kecuali dua tumpukan terbesar menjadi 1- tumpukan, setidaknya tanpa memberi Hawa kemenangan langsung dari formulir ( 1 , 1 , … , 1 , 2 ) . Strategi optimal untuk Otto adalah selalu mengambil dari tumpukan terbesar ketiga, atau dari tumpukan kecil ketika hanya ada dua tumpukan.$1$$1$$(1,1,\dots,1,2)$
• Eve tidak menyukai celah antara tumpukan terbesar dan terbesar kedua. Dia menang jika dia bisa membuat dua tumpukan terbesar dengan ukuran yang sama. Strategi optimal untuk Hawa adalah selalu mengambil dari tumpukan terbesar, jika unik, dan tidak pernah jika ada tepat dua dari ukuran terbesar.

Sebagaimana dicatat oleh @PeterShor, tidak jelas bagaimana (atau jika) analisis ini dapat diperluas ke permainan Putus dan Hubungkan kembali yang lebih umum.

Dalam jawabannya, domotorp menyarankan untuk menganalisis kasus khusus permainan. Kasus khusus ini muncul ketika permutasi adalah serangkaian urutan meningkat, masing-masing lebih besar dari yang berikut, seperti (8,9,5,6,7,4,1,2,3). Dalam permainan ini, Anda mulai dengan koleksi tumpukan batu, dan pemain secara bergantian menghapus satu batu dari tumpukan. Pemain yang meninggalkan satu tumpukan menang. Kami akan mengatakan tumpukan th memiliki h i batu di dalamnya, dan menganggap bahwa h i diberikan dalam urutan menurun. Misalnya, untuk permutasi di atas, h $i$$h_i$$h_i$$h_i$adalah 3,3,2,1. Saya mencoba memberikan analisis permainan ini di komentar untuk jawaban domotorp, tetapi (a) saya salah dan (b) tidak ada cukup ruang di komentar untuk memberikan bukti nyata.

Untuk menganalisis permainan ini, kita perlu membandingkan dua jumlah: , jumlah tumpukan yang mengandung batu tunggal dan t = ∑ i ≥ 2 , h i > $s$ ; perhatikan bahwa kita mengabaikan tumpukan terbesar dalam jumlah. Ini adalah jumlah batu yang harus Anda hapus untuk memastikan bahwa semua timbunan tetapi satu berisi tidak lebih dari dua batu. Kami mengklaim bahwa posisi yang hilang adalah sebagai berikut:$t=\sum_{i\geq 2, h_i>2\,} h_i -2$

1. Posisi di mana berisi jumlah batu ganjil.$t \leq s-2$

2. Posisi di mana berisi jumlah batu genap.$t \geq s$

Sangat mudah untuk menunjukkan bahwa dari posisi yang kalah, Anda harus pergi ke posisi yang menang, karena hanya dapat berubah paling banyak 1 setiap belokan, dan jumlah batu turun 1 langkah.$t - s$

Untuk menyelesaikan menunjukkan bahwa ini benar, kita perlu menunjukkan bahwa dari posisi apa pun yang tidak dalam kategori (1) atau (2), pemain pertama dapat dalam satu gerakan mencapai posisi dalam kategori (1) atau (2), atau menang langsung.

Ada dua kasus:

1. Posisi di mana berisi jumlah batu ganjil. Di sini, jika s > 0 , lepaskan batu dari tumpukan dengan satu batu. Jika hanya ada satu tumpukan yang tersisa, kita menang. Kalau tidak, sekarang kita memiliki t ≥ s . Jika tidak ada tumpukan dengan satu batu, lepaskan batu dari tumpukan dengan setidaknya tiga batu. (Karena ada jumlah batu yang ganjil, ini mungkin). Karena s = 0 , kita memiliki t ≥ s .$t \geq s-1$$s>0$$t \geq s$$s = 0$$t \geq s$

2. $t \leq s-1$$t$$s$$t \leq s-2$

Saya sudah mencoba menyamaratakan strategi ini ke gim asli, dan belum menemukan cara melakukannya.

$O(2^n n)$

@ Jɛ ff E Kebetulan (1,4,3,2) memiliki nilai * 1, bukan * 2 seperti yang Anda sarankan.

Sunting 5 Jan: Faktanya One Heap Game yang dijelaskan di bawah ini adalah kasus khusus dari masalah, yaitu ketika angka-angka saling mengikuti dengan cara tertentu sehingga kelompok pertama lebih besar dari kelompok kedua yang lebih besar dari yang ketiga dll dan jumlah di masing-masing kelompok meningkat. Misalnya 8, 9, 4, 5, 6, 7, 2, 3, 1 adalah permutasi yang demikian. Jadi saya mengusulkan untuk menyelesaikan kasus khusus ini terlebih dahulu.

Penafian: Saya tidak lagi mengklaim bahwa bukti di bawah ini benar, lihat misalnya komentar Tsuyoshi yang menunjukkan bahwa menghapus nomor dari permutasi akan memberikan diagram yang tidak dapat diperoleh dengan menghapus kuadrat dari diagram permutasi. Saya meninggalkan jawaban di sini untuk menunjukkan bahwa pendekatan ini tidak berhasil, ditambah lagi karena berisi permainan sederhana lainnya.

Permainan ini memiliki formulasi lain yang sangat sederhana berkat Young Tableaux. Saya yakin itu bisa dianalisis dari sana sebagai game lain dan itu akan menghasilkan algoritma waktu linier.

Pertama-tama tentukan permainan berikut pada Young Diagram: Di setiap belokan, jika diagram saat ini adalah horisontal (semua kotak dalam satu baris), pemain saat ini kalah dan pemain lain menang; jika tidak, pemain saat ini menghapus salah satu kotak di kanan bawah, dan bermain melewati ke pemain lain.

Sekarang pesan urutan angka menjadi Tableaux Muda. Klaim utama adalah bahwa pemenang dari game asli sama dengan pemenang seperti diagram game yang dimulai dengan bentuk ini. Untuk melihat ini, perhatikan bahwa setiap kali pemain menghapus angka, diagram urutan baru dapat dicapai dengan menghapus kuadrat kanan bawah diagram. Selain itu, diagram semacam itu dapat dicapai dengan menghapus nomor dari masing-masing kotak kanan bawah. Pernyataan-pernyataan ini mengikuti dari teori Young Tableaux standar.

Meskipun permainan diagram ini cukup sederhana, ini sepele setara dengan permainan berikut, yang tampaknya lebih standar:

Satu Heap Game: Para pemain diberi beberapa tumpukan dengan beberapa kerikil di masing-masing. Di setiap belokan, jika hanya ada satu tumpukan yang tersisa, pemain saat ini kalah dan pemain lainnya menang; jika tidak, pemain saat ini menghilangkan sebuah kerikil dari tumpukan, dan bermain melewati ke pemain lain.

Jika ada solusi sederhana untuk game heap (dan saya sangat percaya ada game) kami juga mendapatkan solusi untuk game original: Cukup masukkan urutannya dalam Young Tableaux, dan ubah diagramnya menjadi banyak.

Sayangnya saya tidak melihat posisi tumpukan mana yang menang / bagaimana menentukan nilai Sprague-Grundy. Saya memeriksa beberapa kasing dengan tangan, dan berikut ini adalah posisi yang hilang dengan paling banyak 6 kerikil:

satu tumpukan; (1,1,1); (2,2); (3,1,1); (2,1,1,1); (1,1,1,1,1); (4,2); (3,3); (2,2,2).

Adakah yang bisa menyelesaikan game ini?

Sunting: Peter Shor dapat, lihat jawabannya!