آلفاگو، یادگیری ماشین برای چیرگی بر یک بازی کهن

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

اصولا یکی از روش‌های رایج و اصلی طراحی یک عامل هوش مصنوعی برای بازی‌های تخته‌ای نظیر گو و شطرنج استفاده از جستجو و البته تدارک یک تابع مقدار بهینه (Optimal Value Function) است. تابع مقدار در واقع وظیفه‌اش اینه که وضعیت (State) فعلی بازی (که مثلا در گو و شطرنج میشه موقعیت مهره‌ها) رو دریافت میکنه و با دادن یک خروجی عددی، پیش‌بینی می‌کنه که در صورتی که همه بازیکن‌ها بهترین بازی ممکنشون رو انجام بدن نتیجه بازی چه خواهد بود. حالا وقتی که این تابع مقدار بهینه رو داشته باشیم در هر نوبت که باید یک انتخاب و اکشن انجام بدیم صرفا کافیه در درخت حالات مشتق‌شده از حالت فعلی جستجو کنیم ببینیم کدوم اکشن ما رو به استیتی با بیشترین مقدار ارزش می‌رسونه. حالا سایز فضای حالت برای بازی‌های مختلف می‌تونه تفاوت داشته باشه. مثلا دوز رو در نظر بگیرید و برای خودتون فکر کنید سایز فضای حالتش چه قدره. از طرف دیگر مثلا درخت حالات شطرنج یک درخت با میانگین عمق حدود ۸۰ و ضریب انشعاب ۳۵ هست. نکته جالب اما اینه که بازی گو با وجود قوانین ساده‌تر نسبت به شطرنج دارای یک درخت حالات با میانگین عمق حدود ۱۵۰ و ضریب انشعاب ۲۵۰ هست که همین حل کردن گو رو نسبت به شطرنج چالشی‌تر میکنه (نکته جالب اینه که تعداد حالات ممکن برای وضعیت صفحه گو بیش از تعداد اتم‌های محدوده دنیایی هست که تا حالا کشف کردیم!). کاری که معمولا برای حل چالش جستجو در این فضاهای بزرگ می‌کنند اینه که به‌جای ادامه دادن جست‌و‌جو تا برگ‌های درخت، جست‌و‌جو رو تا عمق مشخصی ادامه میدن و بعد مقدار تابع ارزش گره پیدا شده در اون عمق رو تقریب می‌زنند یا کار دیگه‌ای که می‌کنند اینه که نمیان تمام اکشن‌ها رو در هر حالت گسترش بدن و صرفا اکشن‌ها رو به صورت نمونه‌برداری و محدود بر روی حالت مورد جستجو اعمال می‌کنند. این دو تکنیک با این که باعث جستجوی محدود‌تر روی کل درخت جستجو میشه اما در عمل در مورد بازی‌‌هایی مثل شطرنج جواب خوبی داده و در حد ابرانسان عمل می‌کنند. اما مشکل اینه که گو خیلی فضای پیچیده‌تری داره که این روش‌ها بتونن روش جواب بدن. اینجاست که داستان مدل آلفاگو (AlphaGo) شروع میشه.

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

یادگیری بانظارت شبکه‌های سیاست

در مرحله اول سعی میشه تا با استفاده از یادگیری بانظارت یک شبکه رو بر روی تصمیمات گرفته شده توسط انسان‌ها آموزش بدیم (معنای شبکه سیاست یعنی این که با ورودی گرفتن حالت بازی مدل بتونه پیش‌بینی کنی که حرکت خوب چه می‌تونه باشه). به معنای بهتر یعنی از قبل دیتاستی از بازی‌های آدم‌های خبره‌‌ی گو با همدیگر جمع شده که هر نمونه این دیتاست شامل یک جفت استیت و اکشنه که مشخص میکنه در اون استیت بازیکن خبره انسانی چه اکشنی رو انتخاب کرده. ساختار این شبکه هم یک شبکه کانولوشنی هست که وضعیت صفحه‌ی گو و البته تاریخچه حرکات قبلی رو در ورودی می‌گیره و در نهایت بایستی مشخص کنه حرکت بعدی گذاشتن مهره در کدوم یک از ۱۹*۱۹ خونه صفحه باید باشه. بعد از آموزش‌دادن، عملکرد این شبکه در پیش‌بینی حرکات خبره‌های انسانی، ۵۷ درصده که نسبت به پرچمدار زمان خودش که ۴۴ درصد دقت داشته پیشرفت قابل ملاحظه‌ای بوده. اما از اونجایی که این شبکه سنگینه و خروجی گرفتن ازش زمان میگیره (۳ میلی ثانیه) یک شبکه غیردیپ دیگه هم بر روی این داده‌ها آموزش داده میشه که با این که دقتش کمتره اما سرعت بیشتری داره. این شبکه کوچکتر با این که دقتش ۲۴ درصده اما تنها در ۲ میکروثانیه خروجی میده که سرعت خیلی بالاییه. حالا در پایان این گام، ما دو شبکه سیاست بانظارت داریم که یکیشون دقت بیشتری داره و دیگری هم سرعت بالاتر. در گام‌های بعدی می‌بینیم که از هر کدوم این شبکه‌ها کجا استفاده میشه. ما در نمادگذاری‌هامون پارامتر‌های شبکه بزرگ رو با σ و پارامتر‌های شبکه کوچک رو با π نمایش می‌دهیم.

