آموزش مسئله ۸ وزیر هوش مصنوعی به صورت جامع و گام به گام

مقدمه و تاریخچه مسئله ۸ وزیر هوش مصنوعی

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

مسئله ۸ وزیر ظاهراً اولین بار توسط ماکس بزل (Max Bezzel) در روزنامه شطرنج برلین در سال (۱۸۴۸) مطرح شد و اولین بار توسط فرانتس ناوک (Franz Nauck) در روزنامه مصور لایپزیگ (۱۸۵۰) به‌طور کامل حل شد و بعداً توسط Nauck پازل به مسئله n وزیر روی یک صفحه شطرنج n×n گسترش داده شد. پس از آن (Gunther) راه حلی با استفاده از دترمینان ارائه داد که J.W.L. Glaisher آن‌را کامل کرد و درنهایت در سال ۱۹۷۹، Edsger Dijkstra با استفاده از الگوریتم عقب گرد اول عمق این مسئله را حل کرد.

مسئله ۸ وزیر هوش مصنوعی 92 راه حل دارد که ۱۲ راه حل آن منحصر به فرد است و بقیه از تقارن این ۱۲ تا بدست می‌آیند. هر یک از دوازده راه‌حل نشان‌داده‌شده در این صفحه، یک کلاس معادل از راه‌حل‌ها را نشان می‌دهد که با چرخاندن صفحه شطرنج و یا چرخاندن آن در امتداد یکی از محورهای تقارن آن از یکدیگر حاصل می‌شوند. هر یک از کلاس‌های هم ارزی نشان داده شده توسط راه حل‌های ۱و ۲ و.. ۱۱ شامل هشت راه حل است. از آن‌جایی که راه حل ۱۲ با چرخش ۱۸۰ درجه صفحه شطرنج ثابت است، کلاس هم ارزی آن تنها از چهار راه حل تشکیل شده است.

مسئله n وزیر هوش مصنوعی از جمله مسائل NP-Hard در هوش مصنوعی است که روش‌های جستجوی معمولی قادر به حل آن‌ها نخواهد بود. راستی حواسمان باشد که این مسئله در صورتی که n=۲ و n=۳ باشد، راه حلی ندارد. فهمیدن این موضوع کار سختی نیست. جدولی با ۴ عنصر تصور کنید و دو وزیر هر طوری بچینید همدیگر را تهدید می‌کنند و ۳ وزیر و صفحه شطرنج ۳ در ۳ هم به همین صورت هست. ۱۲ حالت اصلی را در شکل زیر مشاهده می‌کنیم.

مشکل یافتن همه راه‌حل‌ها برای مسئله ۸ وزیر هوش مصنوعی می‌تواند از نظر محاسباتی بسیار گران باشد، زیرا ۴،۴۲۶،۱۶۵،۳۶۸ ترتیب ممکن از هشت وزیر که در یک سطح ۸×۸ وجود دارد، اما تنها دارای ۹۲ راه حل متمایز است پس این مسئله فضای جستجوی وسیعی دارد. می‌توان از میانبرهایی استفاده کرد که الزامات محاسباتی را کاهش می‌دهد یا قوانین کلی که از تکنیک‌های محاسباتی brute-force اجتناب می‌کند. به عنوان مثال، با اعمال یک قانون ساده که هر وزیر را به یک ستون (یا ردیف) محدود می‌کند، اگرچه همچنان نیروی brute در نظر گرفته می‌شود، می‌توان تعداد احتمالات را به ۱۶۷۷۷۲۱۶ (یعنی ۸ به توان ۸) ترکیب ممکن کاهش داد.

چنان‌چه تمایل داشتید در زمینه مسئله ۸ وزیر هوش مصنوعی تحقیق یا ارائه‌ای داشته باشید؛ فایل‌های آماده متنوع موجود در سایت پی استور را مد نظر قرار دهید. نمونه‌هایی از منابع آماده را در زیر درج کرده‌ایم.

• پاورپوینت مسئله هشت وزیر — ٰEight queens Problem — کلیک کنید.
• حل مسئله ۸ وزیر با الگوریتم SA در پایتون — کلیک کنید.
• پاورپوینت حل مساله n وزیر با الگوریتم پس گرد (Backtracking) — کلیک کنید.

روش های حل مسئله ۸ وزیر هوش مصنوعی

