REPORT.md

## گزارش پروژه هوش مصنوعی - بازی othello

موضوع: پیاده‌سازی منطق و agent هوشمند برای بازی othello

هدف: پروژه درس هوش‌مصنوعی و سیستم‌های خبره در پاییز ۹۹، دانشگاه شهید بهشتی

استاد: دکتر سلیمی‌بدر

اعضای تیم:

• روزبه شریف‌نسب
• متین زیودار

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

فاز ۱

در فاز اول به پیاده‌سازی منطق بازی پرداختیم. از زبان برنامه‌نویسی پایتون استفاده کردیم. همچنین برای نگه‌داری زمین از آرایه‌های numpy استفاده کردیم که با توجه به پیاده‌سازی native، پرفورمنس بالاتری ارائه دهند و دچار افت عملکرد ناشی از list های پایتون نشویم.

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

اما UI دوم به صورت گرافیکی با استفاده از پکیج zenipy است.

این پکیج بر روی پکیج zenity که از ابزارهای گنوم برای تسهیل ساخت رابط کاربری‌ست بنا شده است.

استفاده از پکیج zenity به این صورت است که یک باینری برای ما نصب می‌شود و می‌توان از طریق خط فرمان به آن دستور داد تا دیالوگ‌های مختلف را به اجرا در بیاورد. مثلا می‌توان با دستور زیر، پیام helloworld را به کاربر نمایش داد:

zenity --info --text="hello world"

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

اما برای استفاده از این پکیج در پایتون دو راه موجود است. راه اول کار کردن با دستورات subprocess و صدا زدن این باینری از طریق محیط کامند موجود در پایتون. مشکل این روش علاوه بر وابستگی به پلتفرم، دشواری گرفتن خروجی از پروسس است. البته با استفاده از ساب‌پروسس امکان پذیر است ولی راه‌های بهتری نیز وجود دارند. دوستان برنامه‌نویس ما پکیج zenipy را آماده کرده‌اند که با استفاده از api‌های پایتون و فراخوانی کلاس‌ها و متد‌های محتلف می‌توان دیالوگ‌ها را اجرا کرد و خروجی را گرفت. با توجه به استفاده از QT در این پکیج، اسم این کلاس UI را QT گذاشتیم که در فایل ui.py قابل ملاحظه است.

از موارد دیگری که می‌توان به آن‌ها اشاره کرد، نحوه استفاده و پر کردن آرایه‌های نام‌پای است. برای این منظور یکی از کاربران را 1+ و دیگری را 1- در نظر گرفتیم. همچنین خانه‌های خالی را نیز مقدار 0 قرار دادیم. به این صورت تنها با پیاده سازی تابع numpy.sum می‌توانبه نتیجه بازی رسید. همچنین برای اعمال تابع شهودی نیز بسیار مفید است و بسیار از محاسبات زائد را حذف می‌کند.

ایده دیگری که پیاده سازی شد (و البته در ادامه حذف شد) cache کردن توابع pure روی برد بود. مثلا تابعی که move‌های ممکن را می‌گوید می‌تواند تا زمانی که برد عوض نشده cache شود. همچنین تابع valid flip نیز چنین خاصیتی داشت. برای این منظور از lru_cache استفاده کردیم اما نیاز بود که شی موجود (مثلا کلاس board ما) قابل hash گرفتن باشن. با توجه به قابل هش نبودن آرایه‌های نام‌پای، تصمیم گرفتیم آن‌ها را تبدیل به رشته کنیم اما این مورد بدتر سربار پرفورمنسی داشت و از آن صرف نظر شد. البته پکیج‌های خوب دیگری نیز هستند که این امکان را فراهم می‌کنند ولی تلاش شد کم‌ترین وابستگی به پکیج‌های غیرضروری ایجاد شود.

به عنوان آخرین نکته خوب است اشاره کنیم ارورهای موجود (که عمدتا کاربر با آن‌ها رو به رو می‌شود) مانند وارد کردن محل نامناسب در بورد، به کمک اکسپشن‌ها هندل شده.

فاز ۲

در فاز دوم، با توجه به اینکه می‌خواستیم امکان بازی هم با بازیکن دیگر هم با هوش مصنوعی وجود داشته باشد، مانند برنامه‌های cli دیگر و مطابق با فلسفه یونیکس، از آرگومان‌ها استفاده کردیم و با استفاده از argument parser آن‌ها را دریافت کردیم. پیاده‌سازی این قسمت در فایل argparse.py موجود است. در اینجا تنها به چند مثال از اجرای برنامه بسنده می‌کنیم:

# run game in cli mode, user vs ai (minimax)
./src/play.py  --cli --p1 user --p2 ai

# run game in gui mode, user vs user
./src/play.py --gui --p1 user --p2 user

همچنین در این مرحله، type hint به برنامه اضافه شد. با توجه به بزرگ‌شدن برنامه و استفاده از زبان dynamic type این مورد غیرقابل چشم‌پوشی بود. برای استاندارد سازی، تغییراتی در کلاس‌های UI به وجود آمد و از ارث‌بری استفاده شد. (مشابه مفهوم interface)