یادگیری تقویتی شبکه سیاست

مرحله دوم از لحاظ نتیجه‌ای مشابه مرحله اوله. یعنی دنبال یک شبکه سیاست هستیم ولی با این تفاوت که در این جا قصد داریم یک شبکه سیاستی بهتر از مرحله قبل رو با کمک یادگیری تقویتی به دست بیاریم. ساختار و معماری شبکه این بخش دقیقا همون معماری شبکه بزرگ قسمت اول هست. برای آموزش این شبکه اما به جای یادگیری بانظارت روی دیتاست بازی‌ها، میایم و این شبکه سیاست رو با نسخه‌های قبلی خودش بازی می‌دیم (یعنی مثلا اگر در ایتریشن ۱۰۰ام یادگیری این شبکه هستیم این شبکه رو با ایتریشن ۹۰ام اش بازی می‌دیم). حال در طی این بازی‌ها از طریق یادگیری تقویتی، شبکه سیاست رو آموزشش میدیم که انتخاب سیاستش رو بهبود ببخشه. از اونجایی که یادگیری این سیاست‌های پیچیده از اول با شبکه خام و آموزش ندیده ممکنه کار سخت و شاید غیرممکنی باشه میایم و مقدار اولیه پارامتر‌های مدل این بخش رو مساوی با پارامتر‌های شبکه بزرگ آموزش یافته در قسمت اول (یعنی شبکه سیاست یادگیری بانظارت) قرار می‌دهیم. بعد از اتمام آموزش مدل در این بخش، توسعه‌دهندگان آلفاگو اومدند و مدل سیاست این بخش رو با مدل سیاست حاصل از قسمت قبل بازی دادند (یعنی بین مدل‌های حاصل از RL و SL بازی راه انداختند تا بفهمند کدوم مدل بهتر عمل می‌کنه) جالبه که در بیش از ۸۰ درصد بازی‌ها مدل RL تونسته مدل SL رو شکست بده که دلیلی بر بهتر بودن این مدل محسوب میشه. ما در نماد‌گذاریمون پارامتر‌های این شبکه رو با ρ نمایش می‌دهیم.

یادگیری تقویتی شبکه ارزش

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

جستجو با شبکه‌های سیاست و مقدار

خب بیاید مرور کنیم تا اینجا چه شبکه‌هایی داریم:

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

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

حالا برگردیم سمت آلفاگو. فرض کنید موقعیت بازی در حالت s است و شما بایستی یک اکشن رو انتخاب کنید. مساله رو اگر از یک دید دیگه نگاه کنیم معادل با این میتونه باشه که ما با یک درخت جستجو مواجه هستیم که نود‌های اون حالات بازی و یال‌های هر نود اکشن‌های ممکن در اون حالت هستند و مابایستی در هر نود بهترین یال رو انتخاب کنیم. ما می‌تونیم یک تابع داشته باشیم که به هر زوج s و a (اکشن انتخابی در s) یک امتیاز نسبت بده که انجام این اکشن در این موقعیت چه قدر خوب هست (اگر با Qlearning آشنایی داشته‌ باشید یحتمل بهتر متوجه می‌شید این مطلب رو). در کنار این Q(s,a) ما دو مقدار دیگه N(s,a) و P(s,a) هم می‌تونیم تعریف کنیم که به ترتیب بیانگر میزان دفعات انتخاب شدن اکشن a در حالت s و احتمال پیشین انتخاب a در s هستند (اگر نفهمیدید چند دقیقه صبر کنید چند پارگراف پایین‌تر توضیح داده شده اینا دقیقا چی هستند).

حالا فرض کنید آلفاگو در حال بازی کردنه و بازی در موقعیت s است و می‌خوایم ببینیم که چه اکشنی رو باید انتخاب کنیم. آلفاگو فرمولی داره که میگه باید بر طبق این فرمول اکشن a رو انتخاب کنی:

