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

/
/
/

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

نظریه تكاملی بازیها، روشی متفاوت برای تحلیل بازیهاست . به جای تحلیل مستقیم خواص یك بازی، جامعه ای از بازیكنان با استراتژیهای مختلف، شبیه سازی شده و از روشهایی مشابه روش انتخاب طبیعی برای تعیین چگونگی تكامل آنها استفاده میشود.
الگوریتم های هم تکاملی نیز مانند الگوریتم های تکاملی از طبیعت الهام گرفته شده اند. الگوریتم های هم تکاملی مشتق شده از الگوریتم های تکاملی هستند و مجموعه های چند گانه از گونه ها را شبیه سازی می کنند. در مسائلی مثل game strategy فضای جستجو خیلی بزرگ است و تعریف تابع برازندگی مشکل می باشد و حل چنین مسائلی با استفاده از الگوریتم های تکاملی بسیار دشوار می باشد به همین منظور برای حل چنین مسائلی الگوریتم های هم تکاملی را به کار میگیرند.
Coevolution یا هم تکاملی یعنی چند جمعیت با هم در محیطی زندگی می کنند که منابع محدودی به اشتراک گذاشته شده است.
دو نوع الگوریتم هم تکاملی وجود دارد:
cooperative/symbiotic و competitive یعنی مشارکتی/تعاونی و رقابتی
الگوریتم های تعاونی:
مدلی از هم تکاملی است که در آن تعدادی از گونه های مختلف هریک بخشی از مسئله را نمایش می دهند، در این نوع مدل individualهای تعامل، یا با هم شکست می خورند یا با هم موفق می شوند. پس در تعامل دو individual اگر fitness یکی افزایش یابد fitness دیگری هم افزایش می یابد و همچنین اگر fitness یکی کاهش یابد fitness دیگری نیز کاهش می یابد. مزیت این روش این است که اجازه تجزیه تابع موثر را می دهد. البته اشکال آن نیز این است که به کاربر به منظور فراهم آوردن یک بخش بندی مناسب از مسئله متکی می شود. در وظایف خاصی مثل تعقیب و گریز (multiagent)، عامل ها نیاز به هماهنگی رفتارشان برای به دست آوردن هدف مشترک دارند. به همین منظور می توان با استفاده از الگوریتمهای تعاونی رفتار هماهنگی بین عامل ها برقرار کرد. این روش در بازی های گروهی روبوکاپ مورد استفاده قرار می گیرد.
الگوریتم های رقابتی:
در هم تکاملی رقابتی، individualها مقابل یکدیگر برای به دست آوردن fitness رقابت می کنند. این individualها ممکن است از یک گونه باشند و یا از گونه های مختلف. پس موقع تعامل دو individual اگر fitness یکی افزایش یابد fitness دیگری کاهش می یابد. کاربرد این روش در Game player و Trading بوده و از مزایای آن این است که به تابع برازندگی ثابت نیاز ندارد و تمایل به گریز از بهینه محلی دارد.

یادگیری بازی رامی با استفاده از روشهای هم تکاملی
رامی یک بازی ورق است که در آن بازکنان سعی می کنند ست های مختلف کارتها را جمع کنند یعنی به ترتیب ۳ کارت یا بیشتر داشته باشند یا کارتهایی با مقدار یکسان داشته باشند. این بازی یک بازی تصادفی است چون کارتها در هر بازی بر می خورند.
در مقاله ای بین بازیکنان رامی که از طریق تکنیک های هم تکاملی یاد می گیرند با بازیکنانی که از طریق روش temporal-difference آموزش دیده اند مقایسه انجام شده است. دراین روش هم تکاملی که به آن Evo-Rummy گفته شده از دو جمعیت بازیکنان استفاده می شود. بازیکنان دو بازی انجام می دهند که در هر بازی از شرایط شروع یکسان استفاده می کنند ولی بازیکن و حریف در هر بازی جابجا می شوند. بعد از انجام بازیها، شبکه حریف بصورت تصادفی با یک مقدار کوچک mutated می شود (تغییر می یابد). اگر بازیکن دو بازی یا بیشتر را ببرد شبکه وی تغییر نمی کند در غیر این صورت وزن شبکه بازیکن ۵% در جهت وزن شبکه حریف جابجا می شود. چون تنها دو بازیکن داریم این ساده ترین محیط هم تکاملی میان مطالعات انجام شده دیگر است. نویسندگان این مقاله اظهار کرده اند که بازیکنان Evo-Rummy آنها از بازیکنانی که با روش های دیگر یاد گرفته اند بهتر عمل کرده و بدترین بازیکن Evo-Rummy آنها ۶۵% بازی هایی را که در فاز اعتبار سنجی انجام داده، برده است. در این مثال هم تکاملی، دو بازیکن از هر جمعیت در مقابل هم مسابقه می دهند با این وجود علی رغم به دست آوردن fitness points، بازیکن بازنده وزن شبکه را به نزدیکی وزن شبکه بازیکن برنده تغییر می دهد.
مدل PSO (بهینه سازی ازدحام ذرات) هم از هم تکاملی مشارکتی استفاده می کند و هم از هم تکاملی رقابتی. می توان از بهینه سازی ازدحام ذرات برای به کار گیری ایجنت های بازی در مضمون هم تکاملی استفاده کرد و این کار را می توان با تعلیم ایجنت ها با دانش صفر در هر استراتژی بازی انجام داد.
از اهداف دیگر استفاده از این روش این است که می توان یک فریمورک عمومی برای یادگیری استراتژی بازیها با استفاده از رویکرد PSO هم تکاملی ارائه کرد و نشان داد که این فریمورک چگونه می تواند در بازی های مختلف به کار گرفته شود و معیاری برای ارزیابی عملکرد آن ارائه داده و نتایج آن را روی بعضی بازی ها نمایش داد.
در این روش حداقل دانشی که از قبل مورد نیاز است به این صورت است که نیازی به دانشی درباره استراتژی بازی نیست ولی درباره قوانین بازی و حالت فعلی باید دانش وجود داشته باشد. نتیجه بازی بصورت برد، باخت یا مساوی است.

