الگوریتم ام‌تی‌دی-اف

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

الگوریتم MTD-F

MTD-F که در واقع خلاصه شده ی (MTD(f,n می باشد (درایور تست با حافظه ی اضافی با گره n و مقدار f) الگوریتمی برای جستجوی minimax است که میتوان به عنوان جایگزینی برای الگوریتم هرس آلفا و بتا از آن استفاده کرد.

جستجو های zero-window[ویرایش]

(MTD(f به طور کارآمد و موثری، جستجو هایی که فقط zero-window و آلفا و بتا باشند را با کران خوبی انجام میدهد (با بتای متغیر). در نگااسکاتآلفا بتا با یک فضای جستجو نمایان می شود. در AlphaBeta(root, -INFINITY, +INFINITY, depth) مقدار خروجی بین آلفا و بتا می باشد. در MTD(f)، آلفا بتا برای یافتم کران بالا یا کران پایین برای مقدار بیشینه، اشتباه می کند. zero-window برای بیشتر بودن راه های میان بر و مقدار های بازگشتی کمتر، استفاده می شود. برای یافتم مقدار بیشینه، MTD(f)، آلفا بتا را چندین بار صدا میزند تا در نهایت مقدار دقیق و نهایی را پیدا کند. جدول تقدم و تاخر جستجو های قدیمی را بر می گرداند و همچنین جستجو های جدید را برای کاهش رجوع مجدد به جستجو ذخیره می کند.

Pseudocode[ویرایش]

function MTDF(root, f, d)
      g := f
      upperBound := +∞
      lowerBound := -∞
      while lowerBound <upperBound
         if g = lowerBound then 
              β := g+1 
         else 
              β := g
         g := AlphaBetaWithMemory(root, β-1, β, d)
         if g <β the 
              upperBound := g 
          else
              lowerBound := g
     return g

کارکرد[ویرایش]

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

منابع[ویرایش]

  • [۱] توضیح الگوریتم MTD-f

پیوند به بیرون[ویرایش]

  • [۲]الگوریتم کمینه بیشینه بهتر از نگا اسکات
  • [۳] توضیح الگوریتم MTD-f