اما قسمت اصلی که در این فاز اضافه شد، پیاده‌سازی منطق minimax برای بازی به عنوان agent هوشمند بود.

تابع minimax نکته خاصی ندارد و توضیحات استاد و اسلاید‌های درس کفایت می‌کند.

اما واضح است که برای گرفتن نتیجه مطلوب از minimax لازم داریم که بهینه‌سازی‌هایی در آن انجام دهیم. این بازی با توجه به حرکت‌های زیاد و زمین نسبتا بزرگ (به نسبت XO) نیاز به بهینه‌سازی‌هایی در تابع minimax دارد. بهینه سازی اول که منجر به افت کیفیت agent نمی‌شود، پیاده سازی هرس آلفا-بتا است. از توضیحات این قسمت نیز صرف نظر می‌کنیم.

قسمت بعدی، محدود کردن عمق درخت جست‌وجوست. مشخص است که نمی‌توان تمام حرکت‌های موجود را بررسی نمود و در تایم محدود (برای بازی real time) پاسخ را محاسبه کرد. حداقل با سیستم رومیزی ما این امر ممکن نبود. برای همین عمق درخت را محدود کردیم. با پیشنهاد عزیزان تدریس یار، عمق ۱۰ را انتخاب کردیم تا هم زمان پردازش زیاد نشود و هم انتخاب‌های منطقی و آینده نگرانه حفظ شود.

اما یک مشکل وجود دارد، زمانی که به یک عمق مشخص (و نه پایان بازی) برسیم نمی‌دانیم آیا این حالت board مناسب است یا نه؟ بهتر است این حرکت انتخاب شود یا حرکت دیگری؟ برای این مشکل باید یک تابع شهودی ابداع می‌کردیم. تابعی که با صرف هزینه پردازشی کم، بتواند به board ما یک عدد نسبت دهد و میزان خوب بودن آن (با توجه به بازیکن فعلی) را مشخص کند.

ساده‌ترین راهی که به ذهنمان رسید و در هنگام پیاده‌سازی تابع minimax از آن استفاده کردیم، استفاده از همان numpy sum بود. به این معنی که تعداد مهره‌های ما منهای تعداد مهره‌های حریف می‌شد و از آن عدد استفاده می شد. این روش اگرچه برای آخر‌های بازی که فقط تعداد مهره‌ها اهمیت دارد مناسب است برای برای ابتدای بازی استراتژی مناسبی نیست و منجر به برد نمی‌شود. برای مثال می‌دانیم که گرفتن ۴ خانه گوشه در این بازی اهمیت زیادی دارد ولی این تابع مکاشفه‌ای این مورد را لحاظ نمی‌کند و با توجه به عمق محدود (۱۰) کارایی مناسبی نخواهد داشت.

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

به این صورت که برای ۳ مرحله متفاوت بازی، ۳ استراتژی متفاوت در نظر گرفتیم.

1. ۱۶ حرکت آخر بازی که پایه‌های اصلی بازی بنا شده، فقط گرفتن مهره‌های بیشتر اهمیت دارد بنابراین از تابع مکاشفه‌ای absoloute استفاده کردیم به این معنی که از numpy sum استفاده کرده و تعداد مهره‌ها را برمی‌گرداند.
2. برای میانه‌ی بازی از یک ماسک (که خود یک آرایه‌ی numpy است) استفاده کردیم. در تابع calculate positional برد بازی را در یک آرایه دیگر ضرب می‌کنیم و سپس مجموع ان را حساب می‌کنیم. این آرایه که در برد اصلی ضرب می‌کنیم در واقع نقش وزن‌دهی به خانه‌های مختلف را دارد. برای مثال همان ۴ گوشه که در قسمت قبل ذکر شد باید وزن بسیار بیشتری داشته باشند چون در تعیین برنده بسیار حائز اهمیت هستند. در این حالت، وزن‌دهی به هر خانه از آرایه‌ی وزن‌ها اهمیت دارد. برای این منظور بیشترین وزن برای ۴ خانه کناری گرفته شده. خانه‌های وسط امتیازی چندانی ندارد و رغبتی به گرفتنشان وجود ندارد. در عوض خانه‌های محیطی دوست‌داشتنی هستند چون می‌توانند امتیازی آور باشند. خانه‌هایی با اندیس (1,1) (1,0) (0,1) نیز ارزش بسیار کمی دارند چون به حریف کمک می‌کنند خانه‌های گوشه را بگیرد و از این منظر منفی به شما می‌روند.
3. برای ۱۰ مرحله ابتدایی بازی، از تابع mobility استفاده شد. با توجه به مشکلات این تابع و مفید نبودن آن (چرا که حداقل ۱۰ عمق پیش می‌رویم و بعد تابع شهودی را صدا می‌کنیم)، در پیاده‌سازی نهایی این قسمت حذف گردید.

چند نمونه از مقالات بررسی شده را در زیر می‌بینید:

1. مقاله‌ای از سایت ultra board games
2. مقاله‌ای از سایت bonaludo

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

