چگونه جستجوی درخت مونت کارلو با استفاده از فرمول UCB1 بین اکتشاف و بهره‌برداری تعادل ایجاد می‌کند

برای اینکه یک هوش مصنوعی بتواند آینده را جستجو کند، ابتدا باید یک شبیه‌ساز بی‌نقص از زمان حال در اختیار داشته باشد. جستجوی درخت مونت کارلو (MCTS) تنها در صورتی می‌تواند میلیون‌ها پیامد بالقوه را ارزیابی کند که قوانین محیط کاملاً شناخته‌شده و قطعی باشند. در بازی‌های رومیزی مانند شطرنج یا گو، این محدودیت به طور کامل صدق می‌کند؛ اما در دنیای فیزیکی رباتیک، به موتورهای فیزیک بسیار دقیقی نیاز است. زمانی که این مدل پیش‌رونده وجود داشته باشد، MCTS به یکی از قدرتمندترین الگوریتم‌های تصمیم‌گیری در علوم کامپیوتر تبدیل می‌شود.[1]

در هسته MCTS دوراهی‌ای به قدمت خود نظریه تصمیم‌گیری وجود دارد: اینکه آیا باید از یک مزیت شناخته‌شده بهره‌برداری کرد یا یک احتمال ناشناخته را کشف کرد. اگر یک الگوریتم فقط بهره‌برداری کند، در بهینه‌های محلی گرفتار می‌شود؛ یعنی یک حرکت خوب انجام می‌دهد اما یک حرکت درخشان را از دست می‌دهد. اگر فقط اکتشاف کند، منابع محاسباتی خود را برای ارزیابی انتخاب‌های وحشتناک هدر می‌دهد.[1][2]

راه‌حل ریاضی این مشکل در سال ۲۰۰۲ به دست آمد، زمانی که پژوهشگرانی به نام‌های پیتر اوئر، نیکولو چزا-بیانکی و پل فیشر مقاله‌ای منتشر کردند که در آن الگوریتم کران بالای اطمینان (UCB1) به تفصیل شرح داده شده بود. آن‌ها در ابتدا این الگوریتم را برای مسئله «راهزن چندبازو» طراحی کردند؛ یک سناریوی نظری که در آن یک قمارباز باید بدون دانستن شانس‌های زیربنایی، انتخاب کند که با کدام ماشین‌های اسلات بازی کند تا بیشترین سود را به دست آورد.[2]

در سال ۲۰۰۶، دانشمندان علوم کامپیوتر، لِوِنته کوچیس و چابا سپسواری، فرمول UCB1 را روی گره‌های یک درخت تصمیم‌گیری اعمال کردند و الگوریتم کران‌های بالای اطمینان اعمال‌شده روی درخت‌ها (UCT) را خلق کردند. این تلفیق به هوش مصنوعی اجازه داد تا با در نظر گرفتن هر گره در درخت به عنوان یک مسئله راهزن چندبازوی مجزا، در میان احتمالات شاخه‌دار مسیریابی کند.[1][2]

فرمول UCB1 از دو نیمه مجزا تشکیل شده است که با هم جمع می‌شوند. نیمه اول، عبارت بهره‌برداری است: نرخ برد تخمینی فعلی یک گره خاص، که به صورت درصدی بین ۰ و ۱ بیان می‌شود. اگر یک حرکت رباتیک شبیه‌سازی‌شده در ۸۰ مورد از ۱۰۰ آزمایش موفقیت‌آمیز بوده باشد، ارزش بهره‌برداری آن ۰.۸۰ است.[1]

نیمه دوم، عبارت اکتشاف است که از نظر ریاضی الگوریتم را مجبور می‌کند تا به گزینه‌های نادیده‌گرفته‌شده نگاه کند. این مقدار به عنوان جذر لگاریتم طبیعی کل بازدیدهای گره والد، تقسیم بر کل بازدیدهای گره فرزند محاسبه می‌شود.[1][2]

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

