جستجو درخت مونت کارلو تکاملی برای بازی های رقابتی چندعملیاتی

بازی های رقابتی چندعملیاتی نوبتی، بازی هایی هستند که در آن هر نوبت بازیکن شامل یک دنباله از اقدامات اتمی است که منجر به یک عامل انشعاب بسیار بالا می شود. بسیاری از بازی های تخته ای، کارتی و ویدیویی در این دسته قرار می گیرند. وضعیت کنونی پیشرفته ترین روش ها، برنامه ریزی تکاملی آنلاین (OEP) است که الگوریتمی تکاملی (EA) است و اقدامات اتمی را به عنوان ژن و دنباله های کامل اقدامات را به عنوان ژنوم در نظر می گیرد. در این مقاله، ما جستجوی درخت مونت کارلو تکاملی (EMCTS) را برای مقابله با این چالش معرفی می کنیم که جستجوی درخت MCTS را با بهینه سازی دنباله ای الگوریتم های تکاملی ترکیب می کند. آزمایش ها در بازی Hero Academy نشان می دهند که EMCTS به طور قانع کننده ای از چندین الگوریتم پایه، از جمله OEP و یک واریانت بهبود یافته از OEP که در این مقاله معرفی شده، در زمان های مختلف و تعداد اقدامات اتمی مختلف در هر نوبت بهتر عمل می کند. EMCTS همچنین بهتر از هر الگوریتم موجود با پیچیدگی مسئله مقیاس می شود.

کلیدواژه ها:

جستجوی درخت بازی ، جستجوی درخت مونت کارلو ، بازی های استراتژیک