MatlabTips

🔵قسمت دو: از فکر بکر به مدل های انتشار (diffusion models)🔵

ددونالد کنوث (دانشمند مشهور علوم کامپیوتر) روشی بهینه برای حل «بازی حدس کد» ارائه کرده است که بر ایدۀ «مینیمم کردن بدترین حالت» (Minimax) استوار است. در این روش:

تعریف مسئله:
ما n رنگ و d جایگاه داریم و کد مخفی یک رشتۀ d-تایی از این رنگ‌ها است. پس در مجموع n^d کد ممکن وجود دارد.

مجموعه S تمام گزینه‌های فعلیِ «هنوز ممکن» را نشان می‌دهد. در ابتدا S برابر با همۀ کدهای ممکن (Ω) است.

روند کلی:
یک «حدس» (g) هم یک رشتۀ d-تایی از رنگ‌هاست. پس از هر حدس، امتیازی دو بخشی دریافت می‌کنید:
A: تعداد رنگ‌هایی که دقیقاً در جای درست قرار گرفته‌اند.
B: تعداد رنگ‌های درستی که در جایگاه نادرست واقع شده‌اند.

به‌روزرسانی مجموعه گزینه‌ها:

با توجه به امتیازی که برای حدس g گرفته می‌شود، می‌توانیم تمام کدهایی از S را که چنین امتیازی نمی‌دهند حذف کنیم تا تعداد کدهای ممکن کمتر شود.

گزینش حدس بهینه:

در هر مرحله، ما می‌خواهیم حدسی بزنیم که در بدترین حالت کمترین تعداد کدِ ممکن را برای مرحلۀ بعد باقی بگذارد.

بنابراین، برای هر حدس کاندید g درΩ، نگاه می‌کنیم اگر آن را بزنیم، در بدترین حالت چقدر از کدهای S ممکن است باقی بماند. بعد حدسی را انتخاب می‌کنیم که این «بیشترین باقی‌مانده» را تا حد ممکن کوچک کند (مینیمم کردن بدترین حالت).
خلاصه:
این الگوریتم در هر مرحله حدسی می‌زند که بدترین حالت پس از دریافت امتیاز را بهتر (کوچک‌تر) کند. به این ترتیب، بعد از هر حدس، مجموعه کدهای ممکن S تا جای ممکن کوچک می‌شود و در نهایت با کمترین تعداد حدس‌های ممکن به جواب می‌رسیم.

(در این پروژه ی پایتون این بازی ساده را همراه با یک اکتور بسیار ساده که می تواند بازی را در ۵ قدم یا کمتر ببرد پیاده سازی کرده ام. این تمرین خوبی برای دیدن این است که یک «بازی گر» دیجیتال چگونه ممکن است کار کند)

روش مینیمم کردن بدترین حالت یک اسراتژی کلی برای بازی کردن در هر بازی ای رقابتی هم هست. به طور مثال در شطرنج شما فقط به حرکات خود فکر نمیکنید بلکه به اینکه هر مهره ای که حرکت دهید چقدر برایتان خوب یا بد است هم فکر میکنید. برای اینکه می توان گفت یا حداکثر امتیاز طرف مقابل را کمینه (minimax) یا کمترین ضرر طرف مقابل را بیشینه (maxmin). همین روش بسیار ساده در چارچوب شطرنج باز های کلاسیک مانند دیپ بلو (deep blue) در سال ۱۹۸۴ گری کاسپاروف قهرمان شطرنج جهان را شکست دهد. البته دیپ بلو به جای فقط یک قدم چندین قدم این کار را کرد. به این ترتیب که درخت جستجوی مینیمکس عمیقی ساخت و با آن تعدادی زیادی حالت را بررسی کرده و با یک حرکت برگشتی مشخص میکرد چه حرکتی بهترین است!

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

«کمینه کردن بدترین حالت» یا به طور خلاصه «مینیمکس» یک اپراتور است که فضای امتیاز ها را ارزیابی و به شما یک «حدس» می دهد! «حدس» منجر به یک عمل (action) می شود که بهترین عمل است! به این ترتیب می توان رابطه حدس و نظریه بازی ها را هم دید. در قسمت بعد میبینیم که همین عملگر ساده کلید حل بسیاری از مسايل هوش مصنوعی و بخصوص مدل های انتشار (دیفیوژن) است.

GitHub

GitHub - roholazandie/mastermind

Contribute to roholazandie/mastermind development by creating an account on GitHub.

