Apakah pemangkasan alfa-beta mengubah langkah yang akan dipilih minimax?

Tidak. Pemangkasan alfa-beta mengembalikan nilai dan langkah yang sama persis dengan minimax penuh; ini hanya menghindari penjelajahan cabang yang terbukti tidak dapat memengaruhi hasilnya. Manfaatnya adalah kecepatan, dan dengan pengurutan langkah yang baik, ia dapat mencari kira-kira dua kali lebih dalam dalam waktu yang sama.

Mengapa menggunakan pencarian pohon Monte Carlo daripada minimax dalam permainan seperti Go?

Go memiliki faktor percabangan yang sangat besar dan tidak memiliki fungsi evaluasi akurat yang sederhana, sehingga minimax kedalaman tetap tidak efektif. Pencarian pohon Monte Carlo malah memperkirakan kualitas langkah melalui banyak permainan acak dan menumbuhkan pohon secara selektif ke arah garis yang menjanjikan, yang skalanya jauh lebih baik dalam permainan semacam itu.

Pencarian Adversarial dan Permainan Game

Pencarian adversarial adalah studi tentang pengambilan keputusan dalam pengaturan kompetitif, di mana agen harus memilih langkah dalam pohon permainan melawan lawan yang berusaha mencapai hasil yang berlawanan.

Temukan Topik dengan PaperMindSegeraFind papers & topics

Tools & resources

Unduh salindia

Learn & explore

VideoSegera

Definition

Pencarian adversarial menghitung langkah untuk pemain dengan menjelajahi pohon permainan di mana pemain bergantian giliran, menggunakan prinsip minimax (setiap pemain mengoptimalkan dengan asumsi lawan bermain secara optimal) bersama dengan pemangkasan dan evaluasi heuristik untuk mengatasi pohon yang besar.

Scope

Topik ini mencakup pencarian dalam permainan dua pemain, zero-sum, informasi sempurna: aturan keputusan minimax, pemangkasan alfa-beta yang memungkinkan minimax melewati cabang-cabang yang terbukti tidak relevan, fungsi evaluasi dan pencarian terbatas kedalaman untuk permainan yang terlalu besar untuk diselesaikan secara tepat, dan pencarian pohon Monte Carlo untuk permainan dengan faktor percabangan yang sangat besar. Ini membahas bagaimana pohon permainan dimodelkan dan bagaimana batasan komputasi memaksa pemotongan heuristik. Ini tidak mencakup analisis keseimbangan game-teoretis umum dari insentif multi-agen, yang dibahas di bawah sistem multi-agen.

Core questions

Bagaimana aturan minimax menentukan langkah optimal melawan lawan yang optimal?
Bagaimana pemangkasan alfa-beta menghilangkan cabang tanpa memengaruhi nilai minimax?
Bagaimana fungsi evaluasi digunakan untuk memotong pencarian pada kedalaman tetap dalam permainan besar?
Kapan pencarian pohon Monte Carlo lebih disukai daripada minimax terbatas kedalaman?

Key concepts

pohon permainan
nilai minimax
pemangkasan alfa-beta
fungsi evaluasi (heuristik)
pencarian terbatas kedalaman dan efek horizon
permainan informasi sempurna zero-sum
pencarian pohon Monte Carlo
pengurutan langkah

Key theories

Aturan keputusan Minimax: Dalam permainan zero-sum dua pemain, setiap pemain memilih langkah yang memaksimalkan hasil minimum yang dijamin; menyebarkan nilai maks/min ini ke atas pohon permainan menghasilkan langkah optimal di akar.
Pemangkasan alfa-beta: Dengan melacak nilai terbaik yang sudah dijamin untuk pemain yang memaksimalkan dan meminimalkan, pencarian alfa-beta membuktikan bahwa sub-pohon tertentu tidak dapat memengaruhi keputusan akhir dan melewatinya, mengembalikan nilai minimax yang tepat sementara dalam kasus terbaik secara kasar mengkuadratkan kedalaman yang dapat dicapai dalam waktu tertentu.
Pencarian pohon Monte Carlo: Ketika faktor percabangan terlalu besar untuk pencarian menyeluruh, pencarian pohon Monte Carlo membangun pohon asimetris yang dipandu oleh pengguliran acak dan aturan seleksi yang menyeimbangkan eksplorasi dan eksploitasi, sebuah metode yang mengubah permainan komputer dalam permainan seperti Go.

Clinical relevance

Pencarian adversarial menghasilkan sistem AI yang menjadi tonggak sejarah, mulai dari mesin catur yang menggunakan pencarian alfa-beta hingga program Go yang didasarkan pada pencarian pohon Monte Carlo, dan teknik yang sama menginformasikan negosiasi otomatis, permainan keamanan, dan pengaturan apa pun yang dimodelkan sebagai kontes antara pihak-pihak yang mengoptimalkan.

History

Makalah Shannon tahun 1950 membingkai catur komputer sebagai pencarian minimax dengan fungsi evaluasi, dan teorema minimax von Neumann memberikan dasar game-teoretis. Pemangkasan alfa-beta dikembangkan sepanjang tahun 1950-an-60-an dan dianalisis secara ketat oleh Knuth dan Moore (1975). Pencarian pohon Monte Carlo, yang diformalkan pada tahun 2000-an, mendorong lompatan berikutnya dalam kekuatan bermain game, terutama di Go.

Key figures

Claude E. Shannon
John von Neumann
Arthur Samuel
Donald E. Knuth
Ronald W. Moore

Seminal works

shannon1950
knuth1975
browne2012

Frequently asked questions

Apakah pemangkasan alfa-beta mengubah langkah yang akan dipilih minimax?: Tidak. Pemangkasan alfa-beta mengembalikan nilai dan langkah yang sama persis dengan minimax penuh; ini hanya menghindari penjelajahan cabang yang terbukti tidak dapat memengaruhi hasilnya. Manfaatnya adalah kecepatan, dan dengan pengurutan langkah yang baik, ia dapat mencari kira-kira dua kali lebih dalam dalam waktu yang sama.
Mengapa menggunakan pencarian pohon Monte Carlo daripada minimax dalam permainan seperti Go?: Go memiliki faktor percabangan yang sangat besar dan tidak memiliki fungsi evaluasi akurat yang sederhana, sehingga minimax kedalaman tetap tidak efektif. Pencarian pohon Monte Carlo malah memperkirakan kualitas langkah melalui banyak permainan acak dan menumbuhkan pohon secara selektif ke arah garis yang menjanjikan, yang skalanya jauh lebih baik dalam permainan semacam itu.