درخت جستجوی مونت کارلو: پیاده‌سازی الگوریتم‌های یادگیری تقویتی برای بازی‌های زنده

یادگیری تقویتی Reinforcement Learning یک تکنیک یادگیری ماشینی Machine learning است که به کمک آن می‌توانیم عامل تصمیم‌گیرنده‌ای Agent طراحی کنیم که از طریق تعامل با محیط تجربه کسب می‌کند. این عامل از اشتباهاتی که در حین کسب تجربیات مرتکب شده، نکاتی می‌آموزد و براساس این آموزه‌ها رفتارش را به نحوی اصلاح می‌کند که در آینده تنبیه Penalty کمتر و پاداش بیشتری دریافت کند.

مقاله پیش رو به فراز و نشیب‌های پیاده‌سازی یک مدل بازیکن عمومی برای یک بازی تخته‌ای به نام HEX می‌پردازد و کد پایتون این پروژه را نیز می‌توانید در این لینک مشاهده کنید. همچنین کدهای نسخه جدیدتر این پروژه که در آن به منظور افزایش سرعت شبیه‌سازی‌ها از کتابخانه سایتون (cython) استفاده شده در این لینک قابل دسترسی هستند.

ویدیوی زیر نسخه آزمایشی محصول نهایی است:

در این مقاله ابتدا باید به مباحث تئوری بپردازیم. بنابراین، پیش از هر چیز نحوه مدل کردن فضای یک بازی (مثل شطرنج) در قالب الگوریتم یادگیری تقویتی را بررسی خواهیم کرد. به این منظور سعی می‌کنم مطالب را به آسانی بیان کنم و از ریاضیات و فرمول‌های کمتری استفاده کنم تا موضوع قابل درک‌تر باشد. تمرکز اصلی این مقاله بر الگوریتم درخت جستجوی مونت کارلو Monte carlo tree search و نحوه پیاده‌سازی آن برای یک بازی ساده به نام HEX است.

فهرست:

• • بیان مسئله
  • یادگیری تقویتی چیست؟
  • یادگیری Q
  • نتیجه‌گیری

بیان مساله:

فرض کنید یک بازیکن شطرنج هستید و تصویر زیر صفحه بازی است که درحال‌حاضر با آن مواجه هستید.

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

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

گزینه‌های پیش روی بازیکن سیاه عبارتند از:

• حرکت دادن مهره رخ سیاه از D8 به خانه D2 و حذف مهره فیل سفید.
• حرکت اسب سیاه از خانه G4 به خانه E3 و حذف مهره وزیر رقیب.
• حرکت وزیر سیاه از خانه H5 به H1 و کیش و مات رقیب و بردن بازی.

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

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

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

به نظر شما آیا این دقیقاً همان روشی نیست که انسان‌ها برای رسیدن به اهدافشان در پیش می‌گیرند؟

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

یادگیری تقویتی چیست؟

بنیان گذار یادگیری تقویتی پروفسور R.Sutton تعریف بسیار خوبی از یادگیری تقویتی را در کتاب خود ارائه کرده است:

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

عناصر کلیدی الگوریتم یادگیری تقویتی عبارتند از:

1. عامل تصمیم‌گیرنده: در این‌جا همان برنامه‌ای است که بازی را به روش آزمون و خطا یاد می‌گیرد.
2. محیط (وضعیت): دنیایی که عامل در آن اقداماتی انجام می‌دهد (در مثال ما محیط همان صفحه بازی شطرنج است).
3. اقدام: حرکتی که عامل انجام می‌دهد و منجر به ایجاد تغییراتی در محیط می‌شود.
4. پاداش: پس از ارزیابی اقدام، پاداشی مثبت یا منفی به عامل داده می‌شود؛ البته دادن پاداش ممکن است با تأخیر همراه باشد.

چنان‌که در مقاله «Reinforcement Learning and Supervised Learning: A brief comparison» آمده است، تفاوت‌های اصلی یادگیری تقویتی با سایر تکنیک‌ها در این است که ذات این الگوریتم برپایه آزمون و خطا و پاداش مؤخر است. برای درک بهتر تفاوت‌های یادگیری تقویتی با سایر تکنیک می‌توانید به مقالات «Reinforcement Learning, Part 2: Introducing Markov Process» و «Reinforcement Learning, Part 3: The Markov Decision Process» مراجعه نمایید.

محیط یادگیری تقویتی را می‌توان با استفاده از فرایند تصمیم‌گیری مارکوف (MDP) Markov Decision Process (MDP)  مدل‌سازی کرد. فرایند تصمیم‌گیری مارکوف برای ما یک چارچوب ریاضیاتی فراهم می‌کند که برای مدلسازی تصمیم‌گیری‌های متوالی در شرایطی که نیمی از خروجی‌ها تصادفی و نیمی دیگر تحت کنترل تصمیم‌گیرنده هستند (دقیقاً همچون بازی‌هایی که ما تنها قادر به کنترل حرکات خود هستیم و کنترلی بر حرکات رقیب نداریم)، استفاده می‌شود. عامل در محیط MDP باید سیاست بهینه برای حداکثرسازی پاداشش را پیدا کند.

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

https://youtu.be/my207WNoeyA

یادگیری Q

حال باید راهی برای پیدا کردن سیاست بهینه پیدا کنیم. انسان‌ها چگونه می‌توانند بهترین راه‌حل ممکن را برای هر یک از شرایط صفحه بازی پیدا کنند؟

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

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

ویدیوی زیر که توسط تیم Udacity تهیه شده، تفاوت بین محیطی که توسط عامل مدل شده و محیطی که عامل با آن در تعامل است را به خوبی نشان می‌دهد:

https://youtu.be/2xATEwcRpy8

در این‌جاست که متد یادگیری Q به کمک ما می‌آید. یادگیری Q یک الگوریتم یادگیری تقویتی است که از طریق حداکثرسازی پاداش بلندمدت و با توجه به تمامی وضعیت‌های بعد از وضعیت کنونی (برنامه‌ریزی)، سیاست بهینه را می‌آموزد. اگر زمان یادگیری الگوریتم یادگیری Q، نامحدود باشد، این الگوریتم می‌تواند بهترین سیاست و سیاست نیمه تصادفی را یاد بگیرد. برای جزئیات بیشتر به مقاله « Explaining Reinforcement Learning: Active vs Passive» مراجعه کنید.

نتیجه‌گیری

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

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

1. اگر تنها یک «بهترین حرکت» داشته باشیم، چگونه می‌توانیم بدون پردازش تمامی وضعیت‌های بعدی (به دلیل ضیق وقت) آن را پیدا کنیم؟
2. اگر زمان و منابع محاسباتی ما محدود باشند، چطور می‌توانیم بهترین حرکتی که منجر به پاداش بلندمدت می‌شود را پیدا کنیم؟

برای یافتن پاسخ این مسائل در مقاله بعدی مفاهیم مربوط به درخت جستوجوی مونت کارلو و راه‌حل‌هایی که برای این مسائل ارائه می‌دهد را بررسی خواهیم کرد.