این فرمول بیان میکنه که بهترین اکشن در حالت s اون اکشنی هست که بین بقیه اکشن‌ها، مجموع توابع Q و u اش بیشینه باشه. اما هر کدوم این تابع‌ها چطور محاسبه میشن؟ گفتیم که در الگوریتم جستجوی درختی مونته‌کارلو به‌جای این که درخت رو به صورت کامل جستجو کنیم با نمونه‌برداری تصادفی شاخه‌هایی از درخت رو پیمایش و سیمولیشن می‌کنیم و مقدار تخمینی از ارزش یک حالت یا حالت-اکشن رو با این تخمین به دست میاریم. در آلفاگو هم دقیقا همین سناریو رخ میده و ما بر روی درخت سیمولیشن و پیمایش انجام میدیم. بر این اساس تابع u رو به صورت زیر فرموله میکنیم:

این فرمول تابع u رو متناسب با تابع P و معکوس با N مدل میکنه. اول از همه گفتیم که N نشون میده در طی سیمولیشن‌هامون روی درخت چند بار در حالت s اکشن a رو نمونه برداری کردیم. حال هر چه قدر این عدد بیشتر باشه شانس انتخاب اون اکشن پایین‌تر میاد. دیپ‌مایند این جوری توضیح داده که این عمل باعث میشه مدل، تشویق به اکسپلوریشن بیشتر در محیط باشه. اون تابع P هم دانش پیشین ما از میزان خوب بودن انتخاب اکشن a در حالت s است. ما حالا این تابع رو با همون شبکه سیاست بزرگ نظارتی که در بخش اول یاد گرفتیم مدل می‌کنیم. یعنی اگر خواستیم P(s,a) رو حساب کنیم s رو به اون شبکه سیاست بانظارت بزرگ ورودی می‌دیم و احتمالی که برای a برمی‌گردونه رو به عنوان مقدار P(s,a) در نظر می‌گیریم.

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

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

حالا وقتی که سیمولیشن‌هامون رو انجام دادیم از روی میانگین نتایج سیمولیشن‌هامون تابع Q رو به طرز زیر محاسبه می‌کنیم:

که در فرمول‌های بالا تابع (s,a,i)1 بیان ‌میکنه که آیا اکشن a در حالت s در سیمولیشن i ام مورد پیمایش قرار گرفته یا نه. وقتی سیمولیشن‌هامون رو انجام بدیم و مقدار Q(s,a) رو محاسبه کنیم حالا می‌تونیم تصمیم بگیریم که در نود ریشه (همون حالتی که توش هستیم) چه اکشنی رو می‌تونیم انتخاب کنیم.

ارزیابی میزان قدرت آلفاگو

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

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

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

همانطور که می‌بینید وقتی که Rollout استفاده نشده و فقط از شبکه ارزش استفاده شده عملکرد ضعیف‌تر از زمانی بوده که Rollout و شبکه ارزش با هم استفاده شده‌اند. در نهایت در اکتبر ۲۰۱۵ پنج مسابقه بین آلفاگو و فان هویی که قهرمان متوالی سه سال رقابت‌های گو اروپا بود برگزار شد و آلفاگو تونست با اقتدار پنج بر صفر فان هویی رو در هم بکوبه و برای اولین بار یک عامل کامپیوتری تونست یک قهرمان گو رو شکست بده. در ادامه هم در سال ۲۰۱۶ آلفاگو در مقابل لی سدول از کره جنوبی که هجده عنوان در مسابقات جهانی گو داشت قرار گرفت و در مسابقه‌ای که توسط ۲۰۰ میلیون نفر بیننده دنبال میشد تونست این بازیکن رو با نتیجه ۴-۱ بفرسته خونشون سئول.

الان که در سال ۲۰۲۲ هستیم روشی که آلفاگو استفاده کرده به نظر خیلی ساده و مبتدیانه میاد. اما آلفاگو در سال ۲۰۱۵ برای خودش انقلابی در زمینه هوش مصنوعی محسوب می‌شده و باعث شد که موجی از توجهات به RL و یادگیری تقویتی جلب بشه. انشالله اگر عمری باقی باشه به باقی مقالات و مدل‌های مهم جریان‌ساز هوش مصنوعی نیز می‌پردازیم.

در تلگرام می‌تونید دنبالمون کنید و اگر هم متن خوبی در حوزه‌ی هوش مصنوعی و پردازش زبان طبیعی داشتید که در انتشارات یا کانال بگذاریم، از همون‌جا ندا بدید.