AlgoVerse

مینیمکس با هرس آلفا–بتا

بهترین حرکت در درخت بازی: بازیکن‌ها به نوبت بیشینه و کمینه می‌کنند و شاخه‌هایی که روی نتیجه اثری ندارند هرس می‌شوند.

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

ادامه‌ی توضیح ↓
ورودی:
n=8خروجی PDF

هشت برگ در سه سطح (بیشینه، کمینه، بیشینه)؛ دو بار هرس رخ می‌دهد و فقط ۵ برگ دیده می‌شود. جواب ۵ است.

  1. INF = float("inf")
  4. def alpha_beta(leaves):
  5. return search(leaves, 0, len(leaves) - 1, True, -INF, INF)
  8. def search(leaves, lo, hi, maximizing, alpha, beta):
  9. if lo == hi:
  10. return leaves[lo]
  11. mid = (lo + hi) // 2
  12. if maximizing:
  13. best = search(leaves, lo, mid, False, alpha, beta)
  14. alpha = max(alpha, best)
  15. if alpha >= beta:
  16. return best
  17. best = max(best, search(leaves, mid + 1, hi, False, alpha, beta))
  18. return best
  19. best = search(leaves, lo, mid, True, alpha, beta)
  20. beta = min(beta, best)
  21. if alpha >= beta:
  22. return best
  23. best = min(best, search(leaves, mid + 1, hi, True, alpha, beta))
  24. return best

ناوردا: α بهترین مقداری است که بیشینه‌کننده تا اینجا تضمین کرده و β بهترین مقدار کمینه‌کننده؛ اگر α ≥ β، این شاخه هرگز انتخاب نمی‌شود.

شروع اجرا

30516293142506-17

درخت فراخوانی‌های بازگشتی

نارنجی پر = فراخوانی در حال اجرا · حاشیه‌ی نارنجی = هنوز روی پشته · خاکستری = تمام شده

متغیرهای محلی

نارنجی = در همین گام عوض شد

leaves list

3569120-1

Call stack

  1. alpha_beta()خط 4
گام ۱ از ۶۹
خط سیاه = max_update, min_update · خط نارنجی = گام کلیدیleaf: 0/5 · max_update: 0/4 · max_done: 0/3 · min_update: 0/2 · prune: 0/2 · min_done: 0/1
    توضیح

    ایده

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

    اینجا آرایه برگ‌های یک درخت دودویی کامل است: دو حرکت در هر نوبت و نوبت اول با بیشینه‌کننده.

    هرس آلفا–بتا

    • α: امتیازی که بیشینه‌کننده تا اینجا تضمین کرده.
    • β: امتیازی که کمینه‌کننده تا اینجا تضمین کرده.

    اگر جایی α ≥ β شد، حریف هرگز اجازه نمی‌دهد بازی به این شاخه برسد؛ پس بقیه‌ی فرزندان هرس می‌شوند. جواب دقیقاً همان مینیمکس است، فقط سریع‌تر.

    ترتیب حرکت‌ها

    با ترتیب خوب (بهترین حرکت اول) تعداد برگ‌هایی که دیده می‌شوند تقریباً به n^¾ (برای درخت دودویی) کم می‌شود؛ با ترتیب بد هیچ صرفه‌جویی نیست.

    در trace به چه چیزی نگاه کنی

    • درخت فراخوانی‌ها همان درخت بازی است؛ بازه‌ی lo..hi زیر آرایه زیردرخت فعلی است.
    • «ترتیب خوش‌شانس» و «ترتیب بدشانس» را از نظر تعداد برگ‌های دیده‌شده مقایسه کن.