Pemangkasan alfa-beta

Pemangkasan alfa-beta mempercepat pencarian yang dilakukan mesin catur, yaitu program yang membandingkan langkah dan jawaban. Pencarian dapat dibayangkan sebagai pohon: setiap simpul adalah posisi dan setiap cabang adalah langkah legal. Tanpa pemangkasan, program akan memeriksa banyak lanjutan yang akhirnya terbukti tidak relevan.

Metode ini mempertahankan dua batas selama pencarian. Alfa adalah hasil terbaik yang sudah dapat dijamin satu pihak di sepanjang jalur saat ini. Beta adalah batas yang dibentuk oleh alternatif yang sudah tersedia bagi lawan. Setelah suatu lanjutan begitu buruk sehingga pemain rasional tidak akan memilihnya, pencarian lebih jauh tidak dapat mengubah keputusan pada simpul yang lebih tinggi.

Cabang dihentikan karena batas logis dalam pohon, bukan sekadar karena suatu langkah tampak tidak menarik. Pada kedalaman yang sama dan dengan evaluasi yang sama di batas pencarian, alfa-beta menghasilkan pilihan yang sama dengan pencarian lengkap yang menganggap kedua pihak memainkan jawaban terbaiknya.

Penghematannya sangat bergantung pada urutan langkah. Menguji langkah kuat lebih awal menetapkan batas yang berguna lebih cepat dan memungkinkan lebih banyak cabang berhenti tanpa pemeriksaan lebih dalam. Fungsi evaluasi, yang memberikan perkiraan numerik pada suatu posisi, memasok nilai di titik tempat pencarian terbatas berakhir.