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
sumber
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:
Jadi memang, intuisi Anda benar: ini ada di BPP (atau mungkin P).
sumber