Saya ingin memulai dengan skenario yang membuat saya berpikir tentang seberapa baik MCTS dapat melakukan: Mari kita asumsikan ada langkah yang belum ditambahkan ke pohon pencarian. Itu beberapa lapisan / gerakan terlalu dalam. Tetapi jika kita memainkan langkah ini, permainan pada dasarnya dimenangkan. Namun mari kita juga berasumsi bahwa semua gerakan yang bisa diambil sebagai gantinya pada kondisi permainan yang diberikan sangat buruk. Demi argumen, katakanlah ada 1000 kemungkinan gerakan dan hanya satu di antaranya yang bagus (tapi sangat bagus) dan sisanya sangat buruk. Bukankah MCTS gagal mengenali ini dan tidakmenumbuhkan pohon pencarian ke arah langkah ini dan juga menilai subtree ini dengan sangat buruk? Saya tahu bahwa MCTS akhirnya konvergen ke minimax (dan akhirnya akan membangun seluruh pohon jika ada cukup memori). Maka harus tahu bahwa langkah itu baik meskipun ada banyak kemungkinan buruk. Tapi saya kira dalam praktiknya ini bukan sesuatu yang bisa diandalkan. Mungkin seseorang dapat memberi tahu saya jika ini adalah evaluasi yang benar di pihak saya.
Terlepas dari skenario khusus ini, saya juga ingin tahu apakah ada skenario lain di mana MCTS akan berkinerja buruk (atau sangat baik).
Jawaban:
Apakah langkah itu ditemukan dan seberapa cepat itu ditemukan tergantung pada beberapa hal. Jika saya mengerti dengan benar, ada urutan banyak gerakan "buruk" yang mengarah ke langkah "kemenangan besar", dan Anda takut bahwa algoritma MCTS tidak akan sampai ke langkah "kemenangan besar" karena akan memilih yang lebih menjanjikan bergerak lebih jauh ke atas pohon. Beberapa hal untuk dipikirkan (baca juga artikel Wikipedia MCTS ):
saat melakukan permainan, Anda dapat melakukan permainan hanya untuk beberapa gerakan lebih lanjut atau turun sampai akhir permainan. Bermain hanya beberapa langkah lebih jauh jelas lebih cepat, tetapi dalam kasus ekstrim yang Anda gambarkan itu bukan pilihan terbaik. Jika Anda tahu tentang keberadaan skenario seperti itu, pastikan untuk memainkan game sampai akhir di playouts.
saat melakukan permainan, Anda dapat memilih gerakan / tindakan Anda baik secara acak atau berdasarkan heuristik sederhana, serakah (cepat) yang disesuaikan dengan masalah Anda. Apakah mungkin ada heuristik rakus yang dirancang untuk menemukan atau memperhitungkan skenario seperti itu untuk game / masalah Anda? Jika ya, terapkan. Ini kemudian disebut "permainan berat". Bandingkan hasilnya dengan playouts menggunakan gerakan acak.
Jika Anda memilih tindakan menggunakan UCT (Batas Keyakinan Tinggi yang diterapkan pada Pohon), maka bagian pertama dari ekspresi bertanggung jawab atas eksploitasi. Bergerak dengan rasio menang rata-rata tinggi lebih disukai. Bagian kedua sesuai dengan eksplorasi. Jika parameter eksplorasi diatur cukup tinggi (uji secara empiris untuk masalah Anda), maka bergerak dengan beberapa simulasi akan lebih disukai. Eksplorasi tinggi akan menjadi cara lain untuk menemukan langkah emas Anda, yang merugikan eksploitasi (baca tentang dilema eksplorasi / eksploitasi).
Jika Anda menggambarkan permainan yang realistis atau skenario masalah, kami mungkin dapat membantu Anda menemukan strategi yang sesuai.
sumber