نظریهٔ بازی و یادگیری ماشین: از ایده‌های کلاسیک تا ایده‌های نو
يكشنبه, ۱۱ اسفند ۱۳۹۸، ۰۴:۳۴ ب.ظ
نظریهٔ بازی یکی از حوزه‌های شگفتی‌آفرین ریاضیست که بر فیلد‌های مختلفی مانند اقتصاد، جامعه‌شناسی، زیست‌شناسی و (صدالبته) علوم کامپیوتر تاثیر گذاشته است. راه‌های بسیاری برای تعریف نظریهٔ بازی وجود دارد ولی شاید بتوان نظریهٔ بازی را در ساده‌ترین و گویا‌ترین حالت ممکن در جملهٔ زیر خلاصه کرد:
نظریهٔ بازی عبارت است از احتمالات به همراه مشوّق‌ها (incentives).
بازی‌ها نقشی کلیدی در تکامل هوش مصنوعی بازی می‌کنند، حتی برای کسانی هم که تازه شروع به یادگیریِ یادگیری ماشینی می‌کنند. از همین روی شاهد افزایش محبوبیت رویکردهایی مانند Reinforcement Learning (یادگیری تقویتی) و یا Imitation Learning (یادگیری تقلیدی) هستیم.
در تئوری، هر سامانهٔ هوش مصنوعیِ چندعامله (Multi-agent) را می‌توان گیمیفای (Gamify) کرد. شاخه‌ای از ریاضیات که فرمول‌بندی‌های این بازی را انجام می‌دهد، نظریهٔ بازی نام دارد. ما در آن دسته از سامانه‌های هوش مصنوعی و یادگیری عمیق که در آن عامل‌های مختلف (agents) باید با یکدیگر در تعامل باشند تا به هدف مشخصی نائل شوند، از نظریهٔ بازی استفاده می‌کنیم.
تاریخچهٔ نظریهٔ بازی و هوش مصنوعی با هم پیوند خورده. بسیاری از پژوهش‌های فعلیِ نظریهٔ بازی به فعالیت‌های پیشتازان علوم کامپیوتر مانند الن تیورینگ (Alan Turing) یا جان فون نیومن (John Von Neumann) باز می‌گردد. مبحث معروف «تعادل نَش (Nash Equilibrium)» که در فیلم یک ذهن زیبا (A beautiful mind) با بازی راسل کرو هم به آن پرداخته شده، سنگ بنای تعاملات (interactions) سامانه‌های هوش مصنوعی مدرن است. برای داشتن درکی واضح‌تر از تلفیق نظریهٔ بازی و هوش مصنوعی، بهترین کار شناختن انواع «بازی» است که ما در معاملات اقتصادی یا مناسبات اجتماعی با آن روبرو می‌شویم. در نظریهٔ بازی، محیط بازی همانند اهداف و مشوّق‌های بازیکن‌ها متنوع است.
اما چگونه می‌توان اصول نظریهٔ بازی را با سیستم‌های هوش مصنوعی تلفیق کرد؟ این یک چالش است و در مباحثی مانند یادگیری تقویتی چند عامله (Multi-agent Reinforcement learning) به آن پرداخته می‌شود.
شرط لازم برای آن که یک سناریوی هوش مصنوعی، کاندیدای مناسبی برای استفاده از نظریهٔ بازی باشد، این است که بیش از یک شرکت‌کننده (Participant) داشته باشد. برای مثال یک سامانهٔ پیش‌بینی فروش (مانند سامانهٔ اینشتین شرکت Salesforce) کاندید مناسبی نیست، چون که فقط یک شرکت‌کننده (بخوانید هدف یا مشوّق که همان افزایش فروش است) دارد. به هر حال، در سامانه‌های چندعامله (Multi-agent)، نظریهٔ بازی به صورت شگفتی‌آوری می‌تواند بهینه باشد. معماریِ دینامیکِ بازی در یک سامانهٔ هوش مصنوعی می‌تواند در دو گامِ اساسی خلاصه شود:
طراحی شرکت‌کننده (Participant): نظریهٔ بازی می‌تواند برای بهینه‌سازی تصمیم شرکت‌کننده در راستای افزایش سودمندی (utility) استفاده شود.
طراحی سازوکار (Mechanism): «نظریهٔ بازیِ معکوس (Inverse game theory)» بر روی طراحی بازی برای گروهی از شرکت‌کنندگان «آگاه (Intelligent)» تمرکز دارد. برای مثال، می‌توان مزایده را مثالی کلاسیک از یک مکانیسم در نظر گرفت.
5 مدل بازی که هر متخصص داده‌ای باید آن‌ها را بشناسد
فرض کنید شما می‌خواهید یک سامانهٔ هوش مصنوعی که از چند عامل (agent) تشکیل شده و این عامل‌ها با یکدیگر همکاری و رقابت خواهند کرد (تا به هدف مشخصی برسند) را مدل‌سازی کنید. این یک مثال کلاسیک از نظریهٔ بازی است. شناخت انواع مختلفِ دینامیکِ نظریهٔ بازی در یک محیط، گامی کلیدی در طراحی سیستم‌های هوش مصنوعی گیمیفای شده و بهینه است. در سطوح بالا، 5 دسته‌بندی برای سناریوهای مختلف نظریهٔ بازی داریم.
متقارن و نامتقارن (Symmetric vs Asymmetric)
یکی از ساده‌ترین دسته‌بندی‌ها برای بازی‌ها، دسته‌بندی آن‌ها بر اساس تقارن آن‌هاست. یک سامانهٔ متقارن، سامانه‌ایست که در آن بازیکن‌ها اهداف یکسانی دارند و نتیجهٔ بازی را استراتژی بازیکن‌ها رقم می‌زند؛ مثل شطرنج.
بسیاری از وضعیت‌هایی که در دنیای واقعی با آن‌ها مواجه می‌شویم، (از دیدگاه ریاضی) نامتقارن‌اند، چرا که شرکت‌کننده‌ها اهداف متفاوت و حتی اهداف متضاد دارند. مذاکرات تجاری نمونه‌ای از بازی‌های نامتقارن‌اند، چرا که هر کدام از طرفین مذاکره، اهداف متفاوتی دارند و نتایج خود را از دیدگاه‌های متفاوتی می‌سنجند. (برای مثال یکی از طرفین به دنبال بستن قرار داد است در حالی که طرف دیگر در تلاش برای سرمایه‌گذاری کمتر است.)
کامل و ناقص (Perfect vs Imperfect)
این دسته‌بندی بر اساس میزان اطلاعات در دسترس صورت می‌گیرد. یک بازی کامل (از منظر اطلاعات) بازی‌ایست که در آن هر شرکت‌کننده می‌تواند تصمیمات و حرکت‌های طرف دیگر را ببیند؛ مثل شطرنج. امروزه تعاملات مدرن اکثراً در محیط‌هایی صورت می‌گیرند که در آن بازیکن‌ها حرکت‌های خود را از یکدیگر پنهان می‌کنند و از دیدگاه نظریهٔ بازی، این محیط‌ها ناقص (Imperfect) هستند. بازی‌های ورق (مثل پوکر) تا سناریوهای ماشین‌های خودران مثال‌هایی از سیستم‌های ناقص‌اند.
ویکی‌پدیا‌ی فارسی این نوع از دسته‌بندی را با عنوان «با آگاهی کامل – بدون آگاهی کامل» معرفی کرده.
شراکتی و غیرشراکتی (Cooperative vs Non-Cooperative)
یک بازی شراکتی (یا تعاونی) محیطی‌ست که در آن شرکت‌کننگان می‌توانند برای افزایش و بهبود نتایجشان با یکدیگر وارد همکاری شوند.مذاکرات پیمانی (قراردادی) اغلب در این دسته قرار می‌گیرند. محیط‌های غیرشراکتی، محیط‌هایی هستند که در آن بازیکن‌ها از همکاری با یکدیگر منع شده‌اند؛ مثل جنگ.
مقارن و دنباله‌ای (Simultaneous vs Sequential)
یک بازی دنباله‌ای، محیطی‌ست که در آن هر بازیکن اقدامات و حرکت‌های قبلی بازیکن حریف را می‌بیند. بازی‌های کارتی (Board Games) در این دسته قرار می‌گیرند. بازی‌هایی که در آن بازیکن‌ها می‌توانند همزمان (مقارن) با هم حرکت کنند، مقارن نام دارند؛ مثل معاملات کارگزاری‌های بورس.
مجموع-صفر و مجموع-ناصفر (Zero-Sum vs Non-Zero-Sum)
بازی مجموع-صفر به سناریوهایی اشاره دارد که در آن سود یک (یا چند) بازیکن به معنای ضرر یک (یا چند) بازیکن دیگر است. بازی‌های مجموع-ناصفر بازی‌هایی هستند که در آن چند بازیکن می‌توانند از تصمیم‌های یک بازیکن سود ببرند. معاملات اقتصادی، که در آن بازیکن با هم همکاری می‌کنند تا ظرفیت بازار خود را افزایش دهند، گونه‌ای از بازی‌های مجموع-ناصفر است.
تعادل نَش (Nash Equilibrium)
اکثر سناریوهای هوش مصنوعی، از نوع متقارن هستند و بسیاری از آن‌ها بر اساس یکی معروف‌ترین مباحث ریاضی سدهٔ گذشته مدل‌سازی می‌شوند: تعادل نش. تعادل نش وضعیتی را توصیف می‌کند که در آن هر بازیکن یک استراتژی را انتخاب می‌کند و از تغییر دادن آن (مادامی که سایر بازیکن‌ها استراتژی خود را تغییر نداده‌اند) سودی نمی‌برد. نعادل نش به طرز خارق‌العاده‌ای قدرتمند است ولی در برابر سناریوهای نامتقارن به کار نمی‌آید.
به زبان ساده، تعادل نش فرض می‌کند که هر شرکت‌کننده توان پردازشی نامحدود دارد (که می‌دانیم در دنیای واقعی چنین چیزی ممکن نیست.) همچنین اکثر مدل‌های تعادل نش در آنالیز و برخورد با ریسک ضعیف عمل می‌کنند (که در مواردی مانند بازارهای مالی ضعف بزرگی به شمار می‌آید.) در نتیجه استفاده از تعادل نش در سناریوهای نامتقارن ساده نیست و این مورد در بحث سامانه‌های هوش مصنوعی چندعامله حائز اهمیت است.
ایده‌هایی نو در نظریهٔ بازی که یادگیری ماشین را تحت تأثیر قرار می‌دهد
1. Mean field Games
تئوری Mean Field Games شاخه‌ای نسبتاً جدید است که از سال 2006 مورد بررسی قرار می‌گیرد. از نظر مفهومی، Mean Field Games از روش‌ها و تکنیک‌هایی برای مطالعهٔ بازی‌هایی تفاضلی (Differential) با جمعیت بالایی از بازیکن‌های منطقی تشکیل یافته‌است که تعادل نشِ تعمیم‌یافته برای مطالعهٔ سیستم‌ها استفاده می‌کند. این بازیکن‌ها صرفاً بر اساس دارایی‌های خود (مانند سرمایه، پول و...) تصمیم نمی‌گیرند، بلکه به توزیع دارایی‌های باقی‌مانده در سیستم بین بازیکن‌های دیگر نیز اهمیت می‌دهد.
یک مثال کلاسیک از کارکرد Mean Field Games، چگونگی رفتار دسته‌ای ماهی‌ها (در حرکت‌کردن و...) ست. از منظر نظری، این پدیده به سختی توجیه می‌شود اما ریشه در این واقعیت دارد که ماهی‌ها به رفتار نزدیک‌ترین دستهٔ اطراف خود واکنش نشان می‌دهند. به عبارت بهتر، هر ماهی به رفتار تک تکِ ماهی‌ها واکنش نشان نمی‌دهد، بلکه ماهی‌های اطراف خود را به صورت یک دسته در نظر می‌گیرد. از این رو ماهی‌ها دسته‌های بزرگی را تشکیل می‌دهند که به سوی مشخصی (به صورت هماهنگ) حرکت می‌کنند.
اگر بخواهیم به زبان ریاضی صحبت کنیم، واکنش هرکدام از ماهی‌ها به اکثریت اطراف خود، تئوری همیلتون-جاکوبی-بلمن (Hamilton-Jacobi-Bellman) و تجمیع رفتار فردی ماهی‌ها (که نشانگر رفتار کلیت دستهٔ ماهی‌هاست) تئوری فوکر-پلانک-کولوموگروف (Fokker-Planck-Kolmogorov) نامیده می‌شود. تئوری Mean Field Games ترکیب این دو تئوریست.
2. بازی‌های کاتوره‌ای (Stochastic games)
ریشه‌های این ایده به دههٔ پنجاه میلادی باز می‌گردد. از نظر مفهومی، بازه‌های کاتوره‌ای (=رندوم) توسط تعداد محدودی بازیکن در در فضای حالتِ (State space) محدود بازی می‌شود و در هر حالت، بازیکن یکی از گزینه‌ها (که می‌دانیم تعداد انتخاب‌ها نیز محدود است) را انتخاب می‌کند و برآیند تصمیم‌ها یک پاداش (یا جزا) برای هر بازیکن مشخص کرده و یک توزیع احتمال موفقیت برای هر بازیکن ترسیم می‌کند.
بگذارید بار دیگر یک مثال کلاسیک بزنیم. میز گردی را تصور کنید که n+1 فیلسوف در دور آن نشسته‌اند (می‌دانیم که n≥1) یک کاسه برنج در وسط میز قرار دارد. بین هر دو فیلسوفی که کنار هم نشسته‌اند، یک چنگال قرار دارد که توسط هر دو فیلسوف قابل دسترسی است. از آن جایی که میز گرد است، به تعداد فیلسوف‌ها چنگال داریم. برای آن که فیلسوف بتواند از کاسه برنج بردارد، باید از هر دو چنگال (که در اطراف او هستند) استفاده کند. از این روی، اگر یک فیلسوف بتواند غذا بخورد، دو فیلسوف اطرافش نخواهند توانست. زندگی هر فیلسوف از دو جزء ساده تشکیل یافته، خوردن و فکر کردن؛ برای زنده ماندن یک فیلسوف، مکرراً، هم باید فکر کند و هم باید غذا بخورد. مأموریت ما، طراحی یک پروتکل است که در آن همهٔ فیلسوف‌ها زنده بمانند.
3. بازی‌های تکاملی (Evolutionary games)
بازی‌های تکاملی، همانطور که از نامش پیداست، از نظریهٔ تکامل داروین الهام می‌گیرد و از دههٔ هفتاد میلادی برای پیش‌بینی نتیجهٔ استراتژی‌های رقابتی مورد استفاده قرار می‌گیرد. از نظر مفهومی، بازی‌های تکاملی، کاربرد مفاهیم نظریهٔ بازی در موقعیت‌هاییست که در آن گروهی از عامل‌ها (agents) با استراتژی‌ها و رویکرد‌های متنوع، در طول زمان در طی یک فرایند تکاملی انتخاب و تکثیر (Selection and Duplication) با یکدیگر وارد تعامل می‌شوند تا یک راه‌حل (نتیجه) پایدار پیدا کنند. ایدهٔ اصلی پشت این تئوری، این است که تعامل اعضاء بازی، رفتار بسیاری از اعضا را شکل می‌دهد، و موفقیت هر عضو به طریقهٔ برخورد استراتژی وی با رفتار رقبایش بستگی دارد. در حالی که تئوری‌های کلاسیک نظریه بازی بر استراتژی‌های استاتیک (نامتغیر با زمان) تکیه دارد، رویکرد تکاملی بر استراتژی‌هایی تمرکز دارد که با مرور زمان تغییر می‌کنند و رفته رفته بهتر و بهتر می‌شوند. در واقع استراتژی‌ای موفق است که در فرایند تکاملی رفته رفته بهبود یابد و تغییر کند.
نظریهٔ بازی، به خاطر تکامل هوش مصنوعی، در حال تجربهٔ یک رزونانس است و ما روز به روز بیشتر با آن در سرویس‌های هوشمند مواجه خواهیم شد.
برگردان از «A Crash Course in Game Theory for Machine Learning: Classic and New Ideas» با اندکی دخل و تصرف.