Alfa-beta budaması

Alfa-beta budaması, hamleleri ve yanıtları karşılaştıran bir program olan satranç motorunun yaptığı aramayı hızlandırır. Arama bir ağaç olarak düşünülebilir: her düğüm bir konum, her dal yasal bir hamledir. Budama olmadan program, sonunda ilgisiz olduğu anlaşılacak birçok devam yolunu incelemek zorunda kalır.

Yöntem arama sırasında iki sınır tutar. Alfa, bir tarafın mevcut yol boyunca şimdiden güvence altına alabildiği en iyi sonuçtur. Beta, rakibin elindeki başka bir seçeneğin oluşturduğu sınırdır. Bir devam yolu, akılcı bir oyuncunun onu asla seçmeyeceği kadar kötü olduğunda, daha derine inmek üst düğümdeki kararı değiştiremez.

Dal, bir hamle yalnızca çekici görünmediği için değil, ağaçtaki mantıksal bir sınır nedeniyle durdurulur. Aynı derinlikte ve arama sınırındaki aynı değerlendirmelerle alfa-beta, iki tarafın da en iyi yanıtlarını verdiğini varsayan eksiksiz aramayla aynı seçimi döndürür.

Tasarruf büyük ölçüde hamle sırasına bağlıdır. Güçlü hamleleri erken denemek yararlı sınırları daha çabuk kurar ve daha fazla dalın derinlemesine incelenmeden durmasını sağlar. Bir konuma sayısal tahmin atayan değerlendirme fonksiyonu, sonlu aramanın bittiği noktalarda değerleri sağlar.