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

الگوریتم 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