در این مطلب مسئله ۸ وزیر با ۴ روش زیر حل شده‌اند:

• استفاده از روش مکاشفه‌ای یا هیوریستیک (heuristic)
• روش‌های جستجوی محلی
• حل مسئله ۸ وزیر هوش مصنوعی با الگوریتم ژنتیک
• حل مسئله ۸ وزیر هوش مصنوعی با روش عقبگرد یا Back tracking

در ادامه به توضیح هرکدام از این روش‌ها می‌پردازیم.

استفاده از روش مکاشفه ای یا هیوریستیک (heuristic) در حل مسئله ۸ وزیر هوش مصنوعی

برای حل این مسئله که دارای ۹۲ جواب است، باید روش‌هایی جهت کاهش حالات، روش Brute Force یا امتحان تک تک جواب‌ها را انجام داد.

1. عدد n را بر عدد ۱۲ تقسیم کن و باقی مانده را یادداشت کن.
2. به ترتیب اعداد زوج ۲ تا n را در یک لیست بنویس.
3. اگر باقی مانده ۳ یا ۹ بود، عدد ۲ را به انتهای لیست انتقال بده.
4. به لیست اعداد فرد ۱ تا N را به ترتیب اضافه کن. اما اگر باقی مانده ۸ بود جای اعداد را دو به دو باهم عوض کن. ( ۱-۳-۵-۷-۹ می شه ۳-۱-۷-۵-۹)
5. اگر باقی مانده ۲ بود جای ۱ و ۳ را باهم عوض کن و ۵ را به انتهای لیست ببر.
6. اگر باقی مانده ۳ یا ۹ بود، اعداد ۱ و ۳ را به انتهای لیست ببر.
7. حال با استفاده از لیست بدست آمده وزیرها در صفحه شطرنج چیده می‌شوند، به‌طوری‌که جای وزیر ستون اول، اولین عدد لیست، جای وزیر ستون دوم، دومین عدد لیست و…. برای به‌دست آوردن حالات دیگر از روش‌های دیگر باید استفاده شود. روش حل مسئله ۱۲ راه حل یکتا دارد با در نظر گرفتن تقارن و چرخش به ۹۲ حالت قابل تبدیل است.

برای آشنایی بیشتر با روش مکاشفه ای یا هیوریستیک (heuristic) در حل مسئله ۸ وزیر از فایل آماده موجود در سایت پی استور بهره ببرید.

• پاورپوینت جست و جوی هیوریستیک (Heuristic Search) — کلیک کنید.

روش های جستجوی محلی در مسئله ۸ وزیر هوش مصنوعی

در این نوع از روش‌ها هدف یافتن مسیری با کم‌ترین هزینه از حالت شروع به حالت هدف در گراف فضای حالت است. در بسیاری از مسائل بهینه سازی مسیر راه حل اهمیت ندارد. بلکه خود حالت هدف مهم است که نسبت به حالت‌های دیگر در فضای حالت‌ها بهتر باشد. به مسئله ۸ وزیر هوش مصنوعی می‌توان به‌عنوان یک مسئله بهینه سازی هم نگاه کرد که هدف بهینه کردن تعداد تهدیدهای جفت وزیرها است.

یعنی وزیرها را می‌چینیم ولی در نهایت اونی جواب می‌شه که کمترین تعداد برخوردها را داشته باشد.

روش کار به این شکل است که:

• استفاده از یک حالت به‌عنوان حالت فعلی
• بهبود حالت فعلی از طریق حرکت به یکی از حالت‌های همسایه

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

مسئله ۸ وزیر هوش مصنوعی را با این روش حل می‌کنیم. البته مثالمان را برای ۴ وزیر می‌زنیم که حجم مسئله کوچک‌تر باشد. در ابتدا جدولی داریم با ۴ خانه و ۴ وزیر. حالت اولی را اتفاقی انتخاب می‌کنیم. چیدمان آن اتفاقی است. این مسئله را بدین صورت فرموله سازی می‌شود. که در هر ستون می‌دانیم که فقط یک وزیر می‌تواند وجود داشته باشد و عملیات را طوری تعریف می‌کنیم که هر وزیر فقط در ستون خودش حرکت کند. اندازه فضای حالت ۴ به توان ۴ می‌شود. که در حالت‌های بزرگ N به توان N است. نرخ رشد N به توان N بسیار سریع است و فضای حالت بسیار بزرگی دارد.

