====== هرس آلفا-بتا ======

===== تعریف =====

الگوریتم مینیماکس (minimax algorithm) روشی برای یافتن حرکت بهینه در بازی دونفره است. هرس آلفا-بتا (alpha-beta pruning) روشی است برای یافتن جواب بهینه‌ی الگوریتم مینیماکس که از جست‌وجو در برخی فضاهایی که انتخاب نمی‌شوند، جلوگیری می‌کند. به این ترتیب جست‌وجو در درخت کمینه-بیشینه تا عمق مشخصی در زمان کمتری انجام می‌شود.

===== الگوریتم و مثال =====

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

$\alpha \leq N \leq \beta$
که عدد $N$ تخمین فعلی از مقدار آن راس است.

نحوه‌ی بروزرسانی در طی پیمایش:
  * راس‌های کمینه در درخت کمینه‌-بیشینه مقدار $\alpha$ را تغییر می‌دهند.
  * راس‌های بیشینه در درخت کمینه-بیشینه مقدار $\beta$ را تغییر می‌دهند. 

برای نمایش آن می‌توانیم از نمودارهایی مانند عکس زیر استفاده کنیم. در هر مرحله $\alpha$ و $\beta$ مانند زیر هستند:
{{ :آموزش:الگوریتم‌های_تکمیلی:numline1.gif |}}
طبق نحوه‌ی به زور رسانی که توضیح داده شد به مرور $\alpha$ و $\beta$ نزدیک به هم می‌شوند:
{{ :آموزش:الگوریتم‌های_تکمیلی:numline2.gif |}}
در حالت زیر دیگر جست‌وجو را ادامه نمی‌دهیم:
{{ :آموزش:الگوریتم‌های_تکمیلی:numline3.gif |}}

نمونه اجرای الگوریتم را در انیمیشن زیر می‌توان دید:

{{ :آموزش:الگوریتم‌های_تکمیلی:negamax_alphabeta.gif |}}


===== میزان بهبود =====
اگر ضریب انشعاب را $b$ در نظر بگیریم و عمق لازم برای جست و جو را $d$، الگوریتم مینیماکس زمان اجرایی از
$O(b^d)$
 دارد. با استفاده از هرس آلفا-بتا می‌توان اثبات کرد که در حالت جست‌وجوی بهینه تا میزان 
$O(\sqrt{b^d})$
 نیز می‌تواند بهبود پیدا کند.

===== شبه کد =====

شبه کد الگوریتم نیز به صورت زیر است:
<code>
01 function alphabeta(node, depth, α, β, maximizingPlayer)
02      if depth = 0 or node is a terminal node
03          return the heuristic value of node
04      if maximizingPlayer
05          v := -∞
06          for each child of node
07              v := max(v, alphabeta(child, depth – 1, α, β, FALSE))
08              α := max(α, v)
09              if β ≤ α
10                  break (* β cut-off *)
11          return v
12      else
13          v := ∞
14          for each child of node
15              v := min(v, alphabeta(child, depth – 1, α, β, TRUE))
16              β := min(β, v)
17              if β ≤ α
18                  break (* α cut-off *)
19          return v
</code>

===== مراجع =====
  *  [[http://web.cs.ucla.edu/~rosen/161/notes/alphabeta.html]]
  *  [[https://en.wikipedia.org/wiki/Alpha–beta_pruning]]