1. بازنویسی برنامه با یک زبان سطح پایین‌تر: این روش بیشتر شبیه پاک کردن صورت مساله است. اگرچه برنامه سریع‌تر خواهد شد ولی مشکل الگوریتمی حل نشده. همچنین فرصت زیادی هم نداریم که کلا بازنویسی کنیم.
2. استفاده از pypy: این روش، بسیار کارا در سریع‌تر کردن برنامه‌های پایتونیست اما مشکلی که وجود دارد این است که با پکیج‌هایی که پیاده‌سازی native دارند مثل numpy که هسته منطق ما را تشکیل می‌دهد سازگار نیست. بنابراین این روش هم منتفی است.
3. کم کردن عمق: به عنوان آخرین راه حل جزو گزینه‌ها هست ولی بیاید بیشتر فکر کنیم.
4. ایده‌ای که برای حل کردن پرفورمنس در تابع minimax را استفاده کردیم با دوباره به‌کار بگیریم: کم کردن بار محاسباتی با کاهش اندک دقت agent.

نهایتا همین ایده ۴ برگزیده شد ولی چگونگی این کم کردن دقت هم اهمیت دارد. کار مهندس، برقرار کردن تعادل در trade-offهای متفاوت است. اینجا هم باید تعادلی را پیدا کنیم که با حفظ حداکثری دقت، سرعت برنامه قابل قبول شود.

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

اما اینجا باید انتخاب کنیم که از همه حرکات موجود، کدام را انتخاب کنیم و چند تا؟

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

تنها ابهامی که باقی می‌ماند این است که کدام حرکات خوب هستند و کدام‌ها خوبی نیستند؟ حرکتی که هنوز انجام نشده را چطور می‌توان سنجید؟

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

در نهایت برای اینکه دقت همچنان در حد قابل قبولی بماند، عملیات هرس کردن را در عمق دوم به بعد ادامه دادیم، بنابراین در عمق اول تمام حرکات موجود بررسی می‌شوند.

فاز ۳

آن‌چه برای فاز سوم مدنظر بود، استفاده از الگوریتم‌های ژنتیک برای پیدا کردن بهترین ماسک (آرایه‌ی ضرایب) برای تابع مکاشفه‌ای بود.

فضای مسئله را به فضای ژنتیک مپ کنیم:

• ژن‌ها: هر سطر از ماسک یک ژن می‌شود. با استفاده از تابع mutated genes یک سطر رندوم از اعداد تولید می‌شود.

• ژنوم: کل ماسک (شامل ۸ ژن) که برای عمل بازتولید استفاده می‌شود. نهایتا خروجی برنامه ما نیز یک ژنوم که بهترین ماسک است خواهد بود.

• ترکیب: دو حالت ترکیب را پیش‌بینی کرده‌ایم.

  1. حالت ترکیب سطری، یعنی بر اساس یک شاخص رندوم، بین سطر iام ماسک اول و سطر iام ماسک دوم یکی را انتخاب می‌کنیم.
  2. حالت ترکیب میانگین‌گیری، یعنی بین تک تک سطر‌ها میانگین می‌گیریم.

• جهش: در هر دو حالت جهش، برای هر سطر ۱۰ درصد احتمال جهش وجود دارد. جهش به این صورت است که به جای آن سطر (میانگین یا انتخاب بین m1 و m2)، یک سطر رندوم جدید تولید می‌شود و قرار می‌گیرد.

باقی داستان تقریبا مشابه همه الگوریتم‌های ژنتیک است و نکته چندان جدیدی ندارد.

نسل اولیه تولید می شود، از روی هر نسل، نسل جدید ساخته می‌شود. در برنامه ما دو والد به صورت رندوم انتخاب می‌شوند و به وسیله میانگین‌گیری (حالت دوم ترکیب) فرزندی بین آن‌ها تولید می‌شود.

در نهایت مسابقه‌ای بین فرزند i ام و والد i ام برگزار می‌شود و برنده هر مسابقه ذخیره می‌شود.

این برنده‌ها نسل بعد را می‌سازند.

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

الگوریتم مسابقه، دقیقا مشابه بازی ai با ai است. با این تفاوت که ماسک آن agent از بیرون تزریق می‌شود.

ایده‌های دیگری که می‌توان مطرح کرد این است که به جای ساخت ماسک کامل، فقط 1/4 ماسک را بسازیم و فرض کنیم ۴ تا از این 1/4 ها ماسک کامل را تشکیل می‌دهند تا زودتر به همگرایی برسیم.

یا همچنین می‌توان برای سریع تر کردن یادگیری، عمق مینیمکس را کم کرد.

نکته: در برنامه ما اعضای آخرین نسل با هم تفاوت دارند و بهترین آن ها به عنوان برنده اعلام می‌شود.

به این صورت که بین همه آن ها یک تورنومنت برگزار می‌شوند و دو به دو مسابقه می‌دهند. هر کدام که مسابقه‌های بیشتری را ببرد برنده است و چاپ می‌شود.