در این مسئله در حالت ۴ دیگه متوقف می‌شویم و به جواب بهینه رسیدیم.

حل مسئله ۸ وزیر هوش مصنوعی با الگوریتم ژنتیک

در مورد مسئله ۸ وزیر می‌دانیم که دو وزیر نباید در یک ستون قرار بگیرند. برای نمایش مسئله در مورد کروموزوم‌ها بدین ترتیب عمل می‌کنیم: ابتدا یک آرایه تک بعدی ایجاد می‌کنیم که به تعداد ستون‌های شطرنج ما عنصر دارد. هر عنصر از این آرایه نشان می‌دهد که وزیر در آن ستون در کدام سطر قرار دارد. اگر مسئله ۸ وزیر را در این قالب تصور کنیم آرایه ما ۸ عنصر خواهد داشت و فرضاً آرایه دارای مقادیر زیر است.

۸,۷,۶,۵,۴,۳,۲,۱

برای توضیح بیشتر، مقدار ۸ در اولین عنصر نشان دهنده این است که در ستون اول صفحه شطرنج، وزیر در سطر هشتم قرار دارد در ستون دوم وزیر در سطر ۷ قرار دارد و… . ابتدا باید طبق الگوریتم ژنتیک تولید جمعیت اولیه کنیم.

تولید جمعیت اولیه

الگوریتم ژنتیک در ابتدای کار تولید جمعیت اولیه می‌کند بعداً سعی می‌کند این جمعیت اولیه را بهبود ببخشد. برای این مسئله تولید جمعیت اولیه به‌صورت تصادفی خواهد بود.

نحوه انتخاب والدین

نحوه انتخاب والدین به این صورت است که ۵ کروموزوم به‌طور تصادفی انتخاب می‌شوند. بعد از بین این ۵ کروموزوم دوتایی که تابع سازگاری آن‌ها بیشینه‌تر هست انتخاب می‌شوند. نحوه محاسبه این تابع بدین شکل است که برای هر ژن که در مسئله ۸ وزیر هوش مصنوعی ژن همان وزیرهای ما هست. برای هر وزیر تعداد تهدیدها حساب می‌شوند و از معکوس جمع آنها مقدار تابع سازگاری برای هر وزیر به‌دست می‌آید. هدف داشتن حداکثر تابع سازگاری است.

برای تولید فرزندان یک نقطه رندوم در کروموزوم‌ها انتخاب می‌شود. فرزند اول ژن‌های سمت چپ این نقطه در والد اول و فرزند دوم ژن‌های سمت چپ این نقطه در والد دوم را به ارث می‌برند. سپس برای پر کردن باقی ژن‌ها در سمت راست این نقطه در فرزند اول، والد دوم را از سمت چپ به راست پیمایش کرده و هر مقداری که در فرزند اول وجود نداشت را به همان ترتیب پیمایش در این فرزند درج می‌کنیم. برای پر کردن سمت راست فرزند دوم نیز همین کار را با والد اول تکرار می‌کنیم.

برای هر یک از فرزندان به احتمال ۸۰% جهش ایجاد می‌شود. دو اندیس از آرایه به صورت تصادفی انتخاب می‌شود و مقدار موجود در آنها باهم جابه جا می‌شود. سپس کل جمعیت براساس تابع سازگاری مرتب می‌شوند و دو کروموزوم یا وزیر آخر که جز بدترین‌ها هستند را با فرزندان جابه جا می‌کنیم.

نتیجه: الگوریتم با توجه به جمعیت انتخاب شده بعد از یک تا بیشتر از ۲۰ بار تکرار می‌تواند به جواب برسد.

در جهت کسب آگاهی بیشتر در این زمینه، پاورپوینت آماده موجود را مطالعه نمایید.

• پاورپوینت الگوریتم های ژنتیک — کلیک کنید.

حل مسئله ۸ وزیر هوش مصنوعی با روش عقبگرد یا Back tracking

عقبگرد یا همان backtracking روشی است که در آن تمام حالت‌های ممکن ساخته می‌شود و هر حالتی که ساخته می‌شود چک می‌شود تا درست یا غلط بودن آن بررسی شود و اگر غلط بود حالتی دیگر را تولید می‌کند و همین طور ادامه می‌دهد.

