مینیماکس

مینیماکس

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

در نظریه‌ی بازی های هم‌زمان٬ استراتژی کمینه یک استرتژی مرکب است که قسمتی از حل بازی با مجموعه‌ی صفر میباشد. در بازی های مجموعه‌ی صفر حل کمینه(مینیماکس) مشابه تعادل نش (نام دانشمند) است.

حالت های قضیه ی مینیماکس(کمینه ی بیشینه)

برای هر دو نفر ٬ بازی مجموعه ی صفر با استراتژی های متناهی بسیاری وجود دارد٬یک مقدار V و استراتژی آمیخته برای هر بازیکن وجود دارد که:

الف) برای استراتژی در پیش گرفته شده توسط بازیکن دوم بهترین پرداخت ممکن برای بازیکن ۱ ٬ V است و

ب) برای استراتژی در پیش گرفته شده توسط بازیکن اول بهترین پرداخت ممکن برای بازیکن ۲ ٬-V است.
معادلا استراتژی بازیکن ۱ برای او یک سودمندی (پرداخت)V بدون در نظر گرفتن استراتژی بازیکن دوم تضمین میکند. به طور مشابه بازیکن ۲ می تواند سودمندی –V را برای خودش تضمین کند.

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

این قضیه اولین بار توسط جان ون نیومن در سال ۱۹۲۸ انتشار یافت٬ که از او نقل قول شده است”تا جایی که میبینم هیچ قضیه ای از بازی ها بدون این قضیه نخواهد بود. من فکر میکردم هیچ قضیه ی با ارزشی انتشار نیافته تا زمانی که قضیه مینماکس (کمینه ی بیشینه) اثبات شد!”
برای تعمیم می توانید قضیه ی مینماکس سیون (نام دانشمند) قضیه ی پارتاساراتی را ببینید.هم چنین می توانید مثالی از یک بازی بدون متغیر ببینید. مثال
مثال پیش رو بازی مجموعه ی صفر است که A و B حرکات همزمان انجام میدهند و راه حل مینیماکس را نشان میدهد. فرض کنید هر بازیکن ۳ انتخاب دارد و ماتریس پرداخت برای A در سمت راست نمایش داده شد است.ماتریس پرداخت B را هم مانند ماتریس پرداخت A با علامت معکوس در نظر بگیرید.(برای مثال اگر انتخاب بازیکن ها A1 و B1 باشد٬ B باید ۳ تا به A بپردازد.)سپس انتخاب کمینه ی بیشینه برای A ٬A2 است زیرا در بین بدترین ها بهترین انتخاب این است که باید ۱ بپردازد.در حالی که انتخاب کمینه ی بیشینه برای B٬B2 است زیرا در بهترین حالت که کمترین ضرررا میکند این است که چیزی نپردازد. با این وجود این راه حل پایدار نیست زیرا اگرBبداند که A٬A2 را انتخاب میکند ٬ سپس B ٬B2 را انتخاب میکند تا ۱ سود کند. هم چنین اگر A باور داشته باشد که B٬B2 را انتخاب میکند او هم A1 را انتخاب میکند تا ۳ واحد سود ببرد.اما پس از آن B٬B2 را انتخاب میکند و به همین ترتیب هر دو بازیکن سختی تصمیم گیری را میفهمند.به همین دلیل به استراتژی پایدارتری نیاز است.
بعضی انتخاب ها توسط دیگر انتخاب ها مغلوب می شوند و می توانند حذف شوند: A ٬ A3 را انتخاب نخواهد کرد.زیرا انتخاب هر کدام از A1 و A2 نتیجه ی بهتری خواهد داشت بدون اینکه انتخاب B اهمیت داشته باشد. همچنین B٬B3 را انتخا ب نخواهد کرد زیرا ترکیباتی از B2 و B1 صرف نظر از اینکه A چه انتخابی دارد، نتیجه ی بهتری خواهد داشت.
A با انتخاب A1 با احتمال ۶/۱ و , A2 با احتمال ۶/۵ از پرداخت مورد انتظار بیش از ۳/۱ جلوگیری خواهد کرد.
پرداخت مورد انتظار برای A٬ 3*(1/6)-1*(5/6)=-1/3 خواهد بود برای زمانی که B ٬B1 را انتخاب میکند و -2*(1/6)+0*(5/6)=-1/3 خواهد بود برای زمانی که B ٬ B2 را انتخاب میکند.
مشابها زمانی که B استراتژی B1 را با احتمال ۳/۱ و استراتژی B2 با احتمال ۳/۲ بدون در نظر گرفتن انتخاب A انتخاب میکند٬ میتواند مطمئن باشد که حداقل دارای سود مورد انتظار ۳/۱ خواهد بود.
این استراتژی مرکب پایداری دارد و اثبات شدنی نیست.
بیشینه ی کمینه(ماکسمین)
متعاقباً در نظریه بازی ها کمینه بیشینه(مینیماکس) از بیشینه ی کمینه(ماکسمین) متمایز است.مینیماکس در بازی های مجموعه ی صفر استفاده می شود و مینیمم کردن پرداخت ماکسیمم حریف را نشان میدهد که در بازی های مجموعه ی صفر معادل با مینیمم نمودن ماکزیمم ضرر خودش و ماکسیمم کردن مینیمم سود خودش میباشد.
ماکسیمین عبارتیست که عموماً برای بازی های با مجموعه ی غیر صفر برای توصیف استراتژی که ماکسیمم میکند پرداخت مینیمم خودش را استفاده می شود .در بازی های با مجموع غیر صفر عموماً مشابه مینیمم کردن ماکسیمم سود حریف و مشابه استراتژی تعادل نش نیست .
نظریه ی بازی های ترکیبیاتی
در نظریه ی بازی های ترکیبیاتی الگوریتم مینیماکسی برای راه حل ها ی بازی وجود دارد.
یک نسخه ی ساده از الگوریتم مینیماکس که در زیر توضیح داده شده با بازی هایی شبیه تیک تاک توی(بازی شبیه دوز) سرو کار دارد که هر بازیکن میتواند ببرد ٬ ببازد یا مساوی کند.اگر بازیکن A در یک حرکت بتواند ببرد این بهترین حرکت او خواهد بود.اگر بازیکن B بداند که حرکت او می تواند بازی را به موقعیتی ببرد که بازیکن A را در شرایطی قرار دهد که در یک حرکت ببرد٬ در حالی که با حرکتی دیگر میتواند بازیکن A را در موقعیتی قرار دهد که در بهترین حالت با B مساوی کند برای بازیکن B حرکت دوم بهترین خواهد بود. به آسانی میشه بهترین حرکت را پیدا کرد.
الگوریتم مینیماکس با حرکت عقب گرد از آخر بازی به پیدا کردن بهترین حرکت کمک میکند. در هر مرحله فرض میشه که بازیکن A سعی دارد شانس پیروزی خود را ماکزیمم کند در حالی که در نوبت بعدی بازیکن B سعی دارد تا شانس پیروزی A را مینیمم کند (یعنی بازیکن B شانس پیروزی خودش را ماکسیمم میکند).
الگوریتم مینیماکس با حرکت های جایگزینی
یک الگوریتم مینیماکس یک الگوریتم بازگشتی برای انتخاب حرکت بعدی در یک بازی n نفری است که معمولاً بازی ها دو نفره است. هر مقدار٬ به هر موقعیت یا مکان از بازی وابسته است. این مقدار بوسیله ی تابع ارزیابی موقعیت محاسبه میشود و مطلوبیت رسیدن به آن موقعیت را برای یک بازیکن نشان میدهد. سپس بازیکن مینیمم مقدارهای نتایج موقعیت های احتمالی حاصل ٬از حرکت های پیش روی حریف را ماکزیمم میکند. اگر نوبت حرکت A باشد A به هر حرکت مجاز در آن موقعیت یک مقدار می دهد.
یک روش تخصیص ممکن شامل اختصاص دادن یک برد مشخص برای A مانند ۱ و برای B مانند -۱ می باشد. این منتهی می شود به تئوری بازی های ترکیبیاتی که بوسیله ی جان هورتون کانوی توسعه داده شده. یک جایگزین ی از قانونی استفاده میکند که اگر نتیجه ی یک حرکت یک برد فوری برای A باشد یک مقدار متناهی مثبت را به متغیر جایگزینی اختصاص می دهد و اگر یک برد فوری برای B باشد یک مقدار متناهی منفی را اختصاص میدهد. مقدار A از هر حرکت دیگری٬ مینیمم مقداری که از هر پاسخ محتمل B نتیجه شده میباشد. به این دلیل A را بازیکن حداکثری و B را بازیکن حداقلی مینامند. بنابراین نام این الگوریتم مینیماکس است. در الگوریتم بالا یک مقدار مثبت یا منفی متناهی به هر کدام از موقعیت ها اختصاص داده خواهد شد. به همین خاطر مقدار هر موقعیت مقدار موقعیت پیروزی یا شکست نهایی خواهد بود. اغلب این تنها احتمالی است که در انتهای هر بازی پیچیده مثل شطرنج رخ می دهد. زیرا به صورت محاسباتی ٬ عملی نیست که تا انتهای بازی در پیش بگیریم ٬ مگر به سمت انتهای بازی و به موقعیت های به جای آن مقدار های متناهی داده می شود که تخمین زده می شود که کدام بازیکن میبرد.
این میتواند توسعه داده شود٬ اگر بتوانیم یک تابع ارزیابی اکتشافی نگه داریم که مقدار هایی را به حالت های غیر نهایی بازی بدون در نظر گرفتن دنباله ی کامل احتمالی می دهد. سپس میتوانیم الگوریتم مینیماکس را محدود کنیم تا فقط به یکسری حرکات مشخص پیش رو نگاه کنیم.به این عدد٬ عدد پیش بینی می گویند که با “تا”(پایلز) اندازه گیری می شود.
این الگوریتم میتواند به عنوان جستجوی راس های یک درخت بازی در نظر گرفته شود. ضریب انشعاب مفید برای درخت٬ میانگین بچه های هر راس است(برای مثال میانگین حرکات مجاز در یک موقعیت). تعداد راس هایی که میتوان جستجو کرد معمولابه صورت نمایی با عدد پای افزایش میابد.( اگر حرکت های اجباری یا موقعیت های تکراری ارزیابی شود٬ این کمتر از نمایی است )تعداد راس هایی که برای تحلیل یک بازی جستجو می شود حدوداً ضریب انشعاب است که به سمت قدرت تعداد پای ها افزایش میابد.این غیر عملی است که بازی مانند شطریج را به طور کامل با الگوریتم مینیماکس تحلیل کنیم.
کارایی الگوریتم ساده ی مینیماکس احتمالاً به طور چشمگیری بدون تاثیر روی نتیجه با استفاده از هرس آلفا بتا پیشرفت میکند.روش هرس ابتکاری دیگر هم می تواند استفاده شود اما تضمینی وجو ندارد که همه ی آنها نتیجه ای مشابه جستجوی غیر هرسی (un-pruned) دهد.
یک الگوریتم مینیماکس ساده میتواند به طور واضحی اصلاح شود تا علاوه بر نمره ی مینیماکس٬ کل تنوع اصلی را هم برگرداند.
function minimax(node, depth, maximizingPlayer)

   if depth = 0 or node is a terminal node
       return the heuristic value of node
   if maximizingPlayer
       bestValue := -∞
       for each child of node
           val := minimax(child, depth - 1, FALSE))
           bestValue := max(bestValue, val);
       return bestValue
   else
       bestValue := +∞
       for each child of node
           val := minimax(child, depth - 1, TRUE))
           bestValue := min(bestValue, val);
       return bestValue

