Beberapa keraguan tentang penerapan pembelajaran penguatan untuk permainan seperti catur

9

Saya menemukan permainan papan catur. Saya membangun mesin sehingga bisa bermain secara otonom. Mesin pada dasarnya adalah pohon keputusan. Ini disusun oleh:

  1. Fungsi pencarian yang di setiap node menemukan semua langkah hukum yang mungkin
  2. Fungsi evaluasi yang memberikan nilai numerik ke posisi dewan (positif berarti pemain pertama unggul, negatif berarti pemain kedua menang sebagai gantinya)
  3. Algoritma pemangkasan negamax alfabet

Masalah utama tentang mesin ini adalah optmisasi fungsi evaluasi sangat rumit. Saya tidak tahu faktor mana yang harus dipertimbangkan dan bobot yang harus dimasukkan. Satu-satunya cara saya melihat untuk meningkatkan mesin adalah untuk mengulang game mencoba setiap kali kombinasi faktor dan bobot yang berbeda. Namun, ini secara komputasional tampaknya merupakan hal yang sangat sulit (Dapatkah saya melakukan backpropagate tanpa menggunakan deeplearning?).

Saya ingin menggunakan pembelajaran penguatan untuk membuat mesin meningkat dengan bermain melawan dirinya sendiri. Saya sudah membaca tentang topik, tetapi saya masih cukup bingung.

Apa hadiah lain yang ada dalam permainan bagian hasil win-or-loss (1 atau 0)? Jika saya menggunakan hadiah lain, seperti output dari fungsi evaluasi di setiap belokan, bagaimana saya bisa menerapkannya? Bagaimana cara memodifikasi fungsi evaluasi untuk memberikan iterasi penghargaan yang lebih baik setelah iterasi?

Pigna
sumber

Jawaban:

6

Saya ingin menggunakan pembelajaran penguatan untuk membuat mesin meningkat dengan bermain melawan dirinya sendiri. Saya telah membaca tentang topik ini tetapi saya masih cukup bingung.

Diperingatkan: Pembelajaran penguatan adalah subjek yang kompleks dan besar. Meskipun mungkin Anda harus mengambil jalan memutar dari bot bermain game, Anda mungkin ingin mempelajari dasar-dasar RL. Tempat yang baik untuk memulai adalah Sutton & Barto Reinforcement Learning: An Introduction

Apa hadiah lain yang ada dalam permainan bagian hasil win-or-loss (1 atau 0)?

Tergantung pada gim Anda, biasanya itu masalahnya. Sebenarnya untuk permainan menang / imbang / kalah seperti catur maka hadiah dari setiap aksi adalah 0 kecuali untuk menang (+1) atau kalah (-1) pada akhirnya. Dalam permainan zero-sum maka ini selaras dengan minimax, pemangkasan alfabet, dll.

Pembelajaran Penguatan dimaksudkan untuk mengatasi lingkungan dengan imbalan yang tertunda. Menambahkan hadiah "pembantu" untuk non-tujuan sementara biasanya tidak produktif.

Jika saya menggunakan hadiah lain, seperti output dari fungsi evaluasi di setiap belokan, bagaimana saya bisa menerapkannya?

Biasanya tidak. Apa yang menerapkan RL bermain sendiri akan lakukan adalah mempelajari fungsi pengembalian (kadang-kadang disebut utilitas ) yang memprediksi ekspektasi total + 1/0 / -1 hadiah Anda di akhir permainan. Anda akan menggunakan ini sebagai pengganti heuristik Anda saat ini untuk pencarian minimax. Atau, berpotensi Anda akan menyesuaikan fungsi heuristik Anda saat ini untuk menghasilkan dalam kisaran yang sama dan menggunakan RL untuk mengoptimalkan bobotnya untuk membuat perkiraan terbaik untuk fungsi pemutaran kembali yang benar optimal (yang mungkin terlalu rumit untuk menghitung dengan tepat).

Bagaimana cara memodifikasi fungsi evaluasi untuk memberikan iterasi penghargaan yang lebih baik setelah iterasi?

Itulah yang coba dilakukan oleh berbagai pendekatan RL, ada beragam pemecah yang berbeda. Tidak ada cara singkat untuk menjelaskannya. Anda bisa mulai dengan metode sederhana seperti Q-Learning . Q-Learning mempelajari perkiraan Q (s, a) (disebut nilai tindakan) yang merupakan pengembalian yang diharapkan ketika dalam keadaan dan mengambil tindakan a, dan setelah itu mengikuti kebijakan yang optimal. Itu membuat tebakan sewenang-wenang untuk memulai dan memolesnya lebih dekat ke nilai sebenarnya dengan setiap langkah yang dibuat dalam lingkungan belajar. Pelajar-Q tabel sederhana melakukan penyempurnaan ini hanya dengan menyimpan tabel besar semua negara dan tindakan dengan estimasi terbaik sejauh ini dari nilai sebenarnya, dan rata-rata dalam setiap estimasi baru seperti yang dialami.

Dimungkinkan juga untuk menggabungkan metode RL untuk heuristik dengan pencarian minimal di masa depan - itulah yang dilakukan AlphaGo asli, dan apa yang dilakukan AlphaGo Zero selama pelatihan. Ini adalah pendekatan yang kuat karena pencarian minimax akan bekerja untuk memeriksa ulang heuristik yang dihasilkan RL. Meskipun untuk gim yang cukup sederhana, RL dapat mempelajari heuristik yang sempurna dan Anda hanya perlu pencarian lokal (seperti apa langkah selanjutnya).

Kecuali gim Anda sangat sederhana (semua kondisi yang memungkinkan akan sesuai dengan memori), Anda akan memerlukan semacam penduga fungsi di dalam algoritma RL. Jaringan saraf adalah pilihan standar. Memiliki sesuatu untuk bagian itu tidak dapat dihindari - meskipun pilihan lain yang baik adalah mendefinisikan banyak fitur proxy (yang dapat Anda gunakan untuk membangun heuristik dengan tangan) dan menggunakan pendekatan linier - hanya jumlah dari semua fitur. Ini dapat bekerja dengan cukup baik, dan telah digunakan misalnya dalam checker (draft) pemain yang dilatih menggunakan RL.

Bahkan, asalkan fungsi heuristik Anda sendiri tidak terlalu luar biasa, Anda mungkin dapat memperlakukannya seperti aproksimasi linear dan menggunakan RL untuk mempelajari bobot terbaik untuk itu.

Neil Slater
sumber
"Pembelajaran Penguatan dimaksudkan untuk mengatasi lingkungan dengan hadiah yang tertunda. Menambahkan hadiah" pembantu "untuk non-tujuan sementara biasanya kontraproduktif." Saya ingin mencatat bahwa ada makalah yang mencoba untuk memecahkan masalah imbalan yang jarang dengan memperkenalkan tujuan perantara " Pemutaran Pengalaman Hindsight ".
nbro
1
@nbro: Ada banyak upaya untuk menyelesaikan hadiah yang jarang, ini adalah pertanyaan terbuka besar di RL, salah satu cara untuk meningkatkan tantangan masalah adalah dengan membuat hadiah menjadi lebih jarang. Jejak kelayakan adalah upaya lain, Hierarchical RL adalah bidang lain yang menjanjikan. . . Saya rasa saya tidak ingin menambahkan teknik-teknik ini ke jawaban di sini, karena ini lebih tentang kelayakan untuk masalah OP dan intro untuk subjek
Neil Slater