الگوریتم هم تکاملی PSO عمومی
مورد استفاده برای بازی های Deterministic TicTacToe، چکرز، IPD، Bao و Probabilistic TicTacToe
الگوریتم هم تکاملی PSO عمومی از PSO برای تنظیم وزن ها استفاده می کند.
الگوریتم آن بصورت زیر است:
ازدحامی از شبکه های عصبی را ایجاد و بصورت تصادفی مقدار دهی اولیه کن؛
تکرار
بهترین موقعیت های فردی را به competition pool اضافه کن؛
همه ذرات را به competition pool اضافه کن؛
برای هر ذره (یا شبکه عصبی) کارهای زیر را انجام بده
بصورت تصادفی گروهی از رقبا را از competition pool انتخاب کن؛
برای هر حریف کارهای زیر را انجام بده
چند بازی علیه رقبا انجام بده؛
به عنوان بازیکن اول بازی کن؛
برد، باخت یا مساوی شدن بازی را ثبت کن؛
تعدادی بازی را علیه رقبا به عنوان بازیکن دوم بازی کن؛
برد، باخت یا مساوی شدن بازی را ثبت کن؛
پایان
برای هر ذره یک امتیاز تعیین کن؛
بهترین موقعیت فردی جدیدی بر اساس امتیازات محاسبه کن؛
پایان
بهترین موقعیت همسایه را محاسبه کن؛
سرعت ذره ها را به روز رسانی کن؛
موقعیت ذرات را به روز رسانی کن؛
تا زمانی که شرط خاتمه True شود؛
بهترین ذره کلی را به عنوان ایجنت بازی بر گردان؛
چند بازی دیگر

بازی چکرز:
مدل این بازی تشکیل شده از درخت بازی، تابع ارزیابی شبکه عصبی نودهای برگ درخت بازی و جمعیت شبکه های عصبی (تابع ارزیابی). فرایند آموزش آن بصورت رقابتی، مبتنی بر تنها یک جمعیت است. تابع fitness نسبی آن عبارتست از امتیاز دهی به هر فرد بر اساس عملکرد در مقایسه با گروهی تصادفی از افراد و تخصیص وزن بر اساسEP
فضای حالت: ۱۰۱۸
مکانیزم امتیاز دهی: ۱ (برد)، ۰٫۵ (مساوی)، ۰٫۰ (باخت)
معماری شبکه عصبی: تابع فعالیت سیگموید
۳۲ واحد ورودی: (۱٫۰ برای نمایش شاه، ۰٫۷۵ برای نمایش سربازهای شما، ۰٫۵ برای نمایش فضاهای خالی، ۰٫۲۵ برای نمایش سربازهای دشمن، ۰٫۰ برای نمایش شاه دشمن) ، ۱ واحد خروجی

بازی Deterministic TicTacToe
مکانیزم امتیازدهی: ۱(برد)، ۰(مساوی)، ۲-)باخت)
معماری شبکه عصبی: تابع فعالیت سیگموید
۹ واحد ورودی: (۰٫۱ برای نمایش مهره خودتان، ۰٫۰ برای نمایش مهره حریف، ۰٫۵ برای نمایش فضاهای خالی)، ۱ واحد خروجی
بازی Probabilistic TicTacToe
قوانین بازی: بورد ۴X4X4، تاس ۴ طرفه سالم برای تعیین سطح بازی، اگر حرکتی را روی آن سطح نتوان انجام داد بازیکن آن دور را از دست می دهد، زمانی که هیچ فضای خالی باقی نماند بازی تمام می شود، بازیکنی که کامل ترین سطر، ستون یا قطر به طول ۴ را دارد برنده است.

معماری شبکه عصبی: تابع فعالیت سیگموید
۶۴ ورودی: (۰٫۵ برای نمایش مهره شما، -۰٫۵ برای نمایش مهره حریف، ۰٫۰ برای نمایش فضاهای خالی)، ۱ واحد خروجی
بازی Bao
فضای حالت : ۱۰۲۵
بورد آن به شکل زیر است:

اجزا:
Kitchwa (حفره های کناره های سطر دوم)، Kimbi( حفره های سطر دوم)، Nyumba (5 امین حفره سطر دوم)، ۶۴ تا Kete یا سنگ/مهره
هدف:
گرفتن Kete سطر جلویی رقیب، جلوی حریف را برای انجام هر حرکت مجاز گرفتن
حالت اولیه بورد:
هر بازیکنی با ۱۰ Kete روی بورد شروع می کند، ۶Kete در Nyumba، ۲ Kete در Kimbi به سمت راست Nyumba ، ۲Kete در Kimbi بعدی، South اولین حرکت را انجام می دهد
معماری شبکه عصبی: تابع فعالیت سیگموید
۳۲ واحد ورودی با مقادیری که نشان دهنده تعداد مهره ها در حفره متناظر است

مراجع:
Particle Swarm Optimisation for Learning Game Strategies, AP Engelbrecht, Department of Computer Science, University of Pretoria, South Africa engel@cs.up.ac.za

Using Evolutionary Computing to Develop Game Strategy for a Non-Deterministic Game, by Kevin Mukhar

http://artificial.ir/intelligence/thread13174.html

http://ce.sharif.edu/~msafari/courses/GAME_87F/FinalProjects/Mayssam%20-%20EGT.pdf

نظر بدهید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

It is main inner container footer text