این دو نیمه توسط یک پارامتر تنظیم‌کننده به نام C میانجی‌گری می‌شوند که معمولاً روی جذر عدد ۲ (تقریباً ۱.۴۱۴) تنظیم می‌شود. تنظیم این ثابت، شخصیت عملیاتی هوش مصنوعی را دیکته می‌کند. مقدار C بالاتر، یک عامل کنجکاو و کاوشگر ایجاد می‌کند؛ در حالی که مقدار C پایین‌تر، یک عامل بی‌رحم و بهره‌بردار می‌سازد.[1]

با نرمال‌سازی عبارت اکتشاف UCB1 در سه سناریوی مختلف شمارش بازدید، تحلیل تحریریه فکت‌لن نشان می‌دهد که پاداش اکتشاف به صورت لگاریتمی کاهش می‌یابد، نه خطی. به طور خاص، گرهی که برای ۱۰۰ بازدید والد نادیده گرفته شده است، وزن اکتشافی برابر با ۰.۳۰ دارد، اما نادیده گرفتن آن برای ۱۰۰۰ بازدید، این وزن را تنها به ۰.۳۷ افزایش می‌دهد.[3]

این کاهش ریاضی ثابت می‌کند که UCB1 به شدت اکتشاف اولیه را در اولویت قرار می‌دهد، اما با عمیق‌تر شدن شبیه‌سازی، به سرعت به سمت بهره‌برداری دقیق تغییر جهت می‌دهد. این الگوریتم به طور پویا رفتار خود را از کنجکاو به قاطع تغییر می‌دهد، بدون اینکه نیازی باشد مهندسان ثابت C را در طول اجرا به صورت دستی تنظیم کنند.[3]

همین تعادل ریاضی خاص بود که به آلفاگو شرکت دیپ‌مایند اجازه داد تا در سال ۲۰۱۶ لی سدول را شکست دهد. آلفاگو با استفاده از MCTS تقریباً ۱۰۰,۰۰۰ موقعیت را در ثانیه ارزیابی می‌کرد و برای تصمیم‌گیری در مورد اینکه کدام شاخه‌ها از ۱۰ به توان ۱۷۰ وضعیت ممکن صفحه ارزش شبیه‌سازی عمیق‌تر را دارند، به UCB1 تکیه می‌کرد.[1][2]

همان‌طور که بررسی جامع روش‌های MCTS منتشر شده در سال ۲۰۱۲ در آرکایو اشاره می‌کند، قدرت این الگوریتم ناشی از توانایی آن در «ساخت تدریجی یک درخت جستجو، با هدایت نتایج شبیه‌سازی‌های مونت کارلو» است، که برای مدیریت رشد نامتقارن درخت کاملاً به UCB1 متکی است.[2]

الگوریتم UCB1 فرض می‌کند که کران‌های پاداش‌ها دقیقاً بین ۰ و ۱ هستند. در محیط‌هایی با پاداش‌های بی‌کران یا بسیار متغیر - مانند معاملات مالی یا رانندگی خودکار در ترافیک غیرقابل پیش‌بینی - فرمول استاندارد می‌تواند بی‌ثبات شود و برای جلوگیری از تسلط عبارت اکتشاف بر محاسبات، به نرمال‌سازی‌های پیچیده‌ای نیاز دارد.[2]

پیاده‌سازی‌های مدرن اکنون در حال فراتر رفتن از ثابت استاتیک ۱.۴۱۴ هستند. پژوهشگران در حال آموزش شبکه‌های عصبی برای پیش‌بینی پویای مقدار بهینه C برای شاخه‌های خاصی از درخت هستند، که به الگوریتم اجازه می‌دهد تشخیص دهد چه زمانی یک موقعیت به محاسبه عمیق در مقابل طوفان فکری گسترده نیاز دارد.[1][3]