هرس آلفا-بتا

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

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

• مقدار $\alpha$: بیشینه حد پایین امتیازی که بین راه‌حل‌ها به آن رسیده‌ایم.
• مقدار $\beta$: کمینه حد بالای امتیازی که بین راه‌حل‌ها به آن رسیده‌ایم.

بنابراین به هنگام پیمایش، جست‌وجو در زیردرخت راسی را ادامه می‌دهیم که شرط زیر را دارا باشد:

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

نحوه‌ی بروزرسانی در طی پیمایش:

• راس‌های کمینه در درخت کمینه‌-بیشینه مقدار $\alpha$ را تغییر می‌دهند.
• راس‌های بیشینه در درخت کمینه-بیشینه مقدار $\beta$ را تغییر می‌دهند.

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

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

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

شبه کد الگوریتم نیز به صورت زیر است:

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

• http://web.cs.ucla.edu/~rosen/161/notes/alphabeta.html
• https://en.wikipedia.org/wiki/Alpha–beta_pruning