Bagaimana cara memilih algoritma terbaik untuk permainan papan seperti catur?
Sejauh ini, saya hanya mempertimbangkan tiga algoritma, yaitu, minimax, pemangkasan alpha-beta, dan pencarian pohon Monte Carlo (MCTS). Rupanya, pemangkasan alpha-beta dan MCTS adalah ekstensi dari algoritma minimax dasar.
tl; dr:
Tidak satu pun dari algoritma ini yang praktis untuk pekerjaan modern, tetapi mereka adalah tempat yang baik untuk memulai secara pedagogis.
Anda harus selalu lebih suka menggunakan pemangkasan Alpha-Beta daripada pencarian minimal.
Anda harus memilih untuk menggunakan beberapa bentuk pencarian dipandu heuristik jika Anda dapat menemukan heuristik yang berguna. Datang dengan heuristik yang berguna biasanya membutuhkan banyak pengetahuan domain.
Anda harus memilih untuk menggunakan pencarian Monte Carlo Tree ketika Anda tidak memiliki heuristik yang baik, ketika sumber daya komputasi terbatas, dan ketika kesalahan tidak akan melebihi konsekuensi dunia nyata.
Keterangan lebih lanjut:
Dalam pencarian minimum, kami tidak berusaha menjadi sangat pintar. Kami hanya menggunakan pendekatan pemrograman dinamis standar. Sangat mudah untuk mengetahui nilai pergerakan perbedaan jika kita mendekati akhir permainan (karena permainan akan berakhir pada langkah berikutnya, kita tidak harus melihat jauh ke depan). Demikian pula, jika kita tahu apa yang akan dilakukan lawan kita di langkah terakhir permainan, mudah untuk mengetahui apa yang harus kita lakukan di langkah terakhir kedua. Secara efektif kita dapat memperlakukan langkah terakhir kedua sebagai langkah terakhir dari permainan yang lebih pendek. Kami kemudian dapat mengulangi proses ini. Menggunakan pendekatan ini pasti untuk mengungkap strategi terbaik dalam permainan bentuk luas standar, tetapi akan mengharuskan kita untuk mempertimbangkan setiap langkah yang mungkin, yang tidak mungkin dilakukan untuk semua kecuali permainan yang paling sederhana.
Pemangkasan Alpha-Beta adalah peningkatan ketat pada pencarian Minimax. Itu memanfaatkan fakta bahwa beberapa gerakan jelas lebih buruk daripada yang lain. Misalnya, dalam catur, saya tidak perlu mempertimbangkan langkah apa pun yang akan memberi Anda kesempatan untuk menempatkan saya dalam skakmat, bahkan jika Anda dapat melakukan hal-hal lain dari posisi itu. Begitu saya melihat bahwa langkah mungkin menyebabkan kerugian, saya tidak akan repot memikirkan apa lagi yang mungkin terjadi dari titik itu. Saya akan melihat hal-hal lain. Algoritma ini juga pasti menghasilkan hasil yang benar, dan lebih cepat, tetapi masih harus mempertimbangkan sebagian besar gerakan dalam praktik.
Ada dua cara umum yang bisa Anda gunakan untuk mengatasi biaya komputasi ekstrem untuk menyelesaikan jenis gim ini dengan tepat:
Gunakan Heuristik (pencarian A * adalah algoritma yang biasa untuk tujuan pedagogis, tetapi pencarian Quiescence adalah ide yang sama di 2 permainan pemain). Ini hanya fungsi yang memberikan perkiraan nilai kondisi permainan. Alih-alih mempertimbangkan semua gerakan dalam permainan, Anda bisa mempertimbangkan bergerak ke jarak tertentu ke depan, dan kemudian menggunakan nilai heuristik untuk menilai nilai negara yang Anda capai. Jika heuristik Anda konsisten (pada dasarnya: jika selalu melebih - lebihkan kualitas negara), maka ini masih akan menghasilkan jawaban yang benar, tetapi dengan percepatan besar dalam praktik.
Gunakan Rollouts (seperti Pencarian Pohon Monte Carlo). Pada dasarnya, alih-alih mempertimbangkan setiap gerakan, jalankan beberapa ribu game simulasi antara pemain yang bertindak secara acak (ini lebih cepat daripada mempertimbangkan semua gerakan yang mungkin). Tetapkan nilai untuk negara yang setara dengan tingkat kemenangan rata-rata game mulai dari itu. Ini mungkin tidak menghasilkan jawaban yang benar, tetapi dalam beberapa jenis permainan, itu berkinerja andal. Ini sering digunakan sebagai perpanjangan dari teknik yang lebih tepat, daripada digunakan sendiri.
Dengan konteks ini, saya akan merekomendasikan memulai dengan Minimax . Dari ketiga algoritma, Minimax adalah yang paling mudah dipahami.
Alpha-Beta , seperti yang disebutkan orang lain dalam jawaban lain, adalah peningkatan ketat di atas Minimax. Minimax pada dasarnya adalah bagian dari implementasi Alpha-Beta, dan pemahaman yang baik tentang Alpha-Beta memerlukan dimulai dengan pemahaman yang baik tentang Minimax pula. Jika Anda memiliki waktu yang tersisa setelah memahami dan mengimplementasikan Minimax, saya akan merekomendasikan pindah ke Alpha-Beta sesudahnya dan membangunnya di atas Minimax. Memulai dengan Alpha-Beta jika Anda belum mengerti Minimax tidak terlalu masuk akal.
Pencarian Pohon Monte-Carlo mungkin sedikit lebih maju dan lebih rumit untuk benar-benar, sangat memahami. Dalam dekade terakhir atau lebih, MCTS benar-benar telah tumbuh menjadi jauh lebih populer daripada dua lainnya, jadi dari sudut pandang itu memahami MCTS mungkin lebih "berguna".
Koneksi antara Minimax dan MCTS kurang langsung / jelas daripada koneksi antara Minimax dan Alpha-Beta, tetapi masih ada koneksi setidaknya pada tingkat konseptual. Saya berpendapat bahwa memiliki pemahaman yang baik tentang Minimax pertama masih bermanfaat sebelum menyelam ke MCTS ; khususnya, memahami Minimax dan kelemahannya / titik lemahnya dapat memberikan konteks yang bermanfaat / membantu Anda memahami mengapa MCTS menjadi "perlu" / populer.
Untuk menyimpulkan, menurut pendapat saya:
sumber
Jika Anda harus memilih antara pemangkasan Minimax dan Alpha-Beta, Anda harus memilih Alpha-beta. Ini lebih efisien dan cepat karena dapat memangkas sebagian besar pohon eksplorasi Anda. Tetapi Anda perlu memesan tindakan dari yang terbaik ke yang terburuk tergantung pada sudut pandang maksimal atau minimum, sehingga algoritme dapat dengan cepat disadari jika diperlukan eksplorasi.
sumber