شکل بالا درخت تمام حالاتی است که ۴ وزیر را می‌توان در صفحه شطرنج ۴ در ۴ قرار داد. وزیر اول می‌تواند در ستون‌های ۱ تا ۴ قرار گیرد. وزیر دوم هم می‌تواند در سطر دوم در ستون‌های ۱ تا ۴ قرار بگیرد و همین طور الی آخر ادامه دارد. حالا برای پیدا کرن جواب از درخت باید درخت را پیمایش کنیم. ابتدا یک حالت را با پیمایش عمقی درخت به‌دست می‌آوریم.

در پیمایش عمقی ابتدا ریشه دیده می‌شود و بعد از آن فرزندان به‌طوری که فرزندان چپ پیمایش می‌شوند. تا اینکه به فرزند برگ برسیم. مجدد از ریشه شروع می‌کنیم تا فرزند برگ یکی بعد از قبلی که پیمایش شد. با مشاهده نمونه‌های پایین متوجه نحوه پیمایش می‌شوید.

(۱,۱)(۲,۱)(۳,۱)(۴,۱) – (۱,۱)(۲,۱)(۳,۱)(۴,۲) – (۱,۱)(۲,۱)(۳,۱)(۴,۳) – (۱,۱)(۲,۱)(۳,۱)(۴,۴) – (۱,۱)(۲,۱)(۳,۲)(۴,۱) – (۱,۱)(۲,۱)(۳,۲)(۴,۲) – (۱,۱)(۲,۱)(۳,۲)(۴,۳) – (۱,۱)(۲,۱)(۳,۲)(۴,۴) – (۱,۱)(۲,۱)(۳,۳)(۴,۱) – (۱,۱)(۲,۱)(۳,۳)(۴,۲) – (۱,۱)(۲,۱)(۳,۳)(۴,۳) – (۱,۱)(۲,۱)(۳,۳)(۴,۴) – (۱,۱)(۲,۱)(۳,۴)(۴,۱) – (۱,۱)(۲,۱)(۳,۴)(۴,۲) – (۱,۱)(۲,۱)(۳,۴)(۴,۳) – (۱,۱)(۲,۱)(۳,۴)(۴,۴) – (۱,۱)(۲,۲)(۳,۱)(۴,۱) – (۱,۱)(۲,۲)(۳,۱)(۴,۲) – (۱,۱)(۲,۲)(۳,۱)(۴,۳) – (۱,۱)(۲,۲)(۳,۱)(۴,۴) – (۱,۱)(۲,۲)(۳,۲)(۴,۱) – (۱,۱)(۲,۲)(۳,۲)(۴,۲) – (۱,۱)(۲,۲)(۳,۲)(۴,۳) – (۱,۱)(۲,۲)(۳,۲)(۴,۴) – (۱,۱)(۲,۲)(۳,۳)(۴,۱) – (۱,۱)(۲,۲)(۳,۳)(۴,۲) – (۱,۱)(۲,۲)(۳,۳)(۴,۳) – (۱,۱)(۲,۲)(۳,۳)(۴,۴) – (۱,۱)(۲,۲)(۳,۴)(۴,۱) – (۱,۱)(۲,۲)(۳,۴)(۴,۲) – (۱,۱)(۲,۲)(۳,۴)(۴,۳) – (۱,۱)(۲,۲)(۳,۴)(۴,۴) …

بدین ترتیب با پیمایش عمقی درخت به‌صورت preorder تمامی حالات ۴ وزیر به‌صورت منظم به‌دست می‌آیند. برای رسیدن به جواب باید تک تک حالت‌ها رابررسی کنیم که آیا وزیرها همدیگر را تهدید می‌کنند یا نه. اگر هیچ وزیری همدیگر را تهدید نکردند معلوم می‌شود که به جواب رسیده‌ایم و آن را چاپ می‌کنیم.

در فایل آماده‌ای که توسط پی استور طراحی و تهیه گردیده این روش به‌صورت کامل شرح داده شده است. در ادامه لینک پاورپوینت آماده در اختیارتان قرار داده شده.

• پاورپوینت الگوریتم جستجوی بهینه ساز عقب گرد BSO — کلیک کنید.

سخن آخر مقاله آموزش مسئله ۸ وزیر هوش مصنوعی

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