هرس آلفا بتا

هرس آلفا بتا جست‌وجوی یک موتور شطرنج، یعنی برنامه‌ای که حرکت‌ها و پاسخ‌ها را مقایسه می‌کند، سرعت می‌بخشد. می‌توان جست‌وجو را مانند درخت تصور کرد: هر گره یک وضعیت و هر شاخه یک حرکت قانونی است. بدون هرس، برنامه ادامه‌های بسیاری را بررسی می‌کند که در نهایت بی‌اهمیت از آب درمی‌آیند.

این روش هنگام جست‌وجو دو کران را نگه می‌دارد. آلفا بهترین نتیجه‌ای است که یک طرف در مسیر جاری از پیش می‌تواند تضمین کند. بتا کرانی است که گزینه‌ای موجود برای حریف ایجاد می‌کند. وقتی ادامه‌ای آن‌قدر ضعیف باشد که بازیکنی منطقی هرگز آن را انتخاب نکند، جست‌وجوی بیشتر آن نمی‌تواند تصمیم گره بالاتر را تغییر دهد.

شاخه به دلیل یک کران منطقی در درخت متوقف می‌شود، نه فقط چون حرکتی نامطلوب به نظر می‌رسد. در عمق یکسان و با ارزیابی‌های یکسان در مرز جست‌وجو، آلفا بتا همان انتخابی را برمی‌گرداند که جست‌وجوی کامل با فرض بهترین پاسخ‌های هر دو طرف به دست می‌دهد.

میزان صرفه‌جویی به‌شدت به ترتیب حرکت‌ها وابسته است. آزمودن حرکت‌های قوی در ابتدا زودتر کران‌های مفید می‌سازد و اجازه می‌دهد شاخه‌های بیشتری بدون بررسی عمیق‌تر متوقف شوند. تابع ارزیابی که برآوردی عددی به وضعیت می‌دهد، در نقاط پایان جست‌وجوی محدود مقدار فراهم می‌کند.