الگوریتم هرس کردن آلفا - بتا
الگوریتم هرس کردن آلفا - بتا
مشکل جست وجوی minimax این است که تعداد حالتهای بازی که باید بررسی شوند، برحسب تعداد حرکتها، یک رابطه ی نمایی است. متاسفانه این رابطه نمایی را نمیتوان حذف کرد ولی میتوان آنرا به نصف تقلیل داد. علتش این است که محاسبه تصمیم minimax صحیح بدون دیدن همه گره های درخت بازی امکانپذیر است. یعنی با استفاده از مفهوم هرس کردن میتوان بخش های بزرگی از درخت را از بین برد. با استفاده از تکنیکی به نام هرس کردن آلفا – بتا میتوان این کار را انجام داد. وقتی این تکنیک به درخت minimax اعمال میشود، همان حرکتی را برمیگرداند که minimax برخواهد گرداند، اما انشعاب هایی که در تصمیم نهایی تاثیر ندارند، حذف خواهند شد.
هرس کردن آلفا – بتا که یکی از استراتژی های جستوجوی خصمانه است، میتواند به هر درختی با هر عمق اعمال شود. بطور کلی میتوان کل زیردرخت را به جای برگ ها هرس کرد. اصل کلی این است : گره n را در جایی از درخت در نظر بگیرید بطوریکه بازیکن بتواند به آن گره برود. اگر بازیکن، در گره والد n یا هر نقطه ای در سطح بالاتر، انتخاب بهتری مثل m دارد، آنگاه در بازی واقعی هرگز به n نخواهد رسید. لذا وقتی اطلاعات کافی در مورد n کسب کردیم (با بررسی بعضی از فرزندان آن) تا به این نتیجه برسیم، میتوانیم آنرا هرس کنیم.
به یاد داشته باشید که جست وجوی minimax عمقی است، لذا در هر زمان فقط باید گره های موجود در یک مسیر درخت را در نظر بگیریم. نام هرس کردن آلفا – بتا از دو پارامتر زیر به دست آمده که کران مقادیر ذخیره شده در تمام طول مسیر هستند:
α = مقدار بهترین (یعنی بالاترین) انتخابی است که تاکنون در هر نقطه انتخاب در مسیر مربوط به MAX پیدا شده است.
β = مقدار بهترین (یعنی پایین ترین) انتخابی است که تاکنون در هر نقطه انتخاب در مسیر مربوط به MIN پیدا شده است.
جست وجوی آلفا – بتا ، مقادیر α و β را با هرس کردن انشعاب های باقیمانده در یک گره، به هنگام سازی میکند. این کار به محض اینکه مشخص شد مقدار گره فعلی بدتر از مقدار α یا β مربوط به MAX یا MIN است، انجام میگیرد.
اثر بخشی هرس کردن آلفا – بتا به ترتیب بررسی حالت ها بستگی دارد پس بهتر است ابتدا پسین هایی بررسی شوند که ممکن است بهترین باشند. اگر فرض کنیم این کار امکانپذیر باشد، نتیجه میگیریم که در آلفا – بتا فقط O(bm/2) گره باید بررسی شوند تا بهترین انتخاب صورت گیرد در حالیکه در minimax، این تعداد O(bm) بوده است.
با اضافه کردن طرح های تعیین حرکتها بصورت پویا، مثل طرح هایی که سعی میکنند اول حرکتهایی را انجام دهند که در گذشته بهترین بودند، ضریب انشعاب به مقداری که در محاسبات نظری به دست می آید، نزدیک میشود. حرکت گذشته، میتوانست حرکت قبلی باشد یا میتوانست از اکتشاف قبلی مربوط به حرکت فعلی تعیین شود.
الگوریتم جست وجوی آلفا – بتا
function ALPHA – BETA - SEARCH (state) returns an action
v <-- MAX –VALUE (state , -∞ , +∞)
return the action in ACTION(state) with value v
function MAX – VALUE (state, α, β) returns a utility value
if THERMINAL – TEST (state) then return UTILITY (state)
v <-- - ∞
for each a in ACTIONS (state) do
v <-- MAX (v , MIN- VALUE (RESULT (s , a) , α, β ) )
if v >= β then return v
α <-- MAX (α , v)
return v
function MIN – VALUE (state, α, β) returns a utility value
if THERMINAL – TEST (state) then return UTILITY (state)
v <-- + ∞
for each a in ACTIONS (state) do
v <-- MIN (v , MAX- VALUE (RESULT (s , a) , α, β ) )
if v <= α then return v
β <-- MAX (β , v)
return v