(* Initial call for maximizing player *) minimax(origin, depth, TRUE) شبه کد
شبه کدی برای الگوریتم مینیماکس با عمق محدود در زیر آورده شده.
function minimax(node, depth, maximizingPlayer)

   if depth = 0 or node is a terminal node
       return the heuristic value of node
   if maximizingPlayer
       bestValue := -∞
       for each child of node
           val := minimax(child, depth - 1, FALSE))
           bestValue := max(bestValue, val);
       return bestValue
   else
       bestValue := +∞
       for each child of node
           val := minimax(child, depth - 1, TRUE))
           bestValue := min(bestValue, val);
       return bestValue

(* Initial call for maximizing player *) minimax(origin, depth, TRUE)
مینیماکس به طور جداگانه با هر کدام از دو بازیکن در کد برخورد می کند.با توجه به اینکه , مینیماکس به الگوریتم نگاماکس ساده می شود.

مثال

فرض کنید در یک بازی، در هر نوبت، هر بازیکن حداکثر دو گزینه برای حرکت بعدی خود پیش رو داشته باشد. الگوریتم ارائه شده درختی را مانند شکل زیر تولید می‌کند که در آن دایره‌ها نمایانگر حرکت‌های بازیکنی است که الگوریتم را اجرا می‌کند (بازیکن حداکثری) و مربع‌ها نمایانگر حرکت‌های بازیکن مقابل (بازیکن حداقلی) می‌باشد. همان طور که توضیح داده شد به دلیل محدودیت منابع محاسباتی، درخت در هر مرحله فقط 4 حرکت را پیش‌بینی می‌کند.

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

