Kompleksitas hex dengan urutan belokan acak.

Saya telah memikirkan varian hex , di mana alih-alih kedua pemain membuat gerakan secara bergantian, setiap belokan yang dipilih pemain secara acak membuat gerakan. Seberapa sulit untuk menentukan peluang untuk setiap pemain yang menang? Masalah ini jelas di PSPACE, tetapi tidak bisa NP-keras, apalagi PSPACE-lengkap. Kesulitan datang dari bagaimana keacakan membuat pemain tidak mungkin dipaksa untuk membuat pilihan di antara opsi; jika pemain itu beruntung, ia mendapat cukup gerak, dua mengambil kedua opsi, dan jika pemain kurang beruntung, lawan mendapat cukup gerak untuk memblokir kedua opsi. Di sisi lain, saya tidak bisa memikirkan algoritma waktu polinomial untuk ini.

cc.complexity-theory board-games Itai Bar-Natan
sumber

Biarkan S menjadi string biner n-bit yang mewakili pemain mana yang mengambil giliran. Dalam kasus terburuk, Anda memulihkan gim hex standar jika urutan acak adalah 010101 ... atau 101010 .... Jadi, masalah Anda setidaknya sekeras hex standar.

Mohammad Al-Turkistany

Ada dua kemungkinan interpretasi dari game ini. (1) Tepat sebelum setiap belokan, para pemain melempar koin untuk menentukan siapa yang pergi selanjutnya. (2) Di awal permainan, para pemain melempar koin

kali (di papan ukuran

), dan menggunakan urutan ini untuk giliran mereka. Turkistany tampaknya menjadi model asumsi (2); pertanyaan aslinya ambigu, tetapi dari beberapa kata-katanya saya kira Itai bertanya tentang (1), yang mungkin lebih mudah daripada hex standar.

n^{2}

$n^2$

n

$n$

Peter Shor

Memang, maksud saya interpretasi pertama, bahwa koin diputar tepat sebelum bergerak. Selain itu, saya memperhatikan ambiguitas lain dalam pertanyaan saya: ketepatan di mana saya ingin mengetahui probabilitas. Sementara kesan yang saya tinggalkan ketika menanyakan masalah adalah bahwa saya ingin mengetahui probabilitas dalam presisi lengkap, tetapi saya hanya ingin tahu probabilitas dalam presisi logaritmik. Seperti perbedaan antara PP dan BPP, yang belakangan tampaknya lebih bermanfaat dan alami.

Itai Bar-Natan

@ Itai: Pertanyaan lain. Mengapa Anda mengklaim bahwa ini jelas di PSPACE? Tampak bagi saya bahwa itu adalah permainan wasit, yang berarti bahwa kompleksitas alami-teoretis batas atas adalah EKSPTIM. Lihat Feige dan Kilian, "Membuat Game Singkat."

Peter Shor

@tukistany Useless TIDAK menyiratkan sepele!

Jeffε

Jawaban:

Anda mungkin ingin melihat kertas "Random-Turn Hex dan Game Seleksi Lainnya," oleh Yuval Peres, Oded Schramm, Scott Sheffield, dan David Wilson. Dari pendahuluan:

"Random-Turn Hex sama dengan Hex biasa, kecuali bahwa alih-alih belokan bergantian, pemain melemparkan koin sebelum setiap belokan untuk memutuskan siapa yang akan menempatkan batu berikutnya. Meskipun Hex biasa terkenal sulit untuk dianalisis, strategi optimal untuk Random -Turn Hex ternyata sangat sederhana. "

Jadi memang, intuisi Anda benar: ini ada di BPP (atau mungkin P).

Peter Shor
sumber

Saya hanya kagum bahwa orang-orang benar-benar mengerjakan ini :) Referensi yang bagus!

Suresh Venkat

Itu bukti yang sangat bagus juga. Saya pikir saya mendengar Scott Sheffield menyebutkannya dalam salah satu ceramahnya (tapi kemudian saya benar-benar lupa tentangnya sampai muncul di Google).

Peter Shor

Juga, situs web David Wilson sebenarnya memiliki aplikasi yang memungkinkan Anda untuk bermain Hex secara acak (berlawanan dengan strategi mereka yang dipublikasikan, saya yakin): dbwilson.com/#software

Andy Drucker

Dalam kunjungan terakhirnya ke Israel, yang terinspirasi oleh makalah PSSW, Oded Schramm dan saya memainkan beberapa putaran catur acak untuk menyadari bahwa itu bukan permainan yang sangat menarik.

Gil Kalai

Ternyata ada hubungan yang luar biasa (karena David Richman) antara permainan belok acak dan permainan penawaran , di mana para pemain menawar untuk langkah selanjutnya; lihat arxiv.org/pdf/0812.3677.pdf dan users.math.yale.edu/ ~ sp547 / pdf / Discrete - bidding - games.pdf Koneksi ini memungkinkan untuk bermain Hex penawaran yang optimal, menggunakan karya Peres et al. Saya suka ini karena permainan penawaran, setidaknya seolah-olah, bebas keberuntungan, dan saya pikir penawaran Hex akan lebih memuaskan untuk dimainkan daripada Hex putar acak. (Namun, menawar setiap belokan mungkin merupakan tugas yang menjengkelkan.)

Andy Drucker