Versi sederhana dari permainan kartu Winner

Saya telah menanyakan masalah ini di MathOverflow , tanpa jawaban yang memuaskan.

Pertimbangkan permainan dua pemain berikut ini, yang merupakan penyederhanaan dari permainan kartu yang disebut Winner . (Formulasi berikut diambil dari komentar oleh Guillaume Brunerie di MathOverflow.)

Ada dua pemain A dan B. Setiap pemain memiliki satu set kartu (subset dari ), terlihat dari kedua pemain. Tujuan permainan ini adalah untuk menyingkirkan kartunya sendiri. Pemain pertama memainkan kartu apa saja di atas meja, maka pemain lain harus memainkan kartu (ketat) yang lebih besar, dan seterusnya hingga salah satu pemain tidak dapat bermain atau memutuskan untuk lulus. Kemudian kartu di atas meja dibuang, dan pemain lain mulai lagi dengan memainkan kartu apa pun (yang akan diikuti oleh kartu yang lebih besar). Dan seterusnya sampai salah satu dari dua pemain kehabisan kartu dan memenangkan permainan.$\{1,\dots,n\}$

Saya ingin tahu strategi terbaik untuk para pemain (jika dia bisa menang).

Definisi formal

Ditandai dengan konfigurasi permainan di mana set kartu pemain pertama adalah A , set kartu pemain kedua adalah B , dan kartu terbesar di atas meja adalah i , di mana i = 0 berarti tidak ada kartu di atas meja. Saya ingin algoritma menghitung, mengingat i , A , B , apakah pemain pertama memiliki strategi kemenangan dalam konfigurasi w ( i , A , B ) .$w(i,A,B)$$A$$B$$i$$i=0$$i,A,B$$w(i,A,B)$

Secara formal, saya ingin algoritma untuk menghitung fungsi didefinisikan sebagai berikut:$f$

Mari , B o o l = { F a l s e , T r u e } .$\mathbb{Z}_n = \left\{1, 2, \cdots, n\right\}$$\mathrm{Bool} = \left\{\mathrm{False}, \mathrm{True}\right\}$

Fungsi $f:\;\left\{ 0, 1, \cdots, n \right\} \times 2^{\mathbb{Z}_n} \times 2^{\mathbb{Z}_n} \to \mathrm{Bool}$

Strategi yang salah

Berikut adalah beberapa strategi yang salah:

1. $n = 3, A = \{1,3\}, B = \{2\}$$w(0, A, B)$$3$
2. $w(0, \{1, 4, 6, 7\}, \{2, 3, 5, 8\})$$1\rightarrow2\rightarrow4\rightarrow5\rightarrow6\rightarrow8\rightarrow\textrm{pass}\rightarrow3$

Ini mungkin komentar, tapi terlalu panjang.

$n$$2n$$1$ $\ldots$ $2n$

Mereka membuktikan sejumlah fakta menarik tentang strategi optimal, tetapi tidak dapat menemukan algoritma yang efisien untuk bermain optimal, dan juga tidak dapat membuktikan bahwa itu NP-hard.

Untuk permainan misère , di mana setiap orang mencoba untuk mengambil jumlah trik paling sedikit, mereka mampu memberikan strategi yang optimal.

Sebagian besar, hasil ini diperoleh dengan pertama-tama melihat hasil program komputer yang menemukan strategi optimal untuk contoh kecil, kemudian mencari pola untuk mendapatkan dugaan, dan akhirnya membuktikan dugaan ini. Saya menduga bahwa ini juga akan menjadi pendekatan yang bermanfaat untuk permainan OP.