الگوریتم min max
الگوریتم min max
در مسئله ی جست وجوی عادی، جواب بهینه، دنباله ای از فعالیت هاست که منجر به حالت هدف میشوند. در جست وجوی خصمانه، MIN چیزی برای گفتن درباره حالت هدف دارد. بنابراین، MAX باید یک استراتژی اقتضایی را پیدا کند که حرکت MAX را در حالت شروع مشخص می کند، سپس حرکت های MAX در این حالت ها با توجه به پاسخ های MIN مشخص میشود، و سپس MAX به حالتهایی میرود که با پاسخ MIN به آن حرکتها بستگی دارد، و این روند ادامه می یابد. این روند دقیقا مثل الگوریتم AND – OR است، بطوریکه MAX در نقش OR و MIN در نقش AND بازی میکند. به عبارت دقیقتر استراتژی بهینه نتایجی تولید میکند که حداقل به خوبی استراتژی های دیگر در زمانی است که با یک حریف بدون اشتباه بازی میکند.
تعریف بازی بهینه برای MAX فرض میکند که MIN نیز بطور بهینه بازی میکند، یعنی نتیجه بدترین حالت برای MAX را ماکزیمم میکند. اگر MIN بطور بهینه عمل نکند، به آسانی میتوان نشان داد که MAX هنوز بهتر بازی خواهد کرد.
الگوریتم minimax تصمیم minimax را از حالت فعلی محاسبه میکند. این الگوریتم مقادیر minimax مربوط به هر حالت پسین را بطور بازگشتی با پیاده سازی مستقیم معادلات تعریف شده، محاسبه میکند. این محاسبات بازگشتی به طرف پایین تا برگهای درخت پیش میرود و سپس در برگشت از حالت بازگشتی، مقادیر minimax هر گره را اختصاص میدهد.
الگوریتم minimax اکتشاف عمقی کاملی را روی درخت بازی انجام میدهد. اگر حداکثر عمق درخت m باشد و در هر نقطه b حرکت معتبر وجود داشته باشد، آنگاه پیچیدگی زمانی الگوریتم minimax برابر است با O(bm) . برای الگوریتمی که تمام فعالیت ها را همزمان تولید میکند، پیچیدگی فضا (حافظه) برابر با O(bm)، یا برای الگوریتمی که هر بار یک فعالیت را تولید میکند، برابر با O(m) است. البته برای بازی های واقعی هزینه زمان کاملا غیرعملی است. اما این الگوریتم به عنوان مبنایی برای تحلیل ریاضی بازی ها و برای بسیاری از الگوریتم های عملی است.
شبه کد الگوریتم minimax
function MINIMAX – DECISION (state) returns an action
return arg maxa E ACTIONS (s) MIN – VALUE (RESULT (state , a) )
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) ) )
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 , MIN- VALUE (RESULT (s , a) ) )
return v
چگونه میتوان نشان داد اگر MIN بطور بهینه عمل نکند MAX هنوز بهتر بازی خواهد کرد؟؟