Versi Nash ekuilibrium yang dibatasi secara komputasi?

Saya bertanya-tanya apakah ada versi yang dibatasi secara komputasional dari konsep keseimbangan Nash, sesuatu di sepanjang baris berikut.

Bayangkan beberapa jenis dua pemain game informasi yang sempurna yang dimainkan pada papan, dan yang kompleks dalam arti bahwa bermain optimal adalah EXPTIME-keras. Misalkan juga untuk kesederhanaan yang menarik tidak mungkin. Bayangkan sepasang dari mesin Turing polinomial waktu acak bermain game ini satu sama lain. Untuk setiap , biarkan adalah probabilitas bahwa mengalahkan di pesanan- game. (Untuk konkret, katakanlah bisa bermain pertama dengan probabilitas 0,5.) Apa yang saya pikir akan keren adalah jika seseorang dapat membuktikan keberadaan pasangan$n\times n$$(A, B)$$n$$p_{A,B}(n)$$A$$B$$n$$A$$(A,B)$dengan properti yang tidak ada mesin Turing polinomial-waktu acak mendominasi (di mana " mendominasi " berarti untuk semua cukup besar ) , dan juga tidak ada mesin Turing polinomial waktu acak mendominasi (di mana " mendominasi " berarti untuk semua cukup besar ).$A'$ $A$$A'$$A$$p_{A',B}(n) > p_{A,B}(n)$$n$$B'$$B$$B'$$B$$p_{A,B'}(n) < p_{A,B}(n)$$n$

Entah bagaimana, saya menduga ini terlalu banyak untuk diharapkan, tetapi apakah ada harapan untuk hal seperti ini menjadi kenyataan, mungkin untuk kelas permainan yang terbatas?

Salah satu motivasi untuk pertanyaan ini adalah bahwa saya mencari cara untuk memformalkan gagasan bahwa posisi catur yang diberikan "menguntungkan bagi White." Secara klasik, suatu posisi adalah kemenangan bagi White atau tidak. Namun, pemain catur, baik manusia dan komputer, memiliki pemahaman intuitif tentang apa artinya bagi White untuk memiliki keunggulan. Tampaknya ada hubungannya dengan probabilitas bahwa White akan menang, mengingat bahwa para pemain terikat secara komputasi dan harus menebak langkah terbaik. Untuk pasangan tertentu dari algoritma acak seseorang tentu saja dapat berbicara tentang probabilitas bahwa White akan menang, tetapi yang saya ingin tahu adalah apakah ada, dalam beberapa hal, kanonik sepasang pemain yang terikat secara komputasi yang probabilitas menangnya menghasilkan nilai untuk posisi yang hanya bergantung pada permainan itu sendiri dan bukan keanehan para pemain.

Saya tidak bisa memikirkan cara apa pun untuk menjawab pertanyaan ini dengan mudah, sepenuhnya elegan / memuaskan, terutama karena hasil akhirnya sangat sulit untuk dihitung; Namun, pikiran saya terlalu panjang untuk dikirim sebagai komentar.

Ide terbaik yang saya miliki adalah ini: Dalam hal catur, coba perkiraan kemungkinan bahwa White akan menang berdasarkan keunggulan material White (yaitu, bidak tambahan, ksatria, dll.) Untuk posisi tertentu dengan secara acak memilih posisi dengan jumlah yang tepat. konfigurasi bahan. Mungkin dalam kasus "catur semua benteng," kita dapat mengatakan, "Seberapa besar kemungkinan White menang dengan 8 benteng menjadi 17 benteng Black?" Mungkin probabilitas ini adalah 4%; untuk menghitungnya, kita harus memeriksa (katakanlah) 1000 posisi catur yang berbeda yang dihasilkan secara acak yang memiliki 8 benteng putih dan 17 benteng hitam, dan kemudian melihat ke depan (katakanlah) 10 gerakan dalam-dalam dalam setiap kasus, dan lihat apa konfigurasi materi yang baru. . Kemudian, ambil peluang yang diharapkan berdasarkan pada konfigurasi material di akhir,

Tentu saja, akan diperlukan untuk menemukan konfigurasi material untuk setiap kemungkinan yang relevan ( M , N ) dari rooks M putih ke N rooks hitam ... mungkin mulai dari pasangan dengan urutan terendah ( M = 1, N = 1) dan bekerja dari sana.

Untuk posisi asli, jangan hanya pergi dengan statistik yang Anda dapatkan (yaitu, jika posisi asli memiliki ( M = 6, N = 7) rooks, jangan hanya berasumsi bahwa White memiliki peluang 25% untuk menang karena itu peluang kemenangan yang diharapkan untuk (6,7)); sebagai gantinya, karena Anda bisa lebih tepat, lihat 10 gerakan dalam seperti biasa hanya dengan satu posisi ini dan temukan setiap posisi akhir yang memungkinkan. Kemudian, cari jalur yang benar (yang melibatkan permainan optimal oleh kedua sisi) ke konfigurasi 10 langkah, dan pilih peluang jalur ini sebagai peluang yang diharapkan dari posisi awal.

Saya pikir proses ini dapat dilakukan dalam waktu polinomial. Mencari k bergerak dalam untuk k tetap dalam catur adalah polinomial dalam ukuran papan, dan jumlah total benteng putih dan hitam dinyatakan dalam unary (dalam arti) karena jumlah itu harus lebih kecil dari ukuran papan.

Jika ini terdengar rumit dan sulit untuk dijelaskan, itu memang benar. Ringkasan yang lebih ringkas dari apa yang saya jelaskan adalah: Gunakan rekursi dan statistik dasar untuk menghitung peluang kemenangan untuk rook putih M putih dan rook hitam N di papan tulis. Kemudian gunakan nilai-nilai ini untuk melihat k bergerak dalam-dalam dan memastikan peluang bahwa White akan menang di posisi semula.

Komentar akhir: Saya pikir masalah ini juga menarik untuk game yang tidak lengkap EXPTIME, seperti tic-tac-toe, yang menurut Wikipedia adalah PSPACE-complete. Lebih lanjut, saya percaya proses seperti yang saya jelaskan di atas juga bisa berguna di sana, walaupun jelas tidak mungkin memiliki keunggulan "material" dalam tic-tac-toe; harus ada dasar lain untuk menilai superioritas posisi X atau O.