مرحله‌ی بعدی بدست‍‌آوردن مقادیر گره‌های سطر دوم است که در این مرحله هر گره مقداری برابر با ماکسیمم مقادیر فرزندان خود خواهد داشت. به همین صورت این الگوریتم کار خود را ادامه می‌دهد و به صورت یک در میان ماکسیمم مقادیر فرزندان و مینیمم آن‌ها را به گره اختصاص می‌دهد تا این که به ریشه‌ی درخت برسیم که در این مرحله باید ماکسیمم مقادیر فرزندان را به گره اختصاص دهیم (که در شکل با فلش آبی رنگ مشخص شده است) و این همان حرکتی است که بازیکن به منظور به حداقل رساندن انتخاب‌های حداکثری طرف مقابل باید انجام دهد.
مینیماکس و عدم قطعیت
زمانی که بازیکن دیگری وجود نداشته باشد، نظریه‌ی مینیماکس تصمیم گیری را هم در بر می‌گیرد ولی در این حالت دنباله‌ی تصمیم‌گیری‌ها بر اساس حقایق و اتفاقات ناشناخته و نامعلوم می‌باشند. برای مثال تصمیم‌گیری برای اکتشاف یک معدن مستلزم صرف هزینه‌ای است که در صورتی که مواد معدنی موجود نباشند این هزینه هدر رفته است ولی در صورت وجود این مواد این هزینه کاملا به‌صرفه است و موجب سودآوری می‌گردد. یک راه برای رویارویی با این مسئله این است که به آن به عنوان یک بازی با طبیعت نگاه کنیم و با ایده‌ای شبیه به چیزی که در قانون مورفی وجود دارد جلو برویم و از همان تکنیک‌هایی استفاده کنیم که در بازی "دو نفر با مجموع صفر" استفاده می‌کردیم.
مینیماکس در نظریه‌ی تصمیم آماری
در نظریه‌ی تصمیم آماری کلاسیک یک برآورد گر δ داریم که برای تخمین پارامتر θ از آن استفاده می‌کنیم . همچنین تابع ریسک R(θ,δ) را معمولا به عنوان انتگرال تابع شکست در نظر می‌گیریم و محاسبه می‌کنیم در صورتی که شرایط زیر برآورده شود δ̅ را مینیماکس می‌نامیم :
نظریه‌ی تصمیم‌گیری غیراحتمالی
یکی از ویژگی‌های اصلی تصمیم‌گیری مینیماکس غیر احتمالی بودن آن است که در آن بر خلاف تصمیم‌گیری‌هایی که بر اساس مقادیر قابل انتظار و سودهای قابل پیش‌بینی انجام می‌شود، هیچ پیش فرضی راجع به احتمال وقوع پیشامدهای مختلف نداریم و صرفا یک تحلیل از پیشامدهای ممکن را درنظر می‌گیریم و از آن استفاده می‌کنیم بنابراین در این روش در مقایسه با سایر تکنیک‌های تصمیم گیری می‌توانیم راحت‌تر فرضیاتمان را تغییر دهیم.
کاربردهای زیادی از این روش غیر احتمالی وجود دارد که از جمله‌ی مهم‌ترین آن‍ها می‌توان به تاسف مینیماکس و نظریه‌ی تصمیم گیری شکاف اطلاعات اشاره کرد.
علاوه بر این مینیماکس تنها به اندازه‌گیری‌های ترتیبی (که در آن نتایج بتوانند با یکدیگر مقایسه شوند) احتیاج دارد و در آن هیچ احتیاجی به اندازه‌گیری‌های فاصله‌ای نیست (که در آن نتایج شامل این هستند که این روش تا چه میزان بهتر یا بدتر از روش‌های دیگر است) و در نهایت یک داده‌‌ی ترتیبی را به عنوان خروجی می‌دهد.
نتیجه‌ای که از یک تحلیل مینیماکس به دست می‌آید به ما می‌گوید که آیا استراتژی مورد بحث مینیماکس است یا خیر، بدترین حالت و نتیجه‌ی آن چیست و این که در بین بدترین نتایج کدام یک نسبت به بقیه کمتر بد است که در مقایسه با تحلیل‌هایی که بر اساس مقادیر قابل انتظار انجام می‌شود که در آن‎ها نتیجه به این صورت است که به ما می‌گوید که استراتژی مورد بحث به E(x)=n منجر میشود روش مینیماکس شفاف‌تر است و از آن می‌توانیم برای داده‌های ترتیبی استفاده کنیم.