www.tgoop.com/matlabtips/1695

255 viewsedited  Apr 7 at 03:29

🔵قسمت دو: از فکر بکر به مدل های انتشار (diffusion models)🔵

ددونالد کنوث (دانشمند مشهور علوم کامپیوتر) روشی بهینه برای حل «بازی حدس کد» ارائه کرده است که بر ایدۀ «مینیمم کردن بدترین حالت» (Minimax) استوار است. در این روش:

تعریف مسئله:
ما n رنگ و d جایگاه داریم و کد مخفی یک رشتۀ d-تایی از این رنگ‌ها است. پس در مجموع n^d کد ممکن وجود دارد.

مجموعه S تمام گزینه‌های فعلیِ «هنوز ممکن» را نشان می‌دهد. در ابتدا S برابر با همۀ کدهای ممکن (Ω) است.

روند کلی:
یک «حدس» (g) هم یک رشتۀ d-تایی از رنگ‌هاست. پس از هر حدس، امتیازی دو بخشی دریافت می‌کنید:
A: تعداد رنگ‌هایی که دقیقاً در جای درست قرار گرفته‌اند.
B: تعداد رنگ‌های درستی که در جایگاه نادرست واقع شده‌اند.

به‌روزرسانی مجموعه گزینه‌ها:

با توجه به امتیازی که برای حدس g گرفته می‌شود، می‌توانیم تمام کدهایی از S را که چنین امتیازی نمی‌دهند حذف کنیم تا تعداد کدهای ممکن کمتر شود.

گزینش حدس بهینه:

در هر مرحله، ما می‌خواهیم حدسی بزنیم که در بدترین حالت کمترین تعداد کدِ ممکن را برای مرحلۀ بعد باقی بگذارد.

بنابراین، برای هر حدس کاندید g درΩ، نگاه می‌کنیم اگر آن را بزنیم، در بدترین حالت چقدر از کدهای S ممکن است باقی بماند. بعد حدسی را انتخاب می‌کنیم که این «بیشترین باقی‌مانده» را تا حد ممکن کوچک کند (مینیمم کردن بدترین حالت).
خلاصه:
این الگوریتم در هر مرحله حدسی می‌زند که بدترین حالت پس از دریافت امتیاز را بهتر (کوچک‌تر) کند. به این ترتیب، بعد از هر حدس، مجموعه کدهای ممکن S تا جای ممکن کوچک می‌شود و در نهایت با کمترین تعداد حدس‌های ممکن به جواب می‌رسیم.

(در این پروژه ی پایتون این بازی ساده را همراه با یک اکتور بسیار ساده که می تواند بازی را در ۵ قدم یا کمتر ببرد پیاده سازی کرده ام. این تمرین خوبی برای دیدن این است که یک «بازی گر» دیجیتال چگونه ممکن است کار کند)

روش مینیمم کردن بدترین حالت یک اسراتژی کلی برای بازی کردن در هر بازی ای رقابتی هم هست. به طور مثال در شطرنج شما فقط به حرکات خود فکر نمیکنید بلکه به اینکه هر مهره ای که حرکت دهید چقدر برایتان خوب یا بد است هم فکر میکنید. برای اینکه می توان گفت یا حداکثر امتیاز طرف مقابل را کمینه (minimax) یا کمترین ضرر طرف مقابل را بیشینه (maxmin). همین روش بسیار ساده در چارچوب شطرنج باز های کلاسیک مانند دیپ بلو (deep blue) در سال ۱۹۸۴ گری کاسپاروف قهرمان شطرنج جهان را شکست دهد. البته دیپ بلو به جای فقط یک قدم چندین قدم این کار را کرد. به این ترتیب که درخت جستجوی مینیمکس عمیقی ساخت و با آن تعدادی زیادی حالت را بررسی کرده و با یک حرکت برگشتی مشخص میکرد چه حرکتی بهترین است!

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

«کمینه کردن بدترین حالت» یا به طور خلاصه «مینیمکس» یک اپراتور است که فضای امتیاز ها را ارزیابی و به شما یک «حدس» می دهد! «حدس» منجر به یک عمل (action) می شود که بهترین عمل است! به این ترتیب می توان رابطه حدس و نظریه بازی ها را هم دید. در قسمت بعد میبینیم که همین عملگر ساده کلید حل بسیاری از مسايل هوش مصنوعی و بخصوص مدل های انتشار (دیفیوژن) است.

BY MatlabTips