Aplikasi MCTS / UCT

MCTS / UCT adalah metode pencarian tree game yang menggunakan algoritma bandit untuk memilih node yang menjanjikan untuk dijelajahi. Permainan dimainkan sampai selesai secara acak dan simpul yang mengarah ke lebih banyak kemenangan dieksplorasi lebih berat. Algoritme bandit menjaga keseimbangan antara penjelajahan simpul dengan tingkat kemenangan tinggi dan penjelajahan simpul yang tidak diketahui (dan dalam bentuk murni tidak perlu menggunakan fungsi evaluasi heuristik). Program-program yang didasarkan pada teknik umum ini telah mencapai hasil yang cukup luar biasa di komputer Go .

Apakah pencarian monte-carlo yang digerakkan oleh bandit telah diterapkan pada masalah pencarian lainnya? Misalnya, apakah itu akan menjadi pendekatan yang berguna dalam mendekati solusi untuk MAX-SAT, BKP, atau masalah optimasi kombinatorial lainnya? Adakah karakteristik masalah tertentu (struktural / statistik / dll.) Yang akan menyarankan apakah pendekatan gaya bandit akan efektif atau tidak?

Adakah masalah deterministik yang diketahui yang akan benar-benar tahan terhadap metode bandit, karena sifat ruang solusi?

Ini bukan jawaban yang lengkap, tetapi beberapa pengamatan dasar tentang penerapan ini pada MAX-SAT.

$7/8$$x=0$$x=1$$x=0$$x=1$$7/8$$7/8$

$7/8$$NP$$7/8$heuristik yang Anda gunakan, bahkan jika Anda menebak dengan sempurna, masih ada rumus yang tidak memuaskan yang hanya mengulangi akan menyimpulkan mereka tidak memuaskan setelah banyak langkah secara eksponensial. Batas bawah pada panjang bukti resolusi menghasilkan hasil ini. Salah satu referensi adalah:

Pavel Pudlák, Russell Impagliazzo: Batas bawah untuk algoritma DLL untuk k-SAT (versi awal). SODA 2000: 128-136

Adapun pertanyaan tentang karakteristik apa yang membuat masalah setuju dengan pendekatan berbasis bandit, makalah ini menjelaskan perilaku UCT di berbagai ruang pencarian:

http://www.cs.cornell.edu/~raghu/Raghuram_Ramanujan_files/mcts11.pdf

Salam, Cameron

Makalah survei terbaru ini mencantumkan aplikasi MCTS ke sejumlah masalah pencarian dan optimisasi selain game, di Bagian 7.8:

http://pubs.doc.ic.ac.uk/survey-mcts-methods/survey-mcts-methods.pdf

http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=6145622

Adapun domain yang benar-benar tahan terhadap metode berbasis bandit, saya tidak mengetahui adanya masalah. Catur adalah salah satu penghilangan mencolok dari literatur MCTS, mungkin karena "status jebakan" yang mengganggu pencarian, tetapi juga mungkin karena fakta bahwa pemain Catur komputer sangat dioptimalkan dan bagus akhir-akhir ini sehingga setiap pendekatan baru tidak mungkin dilakukan lekuk pada mereka.

Salam, Cameron